Efficient security for post-quantum key encapsulation with correctness errors

DOCTORAL CANDIDATE

Fabrizio Sisinni

Supervisors

Dragoni (DTU), Majenz (DTU), Hülsing (TU/e), Walter (RUB), Schaffner (UvA), Vredendaal (NXP)

Objectives

Establish and tighten the PQC security of the Fujisaki-Okamoto (FO) transform with focus on Lattice and Code-based schemes.

Expected Results

Security reductions for correctness error finding in lattice-based and code-based chosen ciphertext attack (CCA)-secure key encapsulation mechanisms (KEMs). Attack algorithms for finding failures in lattice-based and code-based public key encryption (PKE).

Improved security proof or attack for FO-based PKE derandomization in the QROM.

Description

PQC-secure KEMs have received a lot of attention due to the ongoing NIST standardization efforts. All important PQC KEMs with chosen ciphertext security use the FO transformation whose security needs to be established in the QROM. Security proofs have improved steadily over the years, but leave two important loose ends: 1) The way decryption errors have been handled in security proofs involved heuristics and suffered from arguably unnatural security losses. 2) A central technique for QROM security proofs of FO, the oneway-to-hiding (O2H) lemma suffers from unexplained security losses despite many improvements. Recent progress for 1) has provided a framework for a heuristic-free and tightened security reduction technique dealing with decryption errors. It requires, however, two additional security properties from the underlying PKE. After familiarizing themselves with different code-based and lattice-based PKE schemes, the Doctoral Candidate will work on the characterization of lattice- and code-based PKE with respect to the two security properties needed for conclusively tying up loose end 1). In addition, the Doctoral Candidate will study the O2H lemma and its application to PQC security proofs for FO and work on tightening those proofs.

Methodology

The project will exploit the complexity theory of lattice problems. Crucially, the Doctoral Candidate will develop analytical tools to handle discretized versions of classic random matrix ensembles.

Risks

It might be the case that the current application of the O2H lemma to FO is tight due to a uniquely quantum attack. To mitigate this risk, the Doctoral Candidate will pivot to researching attack avenues in case the provable security effort stalls.