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

PUFs are used in several applications like secure storage, RFID systems, anti-counterfeiting mechanisms, identification and authentication protocols [13, 16, 25, 31, 32, 35].

This can be extended to other functionalities but not to all functionalities.

A concurrent and independent work [30] considers an adversary that can encapsulate PUFs but does not propose UC-secure definitions/constructions.

Since the adversary knows the code of maliciously generated PUFs, this model automatically captures real-world scenarios where an adversary may be encapsulating other malicious PUFs inside its own.

This is fixed later by using coin-tossing to generate \((x_0, x_1)\), see Sect. 4.

In Sect. 6, we consider an even stronger model where \({\mathcal R} \) may encapsulate \(\mathsf {PUF}_s\) within a possibly malicious \(\widehat{\mathsf {PUF}}_s\). \(\widehat{\mathsf {PUF}}_s\) externally forwards some queries to \(\mathsf {PUF}_s\) and forwards the outputs to the evaluator, while possibly replacing some or all of these outputs with other arbitrary values. We note that this covers the case where the receiver generates \(\widehat{\mathsf {PUF}}_s\) malicious and independently of \({\mathsf {PUF}}_s\).

We assume the simulator can control which simulator queries the adversary’s PUF records (but an honest party cannot). Indeed, without our assumption, if a stateful PUF recorded every simulator query, a malicious sender on getting back \(\mathsf {PUF}_s\) may observe the correlation between queries \((c, c')\) recorded by the PUF when the simulator queried it, versus two random queries when an actual honest party queried it. Ours is a natural assumption and obtaining secure OT remains extremely non-trivial even with this assumption. We note that this requirement can be removed using standard secret sharing along with cut-and-choose, but at the cost of a more complicated protocol with a worse OT production rate. This protocol is described in the full version of this paper.

The UC framework (and its variants) seemingly fail to capture the possibility of transfer of physical devices like PUFs across different protocols, to the best of our knowledge. Within our OT protocol, we invoke the ideal functionality for UC-secure commitments. Thus, we would like to ensure that our UC-secure commitment scheme composes with the rest of the protocol even if PUFs created in the commitment scheme are used elsewhere in the OT protocol and vice versa. In our protocol, the only situation where such an issue might arise, is if one of the parties in the main OT protocol, later maliciously passes a PUF that it received from the honest party during a commitment phase. This is avoided by requiring all parties to return the PUFs to their original creator at the end of the decommitment phase. Note that this does not violate security even if the PUFs are malicious and stateful. The creating party, like in previous works [7, 8] can probe a random point before sending the PUF, and then check this point again on receiving the PUF, to ensure that they received the correct PUF. Generic results attempting to model UC security in presence of physical devices that can be transferred across different protocol executions have been presented in [3, 20].