Efficient Card-Based Protocols for Generating a Hidden Random Permutation Without Fixed Points

摘要

Consider the holiday season, where there are n players who would like to exchange gifts. That is, we would like to generate a random permutation having no fixed point. It is known that such a random permutation can be obtained in a hidden form by using a number of physical cards of four colors with identical backs, guaranteeing that it has no fixed point (without revealing the permutation itself). This paper deals with such a problem and improves the known result: whereas the known protocol needs O(n~2) cards of four colors, our efficient protocol uses only O(n log n) cards of two colors.