Say that a manufacturer wants to label her products in such a way that a third party could verify that the manufacturer is the one that labeled the product, meaning it's not a counterfeit.

The manufacturer could have a serial number to each product, and have it signed with some signature scheme. However, this introduces some redundancy, as a verifier would have to use both the manufacture's public key and the serial number.

Is there a different, more efficiently method create such labels?

Two cases are of special interest:

  • The label should be publicly verifiable.
  • The label should only be verifiable by an entity that share some secret information with the manufacturer (so perhaps encryption schemes are relevant).
  • $\begingroup$ Is it required that the third party doing the verification does not need to hold confidential data allowing whoever holds that data (including the third party) to forge a Unique Non-Reproducible ID? Is it required that a serial number (perhaps, sequential) is A) a subfield of the UNRID? B) recoverable by some other public process from UNRID? C) hidden but recoverable by some other process requiring a secret key? D) not needed? $\endgroup$
    – fgrieu
    Nov 26, 2019 at 10:06
  • $\begingroup$ @kelalaka: I'm not familiar with RFC 4122, but I do not see that its UUIDs are verifiable as thought by the question. $\endgroup$
    – fgrieu
    Nov 26, 2019 at 10:09
  • $\begingroup$ @fgrieu Not sure I understand the first question. I am interested in two cases: (1) The genuineness of the label should be publicly verifiable, and (2) The genuineness of the label should be verifiable by an entity given some secret information by the manufacturer. A serial number can be used if needed, but in my eyes it should be possible to avoid it. $\endgroup$
    – Snoop Catt
    Nov 26, 2019 at 10:25

1 Answer 1


It is desired a Unique Non-Reproducible ID (UNRID) which genuineness is publicly verifiable.

I know no standard for that. But we can take as UNRID the signature of a public fixed message (e.g. empty), if the signature scheme is randomized and EUF-CMA secure. Verification simply checks the signature. If probability of collision among signatures is satisfactorily low, security follows from EUF-CMA.

The signature scheme could be RSASSA-PSS of PKCS#1v2.2, with the advantage of fast signature verification. But for modern security that requires 256 bytes (342 Base64 characters), which is a lot.

A more compact option is a slight variant of ECDSA, where a signature $(r,s)$ becomes the UNRID $(r,\min(s,n-s))$, which is presented as EUF-CMA secure there, without proof but plausibly: EUF-CMA security of the signature scheme matters in Bitcoin, and was repaired with apparent success, in a manner equivalent to what's proposed. That would make the UNRID 64-byte (86 Base64 characters).

Using a signature scheme with message recovery, we can embed a serial number or other small ancillary information in the UNRID, without making it bigger. For RSA, ISO/IEC 9796-2 Scheme 2 would do (it's essentially RSASSA-PSS with message recovery). There are ECC-based randomized signature schemes with message recovery as compact as ECDSA, see bibliography.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.