Quantum Random Oracle 모델의 복제 불가능한 비대화형 제로 지식

링크 표

개요 및 소개

기술 개요

예선

CRS 모델의 복제 불가능한 비대화형 영지식

Quantum Ramdon Oracle 모델의 복제 불가능한 NIZK

복제 불가능한 지식의 서명

참고자료

5 Quantum Random Oracle 모델의 복제 불가능한 NIZK

5.1 수정된 시그마 프로토콜

약간 수정된 시그마 프로토콜을 소개하는 것부터 시작하겠습니다. 다음 섹션에서는 이 수정된 프로토콜에 Fiat-Shamir를 적용하는 작업이 포함됩니다.

증거. 완벽한 완전성 이는 Π의 완벽한 완전성에서 바로 이어집니다.

그리고 관련 λ ∈ N을 만족하는 임의의 x

우리는

우리는 다음과 같이 Π.Ext 및 일부 A에 대한 oracle-access로 Ext 3을 정의합니다.

입력: x, S.

(1) AΠ에서 주어진 (x, α, s): α를 Π.Ext로 보내고, Π.Ext에서 β를 받고, β를 AΠ로 보냅니다.

(2) AΠ로부터 γ를 수신하면: γ를 Π.Ext로 보냅니다.

(3) Π.Ext의 결과를 w로 출력한다.

우리는 다음 매개변수 세트를 정의합니다: c = cΠ, p(·) = pΠ(·), negl0 (·) = negl0,Π(·) 및 negl1 (·) = negl1,Π(·).

다항식 크기 양자 회로 A = (A 0, A 1) 및 (x, S)가 다음과 같이 주어집니다.

이제 A에 대한 oracle 액세스를 통해 AΠ = (A0,Π, A1,Π)를 정의합니다. A0,Π는 S와 하드와이어되어 입력 x를 취하고 (x, S)를 A0에 보내고 ((x, α, s)를 받습니다. ), |sti)를 A0에서 출력하고 (α, |sti)를 출력합니다. A1,Π는 S와 연결되어 있고, 입력(x, |sti, β)을 취하고, ((x, S), |sti, β)를 A1에 보내고, A1으로부터 γ를 받고, γ를 출력합니다. 증명의 구조와 검증자의 정의에 따르면 이는 다음을 의미합니다.

이는 식 (15)의 제약을 만족한다. 이는 Ext의 정의와 결합하면 다음을 의미합니다.

따라서 우리의 프로토콜이 지식 프로토콜의 증거임을 보여줍니다.

Quantum Simulator를 사용한 전산 정직 검증기 영지식 . Π.Sim을 Π에 대한 계산적 정직 검증 영지식 양자 시뮬레이터로 설정합니다. 우리는 Π.Sim에 대한 oracle 액세스로 Sim을 다음과 같이 정의합니다:

입력: x, S.

(1) (α, β, γ) ← Π.Sim(1λ , x) 계산

(2) S의 샘플.

(3) 출력((x, α, s), β, γ).

다항식 p(·), 다항식 크기 양자 회로 D, λ ∈ N, 및 ((x, S), w) ∈ R이 다음과 같이 주어집니다.

우리는 Π의 영지식 속성에 대한 축소를 다음과 같이 정의합니다.

감소: 오라클이 D에 액세스할 수 있는 경우 Π에 대한 지식이 전혀 없습니다.

하드와이어: x, S.

(1) 도전자로부터 (실제 또는 시뮬레이션) (α, β, γ)을 받습니다.

(2) S의 샘플.

(3) ((x, α, s), β, γ)를 D로 전송합니다. D로부터 b를 수신합니다.

(4) 출력 b.

도전자가 Π에 대한 실제(또는 시뮬레이션) 증명을 보낼 때 축소는 실제(각각 시뮬레이션) 증명과 동일한 증명을 생성합니다. 따라서 이러한 감소는 D 의 뚜렷한 이점을 유지합니다. 이는 Π의 영지식 속성과 모순됩니다. 따라서 우리의 프로토콜은 영지식이어야 합니다.

정직한 증명자 P.Com,

그것은 모순이다. 따라서 우리의 프로토콜에는 예측할 수 없는 약속이 있어야 합니다.

결과 5.2. 정리 5.1에 정의된 포스트 양자 시그마 프로토콜에 적용된 Fiat-Shamir 경험적 방법은 QROM에서 고전적인 포스트 양자 NIZKPoK Π'을 생성합니다(정의 3.11).

증거 . 이는 정리 5.1과 정리 3.12를 따릅니다.

5.2 복제 불가능성 정의

양자 랜덤 오라클 모델의 복제 불가능한 NIZK는 CRS 모델과 유사하게 정의됩니다. 아래의 완전성을 위해 QRO 모델에서 이러한 정의를 반복합니다.

정의 5.3. (하드 인스턴스에 대한 복제 불가 보안). 증명(P,V)은 대응하는 관계 RL을 갖는 모든 언어 L에 대해, 모든 다항식 크기 양자 회로군 {Cλ}λ∈N에 대해, 그리고 모든 하드 분포 {XLλ에 대해 양자 랜덤 오라클 O와 관련하여 복제 불가 보안을 충족합니다. RL에 대한 ,Wλ}λ∈N, 무시할 수 있는 함수 negl1 (·)이 존재하므로 모든 λ ∈ N에 대해 다음과 같습니다.

정의 5.4(QROM에서 (k−1)-k-Unclonable 추출 가능 NIZK). 보안 매개변수 λ ∈ N과 해당 언어 L과의 NP 관계 R이 주어집니다. P와 V가 폴리(λ) 크기 양자 알고리즘이 되도록 Π = (P,V)가 주어집니다. 임의의 (x, Ω) ∈ R에 대해 P는 인스턴스와 증인 쌍(x, Ω)을 입력으로 받고 π를 출력하고, V는 인스턴스 x와 증명 π를 입력으로 받고 {0에 값을 출력합니다. 1}.

Π는 다음이 성립하는 경우 무작위 오라클 O와 관련하여 언어 L에 대한 비대화형(k − 1)-k 복제 해제 가능 NIZKPoK 프로토콜입니다.

• Π는 양자 무작위 오라클 모델(정의 3.11)에서 언어 L에 대한 NIZKPoK 프로토콜입니다.

• 추출을 통한 (k−1)-to-k-복제 해제 가능: 모든 다항식 크기 양자 회로 A에 대해 k − 1 인스턴스-증인 쌍의 모든 튜플에 대해 Oracle 지원 다항식 크기 양자 회로 E가 존재합니다( x1, Ω1), . . . ,(xk−1, Ωk−1) ∈ R, 우리가 정의하는 모든 x에 대해

다항식 p(·)가 있습니다. 여기서

그러면 다음과 같은 다항식 q (·)도 있습니다.

이전 섹션과 유사하게 다음 기본 정리가 있습니다.

보조정리 5.5. Π = (Setup, P,V)를 비대화형 1대 2 복제 해제 가능 영지식 양자 프로토콜(정의 5.4)이라고 가정합니다. 그러면 Π는 정의 5.3을 만족한다.

Lemma 5.5의 증명은 부록 A를 참조하세요.

5.3 복제 불가능한 NIZK는 QROM의 공개 키 양자 화폐를 의미합니다.

정리 5.6. O를 양자 무작위 오라클이라고 하자. (X ,W)를 언어 L ∈ NP에 대한 하드 분포로 둡니다. Π = (P,V)를 QRO 모델(정의 5.4)에서 L에 대한 1:2 복제 해제 가능 비대화형 완벽하게 완전한, 계산적으로 영지식 프로토콜이라고 가정합니다.

그러면 (P,V)는 그림 4에 설명된 QRO 모델(정의 3.15)의 공개 키 양자 화폐 미니 방식을 의미합니다.

증거 . 완벽한 정확성 . 이는 Π의 완벽한 완전성에서 직접적으로 이어집니다. 위조 불가능. p(·)를 다항식으로 하고 A를 양자 다항식 시간 적이라고 가정하면 무한한 수의 λ ∈ N +에 대해 다음과 같습니다.

우리는 정의(정의 5.4)에 암시되어 있는(부록 A에서) 보여 주는 복제 해제 가능성 정의(정의 5.3)를 깨는 축소를 구성합니다. 무작위 오라클 O에 접근할 수 있는 도전자는 하드 인스턴스-증인 쌍 (x, w) ← (X ,Y) 및 증명 π ← PO(x, w)를 샘플링합니다. 그런 다음 도전자는 (x, π)를 O에 대한 Oracle 액세스 권한이 있는 축소로 전달합니다. 그런 다음 축소는 |$i = π 및 s = x를 설정합니다. 감소는 (|$0, s0, |$1, s1)을 반환하는 적 A에게 (|$i, s)를 보냅니다. 그런 다음 축소는 i ∈ {0, 1}에 대해 πi = |$ii를 구문 분석하고 설정합니다. 그런 다음 감소는 π0과 π1을 도전자에게 다시 보냅니다.

5.4 구성 및 분석

보조정리 5.7. λ, k ∈ N 및 공개키 양자화폐 미니 방식( NoteGen,Ver )을 준다고 하자. 점 q1, . . . , qk는 다음과 같은 구조로 주어집니다. 점 q는 NoteGen (1λ)에 따라 샘플링된 일련 번호 s를 포함합니다.

점 q1, . . . , qk는 압도적인 확률로 구별되어야 합니다.

증거 . 각 포인트에는 양자머니 생성 알고리즘인 NoteGen (1λ)에 따라 샘플링된 일련번호가 포함되어 있습니다. 양자 화폐의 일련번호는 예측 불가능하기 때문에(정의 3.13) 정직하게 생성된 모든 k개의 일련번호는 압도적인 확률로 구별되어야 합니다. 따라서 이러한 k개 포인트는 압도적인 확률로 구별됩니다.

이제 그림 5에서 구성을 소개하고 이 섹션의 주요 정리를 증명합니다.

정리 5.8. k(·)를 다항식이라고 하자. 해당 언어 L과 NP 관계 R이 주어집니다.

( NoteGen, Ver )를 공개키 양자화폐 미니 방식(정의 3.13)으로 하고 Π = (P,V)를 포스트 퀀텀 시그마 프로토콜(정의 3.4)로 하자.

그림 5에 정의된 (P,V)는 양자 무작위 오라클 모델에서 L에 대한 추출 프로토콜을 사용하여 비대화형 지식 사운드, 계산상 제로 지식 및 (k − 1)-to-k-복제 가능이 됩니다(정의 3.11). ).

증거. 매개변수와 프리미티브는 정리문에 주어진 대로 두십시오. 우리는 그림 5의 프로토콜 구성에서 완전성이 나온다고 주장하고 아래의 나머지 속성을 증명합니다.

우리는

다항식 크기의 양자 회로 A와 x가 다음과 같이 주어집니다.

다음과 같이 일부 A 및 O에 대한 oracle 액세스를 사용하여 AF S를 정의합니다.

입력: x, S.

(1) A로부터 쿼리 (x, α, s)가 주어졌을 때: (x, α, s)를 O로 보내고, O로부터 β를 받고, β를 A로 보냅니다.

(2) A로부터 π = (|$i, s, α, β, γ)를 수신하면 πF S = ((x, α, s), β, γ)를 출력합니다.

증명의 구조와 검증자의 정의에 따르면 이는 다음을 의미합니다.

이는 식 (16)의 제약을 만족한다. 이는 Ext와 S의 정의를 결합하면 다음과 같다는 것을 의미합니다.

따라서 우리의 프로토콜이 지식 프로토콜의 증거임을 보여줍니다.

영지식. SimF S를 추론 5.2(여기서 Π는 정리 5.1을 인스턴스화함)의 Π'에 대한 시뮬레이터로 둡니다. RF S를 R에 대한 Π'의 관계로 설정합니다. 우리는 SimF S에 대한 oracle 액세스로 Sim을 정의하고 임의의 oracle O에 대한 프로그램 액세스를 다음과 같이 정의합니다.

입력: x (수신할 수 있는 모든 증인을 무시합니다).

쿼리 (x, w) ∈ R만 할 수 있는 오라클 지원 구분자 D와 다항식 p(·)가 다음과 같이 주어질 수 있다고 가정합니다.

우리는 Π'의 영지식 속성에 대한 축소를 다음과 같이 정의합니다.

감소: 오라클이 D에 액세스하고 프로그램이 O에 액세스할 수 있는 경우 Π'에 대한 지식이 전혀 없습니다.

D의 모든 (x, w)에 대해:

D의 보기는 그림 5 또는 Sim의 프로토콜과 일치합니다. 따라서 우리의 축소는 Π'의 영지식 속성을 깨뜨릴 때 동일한 이점을 가져야 합니다. 우리는 모순에 도달하므로 우리의 프로토콜은 지식이 없어야 합니다.

복제 불가능한 추출 가능성. Ext를 앞서 정의한 추출기의 양자 회로로 둡니다(그림 5가 지식 증명이라는 증거에서). Sim을 앞서 정의한(그림 5가 영지식 프로토콜이라는 증거에서) 시뮬레이터의 양자 회로라고 가정합니다. 다음과 같이 일부 A에 대한 oracle 액세스를 사용하여 추출기 E를 정의합니다.

하드와이어: I ⊆ [k − 1], J ⊆ [k], x1, . . . , xk−1 ∈ R, x.

(1) ℓ ∈ J를 무작위로 균일하게 샘플링합니다.

(2) 시뮬레이션 가능하고 추출 가능한 무작위 오라클 O를 인스턴스화합니다. A와의 상호 작용 전반에 걸쳐 O에서 Ext를 실행합니다(되감기가 포함될 수 있으며 이 경우 A를 되감고 다음 단계를 반복합니다). A의 ℓ번째 증명 출력에 대해 Ext가 추출하도록 요구합니다.

(3) Sim이 프로그래밍할 모든 점을 목록 P에 저장하는 ι ∈ [k − 1]에 대해 πι ← Sim(xι)를 계산합니다.

(4) A에게 {πι}ι∈[k−1]을 보낸다.

(5) A의 모든 쿼리에 대해 쿼리가 P에 있으면 P의 답변으로 응답합니다. 그렇지 않으면 쿼리를 O로 전달하고 답변을 다시 A로 보냅니다. Ob가 이 수정된 무작위 오라클을 나타낸다고 가정합니다.

(7) Ext의 결과를 w로 출력한다.

방정식 (24)이 주어지면 다음 두 가지 경우 중 하나에 있을 수 있습니다. A는 정직하게 생성된 증명과 동일한 일련 번호를 가진 두 개의 수락 가능한 증명을 생성하거나 A는 그렇지 않습니다. 우리는 이 두 가지 시나리오를 개별적으로 고려하여 각각 모순에 도달한다는 것을 보여줍니다.

시나리오 1

A가 정직하게 생성된 증명과 동일한 일련 번호를 가진 두 개의 승인된 증명을 생성한다고 가정해 보겠습니다. 방정식 (24)에 결합 결합을 적용하면 이 사건이 최소한 1/2p(λ) 확률로 발생할 수 있다는 것을 알 수 있습니다. 상징적으로,

시나리오 2

또는 A가 정직하게 생성된 증명과 동일한 일련 번호를 가진 두 개의 승인된 증명을 생성하지 않는다고 가정해 보겠습니다. 비둘기집 원리에 따르면 이는 A가 수신한 일련번호가 아닌 일련번호를 사용하여 수락 가능한 증명을 생성한다는 것을 의미합니다. 방정식 (24)에 결합 결합을 적용하면 이 사건이 최소한 1/2p(λ) 확률로 발생할 수 있다는 것을 알 수 있습니다. 요약하자면, 우리는

평균화 인수를 통해 인덱스 j ∈ J를 수정할 수 있으며 이는 1/(2kp(λ))의 이점으로 동일한 이벤트를 제공합니다. 이제 A에 인덱스 I 의 시뮬레이션 증명을 제공하는 하이브리드로 전환하겠습니다.

주장 5.9. 다음과 같은 다항식 q (·)가 존재합니다.

나중에 주장 5.9의 증거를 볼 것입니다. 지금은 이 주장이 유효하다고 가정하고 Ext가 x에 대한 유효한 증인을 추출할 수 있는 공격자를 정의할 수 있습니다.

주장 5.10. 다음과 같은 다항식 q ′ (·)이 존재합니다.

우리는 곧 클레임 5.10에 대한 증거를 보게 될 것입니다. 한편, 이 주장이 사실이라면 식 (19)와 정면으로 모순이 된다. 따라서 입증되어야 할 것은 두 가지 주장, 즉 청구항 5.9와 청구항 5.10뿐입니다. 우리는 전자의 주장을 증명하는 것부터 시작합니다.

청구 증명 5.9. 먼저 우리의 전략이 잘 정의되어 있고 이러한 k 포인트를 독립적으로 프로그래밍할 수 있다는 점을 주장해야 합니다 . 그러면 우리는 시뮬레이션된 증명으로 하나씩 전환하는 것이 구별 불가능하다고 주장할 수 있습니다. 우리는 시뮬레이터가 예상 다항식 시간에 실행될 것이라고 주장할 것입니다. Lemma 5.7에 따르면 시뮬레이터가 프로그래밍할 k 포인트는 압도적인 확률로 구별됩니다. 게다가 우리는 양자 랜덤 오라클이 여러 개의 서로 다른 지점에서 프로그래밍될 수 있다고 가정했기 때문에(정의 3.10), 우리의 시뮬레이터는 잘 정의되어 있습니다.

이제 우리는 하이브리드 논증을 통해 정직하게 생성된 증명과 시뮬레이션된 증명의 구별이 불가능하다고 주장합니다. 모순을 위해 방정식 (21)과 방정식 (22) 사이의 확률 차이가 일부 다항식 p'(·)에 대해 1/p'(λ)라고 가정합니다. 우리는 i 번째 증명을 생성된 증명자에서 시뮬레이션된 증명으로 전환하는 각 i ∈ [k − 1]에 대해 일련의 연속적인 하이브리드를 구성합니다. 이 혼합 논증에 따르면, ℓ번째 증명을 전환하는 경우 적어도 1/(kp' (λ))의 확률 차이가 있는 일부 위치 ℓ ∈ [k − 1]이 있어야 합니다. 이제 다음 두 설정을 구별할 수 있는 축소를 공식화합니다.

우리는 먼저 축소가 A에 제공하는 관점이 게임 중 하나와 일치한다고 주장합니다: ℓ th까지의 모든 증명이 시뮬레이션되거나 ℓ th까지의 모든 증명이 시뮬레이션되는 곳. Lemma 5.7에 따르면 도전자가 계산하거나 프로그래밍한 포인트는 감소 프로그램이 실행하는 포인트와 구별됩니다. 따라서 A가 인터페이스하는 오라클을 수정하는 축소가 허용됩니다(단계 (4) 참조). 요약하면, A는 받은 모든 증명과 일치하는 오라클에 대한 액세스 권한을 받게 됩니다.

A가 두 게임 모두에서 예상되는 관점과 직접적으로 일치하는 관점을 가지고 있다고 가정할 때, 감소의 이점은 A의 이점과 동일하며 최소 1/(kp′(λ))입니다. 이는 우리 프로토콜의 영지식 속성과 모순됩니다. 따라서 우리의 원래 주장은 사실이어야 합니다.

이제 우리는 계속해서 후자의 주장을 증명합니다.

청구 증명 5.10. 청구항 5.9가 성립한다는 점을 고려하면 이는 다음을 의미합니다.

먼저 우리는 A의 관점이 식 (24)와 식 (25)에 나타나는 게임과 동일하다는 점을 주장해야 합니다. A가 인터페이스하는(단계 (4) 참조) 오라클은 수신하는 모든 증명과 일치합니다.

방정식 (25)를 통해 우리는 다음과 같은 결론에 도달합니다.

일부 매개변수 다항식 p *(·)와 무시할 수 있는 함수 negl0(·) 및 negl1(·)을 갖는 지식 증명(정의 3.11)의 정의에 의해 다음과 같은 일부 다항식 q ′(·)가 존재한다는 것을 알 수 있습니다.

이것이 우리 주장의 증거를 완성합니다.

우리 주장의 증명을 완료함으로써 우리는 정리 진술의 증명을 마무리했습니다.

결과 5.11. 주입적 단방향 함수가 존재하고 양자 이후 iO가 존재한다고 가정하면, 양자 랜덤 오라클에서 NP에 대한 추출 프로토콜을 사용하여 비대화형 지식 소리, 계산상 영지식 및 (k − 1)-to-kclonable이 존재합니다. 모델(정의 5.4).

증거. 이는 정리 3.14와 정리 5.8을 따릅니다.

따라서 우리는 그림 5가 복제 불가 정의인 정의 5.4에 따라 정의된 ROM 모델의 복제 불가 NIZK PoK임을 보여주었습니다.