Graph Automorphism Shuffles from Pile-Scramble Shuffles

MaRDI QIDQ6376566zbMATH OpenFDO

Authors Kengo Miyamoto, Kazumasa Shinagawa

Publication date 1 September 2021

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Cryptography (94A60)

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 article 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 by 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 $1leqkleqn$ 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 realized by $3n$ cards and two pile-scramble shuffles.

This page was built for publication: Graph Automorphism Shuffles from Pile-Scramble Shuffles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6376566)