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.
Blockchain technology realizes unforgeable and decentralized ledger by applying P2P network, cryptography and consensus mechanism over distributed network. Its security relies on all of these technologies. One of fundamental problem of the security of blockchain technology is compromise of underlying cryptographic algorithms. This paper shows the impact of compromise of underlying cryptography and the way to extend the validity of blockchain applying the long-term signature scheme which was standardized in ETSI. The long-term signature scheme assume the existence of centralized PKI and secure time-stamp service. In this paper, we propose a method to apply similar concept and data structure with de-centralized manner. Our scheme avoids hard-fork of original blockchain, in the case of compromise of hash function and provides smooth-fork in the case of compromise of digital signature scheme.
Gorjan Alagic, Yfke Dulek, Christian Schaffner, Florian Speelman
Fully-homomorphic encryption (FHE) enables computation on encrypted data while maintaining secrecy. Recent research has shown that such schemes exist even for quantum computation. Given the numerous applications of classical FHE (zero-knowledge proofs, secure two-party computation, obfuscation, etc.) it is reasonable to hope that quantum FHE (or QFHE) will lead to many new results in the quantum setting. However, a crucial ingredient in almost all applications of FHE is circuit verification. Classically, verification is performed by checking a transcript of the homomorphic computation. Quantumly, this strategy is impossible due to no-cloning. This leads to an important open question: can quantum computations be delegated and verified in a non-interactive manner? In this work, we answer this question in the affirmative, by constructing a scheme for QFHE with verification (vQFHE). Our scheme provides authenticated encryption, and enables arbitrary polynomial-time quantum computations without the need of interaction between client and server. Verification is almost entirely classical; for computations that start and end with classical states, it is completely classical. As a first application, we show how to construct quantum one-time programs from classical one-time programs and vQFHE.
The concept of a Turing machine has been well defined. It would be sufficient to show that Bitcoin uses a dual stack architecture that acts as a dual counter machine. Such systems have already been demonstrated as being Turing complete. We demonstrate that Bitcoin script is a minimal family of which λ and R are members. Further using the compositional product rule and the iteration rule we demonstrate that Bitcoin scripting is Turing complete with the limitations imposed on any realworld computer. This limitation is that there cannot be an infinite tape. Iterations can be simulated using an “unrolled” loop function with allocation to the “Alt” stack. As the product rule states that if A, B are machines, then A.B is also a machine. The iteration rule shows that if A is a machine then (A) is also a machine. Further the minimum power of A under which the observed square of the final configuration is blank. The consequence of these rules is that for every partial recursive function of in variables we can show that it can be evaluated by machine of the proposed family.
Bitcoin is a digital currency and payment system based on classical cryptographic technologies which works without a central administrator such as in traditional currencies. It has long been questioned what the impact of quantum computing would be on Bitcoin, and cryptocurrencies in general. Here, we analyse three primary directions that quantum computers might have an impact in: mining, security, and forks. We find that in the near-term the impact of quantum computers appear to be rather small for all three directions. The impact of quantum computers would require considerably larger number of qubits and breakthroughs in quantum algorithms to reverse existing hash functions.
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.
Broadbent Anne, Zhengfeng Ji, Song Fang, Watrous John
Prior work has established that all problems in NP admit classical zero-knowledge proof systems, and under reasonable hardness assumptions for quantum computations, these proof systems can be made secure against quantum attacks. We prove a result representing a further quantum generalization of this fact, which is that every problem in the complexity class QMA has a quantum zero-knowledge proof system. More specifically, assuming the existence of an unconditionally binding and quantum computationally concealing commitment scheme, we prove that every problem in the complexity class QMA has a quantum interactive proof system that is zero-knowledge with respect to efficient quantum computations. Our QMA proof system is sound against arbitrary quantum provers, but only requires an honest prover to perform polynomial-time quantum computations, provided that it holds a quantum witness for a given instance of the QMA problem under consideration. The proof system relies on a new variant of the QMA-complete local Hamiltonian problem in which the local terms are described by Clifford operations and standard basis measurements. We believe that the QMA-completeness of this problem may have other uses in quantum complexity.
Kriptovalute su digitalni novac utemeljen na kriptografiji i decentraliziranom sustavu. Postoje samo u elektroničkom obliku kao jedinstveni digitalni novčići ("tokeni"). Iza njih ne stoji autoritet države niti ih je moguće svojevoljno proizvesti. Rad se fokusira na značajkama, postavkama, razvoju i svim međuodnosima važnih ekonomskih faktora koji utječu na kriptovalute. U prvom poglavlju navedena su obilježja kriptovaluta. Drugo poglavlje daje primjere i govori o primjeni kriptovaluta u svakodnevnom životu. U trećem poglavlju je raspravljano o trenutnim i budućim regulacijama najmoćnijih zemalja svijeta (G20) , kao i njihovoj zajedničkoj suradnji u želji za jedinstvenim i standardiziranim pravilima, a sve u svrhu što kvalitetnijeg nadzora nad kriptovalutama kako bi se spriječile malverzacije i zaštitili potrošači. Četvrto poglavlje govori o inicijalnoj ponudi kovanica, a peto poglavlje je namijenjeno sigurnosti kriptovaluta. Cilj istraživanja je utvrditi koliko je studentska populacija upoznata i usmjerena prema novim oblicima digitalnog novca, koje značajke kriptovaluta smatraju pozitivnima, a koje negativnima i u kojoj su mjeri investirali ili su spremni investirati dio svojih ulaganja u kriptovalute i sl. Metode istraživanja korištene u radu su kompilacija na temelju proučavanja postojeće literature o temi rada, prikupljanje i analiza podataka vezanih uz kriptovalute, ponajprije podataka vezanih uz cijene i tržišnu kapitalizaciju, anketiranje studenata Ekonomskog fakulteta u Rijeci i metoda dedukcije putem koje su pokazane sve važne karakteristike i obilježja kriptovaluta. Na temelju provedene ankete u kojoj je sudjelovalo 90 studenata Ekonomskog fakulteta u Rijeci zaključak toga dijela istraživanja je da je mlada populacija dobro upoznata s kriptovalutama i njenim glavnim značajkama, ali i određenim nedostatkom informiranosti o tehnologiji (trećina studenata nije čula za pojam "blockchain") i nedovoljnoj odlučnosti oko investiranja i trgovanja u kriptovalute. Povrh toga, dokazan je i negativan utjecaj hakerskih napada i određenih kriminalnih radnji, kao i nestabilnost tržišne cijene na povjerenje studenata, ali i ukupne populacije vezane uz globalni financijski sustav u kriptovalute. Ishod istraživanja omogućio je da zaključimo kako su kriptovalute trenutno u ranoj fazi razvoja i nisu se dovoljno implementirale za široku primjenu u trgovini roba i usluga ili općenito kao sredstvo razmjene. Faktor koji je uključen u istraživanje kako bi opisao veličinu, odnosno obujam neke kriptovalute je tržišna kapitalizacija u dolarima. Temeljna ideja ovog rada je informirati čitatelja o pozitivnim i negativnim značajkama koje se se vežu uz kriptovalute. Na taj način čitatelji će biti bolje informirani i educirani o potencijalnom riziku ulaganja u kriptovalute, kao i većoj razini zaštite prilikom posjedovanja neke digitalne valute.
We present a new definition of computationally binding commitment schemes in the quantum setting, which we call “collapse-binding”. The definition applies to string commitments, composes in parallel, and works well with rewindingbased proofs. We give simple constructions of collapse-binding commitments in the random oracle model, giving evidence that they can be realized from hash functions like SHA-3. We evidence the usefulness of our definition by constructing three-round statistical zero-knowledge quantum arguments of knowledge for all NP languages.
Quantum zero-knowledge proofs and quantum proofs of knowledge are inherently difficult to analyze because their security analysis uses rewinding. Certain cases of quantum rewinding are handled by the results by Watrous (SIAM J Comput, 2009) and Unruh (Eurocrypt 2012), yet in general the problem remains elusive. We show that this is not only due to a lack of proof techniques: relative to an oracle, we show that classically secure proofs and proofs of knowledge are insecure in the quantum setting. More specifically, sigma-protocols, the Fiat-Shamir construction, and Fischlin's proof system are quantum insecure under assumptions that are sufficient for classical security. Additionally, we show that for similar reasons, computationally binding commitments provide almost no security guarantees in a quantum setting. To show these results, we develop the "pick-one trick", a general technique that allows an adversary to find one value satisfying a given predicate, but not two.
Watrous (STOC 2006) proved that plugging classical bit commitment scheme that is secure against quantum attack into the GMW-type construction of zero-knowledge gives a classical zero-knowledge proof that is secure against quantum attack. In this paper, we showed that plugging quantum bit commitment scheme (allowing quantum computation and communication) into the GMW-type construction also gives a quantum zero-knowledge proof, as one expects. However, since the binding condition of quantum bit commitment scheme is inherently different from its classical counterpart, compared with Watrous ’ security proof, here we encounter new difficulty in soundness analysis. To overcome the difficulty, we take a geometric approach, managing to reduce quantum soundness analysis to classical soundness analysis. We also propose a formalization of non-interactive quantum bit commitment scheme, which may come in handy in other places. Moreover, inspired by our formalization, we generalize Naor’s construction of bit commitment scheme to the quantum setting, achieving non-interactive commit stage. We hope quantum bit commitment scheme can find more applications in quantum cryptog-raphy. 1
In the paper, we present a kind of quantum voting protocol, which is based on controlled quantum teleportation of local unitary operations in non-symmetric quantum channel. In this protocol, the umpire CA with zero knowledge proof quantum identity authentication ensures voter’s anonymous identity authentication. The counting institution Bob generates a high-dimensional Greenberger-Horne-Zeilinger entangled state to establish a high-dimensional quantum communication channel. Performing the local unitary operation on their low-dimensional quantum ballot, voter’s quantum vote is teleportated by asymmetric matrix measurement and scrutineer Charlie auxiliary measuring. With the scrutineer Charlie’s help, Bob achieves the voting result by the output of unitary operation. Compared with other general quantum operation teleportation quantum voting protocol, the protocol utilizes the quantum information and transmission of quantum channel, which have different dimensions, so single particle information cannot be stolen, and can prevent forgery. The electoral process is fair and undeniable, owing to Charlie’s supervision. Since the success probability of quantum teleportation of local unitary operations is 1, the quantum voting is reliable.
Xiao Qiang Guo, Li Hong Li, Cui Ling Luo, Yi Shuo Shi
The Bit Commitment (BC) is an important basic agreement in cryptography . The concept was first proposed by the winner of the Turing Award in 1995 ManuelBlum. Bit commitment scheme can be used to build up zero knowledge proof, verified secret sharing, throwing coins etc agreement.Simultaneously and Oblivious Transfer together constitute the basis of secure multi-party computations. Both of them are hotspots in the field of information security. We investigated unconditional secure Quantum Bit Commitment (QBC) existence. And we constructed a new bit commitment model – double prover bit commitment. The Quantum Bit Commitment Protocol can be resistant to errors caused by noise.
We propose a coin-flip protocol which yields a string of strong, random coins and is fully simulatable against poly-sized quantum adversaries on both sides. It can be implemented with quantum-computational security without any set-up assumptions, since our construction only assumes mixed commitment schemes which we show how to construct in the given setting. We then show that the interactive generation of random coins at the beginning or during outer protocols allows for quantum-secure realizations of classical schemes, again without any set-up assumptions. As example applications we discuss quantum zero-knowledge proofs of knowledge and quantum-secure two-party function evaluation. Both applications assume only fully simulatable coin-flipping and mixed commitments. Since our framework allows to construct fully simulatable coin-flipping from mixed commitments, this in particular shows that mixed commitments are complete for quantum-secure two-party function evaluation. This seems to be the first completeness result for quantum-secure two-party function evaluation from a generic assumption.