We investigate the power of physical unclonable functions (PUFs) as a new primitive in cryptographic protocols. Our contributions split into three parts. Firstly, we focus on the realiza bility of PUF-protocols in a special type of stand-alone setting (the “stand-alone, good PUF setting”) under minimal assumptions. We provide new PUF definitions that require only weak average security properties of the PUF, and prove that these definitions suffice to realize secure PUF-based oblivious transfer (OT), bit com mitment (BC) and key exchange (KE) in said setting. Our protocols for OT, BC and KE are partly new, and have certain practicality and security advantages compared to existing schemes. In the second part of the paper, we formally prove that there are very sharp limits on the usability of PUFs for OT and KE beyond the above stand-alone, good PUF scenario. We introduce two new and realistic attack models, the so-called posterior access model (PAM) and the bad PUF model, and prove several impossibility results in these models. First, OT and KE protocols whose security is solely based on PUFs are generally impossible in the PAM. More precisely, one-time access of an adversary to the PUF after the end of a single protocol (sub-)session makes all previous (sub-)sessions provably insecure. Second, OT whose security is solely based on PUFs is impossible in the bad PUF model, even if only a stand alone execution of the protocol is considered (i.e., even if no adversarial PUF access after the protocol is allowed). Our impossibility proofs do not only hold for the weak PUF definition of the first part of the paper, but even apply if ideal rand omness and unpredictability is assumed in the PUF, i.e., if the PUF is modeled as a random permutation oracle. In the third part, we investigate the feasibility of PUF-based bit commitment beyond the stand-alone, good PUF setting. For a number of reasons, this case is more complicated than OT and KE. We first prove that BC is impossible in the bad PUF model if players have got access to the PUF between the commit and the reveal phase. Again, this result holds even if the PUF is “ideal” and modeled as a random permutation oracle. Secondly, we sketch (without proof) two new BC-protocols, which can deal with bad PUFs or with adversarial access between the commit and reveal phase, but not with both. We hope that our results can contribute to a clarification of the usability of PUF s in cryptographic protocols. They show that new hardware properties such as offline certifiability and the erasure of PUF responses would be required in order to make PUFs a broadly applicable cryptographic tool. These features have not yet been realized in practical PUF-implementations and generally seem hard to achieve at low costs. Our findings also show that the question how PUFs can be modeled comprehensively in a UC-setting must be considered at least partly open.
We investigate the power of physical unclonable functions (PUFs) as a new primitive in cryptographic protocols. Our contributions split into three parts. Firstly, we focus on the realiza bility of PUF-protocols in a special type of stand-alone setting (the “stand-alone, good PUF setting”) under minimal assumptions. We provide new PUF definitions that require only weak average security properties of the PUF, and prove that these definitions suffice to realize secure PUF-based oblivious transfer (OT), bit com mitment (BC) and key exchange (KE) in said setting. Our protocols for OT, BC and KE are partly new, and have certain practicality and security advantages compared to existing schemes. In the second part of the paper, we formally prove that there are very sharp limits on the usability of PUFs for OT and KE beyond the above stand-alone, good PUF scenario. We introduce two new and realistic attack models, the so-called posterior access model (PAM) and the bad PUF model, and prove several impossibility results in these models. First, OT and KE protocols whose security is solely based on PUFs are generally impossible in the PAM. More precisely, one-time access of an adversary to the PUF after the end of a single protocol (sub-)session makes all previous (sub-)sessions provably insecure. Second, OT whose security is solely based on PUFs is impossible in the bad PUF model, even if only a stand alone execution of the protocol is considered (i.e., even if no adversarial PUF access after the protocol is allowed). Our impossibility proofs do not only hold for the weak PUF definition of the first part of the paper, but even apply if ideal rand omness and unpredictability is assumed in the PUF, i.e., if the PUF is modeled as a random permutation oracle. In the third part, we investigate the feasibility of PUF-based bit commitment beyond the stand-alone, good PUF setting. For a number of reasons, this case is more complicated than OT and KE. We first prove that BC is impossible in the bad PUF model if players have got access to the PUF between the commit and the reveal phase. Again, this result holds even if the PUF is “ideal” and modeled as a random permutation oracle. Secondly, we sketch (without proof) two new BC-protocols, which can deal with bad PUFs or with adversarial access between the commit and reveal phase, but not with both. We hope that our results can contribute to a clarification of the usability of PUF s in cryptographic protocols. They show that new hardware properties such as offline certifiability and the erasure of PUF responses would be required in order to make PUFs a broadly applicable cryptographic tool. These features have not yet been realized in practical PUF-implementations and generally seem hard to achieve at low costs. Our findings also show that the question how PUFs can be modeled comprehensively in a UC-setting must be considered at least partly open.
In recent years, PUF-based schemes have not only been suggested for the basic security tasks of tamper sensitive key storage or system identification, but also for more complex cryptographic protocols like oblivious transfer (OT), bit commitment (BC), or key exchange (KE). In these works, so-called "Strong PUFs" are regarded as a new, fundamental cryptographic primitive of their own, comparable to the bounded storage model, quantum cryptography, or noisebased cryptography. This paper continues this line of research, investigating the correct adversarial attack model and the actual security of such protocols. In its first part, we define and compare different attack models. They reach from a clean, first setting termed the "stand-alone, good PUF model" to stronger scenarios like the "bad PUF model" and the "PUF re-use model". We argue why these attack models are realistic, and that existing protocols would be faced with them if used in practice. In the second part, we execute exemplary security analyses of existing schemes in the new attack models. The evaluated protocols include recent schemes from Brzuska et al. published at Crypto 2011 [1] and from Ostrovsky et al. [18]. While a number of protocols are certainly secure in their own, original attack models, the security of none of the considered protocols for OT, BC, or KE is maintained in all of the new, realistic scenarios. One consequence of our work is that the design of advanced cryptographic PUF protocols needs to be strongly reconsidered. Furthermore, it suggests that Strong PUFs require additional hardware properties in order to be broadly usable in such protocols: Firstly, they should ideally be "erasable", meaning that single PUF-responses can be erased without affecting other responses. If the area efficient implementation of this feature turns out to be difficult, new forms of Controlled PUFs [8] (such as Logically Erasable and Logically Reconfigurable PUFs [13]) may suffice in certain applications. Secondly, PUFs should be "certifiable", meaning that one can verify that the PUF has been produced faithfully and has not been manipulated in any way afterwards. The combined implementation of these features represents a pressing and challenging problem, which we pose to the PUF hardware community in this work.
Physically Uncloneable Functions (PUFs) [Pap01] are noisy physical sources of randomness. As such, they are naturally appealing for cryptographic applications, and have caught the interest of both theoreticians and practitioners. A major step towards understanding and securely using PUFs was recently taken in [Crypto 2011] where Brzuska, Fischlin, Schroder and Katzenbeisser model PUFs in the Universal Composition (UC) framework of Canetti [FOCS 2001]. Their model considers trusted PUFs only, and thus real-world adversaries can not create malicious PUFs, and can access the physical object only via the prescribed procedure. However, this does not accurately reflect real-life scenarios, where an adversary could be able to create and use malicious PUFs, or access the PUF through other procedures. The goal of this work is to extend the model proposed in [Crypto 2011] in order to capture such real-world attacks. The main contribution of this work is the study of the Malicious PUFs model. Namely, we extend the PUF functionality of Brzuska et al. so that it allows the adversary to create arbitrarily malicious PUFs. Then, we provide positive results in this, more realistic, model. We show that, under computational assumptions, it is possible to UC-securely realize any functionality. Furthermore, we achieve unconditional (not UC) security with malicious PUFs, by showing a statistically hiding statistically binding commitment scheme that uses one PUF only, and such PUF can be malicious. As an additional contribution, we investigate another attack model, where adversaries access to a trusted PUF in a different way (i.e., not following the prescribed procedure). Technically this attack translates into the fact that the simulator cannot observe the queries made to an honest PUF. In this model, queries are oblivious to the simulator, and we call it the “Oblivious Query” model. We are able to achieve unconditionally UC-secure computation, even in this more severe model. This protocol is secure against stronger adversaries compared to the ones of Brzuska et al. Finally, we show the impossibility of UC secure computation in the combination of the above two new models, where the real-world adversary can create malicious PUFs and maliciously access to honest PUFs. Our work sheds light on the significant power and applicability of PUFs in the design of cryptographic protocols modeling adversaries that misbehave with PUFs.
Commitment schemes are one of the basic building blocks to construct secure protocols for multi party computation. Many recent works are exploring hardware primitives like physically unclonable functions to build keyless cryptographic protocols, with minimal assumptions. The asymmetric nature and non-invertibility property of PUFs are widely exploited to build oblivious transfer protocols that are extended to build bit-commitment schemes. However, these schemes require the physical transfer of the PUF device between the interacting parties. In this work, we introduce a new class of hardware-based primitives called physically related functions that enable hardware circuits to securely communicate with each other over insecure channels. We propose a bit-commitment protocol based on this hardware primitive without needing any physical transfer. Our scheme is statistically hiding and computationally binding, requiring only one round of communication while being practically deployable. We explore the security properties of physically related functions, under which we prove the security of our scheme. We experimentally show that it is impossible to break the security of the scheme with more than negligible probability.
We continue investigations on the use of so-called Strong PUFs as a cryptographic primitive in realistic attack models, in particular in the “Bad/Malicious PUF Model”. We obtain the following results: – Bad PUFs and Simplification: As a minor contribution, we simplify a recent OT-protocol for malicious PUFs by Dachman-Soled et al. [4] from CRYPTO 2014. We can achieve the same security properties under the same assumptions, but use only one PUF instead of two. – PUFs-inside-PUFs, Part I: We propose the new, realistic adversarial models of PUF modifications and PUFs-inside-PUF attacks, and show that the earlier protocol of Dachman-Soled et al. [4] is vulnerable against PUFs-inside-PUFs attacks (which lie outside the original framework of [4]). – PUFs-inside-PUFs, Part II: We construct a new PUF-based OT-protocol, which is secure against PUFs-inside-PUFs attacks if the used bad PUFs are stateless. Our protocol introduces the technique of interleaved challenges. – PUFs-inside-PUFs, Part III: In this context, we illustrate why the use of interactive hashing in our new protocol appears necessary, and why a first protocol attempt without interactive hashing fails.
This thesis proposes several protocols for achieving secure com- putation under concurrent and physical attacks. Secure computation allows many parties to compute a joint function of their inputs, while keeping the privacy of their input preserved. It is required that the pri- vacy one party's input is preserved even if other parties participating in the protocol collude or deviate from the protocol. In this thesis we focus on concurrent and physical attacks, where adversarial parties try to break the privacy of honest parties by ex- ploiting the network connection or physical weaknesses of the honest parties' machine. In the rst part of the thesis we discuss how to construct proto- cols that are Universally Composable (UC for short) based on physical setup assumptions. We explore the use of Physically Uncloneable Func- tions (PUFs) as setup assumption for achieving UC-secure computa- tions. PUF are physical noisy source of randomness. The use of PUFs in the UC-framework has been proposed already in [14]. However, this work assumes that all PUFs in the system are trusted. This means that, each party has to trust the PUFs generated by the other parties. In this thesis we focus on reducing the trust involved in the use of such PUFs and we introduce the Malicious PUFs model in which only PUFs generated by honest parties are assumed to be trusted. Thus the secu- rity of each party relies on its own PUF only and holds regardless of the goodness of the PUFs generated/used by the adversary. We are able to show that, under this more realistic assumption, one can achieve UC- secure computation, under computational assumptions. Moreover, we show how to achieve unconditional UC-secure commitments with (ma- licious) PUFs and with stateless tamper-proof hardware tokens. We discuss our contribution on this matter in Part I. These results are contained in papers [80] and [28]. In the second part of the thesis we focus on the concurrent setting, and we investigate on protocols achieving round optimality and black- box access to a cryptographic primitive. We study two fundamental functionalities: commitment scheme and zero knowledge, and we focus on some of the round-optimal constructions and lower bounds con- cerning both functionalities. We nd that such constructions present subtle issues. Hence, we provide new protocols that actually achieve the security guarantee promised by previous results. Concerning physical attacks, we consider adversaries able to re- set the machine of the honest party. In a reset attack a machine is forced to run a protocol several times using the same randomness. In this thesis we provide the rst construction of a witness indistinguish- able argument system that is simultaneous resettable and argument of knowledge. We discuss about this contribution in Part III, which is the content of the paper. [edited by Author]
Oblivious Transfer (OT) protocol is nowadays recognised as a generic primitive for all cryptographic protocols since it is one of the strongest primitives for secure multiparty computation (MPC). To design hardware-assisted OT protocols, Physically Unclonable Functions (PUFs) have been thoroughly studied in the literature. PUF-based OT protocols, however, necessitate the physical transfer of PUF devices, rendering them inappropriate in situations where the physical transfer of devices is not secure. Additionally, two-party secure computation protocols, in general, are performed between two distrusting parties. Yet, the PUF-based OT protocols require the PUF receiver to trust the PUF sender to behave honestly. Recent works have considered malicious PUF models resulting in more complex protocols. To avoid these drawbacks, we in this work rely on the concept of Physically Related Functions (PReFs), a pair of PUF devices that allow two PUF devices to generate similar responses over a "related" input set. XOR composition of PReFs, also called XOR_PReF, is an improved construction that eliminates the need for any trusted party and generates a "related" input set securely and independently. With the help of this new primitive, we propose 1-out-of-2 OT protocols using XOR_PReF in semi-honest as well as malicious settings keeping the protocol secure even after switching the roles of OT-sender and OT-receiver. Our protocols can be integrated into hardware-assisted MPC protocols and provide a safe and valuable solution for all OT-based techniques, notably Private Set Intersection (PSI), Private Information Retrieval (PIR), and Password Authenticated Key Exchange (PAKE).