Cryptography Reference
In-Depth Information
for factoring, the whole privacy and discretion of public-key cryptosystems
could vanish overnight.
Indeed, we know that quantum computers can, at least in principle, effi-
ciently factor large integers [19]. Thus in one sense public-key cryptosystems
are already insecure: any RSA-encrypted message that is recorded today will
become readable moments after the first quantum computer is switched on,
and therefore RSA cannot be used for securely transmitting any information
that will still need to be secret on that happy day. Admittedly, that day is
probably decades away, but can anyone prove, or give any reliable assurance,
that it is? Confidence in the slowness of technological progress is all that the
security of the RSA system now rests on.
1.6 Local Realism and Eavesdropping
We shall now leave mathematics and enter the world of quantum physics.
Physicists view key distribution as a physical process associated with sending
information from one place to another. From this perspective, eavesdropping
is a set of measurements performed on carriers of information. In order to
avoid detection, an eavesdropper wants to learn about the value of a physical
property that encodes information without disturbing it. Is such a passive
measurement always possible?
In 1935, Albert Einstein together with Boris Podolsky and Nathan Rosen
(EPR) published a paper in which they outlined how a “proper” fundamental
theory of nature should look [15]. The EPR program required completeness
(“In a complete theory there is an element corresponding to each element of
reality.”) and locality (“The real factual situation of the system A is indepen-
dent of what is done with the system B, which is spatially separated from the
former.”) and defined the element of physical reality as “If, without in any
way disturbing a system, we can predict with certainty the value of a physical
quantity, then there exists an element of physical reality corresponding to this
physical quantity.” In other words, if we can know the value of some phys-
ical property without “touching” the system in any way, then the property
must be physically real, i.e., it must have a determinate value, even before we
measure it.
This world view is known as “local realism” and it implies possibilities
of perfect eavesdropping. Indeed, this is exactly what the EPR definition of
the element of reality means in the cryptographic context.
Einstein and his colleagues considered a thought experiment, on two en-
tangled particles, that showed that quantum states cannot in all situations be
complete descriptions of physical reality. The EPR argument, as subsequently
modified by David Bohm [9], goes as follows. Imagine the singlet-spin state
of two spin
1
2
particles
1
√
2
(
| ↑|↓ − | ↓|↑
)
|
=
,
(1.3)
where the single particle kets
denote spin up and spin down with
respect to some chosen direction. This state is spherically symmetric, and the
| ↑
and
| ↓
