Code-based Cryptography

This project is funded by a Technology and Production Sciences grant by the Danish Council for Independent Research under grant number 11-105325. This is an individual postdoc grant with duration from September 2011 to August 2013 November 2013.1 The principal investigator is Christiane Peters at DTU Mathematics.

Motivation

Almost all data is nowadays stored electronically. Everyone is concerned with privacy and with secure handling of personal data. Banks, hospitals, governments, and private companies will only use encryption techniques which are well studied and which are easy to handle. Long-term storage of sensitive data requires higher security levels than a one-time key-exchange protocol on a cell phone. Data which needs to be stored securely for decades should be encrypted using algorithms which will not fall prey to attacks by future computing devices.

The aim of this project is to look into alternative cryptosystems which also withstand attacks on quantum computers – machines which allow much more parallelism than conventional computers. Currently only small quantum computers have been built. Realizing a large quantum computer which can pose a threat to RSA and ECC is an enormous challenge and it is unclear when physicists will succeed in building such machines. However, there is plenty of research going on: the National Institute of Standards and Technology (NIST) as only one example is massively supporting research in quantum physics.

Project description

Post-quantum cryptography deals with cryptosystems which run on conventional computers and whose security still holds up against quantum computers. A suitable candidate is code-based cryptography. The basic idea is due to Robert J. McEliece. Other than RSA and ECC code-based public-key cryptography has not shown any vulnerabilities to attacks with quantum computers and the best attacks on conventional computers and on quantum computers all take exponential time. The strength of McEliece's public-key cryptosystem is very fast encryption, but it is not used in practice as RSA and ECC provide much smaller key sizes. This does not mean that code-based cryptography is infeasible, it is just not competitive in a pre-quantum world.

The main objective in code-based cryptography is to reduce the size of the encryption and decryption keys. The main idea behind reducing key sizes is to find alternatives to McEliece's choice of classical Goppa codes. The goal of this project is to examine generic and structural attacks to come up with alternative designs and to find good parameters and setups for various security levels.

Workshop on Code-based Cryptography

I am one of the main organizers of the Code-based Cryptography Workshop 2012 which will take place on May 9-11, 2012 at the Mathematics Department in Lyngby. The workshop is funded by the Danish-Chinese Center for Applications of Algebraic Geometry in Coding Theory and Cryptography (AGINCC) in co-operation with the European Network of Excellence in Cryptology II (ECRYPT-II).

Literature

A collection of literature about and related to code-based cryptography can be found on http://pqcrypto.org/code.html and http://cayrel.net/research/code-based-cryptography/article/code-based-cryptography.

Contact information

Christiane Peters
Department of Mathematics
Technical University of Denmark
E-Mail: c dot p dot peters at mat dot dtu dot dk
Website: http://christianepeters.wordpress.com/


1 I will take a leave of absence from February to April 2013 to visit the Cryptography Group at Microsoft Research in Redmond.