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

Chứng minh hàm G không phải là bộ tạo giả ngẫu nhiên

lá cờ de
archie09

Một hàm G(x) = x || x (trong đó â||â biểu thị nối chuỗi). Giả sử G không phải là bộ tạo ngẫu nhiên giả. Ai đó có thể mô tả làm thế nào chúng ta có thể chứng minh điều này. Tôi hơi bối rối về khái niệm trình tạo ngẫu nhiên giả.

Những gì tôi đã hiểu cho đến bây giờ - Định nghĩa chính thức của trình tạo ngẫu nhiên giả được đưa ra là $\Pr[PRG_{A,G(n)} = 1] ⤠1/2 + negl(n)$. Ở đây chúng ta có thể quan sát thấy rằng đối với hàm G này, đầu ra sẽ có nửa thứ nhất và thứ hai bằng nhau. Làm thế nào để sử dụng điều này với định nghĩa chính thức để chứng minh rằng G không an toàn?

92
0 + 0
Maarten Bodewes avatar
lá cờ in
Maarten Bodewes
Như đã nói, đây vẫn là một nhiệm vụ không có dấu hiệu nỗ lực rõ ràng. Vui lòng [chỉnh sửa] câu hỏi để bao gồm lý do của bạn; nó không cần phải đúng, nó chỉ cần *ở đó*.
4
Hồi đáp
Marc Ilunga avatar
lá cờ tr
Marc Ilunga
Chào mừng đến với Crypto.SE! Một cách tiếp cận hữu ích ở đây là viết ra định nghĩa của PRG và các đảm bảo an ninh của một đối tượng như vậy. Từ đó, có lẽ bạn có thể thấy tại sao trường hợp cụ thể này không hoạt động? Điều này cũng có thể giúp chỉnh sửa nhận xét theo cách phù hợp (xem nhận xét đầu tiên)
2
Hồi đáp
archie09 avatar
lá cờ de
archie09
Cảm ơn bạn đã cho tôi biết. Tôi đã chỉnh sửa câu hỏi. Sẽ thực sự đánh giá cao một số trợ giúp với khái niệm này.
0
Hồi đáp
fgrieu avatar
lá cờ ng
fgrieu
@archie09: bạn đã bỏ qua rất nhiều định nghĩa chính thức về PRG.Giống như miền đầu vào và miền đầu ra, có lẽ đó là thuộc tính mở rộng (một số nguồn bỏ qua điều đó) và chắc chắn là ngữ cảnh của công thức: một cái gì đó giống như "đối với bất kỳ thuật toán Thời gian đa thức xác suất nào $\mathcal A$, có một giá trị không đáng kể function $\mathrm{negl}$ such that..." Ngoài một khía cạnh tương đối nhỏ, tôi không nhận ra công thức này là công thức theo định nghĩa của PRG mà tôi đã nghiên cứu, nhưng có thể tôi đã sử dụng một tài liệu tham khảo khác.
0
Hồi đáp
archie09 avatar
lá cờ de
archie09
@fgrieu Bạn có thể cho tôi biết một nguồn tốt mà tôi có thể tham khảo cho định nghĩa này không. Tôi đã thử tìm kiếm nhưng không thể hiểu đúng khái niệm này.
1
Hồi đáp
Maarten Bodewes avatar
lá cờ in
Maarten Bodewes
Cuối cùng, bạn sẽ có thể chứng minh bằng cách nào đó rằng một bit trong đầu ra không có cơ hội 0,5 + $e$ là 0 hoặc 1, trong khi bao gồm cả đầu ra trước đó. Điều đó sẽ được dễ dàng, phải không? Tuy nhiên, tôi không hiểu làm thế nào để làm điều đó chỉ với xác suất trong định nghĩa, vì vậy tôi sẽ để bạn làm điều đó một cách chính thức.
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.