Proposal for post-quantum encryption wins attention

Some of today's most widely used encryption schemes could be cracked by quantum computers. These three scientists at CQT are working towards a solution. Pictured from left to right are Divesh Aggarwal, Antoine Joux and Miklos Santha.

CQT researchers aiming to protect the security of your future online transactions presented to some of the world’s leading cryptographers on 22 August at the Crypto 2018 conference. The conference was held in Santa Barbara in the United States.

The team's proposal for a new public key cryptosystem based on ‘Mersenne primes’ is also in consideration in the US National Institute of Standards and Technology (NIST) search for cryptographic proposals resistant to attack by quantum computers.

Public key cryptosystems, such as RSA, rely on people sharing ‘public keys’ that can be used to encrypt a message, which can then be decrypted only with a private key. This makes it convenient to exchange confidential information between parties who may not have met before, such as over the internet. Whenever you see ‘https’ in your browser, such a scheme is at work.

The quantum threat

The problem is that scientists expect public key schemes will be cracked by quantum computers as soon as we can make these computers bigger. Underlying the security of these schemes are mathematical problems that regular computers can’t easily solve, but is trifling for quantum computers. This threat has prompted the search for the scheme’s successor. Businesses and governments need quantum-resistant encryption in place early enough to protect data that requires long-term security, overlapping with the possible timeline for the arrival of large-scale quantum computers.

Divesh Aggarwal, a CQT Principal Investigator and Assistant Professor in the NUS School of Computing, explains: “Even though the concept of public-key cryptography was introduced four decades ago, creating public-key cryptographic schemes is a difficult task. Until recently, very few proposals were able to withstand cryptanalysis. Moreover, in practice, systems based on factoring and discrete logarithms — two problems which collapse in front of quantum computers — have dominated the market”

Divesh attended Crypto to present the new scheme he has developed jointly with Antoine Joux, Anupam Prakash and Miklos Santha. Their paper "A New Public-Key Cryptosystem via Mersenne Numbers" is published in the conference proceedings.

Antoine is a CQT Visiting Research Professor from UPMC University of Paris in Paris. Anupam was a CQT Research Fellow when he worked on the project and Miklos is a CQT Principal Investigator and Senior Researcher at CNRS at the University Paris Diderot, France.

The team were motivated by a call for proposals from NIST, launched in 2016. It is the first stage of a process to define post-quantum standards for cryptography. Their submission was among the 69 proposals accepted into the first round.

The security of their proposal is based on arithmetic modulo Mersenne numbers – numbers of the form p = 2ⁿ-1, where n is a prime. NIST asked for a concrete choice of parameters that achieve a desired security. The team’s proposal uses the Mersenne prime 2ⁿ-1, where n = 756839.

“Our goal in designing the Mersenne cryptosystem was to find the simplest possible instantiation of the ring-and-noise public-key cryptosystem paradigm based on the least complicated ring we could find, using only an elementary mathematical structure,” says Divesh.

“It’s the third time I am doing something constructive,” says Antoine, who usually specializes in trying to break encryption schemes instead of inventing them. In 2013, he shared the Gödel Prize for outstanding papers in theoretical computer science for a previous scheme he and his collaborators came up with.

A push for standards

It will take three to five years of analysis before NIST reports its findings, and then a further two years for the agency to have ready draft standards. The agency does not expect to pick a winner, but to identify several algorithms as “good choices”.

All of the first round proposals are public for review. A few have already been shown to be insecure and withdrawn from consideration. Antoine presented the team’s proposal at a workshop NIST held in April 2018 in Florida, where participants were encouraged to look for opportunities to merge and strengthen their schemes. So far, he says, the team has received positive feedback.

The presentation to Crypto will bring further scrutiny. The conference organised by the International Association for Cryptologic Research, a non-profit scientific association, has been held annually in Santa Barbara, California, since 1981. “Anything you’ve ever heard of in encryption was probably presented there,” says Miklos.