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.
We put forward the idea that classical blockchains and smart contracts are potentially useful primitives not only for classical cryptography, but for quantum cryptography as well. Abstractly, a smart contract is a functionality that allows parties to deposit funds, and release them upon fulfillment of algorithmically checkable conditions, and can thus be employed as a formal tool to enforce monetary incentives. In this work, we give the first example of the use of smart contracts in a quantum setting. We describe a simple hybrid classical-quantum payment system whose main ingredients are a classical blockchain capable of handling stateful smart contracts, and quantum lightning, a strengthening of public-key quantum money introduced by Zhandry (Eurocrypt'19). Our hybrid payment system employs quantum states as banknotes and a classical blockchain to settle disputes and to keep track of the valid serial numbers. It has several desirable properties: it is decentralized, requiring no trust in any single entity; payments are as quick as quantum communication, regardless of the total number of users; when a quantum banknote is damaged or lost, the rightful owner can recover the lost value.
As a promising direction of cryptography, the feasibility of quantum key distribution has been widely verified. However, the bottle-neck problems encountered by quantum key distribution network, such as concurrent conflict of large-scale quantum relay links, relay delay and inconvenient access to applications, are still not solved completely. In order to solve these problems, a quantum relay blockchain scheme is proposed in this paper. In the scheme, each relay node in a target network negotiates a quantum key with everyone of its adjacent nodes respectively, and calculates the XOR values of any two quantum keys from these quantum keys, then encapsulates these XOR values into a transaction. A server encapsulates all the current transactions into a block based on which real-time quantum key services can be realized. Furthermore, the scheme can be easily employed to realize quantum key service in cloud platforms with unconditional security and high efficiency. The scheme, which can be used to overcome the bottle-neck of quantum key distribution network, will play a critical role in future world-wide quantum key service.
The field of post-quantum cryptography studies cryptographic systems that are secure against an adversary in possession of a quantum computer. In 2017, the National Institute of Standards and Technology (NIST) initiated a process to standardize quantum-resistant public-key cryptographic algorithms (NIST PQC Project). In this thesis we analyze the performance and security of the Bit-Flipping Key Encapsulation Mechanism (BIKE) -- one of the candidates in the NIST PQC project which advanced to the second round of the standardization process. BIKE is a code-based cryptographic system featuring three different variants of the protocol. In the first round of the NIST PQC project BIKE offered security only against chosen-plaintext attacks (CPA). In the second round, BIKE introduced three new variants that are claimed to be secure also against chosen-ciphertext attacks (CCA). Firstly, we build a secure implementation of the CCA protocol and show that its performance characteristics are only negligibly worse than the CPA variant. In the key decapsulation phase of the protocol BIKE uses a decoding algorithm which fails with some probability, called the Decoding Failure Rate (DFR). We analyze the DFR of two decoders used in BIKE, Back-Flip and Black-Gray, and propose a new decoder, called Black-Gray-Flip, that achieves the same DFR as the two previously used decoders while being almost twice as fast. Finally, we propose an algorithm for inversion of binary polynomials in a polynomial ring used in BIKE-2, the second variant of BIKE. Our implementation of the inversion significantly outperforms previously used algorithms. With this and the fact that the bandwidth requirement for BIKE-2 is the smallest among the three variants, BIKE-2 is positioned as the preferable variant of BIKE. The second part of this thesis studies the Legendre pseudorandom function (PRF) which is proposed to be used in the context of blockchains. We present a new algorithm for cryptanalysis of the Legendre PRF. The complexity of our algorithm is lower than the previous best known algorithm. Moreover, we show the results of breaking three Legendre PRF challenges posed by the Ethereum foundation. The most difficult challenge that we solved set the new record which is not broken so far.
James Bartusek, Andrea Coladangelo, Dakshita Khurana, Fermi Ma
We investigate the round complexity of maliciously-secure two-party quantum computation (2PQC) with setup, and obtain the following results:
- A three-message protocol (two-message if only one party receives output) in the common random string (CRS) model assuming classical two-message oblivious transfer (OT) with post-quantum malicious security. This round complexity is optimal for the sequential communication setting. Under the additional assumption of reusable malicious designated-verifier non-interactive zero-knowledge (MDV-NIZK) arguments for NP, our techniques give an MDV-NIZK for QMA. Each of the assumptions mentioned above is known from the quantum hardness of learning with errors (QLWE).
- A protocol with two simultaneous rounds of communication, in a quantum preprocessing model, assuming sub-exponential QLWE. In fact, we construct a three-round protocol in the CRS model with only two rounds of online communication, which implies the above result. Along the way, we develop a new delayed technique that we call simulation via teleportation, which may be useful in other settings.
In addition, we perform a preliminary investigation into barriers and possible approaches for two-round 2PQC in the CRS model, including an impossibility result for a natural class of simulators, and a proof-of-concept construction from a strong form of quantum virtual black-box (VBB) obfuscation.
Prior to our work, maliciously-secure 2PQC required round complexity linear in the size of the quantum circuit.
Electronic voting solutions are built on complex cryptographic tools to guarantee security and fairness. Currently, those tools are based on hardness assumptions of discrete logarithm, factorization and other classical problems. While they are hard to break in classical computers, there are efficient quantum algorithms to solve using quantum computers of the near future. Thus, there is a need to develop voting protocols that are resistant to quantum attacks. Verifiable shuffling based voting systems are a popular use-case of mix-networks first proposed by Chaum four decades ago [Cha81] as a general tool for building anonymous communication systems. A decade later the quantum threat was known and since then only a few studies searched for post-quantum secure mix-nets. Recently, Costa, Martinez and Morillo introduced new arguments of shuffle for RLWE ciphertexts and how to prove the correctness of the shuffling without leaking sensitive info [CMM17]. In this thesis, we provide exact, shorter proof of Costa et al.’s lattice-based shuffling arguments. As a result, we obtain a practical non-interactive zero-knowledge proof having a runtime of 1 second per voter.
Cryptocurrencies are more than a decade old and several issues have been discovered since their then. One of these issues is a partial negation of the intent to “democratize” money by decentralizing control of the infrastructure that creates, transmits, and stores monetary data. The Programmatic Proof of Work (ProgPoW) algorithm is intended as a possible solution to this problem for the Ethereum cryptocurrency. This paper examines ProgPow’s claim to be Application Specific Integrated Circuit (ASIC) resistant. This is achieved by isolating the proof-of-work code from the Ethereum blockchain, inserting the ProgPoW algorithm, and measuring the performance of the new implementation as a multithread CPU program, as well as a GPU implementation. The most remarkable difference between the ProgPoW algorithm and the currently implemented Ethereum Proof-of Work is the addition of a random sequence of math operations in the main loop that require increased memory bandwidth. Analyzing and comparing the performance of the CPU and GPU implementations should provide an insight into how the ProgPoW algorithm might perform on an ASIC.
We propose a quantum assisted secure distributed ledger system that is client centric and polyvalent. The multiple attribute lock encryption (MALE) provides asymmetric key encryption to protect the data. The keys are of high randomness as they are generated via the simulation of a quantum walk. Quantum random walkers on a circle structure have been shown to be an efficient pseudo-random number generator. On top of the quantum random walker, we apply the quantum key distribution (QKD) protocol to avoid the double spending problem and to serve as a seed provider for the quantum walk. We further design the key chain update protocol with the help of MALE mechanism after each data access. Both QKD and quantum random walker can be efficiently simulated with current classical computation and near-term quantum technologies. Potential applications of proposed work in smart-city context are briefly discussed as well.
In a cryptocurrency network such as Bitcoin or Helium, the fundamental unit of interaction is a transaction where value is transferred from one entity to another. In this type of network, the blockchain is an immutable, distributed ledger of all of the transactions that have transpired on the network. Value is transferred from one public address to another public address. We can examine and enumerate all of the transactions associated with a public address by scanning the entire blockchain for transactions that involve this address. In fact, if we scan the blockchain forward from the genesis block, then the last transaction involving this address also provides the cryptocurrency balance which is associated with this address.
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
Emanuele Bellini, Philippe Gaborit, Alexandros Hasikos, Víctor Mateu
The advent of quantum computers is a threat to most currently deployed cryptographic primitives. Among these, zero-knowledge proofs play an important role, due to their numerous applications. The primitives and protocols presented in this work base their security on the difficulty of solving the Rank Syndrome Decoding (RSD) problem. This problem is believed to be hard even in the quantum model. We first present a perfectly binding commitment scheme. Using this scheme, we are able to build an interactive zero-knowledge proof to prove: the knowledge of a valid opening of a committed value, and that the valid openings of three committed values satisfy a given linear relation, and, more generally, any bitwise relation. With the above protocols it becomes possible to prove the relation of two committed values for an arbitrary circuit, with quasi-linear communication complexity and a soundness error of 2/3. To our knowledge, this is the first quantum resistant zero-knowledge protocol for arbitrary circuits based on the RSD problem. An important contribution of this work is the selection of a set of parameters, and an a full implementation, both for our proposal in the rank metric and for the original LPN based one by Jain et al. in the Hamming metric, from which we took the inspiration. Beside demonstrating the practicality of both constructions, we provide evidence of the convenience of rank metric, by reporting performance benchmarks and a detailed comparison.
Vadim Lyubashevsky, Ngoc Khanh Nguyen, Gregor Seiler
We present a novel lattice-based zero-knowledge proof system for showing that (arbitrary-sized) committed integers satisfy additive and multiplicative relationships. The proof sizes of our schemes are between two to three orders of magnitude smaller than in the lattice proof system of Libert et al. (CRYPTO 2018) for the same relations. Because the proof sizes of our protocols grow linearly in the integer length, our proofs will eventually be longer than those produced by quantum-safe succinct proof systems for general circuits (e.g. Ligero, Aurora, etc.). But for relations between reasonably-sized integers (e.g. $512$-bit), our proofs still result in the smallest zero-knowledge proof system based on a quantum-safe assumption. Of equal importance, the run-time of our proof system is at least an order of magnitude faster than any other quantum-safe scheme.
Current permissionless cryptocurrencies such as Bitcoin suffer from a limited transaction rate and slow confirmation time, which hinders further adoption. Payment channels are one of the most promising solutions to address these problems, as they allow the parties of the channel to perform arbitrarily many payments in a peer-to-peer fashion while uploading only two transactions on the blockchain. This concept has been generalized into payment channel networks where a path of payment channels is used to settle the payment between two users that might not share a direct channel between them. However, this approach requires the active involvement of each user in the path, making the system less reliable (they might be offline), more expensive (they charge fees per payment), and slower (intermediaries need to be actively involved in the payment). To mitigate this issue, recent work has introduced the concept of virtual channels (IEEE S&P’19), which involve intermediaries only in the initial creation of a bridge between payer and payee, who can later on independently perform arbitrarily many off-chain transactions. Unfortunately, existing constructions are only available for Ethereum, as they rely on its account model and Turing-complete scripting language. The realization of virtual channels in other blockchain technologies with limited scripting capabilities, like Bitcoin, was so far considered an open challenge.In this work, we present the first virtual channel protocols that are built on the UTXO-model and require a scripting language supporting only a digital signature scheme and a timelock functionality, being thus backward compatible with virtually every cryptocurrency, including Bitcoin. We formalize the security properties of virtual channels as an ideal functionality in the Universal Composability framework and prove that our protocol constitutes a secure realization thereof. We have prototyped and evaluated our protocol on the Bitcoin blockchain, demonstrating its efficiency: for n sequential payments, they require an off-chain exchange of 9+2n transactions or a total of 3524+695n bytes, with no on-chain footprint in the optimistic case. This is a substantial improvement compared to routing payments in a payment channel network, which requires 8n transactions with a total of 3026n bytes to be exchanged.
Blockchain and other Distributed Ledger Technologies (DLTs) have evolved significantly in the last years and their use has been suggested for numerous applications due to their ability to provide transparency, redundancy and accountability. In the case of blockchain, such characteristics are provided through public-key cryptography and hash functions. However, the fast progress of quantum computing has opened the possibility of performing attacks based on Grover's and Shor's algorithms in the near future. Such algorithms threaten both public-key cryptography and hash functions, forcing to redesign blockchains to make use of cryptosystems that withstand quantum attacks, thus creating which are known as post-quantum, quantum-proof, quantum-safe or quantum-resistant cryptosystems. For such a purpose, this article first studies current state of the art on post-quantum cryptosystems and how they can be applied to blockchains and DLTs. Moreover, the most relevant post-quantum blockchain systems are studied, as well as their main challenges. Furthermore, extensive comparisons are provided on the characteristics and performance of the most promising post-quantum public-key encryption and digital signature schemes for blockchains. Thus, this article seeks to provide a broad view and useful guidelines on post-quantum blockchain security to future blockchain researchers and developers.
Blockchain technology has gained immense popularity in the recent years due to its decentralized computing architecture. While it originally emerged as a technology for (crypto)currencies, it has since found many different application areas including (but not limited to) payments, money transfers, smart contracts, supply-chain management, networking, IoT, etc. Initially, it was only Bitcoin, the de facto standard for cryptocurrencies, but then it was followed by several (in fact hundreds of) others. Each new cryptocurrency had or claimed to have certain advantages over Bitcoin, such as transaction speed and cost. However, they all relied on the original idea of distributed ledger where each block has maintained a complete history of each transaction in the network. Blockchain technology has more recently been challenged by two new technologies called Tangle and Hashgraph, which are “directed acyclic graphs”, i.e. in layman's terms blockchains without blocks and chains. IOTA network is the original Tangle technology, which relies on ternary arithmetic architecture and uses ternary hash function “Troika”. It works on GF(3) and its design follows the sponge construction. Two of the main claims of IOTA are scalability and micro-transitions, both of which are likely to utilize compact hardware platforms in practical implementations. In this paper, an almost-zero logic compact and yet adequately fast hardware architectures of Troika hash function targeting reconfigurable devices are presented. The proposed architectures mainly depend on the utilization of BRAMs on FPGAs. Three different RAM-based hardware implementations have been realized on Xilinx Artix-7xc7a12tcpg238-3 device; all using only a single BRAM tile with minimal number of LUTs and FFs. The proposed architectures can easily be implemented on different reconfigurable devices with similar efficiency. To the best of our knowledge, this is the first reported hardware implementation of Troika hash function on reconfigurable devices which is also compact and fast.
Physical Unclonable Functions (PUFs) and Hardware Security
In this paper, we propose a novel consensus mechanism utilizing the quantum properties of qubits. This move from classical computing to quantum computing is shown to theoretically enhance the scalability and speed of distributed consensus as well as improve security and be a potential solution for the problem of blockchain interoperability. Using this method may circumvent the common problem known as the Blockchain Trilemma, enhancing scalability and speed without sacrificing de-centralization or byzantine fault tolerance [1]. Consensus speed and scalability is shown by removing the need for multicast responses and exploiting quantum properties to ensure that only a single multicast is required. We also leverage work done on the E91 quantum key distribution protocol [2] to securely transmit values and prevent a man-in-the-middle attack or system disturbance, enhancing confidentiality and integrity of transmitted information. Distributed ledger interoperability is explored by proposing a system to achieve a verifiable bridge for private transactions between a small private network and its corresponding consortium network. A proof-of-concept using IBM’s Qskit is shown from which initial results appear to show a strong sensitivity to non-consensus which could be useful in many applications. The present practical feasibility of the above is shown and future work is explored.