Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Virtual Proofs of Reality.

Ulrich Rührmair

Published Jan 1, 2014• 1 citation
OpenAlex

Abstract

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

Related papers

Virtual Proofs of Reality and their Physical Implementation

Ulrich Rührmair, Juan Leonardo Martinez-Hurtado, Xiaolin Xu +5 more

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.

IEEE Symposium on Security and Privacy (S&P)•May 1, 2015•47 citations

Secure Key Exchange Protocol based on Virtual Proof of Reality.

Yansong Gao

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.

•Jan 1, 2015•2 citations

Physical Turing Machines and the Formalization of Physical Cryptography.

Ulrich Rührmair

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.

•Jan 1, 2011•13 citations

Quantum readout of Physical Unclonable Functions

Boris Škorić

Physical unclonable functions (PUFs) are physical structures that are hard to clone and have a unique challenge-response behavior. The term PUF was coined by Pappu et al. in 2001. That work triggered a lot of interest, and since then a substantial number of papers has been written about the use of a wide variety of physical structures for different security purposes such as identification, authentication, read-proof key storage, key distribution, tamper evidence, anti-counterfeiting, software-to-hardware binding and trusted computing. In this paper we propose a new security primitive: the quantum-readout PUF (QR-PUF). This is a classical PUF, without internal quantum degrees of freedom, which is challenged using a quantum state, e.g. a single-photon state, and whose response is also a quantum state. By the no-cloning property of unknown quantum states, attackers cannot intercept challenges or responses without noticeably disturbing the readout process. Thus, a verifier who sends quantum states as challenges and receives the correct quantum states back can be certain that he is probing a specific QR-PUF without disturbances, even if the QR-PUF is far away "in the field" and under hostile control. For PUFs whose information content is not exceedingly large, all currently known PUF-based authentication and anti-counterfeiting schemes require trusted readout devices in the field. Our quantum readout scheme has no such requirement. Furthermore, we show how the QR-PUF authentication scheme can be interwoven with quantum key exchange (QKE), leading to an authenticated QKE protocol between two parties. This protocol has the special property that it requires no a priori secret shared by the two parties, and that the quantum channel is the authenticated channel, allowing for an unauthenticated classical channel. We provide security proofs for a limited class of attacks. The proofs depend on the physical unclonability of PUFs and on the practical infeasibility of building a quantum computer.

International Journal of Quantum Information•Feb 1, 2012•63 citations

Security Models and Cryptographic Protocols in a Quantum World

Céline Chevalier, Paul Hermouet, Quoc-Huy Vu

The emergence of quantum computing has provided new paradigms for cryptography. On the one hand, it poses significant new threats to existing classically cryptographic systems, requiring the community to define new security models that capture what a quantum adversary can do. On the other hand, it gives us new tools to design cryptographic protocols, with weaker assumptions than in the classical world, or even protocols that are impossible classically. In this survey, we first give an overview of new security definitions for classical cryptography, considering quantum adversaries who can either only use local quantum computation (post-quantum security), or even send quantum messages and in particular have access to oracle in superposition (quantum security). We explore these new notions through the examples of commitments, zero-knowledge proofs, encryption, and signatures. Then, we present what is arguably the most famous application of quantum cryptography: quantum key distribution (QKD) protocols that take advantage of unique properties of quantum mechanics to provide secure communication unconditionally. We also explore cryptography beyond QKD, focusing on unclonable cryptography: a family of cryptographic functionalities, built with quantum states, and designed to be resistant to counterfeit by leveraging the “no-cloning” theorem. We examine in particular quantum money, but also the recent notions of unclonable encryption and copy-protection, including related variants. By presenting a comprehensive survey of these topics, this paper aims to provide a thorough understanding of the current landscape and future potential of quantum cryptography.

Foundations and Trends® in Theoretical Computer Science•Jan 15, 2025•1 citation

Quantum Information and Variants of Interactive Proof Systems

Sarvagya Upadhyay

For nearly three decades, the model of interactive proof systems and its variants have been central to many important and exciting developments in computational complexity theory such as exact characterization of some well known complexity classes, development of probabilistically checkable proof systems and theory of hardness of approximation, and formalization of fundamental cryptographic primitives. \n \nOn the other hand, the theory of quantum information, which is primarily concerned with harnessing quantum mechanical features for algorithmic, cryptographic, and information processing tasks has found many applications. In the past three decades, quantum information has been used to develop unconditionally secure quantum cryptography protocols, efficient quantum algorithms for certain problems that are believed to be intractable in classical world, and communication efficient protocols. \n \nIn this thesis, we study the impact of quantum information on the models of interactive proof systems and their multi-prover variants. We study various quantum models and explore two questions. The first question we address pertains to the expressive power of such models with or without resource constraints. The second question is related to error reduction technique of such proof systems via parallel repetition. \n \nThe question related to the expressive power of models of quantum interactive proof systems and their variants lead us to the following results. \n \n(1) We show that the expressive power of quantum interactive proof systems is exactly PSPACE, the class of problems that can be solved by a polynomial-space deterministic Turing machines and that also admit a classical interactive proof systems. This result shows that in terms of complexity-theoretic characterization, both the models are equivalent. The result is obtained using an algorithmic technique known as the matrix multiplicative weights update method to solve a semidefinite program that characterizes the success probability of the quantum prover. \n\t \n(2) We show that polynomially many logarithmic-size unentangled quantum proofs are no more powerful than a classical proof if the verifier has the ability to process quantum information. This result follows from an observation that logarithmic-size quantum states can be efficiently represented classically and such classical representation can be used to efficiently generate the quantum state. \n\t \n(3) We also establish that the model of multi-prover quantum Merlin Arthur proof system, where the verifier is only allowed to apply nonadaptive unentangled measurement on each proof and then a quantum circuit on the classical outcomes, is no more powerful than QMA under the restriction that there are only polynomial number of outcomes per proof. This result follows from showing that such proof systems also admit a QMA verification procedure. \n \nThe question related to error reduction via parallel repetition lead us to following results on a class of two-prover one-round games with quantum provers and a class of multi-prover QMA proof systems. \n \n(1) We establish that for a certain class of two-prover one-round games known as XOR games, admit a perfect parallel repetition theorem in the following sense. When the provers play a collection of XOR games, an optimal strategy of the provers is to play each instance of the collection independently and optimally. In particular, the success probability of the quantum provers in the n-fold repetition of an XOR game G with quantum value w(G) is exactly (w(G))^n. \n\t \n(2) We show a parallel repetition theorem for two-prover one-round unique games. More specifically, we prove that if the quantum value of a unique game is 1-e, then the quantum value of n-fold repetition of the game is at most (1-e^2/49)^n. We also establish that for certain class of unique games, the quantum value of the n-fold repetition of the game is at most (1-e/4)^n. For the special case of XOR games, our proof technique gives an alternate proof of result mentioned above. \n\t \n3. Our final result on parallel repetition is concerned with SepQMA(m) proof systems, where the verifier receives m unentangled quantum proofs and the measurement operator corresponding to outcome "accept" is a fully separable operator. We give an alternate proof of a result of Harrow and Montanaro [HM10] that states that perfect parallel repetition theorem holds for such proof systems. \n \nThe first two results follow from the duality of semidefinite programs and the final result follows from cone programming duality.

•Aug 24, 2011•1 citation
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
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.
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.
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.
Physical unclonable functions (PUFs) are physical structures that are hard to clone and have a unique challenge-response behavior. The term PUF was coined by Pappu et al. in 2001. That work triggered a lot of interest, and since then a substantial number of papers has been written about the use of a wide variety of physical structures for different security purposes such as identification, authentication, read-proof key storage, key distribution, tamper evidence, anti-counterfeiting, software-to-hardware binding and trusted computing. In this paper we propose a new security primitive: the quantum-readout PUF (QR-PUF). This is a classical PUF, without internal quantum degrees of freedom, which is challenged using a quantum state, e.g. a single-photon state, and whose response is also a quantum state. By the no-cloning property of unknown quantum states, attackers cannot intercept challenges or responses without noticeably disturbing the readout process. Thus, a verifier who sends quantum states as challenges and receives the correct quantum states back can be certain that he is probing a specific QR-PUF without disturbances, even if the QR-PUF is far away "in the field" and under hostile control. For PUFs whose information content is not exceedingly large, all currently known PUF-based authentication and anti-counterfeiting schemes require trusted readout devices in the field. Our quantum readout scheme has no such requirement. Furthermore, we show how the QR-PUF authentication scheme can be interwoven with quantum key exchange (QKE), leading to an authenticated QKE protocol between two parties. This protocol has the special property that it requires no a priori secret shared by the two parties, and that the quantum channel is the authenticated channel, allowing for an unauthenticated classical channel. We provide security proofs for a limited class of attacks. The proofs depend on the physical unclonability of PUFs and on the practical infeasibility of building a quantum computer.
The emergence of quantum computing has provided new paradigms for cryptography. On the one hand, it poses significant new threats to existing classically cryptographic systems, requiring the community to define new security models that capture what a quantum adversary can do. On the other hand, it gives us new tools to design cryptographic protocols, with weaker assumptions than in the classical world, or even protocols that are impossible classically. In this survey, we first give an overview of new security definitions for classical cryptography, considering quantum adversaries who can either only use local quantum computation (post-quantum security), or even send quantum messages and in particular have access to oracle in superposition (quantum security). We explore these new notions through the examples of commitments, zero-knowledge proofs, encryption, and signatures. Then, we present what is arguably the most famous application of quantum cryptography: quantum key distribution (QKD) protocols that take advantage of unique properties of quantum mechanics to provide secure communication unconditionally. We also explore cryptography beyond QKD, focusing on unclonable cryptography: a family of cryptographic functionalities, built with quantum states, and designed to be resistant to counterfeit by leveraging the “no-cloning” theorem. We examine in particular quantum money, but also the recent notions of unclonable encryption and copy-protection, including related variants. By presenting a comprehensive survey of these topics, this paper aims to provide a thorough understanding of the current landscape and future potential of quantum cryptography.
For nearly three decades, the model of interactive proof systems and its variants have been central to many important and exciting developments in computational complexity theory such as exact characterization of some well known complexity classes, development of probabilistically checkable proof systems and theory of hardness of approximation, and formalization of fundamental cryptographic primitives. \n \nOn the other hand, the theory of quantum information, which is primarily concerned with harnessing quantum mechanical features for algorithmic, cryptographic, and information processing tasks has found many applications. In the past three decades, quantum information has been used to develop unconditionally secure quantum cryptography protocols, efficient quantum algorithms for certain problems that are believed to be intractable in classical world, and communication efficient protocols. \n \nIn this thesis, we study the impact of quantum information on the models of interactive proof systems and their multi-prover variants. We study various quantum models and explore two questions. The first question we address pertains to the expressive power of such models with or without resource constraints. The second question is related to error reduction technique of such proof systems via parallel repetition. \n \nThe question related to the expressive power of models of quantum interactive proof systems and their variants lead us to the following results. \n \n(1) We show that the expressive power of quantum interactive proof systems is exactly PSPACE, the class of problems that can be solved by a polynomial-space deterministic Turing machines and that also admit a classical interactive proof systems. This result shows that in terms of complexity-theoretic characterization, both the models are equivalent. The result is obtained using an algorithmic technique known as the matrix multiplicative weights update method to solve a semidefinite program that characterizes the success probability of the quantum prover. \n\t \n(2) We show that polynomially many logarithmic-size unentangled quantum proofs are no more powerful than a classical proof if the verifier has the ability to process quantum information. This result follows from an observation that logarithmic-size quantum states can be efficiently represented classically and such classical representation can be used to efficiently generate the quantum state. \n\t \n(3) We also establish that the model of multi-prover quantum Merlin Arthur proof system, where the verifier is only allowed to apply nonadaptive unentangled measurement on each proof and then a quantum circuit on the classical outcomes, is no more powerful than QMA under the restriction that there are only polynomial number of outcomes per proof. This result follows from showing that such proof systems also admit a QMA verification procedure. \n \nThe question related to error reduction via parallel repetition lead us to following results on a class of two-prover one-round games with quantum provers and a class of multi-prover QMA proof systems. \n \n(1) We establish that for a certain class of two-prover one-round games known as XOR games, admit a perfect parallel repetition theorem in the following sense. When the provers play a collection of XOR games, an optimal strategy of the provers is to play each instance of the collection independently and optimally. In particular, the success probability of the quantum provers in the n-fold repetition of an XOR game G with quantum value w(G) is exactly (w(G))^n. \n\t \n(2) We show a parallel repetition theorem for two-prover one-round unique games. More specifically, we prove that if the quantum value of a unique game is 1-e, then the quantum value of n-fold repetition of the game is at most (1-e^2/49)^n. We also establish that for certain class of unique games, the quantum value of the n-fold repetition of the game is at most (1-e/4)^n. For the special case of XOR games, our proof technique gives an alternate proof of result mentioned above. \n\t \n3. Our final result on parallel repetition is concerned with SepQMA(m) proof systems, where the verifier receives m unentangled quantum proofs and the measurement operator corresponding to outcome "accept" is a fully separable operator. We give an alternate proof of a result of Harrow and Montanaro [HM10] that states that perfect parallel repetition theorem holds for such proof systems. \n \nThe first two results follow from the duality of semidefinite programs and the final result follows from cone programming duality.