Graph Automorphism Shuffles from Pile-Scramble Shuffles

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

arXiv comment16 pages. We have corrected some typos and added Subsections 1.3, 3.6, Section 5, and proofs of correctness and security of protocols in Subsections 4.1. 4.2