요약
이 문서는 격자 암호화와 함께 작동하는 계층적 결정론적 지갑 체계를 설명합니다.
동기
계층적 결정론적 지갑(HD 지갑)은 블록체인에서 사실상 표준이 되었습니다. 블록체인 산업이 양자 이후의 미래를 논의함에 따라, 우리는 이 기술을 격자 암호화 설정의 키에 적용하고 싶습니다. 무제한의 사전에 연결되지 않은 키를 생성하는 단일 시드 구문을 백업하는 사용자 경험이 사용자가 매번 작업을 수행할 때마다 동일한 지갑을 백업해야 하는 것보다 훨씬 선호됩니다.
우리는 딜리시움 서명 체계에 초점을 맞추고 있습니다. 이는 최초로 최종화된 NIST 양자 이후 서명이며 산업 표준이 될 가능성이 높습니다.
격자 암호화를 HD 설정에 적용하는 데는 두 가지 과제가 있습니다. 첫째, HMAC-SHA512의 출력을 그대로 격자 개인 키로 사용할 수 없다는 것입니다. 팔콘과 딜리시움의 경우 격자에 대해 "좋은 기반"(작은 벡터)을 형성하는 다항식이 필요하며, 키 생성 알고리즘은 거부 샘플링을 사용하므로 수정 없이는 HD 지갑 체계에 맞지 않습니다.
두 번째 과제는 BIP32에서 비하드웨어 키가 타원곡선 포인트(공개 키)의 덧셈을 통해 파생되지만 격자에는 그러한 동등한 연산이 없다는 것입니다: 격자 공개 키 집합은 덧셈이나 곱셈에 대해 폐쇄적이지 않습니다.
우리는 이 QIP에서 첫 번째 과제를 해결하고 비하드웨어 키를 지원하지 않을 것입니다. 우리의 지식으로는 격자 암호화 설정에서 두 번째 과제를 극복할 수 있는지는 열린 연구 질문입니다. 비하드웨어 키는 읽기 전용 또는 감사 지갑에 사용되며 HD 지갑의 주요 용도에 필수적이지 않으므로 이를 심각한 단점으로 보지 않습니다.
사양
핵심 아이디어는 각 반복에서 HMAC의 엔트로피 출력을 다항식 샘플링을 위한 RNG로 사용하는 것입니다. BIP32에서 HMAC 출력의 절반은 개인 키로 사용되며, "하드웨어" 케이스에서는 직접적으로, "비하드웨어" 케이스에서는 이전 개인 키에 추가됩니다. 이는 타원곡선 암호화 알고리즘의 구조 때문에 개인 키를 타원곡선 그룹의 생성 포인트에 곱해지는 정수로 볼 수 있기 때문입니다.
팔콘과 딜리시움 모두에서 키 생성 알고리즘은 키 파생 프로세스에서 <= 64바이트의 엔트로피를 소비합니다. HMAC의 전체 출력을 키 생성 프로세스에 직접 입력할 수 있지만, BIP44 지갑과의 상호 운용성을 최대화하기 위해 출력의 절반만 사용합니다. 이렇게 하면 체계가 BIP32의 하드웨어 키 파생과 동일해집니다.
시드를 기본 키 형식으로 사용하는 이 기술은 NIST에서 지원됩니다.
참조 구현
격자 HD 지갑의 구현은 여기에 있습니다. 우리는 표준의 저자들이 C로 작성한 딜리시움의 참조 구현인 pq-crystals에서 생성된 테스트 벡터에 대해 테스트합니다.
두 지갑 버전 모두 니모닉 "시드 구문"에서 "시드"로 가져오기 위해 러스트 라이브러리 bip39를 사용합니다. 그런 다음 시드에서 HMAC-SHA512를 통해 "마스터 키"를 파생하고, 이는 키 트리의 루트를 형성하며, 각 에지는 BIP32 표준에 설명된 대로 트리의 상위 분할 값인 L || R에 대해 HMAC-SHA512(R || 0x00 || L || 자식_인덱스)를 나타냅니다.
근거
우리는 처음에 키와 서명이 더 작은 팔콘을 고려했습니다. 이를 위해 우리는 토마스 포닌의 러스트-fn-dsa 구현을 사용했으며, 외부에서 생성된 엔트로피를 허용하도록 약간의 수정을 가했습니다. 토마스 포닌은 팔콘 표준의 저자 중 한 명이었고, 알고리즘의 PQClean C-lang 구현의 저자였습니다. 팔콘 지갑의 구현은 여기에 있습니다.
나중에 토마스 포닌으로부터 팔콘 표준이 키 생성 경로를 완전히 지정하지 않는다는 것을 알게 되어 ml-dsa(이전의 딜리시움)로 전환하기로 결정했습니다. 딜리시움에는 여러 가지 장점이 있습니다.
- 더 단순함
- 더 빠름
- 결정론적 키 생성
- 이미 NIST에 의해 최종화됨
단점은 더 큰 키, 더 큰 서명, 그리고 더 느린 검증입니다.
어쨌든 격자 키와 서명은 타원곡선보다 훨씬 크므로 더 많은 디스크 공간을 사용해야 할 것입니다.
딜리시움과 팔콘 모두 키 생성 프로세스에 <= 64바이트의 엔트로피를 입력으로 요구하므로 HMAC-SHA512 출력의 처음 32바이트를 엔트로피 소스로 사용할 수 있습니다. 비하드웨어 사용 사례는 격자 암호화로 명확하게 달성할 수 없으므로 생략합니다.
HMAC-SHA512의 양자 보안과 관련하여, 해시 함수에 대한 주요 양자 공격은 정렬되지 않은 데이터베이스(우리의 경우 해시 사전 이미지)를 검색하는 데 이차 속도 향상을 제공하는 그로버 알고리즘입니다. 이는 보안 비트를 절반으로 줄이므로 512 → 256, 256 → 128 등입니다. 이는 모든 해시 함수에 적용되므로 고전적으로 안전한 해시 알고리즘은 동일한 문제가 있습니다. 반면에 그로버 알고리즘이 점근적으로 최적임이 증명되었으므로 안전한 해시 함수에 대해 그로버 알고리즘보다 훨씬 나은 다른 양자 알고리즘을 기대해서는 안 됩니다.
해시 함수와 대조적으로, 블록체인의 디지털 서명은 양자 공격에 훨씬 더 취약합니다. 쇼어 알고리즘은 공개 키에서 타원곡선 개인 키를 찾는 난이도를 지수에서 다항 대수 O(log^3(n))로 줄입니다. 여기서 n은 비트 수입니다.
이러한 이유로 우리는 양자 공격에 대비해 디지털 서명을 보호하는 데 우선순위를 두고 해시 함수는 그대로 둘 것입니다.
저작권
이 사양은 공개 도메인에 공개됩니다.
BIP32 요약은 이 다이어그램을 참조하세요.
이 제안은 원래 Quantus 개선 제안으로 여기에 게시되었습니다.
