We consider the task of extending a given coin toss. By this, we mean the two-party task of using a single instance of a given coin toss protocol in order to interactively generate more random coins. A bit more formally, our goal is to generate n common random coins from a single use of an ideal functionality that gives $m<n$ common random coins to both parties. In the framework of universal composability, we show the impossibility of securely extending a coin toss for statistical and perfect security. On the other hand, for computational security, the existence of a protocol for coin toss extension depends on the number m of random coins that can be obtained “for free.” For the case of stand-alone security, i.e., a simulation-based security definition without an environment, we present a protocol for statistically secure coin toss extension. Our protocol works for superlogarithmic m, which is optimal as we show the impossibility of statistically secure coin toss extension for smaller m. Combining our results with already known results, we obtain a (nearly) complete characterization under which circumstances coin toss extension is possible.We consider the task of extending a given coin toss. By this, we mean the two-party task of using a single instance of a given coin toss protocol in order to interactively generate more random coins. A bit more formally, our goal is to generate n common random coins from a single use of an ideal functionality that gives $$m<n$$ common random coins to both parties. In the framework of universal composability, we show the impossibility of securely extending a coin toss for statistical and perfect security. On the other hand, for computational security, the existence of a protocol for coin toss extension depends on the number m of random coins that can be obtained “for free.” For the case of stand-alone security, i.e., a simulation-based security definition without an environment, we present a protocol for statistically secure coin toss extension. Our protocol works for superlogarithmic m, which is optimal as we show the impossibility of statistically secure coin toss extension for smaller m. Combining our results with already known results, we obtain a (nearly) complete characterization under which circumstances coin toss extension is possible.

Journal of CryptologyApr 26, 20180 citations

Quantum Bayesian Networks and Quasi-Probability

Jerome R. Busemeyer, Peter Bruza

Cambridge University Press eBooksNov 14, 20241 citation

Quantum Bayesian Inference: An Exploration

Jon Frost, Carlos Madeira, Harald Uhlig

Jan 1, 20260 citations

Chaotic switching for quantum coin Parrondo's games with application to encryption

Joel Weijia Lai, Kang Hao Cheong

Quantum game theory has stimulated some interest in recent years with the advancement of quantum information theory.This interest has led to a resurgence of quantum Parrondo's games.With two losing games combining to give a winning game, this paradoxical idea is known as Parrondo's paradox.By using chaotic switching between the two losing quantum games, we show that it is possible to achieve Parrondo's paradox involving a quantum walker playing two-sided quantum coin tossing games.Furthermore, we show that the framework of chaotic switching in quantum coin tosses can be applied to encryption.This is a proposal to deploy a quantum coin toss with chaotic switching for semiclassical encryption.Quantum game theory has stimulated some interest in recent years with the advancement of quantum information theory.This interest has led to a resurgence of quantum Parrondo's games.With two losing games combining to give a winning game, this paradoxical idea is known as Parrondo's paradox.By using chaotic switching between the two losing quantum games, we show that it is possible to achieve Parrondo's paradox involving a quantum walker playing two-sided quantum coin tossing games.Furthermore, we show that the framework of chaotic switching in quantum coin tosses can be applied to encryption.This is a proposal to deploy a quantum coin toss with chaotic switching for semiclassical encryption.

Physical Review ResearchJun 2, 202122 citations

Quantum random walks do not need a coin toss

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.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.

arXiv:quant-ph/0405128Physical Review AMar 29, 200567 citations

Quantum Probability for Probabilists

P. A. Meyer

Lecture notes in mathematicsJan 1, 1995155 citations

m<n

common random coins to both parties. In the framework of universal composability, we show the impossibility of securely extending a coin toss for statistical and perfect security. On the other hand, for computational security, the existence of a protocol for coin toss extension depends on the number m of random coins that can be obtained “for free.” For the case of stand-alone security, i.e., a simulation-based security definition without an environment, we present a protocol for statistically secure coin toss extension. Our protocol works for superlogarithmic m, which is optimal as we show the impossibility of statistically secure coin toss extension for smaller m. Combining our results with already known results, we obtain a (nearly) complete characterization under which circumstances coin toss extension is possible.