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.
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.
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
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.
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 present a rigorous, self-contained proof that an idealised Ising Machine (IM)-defined axiomatically from the experimentally observed properties of coherent Ising machines (CIMs), quantum annealers, and memristive/optical Ising processors-satisfies every clause of the canonical definition of a non-deterministic computing device in the sense of Turing (1936), Rabin and Scott (1959), and Cook (1971). Concretely, we show that (i) The physical ground-state search performed by an N-spin Ising Machine is not a deterministic computation: the machine simultaneously and physically explores an exponential number of spin configurations, and the branch that is "selected" (the ground state) is not the output of any single deterministic trajectory. (ii) There exists a polynomial-time simulation of any non-deterministic Turing machine (NDTM) by a suitably scaled Ising Machine, and conversely, every Ising Machine computation can be simulated by an NDTM in polynomial time. Hence the Ising Machine decides exactly the class NP in polynomial physical time. (iii) Because NP is, by definition, the class of languages decidable in polynomial time on a non-deterministic machine, a scalable Ising Machine would solve every NP problem in polynomial time, rendering all cryptographic schemes whose security relies on NP-hard or presumed-intractable problems (RSA, ECC, lattice-based, subset-sum-based, code-based, etc.) insecure. The argument is structured axiomatically: we first isolate the minimal physical axioms an Ising Machine must satisfy, then construct a formal mapping to the NDTM model, and finally derive the complexity-theoretic and cryptographic consequences. We discuss the crucial role of the scalability assumption and the engineering gap that currently prevents the full realisation of the threat.
This thesis presents a formal model for quantum protocols, that is, cryptographic protocols based on quantum mechanics. It also develops a definition of security (which includes notions such as privacy and correctness) for quantum protocols.
First, existing classical (non-quantum) definitions of security are studied. There are essentially two approaches: one based on Turing Machines and simulation, the other using information theory. Both approaches are explored in detail and compared, then a particular variation of the first approach is chosen. Security is defined by introducing an interface (also called a simulator) which is capable of translating an attack on protocol 1 into an attack on protocol 2. The profile of a protocol is a stochastic variable, defined as the output of the participants and the view of the adversary who performs the attack. If an interface exists such that the profile of protocol 1 is indistinguishable from the profile of protocol 2 with the help of this interface, then protocol 1 is at least as secure as protocol 2. An absolute notion of security is obtained by comparing the protocol implementation with its 'ideal' equivalent.
In this approach, and in classical cryptography in general, indistinguishability of probability distributions is a crucial tool. The meaning of this notion is explored in the context of density matrices, the mathematical formalism which is used to describe the state of a quantum system. Various measures of distinguishability of quantum states relevant from a cryptographic point of view are investigated: probability of error, trace norm (related to the Kolmogorov distance), overlap (related to the Bhattacharyya coefficient) and Shannon distinguishability (defined through the mutual information). It is shown that if we require that the distinguishability between two families of quantum states vanish exponentially fast, these four distinguishability measures are equivalent.
Along the way upper and lower bounds for the Shannon distinguishability are obtained. This is a very useful result, because explicit computation of the Shannon distinguishability between two quantum states is often difficult (it requires solving a transcendental equation), whereas the other distinguishability measures, in particular the trace norm, are usually much easier to compute.
In the last chapter the two previous topics are combined. A formal model for quantum protocols is formulated. It uses Quantum Turing Machines to represent the participants, who communicate through a quantum channel. The different nature of quantum information as opposed to classical information is explored in detail, including the implications this has for the definition. As in the classical case, we introduce an interface to compare the security of two protocols for the same task. Subsequently some consequences of the proposed definition are investigated. In particular, strong evidence is given that one classical technique often used in proofs of security for classical protocols, called rewinding, is impossible in the quantum setting.
Over the past decades, quantum technology has seen consistent progress, with notable recent developments in the field of quantum computers. Traditionally, this trend has been primarily seen as a serious risk for cryptography; however, a positive aspect of quantum technology should also be stressed. In this regard, viewing this technology as a resource for honest parties rather than adversaries, it may enhance not only the security, but also the performance of specific cryptographic schemes. While considerable effort has been devoted to the design of quantum-resistant and quantum-enhanced schemes, little effort has been made to understanding their physical security. Physical security deals with the design and implementation of security measures fulfilling the practical requirements of cryptographic primitives, which are equally essential for classic and quantum ones. This survey aims to draw greater attention to the importance of physical security, with a focus on secure key generation and storage as well as secure execution. More specifically, the possibility of performing side-channel analysis in the quantum world is discussed and compared to attacks launched in the classic world. Besides, proposals for quantum random number generation and quantum physically unclonable functions are compared to their classic counterparts and further analyzed to give a better understanding of their features, advantages, and shortcomings. Finally, seen from these three perspectives, this survey provides an outlook for future research in this direction.