Virtual Proofs of Reality and their Physical Implementation
Ulrich Rührmair, Juan Leonardo Martinez-Hurtado, Xiaolin Xu, Christian Kraeh, Christian Hilgers, Dima Kononchuk, Jonathan James Finley, Wayne P. Burleson
We discuss the question of how physical statements can be proven over digital communication channels between two parties (a "prover" and a "verifier") residing in two separate local systems. Examples include: (i) "a certain object in the prover's system has temperature X°C", (ii) "two certain objects in the prover's system are positioned at distance X", or (iii) "a certain object in the prover's system has been irreversibly altered or destroyed". As illustrated by these examples, our treatment goes beyond classical security sensors in considering more general physical statements. Another distinctive aspect is the underlying security model: We neither assume secret keys in the prover's system, nor do we suppose classical sensor hardware in his system which is tamper-resistant and trusted by the verifier. Without an established name, we call this new type of security protocol a "virtual proof of reality" or simply a "virtual proof" (VP). In order to illustrate our novel concept, we give example VPs based on temperature sensitive integrated circuits, disordered optical scattering media, and quantum systems. The corresponding protocols prove the temperature, relative position, or destruction/modification of certain physical objects in the prover's system to the verifier. These objects (so-called "witness objects") are prepared by the verifier and handed over to the prover prior to the VP. Furthermore, we verify the practical validity of our method for all our optical and circuit-based VPs in detailed proof-of-concept experiments. Our work touches upon, and partly extends, several established concepts in cryptography and security, including physical unclonable functions, quantum cryptography, interactive proof systems, and, most recently, physical zero-knowledge proofs. We also discuss potential advancements of our method, for example "public virtual proofs" that function without exchanging witness objects between the verifier and the prover.
We discuss the question of how physical statements can be proven over digital communication channels between two parties (a "prover" and a "verifier") residing in two separate local systems. Examples include: (i) "a certain object in the prover's system has temperature X°C", (ii) "two certain objects in the prover's system are positioned at distance X", or (iii) "a certain object in the prover's system has been irreversibly altered or destroyed". As illustrated by these examples, our treatment goes beyond classical security sensors in considering more general physical statements. Another distinctive aspect is the underlying security model: We neither assume secret keys in the prover's system, nor do we suppose classical sensor hardware in his system which is tamper-resistant and trusted by the verifier. Without an established name, we call this new type of security protocol a "virtual proof of reality" or simply a "virtual proof" (VP). In order to illustrate our novel concept, we give example VPs based on temperature sensitive integrated circuits, disordered optical scattering media, and quantum systems. The corresponding protocols prove the temperature, relative position, or destruction/modification of certain physical objects in the prover's system to the verifier. These objects (so-called "witness objects") are prepared by the verifier and handed over to the prover prior to the VP. Furthermore, we verify the practical validity of our method for all our optical and circuit-based VPs in detailed proof-of-concept experiments. Our work touches upon, and partly extends, several established concepts in cryptography and security, including physical unclonable functions, quantum cryptography, interactive proof systems, and, most recently, physical zero-knowledge proofs. We also discuss potential advancements of our method, for example "public virtual proofs" that function without exchanging witness objects between the verifier and the prover.
In this paper, we discuss the question how physical statements can be proven remotely over digital communication channels without using classical secret keys, and without assuming tamper-resistant and trusted measurement hardware in the location of the prover. Examples for the considered physical statements are: (i) “the temperature of a certain object is X◦C”, (ii) “two certain objects are positioned at distance X”, or (iii) “a certain object has been irreversibly altered or destroyed”. In lack of an established name, we would like to call the corresponding security protocols ”virtual proofs of reality” (VPs). While a host of variants seems conceivable, this paper focuses on VPs in which the verifier has handed over one or more specific physical objects Oi to the prover at some point prior to the VP. These “witness objects” assist the prover during the proof, but shall not contain classical digital keys nor be assumed tamper-resistant in the classical sense. The prover is allowed to open, inspect and alter these objects in our adversarial model, only being limited by current technology, while he shall still be unable to prove false claims to the verifier. In order to illustrate our concept, we give example protocols built on temperature sensitive integrated circuits, disordered optical scattering media, and quantum systems. These protocols prove the temperature, destruction/modification, or relative position of witness objects in the prover’s location. Full experimental realizations of these schemes are beyond the scope of this paper. But the protocols utilize established technologies from the areas of physical unclonable functions and quantum cryptography, and hence appear plausible also without such proof. Finally, we also discuss potential advancements of our method in theory, for example “public virtual proofs” that function without exchanging witness objects Oi between the verifier and the prover. Our work touches upon and partly extends several established cryptographic and security concepts, including physical unclonable functions, quantum cryptography, and interactive proof systems. Keywords-Virtual Proofs of Reality (VPs), Physical Unclonable Functions (PUFs), Interactive Proof Systems, Quantum Cryptography, Physical Cryptography
Abstract. Securely sharing the same secret key among multiple parties is the main concern in symmetric cryptography that is the workhorse of modern cryptography due to its simplicity and fast speed. Typically asymmetric cryptography is used to set up a shared secret between par-ties, after which the switch to symmetric cryptography can be made. In this paper, we introduce a novel key exchange protocol based on phys-ical hardware implementation to establish a shared secret between par-ties rather than relying on mathematical implementation of asymmetric cryptography. In particular, the key exchange is dependent on a new se-curity concept named as virtual proof of reality or simply virtual proof (VP) that enables proof of a physical statement over untrusted digital communication channels between two parties (a “prover ” and a “veri-fier”) residing in two separate local systems. We firstly exploit the VP to secure key exchange and further prove it by using experimental data. The key transfered in this protocol is only seen by the prover and hidden from not only the adversary but also the verifier. While only the verifier can successfully discover it.
A Zero-Knowledge Proof basically is a protocol between two parties, the Prover and the Verifier, that allows the Prover to convince the Verifier about the truthness of a non trivial statement without revealing any additional information. Zero Knowledge Proofs have found a lot of practical applications covering most of the protocols concerning about data privacy and protocol verification. Examples of that are anonymous cash or electronic voting. The possibility to have real quantum computers with a reasonable size in a near future is forcing the cryptographic community to devise new methods to provide security that resist quantum attacks. Most of the zero-knowledge protocols used nowadays are based on computational problems like the discrete logarithm problem that can no longer be considered hard, since there are known efficient ways to solve them with quantum algorithms. Cryptographic research about the quantum security of zero knowledge proofs started nearly 20 years ago in a very theoretical approach, but not many papers on that topic appeared since then. The goal of this thesis is writing a survey including the main concepts about quantum secure zero-knowledge protocols, the state-of-the-art both from the theoretical and practical approaches, and an exploration of their potential application areas. The survey will be a good starting document for further students willing to do research in this topic.
In a proof of knowledge (PoK), a verifier becomes convinced that a prover possesses privileged information. In combination with zero-knowledge proof systems, PoKs play an important role in security protocols such as in digital signatures and authentication schemes, as they enable a prover to demonstrate possession of certain information (such as a private key or a credential), without revealing it. A PoK is formally defined via the existence of an extractor, which is capable of reconstructing the key information that makes a verifier accept, given oracle access to any accepting prover. We extend this concept to the setting of a single classical verifier and multiple quantum provers and present the first statistical zero-knowledge (ZK) PoK proof system for problems in QMA. To achieve this, we establish the PoK property for the ZK protocol of Broadbent, Mehta, and Zhao (TQC 2024), which applies to the local Hamiltonian problem. More specifically, we construct an extractor which, given oracle access to a provers' strategy that leads to high acceptance probability, is able to reconstruct the ground state of a local Hamiltonian. Our result can be seen as a new form of self-testing, where, in addition to certifying a pre-shared entangled state, the verifier also certifies that provers have access to a quantum system, in particular, a ground state; this indicates a new level of verification for a proof of quantumness.
Position verification schemes are interactive protocols where entities prove their physical location to others; this enables interactive proofs for statements of the form "I am at a location L." Although secure position verification cannot be achieved with classical protocols (even with computational assumptions), they are feasible with quantum protocols.
In this paper we introduce the notion of zero-knowledge position verification, which generalizes position verification in two ways:
1. enabling entities to prove more sophisticated statements about their locations at different times (for example, "I was NOT near location L at noon yesterday").
2. maintaining privacy for any other detail about their true location besides the statement they are proving.
We construct zero-knowledge position verification from standard position verification and post-quantum one-way functions. The central tool in our construction is a primitive we call position commitments, which allow entities to privately commit to their physical position in a particular moment, which is then revealed at some later time.
In this paper, we introduce two formal means by which physical adversarial actions and features can be modeled in cryptography and security: The concepts of a “physical Turing machine (PhTM or φ-TM)” and of a “technology” on which the PhTM operates. We show by two examples how these concepts can be applied: Firstly, we sketch their use in formalizing physical adversarial computations (quantum computation [4], optical techniques [26, 15], etc.) in classical cryptpography, which an adversary might carry out to attack complexity-based schemes. Secondly, we work out in more detail the application of PhTMs in the formal treatment of physical unclonable functions and physical cryptography in general, in which disordered, unclonable physical objects are used for cryptographic purposes. PhTMs allow a rigid formal expression of the required properties of these objects (such as their physical unclonability), and enable us to lead formal reductionist proofs in this field. The hybrid nature of PhTMs thereby allows us to combine physical with computational assumptions in the proof. As an example, we lead a formal proof of a physical scheme that combines a classical digital signature with an unclonable, unique object in order to “label” or “tag” valuable objects securely and in a forgery-proof manner. We stress that PhTMs as introduced in this paper cannot directly and straightforwardly answer the question which physical tasks are eventually feasible and infeasible in our universe. But such an expectation would be unreasonably high; recall that classical Turing machines also do not allow to draw a simple line between feasible and infeasible computations, as the NP vs. P issue shows. Rather, they provide us with a formal backbone in which relevant physical security features can be expressed and security proofs can be led. Apart from the applications sketched in this paper, many other uses of PhTMs lie at hand, for example in defining security against side channels or invasive attacks, or in the development of a “physical” structural complexity theory, which are left to future work.