Welcome to this Graduate Research Blog.
This is where our graduate research group will be posting any research related to our postquantum analysis of TLS and SSL. In this blog we will be looking into various topics including postquantum signatures, effects of quantum computing on TLS, benefits of switching to postquantum algorithms, benefits of some postquantum algorithms over others, and whatever other topics come up.
Members
Reid Bixler (Researcher)
Collin Berman (Researcher)
David Evans (Professor/Advisor)
Contact
If you have any questions or would like to contact us about the research, feel free to email anybody that is a part of the team: {rmb3yz, cmb5nh, evans}@virginia.edu
Research
5/4/2017
This is the culmination of our research on postquantum TLS.
What is the Quantum Menace?
3/31/2017
Introduction to PostQuantum Cryptography
Quantum computers are dangerous. No, they’re not going to evolve into the terminator and they’re not going to cause the mystical singularity, but what they will do is give their owners and users the ability to break cryptography once considered secure.
Things such as RSA, DSA, and ECDSA rely on the difficulty of factoring large prime numbers and elliptic curves, both of which were once considered to be a hard problem to solve in polynomial time. The problem with quantum computing is that newly developed quantum algorithms such as Shor’s Algorithm and Grover’s Algorithm decrease the expected solution time to a reasonable polynomial time. What once would’ve taken longer than the age of the universe to solve may now take only a few days or even weeks. Considering the previous impossibility, there surely will exist entities willing to pay for the large time and monetary costs in order to break somebody else’s system.
With the introduction of quantum computing, there surely must exist problems that are even too difficult for a quantum computer to solve. Luckily enough for many cryptographers out there, many current problems and cryptographic systems are ‘quantumresistant’.

HashBased Cryptography : Examples inlcude the wellknown Merkle hashtree publickey signature system, which was built upon ideas of Lamport and Diffie.

CodeBased Cryptography : McEliece’s hiddenGoppacode publickey encryption system is one of the few known examples of such a system.

LatticeBased Cryptography : These are reliant on the difficulty of solving for lattices which are used in a number of algorithms including: NTRU, RingLWE, or BLISS.

MultivariateQuadraticEquations Cryptography : An interesting cryptographic system relying on, surprise, multivariate quadratic equations to protect a publickey, an example of which is Patarin’s HFEV publickeysignature system.

SecretKey Cryptography : The most wellknown and widely used example of this would be the DaemenRijmen “Rijndael” cipher, otherwise named “AES” for the Advanced Encryption Standard.
But Why Switch Now?
One of the biggest questions posed about quantum cryptography is why we need to switch over to these assumedly ‘more secure’ systems if even the best quantum computer out there at the moment can barely handle 10 qubits (with most breaks on RSA relying on multiple thousand). Why not simply switch over when the first sign of a quantumattack comes along?
The problem with that is our current level of quantum cryptography is not good enough to be widely used, and a majority of systems reliant on these ‘insecure’ algorithms would find it very difficult to integrate quantumresistant algorithms into their systems. Therefore there are three things that we need to consider.
1) We need to improve the efficiency of postquantum cryptography. 2) We need time to build confidence in postquantum cryptography. 3) We need time to improve the usability of postquantum cryptography.
We in the security community never want to be caught off guard and are constantly trying to maintain the security of all of our communications, regardless of the required switches and changes to the systems, because the security and reliability of the system comes first. We may not ever end up needing these postquantum cryptographic systems because a quantum computer capable of breaking RSA and DSA may never exist, but we as security researchers are not satisfied under such a strong assumption.
Applications to TLS
Specifically looking at SSL and TLS, there are already some existing research out there suggesting solutions to this ‘Quantum Menace’ for the TLS community. Things such as using RingLWE for postquantum key exchange for the TLS protocol or an altered version of RingLWE known as BCNS which was proposed and modified in Google’s own NewHope TLS research. But where do we come into this? What we have noticed in the TLS community is a severe need for ‘futureproofing’ the systems that we currently use. Yes, there do exist some researchers looking at potential solutions, but implementations of such systems have been rejected as being too insecure and unknown to risk putting into the new version of TLS v1.3.
We have noticed a distinct focus on very specific algorithms (mostly RLWE), and not much analysis on the possibilities of the widerange of postquantum cryptographic systems. While RLWE has some credibility to it, there has been signficant research improving and creating possibly better cryptographic systems that would maybe result in better integration into systems such as TLS. Because of this, our desire is to look at a number of quantumsecure algorithms to replace current protocols, and then present them alongside one another with the benefits and drawbacks of each, allowing for the security community to get a good idea of where the current postquantum world is and where they can fit into the picture.
Interesting Research Found
BLISS, BLISSB, and BLZZRD
One of our researchers has done some previous research along the lines of finding a fast, secure, and quantumresistant algorithm to replace ECDSA in a system that requires small key sizes and fast key verifications. The solution found initially was BLISS, which relies on bimodal lattices with gaussians to create a signature scheme protected against quantumattack. However, even further research has happened since the original paper was released in 2013, with improvements in speed and cache protection brought up in BLISSB and BLZZRD respectively. While we are just mentioning these at the moment, they are being mentioned because of their relative low cost in key size compared to similar cryptographic systems. While TLS doesn’t have limits on their key sizes, there are obvious drawbacks to having extremely large keys.
PASS, PASS2, and PASSign
Research has also been done on alternative quantumresistant algorithms including the Partial Fourier Recovery Problem integrated into the PASS and PASS2 algorithms. In 2013, research was done to create a practical postquantum signature scheme known as PASSign, which relies on the hardness of recovering a ring element with small norm from an incomplete description of its Chinese remainder representation.
Supersingular Isogeny DiffieHellman
Intro to Supersingular Isogney DiffieHellman
DiffieHellman is also one of the algorithms that will be at risk once practical quantum computers become available. As an improvement, recent research suggests the applications of Isogenies and Supersingular Elliptic Curves to prevent the inherent break brought about through quantum computers. DiffieHellman, specifically ephemeral DiffieHellman (DHE), is used in the current versions of TLS and even the proposed new v1.3. While not considered insecure at the moment, we must begin to consider altering current standards or offer alternative solutions to existing ones for the possible case that quantum computers do become practical in the next few decades.
Motivation
Collin and I are interested in postquantum because of its relatively recent prominence in the computing world and the potentially drastic effects that it could have on the internet (more specifically secure connections through TLS and SSL).
We want to analyze a number of different algorithms that protect against postquantum attacks and weigh the benefits and negatives of each in order to get a better grasp on the potential future of TLS. Our general purpose is going to be to determine how the TLS community can best protect against future quantum attacks and offer possible alternatives and options for such protection.
Description
At the moment, we are planning to look at a number of different postquantum capable algorithms and look at their costs for time, space, and security to weigh these algorithms against one another. We will be specifically looking into how TLS connections will be affected in each case as well as in the case that none of these changes are put into effect, with the worst possible case being completely broken TLS connections from quantumattack.
Other Sources
 NewHope : NewHope PostQuantum TLS Paper  Google’s take on how to implement postquantum algorithms into TLS
 Intro to Postquantum : Introduction to PostQuantum  Why we need PQ cryptography, challenges that we may face, and general introduction to PQ</li>
 PQCrypto : PQCrypto.org  Great site for mining PQ sources and to get a good grasp of the current landscape for postquantum
 BLISS : BLISS Paper  Bimodal Lattice Signature Scheme that was one of the best looking algorithms for postquantum in 2013
 BLISSB : BLISSB Paper  Offers speed improvements on BLISS and other potential changes
 BLZZRD : BLZZRD Paper  Offers cache protection for the Gaussians required for BLISS/BLISSB, essentially further improved and secure BLISSB