Giả định Diffie-Hellman quyết định đối với Nhóm dư lượng bậc hai

đã cho $x^2$ hay $g^{x^2}$?

"vì vậy theo trực giác, hình vuông này sẽ không bị rò rỉ thông tin bổ sung"; thực ra, từ quan điểm có thể chứng minh được, thì ngược lại - nếu nó dễ tính toán, thì nó sẽ không rò rỉ bất cứ thứ gì (kẻ tấn công có thể tự tính toán nó, do đó đưa ra giá trị cho kẻ tấn công không cho anh ta biết bất cứ điều gì mà anh ta không biết' t đã biết). Ví dụ phản chứng rõ ràng nhất, giá trị $g^{xy}$ cũng khó tính toán, nhưng việc đưa ra giá trị đó cũng làm cho vấn đề của kẻ tấn công trở nên tầm thường. Tôi không nói rằng việc đưa ra giá trị $g^{x^2}$ làm cho vấn đề của kẻ tấn công trở nên dễ dàng; Tôi đang nói rằng nó không tầm thường để hiển thị.

Cho trước $x^2$ (không phải $g^{x^2}$). Vì vậy, câu hỏi của tôi là: nếu được cung cấp thêm $x^2$ này, quyết định DH có còn khó không (trong bối cảnh nhóm dư lượng bậc hai)

nhưng, chúng ta có thể tính căn bậc hai của $x^2$ trong $\mathbb{R}$ một cách dễ dàng và một trong những căn này sẽ bằng $x^2$. Do đó, thật dễ dàng để kiểm tra xem đó có phải là ddh-tuple hay không.

Câu hỏi thú vị! Tôi thấy không có giảm rõ ràng đối với các giả định tiêu chuẩn. Một gợi ý: bạn có thể bắt đầu bằng cách xem xét một phiên bản đơn giản hóa của vấn đề, khi cho $x^2 \bmod \phi(n)/4$, nhiệm vụ của bạn là phân biệt $g^x$ với một phần tử ngẫu nhiên của $\mathsf {QR}_n$.

Về nhận xét của levgeni: Nhưng trong $QR_n$, $n$ này là hỗn hợp RSA, thì việc cố gắng tìm nghiệm của dư bậc hai tương đương với việc phân tích $n$. Xem ví dụ về bài báo eurocrypt17 của Couteau: https://link.springer.com/chapter/10.1007/978-3-319-56614-6_11.

Đây là một câu hỏi tương tự mà tôi đã đăng ngày hôm qua: -- nó có tạo ra sự khác biệt nào khi mô đun là $\phi(n)/4$ hay $n$ không? https://crypto.stackexchange.com/questions/91786/group-of-quadratic-residue-over-blum-integer

Bây giờ tôi thấy điểm của $\phi(n)/4$ -- đối với $x$ theo số mũ của $g^x$. Khó khăn ở đây là nếu để lộ toàn bộ $\phi(n)$ thì $n$ sẽ được tính. Điều chúng ta có thể làm là yêu cầu một máy chủ đáng tin cậy cung cấp $r \phi(n)$ trong đó $r$ là một số nguyên ngẫu nhiên lớn. Bằng cách này, một $x^2$ đồng dư trên $r \phi(n)$ được cung cấp. Do đó, vấn đề được thay đổi một chút thành: \n Với $x^2 \mod \phi(n)/4*r$ trong đó $r$ và $\phi(n)$ không xác định, liệu có thể phân biệt được $g^ x$ bằng một thuật toán hiệu quả?

Câu hỏi này là trong các ngôn ngữ khác: