量子ランダムOracleモデルにおける複製不可能な非対話型のゼロ知識

リンク表

要約とはじめに

技術概要

予選

CRS モデルにおける複製不可能な非インタラクティブなゼロ知識

Quantum Ramdon Oracle モデルにおけるクローン不可能な NIZK

複製不可能な知識の署名

参考文献

5 量子ランダム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-access を使用して、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 の定義と組み合わせると、次のようになります。

したがって、私たちのプロトコルが知識の証明プロトコルであることがわかります。

量子シミュレータを使用した計算上の正直検証者ゼロ知識。 Π.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。

（１）挑戦者から（現実または模擬の）（α、β、γ）を受け取る。

(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、およびすべての硬分布 {Xλ についての場合、量子ランダム オラクル O に関してクローン不可能なセキュリティを満たします。 RL 上の ,Wλ}λ∈N に対して、すべての λ ∈ N に対して、次のような無視できる関数 negl1 (·) が存在します。

定義 5.4 (QROM 内の (k−1)-to-k-Unclonable Extractable 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-Unclonable with Extraction: すべての多項式サイズの量子回路 A に対して、k − 1 個のインスタンスと証人ペアのすべてのタプルに対して、次のようなオラクル支援多項式サイズの量子回路 E が存在します。 x1、ω1)、. 。 。 ,(xk−1, ωk−1) ∈ R、すべての x に対して定義します。

多項式 p(·) が存在するようにします。

この場合、次のような多項式q (·) も存在します。

前のセクションと同様に、次の補題があります。

補題 5.5。 Π = (Setup, P,V) を非対話型の 1 対 2 複製不可能なゼロ知識量子プロトコル (定義 5.4) とします。この場合、Π は定義 5.3 を満たします。

補題 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.3) を破る削減を構築します。これは、(付録 A) で示したように、定義 (定義 5.4) によって暗示されています。挑戦者は、ランダムなオラクル O にアクセスして、ハードインスタンスと証人のペア (x, w) ← (X ,Y) と証明 π ← PO(x, w) をサンプリングします。次に、チャレンジャーは (x, π) をリダクションに転送します。リダクションは、O へのオラクル アクセスも持ちます。次に、リダクションは |$i = π および s = x を設定します。リダクションにより、(|$i, s) が敵対者 A に送信され、敵対者 A は (|$0, s0, |$1, s1) を返します。次に、リダクションにより i ∈ {0, 1} に対して πi = |$ii が解析され、設定されます。次に、リダクションにより π0 と π1 が挑戦者に送り返されます。

5.4 構築と分析

補題 5.7。 λ, k ∈ N と公開鍵量子マネーミニスキーム ( NoteGen,Ver ) が与えられるとします。点を q1、... とします。 。 。 , qk を次の構造で与えます。点 q には、 NoteGen (1λ ) に従ってサンプリングされたシリアル番号 s が含まれます。

点ｑ１、． 。 。 , 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) は、非インタラクティブな知識サウンド、計算上ゼロ知識、および量子ランダム オラクル モデル (定義 3.11) の L の抽出プロトコルで (k − 1)-to-k 複製不可能です。 ）。

証拠。パラメータとプリミティブを定理ステートメントで指定したとおりにします。完全性は図 5 のプロトコル構造から得られると主張し、残りの特性を以下で証明します。

我々は持っています

多項式サイズの量子回路 A と x が次のように与えられるとします。

次のように、一部の A および O への oracle-access を使用して 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-access とランダムな oracle O へのプログラム アクセスを持つ Sim を次のように定義します。

入力: x (受信する可能性のある証人を無視します)。

クエリ (x, w) ∈ R のみを作成できるオラクル支援識別子 D と、次のような多項式 p(·) が与えられるとします。

Π′ のゼロ知識特性への還元を次のように定義します。

還元: D へのオラクル アクセスと O へのプログラム アクセスが与えられた場合、Π' のゼロ知識になります。

D からのすべての (x, w) について:

D のビューは、図 5 のプロトコルまたは Sim のビューと一致します。したがって、私たちの還元には、 Π' のゼロ知識特性を破る点で同じ利点があるはずです。矛盾に達したため、プロトコルはゼロ知識でなければなりません。

クローン作成不可能な抽出可能性。 Ext を、以前に定義した抽出器の量子回路とします (図 5 が知識の証明であるという証明において)。 Sim を、以前に定義したシミュレーターの量子回路とします (図 5 がゼロ知識プロトコルであることの証明において)。次のように、一部の A への oracle-access を持つエクストラクター E を定義します。

ハードワイヤード: I ⊆ [k − 1]、J ⊆ [k]、x1、... のいずれかの選択。 。 。 , xk−1 ∈ R, x.

(1) ℓ ∈ J を一様にランダムにサンプリングします。

(2) シミュレート可能で抽出可能なランダムオラクル O をインスタンス化します。A との対話中、O で Ext を実行します (これには巻き戻しが含まれる場合があります。その場合、A を巻き戻して次のステップを繰り返します)。 Aが出力したℓ番目の校正に対してExtが抽出することを要求します。

(3) ι ∈ [k − 1] の πι ← Sim(xι) を計算します。ここで、Sim がプログラムするすべての点をリスト P に格納します。

(4) {πι}ι∈[k−1]をAに送信する。

(5) A からのすべてのクエリについて、クエリが P にある場合は、P からの応答で応答します。そうでない場合は、クエリを O に転送し、応答を A に送り返します。Ob がこの修正されたランダム オラクルを示すものとします。

(7) Ext の結果を w として出力します。

式 (24) を考慮すると、次の 2 つのケースのいずれかに該当する可能性があります。A は、正直に生成されたプルーフと同じシリアル番号を持つ 2 つの受け入れ可能なプルーフを生成するか、A は生成しません。これら 2 つのシナリオを個別に検討し、それぞれが矛盾に達することを示します。

シナリオ 1

A が、正直に生成されたプルーフと同じシリアル番号を持つ 2 つの受け入れ可能なプルーフを生成するとします。方程式 (24) に和集合を適用すると、このイベントは少なくとも 1/2p(λ) の確率で発生する可能性があります。象徴的に言えば、

シナリオ 2

あるいは、A が、正直に生成されたプルーフと同じシリアル番号を持つ 2 つの受け入れ可能なプルーフを生成しなかったとします。鳩の巣原理により、これは、A が受け取ったシリアル番号の中にはないシリアル番号を使用して受理証明を生成することを意味します。方程式 (24) に和集合を適用すると、このイベントは少なくとも 1/2p(λ) の確率で発生する可能性があります。要約すると、

平均化引数を通じてインデックス j ∈ J を修正すると、1/(2kp(λ)) の利点を持つ同じイベントが得られます。次に、インデックスIでシミュレートされた証明を A に提供するハイブリッドに切り替えます。

請求項5.9。次のような多項式q (・) が存在します。

クレーム 5.9 の証明については後で説明します。今のところ、この主張が成り立つと仮定すると、Ext が x の有効な証人を抽出できる敵を定義できます。

請求項5.10。次のような多項式q ' (・) が存在します。

主張 5.10 の証拠が間もなく示されるでしょう。一方、この主張が真実であれば、式 (19) と直接矛盾することになります。したがって、証明される必要があるのは、クレーム 5.9 とクレーム 5.10 の 2 つのクレームだけです。まず前者の主張を証明することから始めます。

請求の証明 5.9。まず、戦略が明確に定義されており、これらの k ポイントを独立してプログラムできることを主張する必要があります。そうすれば、模擬証明に 1 つずつ切り替えることの区別がつかないことを主張できます。私たちのシミュレーターは予想される多項式時間で実行されると主張します。補題 5.7 により、シミュレータがプログラムする k 点は、圧倒的な確率で明確になります。さらに、定義 3.10 で量子ランダム オラクルが複数の異なる点でプログラムできると仮定したため、シミュレータは明確に定義されています。

ここで、ハイブリッド議論を通じて、シミュレートされた証明と正直に生成された証明の区別がつかないことを議論します。矛盾を避けるために、ある多項式 p ' (・) について、式 (21) と式 (22) の確率差が 1/p' (λ) であると仮定します。各 i ∈ [k − 1] に対して一連の連続ハイブリッドを構築し、i 番目の証明を生成された証明者からシミュレートされた証明者に切り替えます。このハイブリッド引数により、ℓ 番目の証明の切り替えに少なくとも 1/(kp' (λ)) の確率差がある位置 ℓ ∈ [k − 1] が存在する必要があります。ここで、これら 2 つの設定を区別できるリダクションを形式化します。

まず、リダクションが A に提供するビューは、ℓ 番目までのすべての証明がシミュレートされるゲーム、または ℓ 番目までのすべての証明がシミュレートされるゲームの 1 つと一致すると主張します。補助定理 5.7 により、挑戦者が計算またはプログラムしたポイントは、リダクションがプログラムしたポイントとは区別されます。したがって、リダクションにより、A がインターフェースするオラクルを変更することができます (ステップ (4) を参照)。要約すると、A には、受け取ったすべての証明と一致するオラクルへのアクセスが提供されます。

A がいずれかのゲームで期待されるビューと直接一致するビューを持っているとすると、削減による利点は A の利点と同じであり、少なくとも 1/(kp' (λ)) です。これは、プロトコルのゼロ知識特性と矛盾します。したがって、私たちの当初の主張は真実でなければなりません。

さて、後者の主張の証明を続けます。

請求の証明5.10。請求項 5.9 が成り立つことを考えると、これは次のことを意味します。

まず、A の視点は、方程式 (24) と方程式 (25) の両方に現れるゲームと同一のままであると主張しなければなりません。 A が接続するオラクル (ステップ (4) を参照) は、A が受け取るすべての証明と一致します。

式 (25) を通じて、次の結論に達します。

いくつかのパラメータ多項式 p ∗ (·) と無視できる関数 negl0 (·) および negl1 (·) を持つ知識証明の定義 (定義 3.11) により、次のような多項式 q ' (·) が存在することがわかります。

これで私たちの主張の証明が完了します。

私たちの主張の証明を完了することで、定理ステートメントの証明が完了します。

結果 5.11。単射一方向性関数が存在し、ポスト量子 iO が存在すると仮定すると、量子ランダムオラクルにおける NP の抽出プロトコルを使用して、非対話型知識サウンド、計算上ゼロ知識、(k − 1) からクローン化できる知識サウンドが存在します。モデル (定義 5.4)。

証拠。これは定理 3.14 と定理 5.8 から導き出されます。

したがって、図 5 は、複製不可能性の定義である定義 5.4 に従って定義された ROM モデル内の複製不可能な NIZK PoK であることを示しました。