Private Function Evaluation with Cards

Card-based protocols allow to evaluate an arbitrary fixed Boolean function 𝑓 on a hidden input to obtain a hidden output, without the executer learning anything about either of the two (e.g., [12]). We explore the case where 𝑓 implements a universal function, i.e., 𝑓 is given the encoding ⟨𝑃⟩ of a program 𝑃 and an input 𝑥 and computes 𝑓(⟨𝑃⟩,𝑥)=𝑃(𝑥). More concretely, we consider universal circuits, Turing machines, RAM machines, and branching programs, giving secure and conceptually simple card-based protocols in each case. We argue that card-based cryptography can be performed in a setting that is only very weakly interactive, which we call the “surveillance” model. Here, when Alice executes a protocol on the cards, the only task of Bob is to watch that Alice does not illegitimately turn over cards and that she shuffles in a way that nobody knows anything about the total permutation applied to the cards. We believe that because of this very limited interaction, our results can be called program obfuscation. As a tool, we develop a useful sub-protocol 𝗌𝗈𝗋𝗍$_{II}$𝑋↑𝑌 that couples the two equal-length sequences 𝑋,𝑌 and jointly and obliviously permutes them with the permutation 𝜋∈𝛱 that lexicographically minimizes 𝜋(𝑋). ... mehrWe argue that this generalizes ideas present in many existing card-based protocols. In fact, AND, XOR, bit copy [37], coupled rotation shuffles [30] and the “permutation division” protocol of [22] can all be expressed as “coupled sort protocols”.