Cryptology ePrint Archive: Report 2016/636

Unconditional UC-Secure Computation with (Stronger-Malicious) PUFs

Saikrishna Badrinarayanan and Dakshita Khurana and Rafail Ostrovsky and Ivan Visconti

Abstract: Brzuska \etal. (Crypto 2011) proved that unconditional UC-secure computation is possible if parties have access to honestly generated physically unclonable functions (PUFs). Dachman-Soled \etal. (Crypto 2014) then showed how to obtain unconditional UC secure computation based on malicious PUFs, assuming such PUFs are stateless. They also showed that unconditional oblivious transfer is impossible against an adversary that creates malicious stateful PUFs. \begin​{itemize} \item In this work, we go beyond this seemingly tight result, by allowing any adversary to create stateful PUFs with a-priori bounded state. This relaxes the restriction on the power of the adversary (limited to stateless PUFs in previous feasibility results), therefore achieving improved security guarantees. This is also motivated by practical scenarios, where the size of a physical object may be used to compute an upper bound on the size of its memory. \item As a second contribution, we introduce a new model where any adversary is allowed to generate a malicious PUF that may encapsulate other (honestly generated) PUFs within it, such that the outer PUF has oracle access to all the inner PUFs. This is again a natural scenario, and in fact, similar adversaries have been studied in the tamper-proof hardware-token model (\eg, Chandran \etal. (Eurocrypt 2008)), but no such notion has ever been considered with respect to PUFs. All previous constructions of UC secure protocols suffer from explicit attacks in this stronger model. \end{itemize}

In a direct improvement over previous results, we construct {\em UC protocols with unconditional security} in both these models.

Category / Keywords: cryptographic protocols / Physically uncloneable functions, UC security, hardware setup assumptions

Original Publication (with major differences): IACR-EUROCRYPT-2017

Date: received 19 Jun 2016, last revised 22 Feb 2017

Contact author: saikrishna at cs ucla edu, dakshita@cs ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20170222:072431 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]