Up Next

12/07/21 @ 10:30 (9:30UK)
Finding Collisions in a Quantum World: Quantum Black-Box Separation of Collision-Resistance and One-Wayness – Takashi Yamakawa

Abstract: Since the celebrated work of Impagliazzo and Rudich (STOC 1989), a number of black-box impossibility results have been
established. However, these works only ruled out classical black-box reductions among cryptographic primitives. Therefore it may be
possible to overcome these impossibility results by using quantum reductions. To exclude such a possibility, we have to extend these
impossibility results to the quantum setting. In this paper, we initiate the study of black-box impossibility in the quantum
setting. We first formalize a quantum counterpart of fully-black-box reduction following the formalization by Reingold, Trevisan and
Vadhan (TCC 2004). Then we prove that there is no quantum fully-black-box reduction from collision-resistant hash functions to
one-way permutations (or even trapdoor permutations). We take both of classical and quantum implementations of primitives into
account. This is an extension to the quantum setting of the work of Simon (Eurocrypt 1998) who showed a similar result in the
classical setting.

Speaker Bio: Takashi Yamakawa is a researcher at NTT in Japan. He earned his PhD in Science from The University of Tokyo in 2017.His
research focuses on post-quantum and quantum cryptography.

Full Schedule

• 12/07/21 – (10:30) Finding Collisions in a Quantum World: Quantum Black-Box Separation of Collision-Resistance and One-Wayness – Takashi Yamakawa
• 28/06/21 – (17:00) Private Set Intersection for Contact Tracing – Ni Trieu
• 14/06/21 – (14:00) A key-recovery timing attack on post-quantum primitives using the Fujisaki-Okamoto transformation and its application on FrodoKEM – Alexander Nilsson
• 31/05/21 – (14:00) Simulation-Sound Arguments for LWE and Applications to KDM-CCA2 Security – Radu Titiu
• 17/05/21 – (14:00) Functional Encryption for Attribute-Weighted Sums from k-Lin – Junqing Gong
• 26/04/21 – (14:00) Improvements of Algebraic Attacks for Solving the Rank Decoding and MinRank Problems – Maxime Bros
• 12/04/21 – (14:00) Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings – Gregor Seiler
• 29/03/21 – (15:30) Collusion Resistant Trace-and-Revoke for Arbitrary Identities from Standard Assumptions – David J. Wu
• 15/03/21 – (10:30) Calamari and Falafl: Logarithmic (Linkable) Ring Signatures from Isogenies and Lattices – Shuichi Katsumata
• 01/03/21 – (14:00) Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP – Tamalika Mukherjee
• 15/02/21 – (15:00) Rounding in the Rings – Feng-Hao Liu
• 01/02/21 – (14:00) Impossibility Results for Lattice-Based Functional Encryption Schemes – Akin Ünal
• 18/01/21 – Scalable Ciphertext Compression Techniques for Post-Quantum KEMs and their Applications – Thomas Prest
• 14/12/20 – Improved Cryptanalysis of UOV and Rainbow – Ward Beullens
• 30/11/20 – Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs – Alex Lombardi
• 16/11/20 – Optimal Broadcast Encryption from Pairings and LWE – Shweta Agrawal
• 02/11/20 – Factoring and Pairings are not Necessary for iO: Circular-Secure LWE Suffices – Giulio Malavolta