Koch, Alexander ORCID: 0000-0002-3510-9669 and Walzer, Stefan ORCID: 0000-0002-6477-0106 (2022). Private Function Evaluation with Cards. New Gener. Comput., 40 (1). S. 115 - 148. NEW YORK: SPRINGER. ISSN 1882-7055
Full text not available from this repository.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., [12]). We explore the case where f implements a universal function, i.e., f is given the encoding (P) of a program P and an input x and computes f(< P >,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 sort(Pi)-X up arrow Y that couples the two equal-length sequences X, Y and jointly and obliviously permutes them with the permutation pi is an element of 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 [37], coupled rotation shuffles [30] and the permutation division protocol of [22] can all be expressed as coupled sort protocols.
Item Type: | Journal Article | ||||||||||||
Creators: |
|
||||||||||||
URN: | urn:nbn:de:hbz:38-670863 | ||||||||||||
DOI: | 10.1007/s00354-021-00149-9 | ||||||||||||
Journal or Publication Title: | New Gener. Comput. | ||||||||||||
Volume: | 40 | ||||||||||||
Number: | 1 | ||||||||||||
Page Range: | S. 115 - 148 | ||||||||||||
Date: | 2022 | ||||||||||||
Publisher: | SPRINGER | ||||||||||||
Place of Publication: | NEW YORK | ||||||||||||
ISSN: | 1882-7055 | ||||||||||||
Language: | English | ||||||||||||
Faculty: | Unspecified | ||||||||||||
Divisions: | Unspecified | ||||||||||||
Subjects: | no entry | ||||||||||||
Uncontrolled Keywords: |
|
||||||||||||
URI: | http://kups.ub.uni-koeln.de/id/eprint/67086 |
Downloads
Downloads per month over past year
Altmetric
Export
Actions (login required)
View Item |