IKIordanis Kerenidis

Iordanis Kerenidis

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Iordanis Kerenidis has a total of 11 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Quantum commitments from complexity assumptions

    by André Chailloux, Iordanis Kerenidis, Bill Rosgen


  • Practical quantum coin flipping

    by Anna Pappa, André Chailloux, Eleni Diamanti, Iordanis Kerenidis

    We show that in the unconditional security model, a single quantum strong coin flip with security guarantees that are strictly better than in any classical protocol is possible to implement with current technology. Our protocol takes into account all aspects of an experimental implementation, including losses, multiphoton pulses emitted by practical photon sources, channel noise, detector dark counts, and finite quantum efficiency. We calculate the abort probability when both players are honest, as well as the probability of one player forcing his desired outcome. For a channel length up to 21 km and commonly used parameter values, we can achieve honest abort and cheating probabilities that are better than in any classical protocol. Our protocol is, in principle, implementable using attenuated laser pulses, with no need for entangled photons or any other specific resources. DOI: http://dx.doi.org/10.1103/PhysRevA.84.052305 ©2011 American Physical Society


  • Open Access

    Quantum Commitments from Complexity Assumptions

    by André Chailloux, Iordanis Kerenidis, Bill Rosgen

    Bit commitment schemes are at the basis of modern cryptography. Since information-theoretic security is impossible both in the classical and the quantum regime, we need to look at computationally secure commitment schemes. In this paper, we study worst-case complexity assumptions that imply quantum bit-commitment schemes. First, we show that QSZK not included in QMA implies a computationally hiding and statistically binding auxiliary-input quantum commitment scheme. Additionally, we give auxiliary-input commitment schemes using quantum advice that depend on the much weaker assumption that QIP is not included in QMA (which is weaker than PSPACE not included in PP). Finally, we find a quantum oracle relative to which honest-verifier QSZK is not contained in QCMA, the class of languages that can be verified using a classical proof in quantum polynomial time.

  • Open Access

    A quantum protocol for sampling correlated equilibria unconditionally and without a mediator

    by Iordanis Kerenidis, Shengyu Zhang

    A correlated equilibrium is a fundamental solution concept in game theory that enjoys many desirable properties. However, it requires a trusted mediator, which is a major drawback in many practical applications. A computational solution to this problem was proposed by Dodis, Halevi and Rabin. They extended the original game by adding an initial communication stage and showed that any correlated strategy for 2-player games can be achieved, provided that the players are computationally bounded. In this paper, we show that if the players can communicate via a quantum channel before the game, then any correlated equilibrium for 2-player games can be achieved, without a trusted mediator and unconditionally. This provides another example of a major advantage of quantum information processing. More precisely, we prove that for any correlated equilibrium p of a strategic game G, there exists an extended game (with a quantum communication initial stage) Q with an efficiently computable approximate Nash equilibrium q, such that the expected payoff for both players in q is at least as high as in p. The main cryptographic tool used in the construction is the quantum weak coin flipping protocol of Mochon.

  • Open Access

    Optimal bounds for quantum bit commitment

    by André Chailloux, Iordanis Kerenidis

    Bit commitment is a fundamental cryptographic primitive with numerous applications. Quantum information allows for bit commitment schemes in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum protocol by Ambainis achieved a cheating probability of at most 3/4[Amb01]. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than 1/sqrt{2} [Kit03] (his lower bound on coin flipping can be easily extended to bit commitment). Closing this gap has since been an important and open question. In this paper, we provide the optimal bound for quantum bit commitment. We first show a lower bound of approximately 0.739, improving Kitaev's lower bound. We then present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to 0.739. More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2 + eps in order to achieve a quantum bit commitment protocol with cheating probability 0.739 + O(eps). We then use the optimal quantum weak coin flipping protocol described by Mochon[Moc07]. To stress the fact that our protocol uses quantum effects beyond the weak coin flip, we show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.

  • Open Access

    On the power of a unique quantum witness

    by Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, Shengyu Zhang

    In a celebrated paper, Valiant and Vazirani raised the question of whether the difficulty of NP-complete problems was due to the wide variation of the number of witnesses of their instances. They gave a strong negative answer by showing that distinguishing between instances having zero or one witnesses is as hard as recognizing NP, under randomized reductions. We consider the same question in the quantum setting and investigate the possibility of reducing quantum witnesses in the context of the complexity class QMA, the quantum analogue of NP. The natural way to quantify the number of quantum witnesses is the dimension of the witness subspace W in some appropriate Hilbert space H. We present an efficient deterministic procedure that reduces any problem where the dimension d of W is bounded by a polynomial to a problem with a unique quantum witness. The main idea of our reduction is to consider the Alternating subspace of the d-th tensor power of H. Indeed, the intersection of this subspace with the d-th tensor power of W is one-dimensional, and therefore can play the role of the unique quantum witness.