Điểm:1

PRF Xored (hoặc nhân lên) với một số ngẫu nhiên có còn là một PRF an toàn không?

lá cờ cn

Tôi biết rằng một PRF Xored với khóa của nó không phải là một PRF an toàn. Sau đó, tôi tự hỏi rằng điều gì sẽ xảy ra nếu mục Xored (hoặc nhân) là một số ngẫu nhiên khác. Biểu thức chính thức như sau:

Để cho $F_k(x):\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ là một PRF.

"$<<$" hoạt động cho biết xoay trái,"$\cdot$" hoạt động cho biết mô-đun nhân nhị phân $2^n$ ở đâu $n$-chuỗi bit được hiểu là số trong $Z_{2^n}$ và "$(a, b)$" là ước chung lớn nhất của $a$$b$.

Q1. Định nghĩa $F'_{k_1,k_2}(x) = F_{k_1}(x) \oplus k_2$, ở đâu $k_2$ được chọn thống nhất từ $\{0,1\}^n$. Sau đó $F'_{k_1,k_2}(x)$ một PRF?

Q2. Định nghĩa $F''_{k_1,k_2}(x) = (F_{k_1}(x)<<1) \oplus k_2$, ở đâu $k_2$ được chọn thống nhất từ $\{0,1\}$. Sau đó $F''_{k_1,k_2}(x)$ một PRF?

Q3. Định nghĩa $F'''_{k_1,k_2}(x) = k_2 \cdot F_{k_1}(x)$, ở đâu $k_2$ được chọn thống nhất từ $\{0,1\}^{n-1}||1$, I E. $(k_2,2^n) = 1$. Sau đó $F'''_{k_1,k_2}(x)$ một PRF?

Tôi nghĩ rằng chúng là PRF, nhưng tôi không biết làm cách nào để chứng minh điều đó một cách chính thức. $k_2$ trong Q.3 bắt buộc phải là số lẻ vì nếu là số chẵn thì $F'''$ trả về một số chẵn và không thể là PRF.

lá cờ cn
Về câu hỏi 3: Phép nhân ở đó có nghĩa là gì? Chúng tôi đang làm việc $\pmod {2^{n}}$ ở đó hay sao?
zhuo chen avatar
lá cờ cn
@Maeher Có, phép nhân biểu thị phép nhân nhị phân $\pmod {2^n}$ và đang hoạt động trong $Z_{2^n}$. Ngoài ra, $k_2$ và $F_{k_1}(x)$ được hiểu là số trong $Z_{2^n}$. Xin lỗi vì mô tả phép nhân không rõ ràng lắm do kiểu chữ và tôi đã chỉnh sửa kiểu chữ của mình.
lá cờ cn
Điều kiện đủ là phép nhân $\bmod 2^n$ với một hằng số lẻ là một hoán vị trên $\mathbb{Z}_{2^n}$. Theo trực giác, tôi cho rằng điều đó đúng, nhưng tôi không thể nghĩ ra một lý lẽ chính thức nào ngay lúc này.
zhuo chen avatar
lá cờ cn
@Maeher Vâng, tôi cũng nghĩ vậy và tôi nghĩ đây là điểm để chứng minh rằng $F'''$ là một PRF. Kiến thức liên quan đến Lý thuyết số có thể hữu ích. Tôi sẽ thử nó. Nếu tôi thành công tôi sẽ thông báo cho bạn. Cảm ơn sự giúp đỡ của bạn ~
zhuo chen avatar
lá cờ cn
Nếu $A=\{a_1,a_2,\cdots, a_m\}$ là một hoán vị thì $K=\{k \cdot a_1,k \cdot a_2,\cdots, k \cdot a_m\}$ cũng là một hoán vị trên $Z_{2^n}$, trong đó $k$ là số lẻ và $m \leq 2^n$. Bằng chứng. Giả sử $K$ không phải là một hoán vị và $k \cdot a_i \equiv k \cdot a_j \pmod {2^n}$ï¼ trong đó $i,j \in [1, m]$. Khi đó ta có $a_i \equiv a_j \pmod {2^n}$ vì $(k, 2^n)=1$, điều này mâu thuẫn với giả định. Tôi có đúng không? Và quá trình chứng minh tiếp theo chứng minh Q3 có giống với Q1 không?

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.