2020/10/16 by Dvořák, Pavel, Koucký, Michal
#Computational Complexity (cs.CC) #F.1.1 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2010.08445
In this paper we study the computational complexity of functions that have efficient card-based protocols. Card-based protocols were proposed by den Boer [EUROCRYPT '89] as a means for secure two-party computation. Our contribution is two-fold: We classify a large class of protocols with respect to the computational complexity of functions they compute, and we propose other encodings of inputs which require fewer cards than the usual 2-card representation.