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ả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.

Bằng chứng. Tính đầy đủ hoàn hảo Điều này tiếp nối trực tiếp từ tính đầy đủ hoàn hảo của Π.

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.

(1) Cho (x, α, s) từ AΠ: gửi α tới Π.Ext, nhận β từ Π.Ext và gửi β đến AΠ.

(2) Khi nhận được γ từ AΠ: gửi γ tới Π.Ext.

(3) Xuất kết quả của Π.Ext dưới dạng w.

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.

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ử . 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:

Đầ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 D . Đ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.

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).

Bằng chứng . Tiếp theo là Định lý 5.1 và Định lý 3.12.

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.

Định nghĩa 5.3. (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.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 q (·) sao cho

Tương tự như phần trước, ta có bổ đề sau.

Bổ đề 5.5. Đặ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.

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

Bằng chứng . Sự Chính Xác Hoàn Hảo . Đ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 +,

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

Bổ đề 5.7. Cho λ, k ∈ N và một sơ đồ nhỏ tiền lượng tử khóa công khai ( NoteGen,Ver ). 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 NoteGen (1λ ).

Các điểm q1, . . . , qk phải khác biệt với xác suất áp đảo.

Bằng chứng . 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ử, NoteGen (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â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 ).

Bằng chứng. Đặ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.

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:

Đầu vào: x (bỏ qua mọi nhân chứng mà nó có thể nhận được).

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

Khả năng trích xuất không thể nhân bản. Đặ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:

Đượ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.

Yêu cầu 5.9. Tồn tại đa thức q (·) sao cho

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.

Yêu cầu 5.10. Tồn tại đa thức q ′ (·) sao cho

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. 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ể 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.

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.

Bằng chứng yêu cầu bồi thường 5.10. Cho rằng Yêu cầu bồi thường 5.9 đúng, điều này ngụ ý rằ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.

Hệ quả 5.11. 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).

Bằng chứng. Điều này tuân theo Định lý 3.14 và Định lý 5.8.

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.