Title: Secure Grouping Protocol Using a Deck of Cards,
Abstract: We consider a problem, which we call secure grouping, of dividing a number of
parties into some subsets (groups) in the following manner: Each party has to
know the other members of his/her group, while he/she may not know anything
about how the remaining parties are divided (except for certain public
predetermined constraints, such as the number of parties in each group). In
this paper, we construct an information-theoretically secure protocol using a
deck of physical cards to solve the problem, which is jointly executable by the
parties themselves without a trusted third party. Despite the non-triviality
and the potential usefulness of the secure grouping, our proposed protocol is
fairly simple to describe and execute. Our protocol is based on algebraic
properties of conjugate permutations. A key ingredient of our protocol is our
new techniques to apply multiplication and inverse operations to hidden
permutations (i.e., those encoded by using face-down cards), which would be of
independent interest and would have various potential applications.