Abstract
While the integrity of digital data can be ensured via digital signatures, ensuring the integrity of physical data, i.e., objects, is a more challenging task. For example, constructing a digital signature on data extracted from an object does not necessarily guarantee that an adversary has not tampered with the object or replaced this with a cleverly constructed counterfeit. This paper proposes a new concept called signatures for objects to guarantee the integrity of objects cryptographically. We first need to consider a mechanism that allows us to mathematically treat objects which exist in the physical world. Thus, we define a model called an object setting in which we define physical actions, such as a way to extract data from objects and test whether two objects are identical. Modeling these physical actions via oracle access enables us to naturally enhance probabilistic polynomial-time algorithms to algorithms having access to objects—we denote these physically enhanced algorithms (PEAs). Based on the above formalization, we introduce two security definitions for adversaries modeled as PEAs. The first is unforgeability, which is the natural extension of EUF-CMA security, meaning that any adversary cannot forge a signature for objects. The second is confidentiality, which is a privacy notion, meaning that signatures do not leak any information about signed objects. With these definitions in hand, we show two generic constructions: one satisfies unforgeability by signing extracted data from objects; the other satisfi
