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:

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

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:

Parameter Set Cycles (no AVX) Cycles (AVX2)
Toy64 Gen: 1,269,090 Gen: 703,451
Enc: 947,906 Enc: 564,866
Dec: 1,107,424 Dec: 656,566
Lite96 Gen: 1,426,439 Gen: 773,685
Enc: 1,234,901 Enc: 682,140
Dec: 1,425,403 Dec: 790,026
Std128 Gen: 1,806,119 Gen: 934,051
Enc: 1,446,751 Enc: 865,352
Dec: 1,671,578 Dec: 986,905
Med160 Gen: 2,035,675 Gen: 1,122,462
Enc: 1,855,415 Enc: 1,042,861
Dec: 2,109,199 Dec: 1,182,880
Hi196 Gen: 2,122,547 Gen: 1,189,978
Enc: 1,986,198 Enc: 1,118,572
Dec: 2,310,815 Dec: 1,303,825
Super256 Gen: 2,829,289 Gen: 1,439,023
Enc: 2,799,390 Enc: 1,590,001
Dec: 3,247,542 Dec: 1,811,888


Size Parameters:

Parameter Set Sizes (bytes)
Toy64 pk: 12,192
sk: 12,224
ct: 2,720
Lite96 pk: 14,720
sk: 14,752
ct: 3,008
Std128 pk: 16,352
sk: 16,384
ct: 3,552
Med160 pk: 18,272
sk: 18,304
ct: 4,544
Hi196 pk: 20,512
sk: 20,544
ct: 6,048
Super256 pk: 26,912
sk: 26,944
ct: 8,352


Titanium NIST Submission Package (30 Nov 2017)  

NIST First PQC Conference Presentation Slides (April 2018)

Titanium Specifications Document Updates

Titanium Implementation Updates


Last modified 27 December 2018 by Ron Steinfeld