2021/09/01 by Miyamoto, Kengo, Shinagawa, Kazumasa
#05C20 #94A60 #Combinatorics (math.CO) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2109.00397
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 ≤ k ≤ 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.