Kuantum Rastgele Oracle Modelinde Klonlanamayan Etkileşimli Olmayan Sıfır Bilgi

Bağlantı Tablosu

Özet ve Giriş

Teknik Genel Bakış

Ön Hazırlıklar

CRS Modelinde Klonlanamayan Etkileşimsiz Sıfır Bilgi

Quantum Ramdon Oracle Modelinde Klonlanamayan NIZK

Klonlanamayan Bilgi İmzaları

Referanslar

Kuantum Rastgele Oracle Modelinde Klonlanamayan 5 NIZK

5.1 Değiştirilmiş Bir Sigma Protokolü

Biraz değiştirilmiş bir sigma protokolünü tanıtarak başlayacağız. Önümüzdeki bölümlerde yapımız Fiat-Shamir'in bu değiştirilmiş protokole uygulanmasını içerecek.

Kanıt. Mükemmel tamlık Bu doğrudan Π'nın mükemmel tamlığından kaynaklanır.

ve ilişkili λ ∈ N'yi karşılayan herhangi bir x

sahibiz

Ext 3'ü Π.Ext'e ve bazı A'ya Oracle erişimiyle aşağıdaki gibi tanımlarız:

Giriş: x, S.

(1) AΠ'dan (x, α, s) verildiğinde: α'yı Π.Ext'e gönderin, β'yı Π.Ext'ten alın ve β'yı AΠ'ya gönderin.

(2) AΠ'dan γ alındıktan sonra: γ'yı Π.Ext'e gönderin.

(3) Π.Ext sonucunu w olarak çıktılayın.

Aşağıdaki parametre setini tanımlıyoruz: c = cΠ, p(·) = pΠ(·), negl0 (·) = negl0,Π(·) ve negl1 (·) = negl1,Π(·).

Polinom boyutlu kuantum devresi A = (A 0, A 1) ve (x, S) öyle verilsin ki

Şimdi AΠ = (A0,Π, A1,Π)'yi A'ya oracle erişimiyle tanımlıyoruz. A0,Π S ile donanımsal olarak donatılmıştır, x girişini alır, (x, S)'yi A0'a gönderir, ((x, α, s) alır ), |sti) A0'dan ve çıkışlar (α, |sti). A1,Π, S ile donanımsal olarak bağlantılıdır, (x, |sti, β) girişini alır, ((x, S), |sti, β)'yi A1'e gönderir, A1'den γ alır, γ çıkışını yapar. Kanıtımızın yapısı ve doğrulayıcımızın tanımı gereği bu şu anlama gelir:

bu da Denklem (15)'teki kısıtı karşılamaktadır. Bu, Ext tanımımızla birleştirildiğinde şu anlama gelir:

Böylece protokolümüzün bilgi protokolünün kanıtı olduğunu gösteriyoruz.

Kuantum Simülatörü ile Hesaplamalı Dürüst Doğrulayıcı Sıfır Bilgi . Π.Sim, Π için hesaplamalı dürüst doğrulayıcı sıfır bilgi kuantum simülatörü olsun. Π.Sim'e Oracle erişimi olan Sim'i şu şekilde tanımlıyoruz:

Giriş: x, S.

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

(2) S.'den örnekler.

(3) Çıkış ((x, α, s), β, γ).

Bir polinom p(·), polinom boyutunda bir kuantum devresi D, λ ∈ N ve ((x, S), w) ∈ R öyle bir şekilde verilsin ki

Π'nin sıfır bilgi özelliğine yönelik bir azalmayı şu şekilde tanımlarız:

Azaltma: D'ye kehanet erişimi verildiğinde Π'nin sıfır bilgisine.

Kablolu bağlantı: x, S.

(1) Meydan okuyan kişiden (gerçek veya simüle edilmiş) (α, β, γ) alın.

(2) S.'den örnekler.

(3) ((x, α, s), β, γ)'yı D'ye gönderin. D'den b'yi alın.

(4) Çıkış b.

Meydan okuyan kişi Π için gerçek (veya simüle edilmiş) bir kanıt gönderdiğinde, indirgeme, gerçek (sırasıyla simüle edilmiş) kanıtla aynı olan bir kanıt üretir. Bu nedenle, bu azalma D' nin ayırt edici avantajını korur. Bu, Π'nın sıfır bilgi özelliğine karşı bir çelişkiye ulaşır. Bu nedenle protokolümüz sıfır bilgi olmalıdır.

Dürüst kanıtlayıcı P.Com,

bu bir çelişkidir. Bu nedenle protokolümüzün öngörülemeyen taahhütleri olması gerekir.

Sonuç 5.2. Teorem 5.1'de tanımlanan kuantum sonrası sigma protokolüne uygulanan Fiat-Shamir buluşsal yöntemi, QROM'da klasik bir kuantum sonrası NIZKPoK Π′ verir (Tanım 3.11).

Kanıt . Bunu Teorem 5.1 ve Teorem 3.12 takip etmektedir.

5.2 Klonlanamazlık Tanımları

Kuantum rastgele oracle modelindeki klonlanamayan NIZK'ler, CRS modeline benzer şekilde tanımlanır; bu tanımları, aşağıda tamlık sağlamak için QRO modelinde tekrarlıyoruz.

Tanım 5.3. (Sert Örnekler için Klonlanamayan Güvenlik). Bir kanıt (P,V), bir kuantum rastgele kahin O'ya göre klonlanamaz güvenliği karşılar; eğer karşılık gelen RL ilişkisine sahip her L dili için, her polinom boyutlu kuantum devre ailesi için {Cλ}λ∈N ve her sabit dağılım için {Xλ RL üzerinde ,Wλ}λ∈N, ihmal edilebilir bir negl1 (·) fonksiyonu vardır, öyle ki her λ ∈ N için,

Tanım 5.4 ((k−1)-to-k-Klonlanamayan Çıkarılabilir NIZK, QROM'da). Güvenlik parametresi λ ∈ N ve karşılık gelen L dili ile NP ilişkisi R verilsin. Π = (P,V), P ve V poli(λ) boyutlu kuantum algoritmaları olacak şekilde verilsin. Herhangi bir (x, ω) ∈ R için, P'nin girdi olarak bir örnek ve tanık çifti (x, ω) alması ve π çıktısı alması ve V'nin girdi olarak bir x örneği ve kanıt π alması ve {0'da bir değer çıktısı alması, 1}.

Π, aşağıdaki durum geçerliyse, rastgele bir oracle O'ya göre L dili için etkileşimli olmayan (k − 1)'den k'ye klonlanamayan bir NIZKPoK protokolüdür:

• Π, kuantum rastgele oracle modelinde L dili için bir NIZKPoK protokolüdür (Tanım 3.11).

• (k−1)-k-Çıkartma ile Klonlanamaz: Oracle destekli polinom boyutlu bir kuantum devresi E vardır, öyle ki her polinom boyutlu kuantum devresi A için, her k − 1 örnek-tanık çifti kümesi için ( x1, ω1), . . . ,(xk−1, ωk−1) ∈ R, tanımladığımız her x için

öyle ki bir p(·) polinomu var, burada

o zaman ayrıca bir q (·) polinomu vardır, öyle ki

Önceki bölüme benzer şekilde aşağıdaki lemmaya sahibiz.

Lemma 5.5. Π = (Kurulum, P,V) etkileşimli olmayan, 1'den 2'ye klonlanamayan sıfır bilgi kuantum protokolü olsun (Tanım 5.4). O halde Π Tanım 5.3'ü karşılar.

Lemma 5.5'in kanıtı için Ek A'ya başvuruyoruz.

5.3 Klonlanamayan NIZK, QROM'da Açık Anahtar Kuantum Parasını İfade Ediyor

Teorem 5.6. O bir kuantum rastgele kehanet olsun. (X ,W), L ∈ NP dili üzerinde bir sert dağılım olsun. Π = (P,V), QRO modelinde (Tanım 5.4) L için 1'den 2'ye klonlanamayan, etkileşimli olmayan, mükemmel şekilde tamamlanmış, hesaplama açısından sıfır bilgi protokolü olsun.

O halde (P,V), Şekil 4'te açıklandığı gibi QRO modelinde (Tanım 3.15) bir genel anahtar kuantum para mini şemasını ima eder.

Kanıt . Mükemmel Doğruluk . Bu doğrudan Π'nın mükemmel bütünlüğünden kaynaklanır. Değiştirilemezlik. p(·) bir polinom ve A da kuantum polinom-zaman hasmı olsun, öyle ki sonsuz sayıda λ ∈ N + için,

Tanımımızın (Tanım 5.4) ima ettiğini gösterdiğimiz (Ek A'da) klonlanamazlık tanımını (Tanım 5.3) bozan bir indirgeme inşa ediyoruz. Rastgele O Oracle'a erişimi olan yarışmacı, somut örnek-tanık çiftini (x, w) ← (X ,Y) ve bir π ← PO(x, w) kanıtını örnekler. Meydan okuyan kişi daha sonra (x, π)'yi, aynı zamanda O'ya kehanet erişimi olan indirgemeye iletir. İndirgeme daha sonra |$i = π ve s = x'i ayarlar. İndirgeme, düşman A'ya (|$i, s) gönderir ve o da geri döner (|$0, s0, |$1, s1). İndirgeme daha sonra ayrıştırır ve i ∈ {0, 1} için πi = |$ii değerini belirler. İndirgeme daha sonra π0 ve π1'i meydan okuyana geri gönderir.

5.4 İnşaat ve Analiz

Lemma 5.7. λ, k ∈ N ve açık anahtarlı bir kuantum para mini şeması ( NoteGen,Ver ) verilsin. q1, . . . , qk aşağıdaki yapıya sahip olarak verilebilir: bir q noktası, NoteGen (1λ) göre örneklenmiş bir seri numarası içerir.

q1, . . . qk çok büyük olasılıkla farklı olmalıdır.

Kanıt . Her nokta, kuantum para üretme algoritması NoteGen (1λ) göre örneklenmiş bir seri numarası içerir. Kuantum paranın seri numaralarının tahmin edilemezliği nedeniyle (Tanım 3.13), dürüstçe oluşturulmuş tüm k seri numaralarının büyük olasılıkla farklı olması gerekir. Dolayısıyla bu k noktaları büyük olasılıkla farklı olacaktır.

Şimdi Şekil 5'teki yapımızı tanıtıyoruz ve bu bölümün ana teoremini kanıtlıyoruz.

Teorem 5.8. k(·) bir polinom olsun. Karşılık gelen L dili ile NP ilişkisi R verilsin.

( NoteGen, Ver ) bir genel anahtar kuantum para mini şeması olsun (Tanım 3.13) ve Π = (P,V) bir kuantum sonrası sigma protokolü (Tanım 3.4) olsun.

Şekil 5'te tanımlandığı gibi (P,V), etkileşimli olmayan bir bilgi sesi, hesaplama açısından sıfır bilgi ve kuantum rastgele oracle modelinde L için çıkarma protokolüyle (k − 1)-k-klonlanamaz olacaktır (Tanım 3.11). ).

Kanıt. Parametreler ve ilkeller teorem ifadesinde verildiği gibi olsun. Tamlığın Şekil 5'teki protokol yapısından kaynaklandığını iddia ediyoruz ve geri kalan özellikleri aşağıda kanıtlıyoruz.

sahibiz

Polinom boyutlu kuantum devresi A ve x öyle verilsin ki

AF S'nin bazı A ve O'ya oracle erişimiyle aşağıdaki şekilde tanımlanmasına izin verin:

Giriş: x, S.

(1) A'dan bir (x, α, s) sorgusu verildiğinde: (x, α, s)'yi O'ya gönder, O'dan β al ve β'yı A'ya gönder.

(2) A'dan π = (|$i, s, α, β, γ) alındığında: çıktı πF S = ((x, α, s), β, γ).

Kanıtımızın yapısı ve doğrulayıcımızın tanımı gereği bu şu anlama gelir:

bu da Denklem (16)'daki kısıtı karşılamaktadır. Bu, Ext ve S tanımımızla birleştirildiğinde şunu elde ettiğimiz anlamına gelir:

Böylece protokolümüzün bilgi protokolünün kanıtı olduğunu gösteriyoruz.

Sıfır Bilgi. SimF S, Sonuç 5.2'deki Π′'nin simülatörü olsun (burada Π, Teorem 5.1'i somutlaştırır). RF S, Π′'nin R'ye göre ilişkisi olsun. Sim'i, SimF S'ye oracle erişimi ve bazı rastgele oracle O'ya program erişimi ile tanımlıyoruz:

Girdi: x (alabileceği tanıkları dikkate almaz).

Yalnızca (x, w) ∈ R sorgularını yapabilen kehanet destekli bir D ayırıcısı ve bir p(·) polinomu şu şekilde verilsin:

Π′'nin sıfır bilgi özelliğine yönelik bir azalmayı şu şekilde tanımlarız:

Azaltma: D'ye Oracle erişimi ve O'ya program erişimi verilen Π′'nin sıfır bilgisine.

D'den gelen her (x, w) için:

D'nin görünümü, Şekil 5 veya Sim'deki protokolümüzün görünümüyle eşleşir. Bu nedenle indirgememiz Π''nin sıfır bilgi özelliğini kırmada aynı avantaja sahip olmalıdır. Bir çelişkiye varıyoruz, dolayısıyla protokolümüz sıfır bilgi olmalıdır.

Klonlanamayan Ekstraktlanabilirlik. Daha önce tanımladığımız çıkarıcının kuantum devresi Ext olsun (Şekil 5'in bilginin kanıtı olduğunu ispatlıyoruz). Sim, daha önce tanımladığımız simülatörün kuantum devresi olsun (Şekil 5'in sıfır bilgi protokolü olduğuna dair kanıtımızda). Bazı A'lara Oracle erişimi olan bir çıkarıcı E'yi aşağıdaki gibi tanımlıyoruz:

Donanımla bağlantılı: I ⊆ [k − 1], J ⊆ [k], x1, . . . , xk−1 ∈ R, x.

(1) ℓ ∈ J numuneleri eşit ve rastgele.

(2) Simüle edilebilir ve çıkarılabilir bir rastgele kahin O'yu başlatır. A ile etkileşim boyunca Ext'i O üzerinde çalıştırır (bu, geri sarmayı içerebilir; bu durumda A'yı geri sararız ve aşağıdaki adımları tekrarlarız). A'nın ℓ'inci kanıt çıktısına göre Ext alıntılarının yapılmasını isteyin.

(3) ι ∈ [k − 1] için πι ← Sim(xι)'yi hesaplayın; burada Sim'in programlayacağı tüm noktaları bir P listesine saklarız.

(4) {πι}ι∈[k−1]'i A'ya gönderin.

(5) A'dan gelen her sorgu için, eğer sorgu P'deyse, P'den gelen yanıtla yanıt verin. Aksi takdirde, sorguyu O'ya iletin ve yanıtı A'ya geri gönderin. Ob bu değiştirilmiş rastgele kehaneti göstersin.

(7) Ext'in sonucunu w olarak verir.

Denklem (24) göz önüne alındığında, aşağıdaki iki durumdan birinde olabiliriz: Ya A, dürüstçe oluşturulmuş bir kanıtla aynı seri numarasına sahip iki kabul edici kanıt üretir ya da A üretmez. Bu iki senaryoyu ayrı ayrı ele alıyoruz ve her birinin bir çelişkiye vardığını gösteriyoruz.

Birinci Senaryo

A'nın, dürüstçe oluşturulmuş bir kanıtla aynı seri numarasına sahip iki kabul edici kanıt ürettiğini varsayalım. Denklem (24)'e bağlı bir birlik uygulayarak bu olayın en az 1/2p(λ) olasılıkla gerçekleşebileceğini elde ederiz. Sembolik,

İkinci Senaryo

Alternatif olarak, A'nın dürüstçe üretilmiş bir kanıtla aynı seri numarasına sahip iki kabul edici kanıt üretmediğini söyleyin. Güvercin deliği ilkesine göre bu, A'nın, aldığı seri numaraları arasında olmayan bir seri numarasına sahip bir kabul kanıtı ürettiği anlamına gelir. Denklem (24)'e bağlı bir birlik uygulayarak bu olayın en az 1/2p(λ) olasılıkla gerçekleşebileceğini elde ederiz. Özetle elimizde bu var

Ortalama alma argümanı aracılığıyla, j ∈ J indeksini sabitleyebiliriz, bu da bize aynı olayı 1/(2kp(λ)) avantajıyla verir. Şimdi A'ya I endekslerinde simüle edilmiş ispatlar sunduğumuz bir meleze geçeceğiz.

İddia 5.9. Öyle bir polinom q (·) vardır ki

Daha sonra İddia 5.9'un kanıtını göreceğiz. Şimdilik bu iddianın geçerli olduğunu varsayarak Ext'in x için geçerli bir tanık çıkarabileceği bir düşman tanımlayabiliriz.

İddia 5.10. Öyle bir q ′ (·) polinomu vardır:

Yakında İddia 5.10'un kanıtını göreceğiz. Bu arada eğer bu iddia doğruysa Denklem (19) ile doğrudan çelişkiye düşeriz. Dolayısıyla kanıtlanması gereken tek şey şu iki iddiadır: İstem 5.9 ve İstem 5.10. Önceki iddiayı kanıtlayarak başlıyoruz.

İddia Kanıtı 5.9. Öncelikle stratejimizin iyi tanımlandığını, bu k noktalarını bağımsız olarak programlayabileceğimizi iddia etmemiz gerekiyor . O zaman tek tek simüle edilmiş delillere geçmenin ayırt edilemezliğini tartışabiliriz. Simülatörümüzün beklenen polinom zamanında çalışacağını tartışacağız. Lemma 5.7'ye göre simülatörümüzün programlayacağı k noktaları büyük olasılıkla farklı olacaktır. Ayrıca, kuantum rastgele kehanetimizin birden fazla farklı noktada programlanabileceğini varsaydığımızdan (Tanım 3.10) simülatörümüz iyi tanımlanmıştır.

Şimdi simüle edilmiş kanıtların dürüstçe üretilmiş kanıtlardan ayırt edilemezliğini hibrit bir argümanla tartışıyoruz. Çelişki olsun diye, Denklem (21) ile Denklem (22) arasındaki olasılık farkının bazı p ′ (·) polinomları için 1/p′ (λ) olduğunu varsayalım. Her i ∈ [k − 1] için bir dizi ardışık hibrit oluştururuz ve burada i'inci ispatı oluşturulan kanıttan simüle edilmiş kanıta geçiririz. Bu hibrit argümana göre, ℓ'inci kanıtın değiştirilmesinin en az 1/(kp′ (λ)) olasılık farkına sahip olduğu bir ℓ ∈ [k − 1] konumu olmalıdır. Şimdi bu iki ayarı birbirinden ayırabilecek bir indirgemeyi resmileştiriyoruz:

Öncelikle indirgemenin A'ya sağladığı görüşün oyunlardan biriyle eşleştiğini ileri sürüyoruz: ℓ'ye kadar olan tüm kanıtların simüle edildiği veya ℓ'ye kadar olan tüm kanıtların simüle edildiği yer. Lemma 5.7'ye göre, yarışmacı tarafından hesaplanan veya programlanan puan, azaltma programlarının puanlarından farklı olacaktır. Bu şekilde, indirgemenin A'nın arayüz oluşturduğu kehaneti değiştirmesine izin verilir (bkz. adım (4)). Özetle, A'ya, aldığı tüm kanıtlarla tutarlı bir kehanete erişim sağlanacak.

A'nın her iki oyunda da beklenen görünümüyle doğrudan eşleşen bir görüşe sahip olduğu göz önüne alındığında, bu durumda indirgemenin avantajı A'nın avantajıyla aynıdır, yani en az 1/(kp′ (λ)). Bu, protokolümüzün sıfır bilgi özelliğiyle çelişkilidir. Dolayısıyla asıl iddiamızın doğru olması gerekir.

Şimdi ikinci iddiayı kanıtlamaya devam ediyoruz.

İddia Kanıtı 5.10. İddia 5.9'un geçerli olduğu göz önüne alındığında, bu şu anlama gelir:

Öncelikle A'nın görüşünün hem Denklem (24) hem de Denklem (25)'te görünen oyunla aynı kaldığını iddia etmeliyiz. A'nın etkileşime girdiği kehanet (bkz. adım (4)) aldığı tüm kanıtlarla tutarlı olacaktır.

Denklem (25) aracılığıyla şu sonuca ulaşıyoruz:

Bazı parametreler polinom p ∗ (·) ve ihmal edilebilir fonksiyonlar negl0 (·) ve negl1 (·) olan bir bilgi kanıtının tanımıyla (Tanım 3.11), bazı q ′ (·) polinomunun var olduğunu biliyoruz:

bu da iddiamızın kanıtını tamamlıyor.

İddialarımızın ispatlarını tamamlayarak teorem ifademizin ispatını tamamlamış oluyoruz.

Sonuç 5.11. Enjeksiyonlu tek yönlü fonksiyonların mevcut olduğunu ve kuantum sonrası iO'nun mevcut olduğunu varsayarsak, etkileşimli olmayan bir bilgi sesi, hesaplama açısından sıfır bilgi ve kuantum rastgele kehanetinde NP için çıkarma protokolü ile (k - 1)'den kun'a klonlanabilir bir bilgi vardır. modeli (Tanım 5.4).

Kanıt. Bu, Teorem 3.14 ve Teorem 5.8'den kaynaklanmaktadır.

Böylece Şekil 5'in, klonlanamazlık tanımımız Tanım 5.4'e göre tanımlandığı gibi ROM modelinde klonlanamaz bir NIZK PoK olduğunu gösterdik.