Five-Card AND Computations in Committed Format Using Only Uniform Cyclic Shuffles

Yuta Abe, Yu ichi Hayashi, Takaaki Mizuki, Hideaki Sone

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


In card-based cryptography, designing AND protocols in committed format is a major research topic. The state-of-the-art AND protocol proposed by Koch, Walzer, and Härtel in ASIACRYPT 2015 uses only four cards, which is the minimum permissible number. The minimality of their protocol relies on somewhat complicated shuffles having non-uniform probabilities of possible outcomes. Restricting the allowed shuffles to uniform closed ones entails that, to the best of our knowledge, six cards are sufficient: the six-card AND protocol proposed by Mizuki and Sone in 2009 utilizes the random bisection cut, which is a uniform and cyclic (and hence, closed) shuffle. Thus, a question has arisen: “Can we improve upon this six-card protocol using only uniform closed shuffles?” In other words, the existence or otherwise of a five-card AND protocol in committed format using only uniform closed shuffles has been one of the most important open questions in this field. In this paper, we answer the question affirmatively by designing five-card committed-format AND protocols using only uniform cyclic shuffles. The shuffles that our protocols use are the random cut and random bisection cut, both of which are uniform cyclic shuffles and can be easily implemented by humans.

Original languageEnglish
Pages (from-to)97-114
Number of pages18
JournalNew Generation Computing
Issue number1
Publication statusPublished - 2021 Apr


  • Card-based cryptography
  • Deck of cards
  • Secure multiparty computation


Dive into the research topics of 'Five-Card AND Computations in Committed Format Using Only Uniform Cyclic Shuffles'. Together they form a unique fingerprint.

Cite this