Cryptology ePrint Archive: Report 2014/282

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:

[ Cryptology ePrint archive ]