해시 기반 암호법

Hash-based cryptography

해시 기반 암호는 해시함수의 보안에 기반한 암호 원효 구성의 총칭이다.그것은 후분위 암호학의 한 종류로서 흥미롭다.

지금까지 해시 기반 암호화는 해시위어 프로토콜을 통해 발급된 자격 증명 및 zk-STAKK 증명 시스템 및 범위 증명과 같은 Merkle 서명 체계, 지식 제로 및 계산적으로 무결성 증명과 같은 디지털 서명 체계를 구축하는데 사용된다.해시 기반 서명 체계는 일회성 서명 체계에 Merkle 트리 구조를 결합한다.일회성 서명 방식 키는 하나의 메시지에 안전하게 서명만 할 수 있기 때문에, 그러한 많은 키를 하나의 더 큰 구조 내에서 결합하는 것이 실용적이다.머클 트리 구조는 이 목적을 위해 사용된다.이 계층적 데이터 구조에서는 해시함수와 결합을 반복적으로 사용하여 트리 노드를 계산한다.램포트 서명은 Merkle 트리 구조와 결합할 수 있는 일회성 서명 방식의 예다.

미국 국립표준기술원은 2019년 서로 다른 상황에서 적용 가능한 eXtended Merkle Signature(XMS)와 LMS(Leighton-Micali Signature)를 기반으로 한 국가별 해시 기반 암호 표준의 공표 의사를 밝혔다.[3]

역사

레슬리 램포트는 1979년에 해시 기반 서명을 발명했다.그 XMSS(해시 서명 방안 eXtended)[4]과 SPHINCS[5][6]hash-based 서명 제도 2011년과 2015년에, 각각. XMSS 연구 팀에 의해 요하네스 Buchmann의 방향 아래 개발되었다 둘 다 해시의 독창적인 계획 및 2007 일반화된 해시 서명 제도에 기반을 두고 있(GMSS)[7]multi-tree va. 소개되었다XM의 riantSS, XMSS는MT 2013년에 설명되었다.[8]

일회성 서명 방식

해시 기반 서명 체계는 일회성 서명 체계를 구성 요소로 사용한다.주어진 일회성 서명 키는 오직 하나의 메시지에 안전하게 서명하는 데만 사용될 수 있다.실제로 서명을 하면 서명 키의 일부가 드러난다.(해시 기반) 일회성 서명 체계의 보안은 전적으로 기본 해시함수의 보안에 의존한다.

일반적으로 사용되는 일회성 서명 방식에는 램포트-디피 방식, 윈터니츠 방식[9] 및 W-OTS+ 방식과 같은 개선 사항이 포함된다.[10]세미날 램포트-디피 방식과 달리 윈터니츠 방식과 변형 방식은 한 번에 많은 비트를 서명할 수 있다.한 번에 서명할 비트 수는 값인 Winternitz 파라미터에 의해 결정된다.이 매개변수의 존재는 크기와 속도 사이의 균형을 제공한다.윈터니츠 매개변수의 큰 값은 서명 및 확인 속도가 느린 가격에 짧은 서명과 키를 산출한다.실제로 이 파라미터의 일반적인 값은 16이다.

상태 비저장 해시 기반 서명의 경우, 몇 번의 서명 방식이 사용된다.그러한 계획은 몇 번 키를 두 번 이상 사용할 경우 보안이 점차적으로 감소할 수 있게 한다.HORST는 몇 번의 서명 계획의 한 예다.

많은 일회성 키 쌍을 해시 기반 서명 구성으로 결합

해시 기반 서명 체계의 중심 개념은 많은 수의 일회성 키 쌍을 단일 구조로 결합하여 두 번 이상(제한된 횟수) 서명하는 실질적인 방법을 얻는 것이다.이것은 가능한 변형과 함께 Merkle 트리 구조를 사용하여 수행된다.하나의 공용 키와 하나의 개인 키는 기본 일회성 계획의 수많은 공용 키와 개인 키로 구성된다.글로벌 공개 키는 머클 트리 맨 위에 있는 단일 노드다.그것의 값은 선택한 해시함수의 출력이므로, 일반적인 공개키 크기는 32바이트다.이 글로벌 공개 키의 유효성은 일련의 트리 노드를 사용하여 주어진 일회성 공개 키의 유효성과 관련이 있다.이 순서를 인증 경로라고 한다.서명의 일부로 저장되며, 검증자가 두 공개 키 사이의 노드 경로를 재구성할 수 있다.

글로벌 개인 키는 일반적으로 의사 난수 생성기를 사용하여 처리한다.그러면 시드 값을 저장하기에 충분하다.일회용 비밀키는 생성기를 사용하여 시드 값에서 연속적으로 파생된다.이러한 접근방식을 통해 글로벌 개인 키도 매우 작다(예: 일반적으로 32바이트).

나무횡단 문제는 서명 수행에 매우 중요하다.점점 더 효율적인 접근법이 도입되어 서명 시간이 획기적으로 빨라지고 있다.

일부 해시 기반 서명 체계는 여러 계층의 트리를 사용하며, 더 큰 서명 가격으로 더 빠른 서명을 제공한다.그러한 계획에서는, 가장 낮은 층의 나무만 메시지에 서명하는 반면, 다른 모든 나무들은 낮은 나무의 뿌리 값에 서명한다.

나오-영 작품은[11] 머클 계열의 한정된 시간 서명을 무제한(정규) 서명 방식으로 옮기는 패턴을 보여준다.

해시 기반 서명 구성의 속성

해시 기반 서명 체계는 기본 해시함수에 대한 보안 가정에 의존하지만, 이러한 가정을 충족하는 해시함수는 모두 사용할 수 있다.결과적으로, 각각의 적절한 해시함수는 다른 해시 기반 서명 체계를 산출한다.주어진 해시함수가 불안정하게 되더라도, 그것을 다른 안전한 해시함수로 대체하면 충분히 고려 중인 해시 기반 서명체계의 안전한 인스턴스화를 얻을 수 있다.일부 해시 기반 서명 체계(가성 키 생성을 포함한 XMSS 등)는 정방향 보안으로, 비밀 키가 손상되더라도 이전 서명은 유효함을 의미한다.

보안 가정의 최소성은 해시 기반 서명 체계의 또 다른 특성이다.일반적으로 이러한 체계는 체계의 전체적인 보안을 보장하기 위한 보안(예를 들어 제2의 프리이미지 저항의 의미) 암호 해시함수만 필요로 한다.이러한 종류의 가정은 모든 디지털 서명 방식에 필요하다. 그러나 다른 서명 체계에는 추가적인 보안 가정이 필요하지만, 여기서는 그렇지 않다.

해시 기반 서명 체계에 의존하기 때문에 해시 기반 서명 체계는 정해진 수의 메시지만 안전하게 서명할 수 있다.Merkle 및 XMSS 스키마의 경우, 최대 2개의 메시지를 안전하게 서명할 수 있으며, 총 Merkle 트리 높이는 이다.

해시 기반 서명 구성의 예

Merkle의 초기 계획 이후, 성능 향상을 가진 수많은 해시 기반 서명 체계가 도입되었다.최근의 것에는 XMSS, 레이튼-마이칼리(LMS), SPINGCS 및 BPQS 체계가 포함된다.대부분의 해시 기반 서명 체계는 상태 저장적이며, 이는 서명이 기존의 디지털 서명 체계와는 달리 비밀 키를 업데이트해야 함을 의미한다.상태 저장 해시 기반 서명 체계의 경우 서명은 사용된 일회성 키의 상태를 유지하고 키가 재사용되지 않는지 확인해야 한다.XMSS, LMS 및 BPQS[12] 체계는 상태 비저장인 반면 SPINGCS 체계는 상태 비저장이다.SPINGCS 서명은 XMS, LMS 서명보다 큰 반면 BPQS는 블록체인을 위해 특별히 설계되었다.WOTS+ 일회성 서명 방식 외에도 [10]SPINGCS는 HOST라는 몇 번의 (해시 기반) 서명 방식도 사용한다. HOST는 이전의 몇 번의 서명 방식인 HOST(Hash to Object Subset)를 개선한 것이다.[13]

상태 저장 해시 기반 체계 XMSS와 XMSS는MT RFC 8391(XMS: eXtended Merkle Signature Scheme)에 지정되어 있으며,[14] Leighton-Micali 해시 기반 서명은 RFC 8554에 지정되어 있다.[15]권위 있는 계획들이 도입하는 우려를 완화시키는 실질적인 개선들이 문헌에 제안되어 왔다.[16]이러한 계획에 적합한 해시함수는 SHA-2, SHA-3, 블레이크를 포함한다.

구현

이미 NIST 표준화된 타원 곡선 디지털 시그니처 알고리즘(Electric Curve Digital Signature Algorithm, ECDSA)을 사용하는 다른 인기 있는 블록체인 네트워크나 암호화폐와 달리 오픈 소스 네트워크로는 최초로 eXtended Merkle 시그니처 체계를 구현했다.[17][18]전통적인 ECDSA 서명과는 대조적으로, 이 상태 저장 서명 체계는 쇼르의 알고리즘을 실행하는 충분히 강력한 양자 컴퓨터에 내성이 있다.[19][20]

XMSS, GMSS, SPINGCS 체계는 자바 번시 캐슬 암호화 APIs에서 이용할 수 있으며,[21] SPINGCS는 SUPERCOP 벤치마킹 툴킷에서 구현된다.[22]XMSS RFC의 최적화[23] 및 최적화되지[24] 않은 참조 구현이 존재한다.LMS[25] 체계는 인터넷-대안 작성에 따라 파이톤과 C에서[26] 구현되었다.

참조

  1. ^ 확장 가능하고 투명하며 수량 이후 안전한 컴퓨팅 무결성, 벤사손, 일라이 및 벤토프, 이도 및 호레쉬, 이논 및 리아브제프, 마이클, 2018년
  2. ^ Chalkias, Konstantinos; Cohen, Shir; Lewi, Kevin; Moezinia, Fredric; Romailler, Yolan (2021). "HashWires: Hyperefficient Credential-Based Range Proofs". Privacy Enhancing Technologies Symposium (PETS) 2021.
  3. ^ Computer Security Division, Information Technology Laboratory (2019-02-01). "Request for Public Comments on Stateful HBS CSRC". CSRC NIST. Retrieved 2019-02-04.
  4. ^ Buchmann, Johannes; Dahmen, Erik; Hülsing, Andreas (2011). "XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions". Lecture Notes in Computer Science. 7071 (Post-Quantum Cryptography. PQCrypto 2011): 117–129. CiteSeerX 10.1.1.400.6086. doi:10.1007/978-3-642-25405-5_8. ISSN 0302-9743.
  5. ^ Bernstein, Daniel J.; Hopwood, Daira; Hülsing, Andreas; Lange, Tanja; Niederhagen, Ruben; Papachristodoulou, Louiza; Schneider, Michael; Schwabe, Peter; Wilcox-O’Hearn, Zooko (2015). Oswald, Elisabeth; Fischlin, Marc (eds.). SPHINCS: practical stateless hash-based signatures. Lecture Notes in Computer Science. Vol. 9056. Springer Berlin Heidelberg. pp. 368–397. CiteSeerX 10.1.1.690.6403. doi:10.1007/978-3-662-46800-5_15. ISBN 9783662467992.
  6. ^ "SPHINCS: Introduction".
  7. ^ Buchmann, Johannes; Dahmen, Erik; Klintsevich, Elena; Okeya, Katsuyuki; Vuillaume, Camille (2007). "Merkle Signatures with Virtually Unlimited Signature Capacity". Lecture Notes in Computer Science. 4521 (Applied Cryptography and Network Security): 31–45. doi:10.1007/978-3-540-72738-5_3.
  8. ^ Hülsing, Andreas; Rausch, Lea; Buchmann, Johannes (2013). Optimal Parameters for XMSSMT. Lecture Notes in Computer Science. Vol. 8128. pp. 194–208. doi:10.1007/978-3-642-40588-4_14. ISBN 978-3-642-40587-7.
  9. ^ Dods, C.; Smart, N. P.; Stam, M. (2005). "Hash Based Digital Signature Schemes". Lecture Notes in Computer Science. 3796 (Cryptography and Coding): 96–115. doi:10.1007/11586821_8.
  10. ^ a b Hülsing, Andreas (2013). W-OTS+ — Shorter Signatures for Hash-Based Signature Schemes. Lecture Notes in Computer Science. Vol. 7918. pp. 173–188. doi:10.1007/978-3-642-38553-7_10. ISBN 978-3-642-38552-0.
  11. ^ M. Naor, M. Young."Universal One-Way Hash Functions and the Cryptographic Applications".STOC 1989.[1]
  12. ^ Chalkias, Konstantinos; Brown, James; Hearn, Mike; Lillehagen, Tommy; Nitto, Igor; Schroeter, Thomas (2018). "Blockchained Post-Quantum Signatures" (PDF). Proceedings of the IEEE International Conference on Blockchain (Cybermatics-2018): 1196–1203.
  13. ^ Reyzin, Leonid; Reyzin, Natan (2002). Better than BiBa: Short One-Time Signatures with Fast Signing and Verifying. Lecture Notes in Computer Science. Vol. 2384. pp. 144–153. CiteSeerX 10.1.1.24.7320. doi:10.1007/3-540-45450-0_11. ISBN 978-3-540-43861-8.
  14. ^ Hülsing, Andreas; Butin, Denis; Gazdag, Stefan; Rijneveld, Joost; Mohaisen, Aziz. "RFC 8391 - XMSS: eXtended Merkle Signature Scheme". tools.ietf.org. IETF.
  15. ^ McGrew, David; Curcio, Michael; Fluhrer, Scott. "RFC 8554 - Leighton-Micali Hash-Based Signatures". tools.ietf.org. IETF.
  16. ^ McGrew, David; Kampanakis, Panos; Fluhrer, Scott; Gazdag, Stefan-Lukas; Butin, Denis; Buchmann, Johannes (2016). "State Management for Hash-Based Signatures" (PDF). Lecture Notes in Computer Science. 10074 (Security Standardisation Research): 244–260. doi:10.1007/978-3-319-49100-4_11. Archived from the original (PDF) on 2017-08-18.
  17. ^ Wang, Licheng; Shen, Xiaoying; Li, Jing; Shao, Jun; Yang, Yixian (2019-02-01). "Cryptographic primitives in blockchains". Journal of Network and Computer Applications. 127: 43–58. doi:10.1016/j.jnca.2018.11.003. ISSN 1084-8045.
  18. ^ "The Quantum Resistant Ledger". theqrl.org. 2019-08-24.
  19. ^ "NIST Stateful Hash-Based Signatures" (PDF). NIST. 2019-02-04.
  20. ^ Computer Security Division, Information Technology Laboratory (2018-12-20). "Hash-Based Signatures CSRC". CSRC NIST. Retrieved 2019-09-06.
  21. ^ "bcgit/bc-java". GitHub. 2018-12-18.
  22. ^ "SUPERCOP". Archived from the original on 2015-02-15. Retrieved 2017-05-31.
  23. ^ "Code". Andreas Hülsing.
  24. ^ "squareUP > Publications". www.pqsignatures.org.
  25. ^ David, McGrew (2018-05-29). "The hash-sigs package: an implementation of the Leighton-Micali Hierarchical Signature System (HSS)". GitHub.
  26. ^ David, McGrew (2018-11-22). "A full-featured implementation of the LMS and HSS Hash Based Signature Schemes from draft-mcgrew-hash-sigs-07". GitHub.
  • T. 랑게."해시 기반 서명".Springer US, 2011년 암호 및 보안 백과사전.[2]
  • F. T. 레이튼, S. 미칼리."단일 보안 해시 함수를 기반으로 한 대규모의 빠르고 안전한 디지털 서명 체계"미국 특허 5,432,852, [3] 1995.
  • G. 베커."Merkle Signature Schemes, Merkle Trees and Thes Cryptal Analysis", 2008년 독일 루르 대학교 보훔에서 열린 세미나 'Post Quantum Cryptology'.[4]
  • E. 다멘, M. 드링, E. 클린세비치, J. 부흐만, L.C. 코로나도 가르시아"CMS — 향상된 Merkle 시그니처 스키마".암호학의 진보 - Indocrypt 2006.[5]
  • R. Merkle."재활용, 인증 및 공개 키 시스템 / A 인증 디지털 서명"1979년 스탠퍼드대 전기공학과의 박사학위 논문.[6]
  • S. 미칼리, M. 야콥손, T. 레이튼, M. 시들로."프랙탈 머클 트리 표현 및 트래버설".RSA-CT 03. [7]
  • P. 캄파나키스, S.번지르르하다."LMS 대 XMSS: 상태 저장 해시 기반 서명 제안 표준의 비교".Cryptology ePrint Archive, Report 2017/349.[8]
  • D.나오르, A.선하브 A.울. "원타임 시그니처 재방문: 프랙탈 머클 트리 트래버설을 이용한 실용적인 빠른 시그니처"2006년 이스라엘에서 열린 IEEE 24차 전기전자 기술자 협약.[9]

외부 링크

  • [10] 해시 기반 서명 체계에 관한 참고 문헌 목록이다.
  • [11] 참고문헌의 다른 목록(미작성).