Public-Randomness in Public-Key Cryptography

John Mattsson, Ben Smeets, Erik Thormarker

Quantum-resistant cryptography is cryptography that aims to deliver cryptographic functions and protocols that remain secure even if large-scale fault-tolerant quantum computers are built. NIST will soon announce the first selected public-key cryptography algorithms in its Post-Quantum Cryptography (PQC) standardization which is the most important current effort in the field of quantum-resistant cryptography. This report provides an overview to security experts who do not yet have a deep understanding of quantum-resistant cryptography. It surveys the computational model of quantum computers; the quantum algorithms that affect cryptography the most; the risk of Cryptographically Relevant Quantum Computers (CRQCs) being built; the security of symmetric and public-key cryptography in the presence of CRQCs; the NIST PQC standardization effort; the migration to quantum-resistant public-key cryptography; the relevance of Quantum Key Distribution as a complement to conventional cryptography; and the relevance of Quantum Random Number Generators as a complement to current hardware Random Number Generators.

Mihir Bellare Y, Zvika Brakerski, Moni Naor +4 more

Alfredo De Santis, Giuseppe Persiano

In this work we investigate the power of Public Randomness in the context of Public-key cryptosystems. We consider the Diffie-Hellman Public-key model in which an additional short random string is shared by all users. This, which we call Public-Key Public-Randomness (PKPR) model, is very powerful as we show that it supports simple non-interactive implementations of important cryptographic primitives.We give the first completely non-interactive implementation of Oblivious Transfer. Our implementation is also secure against receivers with unlimited computational power.We propose the first implementation of non-interactive nature for Perfect Zero-Knowledge in the dual model of Brassard, Crepeau, and Chaum for all NP-languages.

圭介 田中, Keisuke Tanaka, 均 並木 +3 more

Yixiang Chen

Certificateless cryptography aims at combining the advantages of identity based and public key cryptography in order to avoid the key escrow problem inherent in the identity based cryptography and cumbersome certificate management in the traditional public key infrastructure. A new two party certificateless key agreement protocol (CL-KA) is proposed and we proved it secure in the random oracle model (ROM). Our protocol only requires each entity to compute one pairing, up to now, it turns out to be the most efficient one of all the previously known CL-KA schemes.