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

PRG từ các chức năng OW

lá cờ jp
Creeptographer

Đưa ra một chức năng OW $f:\{0,1\}^n\to\{0,1\}^n$ với vị từ hardcore $h(x)$, bạn có thể xây dựng một PRG $G$ bằng cách thiết lập $$G(s):=f(s)\Vert h(s), \quad s\leftarrow\{0,1\}^n.$$ Điều kiện mở rộng cho $G$ được thỏa mãn tầm thường (hạt giống $s$ có chiều dài $n$, trong khi chuỗi $f(s)\Vert h(s)$ có chiều dài $n+1$). Làm thế nào tôi có thể chỉ ra điều đó $G$ cũng là giả ngẫu nhiên, nghĩa là, đối với bất kỳ bộ phân biệt thời gian đa xác suất nào $\mathcal D$ $$\mid\Pr[\mathcal D(G(s)=1]-\Pr[\mathcal D(r)=1]\mid\le\epsilon(n), \quad r\leftarrow \{0, 1\}^{n+1} $$ ở đâu $\epsilon(n)$ là một chức năng không đáng kể của $n$?

41
0 + 0
lá cờ jp
Creeptographer
@kelalaka Xin lỗi, nhận xét của bạn về câu hỏi đã xóa của tôi (sự cần thiết của yêu cầu một lần đối với bảng một lần)? Nếu vậy thì tôi đã tìm thấy câu trả lời thỏa đáng [tại đây](https://crypto.stackexchange.com/questions/59/taking-advantage-of-one-time-pad-key-reuse?rq=1) rồi.
1
Hồi đáp
kelalaka avatar
lá cờ in
kelalaka
Chào mừng bạn đến với Cryptography.SE. Thông thường tìm kiếm trước sau đó hỏi. Cách tiếp cận thông thường cho loại câu hỏi này giả định rằng có một dấu phân biệt cho $G$ thì cũng có một dấu phân biệt cho $f$.
0
Hồi đáp
lá cờ jp
Creeptographer
@kelalaka Bạn có thể nói rõ hơn về điều đó không?
0
Hồi đáp
Chris Peikert avatar
lá cờ in
Chris Peikert
$f$ là một *hàm* một chiều là chưa đủ, nhưng nó đủ để nó trở thành một *hoán vị* một chiều (tức là một phép loại).
1
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.