A quantum coin toss

Tal Moran, Moni Naor, Gil Segev

Tomasz Kapitaniak

Tal Moran, Moni Naor, Gil Segev

Nicolas Gisin

Apoorva Patel, K. S. Raghunathan, Pranaw Rungta

Classical randomized algorithms use a coin toss instruction to explore different evolutionary branches of a problem. Quantum algorithms, on the other hand, can explore multiple evolutionary branches by mere superposition of states. Discrete quantum random walks, studied in the literature, have nonetheless used both superposition and a quantum coin toss instruction. This is not necessary, and a discrete quantum random walk without a quantum coin toss instruction is defined and analyzed here. Our construction eliminates quantum entanglement between the coin and the position degrees of freedom from the algorithm, and the results match those obtained with a quantum coin toss instruction.

Guanghui Liu, Dong Cao

Quantum coin tossing is a simple cryptographic primitive with many applications in more complicated tasks and plays a crucial role in complex quantum cryptography protocol design. Coin tossing protocols in classical environment are often based on bit commitment protocol. It has been proved that unconditionally secure quantum bit commitment schemes are insecure. Therefore, quantum coin tossing based on quantum bit commitment protocol isn't unconditionally secure. In general, quantum coin tossing is strictly weaker than bit commitment. In this paper, we have proposed a quantum coin tossing protocol based on quantum public-key cryptosystems. According to quantum CSS codes, we constructed a class of quantum quasi-cyclic low-density parity-check codes, and then proposed a novel quantum coin tossing protocol. Security analysis show that the proposed protocols are more secure.