Cryptography Reference
In-Depth Information
basis). A qubit can be written in terms of function
ψ
=
α
|
0
+
β
|
1
with
2
=1. It is a fundamental law of quantum mechanics
that once we measure the state of a qubit
ψ
, we either get
2
+
α, β
∈
C
and
|
α
|
|
β
|
|
0
or
|
1
as a
2
result. More precisely, we measure
|
0
with probability
|
α
|
and
|
1
with
2
. The fundamental difference between bits and qubits is that
qubits may be in states between
probability
|
β
|
|
0
and
|
1
. Only by measuring the state
of a qubit, one can get one of the states
|
0
or
|
1
. A quantum register of
length
n
is built of
n
qubits
|
q
k
(
k
=1
,...,n
). Each
|
q
k
is of the form
α
k
|
. Due to superposition, a quantum register may be in all of the
2
n
possible states at the same time. A quantum computer may exploit this
fact and make use of such a quantum register to solve a particular problem.
In 1994, Peter W. Shor proposed randomized polynomial-time algorithms for
computing discrete logarithms and factoring integers on a quantum computer
[5, 6]. Although a group of researchers implemented Shor's algorithm to factor
the integer 15 [7], it is not currently known whether a quantum computer
of practical size will ever be put in practice. Furthermore, no polynomial-
time algorithm for solving any
0
+
β
k
|
1
-complete problem
7
has been found so far.
Further information about quantum computers can be found in [8].
NP
•
A
DNA computer
is a computational device that makes use of molecular bi-
ology to solve computational problems. More specifically, molecules of de-
oxyribonucleic acid (DNA) are used to encode problem instances, and stan-
dard protocols and enzymes are used to perform the steps of the corresponding
computations. In 1994, Leonard M. Adleman
8
demonstrated the feasibility of
using a small DNA computer to solve an (arguably small) instance of the
directed Hamiltonian path problem, which is known to be
-complete [9].
Further information about the DNA computer can be found in [10, 11].
NP
It is neither presently known how to build a quantum or DNA computer of
a sufficiently large size, nor is it known to be possible at all (this is particularly
true for DNA computers). Nevertheless, should either quantum computers or DNA
computers ever become feasible and practical, they would have a tremendous
impact on theoretical computer science in general, and cryptography in particular.
In fact, many cryptographic systems that are computationally secure today would
become completely insecure and worthless (this is not true for unconditionally
secure systems).
7
Refer to Section 6.6.2.2 and Definition 6.11 for the notion of an
NP
-complete problem.
8
Leonard M. Adleman is one of the inventors of the RSA public key cryptosystem.
