Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2109.00397 · New Generation Computing

Graph Automorphism Shuffles from Pile-Scramble Shuffles

Kengo Miyamoto, Kazumasa Shinagawa

Published Apr 1, 2022• 12 citations
arXivHTMLPDF
DOI
10.1007/s00354-022-00164-4

Related papers

Automorphism Shuffles for Graphs and Hypergraphs and Its Applications

Kazumasa Shinagawa, Kengo Miyamoto

In card-based cryptography, a deck of physical cards is used to achieve secure computation. A shuffle, which randomly permutes a card-sequence along with some probability distribution, ensures the security of a card-based protocol. The authors proposed a new class of shuffles called graph shuffles, which randomly permutes a card-sequence by an automorphism of a directed graph (New Generation Computing 2022). For a directed graph G with n vertices and m edges, such a shuffle could be implemented with pile-scramble shuffles with 2(n + m) cards. In this paper, we study graph shuffles and give an implementation, an application, and a slight generalization. First, we propose a new protocol for graph shuffles with 2n + m cards. Second, as a new application of graph shuffles, we show that any cyclic group shuffle, which is a shuffle over a cyclic group, is a graph shuffle associated with some graph. Third, we define a hypergraph shuffle, which is a shuffle by an automorphism of a hypergraph, and show that any hypergraph shuffle can also be implemented with pile-scramble shuffles.

arXiv:2205.04774•IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Sep 11, 2022•2 citations

Quantum Random Walks and the Graph Isomorphism Problem

Kenneth Rudinger, John King Gamble, M. Wellons +4 more

Bulletin of the American Physical Society•Feb 29, 2012•0 citations

Lattice-Based Proof of a Shuffle

Núria Costa, Ramiro Pinilla, Paz Morillo

Lecture notes in computer science•Jan 1, 2020•16 citations

Batching Techniques Using Generalized Pile-Scramble Shuffles and Branching Shuffles

Yuto ISHIZAKI, Kazumasa Shinagawa, Koji Nuida

Card-based cryptography is a research field for realizing secure computation using physical cards. In card-based protocols, the efficiency of a protocol is mainly measured by the number of cards and the number of shuffles. Shinagawa and Nuida proposed a batching technique, which is a technique for reducing the number of pile-scramble shuffles (PSS) by combining multiple PSSs into a single PSS. In this paper, we propose three new methods for the batching technique. The first method uses a new shuffle called a generalized PSS; unlike a PSS, this allows the number of cards in each pile to be uneven. The second method uses a shuffle called a branching PSS, which is a PSS for a sequence including face-up cards. The third method uses a shuffle called a branching generalized PSS, which is a generalized PSS for a sequence including face-up cards. Our methods are efficient in terms of the number of cards and shuffles compared to the existing batching technique. As applications, we use our methods to reduce the number of shuffles for AND protocols and XOR protocols.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Mar 31, 2026•0 citations

Towards the fast scrambling conjecture

Nima Lashkari, Douglas Stanford, Matthew B. Hastings +2 more

arXiv:1111.6580•Journal of High Energy Physics•Apr 1, 2013•433 citations

Pile-Shifting Scramble for Card-Based Protocols

Akihiro Nishimura, Yu‐ichi Hayashi, Takaaki Mizuki +1 more

Card-based cryptographic protocols provide secure multi-party computations using a deck of physical cards. The most important primitive of those protocols is the shuffling operation, and most of the existing protocols rely on uniform cyclic shuffles (such as the random cut and random bisection cut) in which each possible outcome is equally likely and all possible outcomes constitute a cyclic subgroup. However, a couple of protocols with non-uniform and/or non-cyclic shuffles were proposed by Koch, Walzer, and Härtel at Asiacrypt 2015. Compared to the previous protocols, their protocols require fewer cards to securely produce a hidden AND value, although to implement of such unconventional shuffles appearing in their protocols remains an open problem. This paper introduces “pile-shifting scramble,” which can be a secure implementation of those shuffles. To implement such unconventional shuffles, we utilize physical cases that can store piles of cards, such as boxes and envelopes. Therefore, humans are able to perform the shuffles using these everyday objects. Furthermore, we show that a certain class of non-uniform and/or non-cyclic shuffles having two possible outcomes can be implemented by the pile-shifting scramble. This also implies that we can improve upon the known COPY protocol using three card cases so that the number of cases required can be reduced to two.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Aug 31, 2018•36 citations
In card-based cryptography, a deck of physical cards is used to achieve secure computation. A shuffle, which randomly permutes a card-sequence along with some probability distribution, ensures the security of a card-based protocol. The authors proposed a new class of shuffles called graph shuffles, which randomly permutes a card-sequence by an automorphism of a directed graph (New Generation Computing 2022). For a directed graph G with n vertices and m edges, such a shuffle could be implemented with pile-scramble shuffles with 2(n + m) cards. In this paper, we study graph shuffles and give an implementation, an application, and a slight generalization. First, we propose a new protocol for graph shuffles with 2n + m cards. Second, as a new application of graph shuffles, we show that any cyclic group shuffle, which is a shuffle over a cyclic group, is a graph shuffle associated with some graph. Third, we define a hypergraph shuffle, which is a shuffle by an automorphism of a hypergraph, and show that any hypergraph shuffle can also be implemented with pile-scramble shuffles.
Card-based cryptography is a research field for realizing secure computation using physical cards. In card-based protocols, the efficiency of a protocol is mainly measured by the number of cards and the number of shuffles. Shinagawa and Nuida proposed a batching technique, which is a technique for reducing the number of pile-scramble shuffles (PSS) by combining multiple PSSs into a single PSS. In this paper, we propose three new methods for the batching technique. The first method uses a new shuffle called a generalized PSS; unlike a PSS, this allows the number of cards in each pile to be uneven. The second method uses a shuffle called a branching PSS, which is a PSS for a sequence including face-up cards. The third method uses a shuffle called a branching generalized PSS, which is a generalized PSS for a sequence including face-up cards. Our methods are efficient in terms of the number of cards and shuffles compared to the existing batching technique. As applications, we use our methods to reduce the number of shuffles for AND protocols and XOR protocols.
Card-based cryptographic protocols provide secure multi-party computations using a deck of physical cards. The most important primitive of those protocols is the shuffling operation, and most of the existing protocols rely on uniform cyclic shuffles (such as the random cut and random bisection cut) in which each possible outcome is equally likely and all possible outcomes constitute a cyclic subgroup. However, a couple of protocols with non-uniform and/or non-cyclic shuffles were proposed by Koch, Walzer, and Härtel at Asiacrypt 2015. Compared to the previous protocols, their protocols require fewer cards to securely produce a hidden AND value, although to implement of such unconventional shuffles appearing in their protocols remains an open problem. This paper introduces “pile-shifting scramble,” which can be a secure implementation of those shuffles. To implement such unconventional shuffles, we utilize physical cases that can store piles of cards, such as boxes and envelopes. Therefore, humans are able to perform the shuffles using these everyday objects. Furthermore, we show that a certain class of non-uniform and/or non-cyclic shuffles having two possible outcomes can be implemented by the pile-shifting scramble. This also implies that we can improve upon the known COPY protocol using three card cases so that the number of cases required can be reduced to two.