Điểm:0

Tính toán không thể phân biệt bằng cách sử dụng giả định DDH

lá cờ tm

Đây là một phần giải thích về chương trình cam kết từ DDH trong bài giảng này của Vipul Goyal: https://www.cs.cmu.edu/~goyal/s18/15503/scribe_notes/lecture22.pdf

Câu hỏi của tôi không liên quan trực tiếp đến nội dung của bản pdf, nhưng ở trang 20-4, nó nói $\{g, g^a, g^b, m \cdot g^r |(a, b, r) \leftarrow \mathbb{Z}_q\}$ không thể phân biệt về mặt tính toán với $\{g, g^a, g^b, g^r |(a, b, r) \leftarrow \mathbb{Z}_q\}$. Tại sao điều đó nhất thiết phải đúng? Ai đó có thể vui lòng giải thích chính thức tại sao lại như vậy không? Ngoài ra, khi văn bản mô tả phân phối theo cách như vậy, là hai $(a, b, r)$âs trong hai phân phối bằng nhau? Hay chỉ là các ký hiệu giống nhau, nhưng trên thực tế chúng được chọn ngẫu nhiên một cách độc lập từ $\mathbb{Z}_q$?

Cảm ơn.

lá cờ us
Xin chào, chào mừng bạn đến với crypto.stackexchange. Tôi bối rối vì trang 20-4 thực sự có giải thích từng bước về lý do tại sao hai bản phân phối đó không thể phân biệt được. Có một bước cụ thể hơn mà không có ý nghĩa?
user658183 avatar
lá cờ tm
Tôi không chắc về phương trình giữa 'Nhưng' và 'Vì vậy, chúng tôi có' ở trang 20-4, nhưng tôi nghĩ câu trả lời của yacovm đã hữu ích.
Điểm:2
lá cờ us

Vâng cái này $m$ là một phần tử nào đó trong nhóm $\mathbb{G}$ vì vậy tồn tại một số $\alpha \in \mathbb{Z}_q$ như vậy mà $m=g^{\alpha}$, vì thế $m \cdot g^r = g^{\alpha+r}$ và nhận thấy rằng kể từ khi $r$ được chọn ngẫu nhiên đồng nhất từ $\mathbb{Z}_q$, sau đó phân phối của $\alpha + r$ chính xác (không chỉ về mặt tính toán mà còn chính xác) thống nhất trong $\mathbb{Z}_q$ cũng.

Bằng trực giác bạn có thể nghĩ về $r+\alpha$ như lấy $\alpha$ mà ai đó đã chọn cho bạn, rồi thêm vào đó một số ngẫu nhiên theo modulo $q$, và nó hoàn toàn đồng nhất vì với mọi kết quả có thể có của $r+\alpha$ có chính xác một $r$ mà làm cho nó có kết quả, do đó nó là thống nhất.

Đối với (a,b,r) - hãy nhớ rằng giả định DDH đang cố nói điều gì đó như: Nếu bạn nhìn vào hai phần tử nhóm ngẫu nhiên $g^a, g^b$ và bạn có một yếu tố nhóm thứ ba $h\in\mathbb{G}$, sau đó bạn không biết nếu $h=g^{a\cdot b}$ hoặc đó $h$ là một số yếu tố nhóm hoàn toàn ngẫu nhiên, không liên quan $g^r$ cho một số ngẫu nhiên $r$. Cách bạn viết điều này, là bạn xem xét hai bản phân phối trong đó $g^a, g^b$ giống nhau ở cả hai vế của đẳng thức, nhưng phần tử thứ ba thì khác (nó là một trong hai $g^{a \cdot b}$ hoặc $g^r$ và bạn nói rằng theo giả định DDH, không tồn tại một máy tính thời gian đa thức xác suất hiệu quả có thể phân biệt giữa $g^{a \cdot b}$ và một yếu tố nhóm ngẫu nhiên.

user658183 avatar
lá cờ tm
Cảm ơn! Làm thế nào về câu hỏi thứ hai? Trong các ký hiệu như vậy, các giá trị $a, b, r$ bằng nhau cho hai bản phân phối hay chúng được chọn ngẫu nhiên riêng biệt?
yacovm avatar
lá cờ us
Tôi đã cập nhật câu trả lời, hãy cho tôi biết nếu nó rõ ràng ngay bây giờ.
user658183 avatar
lá cờ tm
Vâng, tôi hiểu câu trả lời của bạn. Cảm ơn bạn rất nhiều!
yacovm avatar
lá cờ us
Không vấn đề gì, rất vui được giúp đỡ

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