We put forth a new framework for building pairing-based non-interactive zero-knowledge (\(\mathsf {NIZK}\)) arguments for a wide class of algebraic languages, which are an extension of linear languages, containing disjunctions of linear languages and more. Our approach differs from the Groth-Sahai methodology, in that we rely on pairings to compile a \(\varSigma \)-protocol into a \(\mathsf {NIZK}\). Our framework enjoys a number of interesting features:
conceptual simplicity, parameters derive from the \(\varSigma \)-protocol;
proofs as short as resulting from the Fiat-Shamir heuristic applied to the underlying \(\varSigma \)-protocol;
fully adaptive soundness and perfect zero-knowledge in the common random string model with a single random group element as CRS;
yields simple and efficient two-round, public coin, publicly-verifiable perfect witness-indistinguishable (WI) arguments(ZAPs) in the plain model. To our knowledge, this is the first construction of two-rounds statistical witness-indistinguishable arguments from pairing assumptions.
We survey the state-of-the-art non-interactive zero-knowledge argument schemes and their applications in confidential transactions and private smart contracts on blockchain. The main goal of this paper is to serve as a reference for blockchain application developers in finding the most suitable scheme for a particular use case. We give an overview and compare the state-of-the-art protocols for confidential transactions and private smart contracts regarding the protection of the transaction graph and amounts, data and functionality. However, our main focus is on state-of-the-art zero-knowledge argument schemes. We briefly describe their backgrounds, proof lengths and computational complexities and discuss their cryptographic security models. Our focus is on seminal, otherwise notable and, especially, implemented methods that are ready to be applied in practice. We also survey the existing implementations of transforming computations into circuit representations required by those methods. We note that the existing schemes have different strengths and drawbacks regarding usability, setup, proof length and proving and verification costs.
As a kind of point-to-point distributed public ledger technology, blockchain has been widely concerned in recent years. The privacy protection of blockchain technology has always been the core issue of people's attention. In this paper, some existing solutions to the current problems of user identity and transaction privacy protection are surveyed, including coin mixing mechanism, zero knowledge proof, ring signature and other technologies. Secondly, five typical applications of privacy protection technology based on blockchain are proposed and analyzed, which are mainly divided into technology applications based on coin mixing protocol, encryption protocol, secure channel protocol and so on. Finally, in view of the shortages of the existing blockchain privacy protection technology, we explore future research challenges that need to be studied in order to preserve privacy in blockchain system, and looks forward to the future development direction.
Emerson B. Tomaz, José Cláudio do Nascimento, Abdelhakim Hafid, José Neuman de Souza
The advent of miniaturized mobile devices with wireless communication capability and integrated with biosensors has revolutionized healthcare systems. The devices can be used by individuals as wearable accessories to collect health data regularly. This type of medical assistance supported by mobile devices to monitor patients and offer health services remotely is known as mobile health (mHealth). Although mHealth provides many benefits and has become popular, it can pose severe privacy risks. Many features in mHealth are managed through a smartphone. Thus, one of the most worrying issues involves communication between the monitoring devices and the smartphone. When communication uses Bluetooth, it is standard for a device to be paired with the smartphone; but generally, it is not exclusively associated with a specific mHealth app. This characteristic can allow a data theft attack by a malicious app or fake data injection by an illegitimate device. To address this issue, we present an authentication scheme based on Non-Interactive Zero-Knowledge Proof that is lightweight enough to run on mHealth devices with minimal resources. Our scheme ensures that legitimate devices interact exclusively with the official mHealth application. To ensure the patient's privacy-preserving throughout the system, we address the issues of storing, managing, and sharing data using blockchain. Since there is no privacy in the standard blockchain, we present a scheme in which the health data transmitted, stored, or shared are protected by Attribute-Based Encryption. The outcome is a system with fine-grained access control, entirely managed by the patient, and an end-to-end privacy guarantee.
Incorporation of connected vehicle (CV) data into real-time traffic management systems presents a host of new challenges resulting from the current lack of data integrity and data privacy in traffic networks. Over the past few years, blockchain technologies have been inspiring extensive innovations in the transportation field. However, due to the transparency property, sensitive data stored on the blockchain would be accessible to anyone, resulting in a lack of privacy. In this paper, we propose a decentralized and location-aware architecture to address the data integrity along with the privacy-preserving issues in blockchain-based traffic management systems. Our proposed architecture integrates with permissioned and modular blockchain network and non-interactive zero-knowledge range proof (ZKRP) protocol. We develop the prototype system on the Hyperledger Fabric platform and Hyperledger Ursa cryptographic library. The performance results show that our approach is effective and feasible for real-time traffic management while preserving the data privacy requirements.
Lasse Herskind, Panagiota Katsikouli, Nicola Dragoni
Our transaction history in the current centralized banking system has the ability to reveal a lot of private information for each spender, both to the banking system itself, but also to those entities that surround it (e.g., governments, industry etc). Examples of leaking information constitute the amounts spent, the goods on which the amounts were spent, the spending locations and the users we exchange money with. This knowledge is powerful in the hands of those who have it, and can be used in multiple ways, not always to our benefit. Cryptocurrencies, such as the famous Bitcoin, were proposed as a means to address the limitations of centralized banking systems and to offer its users privacy with regards to their transactional data. In this work, we perform a systematic literature review on the realm of privacy for electronic currencies. We present the development of digital money from electronic cash to cryptocurrencies and focus on the techniques that are employed to enhance user-privacy. Furthermore, we present flaws of the current cryptocurrency systems, which reduce the privacy of the cryptocurrency users. Finally, we describe three research directions to enhance privacy for cryptocurrencies: transaction propagation mechanisms, succinct ZK proof systems without a trusted setup, and specialised trustless zero-knowledge proofs.
Data are becoming the cornerstone of many businesses and entire systems infrastructure. Intelligent Transportation Systems (ITS) are no different. The ability of intelligent vehicles and devices to acquire and share environmental measurements in the form of data is leading to the creation of smart services for the benefit of individuals. In this paper, we present a system architecture to promote the development of ITS using distributed ledgers and related technologies. Thanks to these, it becomes possible to create, store and share data generated by users through the sensors on their devices or vehicles, while on the move. We propose an architecture based on Distributed Ledger Technologies (DLTs) to offer features such as immutability, traceability and verifiability of data. IOTA, a promising DLT for IoT, is used together with Decentralized File Storages (DFSes) to store and certify data (and their related metadata) coming from vehicles or by the users' devices themselves (smartphones). Ethereum is then exploited as the smart contract platform that coordinates the data sharing through access control mechanisms. Privacy guarantees are provided by the usage of distributed key management systems and Zero Knowledge Proof. We provide experimental results of a testbed based on real traces, in order to understand if DLT and DFS technologies are ready to support complex services, such as those that pertain to ITS. Results clearly show that, while the viability of the proposal cannot be rejected, further work is needed on the responsiveness of DLT infrastructures.
Recently, application scenario of crowdsourcing IoT has covered to e-healthcare service, smart home, smart city, internet of vehicles due to the proliferation of smart devices such as smart mobile devices, smart wearable device, smart medical devices and smart furniture, etc. Patient's data collected by the smart devices send to the various remote medical servers. A group of medical professionals remote access patient data stored at the medical server database. Smart home users want to remote real-time access information of smart devices at home. All these operations need via wireless remote communication, which is suffering from various kinds of threat and attacks. Hence, there are a large number of multi-factor remote authentication and key agreement schemes designed for the application of crowdsourcing IoT. However, in most existing related multi-factor schemes, all factors for identity authentication only act as a parameter for encrypting the local secret key. In this paper, we propose a new secure remote multi-factor authentication scheme that includes three factors: 1) user identity; 2) password; and 3) user biometrics, which are authenticated by the remote server, act as a part of the secret key and participate in the key agreement process. We choose the chaotic map since it has a smaller key size and lower computational overhead, and then achieve remote multi-factor authentication and key agreement by artfully employ it to zero-knowledge technology and the fuzzy extractor technology. Our scheme is more secure and robust since the user revealing nothing sensitive information, and the adversary cannot impersonate any user even if he gets the server's master key. We have done security proof for our proposed scheme using the Random-Or-Real(ROR) model, Burrows-Abadi-Needham (BAN) logic, and ProVerif 2.00 to show that the presented scheme is secure. Also, we give an additional security analysis for other various attacks. Finally, according to the test and simulation result, the proposed scheme is very suitable for the power-constrained smart devices, and in the next generation 5G communication environment, its applicability and usability will be greatly enhanced.
The pool-hopping attack casts down the expected profits of both the mining pool and honest miners in Blockchain. The mainstream countermeasures, namely PPS (pay-per-share) and PPLNS (pay-per-last-N-share), can hedge pool hopping, but pose a risk to the pool as well as the cost to miners. In this study, we apply the zero-determinant (ZD) theory to design a novel pooled mining which offers an incentive mechanism for motivating non-memorial and memorial evolutionary miners not to switch in pools strategically. In short, our hopping-proof pooled mining has three unique features: 1) fee-free. No fee is charged if the miner does not hop. 2) wide applicability. It can be employed in both prepaid and postpaid mechanisms. 3) fairness. Even the pool can dominate the game with any miner, he has to cooperate when the miner does not hop among pools. The fairness of our scheme makes it have long-term sustainability. To the best of our knowledge, we are the first to propose a hopping-proof pooled mining with the above three natures simultaneously. Both theoretical and experimental analyses demonstrate the effectiveness of our scheme.
With the wide application of cloud storage, cloud security has become a crucial concern. Related works have addressed security issues such as data confidentiality and integrity, which ensure that the remotely stored data are well maintained by the cloud. However, how to define zero-knowledge proof algorithms for stored data integrity check has not been formally defined and investigated. We believe that it is important that the cloud server is unable to reveal any useful information about the stored data. In this paper, we introduce a novel definition of data privacy for integrity checks, which describes very high security of a zero-knowledge proof. We found that all other existing remote integrity proofs do not capture this feature. We provide a comprehensive study of data privacy and an integrity check algorithm that captures data integrity, confidentiality, privacy, and soundness.
We live in an era of information and it is very important to handle the exchange of information. While sending data to an authorized source, we need to protect it from unauthorized sources, changes, and authentication. ZKP technique can be used in designing secure authentication systems that dont involve any direct exchange of information between the claimant and the verifier thus preventing any possible leak of personal information. We propose a Zero-Knowledge Proof (ZKP) algorithm based on isomorphic graphs. We suggest most of the computations should be carried out on the users' web browser without revealing the password to the server at any point in time. Instead, it will generate random graphs and their permutations based on the login ID and password.
Abstract Recent studies show that 20.4% of the internet traffic originates from automated agents. To identify and block such ill-intentioned traffic, mechanisms that verify the humanness of the user are widely deployed, with CAPTCHAs being the most popular. Traditional CAPTCHAs require extra user effort (e.g., solving mathematical puzzles), which can severely downgrade the end-user’s experience, especially on mobile, and provide sporadic humanness verification of questionable accuracy. More recent solutions like Google’s reCAPTCHA v3, leverage user data, thus raising significant privacy concerns. To address these issues, we present zkSENSE: the first zero-knowledge proof-based humanness attestation system for mobile devices. zkSENSE moves the human attestation to the edge: onto the user’s very own device, where humanness of the user is assessed in a privacy-preserving and seamless manner. zkSENSE achieves this by classifying motion sensor outputs of the mobile device, based on a model trained by using both publicly available sensor data and data collected from a small group of volunteers. To ensure the integrity of the process, the classification result is enclosed in a zero-knowledge proof of humanness that can be safely shared with a remote server. We implement zkSENSE as an Android service to demonstrate its effectiveness and practicality. In our evaluation, we show that zkSENSE successfully verifies the humanness of a user across a variety of attacking scenarios and demonstrate 92% accuracy. On a two years old Samsung S9, zkSENSE’s attestation takes around 3 seconds (when visual CAPTCHAs need 9.8 seconds) and consumes a negligible amount of battery.
Recent studies show that 20.4% of the internet traffic originates from automated agents. To identify and block such ill-intentioned traffic, mechanisms that verify the humanness of the user are widely deployed across the internet. CAPTCHA is the most popular among such mechanisms. Original CAPTCHAs require extra user effort (e.g., solving mathematical or image-based puzzles), which severely harms user's experience, especially on mobile, and provide only sporadic verification of their humanness. More recent solutions like Google's reCAPTCHA v3 leverage attestation data (e.g., user behavioral data, device fingerprints) shared with a remote server, thus raising significant privacy concerns. To address all of the above, we present ZKSENSE: the first zero knowledge proof-based humanness attestation system designed for mobile devices. Contrary to state-of-the-art systems, ZKSENSE assesses humanness continuously on the background in a privacy preserving way. ZKSENSE achieves that by classifying the motion sensor outputs of the mobile device based on a model trained by using both publicly available sensor data and data collected from a small group of volunteers. The classification result is enclosed in a zero knowledge proof of humanness that can be safely shared with an attestation service such as Privacy Pass. We implement ZKSENSE as an Android service to demonstrate its effectiveness and practicability. In our evaluation, we show that ZKSENSE verifies the humanness of the users asynchronously, on the background, without degrading their experience or jeopardizing user privacy, while it achieves 91% accuracy across a variety of attack scenarios. On a two years old Samsung S9, each attestation takes around 3 seconds in total (when visual CAPTCHAs need 9.8 seconds) and consumes a negligible amount of battery.
We initiate the study of non-interactive zero-knowledge (NIZK) arguments for languages in QMA. Our first main result is the following: if Learning With Errors (LWE) is hard for quantum computers, then any language in QMA has an NIZK argument with preprocessing. The preprocessing in our argument system consists of (i) the generation of a CRS and (ii) a single (instance-independent) quantum message from verifier to prover. The instance-dependent phase of our argument system involves only a single classical message from prover to verifier. Importantly, verification in our protocol is entirely classical, and the verifier needs not have quantum memory; its only quantum actions are in the preprocessing phase. Our second contribution is to extend the notion of a classical proof of knowledge to the quantum setting. We introduce the notions of arguments and proofs of quantum knowledge (AoQK/PoQK), and we show that our non-interactive argument system satisfies the definition of an AoQK. In particular, we explicitly construct an extractor which can recover a quantum witness from any prover which is successful in our protocol. Finally, we show that any language in QMA has an (interactive) proof of quantum knowledge.
We provide several advances to the understanding of the class of Quantum Merlin-Arthur proof systems (QMA), the quantum analogue of NP. Our central contribution is proving a longstanding conjecture that the Consistency of Local Density Matrices (CLDM) problem is QMA-hard under Karp reductions. The input of CLDM consists of local reduced density matrices on sets of at most k qubits, and the problem asks if there is an n-qubit global quantum state that is locally consistent with all of the k-qubit local density matrices. The containment of this problem in QMA and the QMA-hardness under Turing reductions were proved by Liu [APPROX-RANDOM 2006]. Liu also conjectured that CLDM is QMA-hard under Karp reductions, which is desirable for applications, and we finally prove this conjecture. We establish this result using the techniques of simulatable codes of Grilo, Slofstra, and Yuen [FOCS 2019], simplifying their proofs and tailoring them to the context of OMA. In order to develop applications of CLDM, we propose a framework that we call locally simulatable proofs for QMA: this provides QMA proofs that can be efficiently verified by probing only k qubits and, furthermore, the reduced density matrix of any k-qubit subsystem of a good witness can be computed in polynomial time, independently of the witness. Within this framework, we show several advances in zero-knowledge in the quantum setting. We show for the first time a commit-and-open computational zero-knowledge proof system for all of QMA, as a quantum analogue of a “sigma” protocol. We then define a Proof of Quantum Knowledge, which guarantees that a prover is effectively in possession of a quantum witness in an interactive proof, and show that our zero-knowledge proof system satisfies this definition. Finally, we show that our proof system can be used to establish that QMA has a quantum non-interactive zero-knowledge proof system in the secret parameter setting.11The full version of this work can be found in https://arxiv.org/abs/1911.07782.
We provide several advances to the understanding of the class of Quantum Merlin-Arthur proof systems (QMA), the quantum analogue of NP. First, we answer a longstanding open question by showing that the Consistency of Local Density Matrices problem is QMA-complete under Karp reductions. We also show for the first time a commit-and-open computational zero-knowledge proof system for all of QMA as a quantum analogue of a sigma protocol. We then define a Proof of Quantum Knowledge, which guarantees that a prover is effectively in possession of a quantum witness in an interactive proof, and show that our zero-knowledge proof system satisfies this definition. Finally, we show that our proof system can be used to establish that QMA has a quantum non-interactive zero-knowledge proof system in the secret parameters setting.
Our main technique consists in developing locally simulatable proofs for all of QMA: this is an encoding of a QMA witness such that it can be efficiently verified by probing only five qubits and, furthermore, the reduced density matrix of any five-qubit subsystem can be computed in polynomial time and is independent of the witness. This construction follows the techniques of Grilo, Slofstra, and Yuen [FOCS 2019].
Wouter Lueks, Bogdan Kulynych, Jules Fasquelle, Simon Le Bail-Collet · 5 authors
Zero-knowledge proofs are an essential building block in many privacy-preserving systems. However, implementing these proofs is tedious and error-prone. In this paper, we present zksk, a well-documented Python library for defining and computing sigma protocols: the most popular class of zero-knowledge proofs. In zksk, proofs compose: programmers can convert smaller proofs into building blocks that then can be combined into bigger proofs. zksk features a modern Python-based domain-specific language. This makes possible to define proofs without learning a new custom language, and to benefit from the rich Python syntax and ecosystem. The library is available at https://github.com/spring-epfl/zksk
For an oscillator that is periodically swept in frequency between some upper and lower bound, the output amplitude may easily be made constant and therefore known with a high degree of certainty. The instantaneous frequency exists only at a point in time and therefore possesses a zero probability of existing at any point. This thesis deals with the development of a method for interchanging the probability density functions of amplitude and frequency so that the latter becomes known with certainty while the former is known only to the extent that it is within a certain range. The method developed makes practical the use of the fast tuned voltage controlled oscillator as the local oscillator in a frequency scanning superheterodyne receiver. Exact frequency is expressed by a digital word of finite bit length that, in actuality, expresses the value of a quantized amplitude variable whose quantized value represents a precise frequency. Because of the interrelationship of amplitude, frequency, and time through the Fourier Transform, functions of these variables are also interrelated suggesting the possibility that the original certainty of amplitude information may be traded with the original uncertainty of frequency information. The success of the method presented makes use of the precise knowledge of the frequencies of the sidebands generated by the angle modulation process rather than make direct use of the instantaneous frequency. After mathematical development, a design example addresses the actual frequency range in the microwave region where the scanning superheterodyne receiver finds military application. To demonstrate the concept of precise frequency control with words of finite length, a practical frequency model is designed and constructed by scaling megahertz to hertz. Extensive use is made of monolithic waveform generators, balanced mixers, and operational amplifiers used as active filters and time domain summers. All assemblies within the model have practical microwave counterparts. Time and frequency domain waveforms are observed at virtually every major point of the model corresponding to the functional block interfaces and are compared with the mathematical predictions. The ultimate goal of precise frequency selection as a function of an imprecise independent variable is also obtained with the aid of a spectrum analyzer and dual trace oscilloscope. The causes of less than optimum signal level separation of adjacent discrete frequencies are analyzed in a qualitative manner. Reasons for the ineffectiveness of a quantitative critique are also presented. Experimental results, however, are demonstrated proof of the feasibility of the concept of exchanging probability density functions of related variables and that refinement is the only ingredient missing to render the fast scan VCO a useful local oscillator.
Organized surveillance, especially by governments poses a major challenge to individual privacy, due to the resources governments have at their disposal, and the possibility of overreach. Given the impact of invasive monitoring, in most democratic countries, government surveillance is, in theory, monitored and subject to public oversight to guard against violations. In practice, there is a difficult fine balance between safeguarding individual's privacy rights and not diluting the efficacy of national security investigations, as exemplified by reports on government surveillance programs that have caused public controversy, and have been challenged by civil and privacy rights organizations. Surveillance is generally conducted through a mechanism where federal agencies obtain a warrant from a federal or state judge (e.g., the US FISA court, Supreme Court in Canada) to subpoena a company or service-provider (e.g., Google, Microsoft) for their customers' data. The courts provide annual statistics on the requests (accepted, rejected), while the companies provide annual transparency reports for public auditing. However, in practice, the statistical information provided by the courts and companies is at a very high level, generic, is released after-the-fact, and is inadequate for auditing the operations. Often this is attributed to the lack of scalable mechanisms for reporting and transparent auditing. In this paper, we present SAMPL, a novel auditing framework which leverages cryptographic mechanisms, such as zero knowledge proofs, Pedersen commitments, Merkle trees, and public ledgers to create a scalable mechanism for auditing electronic surveillance processes involving multiple actors. SAMPL is the first framework that can identify the actors (e.g., agencies and companies) that violate the purview of the court orders. We experimentally demonstrate the scalability for SAMPL for handling concurrent monitoring processes without undermining their secrecy and auditability.
Zero-knowledge arguments have become practical, and widely used, especially in the world of Blockchain, for example in Zcash. This work revisits zero-knowledge proofs in the discrete logarithm setting. First, we identify and carve out basic techniques (partly being used implicitly before) to optimise proofs in this setting. In particular, the linear combination of protocols is a useful tool to obtain zero-knowledge and/or reduce communication. With these techniques, we are able to devise zero-knowledge variants of the logarithmic communication arguments by Bootle et al. (EUROCRYPT '16) and Bünz et al. (S&P '18) thereby introducing almost no overhead. We then construct a conceptually simple commit-and-prove argument for satisfiability of a set of quadratic equations. Unlike previous work, we are not restricted to rank 1 constraint systems (R1CS). This is, to the best of our knowledge, the first work demonstrating that general quadratic constraints, not just R1CS, are a natural relation in the dlog (or ideal linear commitment) setting. This enables new possibilities for optimisation, as, eg., any degree n2 polynomial f(X) can now be "evaluated" with at most 2n quadratic constraints. Our protocols are modular. We easily construct an efficient, logarithmic size shuffle proof, which can be used in electronic voting. Additionally, we take a closer look at quantitative security measures, eg. the efficiency of an extractor. We formalise short-circuit extraction, which allows us to give tighter bounds on the efficiency of an extractor.
Recently, crowd sensing has been intensively researched, due to the rapid growth of sensor-integrated mobile devices. Crowd sensing is a participatory sensing service where a server gathers and analyzes sensing data submitted from mobile devices of lots of users. In crowd sensing, the user's anonymity is desired, since the server gathers sensitive data from the participants including their GPS locations and moving path. However, the anonymous data submission may compromise the trust of the sensing data, because anonymous users may submit inappropriate sensing data, but they cannot be traced. Therefore, as the system to achieve both anonymity and trust in crowd sensing, ARTSense has been proposed. In the system, the trust of the sensing data is assessed on the sensed environment, other users' sensing, and the reputation of the user, and furthermore the reputation of the user is anonymously managed on the feedback from the trust assessment for the data. However, the anonymous reputation system of ARTSense has the efficiency problem, i.e., the user needs to wait a random time after the data submission phase before requesting the reputation update, which causes the communication delay. In this paper, we propose an efficient anonymous reputation system for crowd sensing, which can be integrated to the trust assessment in ARTSense. In the proposed system, during the data submission, the reputation update is anonymously completed. This is because the server does not manage the reputation of each user, but each user manages his/her reputation in the user side, where the the validity of the reputation is ensured by a certificate and anonymously checked by zero-knowledge proofs. Therefore, the proposed system achieves the better efficiency with no delay.