In this thesis, we construct an implementation of succinct non-interactive zero knowledge argument system. A non-interactive zero knowledge argument system is a protocol for a party (usually known as Prover) to provide a proof of knowledge to the solution of a statement to other parties (usually known as Verifier). The argument system will be able to provide such proof without leaking any other information regarding the solution. The non-interactivity allows such argument system to be done without requiring interaction between the parties involved. The statement that is proven in this work is the circuit satisfiability problem. The circuit satisfiability problem is a problem of deciding whether there exists an input that can make the final output of a circuit to be true. The argument system is based on Lipmaa's work \\cite{eprint2013:Lipmaa:NIZKSPECC} which uses span programs and linear error-correcting codes in its construction. We also try to give a very general explanation on zero knowledge argument system along the way in order to provide a simple concept to people encountering the notion for the first time. The argument system we attempt to construct is the non-adaptive version of the argument system. This version is useful for verifiable computation as pointed out by \\cite{Pinnochio2013:Parno} apart from its zero knowledge behavior. We begin by giving an overview on non-interactive zero knowledge, followed by span programs. We then proceed to describe on how to represent the circuit satisfiability problem using the mentioned tool. We present our implementation afterwards, listing out the libraries and implementation details that matters. We conclude by providing a speed measurement and possible future improvements of this work.
Cloud computing is a model for enabling convenient, on-demand network access to a shared pool of configurable computing resources (e.g., network, servers, storage, applications and services) that can be rapidly provisioned and released with minimal management effort or service provider interaction. During the last a few years, data security and integrity in cloud computing has emerged as a significantly important research area that has attracted increasing attention from both industry and academia. The virtual environment of cloud computing allows users to access computing power that exceeds what is contained within their own physical worlds. To enter this virtual environment, cloud users must transfer data throughout the cloud. Typically, cloud users know neither the exact location of their data nor the other sources of the data collectively stored with theirs. Consequently, several data security and integrity concerns have arisen, including key management, access control, searchable encryption techniques, remote integrity checks and proof of ownership in the cloud.\nThe first aspect of the work presented in this thesis is tree-based key management in cloud computing. Data encryption before outsourcing to the cloud is a common way to protect data privacy. Thus, key management is a challenging issue in cloud computing. It is the ability to correctly assign, monitor and secure keys which defines the level of operational security provided by any encryption implementation. The fundamental idea of this work is to design a secure and flexible key management mechanism for the outsourced data in cloud computing. In this thesis, an innovative tree-based key management scheme is proposed. The outsourced database remains private and secure, while some selected data and key nodes are shared with other parties in the cloud. Flexibility of key management is achieved and the security is proved in the standard model.\nThe second aspect of the work presented in this thesis is fine-grained access control. In order to secure the outsourced data in the cloud, designing efficient and secure access control is a challenging issue. Unlike traditional access control in which the data users and storage servers are in the same trust domain, access control techniques are very different in cloud computing, as the cloud servers are not trusted by most cloud users. The key idea of this work is to attribute sets-based access control. This thesis points out that any access policy can be defined as a logical expression formula over different attribute sets. Logical expression indicates what kind of user is allowed to access the data. A fine-grained and efficient access control is proposed, based on logical expression.\nThe third aspect of the work presented in this thesis is efficient searchable encryption techniques in cloud computing. Because the data is usually encrypted before being outsourced to the cloud, searching the encrypted data in cloud computing has recently gained attention and led to the development of efficient searchable encryption techniques. The fundamental idea of this work is to reduce the search cost on encrypted data. In this thesis, a practical keyword searching mechanism is proposed. The solution is very simple. It enables efficient multi-user keyword searches and hides the private information in the search queries. The security is proved in the standard model.\nThe fourth aspect of the work presented in this thesis is public remote data integrity checks. As the clients store important data in remote cloud storage without a local copy, it is important to check the remote data integrity. Design of efficient remote integrity check protocols without downloading the data is a challenging issue in cloud computing. The key idea of this work is a public remote integrity check based on zero-knowledge proof. In this thesis, an innovative public remote integrity check scheme (PRIC) is proposed. No information of either the verified data or the homomorphic tags is leaked. In addition, the experiment result shows that PRIC is efficient, especially when the data size is large or the integrity check is frequent. The security of PRIC is proved in the random oracle model.\nThe last aspect of the work presented in this thesis is proof of multiparty ownership for encrypted data in the cloud. There are many applications of ownership sharing by different users and the design of the proof protocols of joint ownership is a challenging issue. Meanwhile, the design of proof-of-ownership mechanisms for encrypted data is even more difficult. This is because encryption of the same file by different users with random keys results in different ciphertexts, and the cloud server cannot store the same hash root value for ownership verification. In this thesis, a proof of multiparty ownership solution (PMOW) with encrypted data is proposed. Every user can prove that he/she holds the plaintext of the encrypted file when the server stores one ciphertext only. In addition, a PMOW system is constructed. The security of PMOW is proved in the ideal cipher model.\nThe major contribution of this thesis is innovative and improved approaches to secure data in cloud computing. Using these approaches developed, a trustworthy cloud environment can be achieved.
Georg Neugebauer, Lucas Brutschy, Ulrike Meyer, Susanne Wetzel
Abstract. The problem of fair and privacy-preserving ordered set reconciliation arises in a variety of applications like auctions, e-voting, and appointment reconciliation. While several multi-party protocols have been proposed that solve this problem in the semi-honest model, there are no multi-party protocols that are secure in the malicious model so far. In this paper, we close this gap. Our newly proposed protocols are shown to be secure in the malicious model based on a variety of novel non-interactive zero-knowledge-proofs. We describe the implementation of our protocols and evaluate their performance in comparison to protocols solving the problem in the semi-honest case.
Abstract. Verifiably encrypted signatures (VES) are signatures encrypted by a public key of a trusted third party and we can verify their validity without decryption. This paper proposes a new VES scheme which is secure under the decisional linear (DLIN) assumption in the standard model. We also propose new obfuscators for encrypted signatures (ES) and encrypted VES (EVES) which are secure under the DLIN assump-tion. All previous efficient VES schemes in the standard model are either secure under standard assumptions (such as the computational Diffie-Hellman assumption) with large verification (or secret) keys or secure under (non-standard) dynamic q-type assumptions (such as the q-strong Diffie-Hellman extraction assumption) with short verification keys. Our construction is the first efficient VES scheme with short verification (and secret) keys secure under a standard assumption (DLIN). As by-products of our VES scheme, we construct new obfuscators for ES/EVES based on our new VES scheme. They are more efficient than previous obfuscators with respect to the public key size. Previous ob-fuscators for EVES are secure under non-standard assumption and use zero-knowledge (ZK) proof systems and Fiat-Shamir heuristics to obtain non-interactive ZK, i.e., its security is considered in the random oracle model. Thus, our construction also has an advantage with respect to as-sumptions and security models. Our new obfuscator for ES is obtained from our new obfuscator for EVES.
Abstract. We present a set of new, efficient, universally composable two-party protocols for evaluating reactive arithmetic circuits modulo n, where n is a safe RSA modulus of unknown factorization. Our protocols are based on a homomorphic encryption scheme with message space Zn, zero-knowledge proofs of existence, and a novel “mixed ” trapdoor commitment scheme. Our protocols are proven secure against adaptive corruptions (assuming secure erasures) under standard assumptions in the CRS model (without random oracles). Our protocols appear to be the most efficient ones that satisfy these security requirements. In contrast to prior protocols, we provide facilities that allow for the use of our protocols as building blocks of higher-level protocols. An additional contribution of this paper is a universally composable construction of the variant of the Dodis-Yampolskiy oblivious pseudorandom function in a group of order n as originally proposed by Jarecki and Liu.
Michael Backes, Aniket Kate, Sebastian Meiser, Tim Ruffing
Cryptographic protocols are commonly designed and their security proven under the assumption that the protocol parties have access to perfect (uniform) randomness. Physical randomness sources deployed in practical implementations of these protocols often fall short in meeting this assumption, but instead provide only a steady stream of bits with certain high entropy. Trying to ground cryptographic protocols on such imperfect, weaker sources of randomness has thus far mostly given rise to a multitude of impossibility results, including the impossibility to construct provably secure encryption, commitments, secret sharing, and zero-knowledge proofs based solely on a weak source. More generally, indistinguishability-based properties break down for such weak sources. In this paper, we show that the loss of security induced by using a weak source can be meaningfully quantified if the source is bounded, e.g., for the well-studied Santha-Vazirani (SV) sources. The quantification relies on a novel relaxation of indistinguishability by a quantitative parameter. We call the resulting notion dierential indistinguishability in order to reflect its structural similarity to dierential privacy. More concretely, we prove that indistinguishability with uniform randomness implies dierential indistinguishability with weak randomness. We show that if the amount of weak randomness is limited (e.g., by using it only to seed a PRG), all cryptographic primitives and protocols still achieve dierential indistinguishability.
Electronic voting is a popular application of cryptographic and network techniques to e-government. Most of the existing e-voting schemes can be classified into two categories: homomorphic voting and shuffling-based voting. In a homomorphic voting, an encryption algorithm with special homomorphic property (e.g. ElGamal encryption or Paillier encryption) is employed to encrypt the votes such that the sum of the votes can be recovered without decrypting any single vote. An advantage of homomorphic voting is efficient tallying. Tallying in homomorphic voting only costs one single decryption operation for each candidate. In this chapter, the existing e-voting solutions in both categories are surveyed and analysed. The key security properties in both categories are presented and then the existing e-voting schemes in each category are checked against the corresponding security properties. Security and efficiency of the schemes are analysed and the strongest security and highest efficiency achievable in each category is estimated. Problems and concerns about the existing solutions including vulnerability to malicious voters and (or) talliers, possible failure of complete correctness, imperfect privacy, dependence on computational assumptions, and exaggerated efficiency are addressed. New approaches will be proposed in both kinds of solutions to overcome the existing drawbacks in them. In homomorphic e-voting, the authors deal with possibly malicious voters and aim at efficient vote validity check to achieve strong and formally provable soundness and privacy. It can be implemented through new zero knowledge proof techniques, which are both efficient and provably secure. In mix-network-based e-voting, the authors deal with possibly deviating operations of both voters and talliers and aim at efficient proof of validity of shuffling, which guarantees the desired security properties and prevent attacks from malicious participants. It can be based on inspiring linear algebra knowledge and the new zero knowledge proof of existence of secret permutation.
In 2010, the fourth decade of the HIV pandemic arrived during a time of unprecedented success in HIV prevention. Globally, UNAIDS estimated that new HIV infections fell by 33% between 2001 and 2011; new infections among adults and adolescents fell by 50% or more in 26 countries (more than half of these countries were in sub-Saharan Africa), and new infections among children worldwide dropped by 52% [1,2]. The declines in new HIV infections are particularly evident in countries with sustained and more strategic investments, which take into account the specifics of local epidemics, increased political leadership and community engagement in response to the HIV epidemic, and scale up of HIV prevention and treatment programmes [2]. The rapidly growing delivery of antiretrovirals to women and infant feeding–based prevention programmes has resulted in a sharp decline in new HIV diagnoses among children. The encouraging declines in HIV infections can also be attributed to the improved effectiveness of combination antiretroviral treatment (cART), an expanded range of improved medications, the declining prices that make cART more accessible to people in low-income countries, growing coverage with HIV testing, and improved access to prevention and treatment services (particularly for women and young people in low-income countries). Global investment in the AIDS response jumped from US$3.8 billion in 2002 to US$18.9 billion in 2012. The new decade also saw a revolution in HIV prevention with ground-breaking scientific advances in HIV biomedical prevention, and specifically, proof that microbicides containing an antiretroviral agent can reduce sexual transmission of HIV to women by 39% [3], that earlier start of treatment by HIV-positive people (treatment as prevention or TasP) can reduce the risk of onward transmission by as much as 96% [4], and that consistent, correct use of a daily antiretroviral tablet by men who have sex with men (MSM) can achieve substantial reductions in HIV infections (pre-exposure prophylaxis or PrEP) [5]. In response to the excitement and optimism surrounding the preventative effects of antiretroviral medications, the UN member states considered and unanimously approved the new Political Declaration on HIV/AIDS at a special session of the General Assembly in New York in 2011 [6]. At the core of the 2011 UN Political Declaration are ambitious new HIV prevention targets calling on governments to commit to reducing sexual transmission of HIV by 50%, reducing HIV transmission though injecting drug use by 50% and eliminating mother-to-child transmission of HIV by 2015. These targets are aimed at reinvigorating the commitment towards achieving the Millennium Development Goal #6 to combat HIV/AIDS [7]. In the past two years, research on HIV biomedical prevention has focused on adapting the new prevention strategies to the context of local HIV epidemics [8]. There have been equal measures of optimism and pessimism expressed about the ability of new prevention strategies to halt the HIV pandemic. Based on the evidence that starting treatment earlier can increase health benefits and extend life for people with HIV [9,10], many clinicians are already recommending early treatment for both medical and TasP purposes. Regarding PrEP, the widespread reaction is caution in recommending this strategy. Such reluctance is based on concerns about the common adherence issues in the studies of PrEP [11], the obvious relationship between level of adherence to daily medication schedule and its preventative effect [12] and side effects and drug-resistant HIV [13], among others. Despite little evidence that PrEP use can affect behaviour, many concerns have been voiced about the future of safe sex practices, particularly condom use among MSM, if new biomedical prevention strategies are introduced. More research is needed to investigate this issue using appropriate study designs. In its current form, daily PrEP may benefit only a small number of people with very high and ongoing risk for HIV infection, and other PrEP regimens must be explored. The overarching concern about new prevention strategies, particularly PrEP, is that the cost and burden of providing them are currently unacceptable for most, even high-income, countries. As a result, there have been calls for more evidence and a very slow progress in implementing these two new exciting HIV prevention developments. Regarding PrEP, only two countries to date have prescription guidelines for people at high risk of HIV infection [14,15]. We now have the knowledge and new tools to revolutionize HIV prevention, and we have the bold new Political Declaration with ambitious targets. It must be acknowledged that the task of bringing HIV infections down to zero seems daunting from where we stand now in late 2013. Despite the global success in lowering the HIV infection rates by 33% [1], sub-Saharan Africa has seen only a 25% decline [16]. Some regions have seen increases (8% in Eastern Europe and central Asia [17], 19% in East Asia [18] and 37% in the Middle East and North Africa [19]). This lack of progress has been associated with insufficient resources, inadequate coverage of women with antiretroviral treatment and HIV testing programmes not reaching the population groups at high risk for HIV infection. While sexual behaviour has changed to become safer in some countries and populations, sexual risk taking has increased in other settings. This is the case in most high-income countries in North America, western and central Europe and Australasia, where MSM are central to local HIV epidemics. In these countries, both high-risk sexual practices among MSM and HIV infections have been on the rise [20,21]. Condom use has increased in some countries, but declined in others. Proven effective interventions (e.g., prevention of mother-to-child transmission (PMTCT) and needle- and syringe-exchange programmes) have not achieved sufficiently high coverage in many countries [1]. Although trends in risky sexual practices have been linked to the trends in HIV incidence [22] and population-level behaviour change to the reduction in HIV prevalence, there are still challenges in linking behaviour-change programmes to specific HIV outcomes on the population level [2]. While new expectations have been raised about the role of antiretrovirals for HIV prevention, mixed progress was observed in access to cART, and only 61% of people eligible for treatment under the 2010 WHO guidelines received it (this is as little as 34% under the 2013 WHO guidelines). The Political Declaration has for the first time named and acknowledged the importance of such population groups as MSM, people who inject drugs and sex workers for HIV prevention, but in many settings, stigma and access to treatment and prevention services for these groups are still important challenges. Many low- and middle-income countries have stepped up their local investments in HIV prevention [2], but, regrettably, the lack of resources has remained a major issue: only US$18.9 billion was available from all sources for the AIDS response in 2012, and this was estimated to be 16–26% short of annual need [1]. It is at this time of some successes in HIV prevention and challenges in how to optimize the available resources and tools that the aspirational Political Declaration of commitment to fight the pandemic is necessary. This year's International AIDS Day marks the midpoint towards the deadline set by the Political Declaration in 2011. It is an opportunity for governments and each of us to revisit and reinvigorate the universal commitment to bring HIV infections to zero. Like never before, we have good cause to expect the next generation to be AIDS-free and new HIV infections to move towards zero. In the face of the 75 million people who have suffered from HIV/AIDS and the many more affected, the international community should keep the promise and bring this HIV pandemic to an end. None were declared. The Kirby Institute receives project funding from the Australian Government Department of Health and Ageing. The views expressed in this publication do not necessarily represent the position of the Australian Government. IZ has prepared the manuscript and approved its final version.
Sherman S. M. Chow, Matthew Franklin, Haibin Zhang
Abstract. We reformalize and recast dual-receiver encryption (DRE) proposed in CCS ’04, a public-key encryption (PKE) scheme for encrypting to two independent recipients in one shot. We start by defining the crucial soundness property for DRE, which ensures that two recipients will get the same decryption result. While conceptually simple, DRE with soundness turns out to be a powerful primitive for various goals for PKE, such as complete non-malleability (CNM) and plaintext-awareness (PA). We then construct practical DRE schemes without random oracles under the Bilinear Decisional Diffie-Hellman assumption, while prior approaches rely on random oracles or inefficient non-interactive zero-knowledge proofs. Finally, we investigate further applications or extensions of DRE, including DRE with CNM, combined use of DRE and PKE, strengthening two types of PKE schemes with plaintext equality test, off-the-record messaging with a stronger notion of deniability, etc.
Cryptographic credentials allow user authorizations to be granted and verified. and have such applications as e-Passports, e-Commerce, and electronic cash. This thesis proposes a privacy protecting approach of binding biometrically derived keys to cryptographic credentials to prevent unauthorized lending. Our approach builds on the 2011 work of Adams, offering additional benefits of privacy protection of biometric information, generality on biometric modalities, and performance. Our protocol integrates into Brands’ Digital Credential scheme, and the Anonymous Credentials scheme of Camenisch and Lysyanskaya. We describe a detailed integration with the Digital Credential Scheme and sketch the integration into the Anonymous Credentials scheme. Security proofs for non-transferability, correctness of ownership, and unlinkability are provided for the protocol’s instantiation into Digital Credentials. Our approach uses specialized biometric devices in both the issue and show protocols. These devices are configured with our proposed primitive, the fuzzy ex-tractor indistinguishability adaptor which uses a traditional fuzzy extractor to create and regenerate cryptographic keys from biometric data and IND-CCA2 secure en-cryption protect the generated public data against multiplicity attacks. Pedersen commitments are used to hold the key at issue and show time, and A zero-knowledge proof of knowledge is used to ensure correspondence of key created at issue-time and regenerated at show-time. The above is done in a manner which preserves biometric privacy, as and delivers non-transferability of digital credentials. The biometric itself is not stored or divulged to any of the parties involved in the protocol. Privacy protection in multiple enrollments scenarios is achieved by the fuzzy extractor indistinguishability adapter. The zero knowledge proof of knowledge is used in the showing protocol to prove knowledge of values without divulging them.
Katz and Vaikuntanathan recently improved smooth projective hash functions in order to build oneround password-authenticated key exchange protocols (PAKE). To achieve security in the UC framework they allowed the simulator to extract the hashing key, which required simulation-sound non-interactive zero-knowledge proofs that are unfortunately inefficient. We improve the way the latter extractability is obtained by introducing the notion of trapdoor smooth projective hash function (TSPHF). A TSPHF is an SPHF with a trapdoor, which may not allow to recover the complete hashing key, but which still allows to compute the hash value, which is enough for an application to PAKE with UC-security against static corruptions. We additionally show that TSPHFs yield zero-knowledge proofs in two flows, with straight-line extractability. Besides those quite interesting applications of TSPHF, we also show how to generically build them on languages of ciphertexts, using any ElGamal-like encryption. Our concrete instantiations lead to efficient one-round UC-secure PAKE, extractable zero-knowledge arguments, and verifiable encryption of Waters signatures. In the case of the PAKE, our construction is the most efficient one-round UC-secure PAKE to date.
For various services, OTP (One-Time Password) is increasingly employed to sign in services. The most popular OTP scheme is S/KEY. However, S/KEY scheme is vulnerable to hash collision. In order to solve this problem, Choi and Kim proposed an OTP scheme based on pairing operation. This scheme overcame hash collision problem. Unfortunately, the scheme is vulnerable against insider attack. In this paper, we propose insider attack-resistant OTP scheme based on pairing operation. Our scheme employed zero-knowledge proof to generate OTP values. In short, our scheme sends an OTP and two random numbers encoded with XOR; any adversary has no sense about the random numbers. Our scheme authenticates entities with an OTP and gain a hint on next OTP value from one of random numbers. Consequently, we present insider attack-resistant OTP scheme by eliminating shared parameter among insider (e.g. time stamp).
Abstract. Consider a joint distribution (X,A) on a set X ×{0, 1}ℓ. We show that for any family F of distinguishers f: X × {0, 1}ℓ → {0, 1}, there exists a simulator h: X → {0, 1}ℓ such that 1. no function in F can distinguish (X,A) from (X,h(X)) with advantage ǫ, 2. h is only O(23ℓǫ−2) times less efficient than the functions in F. For the most interesting settings of the parameters (in particular, the cryptographic case where X has superlogarithmic min-entropy, ǫ> 0 is negligible and F consists of circuits of polynomial size), we can make the simulator h deterministic. As an illustrative application of this theorem, we give a new security proof for the leakage-resilient stream-cipher from Eurocrypt’09. Our proof is simpler and quantitatively much better than the original proof using the dense model theorem, giving meaningful security guarantees if instantiated with a standard blockcipher like AES. Subsequent to this work, Chung, Lui and Pass gave an interactive variant of our main theorem, and used it to investigate weak notions of Zero-Knowledge. Vadhan and Zheng give a more constructive version of our theorem using their new uniform min-max theorem. 1
An industrial scheme, to simulate the compressible two-phase flow in porous media, consists of a finite volume method together with a phase-by-phase upstream scheme. The implicit finite volume scheme satisfies industrial constraints of robustness since the proposed scheme discretizes the equations with gravity and capillary terms. We show that the proposed scheme satisfies the maximum principle for the saturation, a discrete-energy estimate on the pressures, and a function of the saturation that denotes capillary terms. These stability results allow us to derive the convergence of a subsequence to a weak solution of the continuous equations as the size of the discretization tends to zero. To our knowledge, this is the first convergence result of a finite volume scheme in the case of two-phase compressible flow in several space dimensions. The proof is given for the complete system when the density of each phase depends on its own pressure.
Advanced Numerical Methods in Computational Mathematics
We consider a class of two-party function evaluation protocols in which the parties are allowed to<br/>use ideal functionalities as well as a set of powerful primitives, namely commitments, homomorphic<br/>encryption, and certain zero-knowledge proofs. We illustrate that with these it is possible to capture<br/>protocols for oblivious transfer, coin- ipping, and generation of multiplication-triple.<br/>We show how any protocol in our class can be compiled to a symbolic representation expressed<br/>as a process in an abstract process calculus, and prove a general computational soundness theorem<br/>implying that if the protocol realises a given ideal functionality in the symbolic setting, then the<br/>original version also realises the ideal functionality in the standard computational UC setting. In<br/>other words, the theorem allows us to transfer a proof in the abstract symbolic setting to a proof in<br/>the standard UC model.<br/>Finally, we show that the symbolic interpretation is simple enough in a number of cases for the<br/>symbolic proof to be partly automated using ProVerif
In the paper, we present a kind of quantum voting protocol, which is based on controlled quantum teleportation of local unitary operations in non-symmetric quantum channel. In this protocol, the umpire CA with zero knowledge proof quantum identity authentication ensures voter’s anonymous identity authentication. The counting institution Bob generates a high-dimensional Greenberger-Horne-Zeilinger entangled state to establish a high-dimensional quantum communication channel. Performing the local unitary operation on their low-dimensional quantum ballot, voter’s quantum vote is teleportated by asymmetric matrix measurement and scrutineer Charlie auxiliary measuring. With the scrutineer Charlie’s help, Bob achieves the voting result by the output of unitary operation. Compared with other general quantum operation teleportation quantum voting protocol, the protocol utilizes the quantum information and transmission of quantum channel, which have different dimensions, so single particle information cannot be stolen, and can prevent forgery. The electoral process is fair and undeniable, owing to Charlie’s supervision. Since the success probability of quantum teleportation of local unitary operations is 1, the quantum voting is reliable.
Henry Corrigan-Gibbs, Wendy Mu, Dan Boneh, Bryan Ford
The security of any cryptosystem relies on the secrecy of the system's secret keys. Yet, recent experimental work demonstrates that tens of thousands of devices on the Internet use RSA and DSA secrets drawn from a small pool of candidate values. As a result, an adversary can derive the device's secret keys without breaking the underlying cryptosystem. We introduce a new threat model, under which there is a systemic solution to such randomness flaws. In our model, when a device generates a cryptographic key, it incorporates some random values from an "entropy authority" into its cryptographic secrets and then proves to the authority, using zero-knowledge-proof techniques, that it performed this operation correctly. By presenting an entropy-authority-signed public key certificate to a third party (like a certificate authority or SSH client), the device can demonstrate that its public key incorporates randomness from the authority and is therefore drawn from a large pool of candidate values. Where possible, our protocol protects against eavesdroppers, entropy authority misbehavior, and devices attempting to discredit the entropy authority. To demonstrate the practicality of our protocol, we have implemented and evaluated its performance on a commodity wireless home router. When running on a home router, our protocol incurs a $1.7\times$ slowdown over conventional RSA key generation and it incurs a $3.6\times$ slowdown over conventional EC-DSA key generation.
Eli Ben‐Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza
We design and build a system that enables clients to verify the outputs of programs executed by untrusted servers. A server provides a succinct non-interactive zero-knowledge proof (also known as a zk-SNARK), which the client verifies to ascertain correct execution. The system has two components: a cryptographic proof system for verifying satisfiability of arithmetic circuits, and a circuit generator to translate program executions to such circuits. Our design of both components improves in functionality and efficiency over previous work, as follows. Our circuit generator is the first to be universal: it does not need to know the program, but only a bound on its running time. It is also the first to support programs expressed as code for a von Neumann RISC random-access memory architecture, where programs may use just-in-time compilation and selfmodifying code. Moreover, the dependence on program size is additive (instead of multiplicative as in prior works), allowing efficient verification of large programs. The cryptographic proof system significantly improves proving and verification times, using a new pairing-based cryptographic library tailored to the protocol. We evaluated our system for programs with up to 10,000 instructions, running for up to 32,000 machine steps, each of which can arbitrarily access random-access memory; and demonstrated it executing programs that use just-in-time compilation. Our proofs are 230 bytes long at 80 bits of security, or 288 bytes long at 128 bits of security. Typical verification time is 5 ms, regardless of the original program’s running time.