양자 컴퓨팅 분야의 최신 개발로 인해 많은 사람들이 고전 암호화의 전망에 대해 걱정하게 되었습니다.12월 4일 중국 과학자들은 76개의 광자(큐비트)로 양자 컴퓨팅 프로토타입을 구축한 광학 양자 컴퓨터인 Jiuzhang을 성공적으로 검증했습니다. , 기존 암호화를 깨는 데 필요한 수천 개의 사용 가능한 큐비트에서 더 이상 멀지 않습니다. (속도면에서 보면 수학적 알고리즘 가우시안 보스 샘플링을 푸는 데 200초밖에 걸리지 않는 반면, 현재 슈퍼컴퓨터는 6억년이 걸린다. 일반적으로 50큐비트가 양자컴퓨터가 기존의 컴퓨터를 능가할 것으로 예상되는 핵심 임계값으로 여겨진다. 컴퓨터) .
미래에 양자컴퓨팅이 비약적으로 발전한다면 2031년까지 RSA와 ECC(타원암호화) 알고리즘이 깨질 확률은 50% 정도이며, 비트코인, 이더리움 등의 블록체인은 고전 외에도 암호학, Bitcoin은 이중 SHA256 알고리즘을 사용하여 은행 및 Alipay에서 사용하는 보안 시스템에 비해 추가 방어선이 있지만 여전히 다양한 공격 벡터가 있습니다.양자 컴퓨팅이 블록 체인의 발전이되고있는 것 같습니다 모클의 검, 앞으로 세상은 어떻게 될까? 양자 컴퓨터는 블록체인 비밀을 얻게 될까요?실제로 양자 컴퓨터를 사용하더라도 양자 보안 기술이 호황을 누리고 있다는 것은 말할 것도 없고 많은 고전적인 보안 알고리즘이 여전히 효과적일 것입니다. 블록체인 업계의 일부 연구자들도 관련 양자 저항 암호화 알고리즘을 지속적으로 연구하고 있으며, NIST는 빠르면 2017년부터 양자 저항 암호화 표준화 프로세스를 시작하여 2022년 이전에 양자 저항 암호화(양자 저항 암호화)를 준비하기를 희망합니다. 총 69개의 후보 알고리즘이 최소 승인 기준과 제출 요구 사항을 모두 충족했습니다. 엄격한 평가 기준과 선발 과정 때문에 3차 최종 후보와 후보 후보는 2020년 7월 22일까지 발표되지 않았습니다. 모두가 가장 낙관한 디지털 서명은 스위스 ABCMint Mathematical Algorithm에서 추진하는 반양자 서명입니다. Foundation.scheme은 Post-Quantum Encryption Foundation에서 지원하는 반양자 알고리즘 중 서명 길이가 가장 짧은 시그니처 반양자 서명 체계인 Rainbow 서명 Rainbow가 의심할 여지 없이 NIST 디지털 서명 목록의 세 번째 라운드에 진입했습니다.
국립 표준 기술 연구소(National Institute of Standards and Technology, NIST)는 높은 국제적 명성을 누리고 있습니다. NIST에는 노벨 물리학상을 수상한 4명의 연구원이 있습니다: William Daniel Phillips(1997), Eric Cornell(2001) , John Hall(2005) 및 David Vineland(2012)는 미국 정부 연구소에서 가장 많은 수혜자를 받았습니다.그 중 Rainbow는 서명 길이가 가장 작은 서명이고 Falcon과 Dilithium의 서명 길이는 매우 길며 선택된 Dilithium 3개는 크랙될 확률이 가장 높습니다.Falcon은 NTRU 아키텍처이고 NTRU는 약간 물이 새는 냄비. 수리를 하지만 항상 문제가 있습니다. Falcon은 가장 많은 사람들이 균열을 연구하고 포위하는 것입니다. 레인보우의 가장 큰 장점은 역사가 가장 길고, 크랙할 방법이 거의 없다고 인식되며, 시그니처가 가장 짧다는 것입니다. Rainbow는 NP-Hard 문제이며 허점을 찾기가 어렵습니다. 따라서 Rainbow는 디지털 통화가 미래에 오랫동안 채택할 수 있는 유일한 양자 저항 서명이어야 합니다.
그림: 세 가지 알고리즘의 공개 키 및 서명 크기 비교
Rainbow는 UOV(Unbalanced Oil-Gooseberry) 서명 체계를 기반으로 하는 계층 구조의 다변량 서명 체계입니다. Rainbow 계층에 의해 부과된 추가 구조는 체계를 더 많은 암호화 기술에 노출하지만 체계의 효율성을 높입니다. Rainbow는 빠른 서명 및 확인과 매우 짧은 서명을 제공하지만 매우 큰 공개 키를 사용합니다.Rainbow는 UOV(Unbalanced Oil-Gooseberry) 서명 체계를 기반으로 하는 계층 구조의 다변량 서명 체계입니다. Rainbow 계층에 의해 부과된 추가 구조는 체계를 더 많은 암호화 기술에 노출하지만 체계의 효율성을 높입니다. Rainbow는 빠른 서명 및 확인과 매우 짧은 서명을 제공하지만 매우 큰 공개 키를 사용합니다.Rainbow를 선택하면 선정된 서명 체계의 다양성이 증가하지만 키 크기가 매우 크기 때문에 Rainbow는 현재 FIPS 186-4에 나타나는 알고리즘을 대체하는 범용 서명 알고리즘으로 적합하지 않습니다. 특히 공개 키가 크면 인증서 체인이 매우 커집니다. 그러나 일부 애플리케이션은 키를 자주 보낼 필요가 없습니다. 이러한 응용 프로그램을 위해 Rainbow는 작고 빠른 서명을 제공합니다. 유사한 성능 특성을 가진 유일한 다른 고급 서명 후보인 GeMSS는 훨씬 더 큰 키를 가지고 있으며 매우 낮은 사양의 장치에서 구현하기 어려울 것 같습니다. 이러한 이유로 Rainbow가 최종 후보로 선정되었습니다.NIST 연구원들은 Rainbow 계획과 관련된 일부 공격 벡터의 성능과 이론적 복잡성 사이의 차이에 주목했습니다. 두 번째 라운드에서는 이러한 유명한 공격에 대한 좀 더 면밀한 이론적 분석(새로운 알고리즘과 함께)이 발표되었습니다. 특히 선언된 안전 수준을 달성하려면 모든 매개변수 세트에 대한 매개변수 조정이 필요합니다. 그러나 보다 보수적인 매개변수 선택을 통해 최소한의 성능 비용으로 선언된 안전 수준을 달성할 수 있어야 합니다.Rainbow를 표준화할 준비가 되기 전에 명시된 보안 목표를 충족하도록 해당 매개변수를 조정해야 합니다. 또한 NIST는 광범위한 채택을 장려하기 위해 로열티 없는 라이선스가 있는 알고리즘을 선호합니다.
# CRYSTALS-DILITHIUM #
DILITHIUM의 보안은 MLWE의 경도와 MSIS(Modular Short Integer Solution Problem)에 의존하며 Fiat-Shamir 및 중단 기술을 따릅니다. DILITHIUM은 균일 분포를 통해 모든 매개변수 세트 및 샘플에 대해 동일한 모듈러스 및 링을 사용하므로 주요 경쟁 제품인 FALCON보다 구현이 더 간단합니다.전반적으로 DILITHIUM은 키 및 서명 크기뿐만 아니라 키 생성, 서명 및 확인 알고리즘의 효율성에서 강력하고 균형 잡힌 성능을 제공합니다. DILITHIUM은 실제 실험에서 잘 수행되었습니다.두 번째 라운드에서 DILITHIUM은 서명을 비결정적으로 생성하는 옵션을 추가하고 하드웨어 지침의 향후 이점을 설명하기 위해 SHAKE 대신 AES를 사용하는 구현을 추가했습니다. 또한 DILITHIUM에 적용할 수 있는 QROM의 보안에 대한 새로운 연구가 발표되었습니다.NIST는 DILITHIUM 팀이 5개 범주 매개변수 세트를 추가하도록 권장했습니다. DILITHIUM의 CoreSVP 보안 강도 매개변수 세트는 아직 진행 중인 모든 그리드 체계 중 가장 낮기 때문에 특정 보안을 이해하려면 더 많은 연구가 필요합니다. NIST는 DILITHIUM을 결선 진출자로 선택했으며 DILITHIUM 또는 FALCON이 3차 라운드가 끝날 때까지 주요 포스트 양자 서명 체계로 표준화될 것으로 예상합니다.
# FALCON #
FALCON은 그리드 기반 서명 방식으로"해시 및 서명"어형 변화표. 보안은 NTRU 그리드의 SIS(Short Integer Solution) 문제의 난이도를 기반으로 하며, 랜덤 올림피아드 모델(ROM)과 QROM 모두에서 보안 증명을 제공하고 엄격한 축소를 수행합니다. FALCON의 구현은 DILITHIUM보다 더 복잡하여 트리와 같은 데이터 구조, 많은 부동 소수점 연산 및 여러 이산 가우시안 분포의 무작위 샘플링이 필요합니다.FALCON의 장점 중 하나는 모든 2차 디지털 서명 방식 중 가장 작은 대역폭(공개 키 크기 및 서명 크기)을 제공한다는 것입니다. FALCON은 키 생성 속도가 느리지만 서명 및 검증에도 효율적입니다. FALCON은 기존 프로토콜 및 애플리케이션에 쉽게 추가할 수 있으며 전반적으로 매우 우수한 성능을 제공합니다.두 번째 라운드가 시작될 때 FALCON은 범주 3 매개변수 세트를 제거하여 다양한 모듈러스 및 링 선택을 사용하여 사양 및 구현을 단순화했습니다. 두 번째 라운드 동안의 또 다른 주요 업데이트는 NIST의 두 번째 PQC 표준화 회의 직후에 발표된 일정 시간 구현이었습니다.세 번째 라운드에서 NIST는 FALCON 구현에 대한 더 많은 조사를 통해 부동 소수점 산술을 사용하는 것이 다른 체계보다 구현 오류에 더 취약한지 또는 부채널 공격의 수단을 제공하는지 여부를 결정하도록 권장했습니다. 또한 샘플러의 테스트 벡터를 사용할 수 있는 경우 임의 시드를 결정적으로 테스트하여 KAT(알려진 답변 테스트)를 사용하여 구현을 확인할 수 있습니다. 다른 여러 후보와 마찬가지로 FALCON의 범주 1 매개변수의 CoreSVP 보안 강도는 상대적으로 낮으므로 추가 연구가 필요합니다.
부록: Rainbow Signature 3차 결승 진출자 링크: https://groups.google.com/a/list.nist.gov/forum/m/#!topic/pqc-forum/0ieuPB-b8eg
