NIST, "Report on Post-Quantum Cryptography" 직역

이 글은 2016년 NIST 에서 공개한 NISTIR 8105, "Report on Post-Quantum Cryptography", Lily Chen et al[1] 을 공부하는 글입니다. 번역기를 사용하지 않고, 제 번역 능력과 이해도에 따라 단어 선정이나 글의 흐름이 매끄럽지 않을 수 있습니다. 본문의 인용부호[#]는 순서를 조정하여 포함하거나, 불필요하다고 판단하면 생략합니다.

(NIST의 ITL 소개 생략)

요약

최근 몇 년간, 양자 현상 기술을 활용하여 전통적인 컴퓨터는 처리할 수 없거나 어려운 계산 문제들을 푸는 기계인 양자 컴퓨터에 대한 상당한 연구가 있었다. 만약 큰 규모의 양자 컴퓨터가 개발되면, 현재 사용 중인 다수의 공개키 암호체계를 깰 수 있을 것이다. 이는 인터넷 등에서 이뤄지는 디지털 커뮤니케이션의 기밀성과 무결성을 심각하게 훼손한다. 양자 후 암호(또는 양자-내성 암호라 불림)의 목적은 양자 및 전통 컴퓨터 양쪽에서 안전한 암호 체계를 개발하는 것이며, 현존하는 네트워크 및 프로토콜과 연동할 수 있어야 한다. 이 내부 보고서는 현재 양자 계산과 양자 후 암호의 상태에 대한 NIST의 이해를 공유하고, 이 세계로 나아가기 위한 NIST 의 첫 계획을 요약한다. 또한 이 보고서는 새로운 암호 기반으로의 전환이 가지는 어려움(challenge)을 식별하고, 유관 기관(agencies)들이 암호화 민첩성(crypto agility)[2]에 집중해야 하는 필요성을 강조한다.

(Keywords, Table of Contents 생략)

1. 서문

지난 30년 간, 공개키 암호는 우리의 전 세계적 디지털 커뮤니케이션 기반의 필수적인 요소가 되었다. 이 네트워크들은 모바일 폰, 인터넷 거래, 소셜 네트워크와 클라우드 컴퓨팅과 같이 우리의 경제, 우리의 보안, 그리고 우리의 삶의 방식에 중요한 다양한(plethora) 앱들을 지원한다. 이러한 연결된 세계에서, 개인, 기업, 그리고 정부의 안전한 통신 능력은 가장 중요한 요소이다.

대다수 우리의 가장 중요한(crucial) 통신 프로토콜들은 주로 세 개의 핵심적인 암호학적 기능들, 즉 공개키 암호화, 전자 서명, 그리고 키 교환에 의존한다. 현재, 이 기능들은 디피-헬만 키 교환, RSA 암호체계, 그리고 타원 곡선 암호체계를 주로 사용하여 구현된다. 이들의 보안은 다양한 군(group)에서 정수 인수분해 또는 이산 로그 문제와 같은 특정 수의 이론적 문제의 어려움에 의존한다.

1994년, 벨 연구소의 피터 쇼어는 물질의 물리학적 특성과 에너지를 활용하여 계산을 수행하는 양자 컴퓨터가 이 문제들을 효율적으로 풀 수 있고[3], 이를 통해 그 가정[4]을 기반으로 하는 모든 공개키 암호체계가 무력화됨을 보였다. 따라서, 충분히 강력한 양자 컴퓨터는 현재 통신 형태 - 키 교환에서 암호화와 디지털 인증 - 를 위험하게 할 것이다.

양자 컴퓨터가 특정 문제들을 전통 컴퓨터보다 빠르게 푸는 데 활용될 수 있다는 발견은 양자 계산에 대한 흥미를 엄청나게 고무시켰다. 양자 복잡성(complexity)은 전통적인 복잡성과 근본적으로 다른가? 큰 규모의 양자 컴퓨터는 언제 개발될 것인가? 양자 계산과 전통 계산의 공격(adversary) 양쪽 모두에 저항(resist)하는 방법이 있는가? 연구자들은 이 문제에 대해 고민하고 있다.

쇼어의 발견 이후 20년 동안, 양자 알고리즘의 이론은 상당히 발전했다. 지수적 속도 증가(exponential speedup)를 달성하는 양자 알고리즘들이 물리학 모의실험(physics simulation), 정수론(number theory), 그리고 위상수학(topology)에 관련된 문제들에서 발견되었다. 그럼에도, 양자 계산의 지수적 속도 증가를 받아들이는 문제들의 목록은 상대적으로 적게 유지되었다. 반면에, 검색(searching), 충돌 탐지(collision finding), 그리고 부울 공식의 정리(evaluation of Boolean formulae)에 관련된 넓은 집합의 문제들에서 더 적당한(modest) 속도 증가가 개발되었다. 특히, 그로버의 검색 알고리즘은 비구조화된 검색 문제들(unstructured search problems)에서 두 제곱적 속도 증가(quadratic speedup)을 제공한다. 이러한 속도 증가가 암호학적 기술을 쇠태(obsolete)시키지는 않지만, 더 큰 키 길이(size)의 필요성에 영향을 줄 수 있으며, 대칭키의 경우도 포함된다. 표1은 큰 큐모의 양자 컴퓨터가 AES 와 RSA 같은 일반적인 암호 알고리즘에 미치는 영향의 요약을 보여준다. 어느 정도까지 양자 발전이 진행될 수 있는 지와, 양자 모델과 전통 모델 간의 실현 가능성(feasibility)의 차이(gap)가 얼마나 넓은 지는 알려져 있지 않다.

표1. 주요 암호 알고리즘에 대한 양자 컴퓨팅의 영향

큰 규모의 양자 컴퓨터가 언제 만들어질 것인지라는 질문은 복잡하고 논란의 여지가 있다. 과거에는 큰 규모를 가진 양자 컴퓨터의 물리적 가능성이 명확하지 않았으나, 이제 많은 과학자들은 단지 거대한 공학적 어려움이 있을 뿐이라고 믿고 있다. 심지어 일부 전문가들은 다음 20년 정도 안에 현재 사용되고 있는 모든 공개키 기법을 근본적으로 깰 수 있는 충분히 큰 양자 컴퓨터가 만들어질 것이라고 예상한다[5]. 우리의 현재 공개키 암호 기반이 전개되는 데에 거의 20년이 걸렸다. 현재 널리 쓰이는 암호 체계가 그들의(their?) 양자 컴퓨팅을 저항하는 반대측(counterparts)으로 원활하고, 안전하게 이동(migration)하도록 보장하기 위해서는 상당한 노력이 소요된다. 그러므로, 우리는 양자 컴퓨팅 시대가 도래하는 정확한 시간을 추정할 수 있을 지와 관계없이, 지금 반드시 우리의 정보 보안 체계가 양자 컴퓨팅에 저항할 수 있도록 준비를 시작해야 한다.

하나의 큰 다국적 공동체가 새로운 양자-내성의 원시적 특성들(primitives)을 활용하여, 우리의 공개키 기반이 온전하게(intact) 유지되기를 바라며, 미래 양자 컴퓨팅에서의 정보 보안 이슈를 다루기 위해 나타났다. 학계에서는, 이 새로운 과학을 "양자 후 암호(Post-Quantum Cryptography)"라는 이름으로 탄생시켰다(bears). 2006년에 시작된 PQCrypto 는 이 분야의 활발한 연구를 위한 자체 학술대회(conference)이다. 국가 기금(funding) 단체들로부터 상당한 지원을 받아왔으며, 가장 눈에 띄는 국가는 일본과 유럽으로, 유럽 연합의 PQCrypto 와 SAFEcrypto 프로젝트, 그리고 일본의 CREST Crypto-Math 프로젝트가 있다.

이러한 노력들이 기초 연구의 진보를 이끌고, 현실 세계에서 양자 후 암호체계의 발전을 위한 길을 다지고(paving) 있다. 지난 몇 면간, 산업과 표준 단체들은 이 분야에서 각자의 활동을 시작했으며, 2013년 부터 유럽 통신 표준원(ETSI, European Telecommunication Standards Institute)은 세 번의 "양자-안전 암호(Quantum-Safe Cryptography)" 토론회(workshop)를 개최했고, 2015년 NIST 는 정부, 산업, 학계에서 140명 이상이 참석한 "양자 후 세계의 사이버보안(Cybersecurity in a Post-Quantum World)" 토론회를 개최하였다.

NIST는 비정부 보안 연방 정보 체계의 보호를 위한 지침과 표준을 개발하는 넓은 책임의 부분으로 양자 후 암호 표준화의 고유한 역할을 가진다. AES와 같은 많은 NIST 표준들이 학계와 산업계의 폭넓은 참여를 통해 개발되었으며, 효과적인 방안으로 널리 적용되었다. 양자 후 암호의 NIST 표준화는 유사한 유익을 제공할 것이다.

이 모든 소식(sources)들을 고려할 때, 양자-내성 기술을 개발하는 노력이 격렬해지는 것(intensifying)은 명확하다. 동등하게, 새로운 양자 후 공개키 암호가 표준화될 필요성과 동반되는 투자가 시급한 것도 명확하다. 이 다국적 양자 후 암호 공동체에 NIST 암호 표준이 관여하여 전 세계의 학계와 다른 표준 단체들에게 동의를 받는(endorsed) 것은 중요하다. 이 내부 보고서는 양자 계산과 양자 후 암호에 대한 NIST 의 현재 이해와 우리가 앞으로 나아갈 계획의 개요를 공유한다.

2. 양자-내성 암호의 개요

오늘날 공개키 암호의 가장 중요한 사용은 전자 서명과 키 생성이다. 표1에서 언급하였듯이, 큰 규모의 양자 컴퓨터의 개발(construction)은 많은 공개키 암호체계를 불안하게 할 것이다. 특히, RSA와 같이 정수 인수분해의 어려움을 기반으로 하는 것들과 이산 로그 문제의 어려움을 기반으로 하는 것들도 포함한다. 반대로, 대칭 키 체계에 대한 영향은 급격하지않다. 그로버의 알고리즘은 전통적인 컴퓨터에서의 검색 알고리즘과 비교하여 양자 컴퓨터에서 두 제곱(quadratic)적 속도 증가를 제공한다. 우리는 그로버의 알고리즘이 어떤 실질적 관계가 있을지는 잘 모르지만, 만약 그렇다면, 보안을 유지하기 위해 키 길이를 두 배로 늘리는 것이 적당하다. 게다가, 검색 알고리즘의 지수적 속도 증가는 불가능함이 보여졌으므로[6], 양자 시대에도 대칭 알고리즘과 해시 함수는 사용 가능할 것이라고 제안한다.

결과적으로, 전통 컴퓨터와 양자 컴퓨터 양쪽에서 공격에 저항한다고 믿어지는 알고리즘의 탐색은 공개키 알고리즘에 집중되었다. 이 단원에서, 우리는 제안된 양자 후 원시적 특성들의 주요 집단(family)의 개요를 간단하게 설명한다. 이 집단은 격자(lattices), 코드, 그리고 다변수 다항식(multivariate polynomials)과 다른 일부(handful of others)를 기반으로 하는 것들을 포함한다. 추가 정보는 [7, 8]을 보라.

격자-기반 암호 : 격자 문제 기반의 암호체계는 몇 가지 이유로 새로운 관심을 받아왔다. 흥미로운 새 응용들(완전 동형 암호화(fully homomorphic encryption)[9], 코드 난독화, 그리고 속성 기반 암호화[10] 등)이 격자 기반 암호를 사용하여 가능해졌다. 대부분의 격자-기반 키 성립(establishment) 알고리즘들이 상대적으로 단순하고, 효율적이며, 고도의 병렬화가 가능하다. 또한, 일부 격자-기반 체계의 보안은 평균적인 경우가 아닌 최악의 경우의 강도 가정에서도 증명 가능하게 안전하다. 반면에, 알려진 암호문 해독 기법에 대해 격자 기법들의 정확한 보안성을 추측하기 어렵다는 것이 증명되었다. 

코드-기반 암호 : 1978년, McEliece cryptosystem 에서 처음 제안하였고, 아직까지 깨지지 않았다. 그동안, 오류 보정 코드를 기반하는 다른 체계들이 제안되었다. 꽤 빠르지만, 대부분의 코드-기반 원시적 특성들은 매우 큰 키 길이를 가지고 있다. 키 길이를 줄이기 위한 시도로 더 구조적인 코드를 소개하는 다양한 변형들이 소개되었으나, 일부 제안에서는 추가된 구조가 공격을 성공하게 하였다. 코드-기반 서명을 위한 제안들이 일부 있었으나, 코드-기반 암호는 암호화 기법에 더 성공적으로 여겨진다.

다변수 다항식 암호 : 이 기법들은 유한체(finite fields) 의 다변수 다항식의 체계를 푸는 어려움에 기반한다. 몇몇 다변수 암호체계가 지난 몇 십년간 제안되었으며, 다수는 깨져 있다[11]. 다변수 암호화 기법을 위한 제안들이 일부 있었으나, 다변수 암호는 역사적으로 서명을 위한 접근법으로 더 성공적이었다.

해시-기반 서명 : 해시-기반 서명은 해시 함수를 사용하여 생성된 전자 서명이다. 그들의 보안은, 심지어 양자 공격에 대해서도, 잘 이해된다. 더 효율적인 해시-기반 서명 기법의 다수는 서명자가 반드시 이전에 서명한 메시지의 정확한 개수를 기록해야 하는 결점을 가지고 있고, 기록의 어떠한 오류라도 불안정을 초래한다. 이 기법들의 다른 결점은 오직 제한된 횟수의 서명만 생성할 수 있다는 것이다. 제한된 서명 횟수를 효율적으로 증가시키는 것이 가능하지만, 서명의 크기를 증가시킨다.

기타 - 위 집단에 포함되지 않는 다양한 체계가 제안되었다. 그 중 하나는 초단수 타원 곡선(supersingular elliptic curves)[12] 상의 등원사상들(isogenies)[13]의 계산을 기반으로 한다. 타원 곡선 상의 이산 로그 문제는 쇼어의 알고리즘으로 효율적으로 풀릴 수 있으나, 초단수 타원 곡선 상의 등원사상 문제에는 유사한 양자 공격이 알려지지 않았다. 기타 다른 제안들, 예를 들어 꼬임군(braid groups)[14] 안에서 공액 탐색(conjugacy search) 문제[15]와 관련된 문제들은 그들의 보안이 얼마나 자신이 있는 지에 대한 충분한 분석이 이뤄지지 않았다.

현재 알려진 어떤 알고리즘도 오늘날 사용하고 있는 알고리즘을 큰 수정 없이 대체(drop-in replacement)할 수 있을 것이라고 보이지는 않는다(improbable). 아마 우리가 극복해야하는 어려움은 대부분의 양자-내성 알고리즘이 그들이 대체할 알고리즘보다 키가 길다는 것이다. 이는 TLS, IKE 와 같은 다양한 인터넷 프로토콜의 변화를 요구할 것이다. 이로 인해, 위 방법들은 반드시 조심스럽게 고려되어야 한다.

우리는 위에 언급된 제안들 중 어느 것도 모든 양자 공격에 대해 보안을 보장한다고 보지 않는다는 것을 강조(note)한다. 이 기법들을 깨는 새로운 양자 알고리즘이 발견될 수 있다. 그러나, 이는 오늘의 상태와 유사하다. 대부분의 대칭 키 암호체계의 보안이 증명되었지만, 이 증명들은 증명되지 않은 가정을 기반으로 한다. 그러므로, 알려진 공격의 결여는 현재 사용하는 공개키 암호의 보안성을 정당화하는 데 사용된다. 그럼에도, NIST는 위의 제안된 양자 후 알고리즘 중 하나가 오늘날의 사용을 위해 권고되기 전에 더 많은 연구와 분석이 필요하다고 생각한다. 이들은 오늘날 전개된 알고리즘들 만큼 암호학적 공동체로부터 검증(scrutiny)을 받지 않았다. 하나의 예외는 보안성이 널리 알려진 해시-기반 서명이다. 디지털 코드 서명, 해시-기반 서명과 같은 특정 어플리케이션은 앞으로 몇년 동안은 잠재적으로 표준화될 수 있을 것이다.

3. 양자 컴퓨팅 하드웨어의 발전

대규모의 양자 컴퓨터의 개발 가능성에 대한 연구는 피터 쇼어가 1994년에 정수 인수분해를 위한 다항-시간 양자 알고리즘을 발견한 후 진지하게 시작되었다. 그 당시에는, 양자 컴퓨팅이 근본적으로 측정 가능할 수 있을 지가 명확하지 않았다. 많은 선도적인 전문가들은 양자 상태가 너무 취약하고, 오류가 누적되어 큰 규모의 계산이 실현되지 않을 것이라고 추측하였다. 이 상황은 1990년대 후반에 양자 오류 보정 코드와 기준점 정리(threshold theorems)[16]들이 개발되면서 바뀌었다. 이 기준점 정리들은 만약 고정된 기준점 아래로 양자 컴퓨터의 각 논리 게이트("양자 게이트")의 오류율을 낮출 수 있다면, 양자 계산 실행 동안에 오류 보정 과정을 포함시켜서 임의의 긴 양자 계산이 믿을 수 있고, 결함을 포용하는(fault-tolerant) 방법으로 수행될 수 있다는 것을 보인다[17].

몇 년동안, 실험과학자(experimentalists)들은 각 양자 게이트의 오류율을 서서히 낮추며 개선된 하드웨어를 개발하였다. 동시에, 이론과학자(theorists)들은 더 높은 결함 포용 기준을 산출하는 새로운 양자 오류 보정 방법들을 개발했다. 최근에, 일부 실험과학자들은 이온 트랩과 초전도체 회로를 사용하여 가장 높은 이론적 결함 허용(약 1%)보다 명목상(nominally) 낮은 보편적인 양자 게이트들의 집합을 입증하였다[18, 19]. 이는 정부와 산업계 모두 투자를 증가하도록 고무시킨 대단한 이정표(milestone)이다. 하지만, 오늘날 일부 큐비트와 관련된 연구실 재현에서 수십만 또는 수백만의 물리 큐비트로 부호화되는 수천 개의 논리 큐비트와 관련된 대규모 양자 컴퓨터로의 이동은 상당히 장기적인 노력이 요구되는 것은 자명하다.

일반적인 목적의 디지털 양자 컴퓨터를 개발하는 것과 병행하여, 양자 강화기(annealer, 예를들면 D-Wave 기계), 아날로그 양자 모의실험기, 그리고 보손 표본화 기기(boson sampling devices)와 같은 특수한 목적을 가진 양자 아날로그 컴퓨터를 개발하려는 노력이 있다. 이 기기 중 일부는 디지털 양자 컴퓨터보다 큐비트의 수가 매우 크게 증가되었다. 그러나, 그들의 특수한 본성(specialized nature)으로 인해, 이 아날로그 양자 기기들은 암호문 해독(cryptanalysis)과의 관련성이 믿어지지 않는다.

4. 이후 방향

더 강한 암호의 필요가 전통 및 양자 컴퓨팅 기술 양쪽에서의 진보에 의해 이끌어진다. 전통적인 공격들에 대한 보안을 유지하기 위해, NIST는 이미 80 비트 보안을 제공하는 알고리즘과 키 길이를 112 또는 128 비트의 보안을 제공하는 키 길이와 알고리즘으로 권고를 전환하였다[20]. 양자 공격에 대한 보안을 제공하기 위해, NIST 는 새로운 양자 후 암호체계로의 더 어려운 전환을 용이하게 해야 할 것이다.

언제 측정할 수 있는 양자 컴퓨터가 가용해질지는 명확하지 않다. 하지만, 과거와 지금, 양자 컴퓨터를 개발하고 있는 연구자들은 2030년까지 약 10억 달러의 예산으로 2000비트의 RSA를 수 시간내에 깰 수있는 양자컴퓨터가 만들어질 수 있을 것이라고 추정하고 있다[21]. 이는 NIST 가 현재 표준화한 암호체계에 대한 심각한 장기 위협이다.

상기 예측과 전통 컴퓨터를 사용하여 이 암호체계들을 깨는 비용을 비교하는 것은 유용하다.  2011-2013년에 단계적으로 퇴출된 80비트 또는 그 미만의 보안을 제공하는 암호체계는 가장 위험하다. 이들은 현재 수만에서 수억달러의 비용 범위 안에서 깨질 수 있다. 112비트의 보안을 제공하는 암호체계는 당분간 안전하게 유지될 것이다. 이들은 아마 수십억 달러로 30 에서 40년 안에 깨질 것이다(전통 컴퓨터를 사용하여). 

그러므로, 112비트에서 128비트(또는 이상)로의 전환은 아마도 현존하는 암호체계에서 양자 후 암호체계로 전환하는 것보다 덜 긴급할 것이다. 이 양자 후 전환은 많은 근본적인 어려움들을 야기한다.

이전의 약한 암호에서 강한 암호로의 전환은 전통 컴퓨터의 공격에 대한 시간 복잡성을 기반으로 하는 알고리즘의 보안을 측정하는 보안 비트 패러다임을 기반으로 하였다.(예를 들어, 전통 컴퓨터가 128비트 보안 키를 무차별 대입 공격으로 찾는 데에 필요한 시간과 자원만큼 공격이 어렵다면, 이 알고리즘은 128비트의 보안을 가지고 있다고 말한다.) NIST SP 800-57 파트1[22]은 2016년 1월까지 NIST 에 의해 표준화된 알고리즘들을 80, 112, 128, 192, 그리고 256 비트의 보안으로 분류한다. 나아가 80비트 보안 레벨은 더이상 충분히 안전하지 않다고 여기며, 112비트 보안 레벨은 2031년까지 단계적으로 퇴출되어야 한다고 권고한다.

불행하게도, 보안 비트 패러다임은 양자 암호분석을 대항하는 알고리즘의 보안에 고려되지 않는다. 이는 우리의 양자-내성 암호로의 전환 가이드에 부적합하다. 아직 키 길이가 양자 공격에 대항하는 적용할만한 보안 레벨을 제공할 지에 대한 합의된 관점이 없다. 대칭 키에 대해서, 하나의 단순한 경험론은 두 제곱적 성능 증가를 달성하는 그로버의 알고리즘을 보완하기 위해 키 길이를 두배로 하는 것이다. 하지만, 양자 계산 하드웨어의 개발은 전통 하드웨어의 개발보다 훨씬 비용이 클 것이므로, 이 권고도 지나치게 보수적이다. 동시에, 이 권고는 더 복잡한 양자 공격들의 가능성을 고려하지 않았다[23, 24, 25]. 우리의 양자 암호 해독의 이해는 여전히 제한되며, 이 분야의 더 많은 연구가 시급히 필요하다.

양자 후 암호를 위한 표준의 개발은 양자-내성 기법들의 분석을 위한 상당한 자원이 필요할 것이며, NIST 가 표준화하기 위해 선택한 알고리즘을 확신하기 위해서는 상당한 공공의 참여가 필요할 것이다. 양자 계산 하드웨어 발전의 이정표들과 국가 안전 보장국(NSA, National Security Agency)의 최근 그들의 Suite B 지침의 변경[26]으로 인해, 최근 양자 계산과 양자-내성 암호 분야에 대한 관심은 증가되고 있다. 이는 연구 공동체에게 실질적인 양자 컴퓨팅이 정말로 임박하기 전에 다시 오지 않을 수 있는 참여 기회를 제공한다. 결론적으로, NIST는 지금 양자-내성 암호로의 전환을 준비하기 위해 시작하는 중이다.

NIST는 양자 후 암호를 표준화하는 노력을 시작하기 위해 다음의 단계를 밟고 있다. NIST는 양자-내성 공개키 암호 표준을 위한 예비(preliminary) 측정 기준을 명시할 계획이다. 이 기준은 보안과 성능 요구사항들을 포함할 것이다. 기준 초안은 2016년에 공개 의견을 위해 공개될 것이며, 올해 말 안에 완성되기를 기대하고 있다. 이 때, NIST는 양자-내성 공개키 암호, 전자 서명, 그리고 키 교환 알고리즘들의 제안을 받기 시작할 것이다. NIST는 표준화를 위해 이 기능들을 각각 제공하는 최소 하나를 선택하려 한다. NIST 는 고려되어야 하는 알고리즘들의 최종 제출일을 2017년 하반기로 선택할 것이며, 이 제안들은 표준이되기 전에 3~5년의 공개 검증을 허용할 것이다.

이 절차는 AES[27]와 SHA3[28]의 표준화를 이끈 과정들과 많은 공통점을 가질 것이지만, 경쟁이 아니다. NIST는 이 역할을 시의 적절하고 투명하게 공동체의 합의를 달성하는 절차의 관리로 여긴다. 이상적으로, 여러 알고리즘들이 "좋은 선택(good choices)"으로 나타날 것이다. NIST는 각 범주에서 표준화를 위해 하나 또는 이상을 선택할 수 있다. 이 관점에서, NIST의 양자-내성 공개키 암호 표준화 절차는 진행 중인 블록 암호 모드 개발 절차[29]와 유사할 것이다. 

양자-내성 공개키 암호의 표준들이 사용 가능해지면, NIST는 현존하는 표준들에 대한 양자 컴퓨터의 급박한 위협을 재평가할 것이며, 결과에 따라 영향을 받는 표준들을 반대(deprecated)하거나 철회(withdraw)하는 결정을 할 수 있다. 따라서 유관 기관들은 반드시 현재부터 빠르면 10년 안에 이 알고리즘들을 완전히 전환활 수 있도록 준비해야 한다. 현재 표준화된 공개키 알고리즘의 대체는 아직 준비되지 않았지만, 암호화 민첩성의 유지는 필수(imperative)이다. 새로운 양자-내성 알고리즘이 표준화될 때까지, 유관 기관들은 반드시 현재 NIST 표준에 명시된 권고하는 알고리즘들의 사용을 계속해야 한다.

(Appendix A - References 생략.. 하지만 번호를 바꿔서 거의 다 포함됨)

[1] 원문 링크 : https://nvlpubs.nist.gov/nistpubs/ir/2016/nist.ir.8105.pdf#page=13&zoom=100,105,830

[2] 암호화 민첩성(Crypto-agility)은 시스템 인프라에 큰 변화를주지 않으면 서 새로운 암호화 기본 요소 및 알고리즘의 신속한 적응을 지원하는 정보 보안 시스템 설계의 실무 패러다임이라고 한다. 출처는 아래 위키.

https://en.wikipedia.org/wiki/Crypto-agility

[3] P. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete

Logarithms on a Quantum Computer, SIAM J. Comput., 26 (5), 1997, pp.

1484–1509. http://dx.doi.org/10.1137/s0036144598347011.

[4] 앞 문장에서 언급된, 유한체 이산대수의 소인수 분해 또는 이산 로그 문제의 어려움.

[5] M. Mosca, Cybersecurity in an era with quantum computers: will we be ready? IACR Cryptology ePrint Archive Report 2015/1075, 2015. http://eprint.iacr.org/2015/1075.

[6] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, Strengths and weaknesses of quantum computing, SIAM J. Comput., 26 (5), 1997, pp.1510–1523. http://dx.doi.org/10.1137/s0097539796300933

[7] European Telecommunications Standards Institute White Paper No. 8, Quantum Safe Cryptography and Security: An Introduction, Benefits, Enablers and Challenges, June 2015. https://portal.etsi.org/Portals/0/TBpages/QSC/Docs/Quantum_Safe_Whitepaper_1_0_0.pdf

[8] R. Perlner and D. Cooper, Quantum resistant public key cryptography: a survey, In Proc. of IDtrust, ACM, 2009, pp. 85-93. http://dx.doi.org/10.1145/1527017.1527028

[9] 우선, 동형 암호는 암호문끼리 연산이 가능한 암호. 복호화하지 않아도 통계적 처리가 가능하여 민감한 정보(ex. 생체정보) 처리에 유용하다. 동형 암호는 암호문간 연산이 반복되면 노이즈가 발생하여 횟수 제한이 있지만, Bootstrapping 과정을 통해 연산 횟수 제한을 없앨 수 있는 암호화 방식을 완전 동형 암호라고 부른다. 출처는 아래 LG CNS 공식 블로그.
https://blog.lgcns.com/2045

[10] 사용자의 개인키와 암호문이 속성(예를 들어, 살고 있는 국가)에 의존성을 가지며, 속성이 일치해야만 복호화 가능한 암호.. 라고 소개하는 위키는 아래 주소. 공부가 필요함.
https://en.wikipedia.org/wiki/Attribute-based_encryption#cite_note-1

[11] V. Dubois, P. Fouque, A. Shamir and J. Stern, Practical cryptanalysis of SFLASH, Advances in Cryptology — CRYPTO 2007, Lecture Notes in Comput. Sci. 4622, Springer-Verlag, 2007, pp. 1–12. http://dx.doi.org/10.1007/978-3-540-74143-5_1.

[12] https://en.wikipedia.org/wiki/Supersingular_elliptic_curve 공부가 필요함

[13] 단수형은 isogeny 이며, 금융보안원의 "금융부문 암호기술 활용 가이드", 2019 1월, 에서 '등원사상' 이라는 용어를 사용한다. 역시 공부가 필요하다. http://www.fsec.or.kr/common/proc/fsec/bbs/147/fileDownLoad/1794.do

[14] 위상수학에서 주어진 개수의 실을 꼬은 모양으로 구성된 군이며, 대칭군의 일반화라고 한다. 공부가 필요하다.. https://ko.wikipedia.org/wiki/%EA%BC%AC%EC%9E%84%EA%B5%B0_(%EC%9C%84%EC%83%81%EC%88%98%ED%95%99)

[15] 켤레 탐색 문제. 그룹 G 에 속한 원소 g 에 대해 h=x^{-1}gx 를 만족하는 그룹 G 안에 있는 x 를 찾는 문제 ...공부하자... 다음 논문의 abstract 참고함. https://arxiv.org/abs/math/0411644

[16] J. Preskill, Reliable Quantum Computers, Proc. Roy. Soc. London A, 454, 1998, pp. 385–410. http://dx.doi.org/10.1098/rspa.1998.0167

[17] D. Lidar, T. Brun, eds., Quantum Error Correction, Cambridge University Press, 2013. http://dx.doi.org/10.1017/cbo9781139034807

[18] R. Barends, J. Kelly, A. Megrant, A. Veitia, D. Sank, E. Jeffrey, Y. Chen, B. Chiaro, J. Mutus, C. Neil, Superconducting quantum circuits at the surface

code threshold for fault tolerance, Nature 508 (7497), 2014, pp. 500–503. http://dx.doi.org/10.1038/nature13171

[19] T.P. Harty, D.T.C. Allcock, C.J. Balance, L. Guidoni, H.A. Janacek, N.M. Linke, D.N. Stacey, D.M. Lucas, High-Fidelity Preparation, Gates, Memory, and Readout of a Trapped-Ion Quantum Bit, Phys. Rev. Lett. 113 (22), 2014. http://dx.doi.org/10.1103/PhysRevLett.113.220501

[20] NIST Special Publication (SP) 800-131A Revision 1, Transitions: Recommendation for Transitioning the Use of Cryptographic Algorithms and Key Lengths, National Institute of Standards and Technology, Gaithersburg,

Maryland, November 2015, 23pp. http://dx.doi.org/10.6028/nist.sp.800-131ar1

[21] M. Mariantoni, Building a Superconducting Quantum Computer, Invited Talk PQCrypto 2014, October 2014 Waterloo, Canada. https://www.youtube.com/watch?v=wWHAs--HA1c

[22] NIST Special Publication (SP) 800-57 Part 1 Revision 4, Recommendation for Key Management – Part 1: General, National Institute of Standards and Technology, Gaithersburg, Maryland, January 2016, 160pp. http://dx.doi.org/10.6028/NIST.SP.800-57pt1r4. 

[23] P. Campbell, M. Groves, D. Shepherd, Soliloquy: A Cautionary Tale, ETSI Workshop on Quantum-Safe Cryptography, 2014. https://docbox.etsi.org/workshop/2014/201410_CRYPTO/S07_Systems_and_Attacks/S07_Groves_Annex.pdf

[24] M. Kaplan, G. Leurent, A. Leverrier, M. Naya-Plasencia, Quantum Differential and Linear Cryptanalysis, arXiv preprint ArXiv: 1510.05836, 2015. http://arxiv.org/abs/1510.05836

[25] H. Kuwakado, M. Morii, Quantum distinguisher between the 3-round Feistel cipher and the random permutation, In Proc. of 2010 IEEE International Symposium on Information Theory (ISIT), IEEE, 2010, pp. 2682-2685. http://dx.doi.org/10.1109/isit.2010.5513654

[26] National Security Agency, Cryptography Today, report, August 2015. https://www.nsa.gov/ia/programs/suiteb_cryptography/ [accessed 4/20/2016]. Also at: https://www.iad.gov/iad/programs/iad-initiatives/cnsasuite.cfm 둘 다 링크 깨진 것 같아요..

[27] NIST, AES Competition [Web page], http://csrc.nist.gov/archive/aes/

[28] NIST, SHA-3 Competition [Web page], http://csrc.nist.gov/groups/ST/hash/sha-3/

[29] NIST, Modes Development [Web page], http://csrc.nist.gov/groups/ST/toolkit/BCM/modes_development.html