Quantum Bit-commitment for small storage based on quantum one-way permutations

KEISUKE TANAKA

圭介 田中, Keisuke Tanaka

一色 寿幸, 圭介 田中

Paul Dumais, Dominic Mayers, Louis Salvail

Toshiyuki Isshiki, Keisuke Tanaka

We propose quantum bit-commitment schemes based on quantum one-way permutations.Our schemes reduces exponentially the number of bits which Bob needs to store until the opening phase compared with the classical counterpart.

Frédéric Dupuis, Rémi Ligez, Khaireddine Medhioub +2 more

In this paper, we show for the first time that post-quantum one-way permutations are sufficient for perfect zero-knowledge classical arguments for all of NP with security guaranteed against quantum adversaries. We first establish that Naor, Ostrovsky,Venkatesen, and Yung's bit commitment scheme built from any permutation using interactive hashing, called the NOVY scheme, is sum-binding and collapse-binding against quantum polynomial-time committers provided the permutation is post-quantum one-way. We then show that the collapse-binding property of the NOVY scheme allows for Blum's perfect zero-knowledge argument for HAMCYCLE to remain so exactly as it stands against quantum adversaries.