Kafes tabanlı şifreleme - Lattice-based cryptography

Kafes tabanlı kriptografi , yapının kendisinde veya güvenlik kanıtında kafesleri içeren kriptografik ilkel yapıların genel terimidir . Kafes tabanlı yapılar şu anda kuantum sonrası kriptografi için önemli adaylardır . Teorik olarak bir kuantum bilgisayar tarafından kolayca saldırıya uğrayabilen RSA , Diffie-Hellman veya eliptik eğri şifreleme sistemleri gibi daha yaygın olarak kullanılan ve bilinen genel anahtar şemalarının aksine , bazı kafes tabanlı yapılar her ikisinin de saldırılarına karşı dirençli görünmektedir. klasik ve kuantum bilgisayarlar. Ayrıca, iyi çalışılmış belirli hesaplama kafes problemlerinin verimli bir şekilde çözülemeyeceği varsayımı altında birçok kafes tabanlı yapının güvenli olduğu düşünülmektedir .

Tarih

1996 yılında Miklós Ajtai , güvenliği iyi çalışılmış kafes problemlerinin sertliğine dayalı olabilen ilk kafes tabanlı kriptografik yapıyı tanıttı ve Cynthia Dwork , Kısa Tamsayı Çözümleri (SIS) olarak bilinen belirli bir ortalama durum kafes probleminin olduğunu gösterdi. Çözmesi en azından en kötü durumdaki kafes problemi kadar zordur . Ardından , güvenliği SIS'in hesaplama sertliğine eşdeğer olan bir şifreleme karma işlevi gösterdi .

1998'de Jeffrey Hoffstein , Jill Pipher ve Joseph H. Silverman , NTRU olarak bilinen kafes tabanlı bir açık anahtar şifreleme şemasını tanıttı . Bununla birlikte, planlarının en azından en kötü durumdaki kafes problemini çözmek kadar zor olduğu bilinmemektedir.

En kötü durum sertliği varsayımları altında güvenliği kanıtlanmış ilk kafes tabanlı açık anahtar şifreleme şeması, 2005 yılında Oded Regev tarafından Hatalarla Öğrenme problemi (LWE) ile birlikte tanıtıldı . O zamandan beri, birçok takip çalışması Regev'in güvenlik kanıtını iyileştirmeye ve orijinal planın verimliliğini artırmaya odaklandı. LWE ve ilgili sorunlara dayalı ek kriptografik ilkellerin oluşturulması için çok daha fazla çalışma yapılmıştır. Örneğin, 2009'da Craig Gentry , bir kafes problemine dayanan ilk tamamen homomorfik şifreleme şemasını tanıttı .

Matematiksel arka plan

Bir kafes taban vektörlerinin kombinasyonları doğrusal tüm tamsayı kümesidir . Yani, örneğin, standart ortonormal temel tarafından oluşturulan bir kafestir . En önemlisi, bir kafesin temeli benzersiz değildir. Örneğin, vektörler , ve için alternatif bir temel oluşturur . ${\ displaystyle L \ altküme \ mathbb {R} ^ {n}}$ ${\ displaystyle \ mathbf {b} _ {1}, \ ldots, \ mathbf {b} _ {n} \ in \ mathbb {R} ^ {n}}$ ${\ displaystyle L = {\ Büyük \ {} \ toplam a_ {i} \ mathbf {b} _ {i} \: \ a_ {i} \ in \ mathbb {Z} {\ Büyük \}} \ ;.}$ ${\ displaystyle \ mathbb {Z} ^ {n}}$ ${\ displaystyle \ mathbb {R} ^ {n}}$ ${\ displaystyle (3; 1; 4)}$ ${\ displaystyle (1,5,9)}$ ${\ displaystyle (2, -1,0)}$ ${\ displaystyle \ mathbb {Z} ^ {3}}$

En önemli kafes tabanlı hesaplama problemi, sıfır olmayan bir kafes vektörünün minimum Öklid uzunluğunu yaklaşık olarak tahmin etmemizi isteyen En Kısa Vektör Problemidir (SVP veya bazen GapSVP). Bu problemin, polinom içindeki yaklaşık faktörlerle ve hatta bir kuantum bilgisayarla bile verimli bir şekilde çözülmesinin zor olduğu düşünülmektedir . Bu rejimde SVP gerçekten zorsa, kafes tabanlı kriptografik yapıların birçoğunun (hepsi olmasa da) güvenli olduğu bilinmektedir. ${\ displaystyle n}$

Seçilmiş kafes tabanlı şifreleme sistemleri

Şifreleme şemaları

İmzalar

Güneysu, Lyubashevsky ve Poppleman'ın Yüzüğü - Hatalarla Öğrenme (Ring-LWE) İmza
GGH imza şeması
NTRUSign

Hash fonksiyonları

SWIFFT
LASH (Kafes Tabanlı Hash Fonksiyonu)

Tamamen homomorfik şifreleme

Gentry'nin orijinal planı.
Brakerski ve Vaikuntanathan.

Güvenlik

Kafes tabanlı kriptografik yapılar, açık anahtar sonrası kuantum şifreleme için önde gelen adaylardır . Gerçekten de, kamu anahtar şifreleme ana alternatif formları sertliğine göre şema vardır faktoringe ve ilgili problemlerin sertliğine göre ve şemalarda ayrık logaritma ve ilgili sorunlar . Bununla birlikte, hem çarpanlara ayırma hem de ayrık logaritmanın bir kuantum bilgisayarda polinom zamanında çözülebilir olduğu bilinmektedir . Ayrıca, çarpanlara ayırma algoritmaları, ayrık logaritma için algoritmalar üretme eğilimindedir ve bunun tersi de geçerlidir. Bu, kafes problemlerinin sertliği gibi alternatif varsayımlara dayalı yapıların incelenmesini daha da motive eder.

Birçok kafes tabanlı şifreleme şemasının, belirli kafes problemlerinin en kötü durum sertliğini varsayarak güvenli olduğu bilinmektedir . Yani, kriptografik şemayı ihmal edilemez bir olasılıkla verimli bir şekilde kırabilen bir algoritma varsa, o zaman herhangi bir girişte belirli bir kafes problemini çözen verimli bir algoritma vardır. Bunun aksine, örneğin faktoringe dayalı kriptografik şemalar, faktoring kolay olsaydı, " ortalama bir girdiye göre", faktoring aslında en kötü durumda zor olsa bile bozulurdu.Ancak, daha verimli ve pratik kafes tabanlı yapılar için (NTRU'ya dayalı şemalar ve hatta daha agresif parametrelere sahip LWE'ye dayalı şemalar gibi), bu tür en kötü durumdaki sertlik sonuçları bilinmemektedir.Bazı şemalar için, en kötü durumdaki sertlik sonuçları yalnızca belirli yapılandırılmış kafesler için bilinir veya hiç bilinmez .

İşlevsellik

Birçok kriptografik ilkel için, bilinen tek yapılar kafeslere veya yakından ilişkili nesnelere dayanır. Bu ilkel öğeler arasında tamamen homomorfik şifreleme , ayırt edilemezlik gizlemesi , kriptografik çok çizgili haritalar ve işlevsel şifreleme bulunur .

Ayrıca bakınız

Referanslar

^ ^a ^b Ajtai, Miklós (1996). "Kafes Sorunlarının Sabit Örneklerini Oluşturma". Hesaplama Teorisi üzerine Yirmi Sekizinci Yıllık ACM Sempozyumu Bildirileri . s. 99–108. CiteSeerX 10.1.1.40.2489 . doi : 10.1145 / 237814.237838 . ISBN 978-0-89791-785-8 . S2CID 6864824 .
^ En Kötü Durum / Ortalama Durum Eşitliğine Sahip Açık Anahtarlı Şifreleme Sistemi
^ Hoffstein, Jeffrey; Pipher, Jill; Silverman, Joseph H. (1998). "NTRU: Halka tabanlı bir genel anahtar şifreleme sistemi". Algoritmik Sayı Teorisi . Bilgisayar Bilimleri Ders Notları. 1423 . s. 267–288. CiteSeerX 10.1.1.25.8422 . doi : 10.1007 / bfb0054868 . ISBN 978-3-540-64657-0 .
^ ^a ^b Regev, Oded (01.01.2005). "Kafesler üzerinde, hatalarla öğrenme, rastgele doğrusal kodlar ve kriptografi". Hesaplama Teorisi üzerine otuz yedinci yıllık ACM sempozyumunun bildirileri - STOC '05 . ACM. sayfa 84–93. CiteSeerX 10.1.1.110.4776 . doi : 10.1145 / 1060590.1060603 . ISBN 978-1581139600 . S2CID 53223958 .
^ ^a ^b Peikert, Chris (01.01.2009). "En kötü durumdaki en kısa vektör probleminden açık anahtarlı şifreleme sistemleri". Hesaplama Teorisi Sempozyumu üzerine 41. ACM sempozyumunun bildirileri - STOC '09 . ACM. s. 333–342. CiteSeerX 10.1.1.168.270 . doi : 10.1145 / 1536414.1536461 . ISBN 9781605585062 . S2CID 1864880 .
^ Brakerski, Zvika; Langlois, Adeline; Peikert, Chris; Regev, Oded; Stehlé, Damien (2013-01-01). "Hatalarla öğrenmenin klasik zorluğu". Hesaplama Teorisi Sempozyumu üzerine 45. yıllık ACM sempozyumunun bildirileri - STOC '13 . ACM. s. 575–584. arXiv : 1306.0281 . doi : 10.1145 / 2488608.2488680 . ISBN 9781450320290 . S2CID 6005009 .
^ ^a ^b Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010-05-30). İdeal Kafesler ve Halkalar Üzerinden Hatalı Öğrenme Üzerine . Kriptolojideki Gelişmeler - EUROCRYPT 2010 . Bilgisayar Bilimleri Ders Notları. 6110 . s. 1–23. CiteSeerX 10.1.1.352.8218 . doi : 10.1007 / 978-3-642-13190-5_1 . ISBN 978-3-642-13189-9 .
^ ^a ^b Peikert, Chris (2014-07-16). "İnternet için Kafes Kriptografisi" (PDF) . IACR . Erişim tarihi: 2017-01-11 .
^ Alkım, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (2015/01/01). "Post kuantum anahtar değişimi - yeni bir umut" . Alıntı dergisi gerektirir |journal= ( yardım )
^ Bos, Joppe; Costello, Craig; Ducas, Léo; Mironov, Ilya; Naehrig, Michael; Nikolaenko, Valeria; Raghunathan, Ananth; Stebila, Douglas (2016/01/01). "Frodo: Yüzüğü çıkarın! LWE'den Pratik, Kuantum Güvenli Anahtar Değişimi" . Alıntı dergisi gerektirir |journal= ( yardım )
^ ^a ^b ^c Gentry, Craig (2009/01/01). Tamamen Homomorfik Şifreleme Şeması (Tez). Stanford, CA, ABD: Stanford Üniversitesi.
^ Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). "Pratik Kafes Tabanlı Şifreleme: Gömülü Sistemler İçin Bir İmza Şeması" (PDF) . Kriptografik Donanım ve Gömülü Sistemler - CHES 2012 . Bilgisayar Bilimleri Ders Notları. 7428 . IACR. s. 530–547. doi : 10.1007 / 978-3-642-33027-8_31 . ISBN 978-3-642-33026-1 . Erişim tarihi: 2017-01-11 .
^ "LASH: A Kafes Tabanlı Hash Fonksiyonu" . 16 Ekim 2008 tarihinde orjinalinden arşivlendi . Erişim tarihi: 2008-07-31 . CS1 bakimi: bot: orijinal URL durumu bilinmiyor ( bağlantı ) (kırık)
^ Scott Contini, Krystian Matusiewicz, Josef Pieprzyk, Ron Steinfeld, Jian Guo, San Ling ve Huaxiong Wang (2008). "LASH'ın Kriptanalizi" (PDF) . Hızlı Yazılım Şifreleme . Bilgisayar Bilimleri Ders Notları. 5086 . s. 207–223. doi : 10.1007 / 978-3-540-71039-4_13 . ISBN 978-3-540-71038-7 . CS1 Maint: yazar parametresini ( bağlantı ) kullanır
^ Brakerski, Zvika; Vaikuntanathan Vinod (2011). "(Standart) LWE'den Verimli Tamamen Homomorfik Şifreleme" . Alıntı dergisi gerektirir |journal= ( yardım )
^ Brakerski, Zvika; Vaikuntanathan Vinod (2013). "Kafes Tabanlı FHE, PKE kadar Güvenli" . Alıntı dergisi gerektirir |journal= ( yardım )
^ Micciancio, Daniele; Regev, Oded (2008-07-22). "Kafes tabanlı şifreleme" (PDF) . Erişim tarihi: 2017-01-11 . Alıntı dergisi gerektirir |journal= ( yardım )
^ Shor, Peter W. (1997-10-01). "Bir Kuantum Bilgisayarda Asal Çarpanlara Ayırma ve Ayrık Logaritmalar için Polinom Zaman Algoritmaları". Bilgi İşlem Üzerine SIAM Dergisi . 26 (5): 1484–1509. arXiv : quant-ph / 9508027 . doi : 10.1137 / S0097539795293172 . ISSN 0097-5397 . S2CID 2337707 .
^ ^a ^b Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Sular, Brent (2013/01/01). "Tüm devreler için Aday Ayrılmazlık Gizleme ve İşlevsel Şifreleme" . CiteSeerX 10.1.1.400.6501 . Alıntı dergisi gerektirir |journal= ( yardım )

Kaynakça

Oded Goldreich, Shafi Goldwasser ve Shai Halevi. "Kafes azaltma problemlerinden açık anahtarlı şifreleme sistemleri". In Kriptoloji Gelişmeler 17. Yıllık Uluslararası Kriptoloji Konferansı Tutanakları: Kripto '97 , sayfa 112-131, Londra, Birleşik Krallık, 1997, Springer-Verlag.
Phong Q. Nguyen. "Goldreich-Goldwasser-Halevi şifreleme sisteminin '97 şifresinden şifrelenmesi". In Kriptoloji Gelişmeler 19. Yıllık Uluslararası Kriptoloji Konferansı Tutanakları: Kripto '99 , sayfa 288-304, Londra, Birleşik Krallık, 1999, Springer-Verlag.
Oded Regev. Kafes tabanlı kriptografi. Gelen kriptoloji Gelişmeler (KRİPTO) , sayfalar 131-141, 2006.

[:1-1] Ajtai, Miklós (1996). "Kafes Sorunlarının Sabit Örneklerini Oluşturma". Hesaplama Teorisi üzerine Yirmi Sekizinci Yıllık ACM Sempozyumu Bildirileri . s. 99–108. CiteSeerX 10.1.1.40.2489 . doi : 10.1145 / 237814.237838 . ISBN 978-0-89791-785-8 . S2CID 6864824 .

[2] En Kötü Durum / Ortalama Durum Eşitliğine Sahip Açık Anahtarlı Şifreleme Sistemi

[3] Hoffstein, Jeffrey; Pipher, Jill; Silverman, Joseph H. (1998). "NTRU: Halka tabanlı bir genel anahtar şifreleme sistemi". Algoritmik Sayı Teorisi . Bilgisayar Bilimleri Ders Notları. 1423 . s. 267–288. CiteSeerX 10.1.1.25.8422 . doi : 10.1007 / bfb0054868 . ISBN 978-3-540-64657-0 .

[:2-4] Regev, Oded (01.01.2005). "Kafesler üzerinde, hatalarla öğrenme, rastgele doğrusal kodlar ve kriptografi". Hesaplama Teorisi üzerine otuz yedinci yıllık ACM sempozyumunun bildirileri - STOC '05 . ACM. sayfa 84–93. CiteSeerX 10.1.1.110.4776 . doi : 10.1145 / 1060590.1060603 . ISBN 978-1581139600 . S2CID 53223958 .

[:3-5] Peikert, Chris (01.01.2009). "En kötü durumdaki en kısa vektör probleminden açık anahtarlı şifreleme sistemleri". Hesaplama Teorisi Sempozyumu üzerine 41. ACM sempozyumunun bildirileri - STOC '09 . ACM. s. 333–342. CiteSeerX 10.1.1.168.270 . doi : 10.1145 / 1536414.1536461 . ISBN 9781605585062 . S2CID 1864880 .

[6] Brakerski, Zvika; Langlois, Adeline; Peikert, Chris; Regev, Oded; Stehlé, Damien (2013-01-01). "Hatalarla öğrenmenin klasik zorluğu". Hesaplama Teorisi Sempozyumu üzerine 45. yıllık ACM sempozyumunun bildirileri - STOC '13 . ACM. s. 575–584. arXiv : 1306.0281 . doi : 10.1145 / 2488608.2488680 . ISBN 9781450320290 . S2CID 6005009 .

[:4-7] Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010-05-30). İdeal Kafesler ve Halkalar Üzerinden Hatalı Öğrenme Üzerine . Kriptolojideki Gelişmeler - EUROCRYPT 2010 . Bilgisayar Bilimleri Ders Notları. 6110 . s. 1–23. CiteSeerX 10.1.1.352.8218 . doi : 10.1007 / 978-3-642-13190-5_1 . ISBN 978-3-642-13189-9 .

[:0-8] Peikert, Chris (2014-07-16). "İnternet için Kafes Kriptografisi" (PDF) . IACR . Erişim tarihi: 2017-01-11 .

[9] Alkım, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (2015/01/01). "Post kuantum anahtar değişimi - yeni bir umut" . Alıntı dergisi gerektirir |journal= ( yardım )

[10] Bos, Joppe; Costello, Craig; Ducas, Léo; Mironov, Ilya; Naehrig, Michael; Nikolaenko, Valeria; Raghunathan, Ananth; Stebila, Douglas (2016/01/01). "Frodo: Yüzüğü çıkarın! LWE'den Pratik, Kuantum Güvenli Anahtar Değişimi" . Alıntı dergisi gerektirir |journal= ( yardım )

[:5-11] Gentry, Craig (2009/01/01). Tamamen Homomorfik Şifreleme Şeması (Tez). Stanford, CA, ABD: Stanford Üniversitesi.

[12] Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). "Pratik Kafes Tabanlı Şifreleme: Gömülü Sistemler İçin Bir İmza Şeması" (PDF) . Kriptografik Donanım ve Gömülü Sistemler - CHES 2012 . Bilgisayar Bilimleri Ders Notları. 7428 . IACR. s. 530–547. doi : 10.1007 / 978-3-642-33027-8_31 . ISBN 978-3-642-33026-1 . Erişim tarihi: 2017-01-11 .

[13] "LASH: A Kafes Tabanlı Hash Fonksiyonu" . 16 Ekim 2008 tarihinde orjinalinden arşivlendi . Erişim tarihi: 2008-07-31 . CS1 bakimi: bot: orijinal URL durumu bilinmiyor ( bağlantı ) (kırık)

[14] Scott Contini, Krystian Matusiewicz, Josef Pieprzyk, Ron Steinfeld, Jian Guo, San Ling ve Huaxiong Wang (2008). "LASH'ın Kriptanalizi" (PDF) . Hızlı Yazılım Şifreleme . Bilgisayar Bilimleri Ders Notları. 5086 . s. 207–223. doi : 10.1007 / 978-3-540-71039-4_13 . ISBN 978-3-540-71038-7 . CS1 Maint: yazar parametresini ( bağlantı ) kullanır

[15] Brakerski, Zvika; Vaikuntanathan Vinod (2011). "(Standart) LWE'den Verimli Tamamen Homomorfik Şifreleme" . Alıntı dergisi gerektirir |journal= ( yardım )

[16] Brakerski, Zvika; Vaikuntanathan Vinod (2013). "Kafes Tabanlı FHE, PKE kadar Güvenli" . Alıntı dergisi gerektirir |journal= ( yardım )

[17] Micciancio, Daniele; Regev, Oded (2008-07-22). "Kafes tabanlı şifreleme" (PDF) . Erişim tarihi: 2017-01-11 . Alıntı dergisi gerektirir |journal= ( yardım )

[18] Shor, Peter W. (1997-10-01). "Bir Kuantum Bilgisayarda Asal Çarpanlara Ayırma ve Ayrık Logaritmalar için Polinom Zaman Algoritmaları". Bilgi İşlem Üzerine SIAM Dergisi . 26 (5): 1484–1509. arXiv : quant-ph / 9508027 . doi : 10.1137 / S0097539795293172 . ISSN 0097-5397 . S2CID 2337707 .

[:6-19] Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Sular, Brent (2013/01/01). "Tüm devreler için Aday Ayrılmazlık Gizleme ve İşlevsel Şifreleme" . CiteSeerX 10.1.1.400.6501 . Alıntı dergisi gerektirir |journal= ( yardım )

Languages

In other projects