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.
Kazumasa SHINAGAWA
Ibaraki University,National Institute of Advanced Industrial Science and Technology (AIST)
Kengo MIYAMOTO
Ibaraki University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Kazumasa SHINAGAWA, Kengo MIYAMOTO, "Automorphism Shuffles for Graphs and Hypergraphs and Its Applications" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 3, pp. 306-314, March 2023, doi: 10.1587/transfun.2022CIP0020.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022CIP0020/_p
Copy
@ARTICLE{e106-a_3_306,
author={Kazumasa SHINAGAWA, Kengo MIYAMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Automorphism Shuffles for Graphs and Hypergraphs and Its Applications},
year={2023},
volume={E106-A},
number={3},
pages={306-314},
abstract={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.},
keywords={},
doi={10.1587/transfun.2022CIP0020},
ISSN={1745-1337},
month={March},}
Copy
TY - JOUR
TI - Automorphism Shuffles for Graphs and Hypergraphs and Its Applications
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 306
EP - 314
AU - Kazumasa SHINAGAWA
AU - Kengo MIYAMOTO
PY - 2023
DO - 10.1587/transfun.2022CIP0020
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E106-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2023
AB - 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.
ER -