Welcome to the resource topic for 2014/282
Title:
On The Orthogonal Vector Problem and The Feasibility of Unconditionally Secure Leakage Resilient Computation
Authors: Ivan Damgård, Frédéric Dupuis, Jesper Buus Nielsen
Abstract:We consider unconditionally secure leakage resilient two-party computation, where security means that the leakage obtained by an adversary can be simulated using a similar amount of leakage from the private inputs or outputs. A related problem is known as circuit compilation, where there is only one device doing a computation on public input and output. Here the goal is to ensure that the adversary learns only the input/output behaviour of the computation, even given leakage from the internal state of the device. We study these problems in an enhanced version of the only computation leaks'' model, where the adversary is additionally allowed a bounded amount of {\em global} leakage from the state of the entity under attack. In this model, we show the first unconditionally secure leakage resilient two-party computation protocol. The protocol assumes access to correlated randomness in the form of a functionality $\fOrt$ that outputs pairs of orthogonal vectors $(\vec{u}, \vec{v})$ over some finite field, where the adversary can leak independently from $\vec{u}$ and from $\vec{v}$. We also construct a general circuit compiler secure in the same leakage model. Our constructions work, even if the adversary is allowed to corrupt a constant fraction of the calls to $\fOrt$ and decide which vectors should be output. On the negative side, we show that unconditionally secure two-party computation and circuit compilation are in general impossible in the plain version of our model. For circuit compilation we need a computational assumption to exhibit a function that cannot be securely computed, on the other hand impossibility holds even if global leakage is not allowed. It follows that even a somewhat unreliable version of $\fOrt$ cannot be implemented with unconditional security in the plain leakage model, using classical communication. However, we show that an implementation using quantum communication does exist. In particular, we propose a simple prepare-and-measure’’ type protocol which we show secure using a new result on sampling from a quantum population. Although the protocol may produce a small number of incorrect pairs, this is sufficient for leakage resilient computation by our other results.
ePrint: https://eprint.iacr.org/2014/282
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 .