저자: 조나스닉
요약 : 상태 저장 해시 기반 서명은 공개 키로부터 생성되는 서명 수가 적을 경우 매우 효율적일 수 있습니다. 그러나 상태 저장 방식의 주요 문제점은 각 서명 작업 후 상태를 백업하고 정확하게 업데이트해야 한다는 것입니다. 본 논문에서는 상태 비저장 해시 기반 방식(예: SPHINCS+ 변형)과 불균형 XMSS 트리(물론 상태 저장 방식인 일회용 서명 공개 키를 포함)를 직접 결합하여 "SHRINCS"라는 방식을 제안합니다. 이 방식은 필요한 서명 수가 적을 때 매우 효율적이며 정적 시드를 사용하여 백업할 수 있습니다. 더 정확하게 말하면, SHRINCS 공개 키는 상태 저장 공개 키와 상태 비저장 공개 키 모두의 해시입니다. 서명 장치가 상태를 안전하게 저장할 수 있는 환경에서 키 생성이 이루어진다고 가정합니다. 따라서 서명자는 효율적인 상태 저장 서명 방식을 사용하여 서명을 생성할 수 있습니다. 상태가 손상되었거나 손실된 경우(예: 정적 시드를 사용하여 지갑을 복원하는 경우)에는 상태 비저장 서명 방식만 사용할 수 있습니다. 따라서 SHRINCS는 정상 작동 시 상태 저장 서명 방식의 효율성을 활용하는 동시에, 백업 수단으로 견고한 상태 비저장 서명 방식을 유지합니다.
신
SHRINCS 체계는 제 보고서 " 비트코인에 적용 가능한 해시 함수 기반 서명 체계 "의 부록에서 간략하게 소개되었습니다. 이 글에서는 보다 자세한 설명을 제공하며, 여러분의 의견을 환영합니다.
SHRINCS 구축에는 상태 비저장 서명 방식과 상태 저장 서명 방식(후자는 작은 서명을 생성할 수 있음)이 필요합니다. SHRINCS는 다음과 같은 알고리즘으로 구성됩니다.
- $\textsf{KeyGen}() \rightarrow (\mathit{seed}, \mathit{pk}, \mathit{state})$: 이 키 생성 알고리즘은 마스터 시드를 생성하고, 상태 저장 및 상태 비저장 서명 방식에 각각 사용되는 개인 키 $\mathit{sk}_1$과 $\mathit{sk}_2$를 도출합니다. 이 두 개인 키를 사용하여 상태 저장 및 상태 비저장 서명 방식에 각각 사용되는 공개 키 $pk1$과 $pk2$를 생성합니다. 마지막으로, $KeyGen$은 튜플 $(\mathit{seed}, \mathit{pk}, \mathit{state})$를 반환합니다. 여기서 $\mathit{pk} = H(\mathit{pk}_1, \mathit{pk}_2)$이고, $state$는 상태 저장 서명의 초기 상태입니다.
- $\textsf{Restore}(\mathit{seed}) \rightarrow (\mathit{seed}, \mathit{pk}, \mathit{state})$: 복원 알고리즘은 시드에서 SHRINCS 공개 키를 재생성하고 $state$를 $\textsf{LOST}$로 설정한 다음 튜플 $(\mathit{seed}, \mathit{pk}, \mathit{state})$를 반환합니다.
- $\textsf{Sign}(\mathit{seed}, \mathit{state}, m) \rightarrow (\mathit{state}', \mathit{sig})$: $\mathit{state} \neq \textsf{LOST}$인 경우, 서명 알고리즘은 개인 키 $\mathit{sk}_1$과 공개 키 $\mathit{pk}_2$를 다시 생성하고, $\mathit{sk}_1$, $\mathit{state}$, 그리고 메시지 $m$을 사용하여 상태 저장 서명 체계로 $\textsf{Sign}$ 서명 알고리즘을 실행합니다. 그런 다음, 업데이트된 상태 $\mathit{state}'$와 $\mathit{pk}_2$에 연결된 서명을 반환합니다. 그렇지 않으면(상태가 손상된 경우) 개인 키 $\mathit{sk}_2$와 공개 키 $\mathit{pk}_1$을 다시 유도하고 $\mathit{sk}_2$와 $m$을 사용하여 상태 비저장 서명 체계를 실행하여 $\mathit{state}' = \mathit{state}$와 $\mathit{pk}_1$에 연결된 서명을 반환합니다.
- $\textsf{Verify}(\mathit{pk}, m, \mathit{sig}) \rightarrow {\textsf{true}, \textsf{false}}$: 서명 $\mathit{sig}$를 $\mathit{sig}' | \mathit{pk}'$로 파싱하고, 상태 비저장 또는 상태 저장 방식에 따라 $\mathit{sig}'$를 검증한 다음(해시 함수 기반 서명 방식에서는 공개 키 복원을 의미함), 두 공개 키의 해시 값이 $\mathit{pk}$와 같은지 확인하는 검증 알고리즘입니다.
따라서 상태를 보존할 수 있는 서명자가 초기화된 후에는 상태 저장 방식을 사용하여 서명합니다. 그러나 시드를 사용하여 장치를 복원할 때는 상태 비저장 방식만 사용하여 서명합니다. SHRINCS에서는 상태 저장 서명 모드가 훨씬 효율적이기 때문에 복원된 장치로 서명하는 것이 처음에 $\textsf{KeyGen}$을 실행한 장치로 서명하는 것보다 훨씬 비용이 많이 듭니다.
SHRINCS의 상태 비저장 서명 체계로는 SLH-DSA 또는 본 보고서에서 자세히 설명한 SPHINCS+ 변형이 있습니다. 매개변수에 따라 서명 크기는 3KB에서 8KB까지 다양하며, 공개 키는 16바이트(NIST 보안 수준 1)입니다. 상태 저장 서명 체계의 경우, SHRINCS는 "불균형 XMSS"라고 부르는 방식을 사용합니다. 일반적인 XMSS 공개 키는 여러 개의 일회용 서명(OTS) 공개 키로 구성된 머클 트리의 루트입니다. 일회용 서명 체계에서는 하나의 공개 키로 하나의 서명만 생성할 수 있으며, 그렇지 않으면 해당 공개 키는 안전하지 않습니다. 따라서 서명 상태는 이미 생성된 서명의 개수이며, 초기값은 $q=0$입니다. XMSS를 사용하여 메시지에 서명하려면 서명자는 $q$를 증가시키고, 머클 트리에서 $q$번째 일회용 공개 키로 서명한 다음, 루트까지의 인증 경로(소위 "머클 증거")를 계산합니다. 최종 서명은 기본적으로 일회용 서명에 인증 경로가 추가된 것입니다.
SHRINCS는 일회용 서명(공개 키)으로 구성된 불균형 머클 트리를 직접 사용하지 않습니다. 대신, 상태 저장 서명 체계 부분에서 불균형 트리를 사용합니다. 따라서 첫 번째 일회용 서명 공개 키는 깊이 1에, 두 번째는 깊이 2에 위치하는 식입니다. 이는 초기 서명에 대한 인증 경로의 길이를 최소화하여 서명 수가 적을 것으로 예상되는 시나리오에 이상적입니다. 이 "불균형 XMSS" 체계에서 $q$번째 서명은 $q$번째 일회용 서명과 해당 인증 경로로 구성됩니다. NIST 보안 레벨 1에서 인증 경로 크기는 $q \cdot 16$ 바이트이고, 일회용 서명 크기는 292 바이트입니다. 더 구체적으로, 저희가 사용하는 일회용 서명 체계는 WOTS+C입니다(자세한 내용은 논문을 참조하십시오).
요약하자면, 무손실 상태 서명을 사용할 경우 SHRINCS의 서명 크기는 $\min(292 + q \cdot 16, s_l) + 16$입니다. 여기서 $q$는 상태 저장 모드에서 이 공개 키에 대해 생성된 서명의 개수이고, $s_l$은 상태 비저장 방식을 사용하여 생성된 서명의 크기입니다. 만약 $$q = 1$이라면, 이 서명은 가장 작은 서명 크기를 가진 NIST 표준 방식(ML-DSA)보다 11배 작습니다. 일반적인 비트코인 지갑의 평균 $q$ 값은 1에서 2 사이일 것으로 추정됩니다. SHRINCS의 주요 단점은 보안을 위해 안전한 상태 관리가 필수적이라는 점입니다. 하지만 상태 관리 오류로 인해 치명적인 결과를 초래할 수 있는 완전 상태 저장 방식과 달리, SHRINCS에서는 의심스러울 때 언제든지 상태 비저장 모드로 전환할 수 있습니다.
(위에)
