암호학 에서 PQC( post-quantum cryptography )

cloudhwang Quantum 0 73 2023.06.10 17:06

암호학 에서 PQC( post-quantum cryptography )(때때로 양자 증명 , 양자 안전 또는 양자 저항 이라고도 함 )는 암호 분석 공격 에 대해 안전하다고 생각되는 암호화 알고리즘(일반적으로 공개 키 알고리즘) 을 나타냅니다. 양자 컴퓨터 . 현재 널리 사용되는 알고리즘의 문제는 보안이 정수 분해 문제 , 이산 로그 문제 또는 타원 곡선 이산 로그 문제의 세 가지 어려운 수학 문제 중 하나에 의존한다는 것입니다.. 이러한 모든 문제는 Shor의 알고리즘을 실행하는 충분히 강력한 양자 컴퓨터에서 쉽게 해결할 수 있습니다 .

현재의 양자 컴퓨터는 실제 암호화 알고리즘을 깰 수 있는 처리 능력이 부족하지만 [3] 많은 암호 작성자는 양자 컴퓨팅이 위협이 되는 시기에 대비하기 위해 새로운 알고리즘을 설계하고 있습니다. 이 작업은 2006년부터 PQCrypto 컨퍼런스 시리즈를 통해 학계와 업계에서 더 큰 주목을 받았으며 최근에는 ETSI( European Telecommunications Standards Institute )와 Institute for Quantum Computing 에서 주최하는 양자 안전 암호화에 대한 여러 워크숍에서 주목을 받았습니다 . [4] [5] [6] 현재 널리 알려진 수확의 존재 , 나중에 해독프로그램은 또한 현재 기록된 데이터가 향후 몇 년 동안 여전히 민감한 상태로 남아 있을 수 있기 때문에 포스트 양자 알고리즘의 초기 도입에 대한 동기로 여겨져 왔습니다.

양자 컴퓨팅이 현재의 공개 키 알고리즘에 가하는 위협과 달리, 대부분의 최신 대칭 암호화 알고리즘 및 해시 함수는 양자 컴퓨터의 공격에 대해 상대적으로 안전한 것으로 간주됩니다. [2] [9] 양자 Grover의 알고리즘은 대칭 암호에 대한 공격 속도를 높이는 반면 키 크기를 두 배로 늘리면 이러한 공격을 효과적으로 차단할 수 있습니다. 따라서 포스트양자 대칭 암호는 현재의 대칭 암호와 크게 다를 필요가 없습니다.

알고리즘

현재 포스트 양자 암호 연구는 주로 다음과 같은 6가지 접근 방식에 초점을 맞추고 있습니다. [2] [5]

격자 기반 암호화

이 부분의 본문은 격자 기반 암호화입니다.

이 접근 방식에는 오류가 있는 학습 , 오류가 있는 링 학습 ( ring-LWE ), [11] [12] [13] 오류 키 교환이 있는 링 학습 및 오류 서명이 있는 링 학습 , 이전 NTRU 또는 GGH 와 같은 암호화 시스템이 포함됩니다. 암호화 체계, 최신 NTRU 서명 및 BLISS 서명 . [14] NTRU 암호화와 같은 이러한 체계 중 일부는 실행 가능한 공격을 찾지 못한 채 수년 동안 연구되었습니다. ring-LWE 알고리즘과 같은 다른 알고리즘은 보안이 최악의 경우 문제로 감소한다는 증거를 가지고 있습니다.[15] 유럽 위원회가 후원하는 Post Quantum Cryptography Study Group은 NTRU 알고리즘보다 표준화를 위해 NTRU의 Stehle-Steinfeld 변종을 연구할 것을 제안했습니다. [16] [17] 그 당시 NTRU는 여전히 특허를 받았습니다. 연구에 따르면 NTRU는 다른 격자 기반 알고리즘보다 더 안전한 속성을 가질 수 있습니다. [18]

다변량 암호화

이 부분의 본문은 다변수 암호화입니다.

여기에는 다변량 방정식 시스템을 푸는 어려움을 기반으로 하는 Rainbow( Unbalanced Oil and Vinegar ) 체계와 같은 암호화 시스템이 포함됩니다. 안전한 다변량 방정식 암호화 체계를 구축하려는 다양한 시도가 실패했습니다. 그러나 Rainbow와 같은 다변량 서명 체계는 양자 보안 디지털 서명의 기반을 제공할 수 있습니다. [19] Rainbow Signature Scheme에 대한 특허가 있습니다.

해시 기반 암호화

이 부분의 본문은 해시 기반 암호화입니다.

여기에는 Lamport 서명 , Merkle 서명 체계 , XMSS, [20] SPHINCS, [21] 및 WOTS 체계와 같은 암호화 시스템이 포함됩니다 . 해시 기반 디지털 서명은 1970년대 후반 Ralph Merkle 이 발명했습니다.RSA 및 DSA와 같은 숫자 이론 디지털 서명에 대한 흥미로운 대안으로 그 이후로 연구되었습니다. 주요 단점은 모든 해시 기반 공개 키의 경우 해당 개인 키 집합을 사용하여 서명할 수 있는 서명 수에 제한이 있다는 것입니다. 이 사실은 양자 컴퓨터의 공격에 저항하는 암호화에 대한 욕구로 인해 관심이 되살아날 때까지 이러한 서명에 대한 관심을 줄였습니다. Merkle 서명 체계 [ 인용 필요 ] 에 대한 특허가 없는 것으로 보이며 이러한 체계와 함께 사용할 수 있는 특허되지 않은 해시 함수가 많이 있습니다. Johannes Buchmann 의 지도 아래 연구팀이 개발한 상태 저장 해시 기반 서명 체계 XMSSRFC 8391에 설명되어 있습니다. [22] 위의 모든 체계는 일회성 또는 제한된 시간 서명이며 Moni Naor 와 Moti Yung은 1989년에 UOWHF 해싱을 발명 하고 해싱을 기반으로 서명을 설계했습니다(Naor-Yung 체계) [ 23] 무제한으로 사용할 수 있습니다(트랩도어 속성이 필요하지 않은 최초의 서명).

코드 기반 암호화

여기에는 McEliece 및 Niederreiter 암호화 알고리즘 및 관련 Courtois, Finiasz 및 Sendrier 서명 체계 와 같은 오류 수정 코드 에 의존하는 암호화 시스템이 포함됩니다 . 임의의 Goppa 코드를 사용하는 원래 McEliece 서명은 40년 이상 면밀한 조사를 견뎌왔습니다. 그러나 키 크기를 줄이기 위해 사용되는 코드에 더 많은 구조를 도입하려는 McEliece 체계의 많은 변종은 안전하지 않은 것으로 나타났습니다. [24] 유럽 위원회(European Commission)가 후원하는 Post Quantum Cryptography Study Group은 McEliece 공개 키 암호화 시스템을 양자 컴퓨터 공격에 대한 장기 보호 후보로 추천했습니다. [16]

초특이점 타원곡선 동질성 암호

이 부분의 본문은 초특이 이소제니 키 교환입니다.

이 암호화 시스템은 초특이 타원 곡선 과 초특이 등위 그래프 의 속성에 의존하여 순방향 보안 으로 Diffie-Hellman 대체를 생성합니다 . [25] 이 암호화 시스템은 Diffie-Hellman 및 타원 곡선 Diffie-Hellman 키 교환 방법 에 대한 간단한 양자 컴퓨팅 내성 대체품 역할을 할 수 있는 Diffie -Hellman 유사 키 교환 을 생성하기 위해 잘 연구된 초특이 타원 곡선의 수학을 사용합니다. 오늘날 널리 사용됩니다. 기존 Diffie–Hellman 구현과 매우 유사하게 작동하기 때문에 대량 감시를 방지하는 데 중요한 것으로 간주되는 순방향 비밀성을 제공합니다.실패로 인한 장기 키의 손상으로부터 보호합니다. [26] 2012년에 통합 서비스 네트워크를 위한 중국 국가 키 연구소와 Xidian University의 Sun, Tian 및 Wang 연구원은 De Feo, Jao 및 Plut의 작업을 확장하여 초특이 타원 곡선 동질성을 기반으로 양자 보안 디지털 서명을 생성했습니다. [27] 이 암호화 시스템을 다루는 특허는 없습니다.

대칭 키 양자 저항

충분히 큰 키 크기를 사용한다면 AES 및 SNOW 3G 와 같은 대칭 키 암호화 시스템은 이미 양자 컴퓨터의 공격에 저항할 수 있습니다. 또한 Kerberos 및 3GPP 모바일 네트워크 인증 구조 와 같은 공개 키 암호화 대신 대칭 키 암호화를 사용하는 키 관리 시스템 및 프로토콜 도 본질적으로 양자 컴퓨터의 공격에 대해 안전합니다. 이미 전 세계에 널리 배포되어 있는 점을 감안할 때 일부 연구원은 오늘날 포스트 양자 암호화를 얻는 효율적인 방법으로 Kerberos와 같은 대칭 키 관리를 확장하여 사용할 것을 권장합니다. [29]

보안 축소

암호 연구에서는 암호 알고리즘과 알려진 어려운 수학적 문제의 동등성을 증명하는 것이 바람직합니다. 이러한 증명은 종종 "보안 감소"라고 하며 암호화 알고리즘 크래킹의 어려움을 입증하는 데 사용됩니다. 즉, 주어진 암호화 알고리즘의 보안은 알려진 어려운 문제의 보안으로 축소됩니다. 연구원들은 포스트 양자 암호화에 대한 전망에서 보안 감소를 적극적으로 찾고 있습니다. 현재 결과는 다음과 같습니다.

격자 기반 암호화 – Ring-LWE 서명

추가 정보: 오류 키 교환을 사용한 링 학습

Ring-LWE 의 일부 버전에서는 격자의 SVP(Shortest-Vector Problem) 에 대한 보안 감소가 보안의 하한값으로 존재합니다 . SVP는 NP-hard 로 알려져 있습니다 . [30] 입증 가능한 보안 감소가 있는 특정 링-LWE 시스템에는 Güneysu, Lyubashevsky 및 Pöppelmann의 논문에 정의된 Lyubashevsky의 링-LWE 서명의 변형이 포함됩니다. [12] GLYPH 서명 체계는 GLP (Güneysu, Lyubashevsky 및 Pöppelmann) 서명 의 변형으로 2012년 GLP 서명이 발표된 이후에 나온 연구 결과를 고려합니다. 또 다른 Ring-LWE 서명은 Ring-TESLA입니다. . [31]또한 LWR(Learning with Rounding)이라고 하는 LWE의 "무작위화된 변형"이 존재하며, "향상된 속도 향상(결정론적 오류가 있는 가우시안과 같은 분포에서 샘플링 작은 오류를 제거하여) 및 대역폭"을 제공합니다. LWE는 작은 오류를 추가하여 하위 비트를 숨기는 반면 LWR은 같은 목적으로 반올림을 사용합니다 .

격자 기반 암호 – NTRU, BLISS

NTRU 암호화 체계와 BLISS [14] 서명 의 보안 은 격자 의 CVP(가장 가까운 벡터 문제)와 관련이 있지만 증명할 수는 없는 것으로 여겨집니다 . CVP는 NP-hard 로 알려져 있습니다 . 유럽 위원회가 후원하는 Post Quantum Cryptography Study Group 은 원래 NTRU 알고리즘 대신 장기간 사용을 위해 보안 감소가 있는 NTRU의 Stehle–Steinfeld 변형을 연구할 것을 제안 했습니다 . [16]

다변량 암호화 – 불균형 오일과 식초

추가 정보: 다변량 암호화

불균형 오일 및 식초 서명 체계는 유한 필드 에 대한 다변량 다항식을 기반으로 하는 비대칭 암호화 프리미티브입니다. {\displaystyle \mathbb {F} }\mathbb {F}. Bulygin, Petzoldt 및 Buchmann은 일반 다변량 2차 UOV 시스템을 NP-Hard 다변량 2차 방정식 풀이 문제 로 축소하는 것을 보여주었습니다 . [33]

해시 기반 암호화 – Merkle 서명 체계

추가 정보: 해시 기반 암호화 및 Merkle 서명 체계

2005년 Luis Garcia는 기본 해시 함수의 보안에 대한 Merkle Hash Tree 서명 의 보안 감소가 있음을 증명했습니다 . Garcia는 자신의 논문에서 계산적으로 단방향 해시 함수가 존재한다면 Merkle Hash Tree 서명이 안전함을 입증할 수 있음을 보여주었습니다. [34]

따라서 알려진 어려운 문제에 대한 입증 가능한 보안 감소와 함께 해시 함수를 사용하는 경우 알려진 어려운 문제에 대한 Merkle 트리 서명 의 입증 가능한 보안 감소를 갖게 됩니다 . [35]

유럽 위원회가 후원하는 Post Quantum Cryptography Study Group은 양자 컴퓨터에 대한 장기적인 보안 보호를 위해 Merkle 서명 체계를 사용할 것을 권장했습니다. [16]

코드 기반 암호화 – McEliece

추가 정보: McEliece 암호 시스템

McEliece 암호화 시스템은 Syndrome Decoding Problem(SDP)에 대한 보안 감소가 있습니다. SDP는 NP-hard 로 알려져 있습니다. [36] 유럽 위원회가 후원하는 Post Quantum Cryptography Study Group은 양자 컴퓨터의 공격에 대한 장기적인 보호를 위해 이 암호화를 사용할 것을 권장했습니다. [16]

코드 기반 암호화 – RLCE

2016년에 Wang은 McEliece 방식을 기반으로 하는 무작위 선형 코드 암호화 방식 RLCE [37] 를 제안했습니다. RLCE 체계는 기본 선형 코드 생성기 행렬에 임의의 열을 삽입하여 리드 솔로몬 코드와 같은 선형 코드를 사용하여 구성할 수 있습니다.

초특이점 타원곡선 동질성 암호

추가 정보: Supersingular isogeny 키 교환

보안은 동일한 수의 점을 가진 두 개의 초특이 곡선 사이에 isogeny를 구성하는 문제와 관련이 있습니다. 이 문제의 난이도에 대한 가장 최근의 조사는 Delfs와 Galbraith가 이 문제가 키 교환의 발명가가 제안한 것만큼 어렵다는 것을 나타냅니다. 알려진 NP-hard 문제에 대한 보안 감소는 없습니다 .

비교

많은 포스트 퀀텀 암호화 알고리즘의 공통된 특징 중 하나는 일반적으로 사용되는 "프리 퀀텀" 공개 키 알고리즘보다 더 큰 키 크기가 필요하다는 것입니다. 종종 키 크기, 계산 효율성 및 암호문 또는 서명 크기에서 절충이 이루어집니다. 표에는 128비트 사후 양자 보안 수준에서 다양한 체계에 대한 일부 값이 나열되어 있습니다.

연산 유형 공개 키 개인 키 서명

NTRU 암호화 [39] 격자 766.25 비 842.875 비

간소화된 NTRU Prime [ 인용 필요 ] 격자 154B _

레인보우 [40] 다변량 124KB 95KB

스핑크스 [21] 해시 서명 1KB 1KB 41KB

스핑크스+ [41] 해시 서명 32B _ 64B _ 8KB

블리스 -II 격자 7KB 2KB 5KB

GLP-변형 GLYPH 서명 [12] [42] 링-LWE 2KB 0.4KB 1.8KB

새로운 희망 [43] 링-LWE 2KB 2KB

Goppa 기반 McEliece [16] 코드 기반 1MB 11.5KB

무작위 선형 코드 기반 암호화 [44] RLCE 115KB 3KB

준순환 MDPC 기반 McEliece [45] 코드 기반 1,232B _ 2,464B _

예 [46] 동원 564B _ 48B _

SIDH(압축 키) [47] 동원 330B _ 48B _

3072비트 이산 로그 PQC가 아닌 384B _ 32B _ 96B _

256비트 타원 곡선 PQC가 아닌 32B _ 32B _ 65B _

포스트 퀀텀 암호화 알고리즘 중 선택에 대한 실질적인 고려 사항은 인터넷을 통해 공개 키를 보내는 데 필요한 노력입니다. 이러한 관점에서 Ring-LWE, NTRU 및 SIDH 알고리즘은 1KB 미만의 키 크기를 편리하게 제공하고 해시 서명 공개 키는 5KB 미만으로 제공되며 MDPC 기반 McEliece는 약 1KB를 차지합니다. 반면에 Rainbow 체계는 약 125KB가 필요하고 Goppa 기반 McEliece는 거의 1MB 키가 필요합니다.

격자 기반 암호화 – LWE 키 교환 및 Ring-LWE 키 교환

추가 정보: 오류 키 교환을 사용한 링 학습

키 교환을 위해 LWE 및 Ring LWE를 사용하는 기본 아이디어는 Jintai Ding이 2011년 신시내티 대학교에서 제안하고 제출했습니다. 기본 아이디어는 행렬 곱셈의 연관성에서 비롯되며 오류는 보안을 제공하는 데 사용됩니다. 이 논문 [48] 은 2012년 임시 특허 출원이 제출된 후 2012년에 등장했습니다.

2014년 Peikert [49] 는 Ding의 기본 아이디어를 따르는 키 전송 방식을 제시했는데, Ding의 구성에서 반올림을 위해 추가로 1비트 신호를 보내는 새로운 아이디어도 활용되었습니다. 128비트 이상의 보안을 위해 Singh은 Peikert의 체계에 대한 6956비트 공개 키가 있는 매개변수 세트를 제공합니다. 해당 개인 키는 대략 14,000비트입니다.

2015년 Ding의 동일한 기본 아이디어를 따르는 순방향 보안이 입증된 인증된 키 교환이 Crypto2005의 HMQV [52] 구성 의 확장인 Eurocrypt 2015 [51] 에서 발표되었습니다 . 해당 키 크기와 함께 80비트에서 350비트까지 다양한 보안 수준에 대한 매개변수가 백서에 제공됩니다. [51]

격자 기반 암호화 – NTRU 암호화

추가 정보: NTRUEncrypt

NTRU, Hirschhorn, Hoffstein, Howgrave-Graham 및 Whyte의 128비트 보안을 위해 계수가 포함된 613도 다항식으로 표시되는 공개 키를 사용하는 것이 좋습니다.{\displaystyle {\by {\left(2^{10}\right)}}}{\by {\left(2^{10}\right)}}. 결과적으로 6130비트의 공개 키가 생성됩니다. 해당 개인 키는 6743비트입니다. [39]

다변량 암호화 - 레인보우 서명

추가 정보: 다변량 암호화

128비트의 보안과 Rainbow 다변량 2차 방정식 서명 체계에서 가장 작은 서명 크기를 위해 Petzoldt, Bulygin 및 Buchmann은 다음 방정식을 사용하도록 권장합니다.{\displaystyle \mathbb {F} _{31}}\mathbb {F} _{31}공개 키 크기는 991,000비트가 조금 넘고 개인 키는 740,000비트가 조금 넘고 디지털 서명은 길이가 424비트입니다. [40]

해시 기반 암호화 – Merkle 서명 체계

추가 정보: 해시 기반 암호화 및 Merkle 서명 체계

Naor Shenhav 및 Wool의 프랙탈 머클 트리 방법을 사용하여 1백만 개의 메시지에 서명하기 위해 해시 기반 서명에 대해 128비트의 보안을 확보하기 위해 공개 및 개인 키 크기는 대략 36,000비트 길이입니다. [53]

코드 기반 암호화 – McEliece

추가 정보: McEliece 암호 시스템

McEliece 방식의 128비트 보안을 위해 유럽 위원회 Post Quantum Cryptography Study 그룹은 적어도 길이의 이진 Goppa 코드를 사용할 것을 권장합니다.{\displaystyle n=6960}{\displaystyle n=6960}최소 치수{\displaystyle k=5413}{\displaystyle k=5413}, 수정 가능{\디스플레이스타일 t=119}{\디스플레이스타일 t=119}오류. 이러한 매개변수를 사용하여 McEliece 시스템의 공개 키는 비식별 부분이{\displaystyle k\times (nk)=8373911}k\times (nk)=8373911비트. 코드 지원으로 구성된 해당 개인 키{\displaystyle n=6960}{\displaystyle n=6960}요소{\디스플레이스타일 GF(2^{13})}{\디스플레이스타일 GF(2^{13})}및 다음과 같은 생성기 다항식{\디스플레이스타일 t=119}{\디스플레이스타일 t=119}계수{\디스플레이스타일 GF(2^{13})}{\디스플레이스타일 GF(2^{13})}, 길이는 92,027비트 [16]

그룹은 또한 적어도 길이의 준순환 MDPC 코드의 사용을 조사하고 있습니다.{\displaystyle n=2^{16}+6=65542}n=2^{16}+6=65542최소 치수{\displaystyle k=2^{15}+3=32771}{\displaystyle k=2^{15}+3=32771}, 수정 가능{\디스플레이스타일 t=264}{\디스플레이스타일 t=264}오류. 이러한 매개변수를 사용하면 McEliece 시스템의 공개 키는 비식별 부분이 걸리는 체계적 생성기 행렬의 첫 번째 행이 됩니다.{\displaystyle k=32771}{\displaystyle k=32771}비트. 개인 키, 준순환 패리티 검사 행렬{\displaystyle d=274}{\displaystyle d=274}열에 0이 아닌 항목(또는 행에 2배)은{\displaystyle d\times 16=4384}{\displaystyle d\times 16=4384}첫 번째 행에서 0이 아닌 항목의 좌표로 표시될 때 비트입니다.

Barretoet al. 최소한 길이의 이진 Goppa 코드를 사용하는 것이 좋습니다.{\displaystyle n=3307}{\displaystyle n=3307}최소 치수{\displaystyle k=2515}{\displaystyle k=2515}, 수정 가능{\디스플레이스타일 t=66}{\디스플레이스타일 t=66}오류. 이러한 매개변수를 사용하여 McEliece 시스템의 공개 키는 비식별 부분이{\displaystyle k\times (nk)=1991880}{\displaystyle k\times (nk)=1991880}비트. [54] 코드 지원으로 구성된 해당 개인 키{\displaystyle n=3307}{\displaystyle n=3307}요소{\디스플레이스타일 GF(2^{12})}{\디스플레이스타일 GF(2^{12})}및 다음과 같은 생성기 다항식{\디스플레이스타일 t=66}{\디스플레이스타일 t=66}계수{\디스플레이스타일 GF(2^{12})}{\디스플레이스타일 GF(2^{12})}, 길이는 40,476비트입니다.

초특이점 타원곡선 동질성 암호

추가 정보: Supersingular isogeny 키 교환

SIDH(Supersingular isogeny Diffie-Hellman) 방법의 128비트 보안을 위해 De Feo, Jao 및 Plut는 768비트 프라임 모듈로의 초특이 곡선을 사용할 것을 권장합니다. 타원 곡선 점 압축을 사용하는 경우 공개 키의 길이는 8x768 또는 6144비트를 넘지 않아야 합니다. [55] 저자 Azarderakhsh, Jao, Kalach, Koziel 및 Leonardi의 2016년 3월 논문은 전송되는 비트 수를 절반으로 줄이는 방법을 보여 주었으며, 이는 Costello, Jao, Longa, Naehrig, Renes 및 Urbanik 저자에 의해 더욱 개선되어 결과적으로 크기가 2640비트에 불과한 공개 키가 있는 SIDH 프로토콜의 압축 키 버전. [47] 이는 동일한 고전적 보안 수준에서 비양자 보안 RSA 및 Diffie-Hellman과 거의 동일한 전송 비트 수를 만듭니다. [56]

대칭 키 기반 암호화

일반적으로 대칭 키 기반 시스템에서 128비트의 보안을 위해 256비트의 키 크기를 안전하게 사용할 수 있습니다. 일반적인 대칭 키 시스템에 대한 최고의 양자 공격 은 키 공간 크기의 제곱근에 비례하는 작업을 필요로 하는 Grover 알고리즘 의 적용입니다 . 해당 키를 해독하는 데 필요한 대칭 키를 소유한 장치에 암호화된 키를 전송하려면 대략 256비트도 필요합니다. 대칭 키 시스템이 포스트 퀀텀 암호화를 위한 가장 작은 키 크기를 제공한다는 것은 분명합니다.

순방향 비밀성

공개 키 시스템은 키 합의를 위해 세션당 임의의 공개 키를 생성할 때 완전 순방향 보안 이라고 하는 속성을 보여줍니다. 즉, 한 메시지의 침해가 다른 메시지의 침해로 이어질 수 없으며, 여러 메시지의 침해로 이어질 수 있는 하나의 비밀 값도 없다는 의미입니다. 보안 전문가들은 순방향 비밀성을 지원하지 않는 것보다 지원하는 암호화 알고리즘을 사용할 것을 권장합니다. 그 이유는 순방향 보안이 공개/개인 키 쌍과 관련된 장기 개인 키의 손상을 방지할 수 있기 때문입니다. 정보기관의 집단 사찰을 막는 수단으로 풀이된다.

Ring-LWE 키 교환과 SIDH(초특수 동질성 Diffie-Hellman) 키 교환은 모두 상대방과의 한 교환에서 순방향 비밀성을 지원할 수 있습니다. Ring-LWE와 SIDH는 모두 Diffie-Hellman의 고전적인 ElGamal 암호화 변형의 변형을 생성하여 순방향 비밀성 없이 사용할 수 있습니다.

NTRU와 같은 이 문서의 다른 알고리즘은 순방향 보안을 그대로 지원하지 않습니다.

모든 인증된 공개 키 암호화 시스템을 사용하여 순방향 비밀성 키 교환을 구축할 수 있습니다. [58]

Quantum Safe 프로젝트 열기

OQS ( Open Quantum Safe ) 프로젝트는 2016년 말에 시작되었으며 양자 저항 암호화를 개발하고 프로토타이핑하는 것을 목표로 합니다. [59] [60] 현재의 양자 이후 체계를 하나의 라이브러리인 liboqs 에 통합하는 것을 목표로 합니다 . [61] liboqs는 오픈 소스 C 입니다.양자 저항 암호화 알고리즘을 위한 라이브러리. 처음에는 키 교환 알고리즘에 중점을 두었지만 지금은 여러 서명 체계를 포함합니다. 포스트 퀀텀 키 교환 알고리즘에 적합한 공통 API를 제공하며 다양한 구현을 함께 모을 것입니다. liboqs에는 포스트 퀀텀 구현의 성능을 비교하기 위한 테스트 도구와 벤치마킹 루틴도 포함됩니다. 또한 OQS는 liboq를 OpenSSL 에 통합합니다 . [62]

2023년 3월부터 다음 키 교환 알고리즘이 지원됩니다. [59]

연산 유형

CRYSTALS-카이버 오류가 있는 모듈 학습

클래식 매컬리스 고파 코드

자전거 코드

본사 코드

프로도 [63] 오류가 있는 학습

NTRU [64] 격자 기반 암호화

CRYSTALS-Dilithium 최단 정수 솔루션

매 최단 정수 솔루션

스핑크스+ 해시 기반

NIST Post-Quantum Cryptography Standardization Project의 진행으로 인해 제거된 이전 지원 버전은 다음과 같습니다.

연산 유형

BCNS15 [65] 오류가 있는 링 학습 키 교환

새로운 희망 [66] [43] 오류가 있는 링 학습 키 교환

예 [67] [68] 초특이 isogeny 키 교환

맥비츠 [69] 오류 수정 코드

구현

포스트 양자 암호화의 주요 과제 중 하나는 잠재적으로 양자 안전 알고리즘을 기존 시스템에 구현하는 것으로 간주됩니다. 예를 들어 하드웨어 보안 모듈을 사용하여 PKI 에서 PICNIC를 구현하는 Microsoft Research 에서 수행한 테스트가 있습니다 . Google의 NewHope 알고리즘 에 대한 테스트 구현 도 HSM 공급업체 에서 수행했습니다 .

기타 주목할만한 구현은 다음과 같습니다.

바운시캐슬 [71]

liboq [72]

도 참조하십시오.

NIST Post-Quantum Cryptography 표준화

양자암호학 - 양자역학을 기반으로 한 암호학

Crypto-shredding - 암호화 키 삭제

지금 수확하고 나중에 해독

참조

피터 W. 쇼어 (1997). "양자 컴퓨터에서 소인수 분해 및 이산 대수를 위한 다항 시간 알고리즘". 컴퓨팅에 관한 SIAM 저널 . 26 (5): 1484–1509. arXiv : quant-ph/9508027 . 비브코드 : 1995quant.ph..8027S . 도이 : 10.1137/S0097539795293172 . S2CID 2337707 .

다니엘 J. 번스타인(2009). "포스트 양자 암호학 소개"(PDF). 양자 이후 암호화.

"새로운 큐비트 제어는 양자 컴퓨팅의 미래에 좋은 징조" . phys.org .

"Cryptographers Take On Quantum Computer" . IEEE 스펙트럼 . 2009-01-01.

"Post-Quantum Computing Cryptography 연구원 Jintai Ding과의 Q&A". IEEE 스펙트럼 . 2008-11-01.

"ETSI 양자 안전 암호화 워크숍" . ETSI 양자 안전 암호화 워크숍 . ETSI. 2014년 10월. 2016년 8월 17일에 원본 문서 에서 보존된 문서 . 2015년 2월 24일 에 확인함 .

케빈 타운센드 (2022-02-16). "양자 복호화 '지금 수확, 나중에 복호화' 문제 해결" . 시큐리티위크 . 2023년 4월 9일 에 확인함 .

"양자 안전 보안 통신" (PDF) . 영국 국립 양자 기술 프로그램 . 2021년 10월 . 2023년 4월 9일 에 확인함 .

대니얼 J. 번스타인 (2009-05-17). "해시 충돌의 비용 분석: 양자 컴퓨터가 SHARCS를 쓸모없게 만들까요?" (PDF) .

대니얼 J. 번스타인 (2010-03-03). "그로버 대 맥엘리스" (PDF) .

크리스 페이커트 (2014). "인터넷을 위한 격자 암호화" (PDF) . IACR. 2014년 5월 12일에 원본 문서에서 보존된 문서 . 2014년 5월 10일 에 확인함 .

Güneysu, 팀; Lyubashevsky, Vadim; Pöppelmann, 토마스 (2012). "Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems"(PDF). 인리아. 2014년 5월 12일 에 확인함.

장지앙(2014). "이상적인 격자에서 인증된 키 교환" (PDF) . iacr.org . IACR. 2014년 9월 7일에 원본 문서에서 보존된 문서 . 2014년 9월 7일 에 확인함 .

Ducas, 레오; 두르무스, 알랭; Lepoint, Tancrède; Lyubashevsky, Vadim (2013). "격자 서명 및 바이모달 가우시안". 2015년 4월 18일 에 확인함.

류바셰프스키, 바딤; Peikert; 레게브(2013). "이상적인 격자 및 링에 대한 오류로 학습" (PDF) . IACR. 2014년 1월 31일에 원본 문서에서 보존된 문서 . 2013년 5월 14일 에 확인함 .

Augot, Daniel(2015년 9월 7일). "장기적으로 안전한 포스트 퀀텀 시스템의 초기 권장 사항"(PDF). PQCRYPTO. 2015년 9월 13일 에 확인함.

Stehlé, Damien; Steinfeld, Ron (2013-01-01). "Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices". Cryptology ePrint Archive.

Easttom, Chuck (2019-02-01). "An Analysis of Leading Lattice-Based Asymmetric Cryptographic Primitives". An Analysis of Leading Lattice-Based Asymmetric Cryptographic Primitivess. pp. 0811–0818. doi:10.1109/CCWC.2019.8666459. ISBN 978-1-7281-0554-3. S2CID 77376310.

Ding, Jintai; Schmidt (7 June 2005). "Rainbow, a New Multivariable Polynomial Signature Scheme". In Ioannidis, John (ed.). Third International Conference, ACNS 2005, New York, NY, USA, June 7–10, 2005. Proceedings. Lecture Notes in Computer Science. Vol. 3531. pp. 64–175. doi:10.1007/11496137_12. ISBN 978-3-540-26223-7.

Buchmann, Johannes; Dahmen, Erik; Hülsing, Andreas (2011). "XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions". Post-Quantum Cryptography. PQCrypto 2011. Lecture Notes in Computer Science. Vol. 7071. pp. 117–129. CiteSeerX 10.1.1.400.6086. doi:10.1007/978-3-642-25405-5_8. ISSN 0302-9743.

Bernstein, Daniel J.; Hopwood, Daira; Hülsing, Andreas; Lange, Tanja; Niederhagen, Ruben; Papachristodoulou, Louiza; Schneider, Michael; Schwabe, Peter; Wilcox-O'Hearn, Zooko (2015). Oswald, Elisabeth; Fischlin, Marc (eds.). SPHINCS: practical stateless hash-based signatures. Lecture Notes in Computer Science. Vol. 9056. Springer Berlin Heidelberg. pp. 368–397. CiteSeerX 10.1.1.690.6403. doi:10.1007/978-3-662-46800-5_15. ISBN 9783662467992.

Huelsing, A.; Butin, D.; Gazdag, S.; Rijneveld, J.; Mohaisen, A. (2018). "RFC 8391 - XMSS: eXtended Merkle Signature Scheme". tools.ietf.org. doi:10.17487/RFC8391.

Moni Naor, Moti Yung: Universal One-Way Hash Functions and their Cryptographic Applications .STOC 1989: 33-43

Overbeck, Raphael; Sendrier (2009). Bernstein, Daniel (ed.). Code-based cryptography. Post-Quantum Cryptography. pp. 95–145. doi:10.1007/978-3-540-88702-7_4. ISBN 978-3-540-88701-0.

De Feo, Luca; Jao; Plut (2011). "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies" (PDF). PQCrypto 2011. Retrieved 14 May 2014.

Higgins, Peter (2013). "Pushing for Perfect Forward Secrecy, an Important Web Privacy Protection". Electronic Frontier Foundation. Retrieved 15 May 2014.

Sun, Xi; Tian; Wang (19–21 Sep 2012). Browse Conference Publications > Intelligent Networking and Co ... Help Working with Abstracts Toward Quantum-Resistant Strong Designated Verifier Signature from Isogenies. Intelligent Networking and Collaborative Systems (INCoS), 2012 4th International Conference on. pp. 292–296. doi:10.1109/iNCoS.2012.70. ISBN 978-1-4673-2281-2. S2CID 18204496.

Perlner, Ray; Cooper (2009). "Quantum Resistant Public Key Cryptography: A Survey". NIST. Retrieved 23 Apr 2015.

Campagna, Matt; Hardjono; Pintsov; Romansky; Yu (2013). "Kerberos Revisited Quantum-Safe Authentication" (PDF). ETSI.

Lyubashevsky, Vadim; Peikert; Regev (25 June 2013). "On Ideal Lattices and Learning with Errors Over Rings" (PDF). Springer. Retrieved 19 June 2014.

Akleylek, Sedat; Bindel, Nina; Buchmann, Johannes; Krämer, Juliane; Marson, Giorgia Azzurra (2016). "An Efficient Lattice-Based Signature Scheme with Provably Secure Instantiation". Cryptology ePrint Archive.

Nejatollahi, Hamid; Dutt, Nikil; Ray, Sandip; Regazzoni, Francesco; Banerjee, Indranil; Cammarota, Rosario (2019-02-27). "Post-Quantum Lattice-Based Cryptography Implementations: A Survey". ACM Computing Surveys. 51 (6): 1–41. doi:10.1145/3292548. ISSN 0360-0300. S2CID 59337649.

Bulygin, Stanislav; 펫졸트; 부흐만(2010). "직접 공격 하에서 불균형 오일 및 식초 서명 체계의 입증 가능한 보안을 향하여". 암호학의 진행 – INDOCRYPT 2010 . 컴퓨터 과학 강의 노트. Vol. 6498. 17~32쪽. CiteSeerX 10.1.1.294.3105 . 도이 : 10.1007/978-3-642-17401-8_3 . ISBN 978-3-642-17400-1.

Pereira, Geovandro; Puodzius, 카시우스; 바레토, 파울로(2016). "짧은 해시 기반 서명". 시스템 및 소프트웨어 저널 . 116 : 95–100. 도이 : 10.1016/j.jss.2015.07.007 .

가르시아, 루이스. "머클 서명 체계의 보안 및 효율성" (PDF) . 암호화 ePrint 아카이브 . IACR . 2013년 6월 19일 에 확인함 .

블라움, 마리오; 파렐; 틸보그(2002년 5월 31일). 정보, 코딩 및 수학 . 뛰는 것. ISBN 978-1-4757-3585-7.

왕용거(2016). "양자 저항성 랜덤 선형 코드 기반 공개 키 암호화 방식 RLCE". 정보 이론 절차(ISIT) . IEEE ISIT: 2519–2523. arXiv : 1512.08454 . 비브코드 : 2015arXiv151208454W .

크리스티나 델프스; 갤브레이스(2013). "F_p에 대한 초특이 타원 곡선 사이의 등질성 계산". arXiv : 1310.7789 [ 수학.NT ].

Hirschborrn, P; 호프스타인; Howgrave-Graham; 와이트. "결합된 격자 감소 및 MITM 접근법에 비추어 NTRUEncrypt 매개변수 선택"(PDF). NTRU. 2013년 1월 30일에원본(PDF)에서 보존된 문서. 2014년 5월 12일 에 확인함.

Petzoldt, 알브레히트; 불가진; 부흐만(2010). "Rainbow 서명 체계에 대한 매개변수 선택 - 확장 버전 -"(PDF). 2016년 3월 4일에 원본 문서에서 보존된 문서. 2014년 5월 12일 에 확인함.

"SPHINCS+: NIST 포스트 퀀텀 프로젝트에 제출" (PDF) .

초프라, 아르준 (2017). "GLYPH: GLP 디지털 서명 체계의 새로운 인스턴스화" . 암호화 ePrint 아카이브 .

Alkim, Erdem; Ducas, 레오; Pöppelmann, 토마스; 슈바베, 피터 (2015). "이후 양자 키 교환 - 새로운 희망"(PDF). 암호화 ePrint 아카이브, 보고서 2015/1092. 2017년 9월 1일 에 확인함.

왕용거(2017). "McEliece 체계를 위한 수정된 양자 저항 공개 키 암호화 체계 RLCE 및 IND-CCA2 보안" . 암호화 ePrint 아카이브 .

Misoczki, R.; 틸리히, JP; 센드리에, N.; 바레토, PSLM(2013). MDPC-McEliece: Moderate Density Parity-Check 코드의 새로운 McEliece 변형입니다 . 정보 이론에 관한 2013 IEEE 국제 심포지엄 . pp. 2069-2073. CiteSeerX 10.1.1.259.9109 . 도이 : 10.1109/ISIT.2013.6620590 . ISBN 978-1-4799-0446-4. S2CID 9485532 .

코스텔로, 크레이그; 롱가, 패트릭; 네릭, 마이클 (2016). "초특이 isogeny Diffie-Hellman을 위한 효율적인 알고리즘" (PDF) . 암호학의 발전 .

코스텔로, 크레이그; 자오; 론가; 내릭; 르네; Urbanik. "SIDH 공개 키의 효율적인 압축". 2016년 10월 8일 에 확인함.

Lin, Jintai Ding, Xiang Xie, Xiaodong (2012-01-01). "A Simple Provably Secure Key Exchange Scheme based on the learning with errors problem" . 암호화 ePrint 아카이브 .

크리스 페이커트 (2014-01-01). "인터넷을 위한 격자 암호화" . 암호화 ePrint 아카이브 .

비크람 싱(2015). "격자 암호화를 사용한 인터넷의 실용적인 키 교환" . 2015년 4월 18일 에 확인함 .

Zhang, Jiang; Zhang, Zhenfeng; Ding, Jintai; Snook, Michael; Dagdelen, Özgür (2015-04-26). "Authenticated Key Exchange from Ideal Lattices". In Oswald, Elisabeth; Fischlin, Marc (eds.). Advances in Cryptology - EUROCRYPT 2015. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 719–751. CiteSeerX 10.1.1.649.1864. doi:10.1007/978-3-662-46803-6_24. ISBN 978-3-662-46802-9.

Krawczyk, Hugo (2005-08-14). "HMQV: A High-Performance Secure Diffie-Hellman Protocol". In Shoup, Victor (ed.). Advances in Cryptology – CRYPTO 2005. Lecture Notes in Computer Science. Vol. 3621. Springer. pp. 546–566. doi:10.1007/11535218_33. ISBN 978-3-540-28114-6.

Naor, Dalit; Shenhav; Wool (2006). "One-Time Signatures Revisited: Practical Fast Signatures Using Fractal Merkle Tree Traversal" (PDF). IEEE. Retrieved 13 May 2014.

Barreto, Paulo S. L. M.; Biasi, Felipe Piazza; Dahab, Ricardo; López-Hernández, Julio César; Morais, Eduardo M. de; Oliveira, Ana D. Salina de; Pereira, Geovandro C. C. F.; Ricardini, Jefferson E. (2014). Koç, Çetin Kaya (ed.). A Panorama of Post-quantum Cryptography. Springer International Publishing. pp. 387–439. doi:10.1007/978-3-319-10683-0_16. ISBN 978-3-319-10682-3.

De Feo, Luca; Jao; Plut (2011). "Towards Quantum-Resistant Cryptosystems From Supersingular Elliptic Curve Isogenies" (PDF). Archived from the original on 11 February 2014. Retrieved 12 May 2014.

"Cryptology ePrint Archive: Report 2016/229". eprint.iacr.org. Retrieved 2016-03-02.

Ristic, Ivan (2013-06-25). "Deploying Forward Secrecy". SSL Labs. Retrieved 14 June 2014.

"Does NTRU provide Perfect Forward Secrecy?". crypto.stackexchange.com.

"Open Quantum Safe". openquantumsafe.org.

Stebila, Douglas; Mosca, Michele. "Post-Quantum Key Exchange for the Internet and the Open Quantum Safe Project". Cryptology ePrint Archive, Report 2016/1017, 2016. Retrieved 9 April 2017.

"liboqs: C library for quantum-resistant cryptographic algorithms". 26 November 2017 – via GitHub.

"openssl: Fork of OpenSSL that includes quantum-resistant algorithms and ciphersuites based on liboqs". 9 November 2017 – via GitHub.

Bos, Joppe; Costello, Craig; Ducas, Léo; Mironov, Ilya; Naehrig, Michael; Nikolaenko, Valeria; Raghunathan, Ananth; Stebila, Douglas (2016-01-01). "Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE". Cryptology ePrint Archive.

"NTRUOpenSourceProject/NTRUEncrypt". GitHub. Retrieved 2017-04-10.

Stebila, Douglas (26 Mar 2018). "liboqs nist-branch algorithm datasheet: kem_newhopenist". GitHub. Retrieved 27 September 2018.

"Lattice Cryptography Library". Microsoft Research. 19 Apr 2016. Retrieved 27 September 2018.

"SIDH Library - Microsoft Research". Microsoft Research. Retrieved 2017-04-10.

Feo, Luca De; Jao, David; Plût, Jérôme (2011-01-01). "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies". Archived from the original on 2014-05-03.

Bernstein, Daniel J.; Chou, Tung; Schwabe, Peter (2015-01-01). "McBits: fast constant-time code-based cryptography". Cryptology ePrint Archive.

"Microsoft/Picnic" (PDF). GitHub. Retrieved 2018-06-27.

"Bouncy Castle Betas".

"Open Quantum Safe".