{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:55Z","timestamp":1759638955682,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,1,18]],"date-time":"2021-01-18T00:00:00Z","timestamp":1610928000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,1,18]],"date-time":"2021-01-18T00:00:00Z","timestamp":1610928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP17K00001"],"award-info":[{"award-number":["JP17K00001"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["New Gener. Comput."],"published-print":{"date-parts":[[2021,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In card-based cryptography, designing AND protocols in committed format is a major research topic. The state-of-the-art AND protocol proposed by Koch, Walzer, and H\u00e4rtel in ASIACRYPT 2015 uses only four cards, which is the minimum permissible number. The minimality of their protocol relies on somewhat \ncomplicated shuffles having non-uniform probabilities of possible outcomes. Restricting the allowed shuffles to uniform closed ones entails that, to the best of our knowledge, six cards are sufficient: the six-card AND protocol proposed by Mizuki and Sone in 2009 utilizes the random bisection cut, which is a uniform and cyclic (and hence, closed) shuffle. Thus, a question has arisen: \u201cCan we improve upon this six-card protocol using only uniform closed shuffles?\u201d In other words, the existence or otherwise of a five-card AND protocol in committed format using only uniform closed shuffles has been one of the most important open questions in this field. In this paper, we answer the question affirmatively by designing five-card committed-format AND protocols using only uniform cyclic shuffles. The shuffles that our protocols use are the random cut and random bisection cut, both of which are uniform cyclic shuffles and can be easily implemented by humans.<\/jats:p>","DOI":"10.1007\/s00354-020-00110-2","type":"journal-article","created":{"date-parts":[[2021,1,18]],"date-time":"2021-01-18T22:02:45Z","timestamp":1611007365000},"page":"97-114","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Five-Card AND Computations in Committed Format Using Only Uniform Cyclic Shuffles"],"prefix":"10.1007","volume":"39","author":[{"given":"Yuta","family":"Abe","sequence":"first","affiliation":[]},{"given":"Yu-ichi","family":"Hayashi","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8698-1043","authenticated-orcid":false,"given":"Takaaki","family":"Mizuki","sequence":"additional","affiliation":[]},{"given":"Hideaki","family":"Sone","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,18]]},"reference":[{"key":"110_CR1","doi-asserted-by":"publisher","unstructured":"Abe, Y., Hayashi, Y., Mizuki, T., Sone, H.: Five-card AND protocol in committed format using only practical shuffles. In: Proceedings of the 5th ACM ASIA Public-Key Cryptography Workshop, APKC \u201918, pp. 3\u20138. ACM, New York, NY, USA (2018). https:\/\/doi.org\/10.1145\/3197507.3197510","DOI":"10.1145\/3197507.3197510"},{"key":"110_CR2","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/3-540-46885-4_23","volume-title":"Advances in Cryptology\u2013EUROCRYPT \u201989, Lecture Notes in Computer Science","author":"B den Boer","year":"1990","unstructured":"den Boer, B.: More efficient match-making and satisfiability: the five card trick. In: Quisquater, J.J., Vandewalle, J. (eds.) Advances in Cryptology\u2013EUROCRYPT \u201989, Lecture Notes in Computer Science, vol. 434, pp. 208\u2013217. Springer, Berlin (1990). https:\/\/doi.org\/10.1007\/3-540-46885-4_23"},{"key":"110_CR3","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/3-540-48329-2_27","volume-title":"Advances in Cryptology\u2013CRYPTO \u201993, Lecture Notes in Computer Science","author":"C Cr\u00e9peau","year":"1994","unstructured":"Cr\u00e9peau, C., Kilian, J.: Discreet solitary games. In: Stinson, D.R. (ed.) Advances in Cryptology\u2013CRYPTO \u201993, Lecture Notes in Computer Science, vol. 773, pp. 319\u2013330. Springer, Berlin (1994). https:\/\/doi.org\/10.1007\/3-540-48329-2_27"},{"key":"110_CR4","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/978-3-319-70700-6_5","volume-title":"Advances in Cryptology\u2013ASIACRYPT 2017, Lecture Notes in Computer Science","author":"J Kastner","year":"2017","unstructured":"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.) Advances in Cryptology\u2013ASIACRYPT 2017, Lecture Notes in Computer Science, vol. 10626, pp. 126\u2013155. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70700-6_5"},{"key":"110_CR5","unstructured":"Koch, A.: The landscape of optimal card-based protocols. Cryptology ePrint Archive, Report 2018\/951 (2018). https:\/\/eprint.iacr.org\/2018\/951"},{"key":"110_CR6","doi-asserted-by":"publisher","unstructured":"Koch, A., Walzer, S.: Foundations for actively secure card-based cryptography. In: Farach-Colton, M., Prencipe, G., Uehara R (eds.) 10th International Conference on Fun with Algorithms (FUN 2021), vol. 157, pp. 17:1, 17:23, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Germany (2020). https:\/\/doi.org\/10.4230\/LIPIcs.FUN.2021.17","DOI":"10.4230\/LIPIcs.FUN.2021.17"},{"key":"110_CR7","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1007\/978-3-662-48797-6_32","volume-title":"Advances in Cryptology\u2013ASIACRYPT 2015, Lecture Notes in Computer Science","author":"A Koch","year":"2015","unstructured":"Koch, A., Walzer, S., H\u00e4rtel, K.: Card-based cryptographic protocols using a minimal number of cards. In: Iwata, T., Cheon, J.H. (eds.) Advances in Cryptology\u2013ASIACRYPT 2015, Lecture Notes in Computer Science, vol. 9452, pp. 783\u2013807. Springer, Berlin (2015). https:\/\/doi.org\/10.1007\/978-3-662-48797-6_32"},{"key":"110_CR8","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/s10207-013-0219-4","volume":"13","author":"T Mizuki","year":"2014","unstructured":"Mizuki, T., Shizuya, H.: A formalization of card-based cryptographic protocols via abstract machine. Int. J. Inf. Secur. 13, 15\u201323 (2014). https:\/\/doi.org\/10.1007\/s10207-013-0219-4","journal-title":"Int. J. Inf. Secur."},{"key":"110_CR9","doi-asserted-by":"crossref","unstructured":"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, pp. 3\u201311. The Institute of Electronics, Information and Communication Engineers (2017)","DOI":"10.1587\/transfun.E100.A.3"},{"key":"110_CR10","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1007\/978-3-642-02270-8_36","volume-title":"Frontiers in Algorithmics, Lecture Notes in Computer Science","author":"T Mizuki","year":"2009","unstructured":"Mizuki, T., Sone, H.: Six-card secure AND and four-card secure XOR. In: Deng, X., Hopcroft, J.E., Xue, J. (eds.) Frontiers in Algorithmics, Lecture Notes in Computer Science, vol. 5598, pp. 358\u2013369. Springer, Berlin (2009). https:\/\/doi.org\/10.1007\/978-3-642-02270-8_36"},{"key":"110_CR11","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-319-72089-0_9","volume-title":"International Conference on Information Theoretic Security, ICITS 2017, Lecture Notes in Computer Science","author":"T Nakai","year":"2017","unstructured":"Nakai, T., Shirouchi, S., Iwamoto, M., Ohta, K.: Four cards are sufficient for a card-based three-input voting protocol utilizing private permutations. In: Shikata, J. (ed.) International Conference on Information Theoretic Security, ICITS 2017, Lecture Notes in Computer Science, vol. 10681, pp. 153\u2013165. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-72089-0_9"},{"key":"110_CR12","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1007\/978-3-319-48965-0_30","volume-title":"Cryptology and Network Security, CANS 2016, Lecture Notes in Computer Science","author":"T Nakai","year":"2016","unstructured":"Nakai, T., Tokushige, Y., Misawa, Y., Iwamoto, M., Ohta, K.: Efficient card-based cryptographic protocols for millionaires\u2019 problem utilizing private permutations. In: Foresti, S., Persiano, G. (eds.) Cryptology and Network Security, CANS 2016, Lecture Notes in Computer Science, vol. 10052, pp. 500\u2013517. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-48965-0_30"},{"key":"110_CR13","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0304-3975(97)00107-2","volume":"191","author":"V Niemi","year":"1998","unstructured":"Niemi, V., Renvall, A.: Secure multiparty computations without computers. Theor. Comput. Sci. 191, 173\u2013183 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(97)00107-2","journal-title":"Theor. Comput. Sci."},{"key":"110_CR14","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/978-3-030-18419-3_13","volume-title":"Foundations and Practice of Security, Lecture Notes in Computer Science","author":"H Ono","year":"2019","unstructured":"Ono, H., Manabe, Y.: Card-based cryptographic protocols with the minimum number of cards using private operations. In: Zincir-Heywood, N., Bonfante, G., Debbabi, M., Garcia-Alfaro, J. (eds.) Foundations and Practice of Security, Lecture Notes in Computer Science, vol. 11358, pp. 193\u2013207. Springer, Cham (2019)"},{"key":"110_CR15","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/978-3-030-31500-9_10","volume-title":"Data Privacy Management, Cryptocurrencies and Blockchain Technology. Lecture Notes in Computer Science","author":"H Ono","year":"2019","unstructured":"Ono, H., Manabe, Y.: Card-based cryptographic protocols with the minimum number of rounds using private operations. In: P\u00e9rez-Sol\u00e0, C., Navarro-Arribas, G., Biryukov, A., Garcia-Alfaro, J. (eds.) Data Privacy Management, Cryptocurrencies and Blockchain Technology. Lecture Notes in Computer Science, vol. 11737, pp. 156\u2013173. Springer, Cham (2019)"},{"key":"110_CR16","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/978-3-030-19955-5_30","volume-title":"AND Protocols Using only Uniform Shuffles. Computer Science\u2014Theory and Applications. Lecture Notes in Computer Science","author":"S Ruangwises","year":"2019","unstructured":"Ruangwises, S., Itoh, T.: AND Protocols Using only Uniform Shuffles. Computer Science\u2014Theory and Applications. Lecture Notes in Computer Science, vol. 11532, pp. 349\u2013358. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-19955-5_30"},{"key":"110_CR17","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/S0304-3975(00)00409-6","volume":"259","author":"A Stiglic","year":"2001","unstructured":"Stiglic, A.: Computations with a deck of cards. Theor. Comput. Sci. 259, 671\u2013678 (2001). https:\/\/doi.org\/10.1016\/S0304-3975(00)00409-6","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"110_CR18","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s10207-019-00463-w","volume":"19","author":"I Ueda","year":"2020","unstructured":"Ueda, I., Miyahara, D., Nishimura, A., Hayashi, Y., Mizuki, T., Sone, H.: Secure implementations of a random bisection cut. Int. J. Inf. Sec. 19(4), 445\u2013452 (2020). https:\/\/doi.org\/10.1007\/s10207-019-00463-w","journal-title":"Int. J. Inf. Sec."},{"key":"110_CR19","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/978-3-319-49001-4_5","volume-title":"Theory and Practice of Natural Computing, Lecture Notes in Computer Science","author":"I Ueda","year":"2016","unstructured":"Ueda, I., Nishimura, A., Hayashi, Y., Mizuki, T., Sone, H.: How to implement a random bisection cut. In: Mart\u00edn-Vide, C., Mizuki, T., Vega-Rodr\u00edguez, M.A. (eds.) Theory and Practice of Natural Computing, Lecture Notes in Computer Science, vol. 10071, pp. 58\u201369. Springer International Publishing, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-49001-4_5"},{"key":"110_CR20","doi-asserted-by":"publisher","unstructured":"Watanabe, Y., Kuroki, Y., Suzuki, S., Koga, Y., Iwamoto, M., Ohta, K.: Card-based majority voting protocols with three inputs using three cards. In: 2018 International Symposium on Information Theory and Its Applications (ISITA), pp. 218\u2013222 (2018). https:\/\/doi.org\/10.23919\/ISITA.2018.8664324","DOI":"10.23919\/ISITA.2018.8664324"}],"container-title":["New Generation Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00354-020-00110-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00354-020-00110-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00354-020-00110-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T21:42:58Z","timestamp":1618954978000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00354-020-00110-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,18]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["110"],"URL":"https:\/\/doi.org\/10.1007\/s00354-020-00110-2","relation":{},"ISSN":["0288-3635","1882-7055"],"issn-type":[{"type":"print","value":"0288-3635"},{"type":"electronic","value":"1882-7055"}],"subject":[],"published":{"date-parts":[[2021,1,18]]},"assertion":[{"value":"26 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}