Data provenance to maintain data integrity and authenticity is a significant challenge in the Internet of Things (IoT) environments. Additionally, if the provenance metadata itself can be communicated in a privacy-preserving manner, it expands the usage of IoT systems to human societal domains where privacy is of paramount importance. In this paper, we present a scheme to combine data provenance and privacy-preserving solutions. Our scheme merges Physical Unclonable Function (PUF) technology with non-interactive zero-knowledge proof to provide trustworthy and dependable IoT systems. In this context, the IoT device can anonymously send data to the corresponding server associated with the proof of ownership. First, we propose a privacy-preserving data provenance protocol. This protocol was synthesized with Altera Quartus. It was implemented on an Altera Cyclone IV FPGA to demonstrate its practicality and feasibility. Most of the protocol steps take time of the order of 40u sec establishing its practicality.
Physical Unclonable Functions (PUFs) and Hardware Security
The Internet of things (IoT), as an extension of the Internet, has become a trend of network development nowadays. In order to protect the integrity and authenticity of the information in the IoT, an identity authentication protocol applied to the networked devices is designed in this paper, using the physical unclonable function (PUF) to extract the uniqueness and tamper resistance of the randomness in the manufacturing process of the physical device. We propose the protocol including the database, accessed devices, access devices and users in the specific network environment. Relying on the unique identification information generated by the PUF embedded in devices and passwords set by users, devices and users identities could be verified through zero-knowledge proofs. The performance analysis and the experiment at the end of this work show that our protocol provides users with a strong security guarantee for IoT devices.
Physical Unclonable Functions (PUFs) and Hardware Security
Jens Mattke, Christian Maier, Axel Hund, Tim Weitzel
The MediLedger Project has built a blockchain ecosystem application that prevents counterfeit pharmaceuticals from entering the U.S. pharmaceuticals supply chain. From the lessons learned, we make four recommendations: 1) use a “benevolent dictator” and base governance on “consensus through collaboration”; 2) store the verification of transactions, not the transactions themselves, on the blockchain; 3) use zero-knowledge proofs to verify product and transaction authenticity while preserving full privacy; 4) use blockchain application capabilities not found in traditional technologies to fix ineffective IS landscapes.
Zero-knowledge schemes have recently become a popular attempt to offer users privacy in an attribute-based credential system. In this article, we do not contest the mathematics of these schemes; we assume it is logically sound. Instead, we draw attention to the trade-off that is made when employing cryptography instead of trusted parties to protect user privacy. We assert that, for these approaches to create the trust required by credential verifiers, they must introduce mechanisms that limit their utility and create significant privacy risk to the user that cuts against data minimization goals. Greater trust must be placed in the shelf life of cryptography to prevent the user from being unwantonly correlated than alternative approaches. Just as we would discourage storing encrypted private data on public blockchains, we discourage this approach here. Lastly, this article introduces the concept of a trusted witness which provides privacy for honest users and solves the privacy-trust problem without the disadvantages of the zero-knowledge approach.
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].
Ching Lam, Michelle Helena van Velthoven, Edward Meinert
BACKGROUND Advanced therapies, including cell and gene therapies, have shown therapeutic promise in curing life-threatening diseases, such as leukemia and lymphoma. However, these therapies can be complicated and expensive to deliver due to their sensitivity to environment; troublesome tissue, cell, or genetic material sourcing; and complicated regulatory requirements. OBJECTIVE This study aims to create a novel connected supply chain logistics and manufacturing management platform based on blockchain, with cell and gene therapy as a use case. Objectives are to define the requirements and perform feasibility evaluations on the use of blockchain for standardized manufacturing and establishment of a chain of custody for the needle-to-needle delivery of autologous cell and gene therapies. A way of lowering overall regulatory compliance costs for running a network of facilities operating similar or parallel processes will be evaluated by lowering the monitoring costs through publishing zero-knowledge proofs and product release by exception. METHODS The study will use blockchain technologies to digitally connect and integrate supply chain with manufacturing to address the security, scheduling, and communication issues between advanced therapy treatment centers and manufacturing facilities in order to realize a transparent, secure, automated, and cost-effective solution to the delivery of these life-saving therapies. An agile software development methodology will be used to develop, implement, and evaluate the system. The system will adhere to the EU and US good manufacturing practices and regulatory requirements. RESULTS This is a proposed study protocol, and upon acceptance, grant funding will be pursued for its execution in 2021. CONCLUSIONS The successful implementation of the integrated blockchain solution to supply chain and manufacturing of advanced therapies can push the industry standards toward a safer and more secure therapy delivery process. INTERNATIONAL REGISTERED REPORT PRR1-10.2196/17005
We present a new 4-move special honest-verifier zero-knowledge proof of knowledge system for proving that a vector of Pedersen commitments opens to a so-called "one-hot'' vector (i.e., to a vector from the standard orthonormal basis) from Zpn. The need for such proofs arises in the contexts of symmetric private information retrieval (SPIR), end-to-end verifiable voting (E2E), and privacy-preserving data aggregation and analytics, among others. The key insight underlying the new protocol is a simple observation regarding the paucity of roots of polynomials of bounded degree over a finite field. The new protocol is fast and yields succinct proofs: For vectors of length n, the prover evaluates Θ(Θlgn) group operations plus Θ(n) field operations and sends just Θ(Θlgn) group and field elements, while the verifier evaluates one n-base multiexponentiation plus Θ(łlgn) additional group operations and sends just 2(λ+lgn) bits to obtain a soundness error less than 2-λ. (A 5-move variant of the protocol reduces prover upload to just λlgn bits for the same soundness error.) We have implemented both our new protocol and its closest competitors from the literature; in accordance with our analytic results, experiments confirm that the new protocols handily outperform existing protocols for all but the shortest of vectors (roughly, for vectors with more than 16-32 elements).
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.
Russell W. F. Lai, Giulio Malavolta, Viktoria Ronge
In their celebrated work, Groth and Sahai [EUROCRYPT'08, SICOMP' 12] constructed non-interactive zero-knowledge (NIZK) proofs for general bilinear group arithmetic relations, which spawned the entire subfield of structure-preserving cryptography. This branch of the theory of cryptography focuses on modular design of advanced cryptographic primitives. Although the proof systems of Groth and Sahai are a powerful toolkit, their efficiency hits a barrier when the size of the witness is large, as the proof size is linear in that of the witness. In this work, we revisit the problem of proving knowledge of general bilinear group arithmetic relations in zero-knowledge. Specifically, we construct a succinct zero-knowledge argument for such relations, where the communication complexity is logarithmic in the integer and source group components of the witness. Our argument has public-coin setup and verifier and can therefore be turned non-interactive using the Fiat-Shamir transformation in the random oracle model. For the special case of non-bilinear group arithmetic relations with only integer unknowns, our system can be instantiated in non-bilinear groups. In many applications, our argument system can serve as a drop-in replacement of Groth-Sahai proofs, turning existing advanced primitives in the vast literature of structure-preserving cryptography into practically efficient systems with short proofs.
Samuel Steffen, Benjamin Bichsel, Mario Gersbach, Noa Melchior · 6 authors
Privacy concerns of smart contracts are a major roadblock preventing their wider adoption. A promising approach to protect private data is hiding it with cryptographic primitives and then enforcing correctness of state updates by Non-Interactive Zero-Knowledge (NIZK) proofs. Unfortunately, NIZK statements are less expressive than smart contracts, forcing developers to keep some functionality in the contract. This results in scattered logic, split across contract code and NIZK statements, with unclear privacy guarantees. To address these problems, we present the zkay language, which introduces privacy types defining owners of private values. zkay contracts are statically type checked to (i) ensure they are realizable using NIZK proofs and (ii) prevent unintended information leaks. Moreover, the logic of zkay contracts is easy to follow by just ignoring privacy types. To enforce zkay contracts, we automatically transform them into contracts equivalent in terms of privacy and functionality, yet executable on public blockchains. We evaluated our approach on a proof-of-concept implementation generating Solidity contracts and implemented 10 interesting example contracts in zkay. Our results indicate that zkay is practical: On-chain cost for executing the transformed contracts is around 1M gas per transaction (~0.50US$) and off-chain cost is moderate.
While fair exchange of goods is known to be impossible without assuming a trusted party, smart contracts in cryptocurrencies forgo such parties by assuming trust in the currency system. They allow a seller to sell a digital good, which the buyer will obtain if and only if she pays. Zero-knowledge contingent payments (zkCP) show that, despite the limited expressiveness of its scripting language, this is even possible in Bitcoin by using zero-knowledge proofs. At CCS'17, Campanelli, Gennaro, Goldfeder and Nizzardo showed that the zkCP protocol was flawed, in that the buyer could obtain information about the good without paying. They proposed countermeasures to repair zkCP and moreover observed that zkCP cannot be used when a service is sold. They introduce the notion of ZK contingent payments for services and give an instantiation based on a witness-indistinguishable (WI) proof system. We show that some of their proposed countermeasures are not sufficient by presenting an attack against their fixed zkCP scheme. We also show that their realization of zkCP for services is insecure, as the buyer could learn the desired information (i.e., whether the service was provided) without paying; in particular, we show that WI of the used proof system is not enough.
Muhammed F. Esgin, Raymond K. Zhao, Ron Steinfeld, Joseph K. Liu · 5 authors
We introduce MatRiCT, an efficient RingCT protocol for blockchain confidential transactions, whose security is based on "post-quantum'' (module) lattice assumptions. The proof length of the protocol is around two orders of magnitude shorter than the existing post-quantum proposal, and scales efficiently to large anonymity sets, unlike the existing proposal. Further, we provide the first full implementation of a post-quantum RingCT, demonstrating the practicality of our scheme. In particular, a typical transaction can be generated in a fraction of a second and verified in about 23 ms on a standard PC. Moreover, we show how our scheme can be extended to provide auditability, where a user can select a particular authority from a set of authorities to reveal her identity. The user also has the ability to select no auditing and all these auditing options may co-exist in the same environment. The key ingredients, introduced in this work, of MatRiCT are 1) the shortest to date scalable ring signature from standard lattice assumptions with no Gaussian sampling required, 2) a novel balance zero-knowledge proof and 3) a novel extractable commitment scheme from (module) lattices. We believe these ingredients to be of independent interest for other privacy-preserving applications such as secure e-voting. Despite allowing 64-bit precision for transaction amounts, our new balance proof, and thus our protocol, does not require a range proof on a wide range (such as 32- or 64-bit ranges), which has been a major obstacle against efficient lattice-based solutions. Further, we provide new formal definitions for RingCT-like protocols, where the real-world blockchain setting is captured more closely. The definitions are applicable in a generic setting, and thus are believed to contribute to the development of future confidential transaction protocols in general (not only in the lattice setting).
Russell W. F. Lai, Viktoria Ronge, Tim Ruffing, Dominique Schröder · 6 authors
Monero is the largest cryptocurrency with built-in cryptographic privacy features. The transactions are authenticated using zero-knowledge spend proofs, which provide a certain level of anonymity by hiding the source accounts from which the funds are sent among a set of other accounts. Due to its similarities to ring signatures, this core cryptographic component is called Ring Confidential Transactions (RingCT). Because of its practical relevance, several works attempt to analyze the security of RingCT. Since RingCT is rather complex, most of them are either informal, miss fundamental functionalities, or introduce undesirable trusted setup assumptions. Regarding efficiency, Monero currently deploys a scheme in which the size of the spend proof is linear in the ring size. This limits the ring size to only a few accounts, which in turn limits the acquired anonymity significantly and facilitates de-anonymization attacks. As a solution to these problems, we present the first rigorous formalization of RingCT as a cryptographic primitive. We then propose a generic construction of RingCT and prove it secure in our formal security model. By instantiating our generic construction with new efficient zero-knowledge proofs, we obtain Omniring, a fully-fledged RingCT scheme in the discrete logarithm setting that provides the highest concrete and asymptotic efficiency as of today. Omniring is the first RingCT scheme which 1) does not require a trusted setup or pairing-friendly elliptic curves, 2) has a proof size logarithmic in the size of the ring, and 3) allows to share the same ring between all source accounts in a transaction, thereby enabling significantly improved privacy level without sacrificing performance. Our zero-knowledge proofs rely on novel enhancements to the Bulletproofs framework (S&P 2018), which we believe are of independent interest.
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.