Antoine Delignat-Lavaud, CĂŠdric Fournet, Markulf Kohlweiss, Bryan Parno
Despite advances in security engineering, authentication in applications such as email and the Web still primarily relies on the X.509 public key infrastructure introduced in 1988. This PKI has many issues but is nearly impossible to replace. Leveraging recent progress in verifiable computation, we propose a novel use of existing X.509 certificates and infrastructure. Instead of receiving and validating chains of certificates, our applications receive and verify proofs of their knowledge, their validity, and their compliance with application policies. This yields smaller messages (by omitting certificates), stronger privacy (by hiding certificate contents), and stronger integrity (by embedding additional checks, e.g. for revocation). X.509 certificate validation is famously complex and error-prone, as it involves parsing ASN.1 data structures and interpreting them against diverse application policies. To manage this diversity, we propose a new format for writing application policies by composing X.509 templates, and we provide a template compiler that generates C code for validating certificates within a given policy. We then use the Geppetto cryptographic compiler to produce a zero-knowledge verifiable computation scheme for that policy. To optimize the resulting scheme, we develop new C libraries for RSA-PKCS#1 signatures and ASN.1 parsing, carefully tailored for cryptographic verifiability. We evaluate our approach by providing two real-world applications of verifiable computation: a drop-in replacement for certificates within TLS, and access control for the Helios voting protocol. For TLS, we support fine-grained validation policies, with revocation checking and selective disclosure of certificate contents, effectively turning X.509 certificates into anonymous credentials. For Helios, we obtain additional privacy and verifiability guarantees for voters equipped with X.509 certificates, such as those readily available from some national ID cards.
The evolution of the traditional electricity infrastructure into smart grids promises more reliable and efficient power management, more energy aware consumers and inclusion of renewable sources for power generation. These fruitful promises are attracting initiatives by various nations all over the globe in various fields of academia. However, this evolution relies on the advances in the information technologies and communication technologies and thus is inevitably prone to various risks and threats. Even though many solutions have been proposed in the recent literature to overcome the security threats in smart grid networks, many issues still need to be addressed to make smart grids a reliable and efficient innovation. In this thesis, we first introduce the background, network architecture, security threats and the security requirements of smart grid networks. Our work focuses on the security aspects of Neighborhood Area Network (NAN) subsystems of smart grid. We present some of the prominent threats and attacks, specific to this subsystem, which violate the specific security goals requisite for its reliable operation. The proposed solutions and countermeasures for these security issues presented in the recent literature have been deeply reviewed to identify the promising solutions with respect to the specific security goals. Then we propose an improved VI dynamic key refreshment strategy for mesh security in the NAN and an authentication scheme based on software defined network (SDN) using dynamic one-way accumulators. The proposed dynamic key refreshment scheme can protect the mesh network system based on IEEE 802.11s standard from DoS attacks during the key refreshment whereby the intruder could launch the attack using the information from previous key refreshment cycle as proposed in the original key refreshment scheme. The use of simple hash based operation makes the scheme cost effective for the resource limited network devices. The proposed scheme also adds an enhancement to the sub-protocol of the original key refreshment scheme for enhanced security and reliability. The proposed SDN based authentication scheme employs one-way dynamic accumulators combined with zero-knowledge proofs for easy and cost efficient authentication process. The availability of the cross authentication among different NAN devices enables us to replicate the mesh network architecture. Using SDN as the backbone of the scheme helps us accommodate the advances of the upcoming wireless technologies where we can update the changes in the scheme conveniently. Our analysis shows that the proposed schemes can achieve the requisite authentication while withstanding multiple attacks and the balance between security and system performance is also achieved.
Proof-of-work is a central concept in modern cryptocurrencies and denial-ofservice protection tools, but the requirement for fast verification so far has made it an easy prey for GPU-, ASIC-, and botnet-equipped users. The attempts to rely on memory-intensive computations in order to remedy the disparity between architectures have resulted in slow or broken schemes. In this paper we solve this open problem and show how to construct an asymmetric proof-of-work (PoW) based on a computationally-hard problem, which requires a great deal of memory to generate a proof (called a âmemory-hardnessâ feature) but is instant to verify. Our primary proposal, Equihash, is a PoW based on the generalized birthday problem and enhanced Wagnerâs algorithm for it. We introduce the new technique of algorithm binding to prevent cost amortization and demonstrate that possible parallel implementations are constrained by memory bandwidth. Our scheme has tunable and steep time-space tradeoffs, which impose large computational penalties if less memory is used. Our solution is practical and ready to deploy: a reference implementation of a proof-of-work requiring 700 MB of RAM runs in 15 seconds on a 2.1 GHz CPU, increases the computations by a factor of 1000 if memory is halved, and presents a proof of just 120 bytes long.
Cryptographic accumulators allow to succinctly represent a set by an accumulation value with respect to which short non-membership proofs about the set can be efficiently constructed and verified. Traditionally, their security captures soundness but offers no privacy: Convincing proofs reliably encode set membership, but they may well leak information about the accumulated set.
In this paper we put forward a strong privacy-preserving enhancement by introducing and devising zero-knowledge accumulators that additionally provide hiding guarantees: Accumulation values and proofs leak nothing about a dynamic set that evolves via element insertions/deletions. We formalize the new property using the standard real-ideal paradigm, namely demanding that an adaptive adversary with access to query/update oracles, cannot tell whether he interacts with honest protocol executions or a simulator fully ignorant of the set even of the type of updates on it. We rigorously compare the new primitive to existing ones for privacy-preserving verification of set membership or other relations and derive interesting implications among related security definitions, showing that zero-knowledge accumulators offer stronger privacy than recent related works by Naor et al. [TCCiž?2015] and Derler et al. [CT-RSAiž?2015]. We construct the first dynamic universal zero-knowledge accumulator that we show to be perfect zero-knowledge and secure under the q-Strong Bilinear Diffie-Hellman assumption.
Finally, we extend our new privacy notion and our new construction to provide privacy-preserving proofs also for an authenticated dynamic set collection--a primitive for efficiently verifying more elaborate set operations, beyond set-membership. We introduce a primitive that supports a zero-knowledge verifiable set algebra: Succinct proofs for union, intersection and set difference queries over a dynamically evolving collection of sets can be efficiently constructed and optimally verified, while--for the first time--they leak nothing about the collection beyond the query result.
Fan Zhang, Ethan Cecchetti, Kyle Croman, Ari Juels ¡ 5 authors
Smart contracts are programs that execute autonomously on blockchains. Their key envisioned uses (e.g. financial instruments) require them to consume data from outside the blockchain (e.g. stock quotes). Trustworthy data feeds that support a broad range of data requests will thus be critical to smart contract ecosystems. We present an authenticated data feed system called Town Crier (TC). TC acts as a bridge between smart contracts and existing web sites, which are already commonly trusted for non-blockchain applications. It combines a blockchain front end with a trusted hardware back end to scrape HTTPSenabled websites and serve source-authenticated data to relying smart contracts. TC also supports confidentiality. It enables private data requests with encrypted parameters. Additionally, in a generalization that executes smart-contract logic within TC, the system permits secure use of user credentials to scrape access-controlled online data sources. We describe TCâs design principles and architecture and report on an implementation that uses Intelâs recently introduced Software Guard Extensions (SGX) to furnish data to the Ethereum smart contract system. We formally model TC and define and prove its basic security properties in the Universal Composability (UC) framework. Our results include definitions and techniques of general interest relating to resource consumption (Ethereumâs âgasâ fee system) and TCB minimization. We also report on experiments with three example applications. We plan to launch TC soon as an online public service.
The power of linear and affine logic lies in their ability to model state change. However, in a trustless, peer-to-peer setting, it is difficult to force principals to commit to state changes. We show how to solve the peer-to-peer affine commitment problem using a generalization of Bitcoin in which transactions deal in types rather than numbers. This has applications to proof-carrying authorization and mechanically executable contracts. Importantly, our system can be---and is---implemented on top of the existing Bitcoin network, so there is no need to recruit computing power to a new protocol.
Abstract. Pedersen commitments are important cryptographic primi-tives. They allow a prover to commit to a certain value without revealing any information about it and without the prover being able to change its mind later on. Since the first property holds unconditionally this is an essential primitive for many schemes providing long-term confidential-ity. However, the second property only holds computationally. Hence, in the long run bindingness is lost, making the primitive improper for long-lived systems. Thus in this paper, we describe a protocol that, in a sense, prolongs the bindingness of a given Pedersen commitment. More precisely, we demonstrate how to prove in perfect zero-knowledge that a new Pedersen commitment- generated with a larger security param-eter- and a corresponding old commitment both commit to the same value. We stress that this is a non-trivial procedure. Up until now the only known perfect zero-knowledge proof techniques for proving mes-sage equivalence of two commitments work when both commitments use isomorphic message spaces. However, as we will show in this work, to prolong the security of Pedersen commitments we cannot tolerate this restriction. Our prolonging technique works for non-isomorphic message spaces, is efficient, can be repeated an arbitrary number of times, main-tains unconditional confidentiality, and allows to preserve the format of the Pedersen commitments. This makes the construction presented here an important contribution to long-lived systems. Finally, we illustrate this by discussing how commitments with prolongable bindingness can be used to allow for archiving solutions that provide not only integrity but also confidentiality in the long-term.
Ulrich RĂźhrmair, J. L. MartĂnez-Hurtado, Xiaolin Xu, Christian Kraeh ¡ 8 authors
We discuss the question of how physical statements can be proven over digital communication channels between two parties (a "prover" and a "verifier") residing in two separate local systems. Examples include: (i) "a certain object in the prover's system has temperature X°C", (ii) "two certain objects in the prover's system are positioned at distance X", or (iii) "a certain object in the prover's system has been irreversibly altered or destroyed". As illustrated by these examples, our treatment goes beyond classical security sensors in considering more general physical statements. Another distinctive aspect is the underlying security model: We neither assume secret keys in the prover's system, nor do we suppose classical sensor hardware in his system which is tamper-resistant and trusted by the verifier. Without an established name, we call this new type of security protocol a "virtual proof of reality" or simply a "virtual proof" (VP). In order to illustrate our novel concept, we give example VPs based on temperature sensitive integrated circuits, disordered optical scattering media, and quantum systems. The corresponding protocols prove the temperature, relative position, or destruction/modification of certain physical objects in the prover's system to the verifier. These objects (so-called "witness objects") are prepared by the verifier and handed over to the prover prior to the VP. Furthermore, we verify the practical validity of our method for all our optical and circuit-based VPs in detailed proof-of-concept experiments. Our work touches upon, and partly extends, several established concepts in cryptography and security, including physical unclonable functions, quantum cryptography, interactive proof systems, and, most recently, physical zero-knowledge proofs. We also discuss potential advancements of our method, for example "public virtual proofs" that function without exchanging witness objects between the verifier and the prover.
Open access
Physical Unclonable Functions (PUFs) and Hardware Security
Eli BenâSasson, Alessandro Chiesa, Matthew Green, Eran Tromer ¡ 5 authors
Non-interactive zero-knowledge proofs (NIZKs) are a powerful cryptographic tool, with numerous potential applications. However, succinct NIZKs (e.g., zk-SNARK schemes) necessitate a trusted party to generate and publish some public parameters, to be used by all provers and verifiers. This party is trusted to correctly run a probabilistic algorithm (specified by the the proof system) that outputs the public parameters, and publish them, without leaking any other information (such as the internal randomness used by the algorithm), violating either requirement may allow malicious parties to produce convincing "proofs" of false statements. This trust requirement poses a serious impediment to deploying NIZKs in many applications, because a party that is trusted by all users of the envisioned system may simply not exist. In this work, we show how public parameters for a class of NIZKs can be generated by a multi-party protocol, such that if at least one of the parties is honest, then the result is secure (in both aforementioned senses) and can be subsequently used for generating and verifying numerous proofs without any further trust. We design and implement such a protocol, tailored to efficiently support the state-of-the-art NIZK constructions with short and easy-to-verify proofs (Parno et al. IEEE S&P '13, Ben-Sasson et al. USENIX Sec '14, Danezis et al., ASIACRYPT '14). Applications of our system include generating public parameters for systems such as Zero cash (Ben-Sasson et al. IEEE S&P '13) and the scalable zero-knowledge proof system of (Ben-Sasson et al. CRYPTO '14).
Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti
In this work, we show how to use the positive results on succinct argument systems to prove impossibility results on leakage-resilient black-box zero knowledge. This recently proposed notion of zero knowledge deals with an adversary that can make leakage queries on the state of the prover. Our result holds for black-box simulation only and we also give some insights on the non-black-box case. Additionally, we show that, for several functionalities, leakage-resilient multi-party computation is impossible (regardless of the number of players and even if just one player is corrupted). More in details, we achieve the above results by extending a technique of [Nielsen, Venturi, Zottarel â PKC 13] to prove lower bounds for leakage-resilient security. Indeed, we use leakage queries to run an execution of a communication-efficient protocol in the head of the adversary. Moreover, to defeat the black-box simulator we connect the above technique for leakage resilience to security against reset attacks. Our results show that the open problem of [Ananth, Goyal, Pandey â Crypto 14] (i.e., continual leakage-resilient proofs without a common reference string) has a negative answer when security through black-box simulation is desired. Moreover our results close the open problem of [Boyle et al. â STOC 12] for the case of black-box simulation (i.e., the possibility of continual leakage-resilient secure computation without a leak-free interactive preprocessing).
Project development in a power enterprise always needs to authorize external devices access to the enterprise intranet for testing. In order to avoid an external device with a virus and pose a security risk to the power information system, external devices should have strict security assessment before access the enterprise intranet. But after the security assessment, the device user still be possible to change the platform configuration. Remote attestation is one of important measures when two sides need to communicate. It is concernful to attest the remote platform is trusty but not revealing the any private information of the platform. For this reason, we designed a novel remote anonymous attestation protocol based on TCM. The proposed protocol does not need extra zero knowledge proof and the involvement of the third trusted party and the composite signature scheme is proved secure against existential forgery on adaptively chosen message. So this protocol has better security and execution property.
We present a new, decentralized, efficient, and secure digital cryptocurrency, in which the ordinary users themselves keep turns to ensure that the systems works well. âsergeyg@mit.edu â silvio@csail.mit.edu
The Bitcoin cryptocurrency relies heavily on a variety of cryptographic functions and operations, which are currently assumed to be secure, but will inevitably be broken in the future. As Bitcoin tries to compete against traditional currencies, it remains to be seen how the Bitcoin protocol will need to change in response to weakened cryptography. To this end, this study systematically evaluates the effects of broken cryptographic primitives on the operation of the Bitcoin network, and the changes to the Bitcoin protocol that will be necessary in response. We conclude that a broken hash function only requires switching over to a new hash function, without the need to re-write the blockchain, and is well serviced by the âcheckpointâ mechanisms already built into Bitcoin. However, a vulnerability of the signature scheme cannot be dealt with in the same manner without side-e.ects, as it may lead to lost or stolen coins, even if the process is gradual and is conducted before the cryptographic primitive is broken. We conclude that solving this problem either requires some degree of centralization, or the use of Zero-Knowledge Proofs along or on top of Bitcoin.
Adam Everspaugh, Rahul Chatterjee, Samuel Scott, Ari Juels ¡ 5 authors
Conventional cryptographic services such as hardware-security modules and software-based key-management systems offer the ability to apply a pseudorandom function (PRF) such as HMAC to inputs of a client's choosing. These services are used, for example, to harden stored password hashes against offline brute-force attacks.
We propose a modern PRF service called PYTHIA designed to offer a level of flexibility, security, and ease-of-deployability lacking in prior approaches. The keystone of PYTHIA is a new cryptographic primitive called a verifiable partially-oblivious PRF that reveals a portion of an input message to the service but hides the rest. We give a construction that additionally supports efficient bulk rotation of previously obtained PRF values to new keys. Performance measurements show that our construction, which relies on bilinear pairings and zero-knowledge proofs, is highly practical. We also give accompanying formal definitions and proofs of security.
We implement PYTHIA as a multi-tenant, scalable PRF service that can scale up to hundreds of millions of distinct client applications on commodity systems. In our prototype implementation, query latencies are 15 ms in local-area settings and throughput is within a factor of two of a standard HTTPS server. We further report on implementations of two applications using PYTHIA, showing how to bring its security benefits to a new enterprise password storage system and a new brainwallet system for Bitcoin.
Memory-hard functions are becoming an important tool in the design of password hashing schemes, cryptocur-rencies, and more generic proof-of-work primitives that are x86-oriented and can not be computed on dedicated hardware more efficiently. We develop a simple and cryptographically secure approach to the design of such functions and show how to exploit the architecture of modern CPUs and memory chips to make faster and more secure schemes compared to existing alternatives such as scrypt. We also propose cryptographic criteria for the components, that prevent cost reductions using time-memory tradeoffs and side-channel leaks. The concrete proof-of-work instantiation, which we call Argon2, can fill GBytes of RAM within a second, is resilient to various tradeoffs, and is suitable for a wide range of applications, which aim to bind a computation to a certain architecture. Concerning potential DoS attacks, our scheme is lightweight enough to offset the bottleneck from the CPU to the memory bus thus leaving sufficient computing power for other tasks. We also propose parameters for which our scheme is botnet resistant. As an application, we suggest a cryptocurrency design with fast and memory-hard proof-of-work, which allows memoryless verification. 1
Kourosh Davarpanah, Dan Kaufman, Ophelie Pubellier
NeuCoin is a decentralized peer-to-peer cryptocurrency derived from Sunny\nKing's Peercoin, which itself was derived from Satoshi Nakamoto's Bitcoin. As\nwith Peercoin, proof-of-stake replaces proof-of-work as NeuCoin's security\nmodel, effectively replacing the operating costs of Bitcoin miners\n(electricity, computers) with the capital costs of holding the currency.\nProof-of-stake also avoids proof-of-work's inherent tendency towards\ncentralization resulting from competition for coinbase rewards among miners\nbased on lowest cost electricity and hash power.\n NeuCoin increases security relative to Peercoin and other existing\nproof-of-stake currencies in numerous ways, including: (1) incentivizing nodes\nto continuously stake coins over time through substantially higher mining\nrewards and lower minimum stake age; (2) abandoning the use of coin age in the\nmining formula; (3) causing the stake modifier parameter to change over time\nfor each stake; and (4) utilizing a client that punishes nodes that attempt to\nmine on multiple branches with duplicate stakes.\n This paper demonstrates how NeuCoin's proof-of-stake implementation addresses\nall commonly raised "nothing at stake" objections to generic proof-of-stake\nsystems. It also reviews many of the flaws of proof-of-work designs to\nhighlight the potential for an alternate cryptocurrency that solves these\nflaws.\n
We provide a framework for constructing leakage-resilient identification (ID) protocols in the bounded retrieval model (BRM) from proofs of storage (PoS) that hide partial information about the file. More precisely, we describe a generic transformation from any zero-knowledge PoS to a leakage-resilient ID protocol in the BRM. We then describe a ZK-PoS based on RSA which, under our transformation, yields the first ID protocol in the BRM based on RSA (in the ROM). The resulting protocol relies on a different computational assumption and is more efficient than previously-known constructions.
Several new services incentivize clients to compete in solving large computation tasks in exchange for financial rewards. This model of competitive distributed computation enables every user connected to the Internet to participate in a game in which he splits his computational power among a set of competing pools â the game is called a computational power splitting game. We formally model this game and show its utility in analyzing the security of pool protocols that dictate how financial rewards are shared among the members of a pool. As a case study, we analyze the Bitcoin cryptocurrency which attracts computing power roughly equivalent to billions of desktop machines, over 70% of which is organized into public pools. We show that existing pool reward sharing protocols are insecure in our game-theoretic analysis under an attack strategy called the âblock withholding attackâ. This attack is a topic of debate, initially thought to be ill-incentivized in todayâs pool protocols: i.e., causing a net loss to the attacker, and later argued to be always profitable. Our analysis shows that the attack is always well-incentivized in the long-run, but may not be so for a short duration. This implies that existing pool protocols are insecure, and if the attack is conducted systematically, Bitcoin pools could lose millions of dollars worth in months. The equilibrium state is a mixed strategyâthat isâin equilibrium all clients are incentivized to probabilistically attack to maximize their payoffs rather than participate honestly. As a result, a part of the Bitcoin network is incentivized to waste resource competing for higher selfish reward.
Jelle van den Hooff, M. Frans Kaashoek, Nickolai Zeldovich
VerSum allows lightweight clients to outsource expensive computations over large and frequently changing data structures, such as the Bitcoin or Namecoin blockchains, or a Certificate Transparency log. VerSum clients ensure that the output is correct by comparing the outputs from multiple servers. VerSum assumes that at least one server is honest, and crucially, when servers disagree, VerSum uses an efficient conflict resolution protocol to determine which server(s) made a mistake and thus obtain the correct output.