-
Notifications
You must be signed in to change notification settings - Fork 1
/
post-q.tex.2
371 lines (246 loc) · 18.4 KB
/
post-q.tex.2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
\newcommand{\memo}[1]{{\color{red} #1 }}
%\bibliography{../../../refsaono.bib}
% \bibliography{refsaono.bib}
\clearpage
\section{Post-quantum cryptography}
% killed subsection?
% \subsection{Motivation of post-quantum cryptography}
The post-quantum cryptography, sometimes referred as the quantum-resilient or quantum-safe cryptography~\cite{NISTpq}, includes a wide class of cryptographic primitives which are believed to be secure against both classical and quantum computers in theory and practice.
This section introduces a motivation of post-quantum cryptography, where do we use the quantum computers to attack them, and how do we model the world.
%What is pqcrypto?
Since Shor's work~\cite{Shor97} proved there exists polynomial time
quantum attacks to RSA public-key cryptography and DSA signature,
the cryptographers have been developing countermeasure schemes.
Concretely, the standardization criteria requires it must consume a large number
of gates in the sense of both classical and quantum for the attacks~\cite[p.18]{NISTpq}.
However, the resilience against other quantum computers such as quantum annealers are not usually considered because how to quantify their ability is not clear now and it is an important open problem.
As the countermeasure, the cryptographers have been developing
new cryptographic schemes which they call ``post-quantum cryptography''
or ``quantum-resilient cryptography.''
It is widely believed that revealing secret information encrypted by a scheme is an intractable task even we have a large size of classical and quantum computers.
\aono{what is parameter selection?}
Besides the parameter selection,
there are several quantum arguments on security.
Most of them are analogues of cryptography in the classical world, by replacing probabilistic polynomial Turing machine (PPTM) to quantum polynomial time Turing machine (QPTM), with suitable adaptations.
We introduce which parts are replaced and should to argue by quantum peoples.
\rule{\columnwidth}{1pt}
\aono{could we move this to Sec.~\ref{sec:defense}?}
The resilience of cryptography to the computers can be explained in the following way.
The mathematical notion of security has been formulated by Shannon's discussion on the symmetric cryptography in~\cite{Sha49}.
He defined the symmetric cryptography has the perfect security (information-theoretic security) if the eavesdropper that gets ciphertext will gain no information about the plaintext.
This security notion can be described as the equivalent condition that
uses Turing machines (TM):
for any (unlimited time and space) TM $\mathcal{G}$ that outputs a candidate of plaintext from a given ciphertext, there exists a TM $\mathcal{G}'$ with no input that satisfies
%
\begin{equation}
\label{eqn:ITalg}
\Pr[ \mathcal{G}(ct) = m ] = \Pr [\mathcal{G}'() = m ].
\end{equation}
%
Here, the probability is over a fixed distribution of plaintext $m$ and key $k$, and $ct = Enc(k,ct)$.
The equivalence of probabilities means that $\mathcal{G}$ needs not to use $ct$ to recover $m$, thus, $ct$ does not contain any information about $m$ intuitively.
Shannon proved that the information-theoretic security
requires that the sender and receiver have to share
the secret key longer than the message itself.
The source of such unwieldiness is from the tightness of perfect security that requires the eavesdropper can get no information, or it allows unlimited power to the Turing machines.
It is easy to see any public-key cryptography does not satisfy
the perfect security~\cite[Sect. 5.5.2]{GolEnc2},
and the followers tried to relax the notion.
\aono{the part I want to move ends here.}
\rule{\columnwidth}{1pt}
\subsection{Cryptanalyses and Base Problems}
Attacks to cryptographic schemes, i.e., revealing secret information from public information, is roughly classified into two ways: cryptanalysis to a specific scheme, and solving a base problem.
Both are studied to set suitable parameters or to check to see if the scheme is safe or not.
We mainly focus on the theoretical works
because there are very limited quantum works on real cryptanalyses to schemes to our best knowledge.
Standard techniques to guarantee the security of cryptographic scheme
are security reduction and hardness assumption.
The former is mathematical argument to prove that breaking scheme is harder than solving a hard problem.
Thus, with the assumption that the problem is intractable,
the cryptographic scheme is believed to be secure.
To show it, they prove any attacker that can solve the scheme can also solve the intractable problem.
During the proof, it is considered the model of attack, i.e., how the attacker can access to the oracles.
They usually consider three types of oracles to discuss the security:
encryption, decryption and random.
The encryption oracle and decryption oracle are virtual functions which return
a result of encryption function and decryption function from its input.
With these oracles, the security against chosen plaintext attack (CPA) \cite{GM84}
and chosen ciphertext attack (CCA) \cite{NY90,DDN91} are typically
formulated by that any attacker cannot reveal any useful information in a short time from the output of oracles even if one can choose inputs to the oracles; see textbooks \cite{Gol06book,Gol09book} for example.
Under the classical world, the attacker, usually called as ``adversary,'' is regarded as a PPTM and can access to the oracles in a classical way,
i.e., it gets a bit sequence on each input bit sequence deterministically.
In order to the quantum security there are some ways to consider the quantum version of adversary and oracles.
The situation where adversary is QTM whereas the access is classical
\cite{AJOP20} %qCCA1 classical access,
,
which is considered as a cryptographic model in the NISQ era.
We should note that the NIST post-quantum competition
recommends to consider such situation \cite{NISTpqcriteria} for the candidates.
The other situation is both adversary and access are quantum.
\cite{BZCG13,GHS16} % qCPA, superposition
\memo{To be extended}.
%細山田さんレポートの短いまとめ
A similar problem can be arisen in the symmetric key situation.
Kaplan et al. \cite{KLLN16} modeled the ability of QTM attackers.
The Q1 (resp. Q2) model is the situation where the attacker can post classical (resp. quantum superposition) queries to the encryption oracle.
As of 2020, the latter model is not realistic since it assumes a symmetric key hardware that inputs quantum superposition, but it is expected to be developed in the future.
Besides encryption/decryption oracles,
other considered issue is a random oracle \cite{BR93}.
This is also a virtual function that returns uniformly random values from every unique query.
The asymmetric key cryptosystem must have randomness in their encrypting functions since the deterministic public-key cryptsystem is inherently not secure
\cite{Gol09book}. %add page numbers
In the real-world systems, cryptographic hash functions such as AES have been used for constructing to introduce the randomness, that makes the rigid proof difficult.
Bellare and Rogaway \cite{BR93} showed that assuming random oracle is useful to carry out the rigid security proof of schemes and their techniques have been used in many situations.
To discuss the quantum security, it needs to discuss the situation where
the attacker can access the quantum version of random oracle by classical or quantum queries \cite{BDFL+11}.
%To be extended
\subsection{Representative Candidates}
The reduction and assumption tricks allows us to discuss the security of different type of schemes by a single intractable problem.
Hence, it is also important to investigate
how intractable the problem is against classical/quantum attacks.
This section introduces the representative post-quantum cryptographic schemes
which can be classified into several groups with the types of basis computational problems.
As of now, they are all believed to be secure against both classical and quantum attacks, however, it has been found some subclass problems are easily solved.
As of August 2020, there are 7 public-key encryption/Key-establishment/digital signature algorithms as the round 3 finalists of NIST post-quantum competition.
Besides, alternative 8 algorithms have been remained.
%CACR states?
These securities rely on hard problems on lattice, coding theory, multivariate equations, and isogeny.
The lattice-based cryptography is a generic term for cryptographic schemes
whose security assumptions are lattice problems.
The first lattice based public-key cryptography relied on the shortest vector problem (SVP) \cite{Aj96} and practically broken by a classical computer \cite{Nguyen97}.
Today, SVP-based schemes are considered obsolete and successor two lattice assumptions, LWE and NTRU have been used for construction.
The learning with errors (LWE) problem \cite{Regev05} is a problem to solve noisy simultaneous linear equation defined over a ring: $ \langle \bm{a}_i , \bm{s}_i\rangle \approx b_i $ for $i=1,\ldots$ where $\bm{a}_i$'s and $\bm{s}_i$'s are vectors.
The problem harder than SVP with suitable parameter settings \cite{BLPRS13} and
believed to be hard against quantum computers.
One drawback of standard LWE-based schemes is key size to store/send elements $\{ (\bm{a}_i,b_i) \} $ used as a public key.
Schemes based on Ring-LWE problem \cite{} and NTRU problem \cite{} are considered to avoid it.
They compress the public keys by using mathematical structure, but however,
it has been still open whether it is secure against classical/quantum computers.
In fact, some subclass of the problems is solved efficiently \cite{Duc17}.
The main open problem is to investigate structures that satisfies both efficiency and quantum resilience.
\memo{To be extended}
The code-based cryptography is the class of cryptographic schemes
based on the hardness of syndrome decoding of linear codes, which is one of NP-hard problem \cite{BMvT78,Has01}.
It has a long history since McEliece \cite{McE78}.
A fundamental idea is to use the generator matrix $G$ and $G'$ as the secret and public keys respectively;
here, $G'$ is computed from $G$ and how to compute it is also secret.
For a plaintext $m$ and its code $mG'$, ciphertext is $c=mG'+e$ where $e$ is an error bits which is randomly generated by the sender.
Similar to the lattice-based cryptography,
the code based cryptography has the key size drawbacks
and consider several structure in generator matrices.
As of now, no polynomial-time quantum algorithm to solve general syndrome decoding problem, however, a quantum speed up is possible \cite{KT17}.
%In particular, it is usually considered identical to the learning with parity noises (LPN) problem of which the LWE problem is generalization.
Multivariate cryptography is the generic class of cryptographic primitives whose security is based on the problem to solve multivariate algebraic equations over a finite field.
The modern style multivariate cryptsystem is proposed by Matsumoto-Imai \cite{MI88}.
Isogeny-based cryptography is a class of cryptosystem whose security base is computational problems on supersingular elliptic curves.
Jao and De Feo introduced a post-quantum key-exchange scheme SIDH \cite{JF11}
and it was extended to a public key scheme SIKE \cite{SIKEweb} which is one NIST candidate.
********** Aono part end ***********
%-----------------------------------------------------Here end of my section
\if0
\subsection{Standardization}
The most famous competition is NIST's post-quantum cryptography.
- PKE/Key exchange/signature
At the same time, CACR (Chinese Association for Cryptologic Research) in had been held another competition.
\fi
\if0
\memo{ここまで書いた}
A typical form of LWE-based cryptography uses $(A, \bm{b})$
as a public key and $\bm{s}$ as the corresponding secret key.
For a message $m$, the ciphertext is a pair $\bm{c}_1 = \bm{r}A$ and $\bm{c}_2 = \bm{r} \cdot \bm{b} + m$ where $\bm{r}$ a randomly-selected small element vector.
It is easy to see the receiver who knows $\bm{s}$ can recover $m$.
From the viewpoint of computing resource, one advantage is
the simpleness of implementation, thus, the dominating part of encryption is the matrix-vector multiplication and it can be highly parallelized in implementation.
On the other hand, the memory consumption to store the matrix is too large compared to the major schemes like RSA at the time, and other candidates of post-quantum cryptographies.
To solve the problem, it has been proposed some compression techniques to represent the matrix by a small data.
The ideal lattice is one of the most useful technique that represents
the matrix by one polynomial.
The sender and receiver share a polynomial $f(X)$ as a public parameter, which is selected carefully, and then send a public polynomial $a(X)$ instead of $A$.
Then, the sender decompresses it by putting $(i,j)$-element of $A$ as the coefficient of $X^j$ of $X^i a(X)\ \mod\ f(X)$.
As the standard LWE can be reduced to SVP, this type LWE, sometimes are called the ideal-LWE problem, can also be reduced to the ideal-SVP which is an ideal analogue to the SVP.
However, as of 2020, it is still open whether the ideal-type problems are hard enough as a basis problem to cryptosystems.
\fi
\memo{Too long?}
\memo{Abstract, representative basis problems (and major analysis methods?), major candidates, Solving challenges }
%As the theorists have proven the theoretical hardness of their cryptographic scheme from reasonable assumptions, one needs to estimate practical hardness to select the practical parameters.
%\memo{SVP challenge}
\subsection{Classification of Post-quantum cryptographes by the base problems}
As we explained above, each security notions are defined over each cryptographic system, i.e., developers have to prove their cryptographic scheme has some property of security after the scheme proposing.
However, the rigid proof is difficult since we have to consider all types of algorithms (albeit they are limited with a polynomial) to show to have a security notion of the scheme.
To solve the difficulty, a reduction technique has been used.
- TBW
- Classification of schemes by the base problems (lattice, code, multivariate, isogeny, etc.)
\subsection{Competition in NIST/CACR}
\subsection{Applications?}
- Homomorphic encryption?
%・暗号屋は量子計算機がすぐにでもできると仮定している
%・しかし他の分野では?
\if0
if there exists a (classical) algorithm A that can break
a proposed cryptographic scheme (i.e., the algorithm A makes the scheme not IND-CPA et al.),
there also exists an algorithm B that solves a hard problem (factoring, DLP, shortest vector, etc.) efficiently.
It means that breaking the cryptographic scheme is harder than solving the hard problem, and the proof guarantees
the security of the scheme against attackers.
Also, estimating the hardness of solving the hard problem provides us a lower bound of the hardness of breaking the cryptographic scheme.
This is the motivation of security estimation and why we want to solve hard problems by using computers.
5. To discuss the security notions in quantum, it replaces the polynomial TM by the polynomial QTM (of course, after the replacement, some modifications are necessary.)
With the same argument, estimating the quantum hardness of hard problems is also necessary.
6. Post-quantum cryptography is a class of cryptographic algorithms that are secure against both classical and quantum computers.
That is, the scheme must have a security reduction from the scheme to a hard problem that is thought to be not easy to solve by both classical and quantum computers.
7. The phrase "secure against quantum computers" is used by the crypto people to mean "the success probability of breaking the scheme by using
a polynomial-size quantum circuit is exponentially low."
Thus, they didn't consider any other type of quantum computers or other analog-type computers.
8. introduce representative post-quantum cryptos.
9. Applications?
\fi
%%-----------------------Aono
Besides the resilience against quantum computes,
some notable properties has been found around the cryptographies
introduced above.
The most interesting property is the homomorphic encrypton.
\memo{Homomorphic encryption, but this is independent from quantum-resilient}
% =======
% =======
% \clearpage
% \section{Post-quantum cryptography}
\subsection{rdv's notes}
\comment{Jon Dowling (RIP)'s opinions here were strong. He believed that
post-quantum crypto is fundamentally impossible, that all of the
interesting asymmetric problems useful for authentication and key
generation will ultimately fall to quantum algorithms.}
\comment{Aono: lattice crypto is very attractive because a) it reduces to
shortest vector or other problems, and b) implementation is easy,
basically a matrix times a vector~\cite{regev09:jacm}.}
\comment{learning w/ errors As + e = t mod q
candidate for post-quantum crypto}
\comment{(n.b.: cocori created a ipynb, but misunderstood the size of the
matrix necessary)}
Post-quantum cryptography is the attempt to find a public key
cryptosystem that is resistant to quantum computing, Shor's algorithm
in particular.
There is enough interest in this that the Wikipedia pages are
essentially extensive catalogs:
\url{https://en.wikipedia.org/wiki/Post-quantum_cryptography}
\url{https://en.wikipedia.org/wiki/Post-Quantum_Cryptography_Standardization}
An official-looking site:
\url{https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization}
One recent blog posting of some use:
\url{https://blog.trailofbits.com/2018/10/22/a-guide-to-post-quantum-cryptography/}
A very recent blog posting on teaching crypto in the post-quantum
crypto age:
\url{https://news.ncsu.edu/2019/06/teaching-next-generation-cryptosystems/}
which builds on a conference presentation on the course they created:
\url{https://dl.acm.org/citation.cfm?id=3317994}
which goes into a lot of detail on crypto hardware.
A survey from a decade ago:
\url{https://www.nist.gov/publications/quantum-resistant-public-key-cryptography-survey?pub_id=901595}
Also in 2009, there was a book, which I'm sure is almost entirely
outdated by now:
\url{https://www.springer.com/jp/book/9783540887010}
Transition doc from IETF, still in draft:
\url{https://datatracker.ietf.org/doc/draft-hoffman-c2pq/}
\url{https://eprint.iacr.org/2017/847.pdf}
\url{https://arstechnica.com/gadgets/2020/07/ibm-completes-successful-field-trials-on-fully-homomorphic-encryption/}
\subsection{Notes \& References}
To be filled in eventually, mostly by moving the existing parts of
this section into this subsection!