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

Extended Addition Protocol and Efficient Voting Protocols Using Regular Polygon Cards

Yoshihiro Takahashi, Kazumasa Shinagawa

Published Aug 20, 2024• 2 citations
Publisher

Abstract

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 .

DOI
10.1007/s00354-024-00275-0

Related papers

Card-based Cryptography with Dihedral Symmetry

Kazumasa Shinagawa

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.

New Generation Computing•Jan 4, 2021•9 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

Single-shuffle card-based protocol with eight cards per gate and its extensions

Kazunari Tozawa, Hiraku Morita, Takaaki Mizuki

Abstract Card-based cryptography allows us to securely compute arbitrary functions using a deck of physical cards. Its performance is mainly measured by the number of used cards and shuffles, and there is a line of work that aims to reduce either of them. One seminal work is the card-based garbled circuit technique by Shinagawa and Nuida (Discret Appl Math 289:248–261, 2021, https://doi.org/10.1016/j.dam.2020.10.013 ), which allows the construction of a card-based protocol for any Boolean function with a single shuffle. Their construction requires $$2n + 24g$$ 2 n + 24 g cards for an n-input Boolean function that is represented by g logical gates. In this paper, we reduce the number of cards to $$2n + 8g$$ 2 n + 8 g for arbitrary functions while keeping it working with only one shuffle. In addition, we propose two types of extensions to support numerical encoding and multi-input gates. In the extended scheme, the free-ADD technique, obtained by generalizing the free-XOR technique by Manabe and Shinagawa (Deng J, Kolesnikov V, Schwarzmann AA (eds) CANS 2023, LNCS, vol 14342. Springer, Singapore, pp 232–248, 2023, https://doi.org/10.1007/978-981-99-7563-1-11 ), is available. The free-ADD technique allows our scheme to evaluate any n-input symmetric Boolean function using $$2n^2+6n+2$$ 2 n 2 + 6 n + 2 cards.

Natural Computing•Jan 9, 2025•3 citations

A Computationally Efficient Card-Based Majority Voting Protocol with Fewer Cards in the Private Model

Yoshiki Abe, Takeshi Nakai, Yohei Watanabe +2 more

Card-based cryptography realizes secure multiparty computation using physical cards. In 2018, Watanabe et al. proposed a card-based three-input majority voting protocol using three cards. In a card-based cryptographic protocol with n-bit inputs, it is known that a protocol using shuffles requires at least 2n cards. In contrast, as Watanabe et al.'s protocol, a protocol using private permutations can be constructed with fewer cards than the lower bounds above. Moreover, an n-input protocol using private permutations would not even require n cards in principle since a private permutation depending on an input can represent the input without using additional cards. However, there are only a few protocols with fewer than n cards. Recently, Abe et al. extended Watanabe et al.'s protocol and proposed an n-input majority voting protocol with n cards and n + ⌊n/2⌋ + 1 private permutations. This paper proposes an n-input majority voting protocol with ⌈n/2⌉ + 1 cards and 2n-1 private permutations, which is also obtained by extending Watanabe et al.'s protocol. Compared with Abe et al.'s protocol, although the number of private permutations increases by about n/2, the number of cards is reduced by about n/2. In addition, unlike Abe et al.'s protocol, our protocol includes Watanabe et al.'s protocol as a special case where n=3.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Oct 19, 2022•4 citations

Efficient Card-Based Majority Voting Protocols

Yoshiki Abe, Takeshi Nakai, Yoshihisa Kuroki +5 more

Abstract Card-based cryptography is a variety of secure multiparty computation (MPC). Recently, a new technique called private operations was introduced because the protocol can be implemented with fewer cards than that by using the conventional technique called the shuffle. For example, Nakai et al. showed that if the private operations are available, secure computations of AND and OR operations for two inputs can be realized simultaneously by using four cards, and the protocol is applied to a four-card majority voting protocol with three inputs. This paper shows that only three cards are sufficient to construct a majority voting protocol with three inputs. Specifically, we propose two constructions of three-input majority voting protocols. One is a protocol assuming that players can announce their output, and the other is not allowed. Compared to Nakai et al.’s protocol, the protocol with the announcement is realized without any additional private operations and communications. On the other hand, the second construction requires two more private operations and communications because it removes the assumption on the announcement from the first construction. More importantly, the idea of the second protocol can be extended to an n-input majority voting protocol with n cards, which is the main result of this paper.

New Generation Computing•Mar 23, 2022•17 citations

Card-based Cryptography with a Standard Deck of Cards, Revisited: Efficient Protocols in the Private Model

Takeshi Nakai, Keita Iwanari, Tomoki Ono +3 more

Abstract Card-based cryptography is a secure computation protocol realized by using physical cards. There are two models on card-based cryptography: public and private models. We adopt private one that allows players to handle cards privately. While much of the existing works for card-based cryptography use two-colored cards, it is also a vital task to construct an efficient protocol with playing cards. In the public model, 2n cards are necessary for any n-bit input protocol since at least two cards are required to express a Boolean value. It holds true for both two-colored and playing-card settings. On the other hand, the private model enables us to construct a protocol with fewer than 2n cards. However, all existing protocols that achieve such properties are only in the two-colored setting. This paper shows that the private model enables us to construct a protocol with fewer than 2n cards using the playing cards. We first show two-bit input protocols with fewer than four cards for logical operations, AND, OR, and XOR. Furthermore, we show a three-input majority voting protocol using only three cards, which is constructed by combining our AND and OR protocols. Notably, our proposed protocols require no randomness. All operations are deterministic and depend only on players’ private inputs.

New Generation Computing•Jun 21, 2024•6 citations
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 .
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.
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 allows us to securely compute arbitrary functions using a deck of physical cards. Its performance is mainly measured by the number of used cards and shuffles, and there is a line of work that aims to reduce either of them. One seminal work is the card-based garbled circuit technique by Shinagawa and Nuida (Discret Appl Math 289:248–261, 2021, https://doi.org/10.1016/j.dam.2020.10.013 ), which allows the construction of a card-based protocol for any Boolean function with a single shuffle. Their construction requires 2n+24g2n + 24g2n+24g 2 n + 24 g cards for an n-input Boolean function that is represented by g logical gates. In this paper, we reduce the number of cards to 2n+8g2n + 8g2n+8g 2 n + 8 g for arbitrary functions while keeping it working with only one shuffle. In addition, we propose two types of extensions to support numerical encoding and multi-input gates. In the extended scheme, the free-ADD technique, obtained by generalizing the free-XOR technique by Manabe and Shinagawa (Deng J, Kolesnikov V, Schwarzmann AA (eds) CANS 2023, LNCS, vol 14342. Springer, Singapore, pp 232–248, 2023, https://doi.org/10.1007/978-981-99-7563-1-11 ), is available. The free-ADD technique allows our scheme to evaluate any n-input symmetric Boolean function using 2n2+6n+22n^2+6n+22n2+6n+2 2 n 2 + 6 n + 2 cards.
Card-based cryptography realizes secure multiparty computation using physical cards. In 2018, Watanabe et al. proposed a card-based three-input majority voting protocol using three cards. In a card-based cryptographic protocol with n-bit inputs, it is known that a protocol using shuffles requires at least 2n cards. In contrast, as Watanabe et al.'s protocol, a protocol using private permutations can be constructed with fewer cards than the lower bounds above. Moreover, an n-input protocol using private permutations would not even require n cards in principle since a private permutation depending on an input can represent the input without using additional cards. However, there are only a few protocols with fewer than n cards. Recently, Abe et al. extended Watanabe et al.'s protocol and proposed an n-input majority voting protocol with n cards and n + ⌊n/2⌋ + 1 private permutations. This paper proposes an n-input majority voting protocol with ⌈n/2⌉ + 1 cards and 2n-1 private permutations, which is also obtained by extending Watanabe et al.'s protocol. Compared with Abe et al.'s protocol, although the number of private permutations increases by about n/2, the number of cards is reduced by about n/2. In addition, unlike Abe et al.'s protocol, our protocol includes Watanabe et al.'s protocol as a special case where n=3.
Abstract Card-based cryptography is a variety of secure multiparty computation (MPC). Recently, a new technique called private operations was introduced because the protocol can be implemented with fewer cards than that by using the conventional technique called the shuffle. For example, Nakai et al. showed that if the private operations are available, secure computations of AND and OR operations for two inputs can be realized simultaneously by using four cards, and the protocol is applied to a four-card majority voting protocol with three inputs. This paper shows that only three cards are sufficient to construct a majority voting protocol with three inputs. Specifically, we propose two constructions of three-input majority voting protocols. One is a protocol assuming that players can announce their output, and the other is not allowed. Compared to Nakai et al.’s protocol, the protocol with the announcement is realized without any additional private operations and communications. On the other hand, the second construction requires two more private operations and communications because it removes the assumption on the announcement from the first construction. More importantly, the idea of the second protocol can be extended to an n-input majority voting protocol with n cards, which is the main result of this paper.
Abstract Card-based cryptography is a secure computation protocol realized by using physical cards. There are two models on card-based cryptography: public and private models. We adopt private one that allows players to handle cards privately. While much of the existing works for card-based cryptography use two-colored cards, it is also a vital task to construct an efficient protocol with playing cards. In the public model, 2n cards are necessary for any n-bit input protocol since at least two cards are required to express a Boolean value. It holds true for both two-colored and playing-card settings. On the other hand, the private model enables us to construct a protocol with fewer than 2n cards. However, all existing protocols that achieve such properties are only in the two-colored setting. This paper shows that the private model enables us to construct a protocol with fewer than 2n cards using the playing cards. We first show two-bit input protocols with fewer than four cards for logical operations, AND, OR, and XOR. Furthermore, we show a three-input majority voting protocol using only three cards, which is constructed by combining our AND and OR protocols. Notably, our proposed protocols require no randomness. All operations are deterministic and depend only on players’ private inputs.