Document Open Access Logo

Foundations for Actively Secure Card-Based Cryptography

Authors Alexander Koch , Stefan Walzer

PDF
Thumbnail PDF

File

LIPIcs.FUN.2021.17.pdf
  • Filesize: 0.82 MB
  • 23 pages

Document Identifiers

Author Details

Alexander Koch
  • Karlsruhe Institute of Technology (KIT), Germany
Stefan Walzer
  • Technische Universität Ilmenau, Germany

Acknowledgements

We would like to thank the anonymous reviewers for helpful comments.

Cite AsGet BibTex

Alexander Koch and Stefan Walzer. Foundations for Actively Secure Card-Based Cryptography. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FUN.2021.17

Abstract

Card-based cryptography, as first proposed by den Boer [den Boer, 1989], enables secure multiparty computation using only a deck of playing cards. Many protocols as of yet come with an “honest-but-curious” disclaimer. However, modern cryptography aims to provide security also in the presence of active attackers that deviate from the protocol description. In the few places where authors argue for the active security of their protocols, this is done ad-hoc and restricted to the concrete operations needed, often using additional physical tools, such as envelopes or sliding cover boxes. This paper provides the first systematic approach to active security in card-based protocols. The main technical contribution concerns shuffling operations. A shuffle randomly permutes the cards according to a well-defined distribution but hides the chosen permutation from the players. We show how the large and natural class of uniform closed shuffles, which are shuffles that select a permutation uniformly at random from a permutation group, can be implemented using only a linear number of helping cards. This ensures that any protocol in the model of Mizuki and Shizuya [Mizuki and Shizuya, 2014] can be realized in an actively secure fashion, as long as it is secure in this abstract model and restricted to uniform closed shuffles. Uniform closed shuffles are already sufficient for securely computing any circuit [Mizuki and Sone, 2009]. In the process, we develop a more concrete model for card-based cryptographic protocols with two players, which we believe to be of independent interest.

Subject Classification

ACM Subject Classification
  • Security and privacy → Information-theoretic techniques
  • Security and privacy → Usability in security and privacy
  • Theory of computation → Models of computation
Keywords
  • Card-Based Protocols
  • Card Shuffling
  • Secure Multiparty Computation
  • Active Security
  • Cryptography without Computers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Yuta Abe, Yu ichi Hayashi, Takaaki Mizuki, and Hideaki Sone. Five-card and protocol in committed format using only practical shuffles. In Keita Emura, Jae Hong Seo, and Yohei Watanabe, editors, APKC@AsiaCCS 2018, pages 3-8. ACM, 2018. URL: https://doi.org/10.1145/3197507.3197510.
  2. Eddie Cheung, Chris Hawthorne, and Patrick Lee. CS 758 project: Secure computation with playing cards, 2013. URL: https://cdchawthorne.com/writings/secure_playing_cards.pdf.
  3. Claude Crépeau and Joe Kilian. Discreet solitary games. In Douglas R. Stinson, editor, CRYPTO '93, volume 773 of LNCS, pages 319-330. Springer, 1993. URL: https://doi.org/10.1007/3-540-48329-2_27.
  4. Bert den Boer. More efficient match-making and satisfiability: The five card trick. In Jean-Jacques Quisquater and Joos Vandewalle, editors, EUROCRYPT '89, volume 434 of LNCS, pages 208-217. Springer, 1989. URL: https://doi.org/10.1007/3-540-46885-4_23.
  5. Yuval Ishai, Amit Sahai, and David A. Wagner. Private circuits: Securing hardware against probing attacks. In Dan Boneh, editor, CRYPTO 2003, volume 2729 of LNCS, pages 463-481. Springer, 2003. URL: https://doi.org/10.1007/978-3-540-45146-4_27.
  6. Rie Ishikawa, Eikoh Chida, and Takaaki Mizuki. Efficient card-based protocols for generating a hidden random permutation without fixed points. In Cristian S. Calude and Michael J. Dinneen, editors, UCNC 2015, volume 9252 of LNCS, pages 215-226. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21819-9_16.
  7. Julia Kastner, Alexander Koch, Stefan Walzer, Daiki Miyahara, Yu ichi Hayashi, Takaaki Mizuki, and Hideaki Sone. The minimum number of cards in practical card-based protocols. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, volume 10626 of LNCS, pages 126-155. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-70700-6_5.
  8. Alexander Koch. The landscape of optimal card-based protocols. IACR Cryptology ePrint Archive, 2018. Report 2018/951. URL: https://eprint.iacr.org/2018/951.
  9. Alexander Koch. Cryptographic Protocols from Physical Assumptions. PhD thesis, Karlsruhe Institute of Technology (KIT), 2019. URL: https://doi.org/10.5445/IR/1000097756.
  10. Alexander Koch and Stefan Walzer. Foundations for actively secure card-based cryptography. IACR Cryptology ePrint Archive, 2017. Report 2017/423. URL: https://eprint.iacr.org/2017/423.
  11. Alexander Koch and Stefan Walzer. Private function evaluation with cards. IACR Cryptology ePrint Archive, 2018. Report 2018/1113. URL: https://eprint.iacr.org/2018/1113.
  12. Alexander Koch, Stefan Walzer, and Kevin Härtel. Card-based cryptographic protocols using a minimal number of cards. In Tetsu Iwata and Jung Hee Cheon, editors, ASIACRYPT 2015, volume 9452 of LNCS, pages 783-807. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48797-6_32.
  13. Antonio Marcedone, Zikai Wen, and Elaine Shi. Secure dating with four or fewer cards. IACR Cryptology ePrint Archive, 2015. Report 2015/1031. URL: https://eprint.iacr.org/2015/1031.
  14. Takaaki Mizuki. Card-based protocols for securely computing the conjunction of multiple variables. Theoretical Computer Science, 622:34-44, 2016. URL: https://doi.org/10.1016/j.tcs.2016.01.039.
  15. Takaaki Mizuki, Isaac Kobina Asiedu, and Hideaki Sone. Voting with a logarithmic number of cards. In Giancarlo Mauri, Alberto Dennunzio, Luca Manzoni, and Antonio E. Porreca, editors, UCNC 2013, volume 7956 of LNCS, pages 162-173. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-39074-6_16.
  16. Takaaki Mizuki, Michihito Kumamoto, and Hideaki Sone. The five-card trick can be done with four cards. In Xiaoyun Wang and Kazue Sako, editors, ASIACRYPT 2012, volume 7658 of LNCS, pages 598-606. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-34961-4_36.
  17. Takaaki Mizuki and Hiroki Shizuya. A formalization of card-based cryptographic protocols via abstract machine. International Journal of Information Security, 13(1):15-23, 2014. URL: https://doi.org/10.1007/s10207-013-0219-4.
  18. Takaaki Mizuki and Hiroki Shizuya. Practical card-based cryptography. In Alfredo Ferro, Fabrizio Luccio, and Peter Widmayer, editors, FUN 2014, volume 8496 of LNCS, pages 313-324. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-07890-8_27.
  19. Takaaki Mizuki and Hideaki Sone. Six-card secure AND and four-card secure XOR. In Xiaotie Deng, John E. Hopcroft, and Jinyun Xue, editors, FAW 2009, volume 5598 of LNCS, pages 358-369. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02270-8_36.
  20. Tal Moran and Moni Naor. Polling with physical envelopes: A rigorous analysis of a human-centric protocol. In Serge Vaudenay, editor, EUROCRYPT 2006, volume 4004 of LNCS, pages 88-108. Springer, 2006. URL: https://doi.org/10.1007/11761679_7.
  21. Tal Moran and Moni Naor. Basing cryptographic protocols on tamper-evident seals. Theoretical Computer Science, 411(10):1283-1310, 2010. URL: https://doi.org/10.1016/j.tcs.2009.10.023.
  22. Takeshi Nakai, Satoshi Shirouchi, Mitsugu Iwamoto, and Kazuo Ohta. Four cards are sufficient for a card-based three-input voting protocol utilizing private permutations. In Junji Shikata, editor, ICITS 2017, volume 10681 of LNCS, pages 153-165. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-72089-0_9.
  23. Takeshi Nakai, Yuuki Tokushige, Yuto Misawa, Mitsugu Iwamoto, and Kazuo Ohta. Efficient card-based cryptographic protocols for millionaires' problem utilizing private permutations. In Sara Foresti and Giuseppe Persiano, editors, CANS 2016, volume 10052 of LNCS, pages 500-517, 2016. URL: https://doi.org/10.1007/978-3-319-48965-0_30.
  24. Valtteri Niemi and Ari Renvall. Secure multiparty computations without computers. Theoretical Computer Science, 191(1-2):173-183, 1998. URL: https://doi.org/10.1016/S0304-3975(97)00107-2.
  25. Takuya Nishida, Yu-ichi Hayashi, Takaaki Mizuki, and Hideaki Sone. Card-based protocols for any boolean function. In Rahul Jain, Sanjay Jain, and Frank Stephan, editors, TAMC 2015, volume 9076 of LNCS, pages 110-121. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-17142-5_11.
  26. Takuya Nishida, Takaaki Mizuki, and Hideaki Sone. Securely computing the three-input majority function with eight cards. In Adrian Horia Dediu, Carlos Martín-Vide, Bianca Truthe, and Miguel A. Vega-Rodríguez, editors, TPNC 2013, volume 8273 of LNCS, pages 193-204. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-45008-2_16.
  27. Akihiro Nishimura, Yu-ichi Hayashi, Takaaki Mizuki, and Hideaki Sone. An implementation of non-uniform shuffle for secure multi-party computation. In AsiaPKC 2016, pages 49-55. ACM, 2016. URL: https://doi.org/10.1145/2898420.2898425.
  28. Akihiro Nishimura, Takuya Nishida, Yu-ichi Hayashi, Takaaki Mizuki, and Hideaki Sone. Five-card secure computations using unequal division shuffle. In Adrian Horia Dediu, Luis Magdalena, and Carlos Martín-Vide, editors, TPNC 2015, volume 9477 of LNCS, pages 109-120. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-26841-5_9.
  29. Akihiro Nishimura, Takuya Nishida, Yu-ichi Hayashi, Takaaki Mizuki, and Hideaki Sone. Card-based protocols using unequal division shuffles. Soft Computing, 22(2):361-371, 2018. URL: https://doi.org/10.1007/s00500-017-2858-2.
  30. Kazumasa Shinagawa, Takaaki Mizuki, Jacob C. N. Schuldt, Koji Nuida, Naoki Kanayama, Takashi Nishide, Goichiro Hanaoka, and Eiji Okamoto. Secure multi-party computation using polarizing cards. In Keisuke Tanaka and Yuji Suga, editors, IWSEC 2015, volume 9241 of LNCS, pages 281-297. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-22425-1_17.
  31. Anton Stiglic. Computations with a deck of cards. Theoretical Computer Science, 259(1-2):671-678, 2001. URL: https://doi.org/10.1016/S0304-3975(00)00409-6.
  32. Itaru Ueda, Akihiro Nishimura, Yu-ichi Hayashi, Takaaki Mizuki, and Hideaki Sone. How to implement a random bisection cut. In Carlos Martín-Vide, Takaaki Mizuki, and Miguel A. Vega-Rodríguez, editors, TPNC 2016, pages 58-69. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-49001-4_5.
  33. Tom Verhoeff. The zero-knowledge match maker, 2014. URL: https://www.win.tue.nl/~wstomv/publications/liber-AMiCorum-arjeh-bijdrage-van-tom-verhoeff.pdf.
  34. Yohei Watanabe, Yoshihisa Kuroki, Shinnosuke Suzuki, Yuta Koga, Mitsugu Iwamoto, and Kazuo Ohta. Card-based majority voting protocols with three inputs using three cards. In International Symposium on Information Theory and Its Applications, ISITA 2018, pages 218-222. IEEE, 2018. URL: https://doi.org/10.23919/ISITA.2018.8664324.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact