Titanium: Post-Quantum Public-key Encryption and KEM Algorithms

Introduction

Welcome to the homepage for Titanium, a proposal package submitted in November 2017 to the Post-Quantum Cryptography (PQC) standardization process of the US National Institute of Standards and Technology (NIST), a process established by NIST in order to solicit, evaluate and standardize public-key cryptosystems resistant to attack by quantum computer technology.

The Titanium package consists of two public-key cryptosystems:

• Titanium-CPA: a Public-key Encryption scheme designed for post-quantum security against chosen-plaintext attacks (known as IND-CPA security),
• Titanium-CCA: a Key Encapsulation Mechanism (KEM) scheme designed for post-quantum security against chosen-ciphertext attacks (known as IND-CCA2 security).

The Titanium package was designed by a team based at the Faculty of Information Technology, Monash University Melbourne, Australia. The Titanium team members are:

• Ron Steinfeld (principal NIST package submitter, ron.steinfeld at monash dot edu)
• Amin Sakzad (auxilliary NIST package submitter, amin.sakzad at monash dot edu)
• Raymond Kuo Zhao (auxilliary NIST package submitter, raymond.zhao at monash dot edu)

This web page is maintained by the Titanium design team, and is intended to serve as an archive for up to date information on Titanium, including design documentation, design and/or documentation updates/corrections, updated cryptanalysis results, and implementation code and performance benchmark results. We encourage new cryptanalysis, new implementations and feedback on the Titanium design.

Brief Design Background

The security of the Titanium-CPA and Titanium-CCA algorithms is based on the hardness of solving the Middle-Product Learning With Errors (MP-LWE) problem, a variant of the LWE problem defined over polynomial rings Z_q[x]. The Titanium algorithms are MP-LWE variants of Regev's LWE-based encryption scheme.  The algorithms were designed to achieve an intermediate balance between security risk and computational performance for lattice-based cryptography.

On the one hand, Titanium offers significant computational performance gains over schemes based on the plain (unstructured) LWE problem. On the other hand, Titanium provides a lower security risk guarantee compared to schemes based on the Polynomial-LWE problem (PLWE, or the closely related Ring-LWE and Ideal-LWE problems) or Module Polynomial-LWE (MLWE) problems over fixed quotient rings. In particular, the latter fixed quotient ring schemes are defined over one specific polynomial quotient ring, such as Z_q[x]/(x^n+1). In a sense those schemes place all their `security eggs in one basket', as they rely on the hardness of PLWE or MLWE over the particular quotient polynomial ring chosen.  In contrast, the security of MP-LWE (and hence Titanium) is provably guaranteed as long as PLWE over Z_q[x]/(f(x)) is hard for some polynomial f(x) in a huge family F of polynomials. Thus Titanium hedges its security risk by distributing its `security eggs' over the huge family F of quotient rings, and only relies on the hardest PLWE problem among those in this family.

There are 6 parameter sets defined for Titanium with the following names: Toy64, Lite96, Std128, Med160, Hi192, and Super256. The digits at the end of each parameter set name indicate the equivalent symmetric-key security level (e.g. Std128 is designed for security at least equivalent to a brute force key search attack on a symmetric key cipher with 128-bit keys, such as AES-128).

Summary of Titanium-CCA Performance (based on implementation in spec. document version 1.1)

The timing benchmarks below are for Titanium-CCA running on a single core of an Intel i7-7700K CPU.

Timing Benchmarks:

Size Parameters:

Titanium NIST Submission Package (30 Nov 2017)  

• Titanium Submission Document
• Full Titanium NIST Submission Package (ZIP file, ~39 MB)

NIST First PQC Conference Presentation Slides (April 2018)

• NIST First PQC Conference Titanium Presentation Slides
  

Titanium Specifications Document Updates

• Specifications Document Version 1.1 (27 Dec 2018)

Titanium Implementation Updates

• Updated Titanium Implementation code (as documented in Specifications Document Version 1.1)
• See Chapter 7 for a summary of updates in Version 1.1

• Titanium was integrated in Nov. 2018 into the Open Quantum Safe (liboqs) post-quantum cryptography library

• The liboqs Titanium code is available here