Tiêu đề gốc: "Giao thức chứng minh không có kiến thức đầu tiên: Phần dư bậc hai"
Liên kết nguồn: Rock Bit Tác giả: Hu Peng, Cộng đồng công nghệ Ambi
Sự hiểu biết của con người về nhiều khái niệm rất lâu dài, được cập nhật liên tục và quanh co. Ngay cả khi nhiều người ngày nay đọc định nghĩa về bằng chứng không có kiến thức, họ vẫn bối rối. Đừng lo lắng, bài báo cấp Giải thưởng Turing "Sự phức tạp về kiến thức của các hệ thống chứng minh tương tác" (GMR[85]) đề xuất khái niệm này đã bị STOC, hội thảo lý thuyết máy tính hàng đầu của ngành, từ chối bốn lần liên tiếp. Có vẻ như không chỉ chúng ta mà cả những bộ óc thông minh nhất của thời đại cũng khó hiểu được ý nghĩa sâu xa của bài báo vô cùng quan trọng này.

Trong bài "Bằng chứng không có kiến thức đáng kinh ngạc", chúng tôi giới thiệu nó qua ba truyện ngắn Hiểu các khái niệm quan trọng trong bằng chứng không có kiến thức: trò chơi mù đỏ-xanh (tương tác và ngẫu nhiên), Hang Alibaba (trình mô phỏng), nhà toán học du hành (không tương tác và xác minh công khai). Nhưng từ trực giác đến định nghĩa và bằng chứng chặt chẽ, cần có một số công cụ và phương pháp luận mới. Những điều này lần đầu tiên được đưa ra bởi GMR [85] và đã được nghiên cứu và phổ biến rộng rãi kể từ đó. Giao thức chứng minh không có kiến thức chính thức đầu tiên là xác định Dư lượng bậc hai. Thông qua đó, chúng tôi giới thiệu các công cụ trong mô hình mô phỏng và bằng chứng không có kiến thức không thể phân biệt được về mặt tính toán, đồng thời đưa ra bằng chứng cần thiết.
Kiến thức nền
Phần dư bậc hai là một bài toán tồn tại từ lâu trong lý thuyết số, bắt nguồn từ việc nghiên cứu lý thuyết đồng dạng. Trong "Nghiên cứu số học", Gauss lần đầu tiên nghiên cứu một cách có hệ thống lý thuyết phần dư, tóm tắt kết quả lý thuyết của những người đi trước bao gồm Euler, Fermat, Legendre và những người khác.
Trong trường số tự nhiên, phần dư (dư lượng) và mô đun (modulus) tham khảo công thức a = nq + r r; sau khi Gauss đưa ra ký hiệu đồng dư ≡, công thức này có thể được viết tương đương là a ≡ r (mod n).
Định nghĩa: Nếu tồn tại số nguyên x sao cho a ≡ x^k (mod n), khi đó x được gọi là căn nguyên thủy thứ k của modulo n. Khi k = 2 thì a được gọi là số dư bậc hai modulo n.
Ví dụ: 12 ≡ 25 ≡ 5^2 (mod 13). Dạng lũy thừa này rõ ràng đã thu hút sự quan tâm của Gauss, người đã nghiên cứu các mối quan hệ bao gồm sự đồng đẳng bậc một, sự đồng đẳng bậc hai và sự đồng đẳng bậc cao hơn trong các tác phẩm của ông. Chúng tôi cũng sẽ đề cập đến mối quan hệ giữa sự đồng dư và lý thuyết nhóm trong một bài viết sau.
Bài toán dư bậc hai, nghĩa là, cho a, n là các số nguyên tố cùng nhau (nếu không thì a ≡ 0 (mod n)) , Xác định xem a có phải là phần dư bậc hai modulo n hay không (có căn bậc hai modulo x hay không). Khi mọi người tìm kiếm một thuật toán cho bài toán này, họ nhận thấy rằng độ khó của nó tương đương với bài toán phân tích số nguyên. Khi n là số nguyên tố thì tồn tại thuật toán thời gian đa thức, nhưng khi n là hợp số thì không thể tìm thấy thuật toán thời gian đa thức. Bài toán phần dư bậc hai là bài toán NP.
Giao thức chứng minh không có kiến thức cho bài toán dư bậc hai
GMR[85] đã sử dụng bài toán số dư bậc hai để xây dựng giao thức chứng minh không có kiến thức đầu tiên nhằm giải quyết vấn đề sau: Alice tuyên bố rằng "a là modulo Trong “Phần dư bậc hai của modulo n”, cô ấy có thể trực tiếp chỉ ra căn bậc hai của Deception, mặt khác, cũng có thể thử mọi cách để có được “thông tin bổ sung” trong giao tiếp với Alice.
Mặc dù phần trên sử dụng các phép ẩn dụ được nhân cách hóa như Alice và Bob, nhưng người thực thi tất cả các giao thức máy tính thực sự chạy trên máy tính. Trong phân tích lý thuyết, mô hình Turing Machine (Turing Machine, TM) thường được sử dụng. Nói cách khác, Alice và Bob là hai TM. Alice, với tư cách là người chứng minh, được coi là có tài nguyên máy tính không giới hạn, vì vậy cô ấy có thể tính căn bậc hai mô-đun hoặc có thể giải quyết vấn đề NP; Bob, với tư cách là người xác minh, bị giới hạn bởi tài nguyên máy tính và không thể bẻ khóa căn bậc hai mô-đun x , nếu không thì anh ta sẽ có thể tự mình đánh giá xem tuyên bố của Alice có đúng hay không.
Alice nói với Bob rằng có hai công thức:
s ≡ r^2 (mod n)
dưới dạng ≡ (xr)^2 (mod n)
Nếu s và as đều là số dư bậc hai modulo n thì a cũng là số dư bậc hai modulo n. Nhưng tôi sẽ không hiển thị tất cả cho bạn cùng một lúc. Tôi tạo ngẫu nhiên công thức đầu tiên mỗi lần, sau đó nhân nó với a để có công thức thứ hai và hiển thị ngẫu nhiên một trong số chúng theo kết quả tung đồng xu của bạn: nếu bạn tung số 0, tôi sẽ cho bạn căn bậc hai r của công thức 1; nếu bạn ném 1, tôi sẽ cho bạn căn bậc hai rx của công thức 2. Sau đây là sơ đồ của giao thức:
Chạy giao thức này m lần. Nếu Alice vượt qua thành công tấm séc thì xác suất 1-(1/2)^m sẽ thuyết phục Bob. Vì vậy, chúng ta hãy xem mục đích của giao thức này:
1. Nếu Alice có thể tính căn bậc hai mô-đun x, thì cô ấy có thể hoàn thành bất kỳ thử thách nào;
2. Nếu Alice không thể tính căn bậc hai mô đun x, bất kể cô ấy áp dụng chiến lược nào, cô ấy sẽ bị Bob từ chối với xác suất cao; Nhận bất kỳ thông tin nào ngoại trừ "a là phần dư bậc hai modulo n" ;
Ở đâu:
1. Rõ ràng,
2. Vì Alice không biết Bob sẽ đưa ra kết quả gì nên cô ấy không thể vượt qua bài kiểm tra bằng cách thao tác s ở bước đầu tiên (nếu cô ấy biết rằng 0, thì s ≡ r^2 (mod n) sẽ được tạo. Nếu cô ấy biết nó là 1, cô ấy có thể tạo s ≡ r^2/a (mod n), sao cho w được gửi là r và nó cũng có thể chuyển check);
3. Theo trực giác, nếu Bob ném nó về 0, nó trả về r; nếu ném nó về 1, nó trả về rx. Bob không thể tính r từ s ≡ r^2 (mod n) và không thể thu được x .
Phân tích 3 không thỏa đáng, vì theo định nghĩa, Bob không những không thể biết x mà còn không thể có được "Bất kỳ " thông tin ngoại trừ tuyên bố đó là đúng. Làm thế nào để chứng minh rằng một giao thức thực sự đạt được mức độ rò rỉ kiến thức bằng 0?
Ví dụCách chứng minh "không có kiến thức"
Bob as Thông tin mà người xác minh có thể "nhìn thấy" trong quá trình vận hành giao thức chứng minh không có kiến thức bao gồm từng bản ghi được gửi bởi Alice (bản ghi) và kết quả của việc tung đồng xu (đồng cục bộ), tức là view = {tanscript, local coins }. Nếu có một máy Turing S có cùng tài nguyên tính toán như Bob, nó có thể mô phỏng độc lập một khung nhìn' trong thời gian đa thức xác suất thông qua một thuật toán, và khung nhìn và khung nhìn' sẽ không thể phân biệt được. Sau đó, Bob thực sự có thể chạy giao thức này ở nhà để thu được thông tin tương đương. Sau đó, Alice không tiết lộ bất kỳ thông tin nào trong bằng chứng tương tác ngoại trừ việc thuyết phục Bob rằng mệnh đề đó là đúng.
Có hai khái niệm trên cần được định nghĩa chặt chẽ là "không thể phân biệt" và "mô phỏng":
"Không thể phân biệt được" là cách diễn đạt hàng ngày. Hãy nhớ rằng Alice, Bob và S ở trên đều là máy Turing. Chúng không quan tâm các vật thể có thực sự giống nhau hay không, chúng tức là chạy một thuật toán thời gian đa thức xác suất nhất định - được gọi là discriminator (Distinguisher), sự khác biệt về xác suất đánh giá phân bố view và view' có thể được bỏ qua. Thuộc tính này Nó được gọi là "không thể phân biệt về mặt tính toán":
P là Prover (tức là Alice), V* là tất cả Người xác minh (bao gồm cả Bob trung thực và độc hại), S là Trình mô phỏng, D là Người phân biệt, V*, S, D đều là các đa thức xác suất Máy Turing thời gian, w là thông tin riêng của P (hoặc có thể tính bằng P, nhưng không tính được bằng V), x là đầu vào chung (a, n), ở đây “a là phần dư bậc hai modulo n” Trong mệnh đề này, negl có nghĩa là sự khác biệt là không đáng kể (không đáng kể).
"Trình mô phỏng" S ở trên là sai lệch nhất. Vấn đề là các phép tính của chế độ xem và chế độ xem là không thể phân biệt được, vậy chẳng phải Bob cũng bị S thuyết phục sao? Sự hiểu lầm này xuất phát từ việc coi S là vai trò của Alice trong giao thức. Quá trình S tạo chế độ xem' không phải là quá trình Alice và Bob tương tác để tạo chế độ xem theo giao thức chứng minh không có kiến thức; S là một chương trình chạy độc lập, miễn là nó có thể được chứng minh là đủ để có thể tạo ra chế độ xem này' trong thời gian đa thức xác suất mà không cần tương tác với Bob.
Vì lý do này, Bob chỉ có thể bị thuyết phục trong quá trình tương tác với Alice, và quan điểm được tạo ra không thể thuyết phục được người khác. Bob'. Đó là, Bob nói với Bob': Tôi chắc chắn rằng Alice biết căn bậc hai mô đun x. Bạn thấy đấy, đây là góc nhìn của cuộc trò chuyện giữa chúng ta. Bob không thể chấp nhận điều này, vì Bob có thể đánh lừa anh ta bằng cách mô phỏng khung nhìn được tạo ra và anh ta phải tiến hành chứng minh tương tác với chính Alice để bị thuyết phục. Hạn chế này làm cho bằng chứng không có kiến thức không có đặc tính có thể kiểm chứng công khai, điều này cũng cho thấy chữ ký số theo nghĩa chung không phải là bằng chứng không có kiến thức [hoàn hảo]. Điều này sẽ được giới thiệu sau về số 0 không tương tác -bằng chứng kiến thức (NIZK) Thảo luận thêm.
Với hai khái niệm trên, chúng ta có thể xây dựng một "trình mô phỏng" S(a, n):

Trước hết, chương trình này có thuật toán thời gian đa thức xác suất để mô phỏng việc tạo các biến ngẫu nhiên, bao gồm tung đồng xu và tạo ra s; chương trình kết thúc (tạm dừng) và in kết quả với xác suất 1/2, kết quả này vẫn có thể kết thúc trong thời gian đa thức mặc dù có thể có vòng lặp. Tóm lại, S(x) có thể được hoàn thành trong thời gian đa thức;
Thứ hai, cần chứng minh rằng quan điểm {s, do chương trình này tạo ra, b , w} không thể phân biệt được với tính toán lượt xem do hệ thống chứng minh không có kiến thức tạo ra:
1. s và bằng chứng tương tác đầu tiên Các thông báo được tạo ngẫu nhiên và không thể phân biệt được;
2. b và việc tung đồng xu của Bob trong bằng chứng tương tác đều ngẫu nhiên và không thể phân biệt được;
3. Phương pháp xây dựng của w đảm bảo rằng ngay cả khi S không có thông tin về x, theo quan điểm của Bob, w là hợp pháp và w không thể phân biệt được với thông tin thứ ba của Alice trong bằng chứng tương tác;
Trong quy trình chứng minh chặt chẽ hơn, một công cụ phụ trợ cũng sẽ được giới thiệu - trình mô phỏng lai S'(a, n, x), có sức mạnh tính toán tương tự như Prover, nhưng đường dẫn thực thi là Tương tự như chương trình tương đương S(a, n), bạn đọc quan tâm có thể tra cứu bài gốc. Bằng cách lặp lại tuần tự trình mô phỏng ở trên m lần, có thể thu được một tập hợp hoàn chỉnh các khung nhìn, điều này chứng tỏ rằng các thuộc tính trên vẫn được áp dụng (nghĩa là nó bị đóng để sắp xếp tuần tự).
Cho đến nay, chúng tôi đã giới thiệu đầy đủ kiến thức nền tảng, cách xây dựng và bằng chứng của giao thức chứng minh không có kiến thức đầu tiên và cuối cùng chúng tôi có thể lấy Một định nghĩa chặt chẽ: một hệ thống chứng minh tương tác <P, V> là không có kiến thức khi và chỉ nếu có một trình mô phỏng thời gian đa thức xác suất S sao cho:
Trong đó x là mệnh đề mà P muốn chứng minh, L là tập hợp các mệnh đề thuộc một loại nhất định, z là kết quả của việc tung đồng xu và w là một cái gì đó chỉ P có (hoặc có thể tính toán) Thông tin cá nhân, V* đề cập đến tất cả các trình xác thực. Cho dù z V sử dụng chiến lược tung đồng xu nào để tương tác với P, S cũng có thể sử dụng z để tái tạo một phiên bản không thể phân biệt được.
Những độc giả nhìn thấy điều này, tôi tin rằng bạn đã có khả năng hiểu chính xác các bằng chứng không có kiến thức về mặt toán học. Bài tiếp theo Chúng ta sẽ thảo luận giao thức chứng minh không có kiến thức (NIZK) không tương tác và có thể xác minh công khai
Tham khảo
Shafi Goldwasser, Silvio Micali, Charles Rackoff: Sự phức tạp về kiến thức của các hệ thống chứng minh tương tác (Tóm tắt mở rộng). STOC 1985: 291-304
Liên kết nguồn:weixin.qq.com
Chào mừng bạn tham gia cộng đồng chính thức của BlockBeats:
Nhóm Telegram đăng ký: https://t.me/theblockbeats
Nhóm Telegram thảo luận: https://t.me/BlockBeats_App
Tài khoản Twitter chính thức: https://twitter.com/BlockBeatsAsia
