Abstract
In the research area of card-based cryptography, designing committed-format AND protocols that are efficient in terms of the number of required cards is a major topic. Such an AND protocol should receive two pairs of face-down (physical) cards representing two secret input bits, from which it should securely produce a pair of face-down cards representing the AND value of the two bits via a series of actions, such as shuffling and turning over cards, along with some helping cards. The number of required cards typically depends on allowed kinds of shuffling operations. This paper focuses on “RC-protocols” meaning to be able to use only the random cut (RC), which is the easiest shuffling operation to implement. The best committed-format AND RC-protocol currently known was devised by Stiglic in 2001, where eight cards are used (i.e., his protocol needs four helping cards). Since then, it has been an open question to determine whether there exists a committed-format AND RC-protocol using less than eight cards. In this study, we answer to the question: We propose a six-card committed-format AND RC-protocol (using exactly two random cuts). Therefore, we can reduce the number of required cards by two.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Abe Y, Hayashi Y, Mizuki T, Sone H (2018) Five-card AND protocol in committed format using only practical shuffles. In: Proceedings of the 5th ACM on ASIA public-key cryptography workshop, ACM, New York, NY, USA, APKC ’18, pp 3–8
Abe Y, Hayashi Y, Mizuki T, Sone H (2021) Five-card AND computations in committed format using only uniform cyclic shuffles. New Gener Comput. https://doi.org/10.1007/s00354-020-00110-2
Crépeau C, Kilian J (1994) Discreet solitary games. In: Stinson DR (ed) advances in cryptology—CRYPTO’ 93, Springer, Berlin, Heidelberg, Lecture Notes in Computer Science, vol 773, pp 319–330
Kastner J, Koch A, Walzer S, Miyahara D, Hayashi Y, Mizuki T, Sone H (2017) The minimum number of cards in practical card-based protocols. In: Takagi T, Peyrin T (eds) Advances in cryptology–ASIACRYPT 2017, Springer, Cham, Lecture Notes in Computer Science, vol 10626, pp 126–155
Koch A (2018) The landscape of optimal card-based protocols. Cryptology ePrint archive, report 2018/951, https://eprint.iacr.org/2018/951
Koch A, Walzer S, Härtel K (2015) Card-based cryptographic protocols using a minimal number of cards. In: Iwata T, Cheon JH (eds) Advances in cryptology–ASIACRYPT 2015, Springer, Berlin, Heidelberg, Lecture Notes in Computer Science, vol 9452, pp 783–807
Mizuki T, Shizuya H (2017) Computational model of card-based cryptographic protocols and its applications. IEICE Trans Fundam Electron Commun Comput Sci E 100A(1):3–11. https://doi.org/10.1587/transfun.E100.A.3
Mizuki T, Sone H (2009) Six-card secure AND and four-card secure XOR. In: Deng X, Hopcroft JE, Xue J (eds) Frontiers in algorithmics, Springer, Berlin, Heidelberg, Lecture Notes in Computer Science, vol 5598, pp 358–369
Mizuki T, Uchiike F, Sone H (2006) Securely computing XOR with 10 cards. Australas J Comb 36:279–293
Nakai T, Misawa Y, Tokushige Y, Iwamoto M, Ohta K (2021) How to solve millionaires’ problem with two kinds of cards. New Gener Comput. https://doi.org/10.1007/s00354-020-00118-8
Niemi V, Renvall A (1998) Secure multiparty computations without computers. Theor Comput Sci 191(1–2):173–183. https://doi.org/10.1016/S0304-3975(97)00107-2
Nishimura A, Nishida T, Hayashi Y, Mizuki T, Sone H (2018) Card-based protocols using unequal division shuffles. Soft Comput 22:361–371. https://doi.org/10.1007/s00500-017-2858-2
Ono H, Manabe Y (2020) Card-based cryptographic logical computations using private operations. New Gener Comput 39:19–40
Ruangwises S, Itoh T (2019) AND protocols using only uniform shuffles. In: van Bevern R, Kucherov G (eds) Computer science—theory and applications, Springer, Cham, Lecture Notes in Computer Science, vol 11532, pp 349–358
Ruangwises S, Itoh T (2020) Physical zero-knowledge proof for Numberlink puzzle and k vertex-disjoint paths problem. New Gener Comput. https://doi.org/10.1007/s00354-020-00114-y
Stiglic A (2001) Computations with a deck of cards. Theor Comput Sci 259(1–2):671–678. https://doi.org/10.1016/S0304-3975(00)00409-6
Toyoda K, Miyahara D, Mizuki T, Sone H (2020) Six-card finite-runtime XOR protocol with only random cut. In: Proceedings of the 7th ACM on ASIA public-key cryptography workshop, ACM, New York, NY, USA, APKC’20, pp 1–7
Ueda I, Nishimura A, Hayashi Y, Mizuki T, Sone H (2016) How to implement a random bisection cut. In: Martín-Vide C, Mizuki T, Vega-Rodríguez MA (eds) Theory and practice of natural computing, Springer, Cham, Lecture Notes in Computer Science, vol 10071, pp 58–69
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Abe, Y., Mizuki, T. & Sone, H. Committed-format AND protocol using only random cuts. Nat Comput 20, 639–645 (2021). https://doi.org/10.1007/s11047-021-09862-2
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11047-021-09862-2