Everlasting UC Commitment from Malicious PUFs Without a Common Reference String

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

View PDF · LaTeX source · Formal statement — not yet formalized

Everlasting security asks that a protocol stay secure after the computational assumptions it used are broken: the attacker is efficient while the protocol runs and unbounded afterwards. Everlasting composable commitment is known to be unachievable from a common reference string or a PKI alone, so every construction rests on a physical assumption — and until this source, all of them also required the physical device to be honestly manufactured.

The source removes that second requirement. In its fully malicious token model the adversary may build arbitrarily malicious hardware tokens — including tokens that encapsulate other tokens — while the honest party’s device is only assumed to be a PUF with the stated reproducibility and unpredictability properties. Its Theorem 31 gives a protocol that everlastingly UC-realizes the multi-commitment functionality in that model, using a common reference string.

Conjecture (no trusted setup). There exist a polynomial \(\ell\), functions \(\gamma, \delta\), a PUF family that is \(\delta\)-reproducible, \((\gamma,\delta)\)-unpredictable and admits a lazy sampler, and a two-party protocol \(\Pi\) with PPT honest parties, such that \(\Pi\) everlastingly UC-realizes \(\mathcal{F}_{\mathsf{MCom}}\) in the hardware-token hybrid model — with no common reference string and no other trusted setup.

The statement is the affirmative direction. A refutation would be an impossibility theorem, and the source predicts neither.

Sources

Magri, Malavolta, Schröder, and Unruh. Everlasting UC Commitments from Fully Malicious PUFs. Cryptology ePrint Archive, Report 2021/248; Journal of Cryptology, 2022. Read at the revision of 7 June 2022, the later of two postings, byte-identical to the harvested copy (SHA-256 prefix ce85b7f0a94ce11e, 37 pages). The construction claim is on p. 1 and Theorem 31; the reason the CRS is needed, the objection to trace-simulation techniques, and the open question are all on p. 8; the prior impossibility without a physical assumption is quoted on p. 14; the adaptive-unpredictability definition is on p. 19. All four authors read off the paper’s own title page; the venue confirmed against DBLP, which records a Journal of Cryptology 2022 publication.

View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized

Open, and the source says exactly where the difficulty is.

Why the CRS is there. “Our protocol needs to assume the existence of a common reference string to equivocate commitments in the security proof.” The simulator must be able to open a commitment both ways, and it gets that ability from knowing how the reference string was generated.

Why the standard replacement fails. The usual way to avoid a CRS is to extract from, or simulate, the protocol trace. The source rules that out for a reason peculiar to everlasting security: “this class of techniques does not seem to apply to the everlasting setting since the environment can distinguish a simulated trace once it becomes” unbounded. A simulation that is only computationally indistinguishable is worthless once the distinguisher stops being efficient — which is precisely the regime everlasting security is about.

A named avenue, not obviously closed. The source considers adapting the techniques of the prior work it cites and reports: “It is not clear if the techniques of [DS13] can be adapted to our setting.” So there is a candidate route, unresolved.

The impossibility that shapes the question. Prior work showed everlasting UC commitments cannot be realised “not even in the common reference string (CRS) or the public-key infrastructure (PKI)” model — that is, without a physical assumption. That result is why the question is “can the CRS go, given the PUF” rather than “can the physical assumption go”. The two should not be confused: nobody is asking for everlasting UC commitment from nothing.

The interesting structure here is that two setup assumptions are in play and only one is negotiable. The physical assumption is provably necessary. The reference string is not known to be, and the source’s own construction happens to need it for a reason internal to its proof technique rather than for anything the model demands.

That is a good sign for the affirmative direction — a CRS introduced by a proof strategy is more often removable than one introduced by an impossibility — but the source’s objection cuts the other way: the reason the CRS is hard to remove here is the same reason everlasting security is interesting at all, namely that the distinguisher eventually gets unbounded. Equivocation techniques that rely on computational indistinguishability are exactly what everlasting security invalidates.

Worth noting how much the malicious-token model is doing. The tokens may be adversarially manufactured and may wrap other tokens, which is strictly harder than the honestly-manufactured setting earlier work assumed; the site’s F-wrap entry is the idealisation of the honest case, and reading the two together shows how much of the usual token convenience this model gives up.

Construct a CRS-free protocol, or prove an impossibility for the fully malicious token model without setup.
Determine whether the techniques of the prior work the source names can in fact be adapted — the source says it is “not clear”, which is an invitation.
Find an equivocation technique whose indistinguishability survives an eventually-unbounded environment, or show none exists.
Separate the question from the known impossibility: establish precisely which trusted setups remain impossible once a PUF is available.
Check whether the adaptive-unpredictability strengthening the source requires of its PUFs is needed for the CRS-free case too, or is an artefact of the CRS construction.
Formalize the statement in Lean. Everlasting UC, the fully malicious token model and PUF unpredictability all need writing down first, and none exists in Mathlib.