The most spectacular successes of quantum information processing tech-
niques have been in the field of cryptography, the science of secret message
exchange.
1
The reason why Shor’s algorithm shot into prominence and major
players started funding quantum computing research was the challenge it of-
fered to currently trusted schemes of data encryption, particularly the RSA
scheme that is the basis of almost all current public encryption systems, your
online banking transactions or purchases for instance!
Encrypt
Decrypt
FIGURE 9.4: Communication scenario for cryptography.
In this section we will provide a quick birds-eye view of major crypto-
graphic paradigms and where quantum information processing steps in to
make things better. For a delightful survey of the history and current trends
in cryptography I urge you to read the book by Simon Singh [66]. The progress
in quantum cryptography is comprehensively dealt with in the review article
by Gisin et. al. [38].
1
The word “cryptography” is derived from the Greek language: crypto=“secret,” gra-
phy=“writing.” It is actually one part of the science of “cryptology,” the second part being
“cryptanalysis,” which is the art of decoding an encryption. These two go hand-in-hand: to
test the success of any cryptographic scheme a thorough cryptanalysis is important.
184 Introduction to Quantum Physics and Information Processing
9.3.1 Basic cryptographic paradigms
Almost ever since mankind used language for communication, need was
felt for secrecy in that communication, as a protection of personal or national
interests. The basic scheme (Figure 9.4) is the conversion of a natural lan-
guage into a secret form, i.e., encryption, before transmission, and this needs
to be tested against different eavesdropping techniques. Several interesting
cryptographic schemes have evolved as our mathematical and logical prowess
increased. For instance, many of us may have played as children by exchanging
secret notes in which the text was encoded by replacing each letter by another
shifted down the alphabet by a few letters. This in fact was an ancient cipher
system attributed to Julius Caesar! The receiver then decodes the message by
shifting the letters back by the same amount.
Example 9.3.1. The Caesar Cipher: suppose you decide to encode by shifting
each alphabet by 5 letters:
Plain: A B C D E F G H I J . . . Y Z
Cipher: F G H I J K L M N O . . . D E
then the message “THIS IS A SECRET” would be encoded as “YMNX NX
FJHWT.” The sender and receiver both agree as to what scheme of encoding
they’ll use. The danger in such messaging is that if the message is intercepted,
then a clever cryptanalyst can figure out the scheme used and easily translate
any further messages sent by the same scheme. One can try to devise more
complicated translation schemes, but as long as they are one-to-one, statistical
methods such as the average frequency of letters in the English language may
be used to break the code.
The basic paradigm for any secret communication has two requisites:
1. An eavesdropper should not be able to decrypt the message
2. The sender should not be impersonated.
The process of encryption is basically a mathematical transformation E on
the input message m, which converts the plain text into a coded ciphertext c.
The set of symbols used for the cypher is known as the alphabet. The physical
analog is placing the message in a box that is then locked. The locked box
is then transported to Bob, who opens the box, i.e., decodes the message,
and obtains the plain text again. In this raw form of the protocol, security
is minimal since the message can always be intercepted by an eavesdropper
(Eve), who can then try to break the code (or recreate the key). The only
way this threat can be met is that each time Alice wishes to send a message,
she uses a new box (or a new algorithm for encryption) and that is wasteful.
Instead, what she opts for is to change the lock and therefore the key K
A
used
for locking the box. Bob then unlocks using his key K
B
, which has to be the
Information and Communication 185
correct one for the lock Alice used. The problem of keeping the message secret
now reduces to keeping the keys secure.
FIGURE 9.5: Private key cryptography.
Mathematically, we represent the process of cryptography by
m → E(m, K
A
) = c (encryption) (9.3)
c → D(c, K
B
) = m (decryption). (9.4)
The functions E and D need to be inverses of each other in this sense:
D(E) = . (9.5)
The encrypting function can be kept simple, so as to be computationally
efficient, and can be publicly known. This is the modern principle of cryptog-
raphy, sometimes known as Kerckhoff ’s principle. The weak point of an
encryption system should be easily changed if it falls into the enemy’s hands.
The choice then is for the key system, whether the encoding key is kept secret
or not. This results in two sets of schemes:
1. Symmetric or private key cryptography: Alice and Bob share the same
key K (Figure 9.5). This is like the box with a lock, whose key is shared
by both parties. The sharing must be done in an efficient and secret
way. The catch is in this step. If A and B are far separated, how can
one transmit the key to the other in a secure way? This is the problem
of secure key distribution.
2. Public key cryptography: here the same key is not used by both parties.
The sender uses a public or insecure key K
A
to encrypt the message
(Figure 9.6). The decryption process is achieved by a private, secure
keyK
B
. This process is like a ballot box that is locked and given to the
sender, who posts the message in it. The receiver alone can unlock it
with his secret key. Here the E and D processes are asymmetric, and
the problem of distribution of keys doesn’t arise. The security of the
protocol lies in the difficulty of operating D without the knowledge of
K
B
.
186 Introduction to Quantum Physics and Information Processing
FIGURE 9.6: Public key cryptography
Due to the difficulty in sharing truly secure keys, especially when a large
number of parties are involved, modern cryptographic schemes are usually
of the second kind. One of the most widely used protocols for public-key
encryption is a two-step process due to Diffie and Hellman [28], and by Merkle
[47]. Known as the D–H protocol, Alice and Bob each have a private key
denoted L and a public key denoted K.
Encryption (Alice): c
1
= E(m, L
A
); c = E(c
1
, K
B
)
Decryption (Bob): m
1
= D(c, L
B
); m = D(m
1
, K
A
). (9.6)
Exercise 9.2. Show that in the two-way public key cryptosystem of Equation 9.6,
E and D are indeed inverses of each other.
Example 9.3.2. Private key cryptography: the Vernam cipher or one-time pad.
A and B agree on a common encryption system and share a common
secret key K. One example of such an encryption is encoding the message
in N symbols and performing a bitwise addition mod N with the key. The
inverse is performed using the same key.
c = m + k mod N, m = c − K mod N.
• The key is a one-time use only. This is because it can be easily recon-
structed from the cipher if it is intercepted.
• The advantage of this technique is that the process is computationally
simple.
• C. Shannon has proved that this system is truly unbreakable as long as
the key is secret and is of the same length as the message
Leave a Reply