This thesis is the culmination of research conducted between 2019 and 2023. It is divided into three parts. Inthe first part, we explore algorithms related to the Covid-19 pandemic, such as Pool Testing, a well-establishedtechnique where samples from multiple patients are pooled for collective testing, allowing for cost reduction and time savings. We propose algorithms taking into account the a priori probabilities that individual tests are positive, which can be evaluated during a prior clinical examination of the patient. We also examine Pool Testingin emergency situations, where certain samples need to be analyzed according to some prescribed priority order. In both cases, we propose new algorithms and analyze them in detail. This section also deals with DNA privacy preservation in Covid-19 tests. In the second part, we present our results in experimental mathematics, where we have discovered several new conjectures on continued fractions through automated exploration. All those conjectures have been numerically tested to assess their plausibility. Finally, the third part of this thesis is devoted to various results in the field of computer security, such as a previously unknown attack on the Mathematica software, a new protection mechanism against counterfeit medication, and new observations on zero-knowledge proofs.
It is well-known that digital signatures can be constructed from one-way functions in a black-box way. While one-way functions are essentially the minimal assumption in classical cryptography, this is not the case in the quantum setting. A variety of qualitatively weaker and inherently quantum assumptions (e.g. EFI pairs, one-way state generators, and pseudorandom states) are known to be sufficient for non-trivial quantum cryptography. While it is known that commitments, zero-knowledge proofs, and even multiparty computation can be constructed from these assumptions, it has remained an open question whether the same is true for quantum digital signatures schemes (QDS). In this work, we show that there $\textit{does not}$ exist a black-box construction of a QDS scheme with classical signatures from pseudorandom states with linear, or greater, output length. Our result complements that of Morimae and Yamakawa (2022), who described a $\textit{one-time}$ secure QDS scheme with classical signatures, but left open the question of constructing a standard $\textit{multi-time}$ secure one.
Among the hot research topics, Fintech is leading the trend in terms of the newest technology applications. The relatively new emerging paradigms in various sciences, such as geometry (fractals), physics (quantum), and database systems (distributed ledgerâblockchain), seem to potentially contribute to a greater shift in the framework of the finance industry, bringing also some concerns (cyber-threats). Consistent and extensive investigation of the reasonable potential impact of these new models (and their underlying technologies) is performed, and then tested through a SWOT analysis, as the main objective of this research. This research confirms that information availability and the increasing interconnection of crosswise applications of each discovery to the different fields of science is determining the rapid succession of revolutions identified by evident large shifts in economic paradigms. The growing computing capacity and the development of increasingly powerful predictive software are leading to a competitive, extremely dynamic, and challenging system.
Marta Irene GarcĂa Cid, Dileepsai Bodanapu, Alberto Gatto, Paolo Martelli · 6 authors
A new interactive quantum zero-knowledge protocol for identity authentication implementable in currently available quantum cryptographic devices is proposed and demonstrated. The protocol design involves a verifier and a prover knowing a pre-shared secret, and the acceptance or rejection of the proof is determined by the quantum bit error rate. It has been implemented in modified Quantum Key Distribution devices executing two fundamental cases. In the first case, all players are honest, while in the second case, one of the users is a malicious player. We demonstrate an increase of the quantum bit error rate around 25% in the latter case compared to the case of honesty. The protocol has also been validated for distances from a back-to-back setup to more than 60 km between verifier and prover. The security and robustness of the protocol has been analysed, demonstrating its completeness, soundness and zero-knowledge properties.
Blockchain (BC) as a distributed ledger technology is getting more and more recognition in modern network technologies that are moving away from centralized toward decentralized management. However, the blockchainâs security is built on the computational complexity of certain mathematical problems that cannot be solved on existing âclassicalâ computers in an acceptable time. Nevertheless, quantum computers have the capability to effortlessly solve such problems with a significant reduction in time. The current blockchain technology relies on two main computational constructions; digital signatures and cryptographic hash functions. Both of them are threatened by the quantum computers. In this work, we report on the quantum threats to âclassicalâ blockchain technology. The main directions to produce quantum-resistant blockchain (QB) platforms are reviewed with an emphasis on approaches based on Quantum Key Distribution (QKD). Then, some notable challenges in implementing QBs are discussed. Indeed, the future research directions in this field are identified.
Marta Irene GarcĂa Cid, Dileepsai Bodanapu, Rodrigo MartĂn SĂĄnchez-Ledesma, Laura Ortiz MartĂn · 8 authors
This work presents a new scheme based on a quantum zero-knowledge proof for identity authentication. The novelty of this research is the migration of the classical concept Zero-knowledge into the quantum cryptographic framework that, to the best of our knowledge, has never been explored. This approach allows us to take advantage of the principles of quantum mechanics to build a protocol, which is secure against quantum computer attacks, for authenticating several users having access to the same network node. The protocol has been designed, its security analysed and implemented in modified Quantum Key Distribution devices. Two scenarios have been analysed experimentally, the first being both the prover and the verifier honest players, and the second case being the prover a malicious player, the latter demonstrating a notable increase in the quantum bit error rate that prevents a fraudulent authentication.
We show the following unconditional results on quantum commitments in two related yet different models: 1. We revisit the notion of quantum auxiliary-input commitments introduced by Chailloux, Kerenidis, and Rosgen (Comput. Complex. 2016) where both the committer and receiver take the same quantum state, which is determined by the security parameter, as quantum auxiliary inputs. We show that computationally-hiding and statistically-binding quantum auxiliary-input commitments exist unconditionally, i.e., without relying on any unproven assumption, while Chailloux et al. assumed a complexity-theoretic assumption, ${\bf QIP}\not\subseteq{\bf QMA}$. On the other hand, we observe that achieving both statistical hiding and statistical binding at the same time is impossible even in the quantum auxiliary-input setting. To the best of our knowledge, this is the first example of unconditionally proving computational security of any form of (classical or quantum) commitments for which statistical security is impossible. As intermediate steps toward our construction, we introduce and unconditionally construct post-quantum sparse pseudorandom distributions and quantum auxiliary-input EFI pairs which may be of independent interest. 2. We introduce a new model which we call the common reference quantum state (CRQS) model where both the committer and receiver take the same quantum state that is randomly sampled by an efficient setup algorithm. We unconditionally prove that there exist statistically hiding and statistically binding commitments in the CRQS model, circumventing the impossibility in the plain model. We also discuss their applications to zero-knowledge proofs, oblivious transfers, and multi-party computations.
Rakesh Saini, Abhiprada Bera, Bikash K. Behera, Emad A. Ahmed · 6 authors
The sixth-generation (6G) network utilizes state-of-the-art machine learning technology and obtains high attention, while the fifth-generation (5G) industry is still developing globally. Unfortunately, 6G encounters challenges to achieve performance superiority, such as scalability, massive connection, integrity, and trust. As a result, future network technologies are migrating away from centralized management entities and toward decentralized and distributed ledger technology, such as blockchain. However, the security of the blockchain is based on the computational complexity of solving specific mathematical problems that are impossible to solve on existing computers in real-time. On the other hand, quantum computers can effortlessly translate such problems with easy decryption. As a result, this study presents an architecture demonstrating the integration of quantum blockchain (QBC) with 6G networks. To show the quantum advantage, highly entangled/secured QBC of 5-, 6-, and 7-qubits are used to create the above systemâs quantum circuits. After circuit optimization, mitigation is executed with the efficiency analysis to show the advantage of the error mitigation approach in recreating the state of the QBC circuit and executing on quantum hardware. Furthermore, quantum algorithms of blockchain smart provenience contracts for the cloud-centric Internet of Things (IoT) are proposed, and corresponding quantum circuits are designed. The possible outcomes from these circuits based on the input transaction information are verified.
John Bostanci, Luowen Qian, Nicholas Spooner, Henry Yuen
We prove a tight parallel repetition theorem for $3$-message computationally-secure quantum interactive protocols between an efficient challenger and an efficient adversary. We also prove under plausible assumptions that the security of $4$-message computationally secure protocols does not generally decrease under parallel repetition. These mirror the classical results of Bellare, Impagliazzo, and Naor [BIN97]. Finally, we prove that all quantum argument systems can be generically compiled to an equivalent $3$-message argument system, mirroring the transformation for quantum proof systems [KW00, KKMV07]. As immediate applications, we show how to derive hardness amplification theorems for quantum bit commitment schemes (answering a question of Yan [Yan22]), EFI pairs (answering a question of Brakerski, Canetti, and Qian [BCQ23]), public-key quantum money schemes (answering a question of Aaronson and Christiano [AC13]), and quantum zero-knowledge argument systems. We also derive an XOR lemma [Yao82] for quantum predicates as a corollary.
Summary Secure twoâparty computation allows a pair of parties to compute a function together while keeping their inputs private. Ultimately, each party receives only its own correct output. In this paper, a postâquantum secure twoâparty computation protocol is proposed that can be used to effectively block malicious parties. The protocol solves the problems of traditional protocols based on garbled circuits, which are vulnerable to quantum attacks, high communication costs and low computational efficiency. The input garbled keys of the circuit constructor is structured as a Learning with Error (LWE) equation, enabling the circuit constructor to employ a zeroâknowledge proof that demonstrates the uniformity of inputs across all circuits.In the key transfer phase, an LWEâbased batch singleâchoice cutâandâchoose oblivious transfer is proposed to avoid selective failure attacks. In addition, the protocol employs a penalty mechanism to detect if the circuit constructor has generated an incorrect circuit. We have compared the communication overhead of this protocol with three other secure twoâparty computation protocols based on CutâandâChoose technology. The analytical results show that this protocol has the best error probability and is resilient to quantum attacks under the malicious adversary model. In addition, with appropriate parameters, the protocol is able to reduce its communication bandwidth by an average of 40.41%.
Ethereum is one of the most valuable blockchain networks in terms of the total monetary value locked in it, and arguably been the most active network where new blockchain innovations in research and applications are demonstrated. But, this also leads to such transactional networks being susceptible to a wide variety of threats and attacks in an attempt to gain unreasonable advantage or to undermine the value of the users. Even with the state-of-art classical ML algorithms, detecting such attacks is hard. This motivated us explore quantum machine learning algorithms that can probably be better for such hard problems. This paper proposes to improve phishing detection and performance of QML algorithms such as Quantum Support Vector Machine (QSVM) and Variational Quantum Classifier (VQC) by using a cascaded form of Quantum Random Access Coding (QRAC) encoding scheme. We present detailed ablation studies with other encoding strategies, and comparing with classical ML algorithms and quantum algorithms on simulators and real quantum hardware. For QSVM, we have tried two different implementations of QSVM - one using Kernel estimation using quantum circuits on universal quantum computers, and the other using annealers and for VQC, we benchmarked with different ansatzes with different entangling capacities. For both algorithms we tried different feature maps but consistently observe that QRAC-VQC gives 13% improvement and QRAC-QSVM gives 3% improvement over baselines. Overall we observe that QSVM gives least false negatives thus better at detecting phishing nodes even over classical state-of-art graph convolutional networks. Another important and interesting observation is that the performance of these QML algorithms does not drastically drop with currently available noisy hardware and is almost equal to simulator for a quantum device with high quantum volume or performance.
We present a simple quantum interactive proof (QIP) protocol using the quantum state teleportation (QST) and quantum energy teleportation (QET) protocols. QET is a technique that allows a receiver at a distance to extract the local energy by local operations and classical communication (LOCC), using the energy injected by the supplier as collateral. QET works for any local Hamiltonian with entanglement and, for our study, it is important that getting the ground state of a generic local Hamiltonian is quantum Merlin Arthur (QMA)-hard. The key motivations behind employing QET for these purposes are clarified. Firstly, in cases where a prover possesses the correct state and executes the appropriate operations, the verifier can effectively validate the presence of negative energy with a high probability (Completeness). Failure to select the appropriate operators or an incorrect state renders the verifier incapable of observing negative energy (Soundness). Importantly, the verifier solely observes a single qubit from the prover's transmitted state, while remaining oblivious to the prover's Hamiltonian and state (Zero-knowledge). Furthermore, the analysis is extended to distributed quantum interactive proofs, where we propose multiple solutions for the verification of each player's measurement. The complexity class of our protocol in the most general case belongs to QIP(3)=PSPACE, hence it provides a secure quantum authentication scheme that can be implemented in small quantum communication devices. It is straightforward to extend our protocol to Quantum Multi-Prover Interactive Proof (QMIP) systems, where the complexity is expected to be more powerful (PSPACE$\subset$QMIP=NEXPTIME). In our case, all provers share the ground state entanglement, hence it should belong to a more powerful complexity class QMIP$^*$.
Zhiguo Qu, Yunyi Meng, Bo Liu, Ghulam Muhammad · 5 authors
Security and privacy are issues that cannot be ignored when collecting and processing medical data in the Internet of Medical Things (IoMT). The blockchain technology is a decentralized ledger system that has diverse application scenarios in the medical field. The blockchain technology relies on traditional cryptography to ensure data integrity and verifiability, but the creation of quantum computing has made it possible to break traditional encryption and signature methods. Therefore, quantum blockchain can provide a higher level of security for handling medical data. This article innovatively designs a new medical data processing system based on quantum blockchain (QB-IMD). In QB-IMD, a quantum blockchain structure and a novel electronic medical record algorithm (QEMR) are proposed to ensure that the processed data is legitimate and tamper-proof. QEMR combines quantum signature and quantum identity authentication to avoid the potential security risks of digital signatures. In addition, through delegated computing by quantum cloud, medical diagnostic data can be computed without leaking to quantum cloud servers, thus protecting user privacy. Through mathematical proof, theoretical analysis, and simulation, it is demonstrated that our scheme can resist six attacks and is feasible to protect user privacy.
Abstract The rapid advancement of quantum computing has sparked a considerable increase in research attention to quantum technologies. These advances span fundamental theoretical inquiries into quantum information and the exploration of diverse applications arising from this evolving quantum computing paradigm. The scope of the related research is notably diverse. This paper consolidates and presents quantum computing research related to the financial sector. The finance applications considered in this study include portfolio optimization, fraud detection, and Monte Carlo methods for derivative pricing and risk calculation. In addition, we provide a comprehensive analysis of quantum computingâs applications and effects on blockchain technologies, particularly in relation to cryptocurrencies, which are central to financial technology research. As discussed in this study, quantum computing applications in finance are based on fundamental quantum physics principles and key quantum algorithms. This review aims to bridge the research gap between quantum computing and finance. We adopt a two-fold methodology, involving an analysis of quantum algorithms , followed by a discussion of their applications in specific financial contexts. Our study is based on an extensive review of online academic databases, search tools, online journal repositories, and whitepapers from 1952 to 2023, including CiteSeerX, DBLP, ResearchGate, Semantic Scholar, and scientific conference publications. We present state-of-the-art findings at the intersection of finance and quantum technology and highlight open research questions that will be valuable for industry practitioners and academicians as they shape future research agendas.
Ang Liu, XiuâBo Chen, Shengwei Xu, Zhuo Wang · 8 authors
Blockchain technology affords data integrity protection and building trust mechanisms in transactions for distributed networks, and, therefore, is seen as a promising revolutionary information technology. At the same time, the ongoing breakthrough in quantum computation technology contributes toward large-scale quantum computers, which might attack classic cryptography, seriously threatening the classic cryptography security currently employed in the blockchain. As a better alternative, a quantum blockchain has high expectations of being immune to quantum computing attacks perpetrated by quantum adversaries. Although several works have been presented, the problems of impracticality and inefficiency in quantum blockchain systems remain prominent and need to be addressed. First, this paper develops a quantum-secure blockchain (QSB) scheme by introducing a consensus mechanism-quantum proof of authority (QPoA) and an identity-based quantum signature (IQS)-wherein QPoA is used for new block generation and IQS is used for transaction signing and verification. Second, QPoA is developed by adopting a quantum voting protocol to achieve secure and efficient decentralization for the blockchain system, and a quantum random number generator (QRNG) is deployed for randomized leader node election to protect the blockchain system from centralized attacks like distributed denial of service (DDoS). Compared to previous work, our scheme is more practical and efficient without sacrificing security, greatly contributing to better addressing the challenges in the quantum era. Extensive security analysis demonstrates that our scheme provides better protection against quantum computing attacks than classic blockchains. Overall, our scheme presents a feasible solution for blockchain systems against quantum computing attacks through a quantum strategy, contributing toward quantum-secured blockchain in the quantum era.
Most currently used cryptographic tools for protecting data are based on certain computational assumptions, which makes them vulnerable with respect to technological and algorithmic developments, such as quantum computing. One existing option to counter this potential threat is quantum key distribution, whose security is based on the laws of quantum physics. Quantum key distribution is secure against unforeseen technological developments. A second approach is post-quantum cryptography, which is a set of cryptographic primitives that are believed to be secure even against attacks with both classical and quantum computing technologies. From this perspective, this study reviews recent progress in the deployment of the quantum-secured infrastructure based on quantum key distribution, post-quantum cryptography, and their combinations. Various directions in the further development of the full-stack quantum-secured infrastructure are also indicated. Distributed applications, such as blockchains and distributed ledgers, are also discussed.
Given that reliable cloud quantum computers are becoming closer to reality, the concept of delegation of quantum computations and its verifiability is of central interest. Many models have been proposed, each with specific strengths and weaknesses. Here, we put forth a new model where the client trusts only its classical processing, makes no computational assumptions, and interacts with a quantum server in a single round. In addition, during a set-up phase, the client specifies the size $n$ of the computation and receives an untrusted, off-the-shelf (OTS) quantum device that is used to report the outcome of a single measurement. We show how to delegate polynomial-time quantum computations in the OTS model. This also yields an interactive proof system for all of QMA, which, furthermore, we show can be accomplished in statistical zero-knowledge. This provides the first relativistic (one-round), two-prover zero-knowledge proof system for QMA. As a proof approach, we provide a new self-test for n EPR pairs using only constant-sized Pauli measurements, and show how it provides a new avenue for the use of simulatable codes for local Hamiltonian verification. Along the way, we also provide an enhanced version of a well-known stability result due to Gowers and Hatami and show how it completes a common argument used in self-testing.
No system entity within a contemporary distributed cyber system can be entirely trusted. Hence, the classic centralized trust management method cannot be directly applied to it. Blockchain technology is essential to achieving decentralized trust management, its consensus mechanism is useful in addressing large-scale data sharing and data consensus challenges. Herein, an n-party quantum detectable Byzantine agreement (DBA) based on the GHZ state to realize the data consensus in a quantum blockchain is proposed, considering the threat posed by the growth of quantum information technology on the traditional blockchain. Relying on the nonlocality of the GHZ state, the proposed protocol detects the honesty of nodes by allocating the entanglement resources between different nodes. The GHZ state is notably simpler to prepare than other multi-particle entangled states, thus reducing preparation consumption and increasing practicality. When the number of network nodes increases, the proposed protocol provides better scalability and stronger practicability than the current quantum DBA. In addition, the proposed protocol has the optimal fault-tolerant found and does not rely on any other presumptions. A consensus can be reached even when there are nâ2 traitors. The performance analysis confirms viability and effectiveness through exemplification. The security analysis also demonstrates that the quantum DBA protocol is unconditionally secure, effectively ensuring the security of data and realizing data consistency in the quantum blockchain.
Maximus Liu, Khadijeh Najafi, Michael Dubrovsky, Mikhail Y. Shalaginov
We devised a quantum-computer compatible proof-of-work cryptographic algorithm and verified it on superconducting quantum processors. The algorithm enables a noticeable speedup when executed on quantum hardware while it is still verifiable on classical computers.