Cryptography in the Quantum Computing Age

There is a problem with much of modern internet communications at the moment.  The problem is that the security of same relies on factoring being hard.  And, this is the case for a conventional computing machine.  However, for a quantum computer, such as may become available to corporations and governments within the next 5 to 10 years, it will be easy.

So this necessitates the need for a ‘refresh’ of the algorithms maintaining internet security.  So, how can we do this?

How RSA works

Well, recall the following about how RSA works (from the wikipedia entry):

  • Take two very large primes (100s of digits long) and multiply them together.   (n = pq, p and q prime).
  • Compute h = lcm(p – 1, q – 1)  (this is easy via the Euclidean algorithm, as lcm(a, b) = ab/gcd(a, b) ).
  • Choose e st e < h and gcd(e, h) = 1 (again, easy via the Euclidean algorithm).
  • Determine d st ed = 1 (mod h)  [ so that d is the modular multiplicative inverse of e ]
  • e is then the public key.  n is also released as public.
  • d is the private key.

Encryption process:

  • Bob obtain’s Alice’s public key e.  With a message M, he converts it into an integer m.  Then he computes c = m^e (mod n)

Decryption process:

  • Alice obtains Bob’s message c, and decrypts it as c^d = (m^e)^d = m (mod n)
  • Then m -> M is easy if the padding scheme is known.

The Achilles heel exposed by a quantum computer

The main point about the above that makes RSA hard to break is that factorisation is hard.  But, if factorisation is easy, Jill can intercept Bob’s ciphertext c, and, given her knowledge of n and e (which are public), factor n to p and q, compute h, and then identify d as the multiplicative inverse of e mod h.

Consequent to this, she can then decrypt Alice’s message as above.

So, if factorisation is easy, RSA is in a bit of a pickle.  But is there a better way to encrypt?

RSA over an integer polynomial ring

Process:

  • Take two very large irreducible polynomials over the integer polynomial ring Z[x] (100s of tuples long) and multiply them together.   nb. for extra security, you may want to ensure that the coefficients of these polynomials are each at least 100 digits long. (n[x] = p[x]q[x], p[x] and q[x] prime).
  • Compute h[x] = lcm(p – 1, q – 1)  (this is easy via the Euclidean algorithm for integer valued polynomials, as lcm(a, b) = ab/gcd(a, b)).
  • Choose e st e < h and gcd(e, h) = 1 (again, easy via the Euclidean algorithm).
  • Determine d[x] st e[x]d[x] = 1 (mod h[x])  [ so that d is the modular multiplicative inverse of e ]
    • Note: This is hard, unless factorisation is easy.
  • e is then the public key.  n is also released as public.
  • d is the private key.

Encryption process:

  • Bob obtain’s Alice’s public key e.  With a message M, he converts it into an integer m.  Then he computes c = m^e (mod n)

Decryption process:

  • Alice obtains Bob’s message c, and decrypts it as c^d = (m^e)^d = m (mod n)
  • Then m -> M is easy if the padding scheme is known.

Is this vulnerable to attack by a Quantum Computer eavesdropping on a channel carrying an encrypted message?

I claim not, as the size of the set of irreducible (prime) polynomials over the integer ring is much bigger than the set of primes.  The cardinality might be the same, but the complexity just seems intuitively to be much greater to me.  Factorising a semi-prime polynomial, which as factors has prime polynomials with possibly 100 or 200 terms, each with coefficients up to 150 digits in length, is, I suspect, much much more difficult than factorising a semi-prime integer.

If one had a tetra-computer (“hyper-computer”), the story might be different, but I suspect we will not have sufficiently powerful variants of those until 2050.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: