**On The Orthogonal Vector Problem and The Feasibility of Unconditionally Secure Leakage Resilient Computation**

*Ivan Damgård and Frédéric Dupuis and 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.

**Category / Keywords: **cryptographic protocols / Quantum, Leakage-Resilience

**Date: **received 23 Apr 2014

**Contact author: **jbn at cs au dk

**Available format(s): **PDF | BibTeX Citation

**Version: **20140424:223432 (All versions of this report)

**Short URL: **ia.cr/2014/282

[ Cryptology ePrint archive ]