Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
New Generation Computing
Published in: New Generation Computing 1/2022

02-04-2022

Graph Automorphism Shuffles from Pile-Scramble Shuffles

Authors: Kengo Miyamoto, Kazumasa Shinagawa

Published in: New Generation Computing | Issue 1/2022

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

A pile-scramble shuffle is one of the most effective shuffles in card-based cryptography. Indeed, many card-based protocols are constructed from pile-scramble shuffles. This paper aims to study the power of pile-scramble shuffles. In particular, for any directed graph G, we introduce a new protocol called “a graph shuffle protocol for G”, and show that it can be implemented using pile-scramble shuffles only. Our proposed protocol requires \(2(n+m)\) cards, where n and m are the numbers of vertices and edges of G, respectively. The number of pile-scramble shuffles is \(k+1\), where \(1 \le k \le n\) is the number of distinct degrees of vertices of G. As an application, a random cut for n cards, which is also an important shuffle, can be implemented by 3n cards and two pile-scramble shuffles.
previous article Efficient Card-Based Majority Voting Protocols
next article Enhancing Linear Algebraic Computation of Logic Programs Using Sparse Representation

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
Our classification focuses on the group structure of permutations: the cyclic groups (RCs) and the symmetric groups (PSSs). Since RBCs are historically important shuffles and the intersection of RCs and PSSs, we classify them as RC, RBC, and PSS.
 
2
We regard undirected graphs as directed graphs by identifying each undirected edge with two directed edges with opposite directions.
 
3
Koch and Walzer [17] considered a similar notion and proposed a protocol for any uniform closed shuffles. The main difference of their model and our model is that their model allows a randomness generation in the head (see “Related works” in Introduction).
 
4
Note that this rearrangement is possible without looking under the cards since the subscripts of \(\alpha _i\) are public information.
 
5
The order of the pairs of helping cards is not essential.
 
6
We remark that this idea works for every graphs such that all vertices have the same degree.
 
Literature
1.
Abe, Y., Hayashi, Y., Mizuki, T., Sone, H.: Five-card AND protocol in committed format using only practical shuffles. In: Emura, K., Seo, J.H., Watanabe, Y. (eds.) Proceedings of the 5th ACM on ASIA Public-Key Cryptography Workshop, APKC@AsiaCCS, Incheon, June 4, 2018, pp. 3–8. ACM (2018)
2.
Abe, Y., Hayashi, Y., Mizuki, T., Sone, H.: Five-card AND computations in committed format using only uniform cyclic shuffles. New Gener. Comput. 39(1), 97–114 (2021)CrossRef
3.
Abe, Y., Mizuki, T., Sone, H.: Committed-format AND protocol using only random cuts. Nat. Comput. 20(4), 639–645 (2021)MathSciNetCrossRef
4.
Bultel, X., Dreier, J., Dumas, J., Lafourcade, P.: Physical zero-knowledge proofs for akari, takuzu, kakuro and kenken. In: Demaine, E. D., Grandoni, F. (eds.) 8th International Conference on Fun with Algorithms, FUN 2016, June 8–10, 2016, La Maddalena, Italy, LIPIcs, vol. 49, pp. 8:1–8:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
5.
Bultel, X., Dreier, J., Dumas, J., Lafourcade, P., Miyahara, D., Mizuki, T., Nagao, A., Sasaki, T., Shinagawa, K., Sone, H.: Physical zero-knowledge proof for makaro. In: Izumi, T., Kuznetsov, P. (eds.) Stabilization, Safety, and Security of Distributed Systems—20th International Symposium, SSS 2018, Tokyo, Japan, November 4–7, 2018, Proceedings, Lecture Notes in Computer Science, vol. 11201, pp. 111–125. Springer (2018)
6.
7.
Crépeau, C., Kilian, J.: Discreet solitary games. In: Stinson, D. R. (ed.) Advances in Cryptology—CRYPTO ’93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings, Lecture Notes in Computer Science, vol. 773, pp. 319–330. Springer (1993)
8.
den Boer, B.: More efficient match-making and satisfiability: the Five Card Trick. In: Quisquater, J., Vandewalle, J. (eds.) Advances in Cryptology—EUROCRYPT ’89, Workshop on the Theory and Application of of Cryptographic Techniques, Houthalen, Belgium, April 10–13, 1989, Proceedings, Lecture Notes in Computer Science, vol. 434, pp. 208–217. Springer (1989)
9.
Dumas, J., Lafourcade, P., Miyahara, D., Mizuki, T., Sasaki, T., Sone, H.: Interactive physical zero-knowledge proof for norinori. In Du, D., Duan, Z., Tian, C. (eds.) Computing and Combinatorics—25th International Conference, COCOON 2019, Xi’an, China, July 29–31, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11653, pp. 166–177. Springer (2019)
10.
Chartrand, L.L.G., Zhang, P.: Graphs & Digraphs (six edition). CRC Press (2015)
11.
Gradwohl, R., Naor, M., Pinkas, B., Rothblum, G.N.: Cryptographic and physical zero-knowledge proof systems for solutions of sudoku puzzles. In: Fun with Algorithms, 4th International Conference, FUN 2007, Castiglioncello, Italy, June 3–5, 2007, Proceedings, pp. 166–182 (2007)
12.
Hashimoto, Y., Shinagawa, K., Nuida, K., Inamura, M., Hanaoka, G.: Secure grouping protocol using a deck of cards. In: Shikata, J. (ed.) Information Theoretic Security—10th International Conference, ICITS 2017, Hong Kong, China, November 29–December 2, 2017, Proceedings, Lecture Notes in Computer Science, vol. 10681, pp. 135–152. Springer (2017)
13.
Heather, J., Schneider, S., Teague, V.: Cryptographic protocols with everyday objects. Formal Asp. Comput. 26(1), 37–62 (2014)CrossRef
14.
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.) Unconventional Computation and Natural Computation—14th International Conference, UCNC 2015, Auckland, New Zealand, August 30–September 3, 2015, Proceedings, Lecture Notes in Computer Science, vol. 9252, pp. 215–226. Springer (2015)
15.
Isuzugawa, R., Toyoda, K., Sasaki, Y., Miyahara, D., Mizuki, T.: A card-minimal three-input AND protocol using two shuffles. In: Chen, C., Hon, W., Hung, L., Lee, C. (eds.) Computing and Combinatorics—27th International Conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021, Proceedings, Lecture Notes in Computer Science, vol. 13025, pp. 668–679. Springer (2021)
16.
Koch, A., Walzer, S.: Private function evaluation with cards. IACR Cryptology ePrint Archive 2018, 1113 (2018)
17.
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, May 30 to June 1, 2021, Favignana Island, Sicily, Italy, LIPIcs, vol. 157, pp. 17:1–17:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
18.
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.) Computer Science-Theory and Applications—16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28–July 2, 2021, Proceedings, Lecture Notes in Computer Science, vol. 12730, pp. 242–256. Springer (2021)
19.
Koyama, H., Toyoda, K., Miyahara, D., Mizuki, T.: New card-based copy protocols using only random cuts. In: Emura, K., Wang, Y. (eds.) Proceedings of the 8th on ASIA Public-Key Cryptography Workshop, APKC@AsiaCCS 2021, Virtual Event Hong Kong, 7 June, 2021, pp. 13–22. ACM (2021)
20.
Lafourcade, P., Miyahara, D., Mizuki, T., Robert, L., Sasaki, T., Sone, H.: How to construct physical zero-knowledge proofs for puzzles with a “single loop’’ condition. Theor. Comput. Sci. 888, 41–55 (2021)MathSciNetCrossRef
21.
22.
Marcedone, A., Wen, Z., Shi, E.: Secure dating with four or fewer cards. Cryptology ePrint Archive, Report 2015/1031 (2015)
23.
McKay, B., Piperno, A.: The nauty traces page
24.
Miyahara, D., Hayashi, Y., Mizuki, T., Sone, H.: Practical and easy-to-understand card-based implementation of yao’s millionaire protocol. In: Kim, D., Uma, R. N., Zelikovsky, A. (eds.) Combinatorial Optimization and Applications—12th International Conference, COCOA 2018, Atlanta, GA, USA, December 15–17, 2018, Proceedings, Lecture Notes in Computer Science, vol. 11346, pp. 246–261. Springer (2018)
25.
Miyahara, D., Hayashi, Y., Mizuki, T., Sone, H.: Practical card-based implementations of yao’s millionaire protocol. Theor. Comput. Sci. 803, 207–221 (2020)MathSciNetCrossRef
26.
Miyahara, D., Robert, L., Lafourcade, P., Takeshige, S., Mizuki, T., Shinagawa, K., Nagao, A., Sone, H.: 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 2021, May 30 to June 1, 2021, Favignana Island, Sicily, Italy, LIPIcs, vol. 157, pp. 20:1–20:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
27.
Mizuki, T.: Applications of card-based cryptography to education. IEICE Tech. Rep. 116(289), 13–17 (2016). ((In Japanese))
28.
Mizuki, T.: Card-based protocols for securely computing the conjunction of multiple variables. Theor. Comput. Sci. 622, 34–44 (2016)MathSciNetCrossRef
29.
Mizuki, T.: Efficient and secure multiparty computations using a standard deck of playing cards. In: Foresti, S., Persiano, G. (eds.) Cryptology and Network Security—15th International Conference, CANS 2016, Milan, Italy, November 14–16, 2016, Proceedings, Lecture Notes in Computer Science, vol. 10052, pp. 484–499 (2016)
30.
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.) Unconventional Computation and Natural Computation—12th International Conference, UCNC 2013, Milan, Italy, July 1–5, 2013. Proceedings, Lecture Notes in Computer Science, vol. 7956, pp. 162–173. Springer (2013)
31.
Mizuki, T., Kumamoto, M., Sone, H.: The five-card trick can be done with four cards. In: Wang, X., Sako, K. (eds.) Advances in Cryptology—ASIACRYPT 2012–18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2–6, 2012. Proceedings, Lecture Notes in Computer Science, vol. 7658, pp. 598–606. Springer (2012)
32.
Mizuki, T., Shizuya, H.: A formalization of card-based cryptographic protocols via abstract machine. Int. J. Inf. Sec. 13(1), 15–23 (2014)CrossRef
33.
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, Third International Workshop, FAW 2009, Hefei, China, June 20–23, 2009. Proceedings, Lecture Notes in Computer Science, vol. 5598, pp. 358–369. Springer (2009)
34.
Mizuki, T., Uchiike, F., Sone, H.: Securely computing XOR with 10 cards. Australas. J. Comb. 36, 279–293 (2006)MathSciNetMATH
35.
Murata, S., Miyahara, D., Mizuki, T., Sone, H.: Efficient generation of a card-based uniformly distributed random derangement. In: Uehara, R., Hong, S., Nandy, S. C. (eds.) WALCOM: Algorithms and Computation—15th International Conference and Workshops, WALCOM 2021, Yangon, Myanmar, February 28–March 2, 2021, Proceedings, Lecture Notes in Computer Science, vol. 12635, pp. 78–89. Springer (2021)
36.
Niemi, V., Renvall, A.: Secure multiparty computations without computers. Theor. Comput. Sci. 191(1–2), 173–183 (1998)MathSciNetCrossRef
37.
38.
Nishida, T., Hayashi, Y., Mizuki, T., Sone, H.: Card-based protocols for any boolean function. In: Jain, R., Jain, S., Stephan, F. (eds.) Theory and Applications of Models of Computation—12th Annual Conference, TAMC 2015, Singapore, May 18–20, 2015, Proceedings, Lecture Notes in Computer Science, vol. 9076, pp. 110–121. Springer (2015)
39.
Nishida, T., Hayashi, Y., Mizuki, T., Sone, H.: Securely computing three-input functions with eight cards. IEICE Trans. 98-A(6):1145–1152 (2015)
40.
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, M. A. (eds.) Theory and Practice of Natural Computing—Second International Conference, TPNC 2013, Cáceres, Spain, December 3–5, 2013, Proceedings, Lecture Notes in Computer Science, vol. 8273, pp. 193–204. Springer (2013)
41.
Robert, L., Miyahara, D., Lafourcade, P., Mizuki, T.: Physical zero-knowledge proof for suguru puzzle. In: Devismes, S., Mittal, N. (eds.) Stabilization, Safety, and Security of Distributed Systems—22nd International Symposium, SSS 2020, Austin, TX, USA, November 18–21, 2020, Proceedings, Lecture Notes in Computer Science, vol. 12514, pp. 235–247. Springer (2020)
42.
Robert, L., Miyahara, D., Lafourcade, P., Mizuki, T.: Interactive physical ZKP for connectivity: Applications to nurikabe and hitori. In: Mol, L. D., Weiermann, A., Manea, F., Fernández-Duque, D. (eds.) Connecting with Computability—17th Conference on Computability in Europe, CiE 2021, Virtual Event, Ghent, July 5–9, 2021, Proceedings, Lecture Notes in Computer Science, vol. 12813, pp. 373–384. Springer (2021)
43.
Ruangwises, S.: An improved physical ZKP for nonogram. In: Du, D., Du, D., Wu, C., Xu, D. (eds.) Combinatorial Optimization and Applications—15th International Conference, COCOA 2021, Tianjin, China, December 17–19, 2021, Proceedings, Lecture Notes in Computer Science, vol. 13135, pp. 262–272. Springer (2021)
44.
Ruangwises, S.: Two standard decks of playing cards are sufficient for a ZKP for sudoku. In: Chen, C., Hon, W., Hung, L., Lee, C. (eds.) Computing and Combinatorics—27th International Conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021, Proceedings, Lecture Notes in Computer Science, vol. 13025, pp. 631–642. Springer (2021)
45.
Ruangwises, S., Itoh, T.: Physical zero-knowledge proof for numberlink puzzle and k vertex-disjoint paths problem. New Gener. Comput. 39(1), 3–17 (2021)CrossRef
46.
Ruangwises, S., Itoh, T.: Physical zero-knowledge proof for ripple effect. Theor. Comput. Sci. 895, 115–123 (2021)MathSciNetCrossRef
47.
Ruangwises, S., Itoh, T.: Physical ZKP for connected spanning subgraph: Applications to bridges puzzle and other problems. In: Kostitsyna, I., Orponen, P. (eds.) Unconventional Computation and Natural Computation—19th International Conference, UCNC 2021, Espoo, Finland, October 18–22, 2021, Proceedings, Lecture Notes in Computer Science, vol. 12984, pp. 149–163. Springer (2021)
48.
Ruangwises, S., Itoh, T.: Securely computing the n-variable equality function with 2n cards. Theor. Comput. Sci. 887, 99–110 (2021)MathSciNetCrossRef
49.
Saito, T., Miyahara, D., Abe, Y., Mizuki, T., Shizuya, H.: How to implement a non-uniform or non-closed shuffle. In: Martín-Vide, C., Vega-Rodríguez, M. A., Yang, M. (eds.) Theory and Practice of Natural Computing—9th International Conference, TPNC 2020, Taoyuan, Taiwan, December 7–9, 2020, Proceedings, Lecture Notes in Computer Science, vol. 12494, pp. 107–118. Springer (2020)
50.
Sasaki, T., Miyahara, D., Mizuki, T., Sone, H.: Efficient card-based zero-knowledge proof for sudoku. Theor. Comput. Sci. 839, 135–142 (2020)MathSciNetCrossRef
51.
Sasaki, T., Mizuki, T., Sone, H.: Card-based zero-knowledge proof for sudoku. In: Ito, H., Leonardi, S., Pagli, L., Prencipe, G. (eds.) 9th International Conference on Fun with Algorithms, FUN 2018, June 13–15, 2018, La Maddalena, Italy, LIPIcs, vol. 100, pp. 29:1–29:10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
52.
Shinagawa, K., Mizuki, T.: The six-card trick: secure computation of three-input equality. In: Lee, K. (ed.) Information Security and Cryptology—ICISC 2018—21st International Conference, Seoul, South Korea, November 28–30, 2018, Revised Selected Papers, Lecture Notes in Computer Science, vol. 11396, pp. 123–131. Springer (2018)
53.
Shinagawa, K., Mizuki, T.: Secure computation of any boolean function based on any deck of cards. In: Chen, Y., Deng, X., Lu, M. (eds.) Frontiers in Algorithmics—13th International Workshop, FAW 2019, Sanya, China, April 29–May 3, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11458, pp. 63–75. Springer (2019)
54.
Shinagawa, K., Nuida, K.: A single shuffle is enough for secure card-based computation of any boolean circuit. Discrete Appl. Math. 289, 248–261 (2021)MathSciNetCrossRef
55.
Shinoda, Y., Miyahara, D., Shinagawa, K., Mizuki, T., Sone, H.: Card-based covert lottery. In: Maimut, D., Oprina, A., Sauveron, D. (eds.) Innovative Security Solutions for Information Technology and Communications—13th International Conference, SecITC 2020, Bucharest, Romania, November 19–20, 2020, Revised Selected Papers, Lecture Notes in Computer Science, vol. 12596, pp. 257–270. Springer (2020)
56.
57.
Takashima, K., Abe, Y., Sasaki, T., Miyahara, D., Shinagawa, K., Mizuki, T., Sone, H.: Card-based secure ranking computations. In: Li, Y., Cardei, M., Huang, Y. (eds.) Combinatorial Optimization and Applications—13th International Conference, COCOA 2019, Xiamen, China, December 13–15, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11949, pp. 461–472. Springer (2019)
58.
Takashima, K., Abe, Y., Sasaki, T., Miyahara, D., Shinagawa, K., Mizuki, T., Sone, H.: Card-based protocols for secure ranking computations. Theor. Comput. Sci. 845, 122–135 (2020)MathSciNetCrossRef
59.
Takashima, K., Miyahara, D., Mizuki, T., Sone, H.: Card-based protocol against actively revealing card attack. In: Martín-Vide, C., Pond, G. T., Vega-Rodríguez, M. A. (eds.) Theory and Practice of Natural Computing—8th International Conference, TPNC 2019, Kingston, ON, Canada, December 9–11, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11934, pp. 95–106. Springer (2019)
60.
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.) Progress in Cryptology—INDOCRYPT 2021—22nd International Conference on Cryptology in India, Jaipur, India, December 12–15, 2021, Proceedings, Lecture Notes in Computer Science, vol. 13143, pp. 536–555. Springer (2021)
61.
Toyoda, K., Miyahara, D., Mizuki, T., Sone, H.: Six-card finite-runtime XOR protocol with only random cut. In: Emura, K., Yanai, N. (eds.) Proceedings of the 7th on ASIA Public-Key Cryptography Workshop, APKC@AsiaCCS 2020, Taipei, Taiwan, October 6, 2020, pp. 2–8. ACM (2020)
62.
Yao, A. C.: Protocols for secure computations (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3–5 November 1982, pp. 160–164. IEEE Computer Society (1982)
63.
Yao, A. C.: How to generate and exchange secrets (extended abstract). In: 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27–29 October 1986, pp. 162–167. IEEE Computer Society (1986)
Metadata
Title
Graph Automorphism Shuffles from Pile-Scramble Shuffles
Authors
Kengo Miyamoto
Kazumasa Shinagawa
Publication date
02-04-2022
Publisher
Ohmsha
Published in
New Generation Computing / Issue 1/2022
Print ISSN: 0288-3635
Electronic ISSN: 1882-7055
DOI
https://doi.org/10.1007/s00354-022-00164-4

Other articles of this Issue 1/2022

New Generation Computing 1/2022 Go to the issue

EditorialNotes

Preface: Special Issue on Card-Based Cryptography 2

OriginalPaper

Private Function Evaluation with Cards

OriginalPaper

Secure Computation for Threshold Functions with Physical Cards: Power of Private Permutations

OriginalPaper

Discovery of Botnet Activities in Internet-of-Things System Using Dynamic Evolutionary Mechanism

EditorialNotes

Selected Papers from the 35th JSAI Annual Meeting

OriginalPaper

Uncertainty Analysis in Ontology-Based Knowledge Representation

Premium Partner

    Image Credits