NIST IR 8105 日本語訳
英語タイトル : Report on Post-Quantum Cryptography日本語タイトル : 耐量子暗号に関する報告書
公開日 : 2016-04-28
原文URL : https://csrc.nist.gov/pubs/ir/8105/final
翻訳編集 : 自動生成(有志による非公式の日本語訳), 原文取得日 : 2026-10-31, 訳文 : 101 / 102 ブロック
[要約] NIST IR 8105 は、量子コンピューティングと耐量子暗号の現状に関する NIST の現時点での理解を共有し、この分野で前進するための NIST の初期計画を概説する報告書です。大規模な量子コンピュータが実現すれば、現在使われている多くの公開鍵暗号システムを破れる可能性があり、インターネットなどでのデジタル通信の機密性と完全性が損なわれうると説明しています。耐量子暗号(量子耐性暗号とも呼ばれる)の目標は、量子コンピュータにも従来のコンピュータにも安全で、既存の通信プロトコルやネットワークと相互運用できる暗号システムを開発することです。量子耐性暗号の概要と量子コンピューティングのハードウェアの進展を扱ったうえで、新しい暗号基盤への移行の難しさから、各機関が暗号アジリティに注力する必要を強調しています。
NISTIR 8105
NISTIR 8105
Report on Post-Quantum Cryptography
耐量子暗号に関する報告書
Lily Chen
Stephen Jordan
Yi-Kai Liu
Dustin Moody
Rene Peralta
Ray Perlner
Daniel Smith-Tone
Lily Chen
Stephen Jordan
Yi-Kai Liu
Dustin Moody
Rene Peralta
Ray Perlner
Daniel Smith-Tone
This publication is available free of charge from:
http://dx.doi.org/10.6028/NIST.IR.8105
本刊行物は、以下から無償で入手できます。
http://dx.doi.org/10.6028/NIST.IR.8105
[NIST のロゴ。公的な標章のため、この非公式サイトには掲載していません。原本 PDF を参照してください。]
NISTIR 8105
NISTIR 8105
Report on Post-Quantum Cryptography
耐量子暗号に関する報告書
Lily Chen
Stephen Jordan
Yi-Kai Liu
Dustin Moody
Rene Peralta
Ray Perlner
Daniel Smith-Tone
Computer Security Division
Applied and Computational Mathematics Division
Information Technology Laboratory
Lily Chen
Stephen Jordan
Yi-Kai Liu
Dustin Moody
Rene Peralta
Ray Perlner
Daniel Smith-Tone
コンピュータセキュリティ部門
応用・計算数学部門
情報技術研究所
This publication is available free of charge from:
http://dx.doi.org/10.6028/NIST.IR.8105
本刊行物は、以下から無償で入手できます。
http://dx.doi.org/10.6028/NIST.IR.8105
April 2016
2016年4月
U.S. Department of Commerce
Penny Pritzker, Secretary
米国商務省
Penny Pritzker 長官
National Institute of Standards and Technology
Willie May, Under Secretary of Commerce for Standards and Technology and Director
米国国立標準技術研究所
Willie May、商務次官(標準・技術担当)兼所長
National Institute of Standards and Technology Internal Report 8105
15 pages (April 2016)
米国国立標準技術研究所 内部報告書 8105
15 ページ(2016年4月)
This publication is available free of charge from:
http://dx.doi.org/10.6028/NIST.IR.8105
本刊行物は、以下から無償で入手できます。
http://dx.doi.org/10.6028/NIST.IR.8105
Certain commercial entities, equipment, or materials may be identified in this document in order to describe an experimental procedure or concept adequately. Such identification is not intended to imply recommendation or endorsement by NIST, nor is it intended to imply that the entities, materials, or equipment are necessarily the best available for the purpose.
本書では、実験の手順や概念を適切に説明するために、特定の商業主体、機器、または資料を挙げている場合があります。こうした記載は、NIST による推奨や支持を意味するものではなく、それらの主体、資料、または機器が当該目的に必ずしも最適であることを意味するものでもありません。
There may be references in this publication to other publications currently under development by NIST in accordance with its assigned statutory responsibilities. The information in this publication, including concepts and methodologies, may be used by federal agencies even before the completion of such companion publications. Thus, until each publication is completed, current requirements, guidelines, and procedures, where they exist, remain operative. For planning and transition purposes, federal agencies may wish to closely follow the development of these new publications by NIST.
本刊行物では、NIST が法令で定められた責務に従って現在策定中の他の刊行物に言及している場合があります。本刊行物の情報(概念や方法論を含む)は、そうした関連刊行物の完成前であっても、連邦機関が使用してもよいです。したがって、各刊行物が完成するまでは、既存の要件、ガイドライン、手順がある場合は、それらが引き続き有効です。計画および移行のため、連邦機関は、NIST によるこれらの新しい刊行物の策定状況を注意深く追うことを検討してもよいです。
Organizations are encouraged to review all draft publications during public comment periods and provide feedback to NIST. Many NIST cybersecurity publications, other than the ones noted above, are available at http://csrc.nist.gov/publications.
組織は、パブリックコメント期間中にすべてのドラフト刊行物を確認し、NIST にフィードバックを提供することが推奨されています。上記以外にも、NIST のサイバーセキュリティ関連刊行物の多くが http://csrc.nist.gov/publications で公開されています。
Comments on this publication may be submitted to:
本刊行物へのコメント送付先:
National Institute of Standards and Technology
Attn: Computer Security Division, Information Technology Laboratory
100 Bureau Drive (Mail Stop 8930) Gaithersburg, MD 20899-8930
Email: NISTIR8105-comments@nist.gov
National Institute of Standards and Technology
Attn: Computer Security Division, Information Technology Laboratory
100 Bureau Drive (Mail Stop 8930) Gaithersburg, MD 20899-8930
Email: NISTIR8105-comments@nist.gov
All comments are subject to release under the Freedom of Information Act (FOIA).
すべてのコメントは、情報自由法(FOIA)に基づく公開の対象です。
Reports on Computer Systems Technology
コンピュータシステム技術に関する報告書
The Information Technology Laboratory (ITL) at the National Institute of Standards and Technology (NIST) promotes the U.S. economy and public welfare by providing technical leadership for the Nation’s measurement and standards infrastructure. ITL develops tests, test methods, reference data, proof of concept implementations, and technical analyses to advance the development and productive use of information technology. ITL’s responsibilities include the development of management, administrative, technical, and physical standards and guidelines for the cost-effective security and privacy of other than national security-related information in federal information systems.
米国国立標準技術研究所(NIST)の情報技術研究所(ITL)は、国の測定・標準のインフラに対する技術的なリーダーシップを提供することにより、米国の経済と公共の福祉を促進しています。ITL は、情報技術の開発と生産的な利用を促進するため、テスト、テスト方法、参照データ、概念実証の実装、および技術的な分析を開発しています。ITL の責務には、連邦情報システムにおける国家安全保障に関するもの以外の情報について、費用対効果の高いセキュリティとプライバシーを実現するための、管理面、運用面、技術面、物理面の標準およびガイドラインの策定が含まれます。
Abstract
概要
In recent years, there has been a substantial amount of research on quantum computers – machines that exploit quantum mechanical phenomena to solve mathematical problems that are difficult or intractable for conventional computers. If large-scale quantum computers are ever built, they will be able to break many of the public-key cryptosystems currently in use. This would seriously compromise the confidentiality and integrity of digital communications on the Internet and elsewhere. The goal of post-quantum cryptography (also called quantum-resistant cryptography) is to develop cryptographic systems that are secure against both quantum and classical computers, and can interoperate with existing communications protocols and networks. This Internal Report shares the National Institute of Standards and Technology (NIST)’s current understanding about the status of quantum computing and post-quantum cryptography, and outlines NIST’s initial plan to move forward in this space. The report also recognizes the challenge of moving to new cryptographic infrastructures and therefore emphasizes the need for agencies to focus on crypto agility.
近年、量子コンピューター、すなわち、従来のコンピューターでは困難または解決不可能な数学的問題を解くために量子力学的現象を利用するマシンについて、相当量の研究が蓄積されています。大規模な量子コンピューターが実現すれば、現在使用されている多くの公開鍵暗号システムを破ることができるようになります。これは、インターネットなどにおけるデジタル通信の機密性と完全性を深刻に危うくするおそれがあります。耐量子暗号(量子耐性暗号とも呼ばれます)の目標は、量子コンピューターと古典的なコンピューターの両方に対して安全で、既存の通信プロトコルやネットワークと相互運用できる暗号システムを開発することです。本内部報告書は、量子コンピューティングと耐量子暗号の現状についての米国国立標準技術研究所(NIST)の現在の理解を共有し、この分野で前進するための NIST の当初の計画を概説します。また本報告書は、新しい暗号基盤へ移行することの難しさも認識しており、そのため、各機関が暗号アジリティに重点を置く必要性を強調しています。
Keywords
キーワード
post-quantum cryptography; public key cryptography; quantum computing; quantum-resistant; quantum-safe.
耐量子暗号、公開鍵暗号、量子コンピューティング、量子耐性、量子安全。
Table of Contents
目次
List of Appendices
付録一覧
1 Introduction
1 序論
In the last three decades, public key cryptography has become an indispensable component of our global communication digital infrastructure. These networks support a plethora of applications that are important to our economy, our security, and our way of life, such as mobile phones, internet commerce, social networks, and cloud computing. In such a connected world, the ability of individuals, businesses and governments to communicate securely is of the utmost importance.
過去 30 年間で、公開鍵暗号は、世界の通信を支えるデジタルインフラに不可欠な構成要素となりました。これらのネットワークは、携帯電話、インターネット商取引、ソーシャルネットワーク、クラウドコンピューティングなど、私たちの経済、安全保障、生活様式にとって重要な多数のアプリケーションを支えています。このように接続された世界では、個人、事業者、政府が安全に通信できることがきわめて重要です。
Many of our most crucial communication protocols rely principally on three core cryptographic functionalities: public key encryption, digital signatures, and key exchange1. Currently, these functionalities are primarily implemented using Diffie-Hellman key exchange, the RSA (Rivest-Shamir-Adleman) cryptosystem, and elliptic curve cryptosystems. The security of these depends on the difficulty of certain number theoretic problems such as Integer Factorization or the Discrete Log Problem over various groups.
私たちの最も重要な通信プロトコルの多くは、主に 3 つの中核的な暗号機能、すなわち公開鍵暗号化、デジタル署名、鍵交換に依存しています1。現在、これらの機能は主に、Diffie-Hellman 鍵交換、RSA(Rivest-Shamir-Adleman)暗号システム、楕円曲線暗号システムを使って実装されています。これらの安全性は、整数の素因数分解や、さまざまな群上の離散対数問題といった、特定の数論的問題の困難性に依存しています。
In 1994, Peter Shor of Bell Laboratories showed that quantum computers, a new technology leveraging the physical properties of matter and energy to perform calculations, can efficiently solve each of these problems, thereby rendering all public key cryptosystems based on such assumptions impotent [1]. Thus a sufficiently powerful quantum computer will put many forms of modern communication—from key exchange to encryption to digital authentication—in peril.
1994 年に、Bell Laboratories の Peter Shor は、物質とエネルギーの物理的性質を利用して計算を行う新しい技術である量子コンピューターが、これらの問題をそれぞれ効率的に解けることを示し、そのような仮定に基づくすべての公開鍵暗号システムを無力化できることを明らかにしました [1]。したがって、十分に強力な量子コンピューターは、鍵交換から暗号化、デジタル認証に至るまで、現代の通信の多くの形態を危機にさらすことになります。
The discovery that quantum computers could be utilized to solve certain problems faster than classical computers has inspired great interest in quantum computing. Is quantum complexity fundamentally different from classical complexity? When will large-scale quantum computers be built? Is there a way to resist both a quantum and a classical computing adversary? Researchers are working on these questions.
量子コンピューターを使えば、特定の問題を古典的なコンピューターより高速に解けるという発見は、量子コンピューティングへの大きな関心を呼び起こしました。量子の計算量は、古典的な計算量と本質的に異なるのでしょうか。大規模な量子コンピューターは、いつ構築されるのでしょうか。量子計算の敵対者と古典計算の敵対者のどちらに対しても耐える方法はあるのでしょうか。研究者たちは、これらの問いに取り組んでいます。
In the twenty years since Shor’s discovery, the theory of quantum algorithms has developed significantly. Quantum algorithms achieving exponential speedup have been discovered for several problems relating to physics simulation, number theory, and topology. Nevertheless, the list of problems admitting exponential speedup by quantum computation remains relatively small. In contrast, more modest speedups have been developed for broad classes of problems related to searching, collision finding, and evaluation of Boolean formulae. In particular, Grover’s search algorithm proffers a quadratic speedup on unstructured search problems. While such a speedup does not render cryptographic technologies obsolete, it can have the effect of requiring larger key sizes, even in the symmetric key case. See Table 1 for a summary of the impact of large-scale quantum computers on common cryptographic algorithms, such as RSA and the Advanced Encryption Standard (AES). It is not known how far these quantum advantages can be pushed, nor how wide is the gap between feasibility in the classical and quantum models.
Shor の発見以来の 20 年間で、量子アルゴリズムの理論は大きく発展しました。物理シミュレーション、数論、トポロジーに関するいくつかの問題について、指数関数的な高速化を達成する量子アルゴリズムが発見されています。それでも、量子計算によって指数関数的な高速化が可能な問題の一覧は、比較的小さいままです。これに対し、探索、衝突発見、ブール式の評価に関する広範なクラスの問題については、より控えめな高速化が開発されています。特に、Grover の探索アルゴリズムは、構造を持たない探索問題に対して二次(平方)の高速化をもたらします。このような高速化によって暗号技術が時代遅れになるわけではありませんが、共通鍵の場合であっても、より大きな鍵サイズが必要になるという影響が生じる可能性があります。RSA や Advanced Encryption Standard(AES)などの一般的な暗号アルゴリズムに大規模な量子コンピューターが与える影響の概要は、表 1 を参照してください。これらの量子的な優位性をどこまで押し広げられるのか、また古典的なモデルと量子的なモデルにおける実現可能性の差がどれほどあるのかは、わかっていません。
The question of when a large-scale quantum computer will be built is complicated and contentious. While in the past it was less clear that large quantum computers are a physical possibility, many scientists now believe it to be merely a significant engineering challenge. Some experts even predict that within the next 20 or so years, sufficiently large quantum computers will be built to break essentially all public key schemes currently in use [2]. It has taken almost 20 years to deploy our modern public key cryptography infrastructure. It will take significant effort to ensure a smooth and secure migration from the current widely used cryptosystems to their quantum computing resistant counterparts. Therefore, regardless of whether we can estimate the exact time of the arrival of the quantum computing era, we must begin now to prepare our information security systems to be able to resist quantum computing.
大規模な量子コンピューターがいつ構築されるのかという問題は、複雑で議論の的となっています。以前は、大きな量子コンピューターが物理的に可能かどうかがそれほど明らかではありませんでしたが、現在では多くの科学者が、それは単に大きな工学的課題にすぎないと考えています。専門家の中には、今後 20 年ほどのうちに、現在使用されているほぼすべての公開鍵方式を破れるだけの十分に大きな量子コンピューターが構築されると予測する人もいます [2]。現代の公開鍵暗号基盤を展開するには、ほぼ 20 年を要しました。現在広く使用されている暗号システムから、量子コンピューティングに耐性のある対応するものへ、円滑かつ安全に移行するには、相当の労力が必要になります。したがって、量子コンピューティング時代の到来時期を正確に見積もれるかどうかにかかわらず、量子コンピューティングに耐えられるよう情報セキュリティシステムの準備を今から始めなければなりません。
Table 1 - Impact of Quantum Computing on Common Cryptographic Algorithms
表 1 - 量子コンピューティングが一般的な暗号アルゴリズムに与える影響
| Cryptographic Algorithm | Type | Purpose | Impact from large-scale quantum computer |
|---|---|---|---|
| AES | Symmetric key | Encryption | Larger key sizes needed |
| SHA-2, SHA-3 | --------------- | Hash functions | Larger output needed |
| RSA | Public key | Signatures, key establishment | No longer secure |
| ECDSA, ECDH (Elliptic Curve Cryptography) | Public key | Signatures, key exchange | No longer secure |
| DSA (Finite Field Cryptography) | Public key | Signatures, key exchange | No longer secure |
| 暗号アルゴリズム | 種類 | 目的 | 大規模な量子コンピューターによる影響 |
|---|---|---|---|
| AES | 共通鍵 | 暗号化 | より大きな鍵サイズが必要 |
| SHA-2, SHA-3 | --------------- | ハッシュ関数 | より大きな出力が必要 |
| RSA | 公開鍵 | 署名、鍵確立 | もはや安全ではない |
| ECDSA, ECDH (楕円曲線暗号) | 公開鍵 | 署名、鍵交換 | もはや安全ではない |
| DSA (有限体暗号) | 公開鍵 | 署名、鍵交換 | もはや安全ではない |
A large international community has emerged to address the issue of information security in a quantum computing future, in the hope that our public key infrastructure may remain intact by utilizing new quantum-resistant primitives. In the academic world, this new science bears the name “Post-Quantum Cryptography2.” This is an active area of research, with its own conference series, PQCrypto, which started in 2006. It has received substantial support from national funding agencies, most notably in Europe and Japan, through the European Union (EU) projects PQCrypto and SAFEcrypto, and the CREST Crypto-Math project in Japan.
量子コンピューティングの未来における情報セキュリティの問題に取り組むため、大規模な国際コミュニティが生まれました。新たな量子耐性のプリミティブを利用することで、公開鍵基盤を損なわずに維持できるようにすることを目指しています。学術界では、この新しい科学は「耐量子暗号2」と呼ばれています。これは活発な研究分野であり、2006 年に始まった独自の会議シリーズ PQCrypto があります。また、国の資金提供機関、特に欧州と日本から、欧州連合(EU)のプロジェクト PQCrypto と SAFEcrypto、日本の CREST 暗号数理プロジェクトを通じて、相当の支援を受けています。
These efforts have led to advances in fundamental research, paving the way for the deployment of post-quantum cryptosystems in the real world. In the past few years, industry and standards organizations have started their own activities in this field: since 2013, the European Telecommunications Standards Institute (ETSI) has held three “Quantum-Safe Cryptography" workshops, and in 2015 NIST held a workshop on “Cybersecurity in a Post-Quantum World,” which was attended by over 140 people from government, industry, and academia.
これらの取り組みにより、基礎研究が進展し、耐量子暗号システムを現実世界に展開するための道が開かれました。この数年間で、産業界や標準化団体もこの分野で独自の活動を始めています。2013 年以降、欧州電気通信標準化機構(ETSI)は 3 回の「Quantum-Safe Cryptography」ワークショップを開催しており、2015 年には NIST が「Cybersecurity in a Post-Quantum World」ワークショップを開催し、政府、産業界、学術界から 140 人以上が参加しました。
NIST has a unique role to play in standardizing post-quantum cryptography, as part of its broader responsibility for the development of standards and guidelines for the protection of non-national-security federal information systems. Many NIST standards, such as the Advanced Encryption Standard (AES), have been developed with broad participation from academia and industry, and have been widely adopted because they are effective solutions, thus helping to protect U.S. information and information systems. NIST standardization of post-quantum cryptography will likely provide similar benefits.
NIST は、国家安全保障に関するもの以外の連邦情報システムを保護するための標準とガイドラインの策定に対する、より広範な責任の一環として、耐量子暗号の標準化において固有の役割を担っています。Advanced Encryption Standard(AES)など、NIST の多くの標準は、学術界と産業界の幅広い参加を得て策定され、効果的な解決策であるため広く採用されており、米国の情報と情報システムの保護に役立っています。NIST による耐量子暗号の標準化も、同様の恩恵をもたらす可能性が高いです。
Considering all of these sources, it is clear that the effort to develop quantum-resistant technologies is intensifying. Equally clear is the urgency, implied by these investments, of the need for standardizing new post-quantum public key cryptography. It is critical to engage with the community for NIST cryptographic standards to be endorsed by industry and other standards organizations around the world. This Internal Report shares NIST’s current understanding about the status of quantum computing and post-quantum cryptography, and outlines our initial plan to move forward.
これらすべての情報源を考慮すると、量子耐性技術を開発する取り組みが強まっていることは明らかです。これらの投資が示唆するように、新しい耐量子公開鍵暗号を標準化する必要性が差し迫っていることも同様に明らかです。NIST の暗号標準が産業界や世界中のほかの標準化団体に支持されるためには、コミュニティと連携することが重要です。本内部報告書は、量子コンピューティングと耐量子暗号の現状についての NIST の現在の理解を共有し、前進するための当初の計画を概説します。
2 An Overview of Quantum-Resistant Cryptography
2 量子耐性暗号の概要
The most important uses of public key cryptography today are for digital signatures and key establishment. As mentioned in Section 1, the construction of a large-scale quantum computer would render many of these public key cryptosystems insecure. In particular, this includes those based on the difficulty of integer factorization, such as RSA, as well as ones based on the hardness of the discrete log problem. In contrast, the impact on symmetric key systems will not be as drastic (see Table 1). Grover’s algorithm provides a quadratic speed-up for quantum search algorithms in comparison with search algorithms on classical computers. We don’t know that Grover’s algorithm will ever be practically relevant, but if it is, doubling the key size will be sufficient to preserve security. Furthermore, it has been shown that an exponential speed up for search algorithms is impossible, suggesting that symmetric algorithms and hash functions should be usable in a quantum era [3].
現在の公開鍵暗号の最も重要な用途は、デジタル署名と鍵確立です。第 1 節で述べたとおり、大規模な量子コンピューターが構築されると、これらの公開鍵暗号システムの多くが安全でなくなります。特に、RSA など、整数の素因数分解の困難性に基づくものや、離散対数問題の困難性に基づくものが該当します。これに対し、共通鍵システムへの影響はそれほど深刻ではありません(表 1 を参照)。Grover のアルゴリズムは、古典的なコンピューター上の探索アルゴリズムと比べて、量子探索アルゴリズムに 2 次の高速化をもたらします。Grover のアルゴリズムが実際に意味を持つかどうかはわかっていませんが、もしそうなった場合でも、鍵サイズを 2 倍にすれば安全性を維持するのに十分です。さらに、探索アルゴリズムの指数関数的な高速化は不可能であることが示されており、共通鍵アルゴリズムとハッシュ関数は量子時代でも使用できるはずであることが示唆されています [3]。
Consequently, the search for algorithms believed to be resistant to attacks from both classical and quantum computers has focused on public key algorithms. In this section, we briefly give an overview of the main families for which post-quantum primitives have been proposed. These families include those based on lattices, codes, and multivariate polynomials, as well as a handful of others. For further information, see [4, 5].
その結果、古典的なコンピューターと量子コンピューターの両方からの攻撃に耐えると考えられるアルゴリズムの探索は、公開鍵アルゴリズムに集中してきました。本節では、耐量子プリミティブが提案されている主要なファミリーを簡単に概説します。これらのファミリーには、格子、符号、多変数多項式に基づくものと、そのほかのいくつかのものが含まれます。詳細は [4, 5] を参照してください。
Lattice-based cryptography – Cryptosystems based on lattice problems have received renewed interest, for a few reasons. Exciting new applications (such as fully homomorphic encryption, code obfuscation, and attribute-based encryption) have been made possible using lattice-based cryptography. Most lattice-based key establishment algorithms are relatively simple, efficient, and highly parallelizable. Also, the security of some lattice-based systems are provably secure under a worst-case hardness assumption, rather than on the average case. On the other hand, it has proven difficult to give precise estimates of the security of lattice schemes against even known cryptanalysis techniques.
格子ベースの暗号 – 格子問題に基づく暗号システムは、いくつかの理由から、改めて関心を集めています。格子ベースの暗号を使うことで、(完全準同型暗号、コード難読化、属性ベース暗号などの)刺激的な新しい応用が可能になりました。格子ベースの鍵確立アルゴリズムの多くは、比較的単純で効率的であり、並列化が非常に容易です。また、格子ベースのシステムの一部は、平均的な場合ではなく最悪の場合の困難性の仮定のもとで、証明可能な安全性を持ちます。その一方で、既知の暗号解読手法に対してさえ、格子方式の安全性を正確に見積もることは困難であることが明らかになっています。
Code-based cryptography – In 1978, the McEliece cryptosystem was first proposed, and has not been broken since. Since that time, other systems based on error-correcting codes have been proposed. While quite fast, most code-based primitives suffer from having very large key sizes. Newer variants have introduced more structure into the codes in an attempt to reduce the key sizes, however the added structure has also led to successful attacks on some proposals. While there have been some proposals for code-based signatures, code-based cryptography has seen more success with encryption schemes.
符号ベースの暗号 – 1978 年に McEliece 暗号システムが初めて提案され、それ以来破られていません。それ以降、誤り訂正符号に基づくほかのシステムも提案されてきました。非常に高速ではあるものの、符号ベースのプリミティブの多くは、鍵サイズが非常に大きいという欠点があります。より新しい変種は、鍵サイズを小さくしようとして符号により多くの構造を導入しましたが、その追加された構造は、一部の提案に対する攻撃の成功にもつながっています。符号ベースの署名にはいくつかの提案がありますが、符号ベースの暗号は、暗号化方式でより大きな成功を収めてきました。
Multivariate polynomial cryptography – These schemes are based on the difficulty of solving systems of multivariate polynomials over finite fields. Several multivariate cryptosystems have been proposed over the past few decades, with many having been broken [6]. While there have been some proposals for multivariate encryption schemes, multivariate cryptography has historically been more successful as an approach to signatures.
多変数多項式暗号 – これらの方式は、有限体上の多変数多項式の連立方程式を解くことの困難性に基づいています。過去数十年の間に、いくつかの多変数暗号システムが提案されてきましたが、その多くは破られています [6]。多変数の暗号化方式にはいくつかの提案がありますが、多変数暗号は歴史的に、署名へのアプローチとしてより成功してきました。
Hash-based signatures – Hash-based signatures are digital signatures constructed using hash functions. Their security, even against quantum attacks, is well understood. Many of the more efficient hash-based signature schemes have the drawback that the signer must keep a record of the exact number of previously signed messages, and any error in this record will result in insecurity. Another drawback is that they can produce only a limited number of signatures. The number of signatures can be increased, even to the point of being effectively unlimited, but this also increases the signature size.
ハッシュベースの署名 – ハッシュベースの署名は、ハッシュ関数を使って構成されるデジタル署名です。量子攻撃に対しても、その安全性はよく理解されています。より効率的なハッシュベースの署名方式の多くには、署名者が、それまでに署名したメッセージの正確な数の記録を保持しなければならず、この記録に誤りがあれば安全でなくなるという欠点があります。もう 1 つの欠点は、生成できる署名の数が限られていることです。署名の数は、事実上無制限になるところまで増やせますが、そうすると署名のサイズも大きくなります。
Other - A variety of systems have been proposed which do not fall into the above families. One such proposal is based on evaluating isogenies on supersingular elliptic curves. While the discrete log problem on elliptic curves can be efficiently solved by Shor’s algorithm on a quantum computer, the isogeny problem on supersingular curves has no similar quantum attack known. Like some other proposals, for example those based on the conjugacy search problem and related problems in braid groups, there has not been enough analysis to have much confidence in their security.
その他 - 上記のファミリーのいずれにも当てはまらないさまざまなシステムが提案されています。その 1 つは、超特異楕円曲線上の同種写像の評価に基づくものです。楕円曲線上の離散対数問題は、量子コンピューター上の Shor のアルゴリズムで効率的に解けますが、超特異曲線上の同種写像問題には、同様の量子攻撃は知られていません。たとえば、ブレイド群における共役探索問題と関連する問題に基づくものなど、ほかのいくつかの提案と同様に、その安全性に十分な確信を持てるだけの分析が行われていません。
It seems improbable that any of the currently known algorithms can serve as a drop-in replacement for what is in use today. One challenge that will likely need to be overcome is that most of the quantum-resistant algorithms have larger key sizes than the algorithms they will replace. This may result in needing to change various Internet protocols, such as the Transport Layer Security (TLS) protocol, or the Internet Key Exchange (IKE). The ways in which this should be done must be carefully considered.
現在知られているアルゴリズムのいずれかが、現在使用されているものをそのまま置き換えられるもの(ドロップイン置換)になるとは考えにくいです。克服する必要が生じる可能性が高い課題の 1 つは、量子耐性アルゴリズムの多くが、置き換える対象のアルゴリズムより鍵サイズが大きいことです。その結果、Transport Layer Security(TLS)プロトコルや Internet Key Exchange(IKE)など、さまざまなインターネットプロトコルの変更が必要になる可能性があります。その方法は、慎重に検討しなければなりません。
We note that none of the above proposals have been shown to guarantee security against all quantum attacks. A new quantum algorithm may be discovered which breaks some of these schemes. However, this is similar to the state today. Although most public key cryptosystems come with a security proof, these proofs are based on unproven assumptions. Thus the lack of known attacks is used to justify the security of public key cryptography currently in use. Nonetheless, NIST believes that more research and analysis are needed before any of the above proposed post-quantum algorithms could be recommended for use today. They have not received nearly as much scrutiny from the cryptographic community as the currently deployed algorithms. One exception is hash-based signatures, whose security is well-understood. For certain specific applications, such as digital code signing, hash-based signatures could potentially be standardized in the next few years.
上記の提案のいずれについても、あらゆる量子攻撃に対して安全性が保証されることは示されていない点に注意します。これらの方式の一部を破る新しい量子アルゴリズムが発見されるかもしれません。しかし、これは現在の状況と似ています。ほとんどの公開鍵暗号システムには安全性の証明が付いていますが、それらの証明は未証明の仮定に基づいています。したがって、現在使用されている公開鍵暗号の安全性は、既知の攻撃がないことによって正当化されています。それでも NIST は、上記の提案された耐量子アルゴリズムのいずれかを現時点での使用に推奨できるようになるには、さらなる研究と分析が必要であると考えています。これらは、現在展開されているアルゴリズムほどには、暗号コミュニティから精査されていません。例外の 1 つがハッシュベースの署名で、その安全性はよく理解されています。コード署名などの特定の用途については、ハッシュベースの署名が今後数年のうちに標準化される可能性があります。
3 Progress in Quantum Computing Hardware
3 量子コンピューティングハードウェアの進展
Research into the feasibility of building large-scale quantum computers began in earnest after Peter Shor’s 1994 discovery of a polynomial-time quantum algorithm for integer factorization [1]. At the time, it was unclear whether quantum computing would ever be a fundamentally scalable technology. Many leading experts suggested that quantum states were too fragile and subject to the accumulation of error for large-scale quantum computation ever to be realized. This situation changed in the late 1990s with the development of quantum error correcting codes and threshold theorems [7]. These threshold theorems show that if the error rate per logical operation (“quantum gate”) in a quantum computer can be brought below a fixed threshold then arbitrarily long quantum computations can be carried out in a reliable and fault-tolerant manner by incorporating error-correction steps throughout the execution of the quantum computation [8].
大規模な量子コンピューターを構築できるかどうかの研究は、1994 年に Peter Shor が整数の素因数分解に対する多項式時間の量子アルゴリズムを発見した後に、本格的に始まりました [1]。当時は、量子コンピューティングが根本的にスケーラブルな技術になるかどうかは不明でした。多くの第一線の専門家は、量子状態はもろすぎ、誤りの蓄積を受けやすいため、大規模な量子計算が実現されることはないと示唆していました。この状況は、1990 年代後半に量子誤り訂正符号としきい値定理が開発されたことで変わりました [7]。これらのしきい値定理は、量子コンピューターにおける論理演算(「量子ゲート」)ごとの誤り率を一定のしきい値より低くできれば、量子計算の実行全体にわたって誤り訂正のステップを組み込むことで、任意の長さの量子計算を、信頼性があり耐故障性のある方法で実行できることを示しています [8]。
Over the years, experimentalists have gradually developed improved hardware with ever lower error rates per quantum gate. Simultaneously, theorists have developed new quantum error correction procedures yielding higher fault-tolerance thresholds. Recently, some experiments using ion traps and superconducting circuits have demonstrated universal sets of quantum gates that are nominally below the highest theoretical fault-tolerance thresholds (around 1 %) [9, 10]. This is a significant milestone, which has spurred increased investment from both government and industry. However, it is clear that substantial long-term efforts are needed to move from present-day laboratory demonstrations involving a few qubits up to large-scale quantum computers involving thousands of logical qubits encoded in perhaps hundreds of thousands or millions of physical qubits.
長年にわたり、実験家たちは、量子ゲートごとの誤り率がますます低いハードウェアを少しずつ改良してきました。同時に、理論家たちは、より高い耐故障性のしきい値をもたらす新しい量子誤り訂正手順を開発しました。最近では、イオントラップと超伝導回路を用いたいくつかの実験が、理論上の最高の耐故障性のしきい値(約 1 %)を名目上は下回る、量子ゲートの万能集合を実証しました [9, 10]。これは重要なマイルストーンであり、政府と産業界の双方からの投資の増加を促しました。しかし、数量子ビットを扱う現在の実験室での実証から、数十万個や数百万個の物理量子ビットに符号化された数千個の論理量子ビットを扱う大規模な量子コンピューターへ進むには、相当の長期的な取り組みが必要であることは明らかです。
In parallel to the development of general-purpose digital quantum computers, there have been efforts to develop special purpose analog quantum computers, such as quantum annealers (e.g. the D-Wave machine), analog quantum simulators, and boson sampling devices. Some of these devices have been scaled up to far larger numbers of qubits than digital quantum computers have. However, due to their specialized nature, these analog quantum devices are not believed to be of relevance to cryptanalysis.
汎用のデジタル量子コンピューターの開発と並行して、量子アニーラー(たとえば D-Wave のマシン)、アナログ量子シミュレーター、ボソンサンプリング装置など、特殊用途のアナログ量子コンピューターを開発する取り組みもありました。これらの装置の一部は、デジタル量子コンピューターよりもはるかに多い量子ビット数まで拡張されています。しかし、その特殊な性質のため、これらのアナログ量子装置は暗号解読には関係しないと考えられています。
4 The Path Forward
4 今後の進め方
The need for stronger cryptography is driven by advances in both classical and quantum computing technologies. To maintain security against classical attacks, NIST has already recommended transitions from key sizes and algorithms that provide 80 bits of security, to key sizes and algorithms that provide 112 or 128 bits of security [SP 800-131A]. To provide security against quantum attacks, NIST will have to facilitate a more difficult transition, to new post-quantum cryptosystems.
より強力な暗号が必要になっているのは、古典的なコンピューティング技術と量子コンピューティング技術の双方が進歩しているためです。古典的な攻撃に対する安全性を維持するため、NIST はすでに、80 ビットのセキュリティを提供する鍵サイズとアルゴリズムから、112 ビットまたは 128 ビットのセキュリティを提供する鍵サイズとアルゴリズムへの移行を推奨しています [SP 800-131A]。量子攻撃に対する安全性を提供するため、NIST は、新しい耐量子暗号システムへの、より困難な移行を促進しなければなりません。
It is unclear when scalable quantum computers will be available. However, in the past year or so, researchers working on building a quantum computer have estimated that it is likely that a quantum computer capable of breaking 2000-bit RSA in a matter of hours could be built by 2030 for a budget of about a billion dollars [11]. This is a serious long-term threat to the cryptosystems currently standardized by NIST.
スケーラブルな量子コンピューターがいつ利用可能になるかは不明です。しかし、過去 1 年ほどの間に、量子コンピューターの構築に取り組む研究者は、2000 ビットの RSA を数時間で破れる量子コンピューターが、約 10 億ドルの予算で 2030 年までに構築される可能性が高いと見積もっています [11]。これは、現在 NIST が標準化している暗号システムにとって、長期的な深刻な脅威です。
It is useful to compare the above predictions with the cost of breaking these cryptosystems using classical computers. Cryptosystems offering 80 bits of security or less, which were phased out in 2011-2013, are at the greatest risk: they can be broken now at a cost ranging from tens of thousands to hundreds of millions of dollars [12, 13, 14, 15]. Cryptosystems offering 112 bits of security are likely to remain secure for some time: they may be breakable for a budget of a billion dollars in 30 to 40 years3 (using classical computers).
上記の予測を、古典的なコンピューターでこれらの暗号システムを破るためのコストと比較すると有用です。2011 年から 2013 年にかけて段階的に廃止された、80 ビット以下のセキュリティを提供する暗号システムは、最大のリスクにさらされています。これらは現在でも、数万ドルから数億ドルのコストで破ることができます [12, 13, 14, 15]。112 ビットのセキュリティを提供する暗号システムは、しばらくの間は安全なままである可能性が高いです。古典的なコンピューターを使う場合、30 年から 40 年後には、10 億ドルの予算で破れる可能性があります³。
Thus, transitioning from 112 to 128 (or higher) bits of security is perhaps less urgent than transitioning from existing cryptosystems to post-quantum cryptosystems. This post-quantum transition raises many fundamental challenges.
したがって、112 ビットから 128 ビット(またはそれ以上)のセキュリティへの移行は、既存の暗号システムから耐量子暗号システムへの移行ほど差し迫ってはいないかもしれません。この耐量子への移行には、多くの根本的な課題があります。
Previous transitions from weaker to stronger cryptography have been based on the bits-of-security paradigm, which measures the security of an algorithm based on the time-complexity of attacking it with a classical computer (e.g. an algorithm is said to have 128 bits of security if the difficulty of attacking it with a classical computer is comparable to the time and resources required to brute-force search for a 128-bit cryptographic key.) NIST Special Publication (SP) 800-57 Part 1 [SP800-57] classifies the algorithms standardized by NIST as of January 2016 into 80, 112, 128, 192 and 256 bits of security. It further recommended that the 80-bit security level is no longer considered sufficiently secure, and the 112-bit security level be phased out by 2031.
より弱い暗号からより強い暗号への過去の移行は、ビットのセキュリティというパラダイムに基づいていました。これは、アルゴリズムの安全性を、古典的なコンピューターでそれを攻撃する際の時間計算量に基づいて測るものです(たとえば、古典的なコンピューターによる攻撃の困難さが、128 ビットの暗号鍵を総当たりで探索するのに必要な時間と資源に匹敵する場合、そのアルゴリズムは 128 ビットのセキュリティを持つと言われます)。NIST Special Publication(SP)800-57 Part 1 [SP800-57] は、2016年1月時点で NIST が標準化しているアルゴリズムを、80、112、128、192、256 ビットのセキュリティに分類しています。同書はさらに、80 ビットのセキュリティレベルはもはや十分に安全とは見なされないこと、112 ビットのセキュリティレベルは 2031 年までに段階的に廃止することを推奨しています。
Unfortunately, the bits-of-security paradigm does not take into account the security of algorithms against quantum cryptanalysis, so it is inadequate to guide our transition to quantum-resistant cryptography. There is not yet a consensus view on what key lengths will provide acceptable levels of security against quantum attacks. For symmetric key systems, one simple heuristic is to double the key lengths to compensate for the quadratic speedup achieved by Grover’s algorithm. But this recommendation may be overly conservative, as quantum computing hardware will likely be more expensive to build than classical hardware. At the same time, this recommendation does not take into account the possibility of more sophisticated quantum attacks [16, 17, 18]. Our understanding of quantum cryptanalysis remains rather limited, and more research in this area is urgently needed.
残念ながら、ビットのセキュリティというパラダイムは、量子暗号解読に対するアルゴリズムの安全性を考慮していないため、量子耐性暗号への移行の指針としては不十分です。量子攻撃に対して許容できるレベルの安全性をどの鍵長が提供するかについては、まだ合意された見解がありません。共通鍵システムについては、Grover のアルゴリズムによって達成される 2 次の高速化を補うために鍵長を 2 倍にするという単純な経験則が 1 つあります。しかし、量子コンピューティングハードウェアは古典的なハードウェアより構築に費用がかかる可能性が高いため、この推奨は過度に保守的かもしれません。同時に、この推奨は、より高度な量子攻撃の可能性を考慮していません [16, 17, 18]。量子暗号解読に関する私たちの理解はまだかなり限られており、この分野でのさらなる研究が急務です。
The development of standards for post-quantum cryptography will require significant resources to analyze candidate quantum-resistant schemes, and will require significant public engagement to assure trust in the algorithms NIST chooses to standardize. Interest in the areas of quantum computing and quantum-resistant cryptography has recently increased, due to milestones in the development of quantum computing hardware and the National Security Agency’s (NSA) recent changes to its Suite B guidance [19]. This provides an opportunity for engagement with the research community that may not come again before practical quantum computing is truly imminent. Consequently, NIST is beginning to prepare for the transition to quantum-resistant cryptography now.
耐量子暗号の標準の策定には、量子耐性方式の候補を分析するための相当の資源が必要であり、NIST が標準化するアルゴリズムへの信頼を確保するため、一般からの幅広い参加が必要です。量子コンピューティングと量子耐性暗号の分野への関心は、量子コンピューティングハードウェアの開発における節目と、国家安全保障局(NSA)による Suite B ガイダンスの最近の変更 [19] により、近年高まっています。これは、実用的な量子コンピューティングが真に差し迫る前に、再び訪れないかもしれない、研究コミュニティと連携する機会を提供します。したがって、NIST は今から、量子耐性暗号への移行の準備を始めています。
NIST is taking the following steps to initiate a standardization effort in post-quantum cryptography. NIST plans to specify preliminary evaluation criteria for quantum-resistant public key cryptography standards. The criteria will include security and performance requirements. The draft criteria will be released for public comments in 2016 and hopefully finalized by the end of the year. At that time NIST will begin accepting proposals for quantum-resistant public key encryption, digital signature, and key exchange algorithms. NIST intends to select at least one algorithm providing each of these functionalities for standardization. NIST will establish a submission deadline late in 2017 for algorithms to be considered, allowing the proposals to be subject to 3 to 5 years of public scrutiny before they are standardized.
NIST は、耐量子暗号の標準化の取り組みを開始するため、次の手順を進めています。NIST は、量子耐性公開鍵暗号標準の予備的な評価基準を規定する計画です。この基準には、セキュリティ要件と性能要件が含まれます。基準のドラフトは、2016 年にパブリックコメント向けに公開され、年末までに確定することが望まれます。その時点で NIST は、量子耐性の公開鍵暗号、デジタル署名、鍵交換のアルゴリズムの提案の受け付けを開始します。NIST は、これらの機能のそれぞれを提供するアルゴリズムを、少なくとも 1 つ標準化のために選定するつもりです。NIST は、検討対象とするアルゴリズムの提出期限を 2017 年後半に設定し、標準化される前に、提案が 3 年から 5 年にわたる公開の精査を受けられるようにします。
While this process will have many commonalities with the processes that led to the standardization of AES [20] and SHA3 [21], this is not a competition. NIST sees its role as managing a process of achieving community consensus in a transparent and timely manner. Ideally, several algorithms will emerge as “good choices.” NIST may pick one or more of these for standardization in each category. In this respect, NIST’s process for standardizing quantum-resistant public key cryptography will be similar to the ongoing block cipher modes development process [22].
このプロセスには、AES [20] や SHA3 [21] の標準化につながったプロセスと多くの共通点がありますが、これはコンペティションではありません。NIST は、自らの役割を、透明で適時な形でコミュニティの合意を得るプロセスを管理することと考えています。理想的には、複数のアルゴリズムが「良い選択肢」として浮かび上がります。NIST は、各カテゴリーでそれらのうち 1 つ以上を標準化のために選ぶ場合があります。この点で、量子耐性公開鍵暗号を標準化するための NIST のプロセスは、進行中のブロック暗号の動作モードの策定プロセス [22] に似たものになります。
When standards for quantum-resistant public key cryptography become available, NIST will reassess the imminence of the threat of quantum computers to existing standards, and may decide to deprecate or withdraw the affected standards thereafter as a result. Agencies should therefore be prepared to transition away from these algorithms as early as 10 years from now. As the replacements for currently standardized public key algorithms are not yet ready, a focus on maintaining crypto agility is imperative. Until new quantum-resistant algorithms are standardized, agencies should continue to use the recommended algorithms currently specified in NIST standards.
量子耐性公開鍵暗号の標準が利用可能になった時点で、NIST は、量子コンピューターが既存の標準にもたらす脅威の切迫度を再評価し、その結果として、影響を受ける標準を以後に非推奨とする、または廃止することを決定する場合があります。したがって、各機関は、早ければ今から 10 年後にはこれらのアルゴリズムから移行できるよう準備しておくべきです。現在標準化されている公開鍵アルゴリズムに代わるものがまだ準備できていないため、暗号アジリティの維持に重点を置くことが不可欠です。新しい量子耐性アルゴリズムが標準化されるまでは、各機関は、現在 NIST の標準で規定されている推奨アルゴリズムを引き続き使用すべきです。
Appendix A—References
付録 A—参考文献
[FIPS 186-4] Federal Information Processing Standards (FIPS) 186-4, Digital Signature Standard (DSS), National Institute of Standards and Technology, Gaithersburg, Maryland, July 2013, 130pp. http://dx.doi.org/10.6028/nist.fips.186-4.
[FIPS 186-4] Federal Information Processing Standards (FIPS) 186-4, Digital Signature Standard (DSS), National Institute of Standards and Technology, Gaithersburg, Maryland, 2013年7月, 130pp. http://dx.doi.org/10.6028/nist.fips.186-4.
[SP800-56A] NIST Special Publication (SP) 800-56A Revision 2, Recommendations for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography, National Institute of Standards and Technology, Gaithersburg, Maryland, May 2013, 138pp. http://dx.doi.org/10.6028/nist.sp.800-56ar2.
[SP800-56A] NIST Special Publication (SP) 800-56A Revision 2, Recommendations for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography, National Institute of Standards and Technology, Gaithersburg, Maryland, 2013年5月, 138pp. http://dx.doi.org/10.6028/nist.sp.800-56ar2.
[SP800-56B] NIST Special Publication (SP) 800-56B Revision 1, Recommendations for Pair-Wise Key-Establishment Schemes Using Integer Factorization Cryptography, National Institute of Standards and Technology, Gaithersburg, Maryland, September 2014, 131p. http://dx.doi.org/10.6028/nist.sp.800-56br1.
[SP800-56B] NIST Special Publication (SP) 800-56B Revision 1, Recommendations for Pair-Wise Key-Establishment Schemes Using Integer Factorization Cryptography, National Institute of Standards and Technology, Gaithersburg, Maryland, 2014年9月, 131p. http://dx.doi.org/10.6028/nist.sp.800-56br1.
[1] 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.
[1] 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.
[2] 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.
[2] 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.
[3] 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
[3] 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
[4] 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 [accessed 4/15/2016].
[4] European Telecommunications Standards Institute White Paper No. 8, Quantum Safe Cryptography and Security: An Introduction, Benefits, Enablers and Challenges, 2015年6月. https://portal.etsi.org/Portals/0/TBpages/QSC/Docs/Quantum_Safe_Whitepaper_1_0_0.pdf [2016年4月15日にアクセス].
[5] 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.
[5] 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.
[6] 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.
[6] 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.
[7] J. Preskill, Reliable Quantum Computers, Proc. Roy. Soc. London A, 454, 1998, pp. 385–410. http://dx.doi.org/10.1098/rspa.1998.0167.
[7] J. Preskill, Reliable Quantum Computers, Proc. Roy. Soc. London A, 454, 1998, pp. 385–410. http://dx.doi.org/10.1098/rspa.1998.0167.
[8] D. Lidar, T. Brun, eds., Quantum Error Correction, Cambridge University Press, 2013. http://dx.doi.org/10.1017/cbo9781139034807.
[8] D. Lidar, T. Brun, eds., Quantum Error Correction, Cambridge University Press, 2013. http://dx.doi.org/10.1017/cbo9781139034807.
[9] 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.
[9] 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.
[10] 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.
[10] 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.
[SP 800-131A] 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.
[SP 800-131A] 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, 2015年11月, 23pp. http://dx.doi.org/10.6028/nist.sp.800-131ar1.
[11] M. Mariantoni, Building a Superconducting Quantum Computer, Invited Talk PQCrypto 2014, October 2014 Waterloo, Canada. https://www.youtube.com/watch?v=wWHAs--HA1c [accessed 4/20/2016].
[11] M. Mariantoni, Building a Superconducting Quantum Computer, Invited Talk PQCrypto 2014, 2014年10月 Waterloo, Canada. https://www.youtube.com/watch?v=wWHAs--HA1c [2016年4月20日にアクセス].
[12] A. Lenstra, E. Tromer, A. Shamir, W. Kortsmit, B. Dodson, J. Hughes, P. Leyland, Factoring Estimates for a 1024-bit RSA Modulus, Advances in Cryptology - ASIACRYPT 2003, Lecture Notes in Comput. Sci. 2894, Springer-Verlag, 2003, pp. 55–74. http://dx.doi.org/10.1007/978-3-540-40061-5_4.
[12] A. Lenstra, E. Tromer, A. Shamir, W. Kortsmit, B. Dodson, J. Hughes, P. Leyland, Factoring Estimates for a 1024-bit RSA Modulus, Advances in Cryptology - ASIACRYPT 2003, Lecture Notes in Comput. Sci. 2894, Springer-Verlag, 2003, pp. 55–74. http://dx.doi.org/10.1007/978-3-540-40061-5_4.
[13] M. Stevens, P. Karpman, T Peyrin, Freestart Collision on Full SHA-1, IACR Cryptology ePrint Archive 2015/967, 2015. http://eprint.iacr.org/2015/967.
[13] M. Stevens, P. Karpman, T Peyrin, Freestart Collision on Full SHA-1, IACR Cryptology ePrint Archive 2015/967, 2015. http://eprint.iacr.org/2015/967.
[14] J. Bos, M. Kaihara, T. Kleinjung, A. Lenstra, P. Montgomery, On the security of 1024-bit RSA and 160-bit Elliptic Curve Cryptography, IACR Cryptology ePrint Archive 2009/389, 2009. http://eprint.iacr.org/2009/389.
[14] J. Bos, M. Kaihara, T. Kleinjung, A. Lenstra, P. Montgomery, On the security of 1024-bit RSA and 160-bit Elliptic Curve Cryptography, IACR Cryptology ePrint Archive 2009/389, 2009. http://eprint.iacr.org/2009/389.
[15] D. Adrian, K. Bhargavan, Z. Durumeric, P. Gaudry, M. Green, J. A. Halderman, N. Heninger, D. Springall, E. Thomé, L. Valenta, B. VanderSloot, E. Wustrow, S. Zanella-Béguelin, P. Zimmermann, Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice, in: Proc. of the 22nd ACM Conference on Computer and Communications Security, Oct. 2015. http://dx.doi.org/10.1145/2810103.2813707.
[15] D. Adrian, K. Bhargavan, Z. Durumeric, P. Gaudry, M. Green, J. A. Halderman, N. Heninger, D. Springall, E. Thomé, L. Valenta, B. VanderSloot, E. Wustrow, S. Zanella-Béguelin, P. Zimmermann, Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice, in: Proc. of the 22nd ACM Conference on Computer and Communications Security, 2015年10月. http://dx.doi.org/10.1145/2810103.2813707.
[SP 800-57] 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.
[SP 800-57] 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, 2016年1月, 160pp. http://dx.doi.org/10.6028/NIST.SP.800-57pt1r4.
[16] 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.
[16] 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.
[17] 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.
[17] 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.
[18] 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.
[18] 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.
[19] 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/cnsa-suite.cfm.
[19] National Security Agency, Cryptography Today, report, 2015年8月. https://www.nsa.gov/ia/programs/suiteb_cryptography/ [2016年4月20日にアクセス]. 別の入手先: https://www.iad.gov/iad/programs/iad-initiatives/cnsa-suite.cfm.
[20] NIST, AES Competition [Web page], http://csrc.nist.gov/archive/aes/.
[20] NIST, AES Competition [Web page], http://csrc.nist.gov/archive/aes/.
[21] NIST, SHA-3 Competition [Web page], http://csrc.nist.gov/groups/ST/hash/sha-3/.
[21] NIST, SHA-3 Competition [Web page], http://csrc.nist.gov/groups/ST/hash/sha-3/.
[22] NIST, Modes Development [Web page], http://csrc.nist.gov/groups/ST/toolkit/BCM/modes_development.html.
[22] NIST, Modes Development [Web page], http://csrc.nist.gov/groups/ST/toolkit/BCM/modes_development.html.