*00:17*[Pub][ePrint] On The Orthogonal Vector Problem and The Feasibility of Unconditionally Secure Leakage Resilient Computation, by Ivan Damgård and Frédéric Dupuis and Jesper Buus Nielsen

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.