Extended Addition Protocol and Efficient Voting Protocols Using Regular Polygon Cards

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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , and constructed an addition protocol over $$\mathbb {Z}/n\mathbb {Z}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Z</mml:mi> <mml:mo>/</mml:mo> <mml:mi>n</mml:mi> <mml:mi>Z</mml:mi> </mml:mrow> </mml:math> and a voting protocol with v voters and c candidates when $$v&lt;n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>v</mml:mi> <mml:mo>&lt;</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> . In this paper, we propose an addition protocol over $$\mathbb {Z}/mn\mathbb {Z}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Z</mml:mi> <mml:mo>/</mml:mo> <mml:mi>m</mml:mi> <mml:mi>n</mml:mi> <mml:mi>Z</mml:mi> </mml:mrow> </mml:math> 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>c</mml:mi> <mml:mo>(</mml:mo> <mml:mrow> <mml:mo>⌈</mml:mo> <mml:mfrac> <mml:mrow> <mml:mi>v</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:mi>n</mml:mi> </mml:mfrac> <mml:mo>⌉</mml:mo> </mml:mrow> <mml:mo>+</mml:mo> <mml:mi>v</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> cards and $$v+1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>v</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> shuffles without restriction. Our second voting protocol reduces the number of cards to $$\lceil \frac{v+1}{n} \rceil n + v + 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>⌈</mml:mo> <mml:mfrac> <mml:mrow> <mml:mi>v</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:mi>n</mml:mi> </mml:mfrac> <mml:mo>⌉</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mi>v</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> when $$v &lt; n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>v</mml:mi> <mml:mo>&lt;</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> and $$c\le n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>c</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> .