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

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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>24</mml:mn> <mml:mi>g</mml:mi> </mml:mrow> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>8</mml:mn> <mml:mi>g</mml:mi> </mml:mrow> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>+</mml:mo> <mml:mn>6</mml:mn> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> cards.