Abstract Recently, card-based protocols have been extensively explored to illustrate relatively complex cryptographic concepts, such as Secure Multiparty Computations, so that even non-specialists can understand them. These protocols rely on three elements: a given alphabet with a set number of physical cards, encoding those cards, and shuffling operations. However, the execution is becoming over-complicated, as most follow the same encoding: fixed uniform disclosed encoding, which constrains other elements and decreases their expressiveness. This paper introduces the asymmetric five-card trick, a generalization of the five-card trick (a seminal work in the field of card-based cryptography) with the added feature of allowing variable encoding. To do so, we propose a pre-process called “handshake” that allows protocols to adapt operations based on players’ encoding. The protocol handshake is included as part of the protocol’s production phase in the proposed general framework, which is negotiated before its execution. Finally, this paper also introduces the notion of time and space complexity in card-based protocols to assess their production and execution’s lower bounds.Abstract Recently, card-based protocols have been extensively explored to illustrate relatively complex cryptographic concepts, such as Secure Multiparty Computations, so that even non-specialists can understand them. These protocols rely on three elements: a given alphabet with a set number of physical cards, encoding those cards, and shuffling operations. However, the execution is becoming over-complicated, as most follow the same encoding: fixed uniform disclosed encoding, which constrains other elements and decreases their expressiveness. This paper introduces the asymmetric five-card trick, a generalization of the five-card trick (a seminal work in the field of card-based cryptography) with the added feature of allowing variable encoding. To do so, we propose a pre-process called “handshake” that allows protocols to adapt operations based on players’ encoding. The protocol handshake is included as part of the protocol’s production phase in the proposed general framework, which is negotiated before its execution. Finally, this paper also introduces the notion of time and space complexity in card-based protocols to assess their production and execution’s lower bounds.

Journal of Cryptographic EngineeringAug 31, 20230 citations

An $n$ -Card Threshold Protocol Is Impossible

Shizuru Iino, Yang Li, Kazuo Sakiyama +1 more

Card-based cryptography uses a physical deck of playing cards to achieve secure computations. The first card-based protocol, called the five-card trick, allows Alice and Bob to decide whether to have a date without revealing their actual minds, i.e., it performs a secure computation of the logical two-input AND function. It uses a two-color deck of red and black cards, and the Boolean values are encoded based on the arrangement order of two distinct cards. The five-card trick was later optimized into a four-card AND protocol, achieving the minimal number of cards, because each input bit is encoded using two cards. Afterward, an alternative encoding, where each bit is represented by a single card, enabled a three-card AND protocol with a minor modification to the five-card trick. However, the construction of a two-card AND protocol remains an open problem. In this study, we provide a negative result for the problem: a two-card AND protocol is impossible. We extend this result to a more general class of functions, and consequently, derive the main impossibility theorem: an $n$ -card $n$ -input threshold protocol is impossible. Our result implies that the three-card AND protocol uses the minimal number of cards. A unique aspect of our proof is its simplicity; we show that it suffices to consider the initial and its subsequent states, unlike previous impossibility proofs that enumerate all possible states.Card-based cryptography uses a physical deck of playing cards to achieve secure computations. The first card-based protocol, called the five-card trick, allows Alice and Bob to decide whether to have a date without revealing their actual minds, i.e., it performs a secure computation of the logical two-input AND function. It uses a two-color deck of red and black cards, and the Boolean values are encoded based on the arrangement order of two distinct cards. The five-card trick was later optimized into a four-card AND protocol, achieving the minimal number of cards, because each input bit is encoded using two cards. Afterward, an alternative encoding, where each bit is represented by a single card, enabled a three-card AND protocol with a minor modification to the five-card trick. However, the construction of a two-card AND protocol remains an open problem. In this study, we provide a negative result for the problem: a two-card AND protocol is impossible. We extend this result to a more general class of functions, and consequently, derive the main impossibility theorem: an$n$-card$n$-input threshold protocol is impossible. Our result implies that the three-card AND protocol uses the minimal number of cards. A unique aspect of our proof is its simplicity; we show that it suffices to consider the initial and its subsequent states, unlike previous impossibility proofs that enumerate all possible states.

IEEE Annual Computing and Communication Workshop and Conference (CCWC)Jan 5, 20260 citations

An Efficient Parallel Repetition Theorem

Johan Håstad, Rafael Pass, Douglas Wikström +1 more

Lecture notes in computer scienceJan 1, 201046 citations

n

-card

n

-input threshold protocol is impossible. Our result implies that the three-card AND protocol uses the minimal number of cards. A unique aspect of our proof is its simplicity; we show that it suffices to consider the initial and its subsequent states, unlike previous impossibility proofs that enumerate all possible states.