Post-quantum Security of Plain OAEP Transform

Ehsan Ebrahimi

Ehsan Ebrahimi, Dominique Unruh

Juliane Krämer, Patrick Struck

Amit Agarwal, James Bartusek, Vipul Goyal +2 more

We obtain the first constant-round post-quantum multi-party computation protocol for general classical functionalities in the plain model, with security against malicious corruptions. We assume mildly super-polynomial quantum hardness of learning with errors (LWE), and quantum polynomial hardness of an LWE-based circular security assumption. Along the way, we also construct the following protocols that may be of independent interest. (1) Constant-round zero-knowledge against parallel quantum verifiers from quantum polynomial assumptions. Here, we develop a novel parallel no-cloning non-black-box simulation technique. This uses as a starting point the recently introduced no-cloning technique of Bitansky and Shmueli (STOC 2020) and Ananth and La Placa (ePrint 2019), which in turns builds on the classical non-black-box technique of Bitansky, Khurana and Paneth (STOC 2019). Our approach relies on a new technical tool, spooky encryption for relations computable by quantum circuits, that we also construct. (2) Constant-round post-quantum non-malleable commitments from mildly super-polynomial quantum hardness of LWE. This is the first construction of post-quantum non-malleable commitments in the plain model, and is obtained by transforming the construction of Khurana and Sahai (FOCS 2017) to obtain post-quantum security. We achieve quantum security by building a new straight-line non-black-box simulator against parallel verifiers that does not clone the adversary's state. This technique may also be relevant to the classical setting.

Vladimir Soukharev, David Jao, Srinath Seshadri

Tushar Jain

This thesis studies CDOC2 or Crypto Digidoc 2, the file transmission format used in the Estonian eID ecosystem and how it can be adapted for post-quantum security. CDOC2 protects file contents with symmetric cryptography and the key material required for decryption is delivered to recipients through public-key mechanisms such as elliptic-curve Diffie-Hellman, RSA-OAEP, Capsule Server workflows, and Shares Server workflows. These classical public-key mechanisms are vulnerable to quantum computers because of Shor’s algorithm. The thesis proposes a post-quantum design that preserves the existing CDOC2 container structure and operational model wherever possible, while replacing vulnerable key establishment with ML-KEM and adding ML-DSA based authorization for container retrieval from server. A prototype implementation was developed and evaluated against validation tests. The results show that a post-quantum variant of CDOC2 can be implemented without redesigning the symmetric payload encryption layer, but several migration issues were found such as increased header and token sizes, server-side authorization changes, and the need for further production level side-channel, interoperability, and certificate-management analysis.