Hatalarla öğrenmek - Learning with errors

Hatalarla öğrenmek (LWE) hesaplama problemi doğrusal bir sonuç çıkarmak ${ displaystyle n}$ -ary işlevi ${ displaystyle f}$ verilen örneklerden sonlu bir halka üzerinden ${ displaystyle y_ {i} = f ( mathbf {x} _ {i})}$ Bazıları hatalı olabilir. LWE probleminin çözülmesinin zor olduğu varsayılır,^[1] ve bu nedenle kriptografi.

Daha kesin olarak, LWE problemi aşağıdaki gibi tanımlanır. İzin Vermek ${ displaystyle mathbb {Z} _ {q}}$ tamsayılar halkasını gösterir modulo ${ displaystyle q}$ ve izin ver ${ displaystyle mathbb {Z} _ {q} ^ {n}}$ kümesini belirtmek ${ displaystyle n}$ -vektörler bitmiş ${ displaystyle mathbb {Z} _ {q}}$ . Belirli bir bilinmeyen doğrusal fonksiyon var ${ displaystyle f: mathbb {Z} _ {q} ^ {n} rightarrow mathbb {Z} _ {q}}$ ve LWE probleminin girdisi çiftlerin bir örneğidir ${ displaystyle ( mathbf {x}, y)}$ , nerede ${ displaystyle mathbf {x} in mathbb {Z} _ {q} ^ {n}}$ ve ${ displaystyle y in mathbb {Z} _ {q}}$ , böylece yüksek olasılıkla ${ displaystyle y = f ( mathbf {x})}$ . Ayrıca, eşitlikten sapma, bilinen bazı gürültü modellerine göredir. Sorun, işlevi bulmayı gerektirir ${ displaystyle f}$ veya yüksek olasılıkla bazı yakın yaklaşımları.

LWE sorunu, Oded Regev 2005'te^[2] (2018'i kim kazandı Gödel Ödülü bu çalışma için), bir genellemedir eşlik öğrenme sorun. Regev, LWE sorununun çözülmesinin en kötü birkaç durum kadar zor olduğunu gösterdi. kafes sorunları. Daha sonra, LWE problemi bir sertlik varsayımı yaratmak açık anahtarlı şifreleme sistemleri,^[2]^[3] benzeri hatalarla halka öğrenme anahtar değişimi Peikert tarafından.^[4]

Tanım

Gösteren ${ displaystyle mathbb {T} = mathbb {R} / mathbb {Z}}$ reals modulo one üzerinde katkı grubu. İzin Vermek ${ displaystyle mathbf {s} in mathbb {Z} _ {q} ^ {n}}$ sabit bir vektör olalım. ${ displaystyle phi}$ sabit bir olasılık dağılımı olmak ${ displaystyle mathbb {T}}$ .Denote by ${ displaystyle A _ { mathbf {s}, phi}}$ dağıtım ${ displaystyle mathbb {Z} _ {q} ^ {n} times mathbb {T}}$ aşağıdaki gibi elde edilir.

Bir vektör seçin ${ displaystyle mathbf {a} in mathbb {Z} _ {q} ^ {n}}$ üniforma dağılımından ${ displaystyle mathbf {a} in mathbb {Z} _ {q} ^ {n}}$ ,
Bir numara seçin ${ displaystyle e in mathbb {T}}$ dağıtımdan ${ displaystyle phi}$ ,
Değerlendirmek ${ displaystyle t = langle mathbf {a}, mathbf {s} rangle / q + e}$ , nerede ${ displaystyle textstyle langle mathbf {a}, mathbf {s} rangle = sum _ {i = 1} ^ {n} a_ {i} s_ {i}}$ standart iç çarpım ${ displaystyle mathbb {Z} _ {q} ^ {n}}$ bölüm, gerçekler alanı (veya daha resmi olarak, bu "bölüm ${ displaystyle q}$ "grup homomorfizmi için gösterimdir ${ displaystyle mathbb {Z} _ {q} longrightarrow mathbb {T}}$ haritalama ${ displaystyle 1 in mathbb {Z} _ {q}}$ -e ${ displaystyle 1 / q + mathbb {Z} in mathbb {T}}$ ) ve son ekleme ${ displaystyle mathbb {T}}$ .
Çifti çıkar ${ displaystyle ( mathbf {a}, t)}$ .

hatalarla öğrenme problemi ${ displaystyle mathrm {LWE} _ {q, phi}}$ bulmak ${ displaystyle mathbf {s} in mathbb {Z} _ {q} ^ {n}}$ , polinomik olarak seçilen birçok örneğe erişim verildi ${ displaystyle A _ { mathbf {s}, phi}}$ .

Her biri için ${ displaystyle alpha> 0}$ ile belirtmek ${ displaystyle D _ { alpha}}$ tek boyutlu Gauss sıfır ortalama ve varyans ile ${ displaystyle alpha ^ {2} / (2 pi)}$ yani yoğunluk işlevi ${ displaystyle D _ { alpha} (x) = rho _ { alpha} (x) / alpha}$ nerede ${ displaystyle rho _ { alpha} (x) = e ^ {- pi (| x | / alpha) ^ {2}}}$ ve izin ver ${ displaystyle Psi _ { alpha}}$ dağıtımda olmak ${ displaystyle mathbb {T}}$ dikkate alınarak elde edildi ${ displaystyle D _ { alpha}}$ modulo bir. Sonuçların çoğunda dikkate alınan LWE sürümü, ${ displaystyle mathrm {LWE} _ {q, Psi _ { alpha}}}$

Karar versiyonu

LWE yukarıda açıklanan sorun şudur: arama sorunun versiyonu. İçinde karar versiyon (DLWE), amaç gürültülü iç ürünler ile homojen rastgele numuneler arasında ayrım yapmaktır. ${ displaystyle mathbb {Z} _ {q} ^ {n} times mathbb {T}}$ (pratik olarak, bazı ayrıklaştırılmış versiyonu). Regev^[2] gösterdi ki karar ve arama sürümler ne zaman eşdeğerdir ${ displaystyle q}$ bazı polinomlarla sınırlanmış bir asaldır ${ displaystyle n}$ .

Aramayı varsayarak kararı çözme

Sezgisel olarak, arama problemi için bir prosedürümüz varsa, karar versiyonu kolayca çözülebilir: sadece, karar problemi için girdi örneklerini arama problemi için çözücüye besleyin. Verilen örnekleri şu şekilde belirtin: ${ displaystyle {( mathbf {a} _ {i}, mathbf {b} _ {i}) } subset mathbb {Z} _ {q} ^ {n} times mathbb {T} }$ . Çözücü bir aday döndürürse ${ displaystyle mathbf {s}}$ , hepsi için ${ displaystyle i}$ , hesaplamak ${ displaystyle { langle mathbf {a} _ {i}, mathbf {s} rangle - mathbf {b} _ {i} }}$ . Örnekler bir LWE dağılımından geliyorsa, bu hesaplamanın sonuçları göre dağıtılacaktır. ${ displaystyle chi}$ , ancak numuneler tekdüze rasgele ise, bu miktarlar da aynı şekilde dağıtılacaktır.

Kararı varsayarak aramayı çözme

Diğer yön için, karar problemi için bir çözücü verildiğinde, arama versiyonu şu şekilde çözülebilir: Kurtar ${ displaystyle mathbf {s}}$ her seferinde bir koordinat. İlk koordinatı elde etmek için, ${ displaystyle mathbf {s} _ {1}}$ , tahmin et ${ displaystyle k , Z_ {q}}$ ve aşağıdakileri yapın. Bir numara seçin ${ displaystyle r in mathbb {Z} _ {q}}$ tekdüze olarak rastgele. Verilen örnekleri dönüştürün ${ displaystyle {( mathbf {a} _ {i}, mathbf {b} _ {i}) } subset mathbb {Z} _ {q} ^ {n} times mathbb {T} }$ aşağıdaki gibi. Hesaplamak ${ displaystyle {( mathbf {a} _ {i} + (r, 0, ldots, 0), mathbf {b} _ {i} + (rk) / q) }}$ . Dönüştürülen örnekleri karar çözücüye gönderin.

Eğer tahmin ${ displaystyle k}$ doğruydu, dönüşüm dağıtımı alıyor ${ displaystyle A _ { mathbf {s}, chi}}$ kendisi için ve aksi halde ${ displaystyle q}$ asal, onu tekdüze dağılıma götürür. Öyleyse, çok küçük olasılıkla hatalı olan karar problemi için bir polinom zamanlı çözücü verildiğinde, çünkü ${ displaystyle q}$ bazı polinomlarla sınırlıdır ${ displaystyle n}$ için olası her değeri tahmin etmek yalnızca polinom zaman alır ${ displaystyle k}$ ve hangisinin doğru olduğunu görmek için çözücüyü kullanın.

Elde ettikten sonra ${ displaystyle mathbf {s} _ {1}}$ , birbirimizin koordinatları için benzer bir prosedür izliyoruz ${ displaystyle mathbf {s} _ {j}}$ . Yani, biz dönüştürüyoruz ${ displaystyle mathbf {b} _ {i}}$ aynı şekilde örnekler ve ${ displaystyle mathbf {a} _ {i}}$ hesaplayarak örnekler ${ displaystyle mathbf {a} _ {i} + (0, ldots, r, ldots, 0)}$ , nerede ${ displaystyle r}$ içinde ${ displaystyle j ^ { text {th}}}$ koordinat.^[2]

Peikert^[3] küçük bir değişiklikle bu indirgemenin herhangi bir ${ displaystyle q}$ bu, farklı, küçük (polinom ${ displaystyle n}$ ) asal. Ana fikir, eğer ${ displaystyle q = q_ {1} q_ {2} cdots q_ {t}}$ , her biri için ${ displaystyle q _ { ell}}$ , tahmin edin ve kontrol edin ${ displaystyle mathbf {s} _ {j}}$ uyumlu ${ displaystyle 0 mod q _ { ell}}$ ve sonra kullanın Çin kalıntı teoremi iyileşmek ${ displaystyle mathbf {s} _ {j}}$ .

Ortalama kasa sertliği

Regev^[2] gösterdi rastgele kendi kendine indirgenebilirlik of LWE ve DLWE keyfi sorunlar ${ displaystyle q}$ ve ${ displaystyle chi}$ . Verilen örnekler ${ displaystyle {( mathbf {a} _ {i}, mathbf {b} _ {i}) }}$ itibaren ${ displaystyle A _ { mathbf {s}, chi}}$ bunu görmek kolay ${ displaystyle {( mathbf {a} _ {i}, mathbf {b} _ {i} + langle mathbf {a} _ {i}, mathbf {t} rangle) / q } }$ örnekler ${ displaystyle A _ { mathbf {s} + mathbf {t}, chi}}$ .

Diyelim ki bir takım ${ displaystyle { mathcal {S}} subset mathbb {Z} _ {q} ^ {n}}$ öyle ki ${ displaystyle | { mathcal {S}} | / | mathbb {Z} _ {q} ^ {n} | = 1 / operatorname {poli} (n)}$ ve dağıtımlar için ${ displaystyle A _ { mathbf {s} ', chi}}$ , ile ${ displaystyle mathbf {s} ' leftarrow { mathcal {S}}}$ , DLWE kolaydı.

O zaman bir ayırt edici olur ${ displaystyle { mathcal {A}}}$ , kim, örnekler verildi ${ displaystyle {( mathbf {a} _ {i}, mathbf {b} _ {i}) }}$ , bunların tekdüze rastgele mi yoksa ${ displaystyle A _ { mathbf {s} ', chi}}$ . Tekdüze rastgele örnekleri ayırt etmemiz gerekirse ${ displaystyle A _ { mathbf {s}, chi}}$ , nerede ${ displaystyle mathbf {s}}$ tek tip olarak rastgele seçilir ${ displaystyle mathbb {Z} _ {q} ^ {n}}$ farklı değerleri deneyebilirdik ${ displaystyle mathbf {t}}$ rastgele olarak tekdüze örneklenmiş ${ displaystyle mathbb {Z} _ {q} ^ {n}}$ , hesaplamak ${ displaystyle {( mathbf {a} _ {i}, mathbf {b} _ {i} + langle mathbf {a} _ {i}, mathbf {t} rangle) / q } }$ ve bu örnekleri besle ${ displaystyle { mathcal {A}}}$ . Dan beri ${ displaystyle { mathcal {S}}}$ büyük bir bölümünü içerir ${ displaystyle mathbb {Z} _ {q} ^ {n}}$ yüksek olasılıkla, polinomlu bir değer sayısı seçersek ${ displaystyle mathbf {t}}$ öyle bir tane bulacağız ${ mathcal {S}}} içinde { displaystyle mathbf {s} + mathbf {t}$ , ve ${ displaystyle { mathcal {A}}}$ örnekleri başarıyla ayırt edecek.

Bu yüzden böyle değil ${ displaystyle { mathcal {S}}}$ var olabilir, anlamı LWE ve DLWE (bir polinom faktörüne kadar) ortalama durumda en kötü durumda olduğu kadar zordur.

Sertlik sonuçları

Regev'in sonucu

Bir nboyutlu kafes ${ displaystyle L}$ , İzin Vermek yumuşatma parametresi ${ displaystyle eta _ { varepsilon} (L)}$ en küçüğü belirtmek ${ displaystyle s}$ öyle ki ${ displaystyle rho _ {1 / s} (L ^ {*} setminus { mathbf {0} }) leq varepsilon}$ nerede ${ displaystyle L ^ {*}}$ ikilisi ${ displaystyle L}$ ve ${ displaystyle rho _ { alpha} (x) = e ^ {- pi (| x | / alpha) ^ {2}}}$ kümedeki her öğedeki işlev değerlerinin toplanmasıyla kümelere genişletilir. İzin Vermek ${ displaystyle D_ {L, r}}$ ayrık Gauss dağılımını gösterir ${ displaystyle L}$ genişlik ${ displaystyle r}$ kafes için ${ displaystyle L}$ ve gerçek ${ displaystyle r> 0}$ . Her birinin olasılığı ${ displaystyle x L olarak}$ Orantılıdır ${ displaystyle rho _ {r} (x)}$ .

ayrık Gauss örnekleme problemi(DGS) aşağıdaki gibi tanımlanır: ${ displaystyle DGS _ { phi}}$ tarafından verilir ${ displaystyle n}$ boyutlu kafes ${ displaystyle L}$ ve bir sayı ${ displaystyle r geq phi (L)}$ . Amaç, bir örnek çıktısını almaktır. ${ displaystyle D_ {L, r}}$ . Regev, bir azalma olduğunu gösteriyor ${ displaystyle operatorname {GapSVP} _ {100 { sqrt {n}} gamma (n)}}$ -e ${ displaystyle DGS _ {{ sqrt {n}} gamma (n) / lambda (L ^ {*})}}$ herhangi bir işlev için ${ displaystyle gama (n)}$ .

Regev daha sonra etkili bir kuantum algoritması olduğunu gösterir. ${ displaystyle DGS _ {{ sqrt {2n}} eta _ { varepsilon} (L) / alpha}}$ için bir kahine erişim verildi ${ displaystyle mathrm {LWE} _ {q, Psi _ { alpha}}}$ tamsayı için ${ displaystyle q}$ ve ${ displaystyle alpha (0,1)}$ öyle ki ${ displaystyle alpha q> 2 { sqrt {n}}}$ . Bu, LWE için sertliği ifade eder. Bu iddianın kanıtı herhangi biri için işe yarasa da ${ displaystyle q}$ , bir şifreleme sistemi oluşturmak için, ${ displaystyle q}$ polinom olmak zorunda ${ displaystyle n}$ .

Peikert'in sonucu

Peikert kanıtlıyor^[3] olasılıksal bir polinom zaman azalması olduğunu ${ displaystyle operatorname {GapSVP} _ { zeta, gamma}}$ en kötü durumda çözmek için sorun ${ displaystyle mathrm {LWE} _ {q, Psi _ { alpha}}}$ kullanma ${ displaystyle operatöradı {poli} (n)}$ parametreler için örnekler ${ displaystyle alpha (0,1)}$ , ${ displaystyle gamma (n) geq n / ( alpha { sqrt { log n}})}$ , ${ displaystyle zeta (n) geq gamma (n)}$ ve ${ displaystyle q geq ( zeta / { sqrt {n}}) omega { sqrt { log n}})}$ .

Kriptografide kullanın

LWE problem, birkaç yapının yapımında kullanılan çok yönlü bir problemdir.^[2]^[3]^[5]^[6] şifreleme sistemleri. 2005 yılında, Regev^[2] LWE'nin karar versiyonunun, kafes sorunları ${ displaystyle mathrm {GapSVP} _ { gamma}}$ (için ${ displaystyle gamma}$ yukarıdaki gibi) ve ${ displaystyle mathrm {SIVP} _ {t}}$ ile ${ displaystyle t = O (n / alpha)}$ ). 2009 yılında, Peikert^[3] ilgili problemin sadece klasik sertliğini varsayarak benzer bir sonucu kanıtladı ${ displaystyle mathrm {GapSVP} _ { zeta, gamma}}$ . Peikert'in sonucunun dezavantajı, kendisini daha kolay (SIVP ile karşılaştırıldığında) GapSVP'nin standart olmayan bir versiyonuna dayandırmasıdır.

Açık anahtarlı şifreleme sistemi

Regev^[2] önerdi açık anahtarlı şifreleme sistemi sertliğine göre LWE sorun. Şifreleme sisteminin yanı sıra güvenlik ve doğruluğun kanıtı tamamen klasiktir. Sistem şu özelliklere sahiptir: ${ displaystyle m, q}$ ve bir olasılık dağılımı ${ displaystyle chi}$ açık ${ displaystyle mathbb {T}}$ . Doğruluk ve güvenlik kanıtlarında kullanılan parametrelerin ayarı

${ displaystyle q geq 2}$ genellikle arasında bir asal sayı ${ displaystyle n ^ {2}}$ ve ${ displaystyle 2n ^ {2}}$ .
${ displaystyle m = (1+ varepsilon) (n + 1) log q}$ keyfi bir sabit için ${ displaystyle varepsilon}$
${ displaystyle chi = Psi _ { alpha (n)}}$ için ${ displaystyle alpha (n) in o (1 / { sqrt {n}} log n)}$ , nerede ${ displaystyle Psi _ { beta}}$ ortalama ile normal bir değişkeni örnekleyerek elde edilen bir olasılık dağılımıdır ${ displaystyle 0}$ ve standart varyasyon ${ displaystyle { frac { beta} { sqrt {2 pi}}}}$ ve sonuç modülünün azaltılması ${ displaystyle 1}$ .

Şifreleme sistemi daha sonra şu şekilde tanımlanır:

Özel anahtar: Özel anahtar bir ${ displaystyle mathbf {s} in mathbb {Z} _ {q} ^ {n}}$ rastgele olarak tek tip olarak seçilir.
Genel anahtar: Seç ${ displaystyle m}$ vektörler ${ displaystyle mathbf {a} _ {1}, ldots, mathbf {a} _ {m} in mathbb {Z} _ {q} ^ {n}}$ tekdüze ve bağımsız olarak. Hata ofsetlerini seçin ${ displaystyle e_ {1}, ldots, e_ {m} in mathbb {T}}$ göre bağımsız olarak ${ displaystyle chi}$ . Genel anahtar şunlardan oluşur: ${ displaystyle ( mathbf {a} _ {i}, b_ {i} = langle mathbf {a} _ {i}, mathbf {s} rangle / q + e_ {i}) _ {i = 1} ^ {m}}$
Şifreleme: Biraz şifreleme ${ displaystyle x in {0,1 }}$ rastgele bir alt küme seçerek yapılır ${ displaystyle S}$ nın-nin ${ displaystyle [m]}$ ve sonra tanımlama ${ displaystyle operatorname {Enc} (x)}$ gibi

{ displaystyle left ( sum _ {i in S} mathbf {a} _ {i}, { frac {x} {2}} + sum _ {i in S} b_ {i} sağ)}

Şifre çözme: Şifresinin çözülmesi ${ displaystyle ( mathbf {a}, b)}$ dır-dir ${ displaystyle 0}$ Eğer ${ displaystyle b- langle mathbf {a}, mathbf {s} rangle / q}$ daha yakın ${ displaystyle 0}$ daha ${ displaystyle { frac {1} {2}}}$ , ve ${ displaystyle 1}$ aksi takdirde.

Doğruluğun kanıtı, parametrelerin seçiminden ve bazı olasılık analizlerinden kaynaklanır. Güvenlik kanıtı, karar sürümüne indirgemektir. LWE: şifrelemeleri (yukarıdaki parametrelerle) ayırt etmek için bir algoritma ${ displaystyle 0}$ ve ${ displaystyle 1}$ ayırt etmek için kullanılabilir ${ displaystyle A_ {s, chi}}$ ve üzerindeki tekdüze dağılım ${ displaystyle mathbb {Z} _ {q} ^ {n} times mathbb {T}}$

CCA güvenli şifreleme sistemi

Peikert^[3] herhangi birine karşı bile güvenli olan bir sistem önerdi. seçilmiş şifreli metin saldırısı.

Anahtar değişimi

Anahtar değişimi için LWE ve Ring LWE'yi kullanma fikri, Jintai Ding tarafından 2011 yılında Cincinnati Üniversitesi'nde önerildi ve dosyalandı. Fikir, matris çarpımlarının ilişkilendirilmesinden gelir ve hatalar güvenliği sağlamak için kullanılır. Kağıt^[7] 2012'de geçici patent başvurusu yapıldıktan sonra 2012'de ortaya çıktı.

Protokolün güvenliği, LWE problemini çözmenin zorluğuna göre kanıtlanmıştır. Peikert 2014 yılında bir anahtar taşıma planı sundu^[8] Ding'in yapısında yuvarlama için ek bir 1 bitlik sinyal gönderme fikrinin de kullanıldığı Ding'in aynı temel fikrinin ardından. "Yeni umut" uygulaması^[9] Google'ın kuantum sonrası deneyi için seçildi,^[10] Peikert'in hata dağılımındaki varyasyonlu şemasını kullanır.

Ayrıca bakınız

Referanslar

^ Regev, Oded (2009). "Kafesler üzerinde, hatalarla öğrenme, rastgele doğrusal kodlar ve kriptografi". ACM Dergisi. 56 (6): 1–40. doi:10.1145/1568318.1568324.
^ ^a ^b ^c ^d ^e ^f ^g ^h Oded Regev, Otuz yedinci yıllık ACM sempozyumunun Hesaplama Teorisi Bildirilerinde (Baltimore, MD, ABD: ACM, 2005), 84–93, "Kafesler, hatalarla öğrenme, rastgele doğrusal kodlar ve kriptografi", http://portal.acm.org/citation.cfm?id=1060590.1060603.
^ ^a ^b ^c ^d ^e ^f Chris Peikert, "En kötü durum en kısa vektör probleminden açık anahtarlı şifreleme sistemleri: genişletilmiş özet," Hesaplama Teorisi üzerine 41. yıllık ACM sempozyumunun Bildirileri kitabında (Bethesda, MD, ABD: ACM, 2009), 333-342, http://portal.acm.org/citation.cfm?id=1536414.1536461.
^ Peikert, Chris (2014-10-01). "İnternet için Kafes Kriptografisi". Mosca'da Michele (ed.). Kuantum Sonrası Kriptografi. Bilgisayar Bilimlerinde Ders Notları. 8772. Springer Uluslararası Yayıncılık. s. 197–219. CiteSeerX 10.1.1.800.4743. doi:10.1007/978-3-319-11659-4_12. ISBN 978-3-319-11658-7.
^ Chris Peikert ve Brent Waters, "Kayıplı tuzak kapı fonksiyonları ve uygulamaları", 40. yıllık ACM sempozyumunun Hesaplama Teorisi Bildirilerinde (Victoria, British Columbia, Kanada: ACM, 2008), 187-196, http://portal.acm.org/citation.cfm?id=1374406.
^ Craig Gentry, Chris Peikert ve Vinod Vaikuntanathan, "Sert kafesler ve yeni kriptografik yapılar için tuzak kapıları", Hesaplama Teorisi üzerine 40. yıllık ACM sempozyumunun Bildirilerinde (Victoria, British Columbia, Kanada: ACM, 2008), 197-206, http://portal.acm.org/citation.cfm?id=1374407.
^ Lin, Jintai Ding, Xiang Xie, Xiaodong (2012-01-01). "Hatalı Öğrenme Problemine Dayalı Basit, Sağlanabilir Güvenli Anahtar Değişim Programı". Alıntı dergisi gerektirir | günlük = (Yardım)
^ Peikert, Chris (2014/01/01). "İnternet için Kafes Kriptografisi". Alıntı dergisi gerektirir | günlük = (Yardım)
^ Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (2015/01/01). "Kuantum sonrası anahtar değişimi - yeni bir umut". Alıntı dergisi gerektirir | günlük = (Yardım)
^ "Post Kuantum Kriptografi ile Deney Yapmak". Google Çevrimiçi Güvenlik Blogu. Alındı 2017-02-08.

[1] Regev, Oded (2009). "Kafesler üzerinde, hatalarla öğrenme, rastgele doğrusal kodlar ve kriptografi". ACM Dergisi. 56 (6): 1–40. doi:10.1145/1568318.1568324.

[regev05-2] ^ ^a ^b ^c ^d ^e ^f ^g ^h Oded Regev, Otuz yedinci yıllık ACM sempozyumunun Hesaplama Teorisi Bildirilerinde (Baltimore, MD, ABD: ACM, 2005), 84–93, "Kafesler, hatalarla öğrenme, rastgele doğrusal kodlar ve kriptografi", http://portal.acm.org/citation.cfm?id=1060590.1060603.

[peikert09-3] ^ ^a ^b ^c ^d ^e ^f Chris Peikert, "En kötü durum en kısa vektör probleminden açık anahtarlı şifreleme sistemleri: genişletilmiş özet," Hesaplama Teorisi üzerine 41. yıllık ACM sempozyumunun Bildirileri kitabında (Bethesda, MD, ABD: ACM, 2009), 333-342, http://portal.acm.org/citation.cfm?id=1536414.1536461.

[4] Peikert, Chris (2014-10-01). "İnternet için Kafes Kriptografisi". Mosca'da Michele (ed.). Kuantum Sonrası Kriptografi. Bilgisayar Bilimlerinde Ders Notları. 8772. Springer Uluslararası Yayıncılık. s. 197–219. CiteSeerX 10.1.1.800.4743. doi:10.1007/978-3-319-11659-4_12. ISBN 978-3-319-11658-7.

[5] Chris Peikert ve Brent Waters, "Kayıplı tuzak kapı fonksiyonları ve uygulamaları", 40. yıllık ACM sempozyumunun Hesaplama Teorisi Bildirilerinde (Victoria, British Columbia, Kanada: ACM, 2008), 187-196, http://portal.acm.org/citation.cfm?id=1374406.

[6] Craig Gentry, Chris Peikert ve Vinod Vaikuntanathan, "Sert kafesler ve yeni kriptografik yapılar için tuzak kapıları", Hesaplama Teorisi üzerine 40. yıllık ACM sempozyumunun Bildirilerinde (Victoria, British Columbia, Kanada: ACM, 2008), 197-206, http://portal.acm.org/citation.cfm?id=1374407.

[7] Lin, Jintai Ding, Xiang Xie, Xiaodong (2012-01-01). "Hatalı Öğrenme Problemine Dayalı Basit, Sağlanabilir Güvenli Anahtar Değişim Programı". Alıntı dergisi gerektirir | günlük = (Yardım)

[8] Peikert, Chris (2014/01/01). "İnternet için Kafes Kriptografisi". Alıntı dergisi gerektirir | günlük = (Yardım)

[9] Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (2015/01/01). "Kuantum sonrası anahtar değişimi - yeni bir umut". Alıntı dergisi gerektirir | günlük = (Yardım)

[10] "Post Kuantum Kriptografi ile Deney Yapmak". Google Çevrimiçi Güvenlik Blogu. Alındı 2017-02-08.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Hesaplamalı sertlik varsayımları
Sayı teorik	Tamsayı çarpanlara ayırma Phi gizleme RSA sorunu Güçlü RSA İkinci dereceden kalıntı Kararlı bileşik kalıntı Daha yüksek kalıntı
Grup teorik	Ayrık logaritma Diffie-Hellman Decisional Diffie – Hellman Hesaplamalı Diffie – Hellman
Eşleştirmeler	Harici Diffie – Hellman Alt grup gizleme Doğrusal karar
Kafesler	En kısa vektör problemi (boşluk ) En yakın vektör problemi (boşluk ) Hatalarla öğrenmek Hatalarla öğrenme halkası Kısa tamsayı çözümü
Kriptografik olmayan	Üstel zaman hipotezi Benzersiz oyun varsayımı Dikilmiş klik varsayımı