Single-Shuffle Card-Based Protocol with Eight Cards per Gate | SpringerLink
Skip to main content
Springer Nature Link
Log in

Single-Shuffle Card-Based Protocol with Eight Cards per Gate

  • Conference paper
  • First Online:
Unconventional Computation and Natural Computation (UCNC 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14003))

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 of the seminal work is by Shinagawa and Nuida (Discrete Applied Mathematics 2021) that shows any Boolean function can be constructed by shuffling only once based on the garbling scheme. Their construction requires \(2n + 24g\) 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\) for arbitrary functions while keeping it working with only one shuffle.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 7435
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 9294
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Note that a similar procedure was used for changing an integer encoding into two commitments [22].

References

  1. Attrapadung, N., et al.: Oblivious linear group actions and applications. In: Vigna, G., Shi, E. (eds.) ACM CCS 2021, pp. 630–650. ACM Press (2021). https://doi.org/10.1145/3460120.3484584

  2. Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: 22nd ACM STOC, pp. 503–513. ACM Press (1990). https://doi.org/10.1145/100216.100287

  3. Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of garbled circuits. In: Yu, T., Danezis, G., Gligor, V.D. (eds.) ACM CCS 2012, pp. 784–796. ACM Press (2012). https://doi.org/10.1145/2382196.2382279

  4. Boer, B.: More efficient match-making and satisfiability The Five Card Trick. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 208–217. Springer, Heidelberg (1990). https://doi.org/10.1007/3-540-46885-4_23

    Chapter  Google Scholar 

  5. Haga, R., Hayashi, Y., Miyahara, D., Mizuki, T.: Card-minimal protocols for three-input functions with standard playing cards. In: AFRICACRYPT 2022. LNCS, vol. 13503, pp. 448–468. Springer, Cham (2022)

    Google Scholar 

  6. Heather, J., Schneider, S., Teague, V.: Cryptographic protocols with everyday objects. Formal Aspects Comput. 26(1), 37–62 (2014). https://doi.org/10.1007/s00165-013-0274-7

  7. Ishikawa, R., Chida, E., Mizuki, T.: Efficient card-based protocols for generating a hidden random permutation without fixed points. In: Calude, C.S., Dinneen, M.J. (eds.) UCNC 2015. LNCS, vol. 9252, pp. 215–226. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21819-9_16

  8. Isuzugawa, R., Miyahara, D., Mizuki, T.: Zero-knowledge proof protocol for Cryptarithmetic using dihedral cards. In: Kostitsyna, I., Orponen, P. (eds.) UCNC 2021. LNCS, vol. 12984, pp. 51–67. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-87993-8_4

  9. Kastner, J., Koch, A., Walzer, S., Miyahara, D., Hayashi, Y., Mizuki, T., Sone, H.: The minimum number of cards in practical card-based protocols. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10626, pp. 126–155. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70700-6_5

    Chapter  MATH  Google Scholar 

  10. Koch, A., Schrempp, M., Kirsten, M.: Card-based cryptography meets formal verification. New Gener. Comput. 39(1), 115–158 (2021). https://doi.org/10.1007/s00354-020-00120-0

  11. Koch, A., Walzer, S., Härtel, K.: Card-based cryptographic protocols using a minimal number of cards. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 783–807. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_32

    Chapter  Google Scholar 

  12. Koyama, H., Miyahara, D., Mizuki, T., Sone, H.: A secure three-input AND protocol with a standard deck of minimal cards. In: Santhanam, R., Musatov, D. (eds.) CSR 2021. LNCS, vol. 12730, pp. 242–256. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-79416-3_14

    Chapter  MATH  Google Scholar 

  13. Kuzuma, T., Toyoda, K., Miyahara, D., Mizuki, T.: Card-based single-shuffle protocols for secure multiple-input AND and XOR computations. In: ASIA Public-Key Cryptography, pp. 51–58. ACM, NY (2022). https://doi.org/10.1145/3494105.3526236

  14. Miyahara, D., Ueda, I., Hayashi, Y., Mizuki, T., Sone, H.: Analyzing execution time of card-based protocols. In: Stepney, S., Verlan, S. (eds.) UCNC 2018. LNCS, vol. 10867, pp. 145–158. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-92435-9_11

    Chapter  Google Scholar 

  15. Mizuki, T., Asiedu, I.K., Sone, H.: Voting with a logarithmic number of cards. In: Mauri, G., Dennunzio, A., Manzoni, L., Porreca, A.E. (eds.) UCNC 2013. LNCS, vol. 7956, pp. 162–173. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39074-6_16

    Chapter  Google Scholar 

  16. Mizuki, T., Kumamoto, M., Sone, H.: The five-card trick can be done with four cards. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 598–606. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_36

    Chapter  Google Scholar 

  17. Mizuki, T., Shizuya, H.: A formalization of card-based cryptographic protocols via abstract machine. Int. J. Inf. Secur. 13(1), 15–23 (2013). https://doi.org/10.1007/s10207-013-0219-4

    Article  Google Scholar 

  18. Mizuki, T., Sone, H.: Six-card secure AND and four-card secure XOR. In: Deng, X., Hopcroft, J.E., Xue, J. (eds.) FAW 2009. LNCS, vol. 5598, pp. 358–369. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02270-8_36

    Chapter  Google Scholar 

  19. Nishida, T., Hayashi, Y., Mizuki, T., Sone, H.: Card-based protocols for any boolean function. In: Jain, R., Jain, S., Stephan, F. (eds.) TAMC 2015. LNCS, vol. 9076, pp. 110–121. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-17142-5_11

    Chapter  Google Scholar 

  20. Ruangwises, S., Itoh, T.: Physical ZKP for connected spanning subgraph: applications to bridges puzzle and other problems. In: Kostitsyna, I., Orponen, P. (eds.) UCNC 2021. LNCS, vol. 12984, pp. 149–163. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-87993-8_10

    Chapter  MATH  Google Scholar 

  21. Ruangwises, S., Itoh, T.: Securely computing the n-variable equality function with 2n cards. Theor. Comput. Sci. 887, 99–110 (2021). https://doi.org/10.1016/j.tcs.2021.07.007

  22. Shikata, H., Toyoda, K., Miyahara, D., Mizuki, T.: Card-minimal protocols for symmetric boolean functions of more than seven inputs. In: ICTAC 2022. LNCS, vol. 13572, pp. 388–406. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-17715-6_25

  23. Shinagawa, K., Mizuki, T.: The six-card trick: secure computation of three-input equality. In: Lee, K. (ed.) ICISC 2018. LNCS, vol. 11396, pp. 123–131. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-12146-4_8

    Chapter  Google Scholar 

  24. Shinagawa, K., Nuida, K.: A single shuffle is enough for secure card-based computation of any boolean circuit. Discret. Appl. Math. 289, 248–261 (2021). https://doi.org/10.1016/j.dam.2020.10.013

    Article  MathSciNet  MATH  Google Scholar 

  25. Toyoda, K., Miyahara, D., Mizuki, T.: Another use of the five-card trick: card-minimal secure three-input majority function evaluation. In: Adhikari, A., Küsters, R., Preneel, B. (eds.) INDOCRYPT 2021. LNCS, vol. 13143, pp. 536–555. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92518-5_24

    Chapter  Google Scholar 

Download references

Acknowledgements

This work was supported by JSPS KAKENHI Grant Numbers JP21H05052, JP21K11881, and JST, CREST Grant Number JPMJCR22M1, Japan.

Author information

Authors and Affiliations

  1. The University of Tokyo, Tokyo, Japan

    Kazunari Tozawa

  2. University of St. Gallen, St. Gallen, Switzerland

    Hiraku Morita

  3. Tohoku University, Miyagi, Japan

    Takaaki Mizuki

Authors
  1. Kazunari Tozawa
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hiraku Morita
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Takaaki Mizuki
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kazunari Tozawa .

Editor information

Editors and Affiliations

  1. University of North Florida, Jacksonville, FL, USA

    Daniela Genova

  2. University of Turku, Turku, Finland

    Jarkko Kari

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Tozawa, K., Morita, H., Mizuki, T. (2023). Single-Shuffle Card-Based Protocol with Eight Cards per Gate. In: Genova, D., Kari, J. (eds) Unconventional Computation and Natural Computation. UCNC 2023. Lecture Notes in Computer Science, vol 14003. Springer, Cham. https://doi.org/10.1007/978-3-031-34034-5_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-34034-5_12

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-34033-8

  • Online ISBN: 978-3-031-34034-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation