저자: 데이비드 웡
출처: https://cryptologie.net/posts/hash-based-signatures-part-iv-xmss-and-sphincs/
원문은 2015년 12월에 발표되었습니다.
이 글은 해시 함수 기반 서명 방식에 대한 블로그 시리즈의 마지막 글입니다. 시리즈의 첫 번째 글 ( 중국어 번역본 )은 여기에서 확인할 수 있습니다.
자, 이제 흥미로운 부분, 즉 실제 서명 방식에 대해 알아보겠습니다.
PQCrypto는 한 달 전에 예비 제안서를 발표했습니다. 제안된 두 가지 양자 후 암호화 알고리즘은 " XMSS "와 " SPHINCS "입니다.
이 글에서는 먼저 상태 저장 서명 방식인 XMSS를 소개하고, 그 다음 최초의 상태 비저장 서명 방식인 SPHINCS를 소개합니다!
XMSS
" 확장 머클 서명 방식 (XMSS)"은 2011년에 등장했으며 , 2015년에 IETF(인터넷 엔지니어링 태스크 포스)의 초안으로 채택되었습니다 .
XMSS 트리의 주요 구조는 머클 트리와 유사하며, 몇 가지 사소한 차이점만 있습니다. XMSS 트리에서 자식 노드는 부모 노드로 해싱되기 전에 마스크 와 XOR 연산됩니다. 각 노드는 고유한 마스크를 가지고 있습니다.
두 번째 독특한 점은 XMSS 트리의 잎 노드가 일회용 공개 키의 해시값이 아니라 "L-트리"라고 불리는 다른 유형의 트리의 루트 값이라는 것입니다.
L-트리는 노드의 해시 값에 마스크를 적용합니다. L-트리의 마스크는 메인 XMSS 트리의 마스크와는 다르지만, 모든 L-트리에서 공통적으로 사용됩니다.
L-트리의 잎 노드에는 WOTS+ 공개 키를 가진 요소가 저장됩니다(이 체계는 이 시리즈의 첫 번째 기사 ( 중국어 번역 )에서 설명합니다).
저처럼 WOTS+ 공개 키를 트리 구조에 저장해야 하는 이유가 궁금하시다면, Huelsing의 설명을 참고하세요.
트리 구조의 목적은 WOTS 공개 키를 저장하는 것이 아니라 해시하는 것이며, 이 방법을 통해 "2차 역상 저항성"을 갖춘 해시 함수만으로도 충분하다는 것을 증명할 수 있습니다(충돌 저항성을 갖춘 해시 함수는 필요하지 않습니다).
또한, 마스터 공개 키는 XMSS 트리의 루트 노드와 XMSS 트리 및 L-트리에서 사용되는 비트마스크로 구성됩니다.
스펀지
“SPHINCS”는 이 분야의 많은 발전된 기술을 통합한 새로운 접근 방식입니다! 이는 우리 모두가 기다려온 무국적 상태를 실현시켜 줍니다.
맞습니다. 이제 더 이상 상태를 저장할 필요가 없습니다. 하지만 어떻게 가능한지 설명하기 전에 SPHINCS의 구조를 살펴보겠습니다.
첫째, SPHINCS는 여러 개의 나무로 구성되어 있습니다.
첫 번째 나무를 살펴보겠습니다.
- 각 노드는 이전 노드들의 연결 결과를 해당 레벨의 비트마스크와 XOR 연산한 해시 값입니다.
- 공개 키는 루트 해시 값과 비트마스크로 구성됩니다.
- 트리의 잎들은 WOTS+ L-트리의 압축된 공개 키들입니다.
WOTS+ L-트리는 앞서 설명한 XMSS L-트리와 유사하지만, 비트마스크 설계가 SPHINCS 해시 트리와 더 비슷하다는 점(즉, 트리의 각 레벨에 전용 마스크가 있다는 점)을 고려하면 이해하기 쉽습니다.
각 리프에는 Winderitz 일회용 서명이 포함되어 있어 다른 트리에 서명할 수 있습니다. 따라서 위 다이어그램에 따르면 다음 레이어에는 각각 리프에 WOTS+ 공개 키가 포함된 4개의 SPHINCS 트리가 있게 됩니다.
이 과정은 아래쪽으로 계속됩니다... 나무 더미의 수와 각 나무의 잎사귀 수는 초기 매개변수에 따라 완전히 달라집니다. 결국 0층에 도달하면 WOTS+ 서명은 더 이상 다른 SPHINCS 나무에 서명하지 않고 HORS 나무에 서명하게 됩니다.
HORS 트리는 구조적으로 L-트리와 동일하지만, 윈터니츠 일회용 서명 대신 HORS 다회 서명을 포함한다는 점이 다릅니다. 우리는 메시지 서명에 HORS 트리를 사용하는데, 이는 서명 시 항상 동일한 HORS 키를 사용하기 때문에 보안을 강화합니다. 따라서 심각한 보안 문제는 발생하지 않습니다.
SPHINCS 논문에 실린 다음 다이어그램은 WOTS+ L-트리를 추상화하여(다음 SPHINCS 트리의 서명으로 표시) 메시지에 이르는 고유 경로를 보여줍니다.
메시지 M에 서명할 때, 먼저 M에 대한 "랜덤화된" 해시 값과 "랜덤화된" 인덱스 번호를 생성합니다. 여기서 큰따옴표를 사용하는 이유는 SPHINCS 서명 방식에서는 모든 것이 의사 난수 함수를 사용하여 결정론적으로 계산되기 때문입니다. 이 매개변수는 M의 랜덤화된 해시 값에 서명하는 데 사용할 HORS 트리를 지정합니다. 따라서 인덱스 번호가 메시지로부터 결정론적으로 생성되므로 상태를 기억할 필요가 없습니다. 동일한 메시지에 서명할 때는 항상 동일한 HORS 트리가 사용되지만, 서로 다른 두 메시지에 서명할 때는 서로 다른 HORS 트리가 사용될 확률이 높습니다.
이번 시리즈는 여기서 끝납니다!
추가: 제가 생각하기에 아주 훌륭한 논문 " 무장한 스팽그 "에 실린 또 다른 삽화를 소개합니다!
(위에)
