Tham gia Đăng nhập
Điểm:0
Zoey avatar Crypto

XOR của tất cả các bit của $f(x)$ một bit lõi cứng

lá cờ cn
Zoey

Tại sao xét một cách ngẫu nhiên $r$ trong việc xây dựng một vị từ khó tính trong định lý Goldreich Levin? Tại sao không chỉ xem xét XOR của tất cả các bit của đầu vào?

76
0 + 0
lá cờ cn
Maeher
Gọi $f : \{0,1\}^n \to \{0,1\}^n$ là hàm một chiều. Xét hàm $g : \{0,1\}^n \to \{0,1\}^{n+1}$ được định nghĩa là $g(x) = g(x_1\ldots x_n) := f( x)\Vert \bigoplus_{i=1}^{n} x_i$. $g$ có phải là một chiều không? Xor của tất cả các bit đầu vào có phải là vị từ khó cho $g$ không?
2
Hồi đáp
Zoey avatar
lá cờ cn
Zoey
nó không phải vì nó là một phần của đầu ra. Nhưng tại sao không thể làm điều tương tự với . Nếu bạn đưa nó vào đầu ra thì nó cũng sẽ không quá khó phải không? Cũng không phải XOR là trường hợp đặc biệt khi r là tất cả 1?
0
Hồi đáp
lá cờ cn
Maeher
Hãy nhớ rằng GL xác định một OWF *cụ thể*, trong đó sản phẩm bên trong là cốt lõi.
0
Hồi đáp
lá cờ cn
Maeher
$r$ là một phần của *đầu vào* mà bạn không thể *đặt* nó thành bất kỳ thứ gì, nó được chọn ngẫu nhiên thống nhất. Nhưng điều quan trọng là nó không phải là một phần của đầu vào của hàm *cơ bản*, vì vậy hàm đó không thể làm được điều gì buồn cười.
1
Hồi đáp
Zoey avatar
lá cờ cn
Zoey
Hãy để tôi cố gắng hiểu ở đây: XOR bit không phải là bit khó đối với bất kỳ OWF nào vì chúng ta có thể xây dựng một trong đó XOR là một phần của đầu ra. XOR có thể là phần cứng của hàm cơ bản $f$, nó xảy ra nếu $r= 11...1$ (tất cả 1) là một lựa chọn được chọn ngẫu nhiên cho đầu vào của phép biến đổi GL của $f$, tức là $g$ .
0
Hồi đáp
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đă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.