ActiveCyber Interviews Professor Jintai Ding – Author of Post-Quantum Safe Crypto Algorithm and PAKE Protocol

Professor Jintai Ding discusses his ground-breaking work in the complex world of post-quantum cryptography. Learn the background behind the development of his protocol for password authenticated key agreement (PAKE) that is based on a provably secure quantum-safe approach in this interview with ActiveCyber. 

Last fall I attended a conference in Toronto where I heard a myriad of discussions around approaches to post-quantum cryptographic safety. One of the talks was presented by Professor Jintai Ding on a PQ-safe approach to Diffie Hellman Key Exchange. Unfortunately I was not able to connect with Professor Ding at the time, but luckily I ran into him again at the RSA 2017 conference whereupon he graciously accepted my invitation for an interview with ActiveCyber regarding his PQ-safe PAKE protocol. Although the math involved is well above my level of understanding, I was delighted to find Professor Ding’s discourse on the subject to more than adequately meet the needs of a layman in the security field. So read the interview below to learn the background behind this new protocol and why it is sure to make its way into your security life in the post-quantum era.

Spotlight on Professor Jintai Ding, University of Cincinnati

» Title: Professor of Mathematics, University of Cincinnati
» Website: http://math.uc.edu/~ding 
» Email: jintai.ding@uc.edu 
» Linkedin: https://linkedin.com/in/jintai-ding-865b631b
Read his bio below.

May 24, 2017

Chris Daly, ActiveCyber: Recently you announced a new post-quantum (PQ) safe cryptographic algorithm and protocol for password authenticated key agreement (PAKE). Could you provide a brief overview of a PAKE scheme and how it is applied for today’s networks? What class of PAKE does your scheme belong?

Professor Jintai Ding, University of Cincinnati: Authenticated Key Exchange (AKE) is a cryptographic protocol between two parties to derive a shared, high-quality, secret session key for secure communications. A Password-Authenticated Key Exchange (PAKE) is such an AKE protocol where the authentication is achieved with a low-entropy secret (like a password that can be memorized by humans) shared between two users. There are practical advantages of using the password only authenticated key exchange protocols rather than PKI-based alternatives, which is known to be hard to implement and maintain due to issues related to user registration, certificate revocation, management of the keys, user acceptance, susceptibility to phishing attacks, etc. On the contrary, PAKE maintenance seems to be simpler and more flexible. In the initial phase, PAKE protocol participants need only to exchange passwords in a secure manner using public parameters that are known to all participants, which is straightforward, and there is no need for key revocation, and participants are free from storing any unmemorable secrets. The inherent danger in PAKE is its vulnerability to dictionary attacks. PAKE provides a way to “bootstrap” a low entropy password into a strong cryptographic key without using a public key infrastructure. Well-designed PAKE explicitly prevents offline dictionary attacks and can be used as a tool to diminish phishing attacks as well. PAKE can be used in many places such as a file-transfer service like in Magic Wormhole, or in building a secure channel between two computers, like J-PAKE in Firefox and Mozilla, or even for applications in Internet of Things.

The new class of PAKE we proposed in CT-RSA 2017 is based on the ring learning with error problems (RLWE), which is provably secure and could resist future quantum computer attacks (quantum resistant or post-quantum (PQ) safe).

ActiveCyber: Can you provide an overview of your PQ algorithm? What makes your scheme unique and why is it significant in the field of crypto protocols? What types of security and secrecy properties does it provide?

Professor Ding: Our new post-quantum PAKE is more or less an analog of the classical PAKE, but in the new PAKE, we replace the classical Diffie-Hellman type of construction with a new RLWE-based key exchange construction, which was proposed in 2011 by myself.

In 2011, we built the first provably secure Diffie-Hellman-like key exchange based on the learning with error problems (LWE) and the ring learning with error problems (RLWE). (Jintai Ding, Xiang Xie, Xiaodong Lin, A simple provably secure key exchange scheme based on the learning with errors problem. Cryptology ePrint Archive, Report 2012/688, 2012.) Since then, there are many works on building LWE-based key exchange and authenticated key exchange including the New Hope instantiation which was deployed in Google Chrome Canary, and all those key exchanges are variants of our original design with minor modifications. This is clearly explained in the newest version of the publication of New Hope instantiation (IACR Cryptology ePrint Archive report 2015/1092). A new key component of the construction invented first by myself, which did not exist before in the original Diffie-Hellman protocol, is the one bit signal function used for rounding due to the final differences coming from the error terms.

What makes our new schemes unique and significant is that these post-quantum schemes have strong provable security, namely we can reduce the security to the RLWE problem and therefore to an approximate shortest vector problem over ideal lattices. They are also computationally very efficient due to the need to only do simple multiplications over a ring, though the communication cost is a bit higher than the corresponding classical constructions. This fact is further reflected in the claim of Google that their deployment of the New Hope instantiation was a success.

The key security and secrecy property is that we can prove the keys are perfectly random, and we can show that to defeat the scheme means one can defeat the RLWE problem, and therefore the approximate shortest vector problem over ideal lattices. Therefore as long as we choose proper RLWE parameters, the scheme should be very strong and secure.

ActiveCyber: How does the efficiency of your PQ PAKE scheme compare to other PQ and classical PAKE schemes? What timing results have you experienced to date for comparable bit strengths to today’s commonly used PAKE protocols and underlying lattice-based key agreement algorithms?

Professor Ding: Our PAKE is now the only PAKE. From the existing publications, we know that computationally our PAKE should be much more efficient than the classical PAKE schemes though we have a bit higher communication cost.

Our timing results shows that we can finish one round of PAKE within 1ms. However our implementation is not yet fully optimized, it is definitely comparable (if not better) than the classical PAKEs.

ActiveCyber: Where do you believe further optimization may occur for implementations?

Professor Ding: The future optimization will occur in two directions:

1) Choose the proper parameters to achieve a balance of error probability and efficiency.
2) Error distribution samplings, which now takes a lot of time.

ActiveCyber: Can you describe the assumptions your scheme is based on – specifically the hardness problem your scheme relies on? How is this hardness problem different from the discrete logarithm problem used for classical PK cryptosystems?

Professor Ding: The security assumptions of new schemes is first hardness of the RLWE problem, which can be further reduced to an approximate shortest vector problem over ideal lattices. This reduction is the basis of the claim of post-quantum security since we believe the approximate shortest vector problem can not be efficiently solved using quantum computers. All the classical PAKEs rely on the hardness of discrete log problems, which can be defeated by quantum computers.

ActiveCyber: Since you make use of the random oracle model (ROM) and follow classical security proof techniques, how might your proof change with quantum superposition and a quantum ROM?

Professor Ding: This is a very interesting and subtle question. Due to the usage of hash functions, our PAKE (not KE) schemes uses the ROM as the security model. Indeed if we allow quantum type of queries, we need to make sure our hash functions remain secure. Here I would like to emphasize that the security of LWE problem also has quantum reductions. However my opinion is that even if quantum queries are allowed, it is still not clear at all how such queries can be practically used in attacks, and the most possible case is that somehow the adversaries can access the hardware and perform such queries on the classical machines directly. Such a scenario is out of the scope what we consider here. Overall my opinion is that quantum ROM concern is more a hardware and physical security concern.

ActiveCyber: What previous research or work did you find useful in your development of this new protocol and why was it useful?

Professor Ding: The most useful previous work is surely the new post-quantum key exchange from the LWE (RLWE) problems, which I developed in 2011, since it is the basis of what I did for PAKE. One more thing I found very useful is the many years’ work I spent to understand deeply the key exchange protocols, why some worked and why some did not work. My work, in particular, the invention of the new post-quantum key exchange, is very much inspired by my 5 years search (2000-2005) for a new key exchange following the direction of looking for nontrivial polynomial and rational maps which commute with each other under composition. At the end of the fifth year, I found the paper by Joseph Fels Ritt: Permutable rational functions. Transactions of the American Mathematical Society 25 (1923), 399–448, which basically says, in my opinion, that:  the only nontrivial rational functions commuting under composition are: power functions, Chebyshev polynomials, and rational functions coming from the multiplication of points on elliptic curves. These permutable functions have been used to build Diffie-Hellman KE (power function) and EC KE. They all essentially come from multiplications on some groups (punctured plane, unit circle and elliptic curve), and therefore all of them can be defeated by quantum computers. This made me give up in the direction of permutable maps, but it also made me realize that we need to do something fundamentally new and different to build new Diffie-Hellman key exchanges. This is very much the reason I could build the new key exchange based on the LWE problems, in particular, the invention of a one bit signal for deriving the shared secret.

ActiveCyber: What level of independent cryptoanalysis has been performed to date on your protocol / proofs and what findings have resulted from this analysis?

Professor Ding: This work is relatively new. I think it has attracted a lot of attention. S. Fluhrer in CISCO and my research group (my students Sara RV, S. Alsayigh, and myself) have done some related cryptanalysis work on key reuses in RLWE-based key exchanges. As far as I know, I think the group of Professor Peter Ryan and some people in South Korea are looking carefully into the cryptanalysis of these new schemes, but nothing definite yet.

ActiveCyber: What level of acceptance have you seen from the crypto industry? Are there any vendors currently planning to implement the protocol? What are your plans for submitting the protocol to a standards body?

Professor Ding: People have shown very strong interest in our PAKE (and KE as in the usage in Chrome). I know some people in industry are implementing our schemes, but I know of nothing on deploying it yet. We are surely interested in submitting it to standard bodies, but that requires a lot of work.

ActiveCyber: What are your future plans for research in the crypto field?

Professor Ding: At the moment, my research concentrations are in the following three areas:

1) Truly understand the security of the lattice-based cryptosystems, in particular, I would like to find a way to resolve the issue related to the theoretical gap in the LLL reduction algorithms, namely why there is a gap between the theoretical estimate and experimental results of the quality of the shortest vector in LLL reduction;
2) Build the best post-quantum KE and AKE schemes including selecting the best parameters for the RLWE type of problems for practical applications;
3) Build the best post-quantum multivariate signature schemes including selecting the best parameters for practical applications.

Thank you Professor Ding for describing the incredible progress you have made in the area of post-quantum safe protocols. Your work is aligned to provide a secure foundation as we enter the post-quantum era. I look forward to seeing how the cryptologists, cryptoanalysts, mathematicians, and the rest of the security industry respond to the challenges of quantum computers and to the work you have brilliantly developed.

And thanks for checking out ActiveCyber.net! Please give us your feedback because we’d love to know some topics you’d like to hear about in the area of active cyber defenses, PQ cryptography, or other security topics. Also, email marketing@activecyber.net if you’re interested in interviewing or advertising with us at ActiveCyber.