The Bridge - February 2018 - 20
Feature
encryption process is a "one-way function" [11].
That is, the public key cannot decrypt the encrypted
message. Alice then sends the encrypted message
to Bob, who can decrypt it with his private key
due to the mathematical relationship between the
public and private keys. Intuitively, this is similar
to "encrypting" a message by putting it in a USPS
mailbox. Nobody except the postal worker has the
"private" key to the mailbox, so he is the only person
who can decrypt the letter by unlocking the mailbox.
A common public key cryptosystem is RSA,
introduced in 1978 [11]. RSA relies critically on
the difficulty of factoring large numbers. To date,
there is no known classical algorithm capable of
factoring integers in polynomial time. The fastest,
well-known classical factoring algorithms, such
as the Number Field Sieve, run in time of order
exp[(log(N))⅓(loglog(N))⅔], scaling exponentially
in time [13]. As a result, Eve cannot factor the key
fast enough to discover the secret message while it
still has value to Alice and Bob. Assuming each each
computer operation takes 1 µs, a 50 digit key would
require roughly 4 hours, but a 200-digit key would
require almost 4 billion years to factor [11].
Because public-key cryptosystems like RSA permit
Alice and Bob to send encrypted messages without
the need to agree on a secret key beforehand,
those cryptosystems have proven to be much
more practical to implement on a global scale than
the one-time pad and secure the majority of our
electronic communications today.
2.3 Impact of Quantum Computers on
Classical Cryptography
The discovery of a practical polynomial-time factoring
algorithm would suddenly cast the security of
cryptosystems like RSA in doubt, with far-reaching
effects on the foundations of our society. For
this reason, Peter Shor caught the attention of
the cryptography community in 1994 when he
discovered an algorithm (now known as Shor's
algorithm) capable of factoring in polynomial time
[14] using a quantum computer.
THE BRIDGE
The factoring problem is in fact a period-finding
problem in disguise, which Shor's algorithm is able to
solve much more efficiently than classical algorithms.
While Shor's algorithm includes several procedures
that may be performed efficiently on a classical
computer, its core consists of the quantum Fourier
transform (QFT). The classical fast Fourier transform
(FFT) requires a computational time proportional to
n2n (compared to (2n)2 for the brute force solution),
where n is the number of bits. In contrast, the
quantum Fourier transform runs in time proportional
to n2, which is significantly faster [12]. The combined
algorithm requires poly(log(N)) steps for a general
input N, which is polynomial time [13].
Fortunately, quantum computers did not exist in
1994 and Shor's algorithm remained a harmless
theoretical exercise. However, since then there has
been significant progress in the building of practical
quantum computers and a replacement for public
key cryptosystems is necessary.
3 QUANTUM KEY DISTRIBUTION
Fortunately, while the advent of quantum
information (i.e. quantum computers) is the bane
of the information security world, it also presents
a possible solution in the form of quantum key
distribution (QKD), which revisits the theoretically
secure one-time pad. As its name implies, QKD
attempts to address the main disadvantage of the
one-time pad by solving the secure distribution
problem with the probabilistic nature of quantum
measurement [1].
QKD was first introduced in 1984 by Charles
Bennett and Gilles Brassard [16]. In their paper, they
describe a protocol, now known as BB84, to permit
the secure distribution of keys. The sender encodes
keys in quantum states such as photon polarization,
and then transmits those states to a receiver, who
measures them (e.g. determine photon polarization).
Both parties then perform post-processing to
obtain a secret key and to confirm that it has been
transmitted securely.
Table of Contents for the Digital Edition of The Bridge - February 2018
Contents
The Bridge - February 2018 - Cover1
The Bridge - February 2018 - Cover2
The Bridge - February 2018 - Contents
The Bridge - February 2018 - 4
The Bridge - February 2018 - 5
The Bridge - February 2018 - 6
The Bridge - February 2018 - 7
The Bridge - February 2018 - 8
The Bridge - February 2018 - 9
The Bridge - February 2018 - 10
The Bridge - February 2018 - 11
The Bridge - February 2018 - 12
The Bridge - February 2018 - 13
The Bridge - February 2018 - 14
The Bridge - February 2018 - 15
The Bridge - February 2018 - 16
The Bridge - February 2018 - 17
The Bridge - February 2018 - 18
The Bridge - February 2018 - 19
The Bridge - February 2018 - 20
The Bridge - February 2018 - 21
The Bridge - February 2018 - 22
The Bridge - February 2018 - 23
The Bridge - February 2018 - 24
The Bridge - February 2018 - 25
The Bridge - February 2018 - 26
The Bridge - February 2018 - 27
The Bridge - February 2018 - 28
The Bridge - February 2018 - 29
The Bridge - February 2018 - 30
The Bridge - February 2018 - 31
The Bridge - February 2018 - 32
The Bridge - February 2018 - 33
The Bridge - February 2018 - 34
The Bridge - February 2018 - 35
The Bridge - February 2018 - 36
The Bridge - February 2018 - 37
The Bridge - February 2018 - 38
The Bridge - February 2018 - 39
The Bridge - February 2018 - 40
The Bridge - February 2018 - 41
The Bridge - February 2018 - 42
The Bridge - February 2018 - 43
The Bridge - February 2018 - 44
The Bridge - February 2018 - 45
The Bridge - February 2018 - 46
The Bridge - February 2018 - 47
The Bridge - February 2018 - 48
The Bridge - February 2018 - 49
The Bridge - February 2018 - 50
The Bridge - February 2018 - 51
https://www.nxtbook.com/nxtbooks/ieee/bridge_issue3_2023
https://www.nxtbook.com/nxtbooks/ieee/bridge_issue2_2023
https://www.nxtbook.com/nxtbooks/ieee/bridge_issue1_2023
https://www.nxtbook.com/nxtbooks/ieee/bridge_issue3_2022
https://www.nxtbook.com/nxtbooks/ieee/bridge_issue2_2022
https://www.nxtbook.com/nxtbooks/ieee/bridge_issue1_2022
https://www.nxtbook.com/nxtbooks/ieee/bridge_issue3_2021
https://www.nxtbook.com/nxtbooks/ieee/bridge_issue2_2021
https://www.nxtbook.com/nxtbooks/ieee/bridge_issue1_2021
https://www.nxtbook.com/nxtbooks/ieee/bridge_2020_issue3
https://www.nxtbook.com/nxtbooks/ieee/bridge_2020_issue2
https://www.nxtbook.com/nxtbooks/ieee/bridge_2020_issue1
https://www.nxtbook.com/nxtbooks/ieee/bridge_2019_issue3
https://www.nxtbook.com/nxtbooks/ieee/bridge_2019_issue2
https://www.nxtbook.com/nxtbooks/ieee/bridge_2019_issue1
https://www.nxtbook.com/nxtbooks/ieee/bridge_2018_issue3
https://www.nxtbook.com/nxtbooks/ieee/bridge_2018_issue2
https://www.nxtbook.com/nxtbooks/ieee/bridge_2018_issue1
https://www.nxtbookmedia.com