Phát hiện nếu hai số bằng nhau mà không tiết lộ thêm thông tin

Matteo Monti

22:42, 29/11/2022

Hãy xem xét kịch bản sau đây. Alice chọn một số A; Bob chọn một số B. Cả A và B đều thuộc về một tập X tương đối nhỏ (ý tôi là X có thể lặp lại dễ dàng: vì trực giác, hãy tưởng tượng X có kích thước bằng một cỗ bài). Tôi muốn Alice và Bob tham gia vào một giao thức cho cả hai biết nếu A = B. Nếu A != B, thì Alice sẽ không có thêm thông tin nào về B và Bob sẽ không có thêm thông tin nào về A.

Tôi tự hỏi nếu điều này là có thể? Nếu X rất lớn, và giả sử không mất tính tổng quát rằng A là số nguyên tố, Alice có thể chọn một số nguyên tố P tùy ý lớn hơn giá trị lớn nhất trong X và gửi A * P cho Bob. Sau đó, Bob có thể thử và tính A * P theo B: nếu nó hoạt động, thì A = B. Tuy nhiên, điều này rõ ràng giả định rằng Bob không thể thử tất cả các phần tử của X. Nếu X nhỏ, giả định này ngay lập tức bị loại bỏ.

1 + 1

thiết kế giao thức

Perseids

22:13, 30/11/2022

Nhân tiện, đây được gọi là [vấn đề của các triệu phú xã hội chủ nghĩa](https://en.wikipedia.org/wiki/Socialist_millionaire_problem).

Hồi đáp

Điểm:3

Crypto

poncho

23:03, 29/11/2022

Vâng, nó là hoàn toàn có thể.

Cách tiếp cận rõ ràng là để Alice và Bob thực hiện giao thức Trao đổi khóa xác thực mật khẩu cân bằng (PAKE), với $A$ và $B$ là 'mật khẩu' của họ. Nếu họ nghĩ ra cùng một bí mật chung, $A=B$, và nếu họ nghĩ ra $A \ne B$ và họ không học bất cứ điều gì khác về $A$ và $B$

Có một số giao thức PAKE ngoài kia; xem bài viết trên wikipedia cho một số trong những cái phổ biến hơn.

Một cách như vậy (được đơn giản hóa CPACE) để so sánh các giá trị $a$ được biết đến với Alice và $b$ mà Bob biết sẽ là chọn các giá trị không liên quan $G$ và $N$ (Tôi đã viết điều này giả sử các đường cong elip; nó có thể được dịch trực tiếp sang một nhóm modp, ngoại trừ phép trừ trở thành một nghịch đảo moduluar) và:

Alice chọn một giá trị ngẫu nhiên $r$ và tính toán $C = r G + a N$; cô gửi $C$
Bob chọn một giá trị ngẫu nhiên $s$ và tính toán $D = s G + b N$; anh ấy gửi $D$
Alice tính toán $S = r (D - a N)$; Bob tính toán $T = s (C - b N)$; nếu $a=b$, sau đó $S=T$; nếu không thì chúng không liên quan.

Alice và Bob có thể gửi $S$ và $T$ với nhau (nếu họ tin tưởng phía bên kia trung thực) hoặc sử dụng cách khác để tạo khóa mã hóa và thực hiện một giao thức xác minh đơn giản.

0 + 0

Phan Văn Trường

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

EN: Detect if two numbers are equal without disclosing further information

TH: ตรวจหาว่าตัวเลขสองตัวเท่ากันหรือไม่โดยไม่ต้องเปิดเผยข้อมูลเพิ่มเติม

RO: Detectați dacă două numere sunt egale fără a dezvălui informații suplimentare

RU: Определите, равны ли два числа, не раскрывая дополнительной информации

VI: Phát hiện nếu hai số bằng nhau mà không tiết lộ thêm thông tin

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