Thursday, 5 May 2016

Is Quantum Encryption Provably Secure

Much research is required on how you "prove" that quantum encryption schemes are secure.  Cryptographers have developed many ways of proving that new schemes are secure.  If you attend a cryptography course it won't be long before you are introduced to the concept of semantic security and the ubiquitous "game" where you an attack attempts to use plain text and cipher text to break the scheme.

Before proceeding it worth a very brief detour to clear up a common misunderstanding: the threat from quantum computers to public key encryption is not the same as quantum encryption.  For an introduction to early quantum encryption (quantum key distribution) you can start here.  Also "post quantum encryption" is simply those schemes being developed that are resistant to the threat posed by quantum computers.

The concept of semantic security first emerged in 1982.  It is a bit cumbersome which is why it was shown only two years later (by the same researchers) that semantic security was essentially the same as another concept called "ciphertext indistinguishability".  It is a simple but powerful concept where an attacker cannot distinguish between two separate ciphertexts to determine which contains each of two messages.  This is a much more intuitive means by which the adversary game can be run and it is considered a fundamental requirement if an encryption scheme is to be considered provably secure.

But, and it is a big but, how the concept of indistinguishability applied to quantum based schemes is far from intuitive. It means that applying the same proofs to quantum schemes that have previously been used in conventional cryptography needs careful thought.

Much of the early work on quantum key distribution relied upon the fact that quantum physics tells us that if, say, a photon is observed by an attacker then it will be disturbed and its quantum state (polarization in the case of a photon) will be unpredictable.  Protocols were defined that allowed sender and receiver to know whether to trust the cryptographic key that was being sent along the quantum circuit or if it was now know to a third party.  However, things have moved on a long way since those early schemes.  Hence, we now need to know if and how concepts like semantic security and indistinguishability apply in the quantum realm.

One of the problems that quantum encryption has had over the years is that it involves two disciplines (physics and cryptography) that do not necessarily talk the same language.  This is best illustrated by a very important paper entitled “Conjugate Coding” Wiesner submitted  to the IEEE Transactions on Information Theory.  It was rejected, presumably considered incomprehensible by the editors and referees as it was written in the technical language of physicists.  The whole episode is recounted in this paper from 2006, and stands as an vital reminder that having a common technical language is important.

One paper that has recently appeared addresses exactly these issues.  It is entitled "Computational Security of Quantum Encryption".   The paper develops quantum version of the fundamental concepts discussed above.  It goes on to apply these to quantum private and public key examples.

I suspect some will say that what is presented in this paper is just restating what use in conventional cryptography and adding the term "quantum".  I think it is more.  true several of the theorems are analogues of the conventional versions, but then you would hope they would be.  Indeed, some of this is not surprising as the modelling that is used tends to envisage, for example, extra registers as a means of coping with additional dimensions in the quantum space.

It is also worth noting that whilst some of the theorems postulated are self-evident, many of the equivalences made are not taken as read and there are several interesting lemmas proving that the quantum version of public key, private key and pseudorandom functions interrelate.

What really matters is how these techniques behave when you apply them to quantum schemes and if they prove to be adequate proofs. The initial examples shown in the paper definitely appear to do that.  As ever, there is scope for further research, and that is also laid out in the paper.

As quantum encryption has entered the mainstream I would encourage anyone involved in the research to read this paper.  I suspect it is an area about which we will hear much more in the next few years.  In order to bridge between the bit stream based cryptographic community and those developing quantum schemes I think we will need the definitions given in this paper.