Điểm:1

Tương quan OWF và iO

lá cờ br

Mối quan hệ giữa chức năng một chiều (OWF) và obfuscation không thể phân biệt (iO) là gì? Tôi biết rằng iO tồn tại ngay cả khi P=NP và OWF không tồn tại. Nhưng sự tồn tại của OWF có ngụ ý iO không?

Geoffroy Couteau avatar
lá cờ cn
Lưu ý rằng iO vẫn "về mặt đạo đức" ngụ ý OWF: nếu NP không có trong (thường xuyên) BPP, thì iO ngụ ý OWF - xem [tại đây](https://eprint.iacr.org/2014/347.pdf).
Điểm:4
lá cờ kr

Chúng tôi không biết bất kỳ cấu trúc nào của iO từ hàm một chiều[*], và sẽ rất ngạc nhiên nếu một thứ như vậy tồn tại. Thực vậy, iO + OWF ngụ ý mã hóa khóa công khai (và nhiều nguyên thủy âcryptomaniaâ khác), vì vậy nếu một mình OWF ngụ ý iO, thì nó cũng có nghĩa là PKE.

[*] Tại thời điểm này, chúng tôi không biết về bất kỳ cấu trúc nào của iO từ các giả định tiêu chuẩn, theo như tôi biết (xem bình luận của Geoffroy bên dưới).

Fractalice avatar
lá cờ in
Tôi đoán chúng ta không biết cách xây dựng PKE từ OWF?
lá cờ kr
Vâng, và tôi có lý do chính đáng để nghĩ rằng một công trình như vậy không nên tồn tại. Ví dụ: cấu trúc *hộp đen* được biết là không thể thực hiện được và thậm chí một số loại cấu trúc không phải hộp đen đã bị loại trừ. Xem ví dụ câu trả lời này: https://crypto.stackexchange.com/a/83929/1423
Geoffroy Couteau avatar
lá cờ cn
"Tại thời điểm này, chúng tôi không biết về bất kỳ cấu trúc nào của iO từ các giả định tiêu chuẩn, theo như tôi biết" Tôi không đồng ý, giờ đây chúng ta có các cấu trúc của iO từ các giả định hoàn toàn chính xác: LPN theo cấp số nhân trên các trường lớn + độ cứng theo cấp số nhân của Goldreich PRG + SXDH theo cấp số nhân. Tất cả đều là những giả định cũ, được nghiên cứu kỹ lưỡng, có tính hợp lý cao mà tôi gọi là tiêu chuẩn.
lá cờ kr
Đủ công bằng, tôi đã không theo dõi tất cả các kết quả gần đây!

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