격자 기반 암호법

Lattice-based cryptography

격자 기반 암호는 구조 자체 또는 보안 증명서 중 어느 하나에 격자를 포함하는 암호 원시 형질의 구성을 총칭하는 말이다.격자 기반 구조는 현재 사후 수량 암호화에 중요한 후보군이다.이론적으로 양자 컴퓨터에 의해 쉽게 공격될 수 있는 RSA, Diffie-Hellman 또는 타원곡선 암호 시스템과 같이 더 널리 사용되고 알려진 공개 키 체계와는 달리, 일부 격자 기반 구조는 고전 컴퓨터와 양자 컴퓨터 모두의 공격에 저항하는 것으로 보인다.더욱이 많은 격자 기반 구조는 잘 연구된 특정 계산 격자 문제를 효율적으로 해결할 수 없다는 가정 하에 안전한 것으로 간주된다.null

역사

1996년 미클로즈 아제이는 잘 연구된 격자 문제의 경도에 기초할 수 있는 보안성을 가진 격자 기반 암호구축법을 최초로 도입했고,[1] 신시아 드워크는 '단수 정수 솔루션(SIS)'으로 알려진 특정 평균 사례 격자 문제는 적어도 최악의 격자 문제만큼 해결하기 어렵다는 것을 보여주었다.[2]이어 SIS의 연산 경도에 해당하는 보안성을 가진 암호해시함수를 선보였다.null

1998년에 제프리 호프스타인, 질 피퍼, 그리고 조셉 H. 실버맨은 NTRU로 알려진 격자 기반의 공개키 암호화 체계를 도입했다.[3]그러나 그들의 계획은 적어도 최악의 격자 문제를 해결하는 것만큼 어려운 것으로 알려져 있지 않다.null

최악의 경도 가정 하에서 보안성이 입증된 최초의 격자 기반 공개키 암호화 체계는 2005년 Oed Regev에 의해 [4]LWE(Learning with Errors) 문제와 함께 도입되었다.이후 많은 후속 작업은 레게프의 보안 증빙을[5][6] 개선하고 원래 계획의 효율성을 높이는 데 초점을 맞췄다.[7][8][9][10]훨씬 더 많은 작업이 LWE 및 관련 문제에 기반한 추가적인 암호화 원시 요소 구축에 투입되었다.예를 들어, 2009년에 크레이그 젠트리는 격자 문제에 기초하여 최초의 완전한 동형 암호화 체계를 도입했다.[11]null

수학적 배경

A lattice is the set of all integer linear combinations of basis vectors . I.e., For example, is a lattice, generated by the standard basis for . Crucially, the basis for a lattice is not unique.예를 들어 벡터 ,) (,,) ,(,- ,0) 은 Z ^{의 대체 기준을 형성한다

가장 중요한 격자 기반 계산 문제는 최단 벡터 문제(SVP 또는 때때로 GapSVP)로, 0이 아닌 격자 벡터의 최소 유클리드 길이를 대략적으로 파악하도록 요구한다. 문제는 n 에서 다항식인 근사계수를 사용해도 효율적으로 해결하기 어렵다고 생각된다.사실 SVP가 이 정권에서 어렵다면 (전부는 아니지만) 격자 기반의 많은 암호구축이 안전한 것으로 알려져 있다.null

선택한 격자 기반 암호 시스템

암호화 구성표

서명

해시함수

완전 동형 암호화

참고 항목:완전 동형 암호화
  • 젠트리 본래의 계획.[11]
  • 브레이커스키와 [15][16]바이쿤타나단

보안

격자 기반 암호구축은 공개키 포스트 퀀텀 암호화의 유력한 후보다.[17]실제로 공개키 암호화의 주요 대체 형태는 인수 경도에 기초한 체계와 관련 문제 및 이산 로그의 경도와 관련 문제에 기초한 체계다.그러나 인수와 이산 로그 모두 양자 컴퓨터에서 다항식 시간으로 해결할 수 있는 것으로 알려져 있다.[18]더욱이 인자화를 위한 알고리즘은 이산 로그에 대한 알고리즘을 산출하는 경향이 있으며, 그 반대의 경우도 마찬가지다.이는 격자 문제의 경도와 같은 대안적 가정에 근거한 건설 연구의 동기를 더욱 자극한다.null

많은 격자 기반 암호 체계는 특정 격자 문제의 최악의 경도를 가정하여 안전한 것으로 알려져 있다.[1][4][5]즉, 불가해한 확률로 암호 체계를 효율적으로 깨트릴 수 있는 알고리즘이 존재한다면, 어떤 입력에서 어떤 격자 문제를 해결하는 효율적인 알고리즘이 존재한다.이와는 대조적으로, 예를 들어, 팩토링이 사실 최악의 경우 팩토링이 어렵더라도 "평균 입력"으로 쉬웠다면, 팩토링에 기반한 암호 체계는 깨질 것이다.그러나 보다 효율적이고 실용적인 격자 기반 구조(NTRU에 기반한 체계 및 보다 공격적인 매개변수를 가진 LWE에 기반한 체계 등)의 경우, 그러한 최악의 경도 결과는 알려져 있지 않다.일부 체계의 경우, 최악의 경우 경도 결과는 특정 구조화된 격자에[7] 대해서만 알려져 있거나 전혀 알려져 있지 않다.null

기능

많은 암호화 원시성의 경우 알려진 유일한 구조는 격자 또는 밀접하게 연관된 객체에 기초한다.이러한 원시적 요소에는 완전한 동형 암호화,[11] 구별할 수 없는 난독화,[19] 암호 다중선 지도, 기능 암호화가 포함된다.[19]null

참고 항목

참조

  1. ^ a b Ajtai, Miklós (1996). "Generating Hard Instances of Lattice Problems". Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. pp. 99–108. CiteSeerX 10.1.1.40.2489. doi:10.1145/237814.237838. ISBN 978-0-89791-785-8. S2CID 6864824.
  2. ^ 최악의 경우/평균 사례 동등성을 갖는 공용 키 암호 시스템
  3. ^ Hoffstein, Jeffrey; Pipher, Jill; Silverman, Joseph H. (1998). "NTRU: A ring-based public key cryptosystem". Algorithmic Number Theory. Lecture Notes in Computer Science. Vol. 1423. pp. 267–288. CiteSeerX 10.1.1.25.8422. doi:10.1007/bfb0054868. ISBN 978-3-540-64657-0.
  4. ^ a b Regev, Oded (2005-01-01). "On lattices, learning with errors, random linear codes, and cryptography". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05. ACM. pp. 84–93. CiteSeerX 10.1.1.110.4776. doi:10.1145/1060590.1060603. ISBN 978-1581139600. S2CID 53223958.
  5. ^ a b Peikert, Chris (2009-01-01). "Public-key cryptosystems from the worst-case shortest vector problem". Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09. ACM. pp. 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). "Classical hardness of learning with errors". Proceedings of the 45th annual ACM symposium on Symposium on theory of computing - STOC '13. ACM. pp. 575–584. arXiv:1306.0281. doi:10.1145/2488608.2488680. ISBN 9781450320290. S2CID 6005009.
  7. ^ a b Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010-05-30). On Ideal Lattices and Learning with Errors over Rings. Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science. Vol. 6110. pp. 1–23. CiteSeerX 10.1.1.352.8218. doi:10.1007/978-3-642-13190-5_1. ISBN 978-3-642-13189-9.
  8. ^ a b Peikert, Chris (2014-07-16). "Lattice Cryptography for the Internet" (PDF). IACR. Retrieved 2017-01-11.
  9. ^ Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (2015-01-01). "Post-quantum key exchange - a new hope". {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  10. ^ Bos, Joppe; Costello, Craig; Ducas, Léo; Mironov, Ilya; Naehrig, Michael; Nikolaenko, Valeria; Raghunathan, Ananth; Stebila, Douglas (2016-01-01). "Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE". {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  11. ^ a b c Gentry, Craig (2009-01-01). A Fully Homomorphic Encryption Scheme (Thesis). Stanford, CA, USA: Stanford University.
  12. ^ Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). "Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems" (PDF). Cryptographic Hardware and Embedded Systems – CHES 2012. Lecture Notes in Computer Science. Vol. 7428. IACR. pp. 530–547. doi:10.1007/978-3-642-33027-8_31. ISBN 978-3-642-33026-1. Retrieved 2017-01-11.
  13. ^ "LASH: A Lattice Based Hash Function". Archived from the original on October 16, 2008. Retrieved 2008-07-31.{{cite web}}: CS1 maint : bot : 원래의 URL 상태를 알 수 없음(링크) (파손)
  14. ^ Scott Contini, Krystian Matusiewicz, Josef Pieprzyk, Ron Steinfeld, Jian Guo, San Ling and Huaxiong Wang (2008). "Cryptanalysis of LASH" (PDF). Fast Software Encryption. Lecture Notes in Computer Science. Vol. 5086. pp. 207–223. doi:10.1007/978-3-540-71039-4_13. ISBN 978-3-540-71038-7.{{cite book}}: CS1 maint: 작성자 매개변수 사용(링크)
  15. ^ Brakerski, Zvika; Vaikuntanathan, Vinod (2011). "Efficient Fully Homomorphic Encryption from (Standard) LWE". {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  16. ^ Brakerski, Zvika; Vaikuntanathan, Vinod (2013). "Lattice-Based FHE as Secure as PKE". {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  17. ^ Micciancio, Daniele; Regev, Oded (2008-07-22). "Lattice-based cryptography" (PDF). Retrieved 2017-01-11. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  18. ^ Shor, Peter W. (1997-10-01). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing. 26 (5): 1484–1509. arXiv:quant-ph/9508027. doi:10.1137/S0097539795293172. ISSN 0097-5397. S2CID 2337707.
  19. ^ a b Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (2013-01-01). "Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits". CiteSeerX 10.1.1.400.6501. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)

참고 문헌 목록

  • 오드 골드레이치, 샤피 골드워서, 샤이 헤일비." 격자 감소 문제로 인한 공개 키 암호 시스템"CRYPLO '97: 제17회 암호학의 진보에 관한 국제 암호학 회의의 절차, 112–131페이지, 영국 런던, 1997.스프링거-베를라크.
  • 퐁큐.응우옌."골드레이히-골드와세르의 크립트 분석-'97' 암호의 헤일비 암호 시스템.CRYPLO '99: 제19회 암호학의 진보에 관한 국제 암호학 회의의 절차, 288–304페이지, 영국 런던, 1999.스프링거-베를라크.
  • 오드 레게브격자 기반 암호법CryptO(암호학의 진보)의 경우, 131-141, 2006페이지.