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

New Generation Computing

Card-based Cryptography with Dihedral Symmetry

Kazumasa Shinagawa

Published Jan 4, 2021• 9 citations
Publisher

Abstract

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 $${\mathbb {Z}}/n{\mathbb {Z}}$$ Z / n Z . In particular, they designed efficient protocols for linear functions (e.g. addition and constant multiplication) over $${\mathbb {Z}}/n{\mathbb {Z}}$$ 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.

DOI
10.1007/s00354-020-00117-9

Related papers

Extended Addition Protocol and Efficient Voting Protocols Using Regular Polygon Cards

Yoshihiro Takahashi, Kazumasa Shinagawa

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 $$\mathbb {Z}/n\mathbb {Z}$$ 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 $$\mathbb {Z}/mn\mathbb {Z}$$ 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(\lceil \frac{v+1}{n} \rceil + 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 $$\lceil \frac{v+1}{n} \rceil n + v + 1$$ ⌈ v + 1 n ⌉ n + v + 1 when $$v < n$$ v < n and $$c\le n$$ c ≤ n .

New Generation Computing•Aug 20, 2024•2 citations

Card-Based Protocols Using Regular Polygon Cards

Kazumasa Shinagawa, Takaaki Mizuki, Jacob C. N. Schuldt +5 more

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.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2017•55 citations

Efficient Card-Based Protocols for Symmetric Functions Using Four-Colored Decks

Yoshihiro Takahashi, Kazumasa Shinagawa, Hayato Shikata +1 more

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.

ACM ASIA Public-Key Cryptography Workshop (APKC)•Jun 28, 2024•8 citations

Efficient Card-Based Protocols for Symmetric and Partially Doubly Symmetric Functions

S. Ikeda, Yoshihiro Takahashi, Kazumasa Shinagawa +1 more

Symmetric functions are an important class of functions that includes many interesting functions. Constructing efficient card-based protocols for symmetric functions is an important research topic in card-based cryptography. In 2020, Ruangwises and Itoh designed a protocol for symmetric functions f : {0, 1}n → R using 2n + 2 cards of a two-colored deck. Whether the number of cards in this protocol could be reduced is an open problem. In this paper, we design protocols for symmetric functions using 2n + 1 cards of a two-colored deck, which solve the above problem affirmatively. We also propose protocols for symmetric functions using 2n cards of a three-colored deck, while the existing 2n-card protocol requires a four-colored deck. By further restricting the class of functions to {0}-partially doubly symmetric functions, we can construct even more efficient protocols. In particular, we construct protocols for {0}-partially doubly symmetric functions using 2n cards of a two-colored deck, while the existing protocol requires 2n + 1 cards.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Mar 9, 2026•0 citations

Efficient Card-Based Protocols for Basic Arithmetic Operations

Reo Eriguchi, Kazumasa Shinagawa

Card-based cryptography studies the problem of representing the functionality and security of cryptographic primitives visually by using physical cards, to demonstrate their security properties for those who are unfamiliar with cryptography. In this study, we propose efficient card-based protocols for secure computation of the four basic arithmetic operations (addition, subtraction, multiplication, and division). Existing protocols for securely performing these operations on ℓ-bit integers either require an exponential number of card manipulations in ℓ or need Ω (ℓ) additional cards. The proposed protocols simultaneously resolves these drawbacks for the first time by achieving a polynomial number of card manipulations in ℓ while requiring only a constant number of additional cards. The construction of our protocols is based on the long-hand algorithms for each of the four arithmetic operations. The technical novelty lies in demonstrating that the number of additional cards can be kept constant by freeing the cards representing intermediate values that are no longer needed during the process.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Aug 31, 2025•1 citation

Coin-based Secure Computations

Yuichi Komano, Takaaki Mizuki

Abstract In the history of cryptography, many cryptographic protocols have relied on random coin tosses to prove their security. Although flipping coins is indispensable in this manner, the coins themselves have never been in the spotlight. Therefore, we would like to make physical coins rise to the level of cryptography, just as a deck of physical playing cards has been used to perform a secure multi-party computation. Such a card-based protocol is known to be helpful both to perform a secure computation without any black-box computers and to understand the principles of secure protocols. In this paper, we propose a new framework of secure multi-party computation using physical coins, named a coin-based protocol. One advantage of the use of coins is that they are more ubiquitous than cards. Whereas a face-down card can conceal the information about its face side, one side of a coin reveals the information of its other side. Hence, more careful design is required for a secure coin-based protocol than for a card-based one. We formalize a computational model of the coin-based protocol and explicitly give protocols for NOT, AND, COPY, OR, and XOR computations. We also discuss the composability of the extended protocols and how to implement them in practice.

International Journal of Information Security•Apr 6, 2022•9 citations
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{\mathbb {Z}}/n{\mathbb {Z}}Z/nZ Z / n Z . In particular, they designed efficient protocols for linear functions (e.g. addition and constant multiplication) over Z/nZ{\mathbb {Z}}/n{\mathbb {Z}}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.
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−1n-1n−1 n - 1 , and constructed an addition protocol over Z/nZ\mathbb {Z}/n\mathbb {Z}Z/nZ Z / n Z and a voting protocol with v voters and c candidates when v<nv<nv<n v < n . In this paper, we propose an addition protocol over Z/mnZ\mathbb {Z}/mn\mathbb {Z}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(⌈v+1n⌉+v+1)c(\lceil \frac{v+1}{n} \rceil + v + 1)c(⌈nv+1​⌉+v+1) c ( ⌈ v + 1 n ⌉ + v + 1 ) cards and v+1v+1v+1 v + 1 shuffles without restriction. Our second voting protocol reduces the number of cards to ⌈v+1n⌉n+v+1\lceil \frac{v+1}{n} \rceil n + v + 1⌈nv+1​⌉n+v+1 ⌈ v + 1 n ⌉ n + v + 1 when v<nv < nv<n v < n and c≤nc\le nc≤n c ≤ n .
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.
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.
Symmetric functions are an important class of functions that includes many interesting functions. Constructing efficient card-based protocols for symmetric functions is an important research topic in card-based cryptography. In 2020, Ruangwises and Itoh designed a protocol for symmetric functions f : {0, 1}n → R using 2n + 2 cards of a two-colored deck. Whether the number of cards in this protocol could be reduced is an open problem. In this paper, we design protocols for symmetric functions using 2n + 1 cards of a two-colored deck, which solve the above problem affirmatively. We also propose protocols for symmetric functions using 2n cards of a three-colored deck, while the existing 2n-card protocol requires a four-colored deck. By further restricting the class of functions to {0}-partially doubly symmetric functions, we can construct even more efficient protocols. In particular, we construct protocols for {0}-partially doubly symmetric functions using 2n cards of a two-colored deck, while the existing protocol requires 2n + 1 cards.
Card-based cryptography studies the problem of representing the functionality and security of cryptographic primitives visually by using physical cards, to demonstrate their security properties for those who are unfamiliar with cryptography. In this study, we propose efficient card-based protocols for secure computation of the four basic arithmetic operations (addition, subtraction, multiplication, and division). Existing protocols for securely performing these operations on ℓ-bit integers either require an exponential number of card manipulations in ℓ or need Ω (ℓ) additional cards. The proposed protocols simultaneously resolves these drawbacks for the first time by achieving a polynomial number of card manipulations in ℓ while requiring only a constant number of additional cards. The construction of our protocols is based on the long-hand algorithms for each of the four arithmetic operations. The technical novelty lies in demonstrating that the number of additional cards can be kept constant by freeing the cards representing intermediate values that are no longer needed during the process.
Abstract In the history of cryptography, many cryptographic protocols have relied on random coin tosses to prove their security. Although flipping coins is indispensable in this manner, the coins themselves have never been in the spotlight. Therefore, we would like to make physical coins rise to the level of cryptography, just as a deck of physical playing cards has been used to perform a secure multi-party computation. Such a card-based protocol is known to be helpful both to perform a secure computation without any black-box computers and to understand the principles of secure protocols. In this paper, we propose a new framework of secure multi-party computation using physical coins, named a coin-based protocol. One advantage of the use of coins is that they are more ubiquitous than cards. Whereas a face-down card can conceal the information about its face side, one side of a coin reveals the information of its other side. Hence, more careful design is required for a secure coin-based protocol than for a card-based one. We formalize a computational model of the coin-based protocol and explicitly give protocols for NOT, AND, COPY, OR, and XOR computations. We also discuss the composability of the extended protocols and how to implement them in practice.