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 .