Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

How to Implement a Non-uniform or Non-closed Shuffle

  • Conference paper
  • First Online:
Theory and Practice of Natural Computing (TPNC 2020)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12494))

Abstract

Card-based protocols allow to perform secure multiparty computations using a deck of physical cards, and rely on shuffle actions such as the (normal) shuffle, the random cut, and the random bisection cut. A shuffle action is mathematically defined by a pair of a permutation set (which is a subset of the symmetric group) and a probability distribution on it; while one can theoretically consider any shuffle action in mind, he or she may be unable to determine whether it can be easily implemented by human hands. As one of the most general results, Koch and Walzer showed that any uniform closed shuffle (meaning that its permutation set is a subgroup and its distribution is uniform) can be implemented by human hands with the help of additional cards. However, there are several existing protocols which use non-uniform and/or non-closed shuffles. To implement these specific shuffles, Nishimura et al. proposed an idea of using (special) physical cases that can store piles of cards as well as Koch and Walzer proposed an implementation of a specific non-closed shuffle with additional cards. Because their implementations handle a limited class of non-uniform and/or non-closed shuffles, it is still open to find a general method for implementing any shuffle. In this paper, we solve the above problem; we implement “any” shuffle with only additional cards, provided that every probability of its distribution is a rational number. Therefore, our implementation works for any non-closed or non-uniform shuffle (if the distribution is rational as above).

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
$34.99 /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
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • 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.

    After swapping them, the padding 2q cards are discarded.

References

  1. 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 

  2. Hshimoto, Y., Nuida, K., Shinagawa, K., Inamura, M., Hanaoka, G.: Toward finite-runtime card-based protocol for generating a hidden random permutation without fixed points. In: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 2018. Lecture Notes in Computer Science, vol. E101.A , no. 9, pp. 1503–1511 (2018). https://doi.org/10.1587/transfun.E101.A.1503

  3. Kastner, J., et al.: 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  Google Scholar 

  4. Koch, A.: The landscape of optimal card-based protocols (2018). https://eprint.iacr.org/2018/951

  5. Koch, A., Schrempp, M., Kirsten, M.: Card-based cryptography meets formal verification. In: Galbraith, S.D., Moriai, S. (eds.) Advances in Cryptology - ASIACRYPT 2019. Lecture Notes in Computer Science, vol. 11921, pp. 488–517. Springer International Publishing, Cham (2019). https://doi.org/10.1007/978-3-030-34578-5_18

    Chapter  Google Scholar 

  6. Koch, A., Walzer, S.: Foundations for actively secure card-based cryptography. Cryptology ePrint Archive, Report 2017/422 (2017)

    Google Scholar 

  7. 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 

  8. Miyahara, D., Hayashi, Y., Mizuki, T., Sone, H.: Practical card-based implementations of Yao’s millionaire protocol. Theoret. Comput. Sci. 803, 207–221 (2020). https://doi.org/10.1016/j.tcs.2019.11.005

    Article  MathSciNet  MATH  Google Scholar 

  9. Miyahara, D., et al.: Card-based ZKP protocols for Takuzu and Juosan. In: Farach-Colton, M., Prencipe, G., Uehara, R. (eds.) 10th International Conference on Fun with Algorithms (FUN 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 157, pp. 20:1–20:21. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2020). https://drops.dagstuhl.de/opus/volltexte/2020/12781

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

    Article  Google Scholar 

  11. Mizuki, T., Shizuya, H.: Computational model of card-based cryptographic protocols and its applications. In: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E100.A, no. 1, pp. 3–11 (2017). https://doi.org/10.1587/transfun.E100.A.3

  12. 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 

  13. Nishida, T., Mizuki, T., Sone, H.: Securely computing the three-input majority function with eight cards. In: Dediu, A., Martín-Vide, C., Truthe, B., Vega-Rodríguez, A.M. (eds.) Theory and Practice of Natural Computing. TPNC 2013. Lecture Notes in Computer Science, vol. 8273, pp. 193–204. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-45008-2_16

  14. Nishimura, A., Hayashi, Y., Mizuki, T., Sone, H.: Pile-shifting scramble for card-based protocols. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E101-A, 1494–1502 (2017). https://doi.org/10.1587/transfun.E101.A.1494

  15. Nishimura, A., Nishida, T., Hayashi, Y., Mizuki, T., Sone, H.: Five-card secure computations using unequal division shuffle. In: Dediu, A., Magdalena, L., Martín-Vide, C. (eds.) Theory and Practice of Natural Computing. TPNC 2015. Lecture Notes in Computer Science, vol. 9477, pp. 109–120. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-26841-5_9

  16. Nishimura, A., Nishida, T., Hayashi, Y., Mizuki, T., Sone, H.: Card-based protocols using unequal division shuffles. Soft Comput. 22, 361–371 (2018). https://doi.org/10.1007/s00500-017-2858-2

    Article  MATH  Google Scholar 

  17. Ruangwises, S., Itoh, T.: AND protocols using only uniform shuffles. In: van Bevern, R., Kucherov, G. (eds.) Computer Science - Theory and Applications. CSR 2019. Lecture Notes in Computer Science, vol. 11532, pp. 349–358. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-19955-5_30

  18. Sasaki, T., Miyahara, D., Mizuki, T., Sone, H.: Efficient card-based zero-knowledge proof for Sudoku. Theoret. Comput. Sci. 839, 135–142 (2020). https://doi.org/10.1016/j.tcs.2020.05.036

    Article  MathSciNet  MATH  Google Scholar 

  19. Takashima, K., et al.: Card-based secure ranking computations. In: Li, Y., Cardei, M., Huang, Y. (eds.) Combinatorial Optimization and Applications. COCOA 2019. Lecture Notes in Computer Science, vol. 11949, pp. 461–472. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36412-0_37

  20. Takashima, K., Miyahara, D., Mizuki, T., Sone, H.: Card-based protocol against actively revealing card attack. In: Martín-Vide, C., Pond, G., Vega-Rodríguez, M. (eds.) Theory and Practice of Natural Computing. TPNC 2019. Lecture Notes in Computer Science, vol. 11934, pp. 95–106. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34500-6_6

  21. Ueda, I., Miyahara, D., Nishimura, A., Hayashi, Y., Mizuki, T., Sone, H.: Secure implementations of a random bisection cut. Int. J. Inf. Secur. 19, 445–452 (2020). https://doi.org/10.1007/s10207-019-00463-w

    Article  Google Scholar 

  22. Ueda, I., Nishimura, A., Hayashi, Y., Mizuki, T., Sone, H.: How to implement a random bisection cut. In: Martín-Vide, C., Mizuki, T., Vega-Rodríguez, M.A. (eds.) TPNC 2016. LNCS, vol. 10071, pp. 58–69. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-49001-4_5

    Chapter  Google Scholar 

Download references

Acknowledgments

This work was supported in part by JSPS KAKENHI Grant Numbers JP19J21153 and JP19K11956. We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper.

Author information

Authors and Affiliations

  1. Graduate School of Information Sciences, Tohoku University, 6–3–09 Aramaki-Aza-Aoba, Aoba, Sendai, 980–8579, Japan

    Takahiro Saito, Daiki Miyahara, Yuta Abe & Hiroki Shizuya

  2. Cyberscience Center, Tohoku University, 6–3 Aramaki-Aza-Aoba, Aoba, Sendai, 980–8578, Japan

    Takaaki Mizuki

  3. National Institute of Advanced Industrial Science and Technology (AIST), 2–4–7 Aomi, Koto-ku, Tokyo, 135–0064, Japan

    Daiki Miyahara

Authors
  1. Takahiro Saito
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daiki Miyahara
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yuta Abe
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Takaaki Mizuki
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Hiroki Shizuya
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Takahiro Saito .

Editor information

Editors and Affiliations

  1. Rovira i Virgili University, Tarragona, Spain

    Carlos Martín-Vide

  2. University of Extremadura, Cáceres, Spain

    Miguel A. Vega-Rodríguez

  3. Chung Yuan Christian University, Taoyuan, Taiwan

    Miin-Shen Yang

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Saito, T., Miyahara, D., Abe, Y., Mizuki, T., Shizuya, H. (2020). How to Implement a Non-uniform or Non-closed Shuffle. In: Martín-Vide, C., Vega-Rodríguez, M.A., Yang, MS. (eds) Theory and Practice of Natural Computing. TPNC 2020. Lecture Notes in Computer Science(), vol 12494. Springer, Cham. https://doi.org/10.1007/978-3-030-63000-3_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-63000-3_9

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-62999-1

  • Online ISBN: 978-3-030-63000-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation