Lattice 암호동물학을 위한 Quantum of Solace? 격자암호학의 학술논쟁을 분석하는 데 도움이 될 글 한 편

블록체인의 양자 보안 위협과 대응

2024년 3월 10일, 이더리움 공동 창업자 비탈릭 부테린은 이더리움 연구 포럼(ethresear.ch)에 "대부분의 사용자 자금을 절약하기 위해 하드포크하는 방법"이라는 최신 기사를 게재했습니다. 양자 비상"[1] 기사에서는 이더리움 생태계가 직면한 양자 컴퓨팅 공격의 위협을 복원 포크 전략과 반양자 암호화 기술을 통해 사용자 자금의 보안을 보호하는 데 사용할 수 있다고 명시했습니다.

블록체인에 대한 양자 보안 위협은 정확히 무엇입니까?

양자 컴퓨팅[2]은 양자역학을 이용해 계산을 위한 양자 정보 단위를 제어하는 ​​새로운 컴퓨팅 모델입니다. 개념이 제안된 지 10년이 채 지나지 않아 양자 컴퓨터는 추상적인 이론 단계에 머물렀습니다. 1990년대 중반까지 양자 알고리즘에는 Shor의 알고리즘[3](다항식 시간의 큰 수 분해 및 이산 로그의 어려운 문제를 해결)과 Grover의 알고리즘[4](비정형 데이터에 대한 철저한 검색 제공)이 있었습니다. 2차 가속도 제안을 통해 양자 컴퓨팅은 추상적인 이론 단계를 뛰어넘어 현재 양자 컴퓨터라고 불리는 물리적 캐리어 연구 개발의 새로운 단계로 진입할 수 있게 되었습니다. 아래 그림은 1998년부터 2026년까지 양자 컴퓨터의 물리적 큐비트 개발 로드맵을 보여줍니다.

양자 컴퓨팅은 만병통치약이 아니며 모든 컴퓨팅 문제를 해결할 수는 없습니다. 현재는 시뮬레이션(자연에서 발생하는 프로세스 시뮬레이션, 화학 및 생물학 공학에 적합), 해독(가장 전통적인 암호화 시스템을 깨고 네트워크 보안에 적합), 최적화(실행 가능한 옵션 중에서 최적의 솔루션 찾기, 다음에 적합)에 사용될 수 있습니다. 금융, 공급망) 및 기타 특정 도메인 문제.

현재 블록체인이 광범위하게 적용되는 것은 서로 다른 요청 당사자 간의 협력에 새로운 신뢰 기반을 제공한다는 사실에서 비롯되며, 이 신뢰 기반은 기본 암호화에서 제공하는 보안 보장을 기반으로 합니다.

• 신뢰할 수 있는 신원 및 거래 권한 확인: 비대칭 공개 키와 개인 키 쌍을 기반으로 사용자가 신뢰할 수 있는 ID를 설정하고 ID 정보를 통합적으로 관리합니다. 디지털 자산의 소유권은 디지털 서명을 통해 확인되며, 유효한 서명이 있는 개인 키 보유자가 실제로 해당 자산을 소유하게 됩니다.

• 핵심 합의 및 운영 보안: 해시 함수, 임계값 서명, 검증 가능한 무작위 기능과 같은 최신 암호화 기술을 기반으로 합의 메커니즘을 구축하여 합의 메커니즘의 보안을 보장합니다.

• 개인 정보 보호 및 안전한 공유: 영지식 증명, 안전한 다자간 계산, 완전 동형 등 다양한 기능의 암호화 기술을 기반으로 개인 정보 보호 솔루션을 구축하여 블록체인에서 데이터를 안전하게 공유할 수 있습니다.

• 제어 가능한 감독 및 규정 준수 애플리케이션: 링 서명, 동형 암호화 체계, 숨겨진 주소 및 비밀 공유와 같은 암호화 기술을 통합 및 배포하여 블록체인 거래의 안전한 감독을 보장합니다.

공개 키 암호화의 사용은 크게 체인의 거래 변조를 방지하는 데 사용되는 디지털 서명 메커니즘과 노드 간 통신에 사용되는 보안 전송 프로토콜로 나눌 수 있습니다. Shor 알고리즘의 영향으로 위 공개 키 암호화의 보안을 효과적으로 보장할 수 없습니다. 암호해독 전용 양자컴퓨터가 대규모로 구현되기까지 걸리는 시간을 고려하는 동시에, 블록체인에 저장된 데이터를 얼마나 오래 보관해야 하는지, 기존 블록체인 시스템이 이를 완료하는 데 얼마나 오랜 시간이 걸릴지 고려하는 것도 중요하다. 양자 보안 수준으로 업그레이드됩니다. 후자의 두 배의 합이 전자보다 크면 블록체인의 데이터는 양자 컴퓨팅으로 인해 심각한 보안 위협을 받게 됩니다.

양자 컴퓨팅의 급속한 발전으로 인해 컴퓨팅 성능이 증가하는 현재 상황을 고려할 때, 현재 보안 위험에 효과적으로 대처할 수 있는 두 가지 주요 기술 접근 ​​방식이 있습니다.

1. 새로운 수학적 문제를 기반으로 하는 포스트 양자 암호화 물리적 장비를 사용하지 않고 [ 5] 기술 경로

2. 특수 물리적 장비를 사용하여 물리적 원리를 기반으로 하는 양자 암호화 [6] 기술 경로.

구현 검증 및 기타 요소와 같은 다양한 요소를 고려하여 장기적인 발전에 따른 블록체인의 보안을 보장하기 위해 기존 비밀번호의 보안과 호환된다는 전제하에 배포를 고려할 수 있습니다. 포스트퀀텀 암호화 마이그레이션을 통해 블록체인을 사전에 양자 안전 수준으로 업그레이드합니다. 이상적으로는 기존 블록체인에서 사용하는 공개 키 암호화 알고리즘을 양자 안전 포스트 양자 암호화 알고리즘으로 업그레이드하면 다음 특성을 최대한 만족해야 합니다.

• 키가 작고 서명이 짧습니다. 블록체인 각 거래에는 서명 정보가 포함되며, 거래를 확인하는 공개 키도 체인에 저장됩니다. 키와 서명의 크기가 너무 크면 블록체인의 저장 비용과 통신 오버헤드가 크게 증가합니다.

• 높은 계산 효율성: 블록체인이 각 기간에 처리할 수 있는 트랜잭션 수; 실행은 알고리즘, 특히 서명 검증 알고리즘의 실행 시간과 크게 관련됩니다. 알고리즘의 더 빠른 컴퓨팅 효율성은 고성능 블록체인 애플리케이션을 더 잘 지원할 수 있습니다.

포스트양자암호의 발전현황

포스트양자암호는 한 문장으로 표현하면 기존 암호알고리즘에 대한 양자컴퓨터 공격에 저항할 수 있는 1세대 암호알고리즘이다.

• 공개를 지향한다.

• 새로운 수학 문제에 따라 다름

• 특수 장비 지원이 필요하지 않음

• 클래식 컴퓨팅 및 양자 컴퓨팅 조건에서 안전함.

아래 그림에 표시된 대로 현재 5가지 주류 건설 기술 경로가 있습니다. 왼쪽부터 격자, 인코딩, 다변수, 해싱 및 상동성입니다.

1. 격자: 격자 기반 어려움 질문.

2. 인코딩: 디코딩 난이도를 기준으로 합니다.

3. 다변수: 유한 필드에 대한 다변수 2차 다항식 그룹의 난해성에 기초합니다.

4. Hash: 해시 함수를 기반으로 한 충돌 저항입니다.

5. 동일한 출처: 초특이 타원 곡선을 기반으로 한 의사 무작위 보행.

새로운 세대의 암호화 알고리즘에는 자연스럽게 표준 암호화 시스템의 확립이 수반됩니다. 포스트 양자 암호 표준에 관해 가장 주목할만한 점은 국립표준기술원(NTST)[7]의 포스트 양자 암호 표준화 프로젝트로, 2016년에 시작되어 이제 기본적으로 공식화 막바지에 접어들었습니다. 포스트퀀텀 암호화 표준화. 거의 10년에 걸친 표준화 일정을 되돌아보면 NIST는 4개의 양자 이후 암호화 표준 후보 알고리즘[8]을 다음과 같이 공식적으로 발표했습니다.

디지털 서명: CRYSTALS-Dilithium, SPHINCS+;
그 중 CRYSTALS-KYBER, CRYSTALS-Dilithium 및 FALCON은 모두 격자 암호화 알고리즘이지만 세 가지의 보안 기반은 다릅니다. 모듈형 격자의 어려운 MLWE 문제를 기반으로 하고, Dilithium은 모듈형 격자의 어려운 문제인 MLWE 및 MSIS를 기반으로 하며, FALCON은 NTRU 격자의 어려운 SIS 문제를 기반으로 하며, SPHINCS+는 무상태 해시 서명 알고리즘입니다.

• 2023년 8월 24일, CRYSTALS-KYBER, CRYSTALS-Dilithium 및 SPHINCS+가 각각 FIPS203, FIPS 204 및 FIPS205 표준 초안으로 구성되었습니다[9]. FALCON 표준 초안도 2024년에 발표될 예정입니다.

현재 NIST가 선정한 대부분의 표준 알고리즘이 격자 암호화라는 기술적 루트를 기반으로 하고 있다고 보는 것은 어렵지 않습니다. 하지만 NIST는 계란을 같은 바구니에 넣지 않습니다. 격자 구성 외에도 다양한 옵션을 적극적으로 찾고 있습니다. 2022년에 4가지 표준 알고리즘을 발표하는 동시에 4차 포스트 양자 암호화 표준 알고리즘 출시도 발표했습니다. 평가 작업, 이번 라운드에서는 공개 키 암호화/키 캡슐화 알고리즘에 중점을 두고 있으며 선택한 알고리즘은 격자 구조를 기반으로 하지 않습니다. 또한, 디지털 서명 알고리즘에 대한 새로운 모집 라운드도 시작되었습니다. 이번 모집은 4차 평가와 별도로 진행되므로 포스트 퀀텀 서명 알고리즘의 포트폴리오를 풍부하게 하는 것이 목표입니다. 알고리즘 구조가 다른 격자 기반 알고리즘으로, 작은 알고리즘 서명 크기와 빠른 검증 속도를 갖춘 새로운 제안입니다.

NIST 표준 외에도 IETF는 상태 저장 해시 서명 알고리즘 XMSS를 2018년과 2019년에 각각 RFC 8391[10]으로, LMS를 RFC 8554[11]로 표준화하여 NIST에서 승인했습니다.

격자 암호 해독을 위한 양자 알고리즘

2024년 4월 10일, Chen Yilei 교사의 eprint에 게재된 "격자 문제에 대한 양자 알고리즘"[12] 기사가 학계에 센세이션을 일으켰습니다. 이 논문은 격자의 어려운 문제를 해결하기 위한 다항식 시간 양자 알고리즘을 제공합니다. 이 알고리즘은 격자의 어려운 문제를 기반으로 하는 많은 암호화 방식에 큰 영향을 미치며 많은 알고리즘이 더 이상 양자 컴퓨터 공격에 저항할 수 없게 만들 수 있습니다. 예를 들어, 현재 널리 사용되는 LWE 가정 기반 동형암호 알고리즘입니다. 논문에 있는 알고리즘의 정확성은 아직 알려지지 않았습니다.

LWE 문제의 난이도는 Oded Regev가 "On lattices, learning with error, Random Linear Codes, and cryptography"[13]라는 논문에서 엄격하게 시연했습니다. 특히 저자는 LWE 문제의 난이도를 다음에서 설명했습니다. 논문에서는 난이도가 격자의 이산 가우스 샘플링 문제로 줄어들고 이산 가우스 샘플링 문제는 GapSVP, SIVP와 같은 고전적인 문제로 쉽게 줄어들 수 있습니다. 물론 각 특정 문제에는 무시되는 특정 매개변수가 있습니다. 여기) LWE 문제가 이러한 고전적인 격자 문제보다 더 어렵다는 것을 보여주세요. LWE 문제의 난이도가 엄격하게 감소된 이후에는 단순한 구조로 인해 (동형) 암호화, 서명, 키 교환과 같은 기본적인 암호화 기본 요소를 다루는 LWE를 기반으로 한 수많은 암호화 방식이 뒤따랐습니다. ID 기반 암호화 및 속성 암호화와 같은 고급 암호화 기본 요소입니다. 그 중 업계에서 널리 사용되고 있는 것은 위에서 언급한 NIST에서 발표한 완전동형암호와 포스트양자표준알고리즘(KYBER, Dilithium 등)이 주로 사용된다.

요약

논문이 공개된 후 학계에 큰 반향을 일으켰고 많은 전문가들 사이에서 논의가 촉발되었습니다. 그러나 논문의 이해가 극도로 어렵기 때문에 논문의 내용을 완전히 이해할 수 있는 학자는 전 세계적으로 5명 미만일 수 있으며, 논문의 정확성을 완전히 검증하는 데는 1~2년이 걸릴 수 있습니다. 현재 많은 사람들이 일부 포럼, 공개 계정, Zhihu 및 기타 플랫폼에서 관련 의견을 표명했습니다. 논문의 알고리즘이 올바른지 모두가 그 영향을 분석하고 있습니다. 아직 결론을 내릴 수는 없습니다. 그중 유명한 암호학자 N. P. Smart는 블로그 기사 "LWE에 대한 제안된 양자 공격의 의미"[14]를 게시했는데, 이 기사는 이 공격의 영향과 몇 가지 의견을 자세히 설명하며 다음과 같이 요약됩니다.

• 이 논문은 아직 승인되지 않았습니다. 동료 검토는 올바른 것으로 입증되더라도 양자 컴퓨터에 의존하므로 양자 컴퓨터를 아직 사용할 수 없는 한 현재 사용 중인 암호화 체계에 영향을 미치지 않습니다.

• 논문에 제시된 결과에 따르면 이전에 NIST가 제공한 Kyber 및 Dilithium 표준화 알고리즘을 깨는 것은 여전히 ​​불가능하지만 NIST는 이러한 알고리즘의 매개변수를 재평가할 수 있습니다.

• BFV/CKKS/BGV와 같이 일반적으로 사용되는 RLWE 동형 암호화 알고리즘의 경우 이러한 알고리즘은 이 문서의 공격 기능 내에 있습니다. 그러나 학계나 산업계의 관점에서 볼 때 동형암호 기술의 "동형"은 "양자 저항"보다 더 매력적이며 "최첨단 양자 저항"을 추구하기 위해 RLWE를 사용하는 사람은 거의 없습니다. 타원 곡선을 기반으로 한 암호화 방식과 같은 암호화 알고리즘은 이산 로그 난제에 의존하며, 이 문제를 해결하기 위한 양자 알고리즘은 아주 일찍부터 제안되었지만 학계와 업계에서는 여전히 이러한 방식을 연구하고 사용하고 있습니다.

최신 소식: 첸 선생님의 논문 계산에 문제가 있어 그리드 비밀번호 알람이 일시적으로 해제되었습니다.

[1] https://ethresear.ch/t/how-to-hard-fork-to-save-most-users-funds-in-a-퀀텀-emergency/18901/ 9

[2] Benioff P. 물리적 시스템으로서의 컴퓨터: 튜링 기계로 대표되는 컴퓨터의 미세한 양자 역학 해밀턴 모델[J] Journal of StatisticalPhysics, 1980, 22: 563-591.

[ 3] Shor P W. 양자 계산을 위한 알고리즘: 이산 로그 및 인수분해[C]//Proceedings 35th Annual Symposium on Foundations of Computer Science, 1994: 124-134.

[4] Grover L K. 빠른 양자 데이터베이스 검색을 위한 기계적 알고리즘[C]//1996년 제28회 연례 ACM 심포지엄 진행: 212-219.

[5] Bernstein, D.J.(2009). : Bernstein, D.J., Buchmann, J., Dahmen, E. (eds) 포스트 양자 암호화. Springer, Berlin, Heidelberg.

[6] Gisin N, Ribordy G, Tittel W, et al. . 현대 물리학 리뷰, 2002, 74(1): 145.

[7]https://csrc.nist.gov/Projects/post-퀀텀-cryptography/post-퀀텀-cryptography-standardization

[ 8]https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4

[9]https://csrc.nist.gov/News /2023/3-draft-fips-for-post-퀀텀-암호화

[10] Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J. 및 A. Mohaisen, "XMSS: eXtended Merkle Signature Scheme", RFC 8391, DOI 10.17487/RFC8391, 2018년 5월, https://www.rfc-editor.org/info/rfc8391>.

[11] McGrew, D., Curcio , M., S. Fluhrer, "Leighton-Micali 해시 기반 서명", RFC 8554, DOI 10.17487/RFC8554, 2019년 4월, https://www.rfc-editor.org/info/rfc8554> ;.

[12] Chen Y. 격자 문제에 대한 양자 알고리즘[J]. 암호화 ePrint 아카이브, 2024.

[13] Regev O. 격자에 대해 오류, 무작위 선형 코드 및 암호화 학습[J]. Journal of the ACM (JACM), 2009, 56(6): 1-40.

[14]https://nigelsmart.github.io/LWE.html

이 기사는 ZAN 팀( X 계정 @ zan_team의 Dongni와 Jiaxing이 공동 작성했습니다.

위 내용은 Lattice 암호동물학을 위한 Quantum of Solace? 격자암호학의 학술논쟁을 분석하는 데 도움이 될 글 한 편의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!