Page 72 - Cyber Warnings

coefficients are used which show the probability of the state that the configuration is in (up-
up/up-down/down-up/down-down). The four coefficients are equivalent to bits in current
computers which is where the power in quantum computing comes from. In current computers
for two bits you get 2 bits of information, with 2 qubits you get 4 bits of information, with 3 qubits
you get 8 bits of information and this curve continues exponentially and can be shown with the
n
equation 2 = X where “n” is the number of qubits in a configuration and “X” is the number of bits
you will get out of the configuration.

Quantum computers having all this power make it extremely easy for them to go through huge
amounts of data relatively quickly whether that be simulation of a quantum environment,
searching a database, or most important for information security, finding the prime factors of a
number. Shor’s Algorithm answers the problem of “given a large integer ‘n’ (typically several
hundred digits long), factorize ‘n’ as a product of primes” (Moorhouse). The problem with this is
that common encryption such as RSA are built upon the fact that factoring a large number into
two large prime factors is very difficult and time consuming for current computers. However, this
is not difficult for quantum computers as they have the capability to do complex algorithms in a
significantly less amount of time.

Old methods of encryption are slowly being replaced by stronger more modern methods that
can resist the computing power of quantum computers giving birth to a new age of post-
quantum encryption. One of the new methods to withstand quantum computers is a hash-based
public-key signature system. In this system the equation of H(x) = y is utilized. “The signer starts
2
by generating a secret x and then computes y = H(x), the signers secret key has 8b bits
(b=128), namely 4b independent uniform random strings, each string having 2b bits, the signer
then computes the public key as H. To sign a message m the signer generates a uniform
random string r, computes the bits, and reveals as a signature of m” (Bernstein). This method is
known more commonly as the Lamport-Diffie one-time signature system. If a signer wants to
sign more than one message they have to chain the messages together. To accomplish this the
signer generates a public key to be placed at the end of a message. The next message sent is
decrypted with the public key placed at the end of the previous message. This chaining process
can be repeated as many times as necessary.

Code-based public-key encryption built on the McEliece cryptosystem utilizes asymmetric
encryption and includes both encryption of data as well as a signature scheme for the sender,
made in 1978 by Robert McEliece. It was the first scheme to put randomization into the process
of how it encrypts data. Due to that randomization, this system is extremely resistant to attacks
using Shor’s algorithm making it a good candidate for the post-quantum age (McEliece). This
system utilizes a public key (G) with the equation G = SG sP. The variable S is a random dense
nonsingular matrix and P is a random permutation matrix. G s in the equation is the private key
(Wang). This system relies on hidden Goppa code in order to be decrypted. Hidden Goppa code
is an algebraic geometric linear code which is made using an algebraic curve over an infinite
field. The reason it is hidden is because the public key is derived from the private key and is
disguised in the encryption as a general linear code.

72 Cyber Warnings E-Magazine – June 2017 Edition
Copyright © Cyber Defense Magazine, All rights reserved worldwide