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, <a href="https://doi.org/10.1016/j.dam.2020.10.013">https://doi.org/10.1016/j.dam.2020.10.013</a>), which allows the construction of a card-based protocol for any Boolean function with a single shuffle. Their construction requires <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11047_2024_10006_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="65" /> </InlineMediaObject> <EquationSource Format="TEX">$2n + 24g$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>n</mi> <mo>+</mo> <mn>24</mn> <mi>g</mi> </mrow> </math></EquationSource> </InlineEquation> cards for an n-input Boolean function that is represented by g logical gates. In this paper, we reduce the number of cards to <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11047_2024_10006_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">$2n + 8g$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>n</mi> <mo>+</mo> <mn>8</mn> <mi>g</mi> </mrow> </math></EquationSource> </InlineEquation> 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, <a href="https://doi.org/10.1007/978-981-99-7563-1-11">https://doi.org/10.1007/978-981-99-7563-1-11</a>), is available. The free-ADD technique allows our scheme to evaluate any n-input symmetric Boolean function using <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11047_2024_10006_Article_IEq3.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="92" /> </InlineMediaObject> <EquationSource Format="TEX">$2n^2+6n+2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo>+</mo> <mn>6</mn> <mi>n</mi> <mo>+</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> cards.

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

期刊论文
出版模式：

开放获取
发表日期：

2025年1月9日

查看全文

Kazunari Tozawa,
Hiraku Morita,
Takaaki Mizuki

摘要

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.