AND Protocols Using Only Uniform Shuffles
This work addresses a specific challenge in card-based cryptography for secure computation, but it is incremental as it builds on existing research with minor improvements in shuffle restrictions.
The paper tackles the problem of designing secure multi-party computation protocols for Boolean AND operations using playing cards, introducing two protocols that use only uniform shuffles: one with four cards and finite expected runtime, and another with five cards that always terminates in finite time.
Secure multi-party computation using a deck of playing cards has been a subject of research since the "five-card trick" introduced by den Boer in 1989. One of the main problems in card-based cryptography is to design committed-format protocols to compute a Boolean AND operation subject to different runtime and shuffle restrictions by using as few cards as possible. In this paper, we introduce two AND protocols that use only uniform shuffles. The first one requires four cards and is a restart-free Las Vegas protocol with finite expected runtime. The second one requires five cards and always terminates in finite time.