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 technology has emerged as a cornerstone of se- cure online activities, leveraging an extensive array of cryp- tographic tools. This paper delves into an extensive survey of the current literature on post-quantum secure digital sig- natures, focusing on those with advanced, exotic features that play pivotal roles in the blockchain ecosystem. These signatures serve essential functions, including account man- agement,enhancing consensus efficiency,enabling scriptless blockchains, and fortifying user privacy. The term "exotic" in this context signifies signatures that transcend conven- tional properties such as unforgeability, introducing novel functionalities that redefine the blockchain landscape. Our exploration centers on several such exotic signatures, in- cluding multi-/aggregate, threshold, adaptor, blind, and ring signatures. These cryptographic innovations not only bolster security but also empower blockchain systems in unprece- dented ways.Within this comprehensive treatment of exotic signatures, we engage in discussions surrounding the pre- vailing challenges and chart promising avenues for future research within the post-quantum realm. As quantum threats loom ever closer, our aim is to catalyze further inquiry, facil- itating the broader accessibility of post-quantum cryptogra- phy. This, in turn, will fortify blockchain systems, preparing them to withstand the impending quantum era while fos- tering innovation and excellence in the field of blockchain security.
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.
Cryptocurrency mining processes always lead to a high energy consumption at considerably high production cost, which is nearly one-third of cryptocurrency (e.g. Bitcoin) price itself. As the core of mining process is based on SHA-256 cryptographic hashing function, by using the alternative quantum computers, hybrid quantum computers or more larger quantum computing devices like quantum annealers, it would be possible to reduce the mining energy consumption with a quantum hardware's low-energy-operation characteristics. Within this work we demonstrated the use of optimized quantum mining facilities which would replace the classical SHA-256 and high energy consuming classical hardware in near future.
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.
This paper delves into the crucial challenge of safeguarding data sensitivity and preventing security breaches, which can result in substantial losses, including significant financial costs and potential loss of lives. Notably, the United States faces the highest financial burden, with data breaches costing approximately USD 5.09 million. With the proliferation of Internet of Things (IoT) devices, enormous volumes of data are collected from diverse sources. However, the inherent limitations in computational power and memory of IoT devices render them susceptible targets for malicious attacks. This study focuses on fortifying the security of multimedia data, encompassing audio, video, and images, obtained from IoT devices. Cutting-edge technologies such as blockchain and quantum cryptography are explored as promising avenues to bolster multimedia security and preserve privacy. Quantum Key Distribution (QKD) emerges as an alternative to classical encryption and key distribution methods, offering heightened data security. Simultaneously, blockchain leverages hash functions to augment the overall security posture. By harnessing the principles of quantum mechanics, QKD facilitates secure key exchange between involved parties for data encryption and decryption. Additionally, the paper introduces innovative methodologies to enhance the security, privacy, and anonymity of IoT devices.
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.
Blockchain technology finds widespread application across various fields due to its key features such as immutability, reduced costs, decentralization, and transparency. The security of blockchain relies on elements like hashing, digital signatures, and cryptography. However, the emergence of quantum computers and supporting algorithms poses a threat to blockchain security. These quantum algorithms pose a significant threat to both public-key cryptography and hash functions, compelling the redesign of blockchain architectures. This paper investigates the status quo of the post-quantum, quantum-safe, or quantum-resistant cryptosystems within the framework of blockchain. This study starts with a fundamental overview of both blockchain and quantum computing, examining their reciprocal influence and evolution. Subsequently, a comprehensive literature review is conducted focusing on Post-Quantum Distributed Ledger Technology (PQDLT). This research emphasizes the practical implementation of these protocols and algorithms providing extensive comparisons of characteristics and performance. This work will help to foster further research at the intersection of post-quantum cryptography and blockchain systems and give prospective directions for future PQDLT researchers and developers.
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.
Sumit Chauhan, Vaghawan Prasad Ojha, Shantia Yarahmadian, David B. Carvalho
The advent of quantum computing has generated apprehensions regarding the viability and security of conventional cryptographic algorithms. These algorithms safeguard the decentralized trust built into the blockchain, which relies on decentralized cryptographic consensus, instead of a central authority. Simultaneously, quantum computing has also unveiled unprecedented possibilities, opportunities and risks in the realm of technology. The significance of this is that numerous sub-routines employed within the blockchain, such as consensus protocols, data transmission, storage, and communication, heavily depend on conventional cryptographic algorithms like Rivest-Shamir-Adleman (RSA) and Elliptic Curve Digital Signature Algorithm (ECDSA). However, these algorithms are susceptible to quantum algorithms, which have the potential to effectively compromise them once quantum computers with sufficient computational capabilities are developed. Blockchain, although primarily recognized for its association with cryptocurrencies, is essentially a decentralized and trustless distributed ledger system. Its purpose is to enable decentralized communication, coordination, and the attainment of desired objectives through consensus mechanisms. A notable illustration of this concept is a blockchain transaction. The advent of quantum computing poses a significant threat to the security of blockchain systems, as the asymmetric algorithms employed within their many components will likely become obsolete. This jeopardizes the integrity of the blockchain system, which underpins a multi-billion dollar economy reliant on its inherent transparency and safety. This paper seeks to present an overview of the various threats faced by blockchain systems, examine the potential of quantum algorithms in offering cryptographic signatures for these systems, and provide a broad perspective on how to protect blockchain systems from quantum threats by utilizing quantum algorithms for cryptographic signatures. This study enhances the comprehension of existing vulnerabilities in blockchain systems, specifically focusing on the potential risks posed by quantum computing. Additionally, it sheds light on the ongoing efforts within the industry and current research endeavors aimed at addressing these weaknesses.
Non-fungible tokens (NFTs) could potentially have a broader transformational effect than mere blockchain because they challenge the traditional notions of ownership and is, therefore, a more fundamental challenge to our established economic and social structures. This paper provides a systematic review of the NFT literature outlining the research opportunities for NFTs.
Driven by the wide adoption of distributed renewable energy sources (RES), peer-to-peer (P2P) regional energy trading models have emerged as a major service offering, where prosumers can participate directly in local transactions. However, this distributed approach may result in privacy risks since the malicious users might manipulate the user data to compromise the integrity of the entire trading market. In this study, we introduce a verifiable secure multi-party computation scheme for P2P regional energy trading. This scheme facilitates the market pricing and clearing process in a distributed computing context without a third-party authority. Furthermore, we develop a multi-party zero-knowledge proof algorithm by leveraging the multi-party computation paradigm. This algorithm ensures the integrity of trading computations by guaranteeing the correctness of both data and computational process. We conduct experiments to evaluate the performance of our scheme in terms of proof generation and validation time by varying the number of participants. The results highlight the feasibility of our scheme for real-world applications, while preserving the privacy and integrity of energy trading computations.