Toward an automated verification of certificates of authenticity

A certificate of authenticity (COA) is an inexpensivephysical object that has a random unique structure with a highcost of exact reproduction. An additional requirement is that theuniqueness of COA's random structure can be verified using aninexpensive device. Donald Bauder was the first to propose COA screated as a randomized augmentation of a set of fixed-length fibers into a transparent gluing material that fixes once for all the position of the fibers within. The statistics of the positioning of fibers is used as a source of randomness that is difficult to replicate.As oppose to recording authentic fiber-based COA structures in adatabase, we use public-key cryptography to authenticate COAs.During certification, the unique property of the physical objectis extracted, combined with an arbitrary text, signed with the private key of the issuer, and the signature is encoded andprinted as a barcode on the COA. Since the capacity of the barcodeis limited, the goal of any COA system is to contain in the signed message as much information about the random structure of the physical object as possible. In this paper, we show that the cost of forging a particular COA instance is exponentially proportional to the improvement in compressing COA's random features. Next, we formally define the compression objective, show that finding its optimal solution is an NP-hard problem, and propose a heuristic that improves significantly upon best standard compression methods.