Welcome to the resource topic for 2018/1113
Title:
Private Function Evaluation with Cards
Authors: Alexander Koch, Stefan Walzer
Abstract:Card-based protocols allow to evaluate an arbitrary fixed Boolean function f on a hidden input to obtain a hidden output, without the executer learning anything about either of the two (e.g. Crépeau and Kilian, CRYPTO 1993). We explore the case where f implements a universal function, i.e. f is given the encoding \langle P\rangle of a program P and an input x and computes f(\langle P\rangle, x) = P(x). 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 \mathsf{sort}_{\Pi}X\mathop{\uparrow}Y that couples the two equal-length sequences X, Y and jointly and obliviously permutes them with the permutation \pi\in\Pi that lexicographically minimizes \pi(X). We argue that this generalizes ideas present in many existing card-based protocols. In fact, AND, XOR, bit copy (Mizuki and Sone, FAW 2009), coupled rotation shuffles (Koch and Walzer, ePrint 2017) and the “permutation division” protocol of (Hashimoto et al., ICITS 2017) can all be expressed as “coupled sort protocols”.
ePrint: https://eprint.iacr.org/2018/1113
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .