제작자: Blocksteam 팀
출처: https://blog.blockstream.com/schnorr-but-with-vectors-lattice-based-signatures-explained/
참고 : 이 글은 심층 연구 논문 및 강좌에 대한 소개입니다. 보다 자세한 기술적 설명은 연구 보고서를 참조하시고 강좌를 시청해 주시기 바랍니다.
구글이 양자 컴퓨팅을 다룬 양자 인공지능 관련 논문을 발표하면서 암호학적으로 중요한 양자 컴퓨터 (CRQC)의 등장 시기에 대한 논의가 활발해졌습니다. 출시 시기에 대한 예측은 다양하지만, 암호학계의 공통된 의견은 양자 보안 암호화 알고리즘을 지금부터 연구하고 준비해야 한다는 것입니다.
주요 과제는 현재 비트코인에서 사용하는 양자역학적으로 취약한 타원곡선 암호화(ECDSA)를 대체할 양자 안전성이 확보된 전자 서명 체계를 선택하는 것입니다. 그러나 Schnorr와 ECDSA를 능가하는 것은 단순히 다른 알고리즘으로 전환하는 것만큼 간단하지 않습니다. 비트코인 커뮤니티는 현재 두 가지 주요 문제에 집중하고 있습니다. 첫째, 안전하게 마이그레이션을 수행하는 방법 이고, 둘째, 어떤 양자 후(PQ) 암호화 체계로 마이그레이션할 것인가입니다. 이 글에서는 후자에 초점을 맞춰 가장 유망한 양자 후 서명 체계를 살펴보고자 합니다.
다음은 현재 양자역학 분야에 대한 저희의 관찰 내용입니다. 이러한 관찰 내용은 블록스트림이 "격자 기반" 암호화에 집중하는 이유와 이러한 서명 방식이 작동하는 방식에 대한 설명도 포함합니다.
양자역학 이후 시대
양자 후 서명과 관련하여 암호학자들은 일반적으로 양자 컴퓨터가 해독하기 어려울 것으로 예상되는 네 가지 (가상의) 까다로운 가정에 초점을 맞춥니다.
1. 해시 함수 기반 암호화 . 이 방식의 보안은 해시 함수를 역으로 복호화할 수 없다는 가정에 기반합니다. 오늘날 사용되는 모든 암호화 기본 요소 중에서 이러한 가정이 가장 안정적인 것으로 간주됩니다.
또한, 상태 저장 방식(예: SHRINCS )은 324바이트에 불과한 매우 간결한 서명을 생성할 수 있지만, 이러한 간결성은 세심한 상태 관리라는 대가를 치러야 합니다. 반대로, 상태 관리의 부담을 피하는 방식은 상대적으로 큰 최종 서명 참조 크기를 갖는 상태 비저장 서명을 생성합니다. 두 방식 모두 대수적 유연성이 부족하다는 문제점을 안고 있습니다. 즉, 효율적인 다중 서명이나 임계값 서명과 같은 변형 방식을 개발하는 것은 현재로서는 불가능해 보입니다.
Blockstream은 " 비트코인을 위한 해시 함수 기반 서명 체계 연구 "(미하일 쿠디노프, 조나스 닉 공저)와 " SHRIMPS "(조나스 닉 공저)에서 볼 수 있듯이 이러한 유형의 암호화에 대한 포괄적인 연구를 수행했습니다. 이제 우리는 앞서 언급한 문제점들을 해결할 수 있는 격자 기반 방식에 대해 살펴보겠습니다.
2. 격자 기반 암호화 . 이러한 방식의 보안은 " 격자 "라고 불리는 수학적 대상과 관련된 특정 문제와 연관됩니다. 이 대상은 18세기부터 수학자들에 의해 연구되어 왔습니다. 아래 그림과 같이 격자는 무수히 많은 점으로 이루어진 행렬로 상상할 수 있습니다. 타원 곡선 위의 두 점을 더하면 같은 타원 곡선 위의 세 번째 점이 생성되는 것처럼, 이 격자 위의 두 점을 더하면 같은 격자 위의 또 다른 유효한 점이 생성됩니다.
따라서 이 격자에 대해 다음과 같은 질문을 할 수 있습니다. 이 격자 위의 두 점 사이의 최단 거리는 얼마인가? 또는 평면에서 임의로 한 점을 선택했을 때, 그 점에 가장 가까운 격자점은 무엇인가? 적절하게 구성된 격자의 경우, 양자 컴퓨터는 격자의 기본 기하학적 세부 사항을 알지 못하면 이러한 모든 질문에 답하기 어렵다고 여겨집니다.
해시 함수 기반 방식이나 더 작은 무상태 서명 방식과 비교했을 때, 격자 방식의 주요 특징은 대수적 유연성입니다. 이에 대해서는 다음 장에서 더 자세히 설명하겠습니다.
3. 인코딩 기반 암호화 . 오류 정정 코드(ECC)는 이 분야에서 널리 사용되는 또 다른 수학적 도구입니다. 예를 들어, ZK-STARK와 같은 양자 후 검증 시스템에서 활용되기 때문에 들어보셨을 수도 있습니다. 그러나 ECC를 기반으로 하는 현재의 서명 방식은 (해시 함수 기반 및 격자 기반 방식과 비교했을 때) 생성되는 공개 키와 서명의 크기가 너무 커서 실용적이지 않습니다. 일반적으로 이러한 객체는 크기가 10KB를 쉽게 초과하며, NIST 후보 방식인 LESS가 대표적인 예입니다.
4. 동형 암호화 . 이 유형의 암호화는 앞서 언급한 후보 방식들보다 더 작은 공개 키와 서명을 생성할 수 있습니다. 예를 들어, SQISign 의 공개 키와 서명의 총 크기는 213바이트에 불과합니다(비교하자면, Schnorr 서명 방식은 96바이트입니다). 이는 매우 인상적인 수치입니다. 그러나 이 방식의 수학적 기반은 대수 기하학의 매우 새로운 개념에 의존합니다. 암호학에서 복잡성은 종종 보안의 적이 되는데, 이러한 복잡한 집합 구조가 작은 취약점을 숨길 수 있기 때문입니다. 따라서 이러한 방식들을 비트코인에 통합하기 전에 대량 스트레스 테스트를 거쳐야 합니다.
보시다시피, 위에서 언급한 네 가지 패러다임 각각에는 서명 크기, 보안 및 견고성, 유연성과 같은 장단점이 있으며, 이는 다음 다이어그램에 요약되어 있습니다.
요약하자면, 현재의 코드 기반 서명 방식은 비트코인의 엄격한 블록 공간 제약 조건에 비해 너무 번거롭습니다. 공통 기원을 기반으로 하는 수학적 방식은 간결하지만 안전하게 구현하기가 매우 어렵고 여전히 논란의 여지가 많습니다. 해시 함수 기반 서명 방식은 매우 안전하고 잘 알려져 있지만, 대수적으로 "경직"하다는 단점이 있습니다.
비트코인의 장기적인 미래를 볼 때, 격자 기반 암호화 방식은 가장 균형 잡히고 유망한 후보 중 하나로 떠올랐습니다.
격자 서명을 사용하는 이유는 무엇일까요? 대수적 유연성 때문입니다.
격자 암호화가 비트코인에 매력적인 이유를 이해하려면 현재 비트코인 서명 방식(슈노르 및 ECDSA)을 매우 효율적으로 만드는 요소를 살펴볼 필요가 있습니다.
현재 비트코인 서명 체계의 보안은 이산 로그(DL) 문제에 기반합니다. DL 방식의 중요한 장점은 잘 짜여진 수학적 프레임워크입니다. 예를 들어, 두 개의 개인 키를 결합하면 공개 키의 조합 또한 예측 가능한 형태로 만들 수 있습니다.
[x + y].G = [x].G + [y].G이러한 기하학적 동형 속성은 비트코인 개발자들이 다중 서명(예: Onas Nick, Tim Ruffing, Yannick Seurin이 개발한 MuSig2 ), 임계값 서명, 계층적 결정론적 유도, "어댑터 서명"과 같은 고급 프로토콜을 개발할 수 있었던 이유입니다.
해시 함수 (SHA256 및 BLAKE 등)는 이와 정반대입니다. 마치 무작위 믹서처럼 작동합니다. 해시 함수 H 가 주어졌을 때, 두 입력값을 더해도 두 입력값의 해시 함수 출력값 사이에는 아무런 관계가 없습니다. 즉, H(x+y) H(x)+H(y) 와 같지 않습니다. 이러한 구조의 부재가 바로 해시 함수의 보안성을 보장하는 요소이지만, 동시에 해시 함수 위에 고수준 프로토콜을 개발하는 것을 매우 어렵게 만듭니다.
하지만 격자 암호화는 이러한 수학적 구조를 제공합니다. 타원 곡선 위의 한 점에 스칼라 값을 곱하는 대신, 격자 암호화는 숫자 격자(행렬)에 숫자 열(벡터)을 곱합니다. 공개 행렬 A 와 두 개의 비밀 값 x 와 y 가 있다면, A(x+y) = Ax + Ay 성립합니다(이산 로그의 맥락에서 (x+y)G=xG+yG 유사합니다).
여기서 중요한 점은 격자 암호화에서는 일반적으로 짧은 비밀값을 사용한다는 것입니다. 격자 방정식을 결합할 때(예: x+y 계산) "집계된" 비밀값의 길이는 증가합니다. 그러나 이러한 오류의 크기를 적절히 제어한다면 앞서 언급한 구조적 속성은 여전히 유지됩니다. 이는 격자가 양자 후 다중 서명, 영지식 증명, 기밀 자산과 같은 고급 프로토콜 개선을 가능하게 할 잠재력을 가지고 있음을 의미합니다.
격자 서명의 작동 방식: 벡터를 사용한 슈노르 기법
비트코인의 슈노르 서명을 이해할 수 있다면, 딜리튬 과 같은 격자 서명에 대해 50% 정도는 이해한 셈입니다. 이 가장 주류적인 격자 서명 방식은 우리가 농담 삼아 "벡터를 이용한 슈노르 방식"이라고 부르는 기술을 사용합니다.
전통적인 슈노르 서명에서 개인 키 x 사용한 서명 과정은 다음과 같습니다.
- 임의의 숫자
r을 선택하세요 - 이 숫자에 대한 "약속"을 만드세요.
- 약속과 서명할 데이터를 해시하여 임의의 챌린지 값
e - 이 챌린지 값을 사용하여 개인 키를 마스킹하고 최종 응답 값
z = r + xe생성합니다.
격자 기반 서명 방식에서는 행렬과 벡터를 사용하는 것 외에는 정확히 동일한 단계를 수행합니다. 방정식은 비슷하게 생겼습니다. 예를 들어, 격자 서명에 대한 초기 연구에서는 z = r + Se 방정식을 많이 사용했는데, 여기서 S 는 비밀 행렬, e 는 챌린지 벡터, r 은 임의 벡터입니다.
거부 샘플링*
여기에는 심각한 보안 문제가 있습니다. 양자 컴퓨터가 격자 방정식을 풀기 어렵게 하려면 벡터 z 와 r 의 숫자가 작아야 합니다(이것이 소위 " 짧은 정수 해법 " 문제입니다).
하지만 z = r + Se 로 계산하면 서명 z 와 그 뒤에 숨겨진 비밀 값 S 사이에 통계적 의존성이 생깁니다(슈노르 서명의 경우 r 과 e 임의적일 수 있으므로 이러한 의존성이 발생하지 않습니다). 공격자가 충분한 수의 서명을 수집할 수 있다면 이러한 통계적 편향을 알아차리고 개인 키를 알아낼 수 있을 것입니다.
이 문제를 해결하기 위해 격자 암호화는 "거부 샘플링을 사용한 피아트-샤미르 변환 "이라는 독창적인 기술을 사용합니다.
이 아이디어는 매우 간단합니다. 서명자가 서명 z 를 생성한 후, 먼저 개인 키를 추가했을 때 이 값에 상당한 변화가 발생하는지 확인합니다. 서명이 "편향"되어 개인 키를 노출할 가능성이 있는 경우(위 그림 참조), 해당 서명을 폐기하고 새로운 난수를 사용하여 다시 서명을 생성합니다. 이 과정은 최종 서명이 개인 키를 완벽하게 가릴 때까지(위 그림의 점선 참조) 여러 번 반복됩니다.
참고로 , 실제로 중간 Se 자체는 무작위 분포입니다. 하지만 원칙적으로는 차이가 없습니다. 분포의 오프셋은 숨겨진 비밀 값 S 에 대한 일부 정보를 드러내므로 오프셋을 제거해야 합니다(이는 또한 매우 간단하게 수행할 수 있음을 증명할 수 있기 때문입니다).
다음 단계
격자 기반 암호화는 심오한 주제이자 양자 후 암호화 분야에서 유망한 방향으로, 현재의 디지털 서명 체계를 단순히 대체하는 것을 훨씬 뛰어넘는 가능성을 제시합니다. 이는 비트코인의 양자 보안을 보장하는 수학적 기반을 제공하는 동시에, 더욱 효율적인 집계 및 임계값 체계로의 업그레이드 가능성도 품고 있습니다.
이산 가우스 함수, 최단 벡터 문제 및 거부 샘플링의 수학적 배경을 포함한 보다 심층적인 설명은 연구 보고서 전문 과 전체 비디오 데모를 참조하십시오.
(위에)
