Cryptology ePrint Archive: Report 2018/358

Efficient Erasable PUFs from Programmable Logic and Memristors

Yansong Gao and Chenglu Jin and Jeeson Kim and Hussein Nili and Xiaolin Xu and Wayne Burleson and Omid Kavehei and Marten van Dijk and Damith C. Ranasinghe and Ulrich Rührmair

Abstract: At Oakland 2013, R{\"u}hrmair and van Dijk showed that many advanced PUF (Physical Unclonable Function)-based security protocols (e.g. key agreement, oblivious transfer, and bit commitment) can be vulnerable if adversaries get access to the PUF and reuse the responses used in the protocol after the protocol execution. This observation implies the necessity of erasable PUFs for realizing secure PUF-based protocols in practice. Erasable PUFs are PUFs where the responses of any single challenge-response pair (CRP) can be selectively and dedicatedly erased, without affecting any other responses.

In this paper, we introduce two practical implementations of erasable PUFs: Firstly, we propose a full-fledged logical version of an erasable PUF, called programmable logically erasable PUF or PLayPUF, where an additional constant-size trusted computing base keeps track of the usage of every single CRP. Knowing the query history of each CRP, a PLayPUF interface can \textit{automatically} erase an individual CRP, if it has been used for a certain number of times. This threshold can be programmed a-priori to limit the usage of a given challenge in the future before erasure.

Secondly, we introduce two nanotechnological, memristor-based solutions: mrSHIC-PUFs and erasable mrSPUFs. The mrSHIC-PUF is a weak PUF in terms of the size of CRP space, and therefore its readout speed has to be limited intentionally to prolong the time for exhaustive reading. However, each individual response can be {\it physically} altered and erased for good. The erasable mrSPUF, as the second proposed physical erasable PUF, is a strong PUF in terms of the size of CRP space, such that no limit on readout speed is needed, but it can only erase/alter CRPs in groups. Both of these two physical erasable PUFs improve over the state-of-the-art erasable SHIC PUF, which does not offer reconfigurability of erased CRPs making the erasable SHIC PUF less practical.

In passing, we contextualize and locate our new PUF type in the existing landscape, illustrating their essential advantages over variants like reconfigurable PUFs.

Category / Keywords: implementation / Physical Unclonable Functions, PUF Re-use Model, Memristor, Erasable PUFs, Reconfigurable PUFs, PLayPUFs, mrSHIC-PUFs, mrSPUFs

Date: received 16 Apr 2018

Contact author: chenglu jin at uconn edu

Available format(s): PDF | BibTeX Citation

Version: 20180418:203429 (All versions of this report)

Short URL: ia.cr/2018/358


[ Cryptology ePrint archive ]