Cryptographic protocols enable participating parties to compute any function of their inputs without leaking any information beyond the output. A card-based protocol is a cryptographic protocol implemented by physical cards. In this paper, for constructing protocols with small numbers of shuffles, we introduce a new type of cards, regular polygon cards, and a new protocol, oblivious conversion. Using our cards, we construct an addition protocol on non-binary inputs with only one shuffle and two cards. Furthermore, using our oblivious conversion protocol, we construct the first protocol for general functions in which the number of shuffles is linear in the number of inputs.
Cryptographic protocols enable participating parties to compute any function of their inputs without leaking any information beyond the output. A card-based protocol is a cryptographic protocol implemented by physical cards. In this paper, for constructing protocols with small numbers of shuffles, we introduce a new type of cards, regular polygon cards, and a new protocol, oblivious conversion. Using our cards, we construct an addition protocol on non-binary inputs with only one shuffle and two cards. Furthermore, using our oblivious conversion protocol, we construct the first protocol for general functions in which the number of shuffles is linear in the number of inputs.
Abstract Card-based cryptography is a research field for realizing cryptographic protocols using a deck of physical cards. Shinagawa et al. proposed a regular n-sided polygon card, which can hold a value from 0 to n−1 n - 1 , and constructed an addition protocol over Z/nZ Z / n Z and a voting protocol with v voters and c candidates when v<n v < n . In this paper, we propose an addition protocol over Z/mnZ Z / m n Z using regular n-sided polygon cards. Technically, we introduce a cyclic integer encoding and a rot-and-shift shuffle to extend the modulus from n to mn. In addition, we construct two voting protocols with v voters and c candidates using regular n-sided polygon cards. Our first voting protocol requires c(⌈nv+1⌉+v+1) c ( ⌈ v + 1 n ⌉ + v + 1 ) cards and v+1 v + 1 shuffles without restriction. Our second voting protocol reduces the number of cards to ⌈nv+1⌉n+v+1 ⌈ v + 1 n ⌉ n + v + 1 when v<n v < n and c≤n c ≤ n .
Secure computation is a cryptographic primitive that enables mutually distrustful parties to jointly realize a possibly randomized functionality in a secure manner. Card-based secure computation studies the problem of implementing secure computation protocols visually by using physical cards, to help non-experts understand their mechanisms. Although many card-based secure computation protocols have been proposed, most of them focus on deterministic functionalities and only a few protocols for randomized functionalities are tailored to specific applications. In this work, we initiate the study of card-based protocols for generating uniformly random bits, which is the most fundamental randomized functionality in secure computation. We present four constructions of such protocols differing in the types of shuffles they use. We also show a lower-bound result that the number of shuffles required for protocols using complete shuffles must be at least the number of output bits. Furthermore, we demonstrate that our protocols for generating uniformly random bits can be extended to those for generating possibly non-uniform random numbers, when combined with existing card-based protocols for computing deterministic functions.
Abstract It is known that secure computation can be done by using a deck of physical cards. This area is called card-based cryptography. Shinagawa et al. (in: Provable security—9th international conference, ProvSec 2015, Kanazawa, Japan, 2015) proposed regular n-sided polygon cards that enable to compute functions over Z/nZ Z / n Z . In particular, they designed efficient protocols for linear functions (e.g. addition and constant multiplication) over Z/nZ Z / n Z . Here, efficiency is measured by the number of cards used in the protocol. In this paper, we propose a new type of cards, dihedral cards, as a natural generalization of regular polygon cards. Based on them, we construct efficient protocols for various interesting functions such as carry of addition, equality, and greater-than, whose efficient construction has not been known before. Beside this, we introduce a new protocol framework that captures a wide class of card types including binary cards, regular polygon cards, dihedral cards, and so on.
A card-based secure computation protocol is a method for n parties to compute a function f on their private inputs (x1,…,xn) using physical playing cards, in such a way that the suits of revealed cards leak no information beyond the value of f(x1,…,xn). A \textit{single-shuffle full-open} protocol is a minimal model of card-based secure computation in which, after the parties place face-down cards representing their inputs, a single shuffle operation is performed and then all cards are opened to derive the output. Despite the simplicity of this model, the class of functions known to admit single-shuffle full-open protocols has been limited to a few small examples. In this work, we prove for the first time that every function admits a single-shuffle full-open protocol. We present two constructions that offer a trade-off between the number of cards and the complexity of the shuffle operation. These feasibility results are derived from a novel connection between single-shuffle full-open protocols and a cryptographic primitive known as \textit{Private Simultaneous Messages} protocols, which has rarely been studied in the context of card-based cryptography. We also present variants of single-shuffle protocols in which only a subset of cards are revealed. These protocols reduce the complexity of the shuffle operation compared to existing protocols in the same setting.
Card-based cryptography is an area involving cryptographic techniques that use a deck of physical cards to implement secure computation. In this paper, we study card-based cryptographic protocols for symmetric functions f: {0, 1}n → R, where R is an arbitrary finite set. Any symmetric Boolean function has the property that its output value is determined only by the sum of input bits, and the class of them includes many interesting functions such as the AND and equality functions. In 2020, Ruangwises and Itoh proposed a protocol which uses 2n + 2 cards to securely compute any symmetric function f: {0, 1}n → R; reducing the number of cards to less than 2n + 2 was left as an open problem. While the Ruangwises–Itoh protocol uses a two-colored deck of cards, this paper considers using three-colored and four-colored decks: to give a partial answer to the open problem, we propose three protocols for symmetric functions using 2n + 1 cards or less. Specifically, we first propose a protocol using 2n + 1 cards from a three-colored deck. We then propose two protocols using 2n cards from a four-colored deck; one is a simpler protocol and the other is a more shuffle-efficient protocol.
In card-based cryptography, the numbers of cards and shuffles are the complexity measures of protocols for secure computations, and the smaller these values are, the better. As the state-of-the-art study to minimize the latter measure, Shinagawa and Nuida showed a surprising result that any n-input logical function can be securely computed with only one shuffle, based on the idea of Yao's garbled circuit. When executing their protocol, the number of required cards is 2n+24q, where the n-input logical function to be computed is represented by q gates. For example, when applied to the n-input AND and XOR functions, the number of gates is n-1, and hence, 26n-24 cards are required. In this paper, we show that the number of required cards can be reduced by focusing on these two specific functions. Specifically, we construct a single-shuffle protocol for the n-input AND function using 4n-2 cards, and construct a single-shuffle protocol for the n-input XOR function using 2n cards.