Quantum entangled states have shown distinguished features beyond any classical state. Many methods like quantum state tomography have been presented to verify entanglement. In this work, we aim to identify unknown entanglements with partial information of the state space by developing a nonlinear entanglement witness. The witness consists of a generalized Greenberger-Horne-Zeilinger-like paradox expressed by Pauli observables, and a nonlinear inequality expressed by density matrix elements. First, we verify unknown bipartite entanglements and study the robustness of entanglement witnesses against the white noise. Second, we generalize such a verification to unknown multipartite entangled states, including the Greenberger-Horne-Zeilinger-type states and the cluster states under local channel operations. Third, we give a quantum-information application related to the quantum zero-knowledge proof. Our results provide a useful method in verifying universal quantum computation resources with robustness against white noises. Our work is applicable to detect unknown entanglement without the state tomography.
The advancement of quantum computers undermines the security of classical blockchain, necessitating either a post-quantum upgrade of the existing architecture or creation of an inherently quantum blockchain. Here we propose a practically realizable model of a fully quantum blockchain based on a generalized Gram-Schmidt procedure utilizing dimensional lifting. In this model, information of transactions stored in a multi-qubit state are subsequently encoded using the generalized Gram-Schmidt process. The chain is generated as a result of the reliance of orthogonalized state on the sequence of states preceding it. Various forking scenarios and their countermeasures are considered for the proposed model. It is shown to be secure even against quantum computing attacks using the no-cloning theorem and non-democratic nature of Generalized Gram-Schmidt orthogonalization. Finally, we outline a framework for a quantum token built on the same architecture as our blockchain.
Quantum computing is no longer a thing of the future. Shor’s algorithm proved that a quantum computer couldtraverse key of factoring problems in polynomial time. Because the time-complexity of the exhaustive keysearch for quantum computing has not reliably exceeded the reasonable expiry of crypto key validity, it is believedthat current cryptography systems built on top of computational security are not quantum-safe. Quantumkey distribution fundamentally solves the problem of eavesdropping; nevertheless, it requires quantumpreparatory work and quantum-network infrastructure, and these remain unrealistic with classical computers.In transitioning to a mature quantum world, developing a quantum-resistant mechanism becomes a stringentproblem. In this research, we innovatively tackled this challenge using a non-computational difficulty schemewith zero-knowledge proof in order to achieve repellency against quantum computing cryptanalysis attacks foruniversal classical clients.
The advent of quantum computing threatens blockchain protocols and networks because they utilize non-quantum resistant cryptographic algorithms. When quantum computers become robust enough to run Shor's algorithm on a large scale, the most used asymmetric algorithms, utilized for digital signatures and message encryption, such as RSA, (EC)DSA, and (EC)DH, will be no longer secure. Quantum computers will be able to break them within a short period of time. Similarly, Grover's algorithm concedes a quadratic advantage for mining blocks in certain consensus protocols such as proof of work. Today, there are hundreds of billions of dollars denominated in cryptocurrencies and other digital assets that rely on blockchain ledgers as well as thousands of blockchain-based applications storing value in blockchain networks. Cryptocurrencies and blockchain-based applications require solutions that guarantee quantum resistance in order to preserve the integrity of data and assets in these public and immutable ledgers. The quantum threat and some potential solutions are well understood and presented in the literature. However, most proposals are theoretical, require large QKD networks, or propose new quantum-resistant blockchain networks to be built from scratch. Our work, which is presented in this paper, is pioneer in proposing an end-to-end framework for post-quantum blockchain networks that can be applied to existing blockchain to achieve quantum-resistance. We have developed an open-source implementation in an Ethereum-based (i.e., EVM compatible) network that can be extended to other existing blockchains. For the implementation we have (i) used quantum entropy to generate post-quantum key pairs, (ii) established post-quantum TLS connections and X.509 certificates to secure the exchange of information between blockchain nodes over the internet without needing a large QKD network, (iii) introduced a post-quantum second signature in transactions using Falcon-512 post-quantum keys, and (iv) developed the first on-chain verification of post-quantum signatures using three different mechanisms that are compared and analyzed: Solidity smart-contracts run by the validators for each transaction, modified EVM Opcode, and precompiled smart contracts.
We propose the first generalization of the famous Non-Interactive\nZero-Knowledge (NIZK) proofs to quantum languages (NIZKoQS) and we provide a\nprotocol to prove advanced properties on a received quantum state\nnon-destructively and non-interactively (a single message being sent from the\nprover to the verifier).\n In our second orthogonal contribution, we improve the costly Remote State\nPreparation protocols [CCKW18,CCKW19,GV19] that can classically fake a quantum\nchannel (this is at the heart of our NIZKoQS protocol) by showing how to create\na multi-qubits state from a single superposition.\n Finally, we generalize these results to a multi-party setting and prove that\nmultiple parties can anonymously distribute a GHZ state in such a way that only\nparticipants knowing a secret credential can share this state, which could have\napplications to quantum anonymous transmission, quantum secret sharing, quantum\nonion routing and more.\n
In this paper, we introduce a new approach to fix the validation of a block and the assignment of a new block in a blockchain infrastructure by using a novel negotiation procedure. The block validation and assignment are reached thanks to negotiation procedures based on an extended probability environment. Also, by using a multiscale approach (typical of Complexity Theory) and Quantum and Relativistic Mechanics, the result appears to solve some of the most relevant questions in the Blockchain context, which are the democracy and the randomness of the validator of a block and the assignment of the new one. The selection of actors to mine is invariant concerning the number of addresses, i.e., the coins of owners, which have more chance to be selected generally. This work is the companion of CQKD (Computational Quantum Key Distribution), as we will see in the introduction, where we considered the infrastructural question of the key distribution; also, it is a very effective application of the decision and reasoning in incompleteness or uncertainty conditions as described in the previous and prodromic paper as described in the introduction too.
This White Paper introduces and contributes the first implementation of the Decentralized Voting Algorithm. First, Part I provides an overview for the software structures relevant to this work. Second, Part II introduces a decentralized voting algorithm for transferring value on blockchain networks. Third, Part III explains the voting algorithm’s implementation in reach, including the backend architecture, web deployment, and quantum integration. Perhaps most significantly, this paper solves the Decentralized Voting Problem with a new quantum consensus system.
This article considered deficiencies of the flourishing blockchain technology manifested by the development of quantum computation. We show that the future blockchain technology would under constant threats from the following aspects: 1) Speed up the generation of nonces; 2) Faster searching for hash collisions; 3) Break the security of the classical encryption. We also demonstrate that incorporating some quantum properties into blockchain makes it more robust and more efficient. For example people can establish a quantum-security blockchain system that utilizes quantum key distribution (QKD), and quantum synchronization and detectable Byzantine agreement (DBA) can help the blockchain systems achieve faster consensus even if there exist a number of malicious nodes.
The posthoc verification protocol [J. F. Fitzsimons, M. Hajdu{\v s}ek, and T. Morimae, Physical Review Letters {\bf120}, 040501 (2018)] enables an information-theoretically-sound non-interactive verification of quantum computing, but the message from the prover to the verifier is quantum and the verifier has to do single-qubit measurements. The Mahadev protocol removes these quantum parts, but the soundness becomes the computational one. In this paper, we construct an information-theoretically-sound non-interactive classical verification protocol for quantum computing with a trusted center. The trusted center sends random BB84 states to the prover, and the classical descriptions of these BB84 states to the verifier. The messages from the center to the prover and the verifier are independent of the instance. By slightly modifying our protocol, we also construct a non-interactive statistical zero-knowledge proof system for QMA with the trusted center.
Shreya Banerjee, Arghya Mukherjee, Prasanta K. Panigrahi
This paper proposes a protocol to prepare a blockchain using quantum tools which maintains the distributive nature of the blockchain and provides security against a quantum attacker. The authors provide an example of a two blockchain prepared in IBM 5 qubit quantum computer, as a proof of concept with fidelity close to 0.9548.
No-signalling (NOSIG) correlations, that are stronger than those allowed by quantum entanglement yet do not violate relativistic causality, are a valuable resource for understanding information processing systems. Such correlations can be achieved between non-communicating players in games when the players use what is called non-local strategies, and can give the players better odds at winning in these games. We propose definitions for non-local strategies in relativistic multi-player non-local games. We prove a conjecture by Crépeau stating that any non-local strategy that can be simultaneously produced by any pi-signalling strategy in a multi-player non-local game, has to be a NOSIG strategy. Pi-signalling strategies are achieved when 1-way signalling is allowed between players arranged on a line defined by some permutation. This result gives us a better understanding of how NOSIG strategies fit with the other non-local strategies, and can help in constructing novel NOSIG multi-player strategies and help prove they produce NOSIG correlations. Finally, we extend the definition of zero-knowledge proof systems to the relativistic multi-prover, multi-verifier setting, and propose definitions for what it means for a non-local strategy to have polynomial time complexity
In this work we consider the interplay between multiprover interactive proofs, quantum entanglement, and zero knowledge proofs - notions that are central pillars of complexity theory, quantum information and cryptography. In particular, we study the relationship between the complexity class MIP*, the set of languages decidable by multiprover interactive proofs with quantumly entangled provers, and the class PZK-MIP*, which is the set of languages decidable by MIP* protocols that furthermore possess the perfect zero knowledge property. Our main result is that the two classes are equal, i.e., MIP* = PZK-MIP*. This result provides a quantum analogue of the celebrated result of Ben-Or, Goldwasser, Kilian, and Wigderson (STOC 1988) who show that MIP = PZK-MIP (in other words, all classical multiprover interactive protocols can be made zero knowledge). We prove our result by showing that every MIP* protocol can be efficiently transformed into an equivalent zero knowledge MIP* protocol in a manner that preserves the completeness-soundness gap. Combining our transformation with previous results, we obtain the corollaries that i) all languages that can be solved in non-deterministic double exponential time have zero knowledge MIP* protocols and ii) all co-recursively enumerable languages (which include undecidable problems as well as all decidable problems) have zero knowledge MIP* protocols with vanishing promise gap.
We outline a quantum-enabled blockchain architecture based on a consortium of quantum servers. The network is hybridised, utilising digital systems for sharing and processing classical information combined with a fibre--optic infrastructure and quantum devices for transmitting and processing quantum information. We deliver an energy efficient interactive mining protocol enacted between clients and servers which uses quantum information encoded in light and removes the need for trust in network infrastructure. Instead, clients on the network need only trust the transparent network code, and that their devices adhere to the rules of quantum physics. To demonstrate the energy efficiency of the mining protocol, we elaborate upon the results of two previous experiments (one performed over 1km of optical fibre) as applied to this work. Finally, we address some key vulnerabilities, explore open questions, and observe forward--compatibility with the quantum internet and quantum computing technologies.
We propose definitions and implementations of "S-money" - virtual tokens designed for high value fast transactions on networks with relativistic or other trusted signalling constraints, defined by inputs that in general are made at many network points, some or all of which may be space-like separated. We argue that one significant way of characterising types of money in space-time is via the "summoning" tasks they can solve: that is, how flexibly the money can be propagated to a desired space-time point in response to relevant information received at various space-time points. We show that S-money is more flexible than standard quantum or classical money in the sense that it can solve deterministic summoning tasks that they cannot. It requires the issuer and user to have networks of agents with classical data storage and communication, but no long term quantum state storage, and is feasible with current technology. User privacy can be incorporated by secure bit commitment and zero knowledge proof protocols. The level of privacy feasible in given scenarios depends on efficiency and composable security questions that remain to be systematically addressed.
Grover's algorithm confers on quantum computers a quadratic advantage over classical computers for searching in an arbitrary data set, a scenario that describes Bitcoin mining. It has previously been argued that the only side-effect of quantum mining would be an increased difficulty. In this work, we argue that a crucial argument in the analysis of Bitcoin security breaks down when quantum mining is performed. Classically, a Bitcoin fork occurs rarely, i.e., when two miners find a block almost simultaneously, due to propagation time effects. The situation differs dramatically when quantum miners use Grover's algorithm, which repeatedly applies a procedure called a Grover iteration. The chances of finding a block grow quadratically with the number of Grover iterations applied. Crucially, a miner does not have to choose how many iterations to apply in advance. Suppose Alice receives Bob's new block. To maximize her revenue, she should stop and measure her state immediately in the hopes that her block (rather than Bob's) will become part of the longest chain. The strong correlation between the miners' actions and the fact that they all measure their states at the same time may lead to more forks -- which is known to be a security risk for Bitcoin. We propose a mechanism that, we conjecture, will prevent this form of quantum mining, thereby circumventing the high rate of forks.
We propose a conceptual design for a quantum blockchain. Our method involves encoding the blockchain into a temporal GHZ (Greenberger-Horne-Zeilinger) state of photons that do not simultaneously coexist. It is shown that the entanglement in time, as opposed to an entanglement in space, provides the crucial quantum advantage. All the subcomponents of this system have already been shown to be experimentally realized. Furthermore, our encoding procedure can be interpreted as nonclassically influencing the past.
Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP , as long as one is willing to make a suitable physical assumption : if the provers are spatially isolated, then they can be assumed to be playing independent strategies. Quantum mechanics, however, tells us that this assumption is unrealistic, because spatially-isolated provers could share a quantum entangled state and realize a non-local correlated strategy. The MIP * model captures this setting. In this work, we study the following question: Does spatial isolation still suffice to unconditionally achieve zero knowledge even in the presence of quantum entanglement? We answer this question in the affirmative: we prove that every language in NEXP has a 2-prover zero knowledge interactive proof that is sound against entangled provers; that is, NEXP ⊆ ZK-MIP * . Our proof consists of constructing a zero knowledge interactive probabilistically checkable proof with a strong algebraic structure, and then lifting it to the MIP * model. This lifting relies on a new framework that builds on recent advances in low-degree testing against entangled strategies, and clearly separates classical and quantum tools. Our main technical contribution is the development of new algebraic techniques for obtaining unconditional zero knowledge; this includes a zero knowledge variant of the celebrated sumcheck protocol, a key building block in many probabilistic proof systems. A core component of our sumcheck protocol is a new algebraic commitment scheme, whose analysis relies on algebraic complexity theory.
Farid Ablayev, D. A. Bulychkov, D. A. Sapaev, Alexander Vasiliev · 5 authors
Bitcoin and blockchain in general is a hot topic nowadays. In the paper we propose a quantum empowering of this technology and show how to speed-up the mining procedure using the modified Grover's algorithm.
A decentralized online quantum cash system, called qBitcoin, is given. We design the system which has great benefits of quantization in the following sense. Firstly, quantum teleportation technology is used for coin transaction, which prevents from the owner of the coin keeping the original coin data even after sending the coin to another. This was a main problem in a classical circuit and a blockchain was introduced to solve this issue. In qBitcoin, the double-spending problem never happens and its security is guaranteed theoretically by virtue of quantum information theory. Making a block is time consuming and the system of qBitcoin is based on a quantum chain, instead of blocks. Therefore a payment can be completed much faster than Bitcoin. Moreover we employ quantum digital signature so that it naturally inherits properties of peer-to-peer (P2P) cash system as originally proposed in Bitcoin.
E O Kiktenko, N O Pozhar, M N Anufriev, A S Trushechkin · 8 authors
Abstract Blockchain is a distributed database which is cryptographically protected against malicious modifications. While promising for a wide range of applications, current blockchain platforms rely on digital signatures, which are vulnerable to attacks by means of quantum computers. The same, albeit to a lesser extent, applies to cryptographic hash functions that are used in preparing new blocks, so parties with access to quantum computation would have unfair advantage in procuring mining rewards. Here we propose a possible solution to the quantum era blockchain challenge and report an experimental realization of a quantum-safe blockchain platform that utilizes quantum key distribution across an urban fiber network for information-theoretically secure authentication. These results address important questions about realizability and scalability of quantum-safe blockchains for commercial and governmental applications.
The digital currency Bitcoin has had remarkable growth since it was first proposed in 2008. Its distributed nature allows currency transactions without a central authority by using cryptographic methods and a data structure called the blockchain. In this paper we use the no-cloning theorem of quantum mechanics to introduce Quantum Bitcoin, a Bitcoin-like currency that runs on a quantum computer. We show that our construction of quantum shards and two blockchains allows untrusted peers to mint quantum money without risking the integrity of the currency. The Quantum Bitcoin protocol has several advantages over classical Bitcoin, including immediate local verification of transactions. This is a major improvement since we no longer need the computationally intensive and time-consuming method Bitcoin uses to record all transactions in the blockchain. Instead, Quantum Bitcoin only records newly minted currency which drastically reduces the footprint and increases efficiency. We present formal security proofs for counterfeiting resistance and show that a quantum bitcoin can be re-used a large number of times before wearing out - just like ordinary coins and banknotes. Quantum Bitcoin is the first distributed quantum money system and we show that the lack of a paper trail implies full anonymity for the users. In addition, there are no transaction fees and the system can scale to any transaction volume.
Bit commitment is a fundamental cryptographic task that guarantees a secure commitment between two mutually mistrustful parties and is a building block for many cryptographic primitives, including coin tossing, zero-knowledge proofs, oblivious transfer and secure two-party computation. Unconditionally secure bit commitment was thought to be impossible until recent theoretical protocols that combine quantum mechanics and relativity were shown to elude previous impossibility proofs. Here we implement such a bit commitment protocol. In the experiment, the committer performs quantum measurements using two quantum key distribution systems and the results are transmitted via free-space optical communication to two agents separated with more than 20 km. The security of the protocol relies on the properties of quantum information and relativity theory. We show that, in each run of the experiment, a bit is successfully committed with less than 5.68*10^-2 cheating probability. Our result demonstrates unconditionally secure bit commitment and the experimental feasibility of relativistic quantum communication.