Zhenfeng Zhang, Kang Yang, Xuexian Hu, Yuchen Wang
Anonymous authentication allows one to authenticate herself without revealing her identity, and becomes an important technique for constructing privacy-preserving Internet connections. Anonymous password authentication is highly desirable as it enables a client to authenticate herself by a human-memorable password while preserving her privacy. In this paper, we introduce a novel approach for designing anonymous password-authenticated key exchange (APAKE) protocols using algebraic message authentication codes (MACs), where an algebraic MAC wrapped by a password is used by a client for anonymous authentication, and a server issues algebraic MACs to clients and acts as the verifier of login protocols. Our APAKE construction is secure provided that the algebraic MAC is strongly existentially unforgeable under random message and chosen verification queries attack (suf-rmva), weak pseudorandom and tag-randomization simulatable, and has simulation-sound extractable non-interactive zero-knowledge proofs (SE-NIZKs). To design practical APAKE protocols, we instantiate an algebraic MAC based on the q-SDH assumption which satisfies all the required properties, and construct credential presentation algorithms for the MAC which have optimal efficiency for a randomize-then-prove paradigm. Based on the algebraic MAC, we instantiate a highly practical APAKE protocol and denote it by APAKE, which is much more efficient than the mechanisms specified by ISO/IEC 20009-4. An efficient revocation mechanism for APAKE is also proposed.
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.
Thanks to their anonymity (pseudonymity) and elimination of trusted intermediaries, cryptocurrencies such as Bitcoin have created or stimulated growth in many businesses and communities. Unfortunately, some of these are criminal, e.g., money laundering, illicit marketplaces, and ransomware. Next-generation cryptocurrencies such as Ethereum will include rich scripting languages in support of smart contracts, programs that autonomously intermediate transactions. In this paper, we explore the risk of smart contracts fueling new criminal ecosystems. Specifically, we show how what we call criminal smart contracts (CSCs) can facilitate leakage of confidential information, theft of cryptographic keys, and various real-world crimes (murder, arson, terrorism).
Roman Matzutt, Oliver Hohlfeld, Martin Henze, Robin Rawiel · 6 authors
As transaction fees skyrocket today, blockchains become increasingly expensive, hurting their adoption in broader applications. This work tackles the saving of transaction fees for economic blockchain applications. The key insight is that other than the existing "default'' mode to execute application logic fully on-chain, i.e., in smart contracts, and in fine granularity, i.e., user request per transaction, there are alternative execution modes with advantages in cost-effectiveness. On Ethereum, we propose a holistic middleware platform supporting flexible and secure transaction executions, including off-chain states and batching of user requests. Furthermore, we propose control-plane schemes to adapt the execution mode to the current workload for optimal runtime cost. We present a case study on the institutional accounts (e.g., coinbase.com) intensively sending Ether on Ethereum blockchains. By collecting real-life transactions, we construct workload benchmarks and show that our work saves 18%\sim 47%18%-47% per invocation than the default baseline while introducing 1.81%\sim 16.59%1.81%-16.59% blocks delay.
Cryptocurrencies, such as Bitcoin and 250 similar alt-coins, embody at their core a blockchain protocol --- a mechanism for a distributed network of computational nodes to periodically agree on a set of new transactions. Designing a secure blockchain protocol relies on an open challenge in security, that of designing a highly-scalable agreement protocol open to manipulation by byzantine or arbitrarily malicious nodes. Bitcoin's blockchain agreement protocol exhibits security, but does not scale: it processes 3--7 transactions per second at present, irrespective of the available computation capacity at hand.
Arthur Gervais, Ghassan Karame, Karl Wüst, Vasileios Glykantzis · 6 authors
Proof of Work (PoW) powered blockchains currently account for more than 90% of the total market capitalization of existing digital cryptocurrencies. Although the security provisions of Bitcoin have been thoroughly analysed, the security guarantees of variant (forked) PoW blockchains (which were instantiated with different parameters) have not received much attention in the literature. This opens the question whether existing security analysis of Bitcoin's PoW applies to other implementations which have been instantiated with different consensus and/or network parameters.
Gina Gallegos-García, Vincenzo Iovino, Alfredo Rial, Peter B. Roenne · 5 authors
In e-voting protocols, cryptographers must balance usability with strong security guarantees, such as privacy and verifiability. In traditional e-voting protocols, privacy is often provided by a trusted authority that learns the votes and computes the tally. Some protocols replace the trusted authority by a set of authorities, and privacy is guaranteed if less than a threshold number of authorities are corrupt. For verifiability, stronger security is demanded. Typically, corrupt authorities that try to fake the tally result must always be detected.To provide verifiability, many e-voting protocols use Non-Interactive Zero-Knowledge proofs (NIZK). Thanks to their non-interactive nature, NIZK allow anybody, including third parties that do not participate in the protocol, to verify the correctness of the tally. Therefore, NIZK can be used to obtain universal verifiability. Additionally, NIZK also improve usability because they allow voters to cast a vote non-interactively.The disadvantage of NIZK is that their security is based on setup assumptions such as the common reference string (CRS) or the random oracle model. The former requires a trusted party to generate a CRS. The latter, though a popular model for secure protocol design, has been shown to be unsound.We address the design of e-voting protocols that provide verifiability without any trust assumptions. We show that Non-Interactive Witness-Indistinguishable proofs can be used for this purpose. Our e-voting protocols are private under the Decision Linear assumption, while perfect individual verifiability, i.e. a fake tally is detected with probability 1, holds unconditionally. Perfect universal verifiability requires a trusted public bulletin board. We remark that our definition of verifiability does not consider eligibility or end-to-end verifiability. First, we present a general construction that supports any tally function. Then, we show how to efficiently instantiate it for specific types of elections through Groth-Sahai proofs.
Recently, by changing security requirements of computer networks, many public key schemes are introduced. One major shortcoming of identity-based cryptosystems is key screw. Certificateless public key cryptosystems were introduced to solve this problem. In this paper, a certificateless, public-key, multiple-key-agreement scheme will be offered which has some significant security properties such as perfect forward secrecy, strong security, and zero-knowledge proof. This scheme produces far more shared hidden keys per session in comparison with many existing schemes. In this paper, the security and the efficiency of the proposed scheme will be compared with some well-known current schemes.
Eli Ben‐Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon · 6 authors
We present the first constructions of single-prover proof systems that achieve perfect zero knowledge (PZK) for languages beyond NP, under no intractability assumptions: 1. The complexity class #P has PZK proofs in the model of Interactive PCPs (IPCPs) [KR08], where the verifier first receives from the prover a PCP and then engages with the prover in an Interactive Proof (IP). 2. The complexity class NEXP has PZK proofs in the model of Interactive Oracle Proofs (IOPs) [BCS16,RRR16], where the verifier, in every round of interaction, receives a PCP from the prover. Our constructions rely on succinct simulators that enable us to "simulate beyond NP", achieving exponential savings in efficiency over [BCGV16]. These simulators crucially rely on solving a problem that lies at the intersection of coding theory, linear algebra, and computational complexity, which we call the succinct constraint detection problem, and consists of detecting dual constraints with polynomial support size for codes of exponential block length. Our two results rely on solutions to this problem for fundamental classes of linear codes: * An algorithm to detect constraints for Reed--Muller codes of exponential length. * An algorithm to detect constraints for PCPs of Proximity of Reed--Solomon codes [BS08] of exponential degree. The first algorithm exploits the Raz--Shpilka [RS05] deterministic polynomial identity testing algorithm, and shows, to our knowledge, a first connection of algebraic complexity theory with zero knowledge. Along the way, we give a perfect zero knowledge analogue of the celebrated sumcheck protocol [LFKN92], by leveraging both succinct constraint detection and low-degree testing. The second algorithm exploits the recursive structure of the PCPs of Proximity to show that small-support constraints are "locally" spanned by a small number of small-support constraints.
Internet of Things (IoT) is considered as an advanced version of machine - to-machine technology where the communication between intelligent things is possible with internet connectivity. Security and privacy issues of these things are more prominent since it is widely used in IoT related applications. Even though several authentication schemes which are based on password, hash function and other cryptographic primitives are existing, studies showing that it is vulnerable to different kinds of attacks. This paper proposes an Elliptic Curve Cryptography (ECC) based Self-Certified Key Management (SCKM) scheme for mutual authentication scheme relying on self-certified public key management of IoT systems. In this scheme, the public key of the more resource constrained nodes in the IoT system is generated by the less constrained systems. The private key of the more constrained nodes is generated jointly by the nodes. This concept satisfies the zero knowledge Proof. A security analysis shows that of proposed scheme is effective in defending against various attacks.
Emmanuelle Anceaume, Thibaut Lajoie-Mazenc, Romaric Ludinard, Bruno Sericola
Decentralized cryptocurrency systems offer a medium of exchange secured by cryptography, without the need of a centralized banking authority. Among others, Bitcoin is considered as the most mature one. Its popularity lies on the introduction of the concept of the blockchain, a public distributed ledger shared by all participants of the system. Double spending attacks and blockchain forks are two main issues in blockchain-based protocols. The first one refers to the ability of an adversary to use the very same bitcoin more than once, while blockchain forks cause transient inconsistencies in the blockchain. We show through probabilistic analysis that the reliability of recent solutions that exclusively rely on a particular type of Bitcoin actors, called miners, to guarantee the consistency of Bitcoin operations, drastically decreases with the size of the blockchain.
Motivated by the great success and adoption of Bitcoin, a number of cryptocurrencies such as Litecoin, Dogecoin, and Ethereum are becoming increasingly popular. Although existing blockchain-based cryptocurrency schemes can ensure reasonable security for transactions, they do not consider any notion of fairness. Fair exchange allows two players to exchange digital items, such as digital signatures, over insecure networks fairly, so that either each player gets the other's item, or neither player does. Given that blockchain participants typically do not trust each other, enabling fairness in existing cryptocurrencies is an essential but insufficiently explored problem. In this paper, we explore the solution space for enabling the fair exchange of a cryptocurrency payment for a receipt. We identify the timeliness of an exchange as an important property especially when one of the parties involved in the exchange is resource-constrained. We introduce the notion of strong timeliness for a fair exchange protocol and propose two fair payment-for-receipt protocol instantiations that leverage functionality of the blockchain to achieve strong timeliness. We implement both and compare their security and efficiency.
Motivated by the great success and adoption of Bitcoin, a number of cryptocurrencies such as Litecoin, Dogecoin, and Ethereum are becoming increasingly popular. Although existing blockchain-based cryptocurrency schemes can ensure reasonable security for transactions, they do not consider any notion of fairness. Fair exchange allows two players to exchange digital "items", such as digital signatures, over insecure networks fairly, so that either each player gets the other's item, or neither player does. Given that blockchain participants typically do not trust each other, enabling fairness in existing cryptocurrencies is an essential but insufficiently explored problem. In this paper, we explore the solution space for enabling the fair exchange of a cryptocurrency payment for a receipt. We identify the timeliness of an exchange as an important property especially when one of the parties involved in the exchange is resource-constrained. We introduce the notion of strong timeliness for a fair exchange protocol and propose two fair payment-for-receipt protocol instantiations that leverage functionality of the blockchain to achieve strong timeliness. We implement both and compare their security and efficiency.
We examine the power of statistical zero knowledge proofs (captured by the complexity class SZK) and their variants. First, we give the strongest known relativized evidence that SZK contains hard problems, by exhibiting an oracle relative to which SZK (indeed, even NISZK) is not contained in the class UPP, containing those problems solvable by randomized algorithms with unbounded error. This answers an open question of Watrous from 2002 [Aar]. Second, we "lift" this oracle separation to the setting of communication complexity, thereby answering a question of Göös et al. (ICALP 2016). Third, we give relativized evidence that perfect zero knowledge proofs (captured by the class PZK) are weaker than general zero knowledge proofs. Specifically, we exhibit oracles relative to which SZK is not contained in PZK, NISZK is not contained in NIPZK, and PZK is not equal to coPZK. The first of these results answers a question raised in 1991 by Aiello and Håstad (Information and Computation), and the second answers a question of Lovett and Zhang (2016). We also describe additional applications of these results outside of structural complexity. The technical core of our results is a stronger hardness amplification theorem for approximate degree, which roughly says that composing the gapped-majority function with any function of high approximate degree yields a function with high threshold degree.
Cloud storage services allow users to outsource their data to cloud servers to save on local data storage costs. However, unlike using local storage devices, users don't physically own the data stored on cloud servers and can't be certain about the integrity of the cloud-stored data. Many public verification schemes have been proposed to allow a third-party auditor to verify the integrity of outsourced data. However, most of these schemes assume that the auditors are honest and reliable, so are vulnerable to malicious auditors. Moreover, in most of these schemes, an external adversary could modify the outsourced data and tamper with the interaction messages between the cloud server and the auditor, thus invalidating the outsourced data integrity verification. This article proposes an efficient and secure public verification of data integrity scheme that protects against external adversaries and malicious auditors. The proposed scheme adopts a random masking technique to protect against external adversaries, and requires users to audit auditors' behaviors to prevent malicious auditors from fabricating verification results. It uses Bitcoin to construct unbiased challenge messages to thwart collusion between malicious auditors and cloud servers. A performance analysis demonstrates that the proposed scheme is efficient in terms of the user's auditing overhead.
In this paper, we propose a joint random secret sharing scheme with public verifiability. It is practical in distributed environment. Utilizing additive homomorphism, a random secret will be corporately constructed by some participants, which avoids the need for a mutually trusted dealer. In addition, we explore the technique of homomorphic verification and that of bilinear pairing to allow each participant to publicly verify whether the received shares are consistent. The verification process in our scheme is unconditionally secure and non-interactive without using Fiat-Shamir technique or any additional zero knowledge proof, which is simple and higher efficient compared with previously known. Lastly, as an applied example of our work, we present how our techniques can be applied to handle dynamic node-join in mobile ad hoc network.
Nicolas T. Courtois, Guangyan Song, Ryan Castellucci
Abstract In this paper, we study and give the first detailed benchmarks on existing implementations of the secp256k1 elliptic curve used by at least hundreds of thousands of users in Bitcoin and other cryptocurrencies. Our implementation improves the state of the art by a factor of 2.5 with a focus on the cases, where side channel attacks are not a concern and a large quantity of RAM is available. As a result, we are able to scan the Bitcoin blockchain for weak keys faster than any previous implementation. We also give some examples of passwords which we have cracked, showing that brain wallets are not secure in practice even for quite complex passwords.
The authors define a notion of adaptive proofs of knowledge (PoKs) in the random oracle model (ROM). These are proofs where the malicious prover can adaptively issue multiple statements and proofs, and where the extractor is supposed to extract a witness for each statement. They begin by studying the traditional notion of zero‐knowledge PoKs in the ROM and then show how to extend it to the case of adaptive adversaries and to simulation soundness, where the adversary can also learn simulated proofs. The authors’ first main result is negative. Under common assumptions, they can show that the well‐known Fiat–Shamir–Schnorr proof system is not adaptively secure. As for the second result, they prove that an existing construction due to Fischlin (Crypto 2005) yields adaptively secure simulation‐sound PoKs in the ROM. Since the purpose of this work is to motivate and introduce adaptive proofs, they only briefly discuss some applications to other areas, for example that adaptive proofs seem to be exactly what one requires to construct chosen‐ciphertext attack‐secure public‐key encryption from indistinguishability under chosen plaintext attack secure schemes.
Die Möglichkeit der Programmierbarkeit des Bitcoins ist fast ein nachträglicher Einfall, auch wenn Sidechain‐Vorschläge diese Programmierbarkeit ein wenig leichter machen wollen und es bereits Altcoins mit verschiedenen spezifischen Anwendungen gibt. Im Gegensatz dazu wurde das Kryptowährungstechnologieprojekt Ethereum von Vitalik Buterin, seinem Erfinder, von Tag 1 als Software‐Entwicklungsplattform für dezentrale Applikationen konzipiert, und ihre Blockchain wurde speziell entwickelt, um die Ausführung dieser dezentralen Apps (auch Dapps genannt) zu unterstützen. Vitalik Buterin, 1994 in Russland geboren, war vor der Gründung von Ethereum auch involviert in die Entwicklungsprojekte Colored Coins und Mastercoins. Er gewann 2014 den "World Technology Award" und ein Stipendium des Risikokapitalgebers Peter Thiel. In dem Diskussionspapier zu Ethereum skizzierte Buterin vor allem die Grenzen einer Programmierbarkeit der Bitcoin‐Blockchain und schlug die Erstellung einer neuen komplett programmierbaren Blockchain mit einer turing‐vollständigen Programmiersprache vor. Anders als andere Blockchain‐Projekte soll die Ethereum Software nicht nur für einen Zweck nutzbar sein – sondern soll die Basis für die Erarbeitung aller möglichen Arten von Lösungen sein und dabei die Umsetzung intelligenter Verträge (Smart Contracts) ebenso erfassen als auch die Ethereum‐spezifische Idee von dezentralen autonomen Organisationen (DAOs).
There has recently been a flood of interest in potential new applications of blockchains, as well as proposals for more generic designs called public ledgers. Most of the novel proposals have been in the financial sector. However, the public ledger is an abstraction that solves several of the fundamental problems in the design of secure distributed systems: global time in the form of a strict linear order of past events, globally consistent and immutable view of the history, and enforcement of some application-specific safety properties. This paper investigates the applications of public ledgers to access control and, more specifically, to group management in distributed systems where entities are represented by their public keys and authorization is encoded into signed certificates. It is particularly difficult to handle negative information, such as revocation of certificates or group membership, in the distributed setting. The linear order of events and global consistency simplify these problems, but the enforcement of internal constraints in the ledger implementation often presents problems. We show that different types of revocation require slightly different properties from the ledger. We compare the requirements with Bitcoin, the best known blockchain, and describe an efficient ledger design for membership revocation that combines ideas from blockchains and from web-PKI monitoring. While we use certificate-based group-membership management as the case study, the same ideas can be applied more widely to rights revocation in distributed systems.