Post-Quantum Cryptography logo

One day, quantum computers will become a reality. When that day comes, RSA, Elliptic Curves and many other fundamental cryptographic primitives will become obsolete. Post-Quantum Cryptography offers secure alternatives and we can help you get ready.

Related technology

Fully Homomorphic Encryption

Meet the Holy Grail of cryptography.

Fully homomorphic encryption is the ultimate cryptographic tool to build more secure cloud computing services that respect everybody's privacy. It allows to confidentialy share data, and the encrypted data can then be processed without ever needing to decrypt or reveal it.

Our CEO is the main editor of the upcoming standard ISO/IEC 18033-6 on partially homomorphic encryption.

Homomorphic encryption is the future, and we can help you get there!

Details

Related service

Cryptographic Protocols

Security by design is not an abstract concept.

Beware of alleged "military grade secure" products. It is one thing to use AES-256 or RSA-4096, using it correctly is a different kettle of fish.
We can help you build innovative products that require any standard or advanced cryptographic tools, such as elliptic curves, identity-based encryption, anonymous signatures, e-cash, DRM, Pay-TV and many others.

Details

Related research projects

HEAT

Using Fully Homomorphic Encryption in Practice.

The HEAT project will develop advanced cryptographic technologies using Fully Homomorphic Encryption to process sensitive information in ecrypted form, without needing to compromise on the privacy and security of the citizens and organizations that provide the input data.

Details

CRYPTOCOMP

A crypto-calculus platform for the Cloud.

The principle of cloud computing is to allow users to outsource computation resources to the cloud by allowing a remote service to execute, in their name, some procedures on their private data. While many commercial services are growing fast, to this day, all require the client to place total trust in the service regarding the confidentiality of their data. The aim of CRYPTOCOMP is to develop an efficient cloud-based crypto-calculus platform which, using the latest advances in Fully Homomorphic Encryption, would make it impossible for the cloud service to learn anything whatsoever about the user's data, while still executing the procedures as intended.

Details

Traditional computers work with bits, simple binary values equal to 0 or 1. Quantum computers on the other hand work with qubits, quantum bits that can be a superposition of both 0 and 1 at the same time. Additional properties, such as the possibility of computing with entangled qubits, allow quantum computer to run specific algorithms that could not run on traditional computers.

A majority of modern cryptographic primitives relies on two problems: integer factorization and discrete logarithm. Both these problems happen to be efficiently solvable using a large enough quantum computer. Luckily, such large quantum computers do not exist yet. Still, most experts agree that at one point in the future, maybe in 5 years, 15 years, or more, they will exist. When that day comes, all security products will need to shift to so-called Post-Quantum Cryptographic primitives.

Many hard problems have been proposed for post-quantum cryptography, but the most trustworthy solutions can be grouped in three families:

  • Code-based cryptography
  • Lattice cryptography
  • Multivariate cryptography

CryptoExperts’ team includes experts in each of these specific research topics, so we can tell you exactly which solution best fits your post-quantum cryptographic needs.

CODE-BASED CRYPTOGRAPHY

Code-based cryptography encompasses all cryptographic constructions relying on hard problems from the theory of error-correcting codes. The oldest member of this family is the McEliece cryptosystem, dating back to 1978, relying on the hardness of decoding in a random binary code. Since then, many other constructions have been proposed, offering a wide range of functionalities: public key encryption, short digital signatures, zero-knowledge authentication, provably secure PRNG, cryptographic hashing, etc.

On top of being post-quantum, code-based cryptosystems have the following traits:

  • they work over small binary fields, so no need for an arithmetic co-processor
  • public key encryption or signature verification is very lightweight, requiring only a few hundred binary XORs
  • most code-based systems require to store a large random looking binary matrix, so they are probably not the best candidate for the most memory constrained environments

LATTICE CRYPTOGRAPHY

Lattice cryptography is algorithmically simple and highly parallelizable. Also, it is very versatile: besides the classical functionalities (key exchange, signature, encryption), it can be used to build powerful cryptographic features such as fully homomorphic encryption, allowing any untrusted environment to perform computations over encrypted data (fully homomophic encryption is one of CryptoExperts’ core technology: check it out!). Finally, lattice cryptography features a very strong security guarantee: choosing any random parameters provably yields a system as secure as possible.

On top of being post-quantum, lattice cryptosystems have the following traits:

  • some lattice systems are standardized (IEEE P1363 and X9.98 standards), and very efficient
  • signatures in lattice cryptography are faster than with elliptic curves and RSA
  • most systems have small parameters (about the size of RSA parameters and less), making them suitable to constrained environments

MULTIVARIATE CRYPTOGRAPHY

Public-Key Multivariate Cryptography is a part of public-key cryptography in which the public key is given as a set of polynomials in several variables, of small degree over a small finite field. Among the most famous multivariate public-key schemes are C*, HFE, UOV and Rainbow. Multivariate schemes make it possible to obtain signature schemes which provide short signatures. For instance the QUARTZ algorithm allows to sign messages with approximately 100 bit long signatures. Multivariate cryptography also make it possible to design signature schemes in which the verification of the signature is very fast. High performances can also often be reached for the signature phase, so that digital signature schemes can be implemented cheaply on ASICs. Another advantage of multivariate schemes is their flexibility in the design of various schemes, with ad-hoc properties.

On top of being post-quantum, multivariate cryptosystems have the following traits:

  • they work over small binary fields, so no need for an arithmetic co-processor
  • public key encryption or signature verification is very lightweight, requiring only a few hundred binary operations
  • most multivariate systems require to store a large random looking matrix, so they are probably not the best candidate for the most memory constrained environments

Related publications

  • NFLlib: NTT-based Fast Lattice Library.
    Carlos Aguilar-Melchor, Joris Barrier, Serge Guelton, Adrien Guinet, Marc-Olivier Killijian, Tancrède Lepoint.
    In CT-RSA 2016, 2016.
  • Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance.
    Shi Bai, Adeline Langlois, Tancrède Lepoint, Damien Stehlé, Ron Steinfeld.
    In ASIACRYPT (1) 2015, 2015. Best Paper Award
  • 🇫🇷 Quatre millions d'échanges de clés par seconde.
    Carlos Aguilar-Melchor, Serge Guelton, Adrien Guinet, Tancrède Lepoint.
    In SSTIC 2015, 2015.
  • Lattice Signatures and Bimodal Gaussians.
    Léo Ducas, Alain Durmus, Tancrède Lepoint, Vadim Lyubashevsky.
    In CRYPTO (1) 2013, pp. 40-56, 2013.
  • A family of weak keys in HFE and the corresponding practical key-recovery.
    Charles Bouillaguet, Pierre-Alain Fouque, portrait ofAntoine Joux, Joana Treger.
    In J. Mathematical Cryptology, 2012.
  • Parallel-CFS - Strengthening the CFS McEliece-Based Signature Scheme.
    Matthieu Finiasz.
    In Selected Areas in Cryptography 2010, pp. 159-170, 2010.
  • Security Bounds for the Design of Code-Based Cryptosystems.
    Matthieu Finiasz, Nicolas Sendrier.
    In ASIACRYPT 2009, pp. 88-105, 2009.
  • SHA-3 Proposal: FSB.
    Daniel Augot, Matthieu Finiasz, Philippe Gaborit, Stéphane Manuel, Nicolas Sendrier.
    In Submission to the NIST SHA-3 competition, 2008.
  • Toward a Rigorous Variation of Coppersmith's Algorithm on Three Variables.
    Aurélie Bauer, portrait ofAntoine Joux.
    In EUROCRYPT 2007, pp. 361-378, 2007.
  • When Stream Cipher Analysis Meets Public-Key Cryptography.
    Matthieu Finiasz, Serge Vaudenay.
    In Selected Areas in Cryptography 2006, pp. 266-284, 2006.
  • Inverting HFE Is Quasipolynomial.
    Louis Granboulan, portrait ofAntoine Joux, Jacques Stern.
    In CRYPTO 2006, pp. 345-356, 2006.
  • A Family of Fast Syndrome Based Cryptographic Hash Functions.
    Daniel Augot, Matthieu Finiasz, Nicolas Sendrier.
    In Mycrypt 2005, pp. 64-83, 2005.
  • A Public Key Encryption Scheme Based on the Polynomial Reconstruction Problem.
    Daniel Augot, Matthieu Finiasz.
    In EUROCRYPT 2003, pp. 229-240, 2003.
  • Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases.
    Jean-Charles Faugère, portrait ofAntoine Joux.
    In CRYPTO 2003, pp. 44-60, 2003.
  • Solving Underdefined Systems of Multivariate Quadratic Equations.
    Nicolas Courtois, portrait ofLouis Goubin, Willi Meier, Jean-Daniel Tacier.
    In Public Key Cryptography 2002, pp. 211-227, 2002.
  • FLASH, a Fast Multivariate Signature Algorithm.
    Jacques Patarin, Nicolas Courtois, portrait ofLouis Goubin.
    In CT-RSA 2001, pp. 298-307, 2001.
  • How to Achieve a McEliece-Based Digital Signature Scheme.
    Nicolas Courtois, Matthieu Finiasz, Nicolas Sendrier.
    In ASIACRYPT 2001, pp. 157-174, 2001.
  • QUARTZ, 128-Bit Long Digital Signatures.
    Jacques Patarin, Nicolas Courtois, portrait ofLouis Goubin.
    In CT-RSA 2001, pp. 282-297, 2001.
  • A Chosen-Ciphertext Attack against NTRU.
    Éliane Jaulmes, portrait ofAntoine Joux.
    In CRYPTO 2000, pp. 20-35, 2000.
  • Cryptanalysis of the TTM Cryptosystem.
    portrait ofLouis Goubin, Nicolas Courtois.
    In ASIACRYPT 2000, pp. 44-57, 2000.
  • Unbalanced Oil and Vinegar Signature Schemes.
    Aviad Kipnis, Jacques Patarin, portrait ofLouis Goubin.
    In EUROCRYPT 1999, pp. 206-222, 1999.
  • Lattice Reduction: A Toolbox for the Cryptanalyst.
    portrait ofAntoine Joux, Jacques Stern.
    In J. Cryptology, 1998.
  • C*-+ and HM: Variations Around Two Schemes of T. Matsumoto and H. Imai.
    Jacques Patarin, portrait ofLouis Goubin, Nicolas Courtois.
    In ASIACRYPT 1998, pp. 35-49, 1998.
  • Improved Algorithms for Isomorphisms of Polynomials.
    Jacques Patarin, portrait ofLouis Goubin, Nicolas Courtois.
    In EUROCRYPT 1998, pp. 184-200, 1998.
  • Trapdoor one-way permutations and multivariate polynominals.
    Jacques Patarin, portrait ofLouis Goubin.
    In ICICS 1997, pp. 356-368, 1997.