Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEICE Technical Report; IEICE Tech. Rep.

A Lower Bound on the Number of Shuffles for Commited-Format AND Protocols

Daiki Miyahara, Yuichi Hayashi, Takaaki Mizuki, Hideaki Sone

Published Aug 28, 2017• 0 citations
OpenAlex

Related papers

Upper Bounds on the Number of Shuffles for Two-Helping-Card Multi-Input AND Protocols

Takuto Yoshida, K. Tanaka, Keisuke Nakabayashi +2 more

Lecture notes in computer science•Jan 1, 2023•7 citations

AND Protocols Using only Uniform Shuffles

Suthee Ruangwises, Toshiya Itoh

arXiv:1810.00769•Lecture notes in computer science•Jan 1, 2019•29 citations

Five-Card AND Protocol in Committed Format Using Only Practical Shuffles

Yuta Abe, Yu‐ichi Hayashi, Takaaki Mizuki +1 more

In card-based cryptography, designing AND protocols in committed format is a major topic of research. 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. Their protocol»s minimality relies on somewhat complicated shuffles having non-uniform probabilities of possible outcomes. Restricting the allowed shuffles to "practical»» ones, namely uniform closed shuffles, to 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 practical shuffles? In other words, whether there exists 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 a five-card committed-format AND protocol using only practical shuffles. The shuffles that our protocol uses are random cut and random bisection cut, both of which are uniform cyclic shuffles and can be easily implemented by humans.

ACM ASIA Public-Key Cryptography Workshop (APKC)•May 23, 2018•27 citations

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

Yuta Abe, Yu‐ichi Hayashi, Takaaki Mizuki +1 more

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

New Generation Computing•Jan 18, 2021•22 citations

How to Detect Malicious Behaviors in a Card-Based Majority Voting Protocol with Three Inputs

Yoshiki Abe, Mitsugu Iwamoto, Kazuo Ohta

Card-based protocol is a multi-party computation using cards. The card-based protocol using operations called private operation has an advantage that the number of cards and the number of times of communication are smaller than the card-based protocol using operations called shuffle. However, there is a disadvantage that private operation allows dishonest players to perform malicious behaviors. Although the method to detect malicious behaviors in private operations was proposed, the method was available only in committed-format protocols, where inputs and outputs are represented by a pair of cards called commitment. In this paper, we show how to detect malicious behaviors in non-committed-format protocol with an example of a three-input majority voting protocol using private operations. Our majority voting protocol requires a smaller number of cards than the minimum number of cards required for committed-format protocols.

International Symposium on Information Theory and its Applications•Oct 18, 2020•2 citations

Impossibility of Four-Card AND Protocols with a Single Closed Shuffle

Shizuru Iino, Shota Ikeda, Kazumasa Shinagawa +3 more

Lecture notes in computer science•Nov 12, 2025•1 citation
In card-based cryptography, designing AND protocols in committed format is a major topic of research. 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. Their protocol»s minimality relies on somewhat complicated shuffles having non-uniform probabilities of possible outcomes. Restricting the allowed shuffles to "practical»» ones, namely uniform closed shuffles, to 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 practical shuffles? In other words, whether there exists 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 a five-card committed-format AND protocol using only practical shuffles. The shuffles that our protocol uses are random cut and random bisection cut, both of which are uniform cyclic shuffles and can be easily implemented by humans.
Abstract 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.
Card-based protocol is a multi-party computation using cards. The card-based protocol using operations called private operation has an advantage that the number of cards and the number of times of communication are smaller than the card-based protocol using operations called shuffle. However, there is a disadvantage that private operation allows dishonest players to perform malicious behaviors. Although the method to detect malicious behaviors in private operations was proposed, the method was available only in committed-format protocols, where inputs and outputs are represented by a pair of cards called commitment. In this paper, we show how to detect malicious behaviors in non-committed-format protocol with an example of a three-input majority voting protocol using private operations. Our majority voting protocol requires a smaller number of cards than the minimum number of cards required for committed-format protocols.