Không có kiến thức không tương tác, không thể nhân bản trong Mô hình Oracle ngẫu nhiên lượng tử

Bài viết này có sẵn trên arxiv theo giấy phép CC 4.0. tác giả: (1) Ruta Jawale; (2) Dakshita Khurana. Bảng liên kết Tóm tắt và giới thiệu Tổng quan về kỹ thuật Vòng sơ loại Không có kiến thức không tương tác, không thể nhân bản trong mô hình CRS NIZK không thể nhân bản trong Mô hình Oracle Lượng tử Ramdon Chữ ký tri thức không thể nhân bản Người giới thiệu 5 NIZK không thể nhân bản trong Mô hình Oracle ngẫu nhiên lượng tử 5.1 Giao thức Sigma được sửa đổi Chúng tôi sẽ bắt đầu bằng cách giới thiệu một giao thức sigma được sửa đổi một chút. Trong các phần tiếp theo, quá trình xây dựng của chúng tôi sẽ liên quan đến việc áp dụng Fiat-Shamir cho giao thức đã sửa đổi này. Điều này tiếp nối trực tiếp từ tính đầy đủ hoàn hảo của Π. Bằng chứng. Tính đầy đủ hoàn hảo và bất kỳ x nào có liên quan λ ∈ N thỏa mãn chúng ta có Chúng tôi xác định Ext 3 với quyền truy cập oracle vào Π.Ext và một số A như sau: Đầu vào: x, S. Cho (x, α, s) từ AΠ: gửi α tới Π.Ext, nhận β từ Π.Ext và gửi β đến AΠ. (1) Khi nhận được γ từ AΠ: gửi γ tới Π.Ext. (2) Xuất kết quả của Π.Ext dưới dạng w. (3) Ta xác định tập tham số sau: c = cΠ, p(·) = pΠ(·), negl0 (·) = negl0,Π(·) và negl1 (·) = negl1,Π(·). Cho mạch lượng tử có kích thước đa thức A = (A 0, A 1) và (x, S) sao cho Bây giờ chúng ta xác định AΠ = (A0,Π, A1,Π) với quyền truy cập oracle vào A. A0,Π được nối cứng với S, nhận đầu vào x, gửi (x, S) đến A0, nhận ((x, α, s ), |sti) từ A0 và đầu ra (α, |sti). A1,Π được nối cứng với S, nhận đầu vào (x, |sti, β), gửi ((x, S), |sti, β) đến A1, nhận γ từ A1, xuất ra γ. Theo cấu trúc bằng chứng và định nghĩa của người xác minh của chúng tôi, điều này có nghĩa là thỏa mãn ràng buộc trong phương trình (15). Điều này có nghĩa là chúng ta có, khi kết hợp với định nghĩa của Ext, rằng Do đó cho thấy rằng giao thức của chúng tôi là một giao thức bằng chứng về kiến thức. . Giả sử Π.Sim là trình mô phỏng lượng tử không có kiến thức xác minh trung thực tính toán cho Π. Chúng tôi xác định Sim có quyền truy cập oracle vào Π.Sim như sau: Trình xác minh trung thực về tính toán Không có kiến thức với Trình mô phỏng lượng tử Đầu vào: x, S. (1) Tính (α, β, γ) ← Π.Sim(1λ , x) (2) Các mẫu từ S. (3) Đầu ra ((x, α, s), β, γ). Cho một đa thức p(·), một mạch lượng tử có kích thước đa thức D, λ ∈ N, và ((x, S), w) ∈ R sao cho Chúng tôi xác định mức rút gọn về thuộc tính không có kiến thức của Π như sau: Giảm thiểu: không có kiến thức về Π được cung cấp quyền truy cập oracle vào D. Gắn cứng với: x, S. (1) Nhận (thật hoặc mô phỏng) (α, β, γ) từ người thách đấu. (2) Các mẫu từ S. (3) Gửi ((x, α, s), β, γ) tới D. Nhận b từ D. (4) Đầu ra b. Khi người thách thức gửi bằng chứng thực (hoặc mô phỏng) cho Π, việc rút gọn sẽ tạo ra một bằng chứng giống hệt với bằng chứng thực (tương ứng với mô phỏng). Như vậy, sự giảm thiểu này bảo toàn lợi thế khác biệt của . Điều này mâu thuẫn với tính chất không biết của Π. Do đó, giao thức của chúng tôi phải không có kiến thức. D Theo định nghĩa của người tục ngữ trung thực P.Com, đó là một sự mâu thuẫn. Do đó giao thức của chúng tôi phải có những cam kết không thể đoán trước. Hệ quả 5.2. Phương pháp phỏng đoán Fiat-Shamir được áp dụng cho giao thức sigma hậu lượng tử được xác định trong Định lý 5.1 mang lại NIZKPoK hậu lượng tử cổ điển Π′ trong QROM (Định nghĩa 3.11). . Tiếp theo là Định lý 5.1 và Định lý 3.12. Bằng chứng 5.2 Định nghĩa về khả năng không thể nhân bản NIZK không thể sao chép trong mô hình tiên tri ngẫu nhiên lượng tử được định nghĩa tương tự như mô hình CRS – chúng tôi lặp lại các định nghĩa này trong mô hình QRO để hoàn thiện bên dưới. (Bảo mật không thể sao chép cho các trường hợp cứng). Một bằng chứng (P,V) thỏa mãn tính bảo mật không thể nhân bản đối với một oracle ngẫu nhiên lượng tử O nếu với mọi ngôn ngữ L có quan hệ tương ứng RL, với mọi họ mạch lượng tử có kích thước đa thức {Cλ}λ∈N và với mọi phân bố cứng {Xλ ,Wλ}λ∈N trên RL, tồn tại hàm số negl1 (·) không đáng kể sao cho với mọi λ ∈ N, Định nghĩa 5.3. Định nghĩa 5.4 ((k−1)-to-k-NIZK có thể trích xuất được trong QROM). Cho tham số bảo mật λ ∈ N và quan hệ NP R với ngôn ngữ tương ứng L. Đặt Π = (P,V) sao cho P và V là các thuật toán lượng tử có kích thước poly(λ). Chúng ta có điều đó với bất kỳ (x, ω) ∈ R nào, P nhận một cặp thể hiện và nhân chứng (x, ω) làm đầu vào và đầu ra π, còn V nhận một thể hiện x và bằng chứng π làm đầu vào và xuất ra một giá trị trong {0, 1}. Π là giao thức NIZKPoK không tương tác (k − 1)-to-k-unclonable cho ngôn ngữ L đối với một oracle O ngẫu nhiên nếu các điều sau đây đúng: • Π là giao thức NIZKPoK cho ngôn ngữ L trong mô hình tiên tri ngẫu nhiên lượng tử (Định nghĩa 3.11). • (k−1)-to-k-Unclonable with Extraction: Tồn tại một mạch lượng tử có kích thước đa thức được oracle hỗ trợ E sao cho với mọi mạch lượng tử có kích thước đa thức A, với mỗi bộ k − 1 cặp nhân chứng ( x1, ω1), . . . ,(xk−1, ωk−1) ∈ R, với mọi x nơi chúng ta xác định sao cho tồn tại đa thức p(·) trong đó thì cũng tồn tại đa thức (·) sao cho q Tương tự như phần trước, ta có bổ đề sau. Đặt Π = (Setup, P,V) là một giao thức lượng tử không có kiến thức 1 đến 2 không thể nhân bản (Định nghĩa 5.4). Khi đó, Π thỏa mãn Định nghĩa 5.3. Bổ đề 5.5. Để chứng minh Bổ đề 5.5, chúng ta tham khảo Phụ lục A. 5.3 NIZK không thể sao chép ngụ ý tiền lượng tử khóa công khai trong QROM Định lý 5.6. Cho O là một nhà tiên tri ngẫu nhiên lượng tử. Giả sử (X ,W) là phân phối cứng trên ngôn ngữ L ∈ NP. Đặt Π = (P,V) là giao thức 1 đến 2 không thể nhân bản, không tương tác, hoàn chỉnh hoàn hảo, không có kiến thức về mặt tính toán cho L trong mô hình QRO (Định nghĩa 5.4). Khi đó (P,V) hàm ý một sơ đồ nhỏ tiền lượng tử khóa công khai trong mô hình QRO (Định nghĩa 3.15) như được mô tả trong Hình 4. . . Điều này xuất phát trực tiếp từ tính đầy đủ hoàn hảo của Π. Không thể tha thứ. Cho p(·) là đa thức và A là đối thủ thời gian đa thức lượng tử sao cho với vô số λ ∈ N +, Bằng chứng Sự Chính Xác Hoàn Hảo Chúng tôi xây dựng một sự rút gọn phá vỡ định nghĩa về tính không thể sao chép (Định nghĩa 5.3) mà chúng tôi chỉ ra (trong Phụ lục A) được ngụ ý trong định nghĩa của chúng tôi (Định nghĩa 5.4). Người thách đấu, với quyền truy cập vào oracle O ngẫu nhiên, lấy mẫu một cặp nhân chứng cứng (x, w) ← (X ,Y) và bằng chứng π ← PO(x, w). Sau đó, người thách thức chuyển tiếp (x, π) tới phần rút gọn, phần rút gọn này cũng có quyền truy cập oracle vào O. Sau đó, phần rút gọn đặt |$i = π và s = x. Việc giảm sẽ gửi (|$i, s) đến đối thủ A và đối thủ này sẽ quay lại (|$0, s0, |$1, s1). Sau đó, quá trình rút gọn sẽ phân tích cú pháp và đặt πi = |$ii cho i ∈ {0, 1}. Việc giảm sau đó sẽ gửi lại π0 và π1 cho người thách đấu. 5.4 Xây dựng và phân tích Cho λ, k ∈ N và một sơ đồ nhỏ tiền lượng tử khóa công khai ( ). Cho điểm q1, . . . , qk có cấu trúc như sau: điểm q chứa số xê-ri s được lấy mẫu theo (1λ ). Bổ đề 5.7. NoteGen,Ver NoteGen Các điểm q1, . . . , qk phải khác biệt với xác suất áp đảo. . Mỗi điểm chứa một số sê-ri được lấy mẫu theo thuật toán tạo tiền lượng tử, (1λ ). Do tính không thể đoán trước được của các số xê-ri của tiền lượng tử (Định nghĩa 3.13), tất cả k số xê-ri được tạo ra một cách trung thực phải khác biệt với xác suất áp đảo. Do đó, k điểm này sẽ khác biệt với xác suất áp đảo. Bằng chứng NoteGen Bây giờ chúng ta giới thiệu cách xây dựng của mình trong Hình 5 và chứng minh định lý chính của phần này. Định lý 5.8. Cho k(·) là một đa thức. Cho quan hệ NP R với ngôn ngữ tương ứng L. Giả sử ( ) NoteGen, Ver là một sơ đồ nhỏ tiền lượng tử khóa công khai (Định nghĩa 3.13) và Π = (P,V) là một giao thức sigma hậu lượng tử (Định nghĩa 3.4). (P,V) như được định nghĩa trong Hình 5 sẽ là âm thanh tri thức không tương tác, không có tri thức về mặt tính toán và (k − 1)-to-k-unclonable với giao thức trích xuất cho L trong mô hình oracle ngẫu nhiên lượng tử (Định nghĩa 3.11 ). Đặt các tham số và nguyên hàm như đã cho trong phát biểu định lý. Chúng tôi lập luận rằng tính đầy đủ xuất phát từ việc xây dựng giao thức trong Hình 5 và chúng tôi chứng minh các thuộc tính còn lại bên dưới. Bằng chứng. chúng ta có Cho mạch lượng tử có kích thước đa thức A và x sao cho Giả sử AF S được xác định bằng oracle-access đối với một số A và O như sau: Đầu vào: x, S. (1) Cho một truy vấn (x, α, s) từ A: gửi (x, α, s) đến O, nhận β từ O và gửi β đến A. (2) Khi nhận π = (|$i, s, α, β, γ) từ A: xuất ra πF S = ((x, α, s), β, γ). Theo cấu trúc bằng chứng và định nghĩa của người xác minh của chúng tôi, điều này có nghĩa là thỏa mãn ràng buộc trong phương trình (16). Điều này có nghĩa là chúng ta có, khi kết hợp với định nghĩa của Ext và S, rằng Do đó cho thấy rằng giao thức của chúng tôi là một giao thức bằng chứng về kiến thức. Không có kiến thức. Giả sử SimF S là trình mô phỏng cho Π′ trong Hệ quả 5.2 (trong đó Π thể hiện Định lý 5.1). Đặt RF S là mối quan hệ của Π′ đối với R. Chúng tôi xác định Sim có quyền truy cập oracle vào SimF S và quyền truy cập chương trình vào một số oracle O ngẫu nhiên như sau: (bỏ qua mọi nhân chứng mà nó có thể nhận được). Đầu vào: x Đặt một bộ phân biệt D được Oracle hỗ trợ chỉ có thể thực hiện các truy vấn (x, w) ∈ R và đa thức p(·) được đưa ra sao cho Chúng tôi xác định sự rút gọn về thuộc tính không có kiến thức của Π′ như sau: Giảm thiểu: không có kiến thức về Π′ được cấp quyền truy cập oracle vào D và quyền truy cập chương trình vào O. Với mọi (x, w) từ D: Chế độ xem của D khớp với giao thức của chúng tôi trong Hình 5 hoặc Sim. Như vậy, sự rút gọn của chúng ta sẽ có cùng ưu điểm trong việc phá vỡ tính chất không biết của Π′ . Chúng ta đạt đến một mâu thuẫn, do đó giao thức của chúng ta phải là không có kiến thức. Đặt Ext là mạch lượng tử của bộ trích xuất mà chúng ta đã xác định trước đó (trong chứng minh của chúng ta rằng Hình 5 là bằng chứng về kiến thức). Giả sử Sim là mạch lượng tử của trình mô phỏng mà chúng tôi đã xác định trước đó (trong bằng chứng của chúng tôi rằng Hình 5 là giao thức không có kiến thức). Chúng tôi xác định một trình trích xuất E có quyền truy cập oracle vào một số A như sau: Khả năng trích xuất không thể nhân bản. Được nối cứng với: một số lựa chọn của I ⊆ [k − 1], J ⊆ [k], x1, . . . , xk−1 ∈ R, x. (1) Các mẫu ℓ ∈ J đồng đều một cách ngẫu nhiên. (2) Khởi tạo một oracle ngẫu nhiên có thể mô phỏng và trích xuất được O. Chạy Ext trên O trong suốt quá trình tương tác với A (có thể liên quan đến việc tua lại, trong trường hợp đó chúng tôi sẽ tua lại A và lặp lại các bước sau). Yêu cầu Ext trích xuất đối với kết quả chứng minh thứ ℓ của A. (3) Tính πι ← Sim(xι) cho ι ∈ [k − 1] trong đó chúng ta lưu trữ tất cả các điểm mà Sim sẽ lập trình vào danh sách P. (4) Gửi {πι}ι∈[k−1] tới A. (5) Đối với mọi truy vấn từ A, nếu truy vấn thuộc P thì trả lời bằng câu trả lời từ P. Ngược lại, chuyển tiếp truy vấn đến O và gửi câu trả lời lại cho A. Gọi Ob biểu thị tiên tri ngẫu nhiên đã được sửa đổi này. (7) Xuất kết quả của Ext dưới dạng w. Với phương trình (24), chúng ta có thể thuộc một trong hai trường hợp sau: hoặc A tạo ra hai bằng chứng chấp nhận có cùng số sê-ri với bằng chứng được tạo ra một cách trung thực, hoặc A thì không. Chúng tôi xem xét hai kịch bản này một cách riêng biệt và cho thấy rằng mỗi kịch bản đều mâu thuẫn. Kịch bản một Giả sử A tạo ra hai bằng chứng chấp nhận có cùng số sê-ri với một bằng chứng được tạo ra một cách trung thực. Bằng cách áp dụng một liên kết ràng buộc với phương trình (24), chúng ta có rằng sự kiện này có thể xảy ra với xác suất ít nhất là 1/2p(λ). Một cách tượng trưng, Kịch bản hai Ngoài ra, giả sử rằng A không tạo ra hai bằng chứng chấp nhận có cùng số sê-ri với bằng chứng được tạo ra một cách trung thực. Theo nguyên tắc chuồng bồ câu, điều này có nghĩa là A tạo ra bằng chứng chấp nhận có số sê-ri không nằm trong số những số mà nó nhận được. Bằng cách áp dụng một liên kết ràng buộc với phương trình (24), chúng ta có rằng sự kiện này có thể xảy ra với xác suất ít nhất là 1/2p(λ). Tóm lại, chúng ta có điều đó Thông qua đối số tính trung bình, chúng ta có thể sửa chỉ số j ∈ J mang lại cho chúng ta cùng một sự kiện với lợi thế là 1/(2kp(λ)). Bây giờ chúng tôi sẽ chuyển sang kết hợp trong đó chúng tôi cung cấp cho A bằng chứng mô phỏng ở chỉ số I. Tồn tại đa thức (·) sao cho Yêu cầu 5.9. q Sau này chúng ta sẽ thấy bằng chứng của Yêu cầu 5.9. Hiện tại, giả sử rằng tuyên bố này đúng, chúng ta có thể xác định một đối thủ mà từ đó Ext có thể trích xuất một nhân chứng hợp lệ cho x. Tồn tại đa thức ′ (·) sao cho Yêu cầu 5.10. q Chúng ta sẽ sớm thấy bằng chứng cho Yêu cầu 5.10. Trong khi đó, nếu khẳng định này đúng thì chúng ta sẽ mâu thuẫn trực tiếp với phương trình (19). Vì vậy, tất cả những gì còn lại phải được chứng minh là hai khẳng định: khẳng định 5.9 và khẳng định 5.10. Chúng ta bắt đầu bằng việc chứng minh khẳng định trước đây. Bằng chứng yêu cầu bồi thường 5.9. lập trình k điểm này một cách độc lập. Sau đó, chúng ta có thể tranh luận về tính không thể phân biệt được của việc chuyển từng cái một sang bằng chứng mô phỏng. Chúng ta sẽ lập luận rằng trình mô phỏng của chúng ta sẽ chạy trong thời gian đa thức dự kiến. Theo Bổ đề 5.7, k điểm mà trình mô phỏng của chúng ta sẽ lập trình sẽ khác biệt với xác suất áp đảo. Hơn nữa, vì chúng tôi giả định rằng nhà tiên tri ngẫu nhiên lượng tử của chúng tôi có thể được lập trình tại nhiều điểm riêng biệt Định nghĩa 3.10, nên trình mô phỏng của chúng tôi được xác định rõ ràng. Trước tiên, chúng ta cần chứng minh rằng chiến lược của chúng ta đã được xác định rõ ràng, rằng chúng ta sẽ có thể Bây giờ chúng tôi tranh luận về tính không thể phân biệt giữa các bằng chứng mô phỏng với các bằng chứng được tạo ra một cách trung thực thông qua một lập luận kết hợp. Giả sử để mâu thuẫn rằng hiệu xác suất giữa Công thức (21) và Công thức (22) là 1/p′ (λ) đối với một số đa thức p ′ (·). Chúng tôi xây dựng một loạt các phép lai liên tiếp cho mỗi i ∈ [k − 1] trong đó chúng tôi chuyển bằng chứng thứ i từ chứng minh được tạo ra sang mô phỏng. Theo đối số lai này, phải có một số vị trí ℓ ∈ [k − 1] trong đó việc chuyển đổi chứng minh thứ ℓ có chênh lệch xác suất ít nhất là 1/(kp′ (λ)). Bây giờ chúng tôi chính thức hóa một cách giảm có thể phân biệt giữa hai cài đặt này: Trước tiên, chúng tôi lập luận rằng quan điểm mà việc rút gọn mang lại cho A phù hợp với một trong các trò chơi: trong đó tất cả các bằng chứng cho đến ℓ th đều được mô phỏng hoặc trong đó tất cả các bằng chứng cho đến và bao gồm cả ℓ th đều được mô phỏng. Theo Bổ đề 5.7, điểm được người thách thức tính toán hoặc lập trình sẽ khác biệt với các điểm mà chương trình rút gọn. Như vậy, việc rút gọn được phép sửa đổi 5 oracle mà A giao tiếp với (xem bước (4)). Tóm lại, A sẽ được cấp quyền truy cập vào một oracle phù hợp với tất cả các bằng chứng mà nó nhận được. Giả sử A có lượt xem khớp trực tiếp với lượt xem mong đợi của nó trong một trong hai trò chơi, thì lợi thế của mức giảm cũng giống như lợi thế của A ít nhất là 1/(kp′ (λ)). Điều này mâu thuẫn với thuộc tính không có kiến thức trong giao thức của chúng tôi. Vì vậy, yêu cầu ban đầu của chúng tôi phải đúng. Bây giờ chúng ta tiếp tục chứng minh khẳng định sau. 5.10. Cho rằng Yêu cầu bồi thường 5.9 đúng, điều này ngụ ý rằng Bằng chứng yêu cầu bồi thường Đầu tiên chúng ta phải lập luận rằng quan điểm của A vẫn giống với trò chơi xuất hiện trong cả Phương trình (24) và Phương trình (25). Oracle mà A giao tiếp (xem bước (4)) sẽ nhất quán với tất cả các bằng chứng mà nó nhận được. Thông qua phương trình (25), chúng ta đi đến kết luận rằng Theo định nghĩa chứng minh tri thức (Định nghĩa 3.11) có một số tham số đa thức p ∗ (·) và các hàm bỏ qua negl0 (·) và negl1 (·), ta có tồn tại một số đa thức q ′ (·) sao cho Điều này hoàn thành bằng chứng cho yêu cầu của chúng tôi. Bằng cách hoàn thành việc chứng minh các khẳng định của mình, chúng ta đã kết luận việc chứng minh phát biểu định lý của mình. Giả sử tồn tại các hàm nội xạ một chiều và iO sau lượng tử tồn tại, tồn tại âm thanh kiến thức không tương tác, kiến thức bằng 0 về mặt tính toán và (k − 1)-to-kunclonable với giao thức trích xuất cho NP trong nhà tiên tri ngẫu nhiên lượng tử mô hình (Định nghĩa 5.4). Hệ quả 5.11. Điều này tuân theo Định lý 3.14 và Định lý 5.8. Bằng chứng. Do đó, chúng tôi đã chỉ ra rằng Hình 5 là NIZK PoK không thể sao chép được trong mô hình ROM như được xác định theo định nghĩa về khả năng không thể sao chép của chúng tôi, Định nghĩa 5.4.