International Association for Cryptologic Research

IACR News Central

Here you can see all recent updates to the IACR webpage. These updates are also available:

Now viewing news items related to:

11 March 2017
Secure and highly efficient authenticated encryption (AE) algorithms which achieve data confidentiality and authenticity in the symmetric-key setting have existed for well over a decade. By all conventional measures, AES-OCB seems to be the AE algorithm of choice on any platform with AES-NI: it has a proof showing it is secure assuming AES is, and it is one of the fastest out of all such algorithms. However, algorithms such as AES-GCM and ChaCha20+Poly1305 have seen more widespread adoption, even though they will likely never outperform AES-OCB on platforms with AES-NI. Given the fact that changing algorithms is a long and costly process, some have set out to maximize the security that can be achieved with the already deployed algorithms, without sacrificing efficiency: ChaCha20+Poly1305 already improves over GCM in how it authenticates, GCM-SIV uses GCM's underlying components to provide nonce misuse resistance, and TLS1.3 introduces a randomized nonce in order to improve GCM's multi-user security. We continue this line of work by looking more closely at GCM and ChaCha20+Poly1305 to see what robustness they already provide over algorithms such as OCB, and whether minor variants of the algorithms can be used for applications where defense in depth is critical. We formalize and illustrate how GCM and ChaCha20+Poly1305 offer varying degrees of resilience to nonce misuse, as they can recover quickly from repeated nonces, as opposed to OCB, which loses all security. More surprisingly, by introducing minor tweaks such as an additional XOR, we can create a GCM variant which provides security even when unverified plaintext is released.
The public nature of the blockchain has been shown to be a severe threat for the privacy of Bitcoin users. Even worse, since funds can be tracked and tainted, no two coins are equal, and fungibility, a fundamental property required in every currency, is at risk. With these threats in mind, several privacy-enhancing technologies have been proposed to improve transaction privacy in Bitcoin. However, they either require a deep redesign of the currency, breaking many currently deployed features, or they address only specific privacy issues and consequently provide only very limited guarantees when deployed separately.

The goal of this work is to overcome this trade-off. Building on CoinJoin, we design ValueShuffle, the first coin mixing protocol compatible with Confidential Transactions, a proposed enhancement to the Bitcoin protocol to hide payment values in the blockchain. ValueShuffle ensures the anonymity of mixing participants as well as the confidentiality of their payment values even against other possibly malicious mixing participants. By combining CoinJoin with Confidential Transactions and additionally Stealth Addresses, ValueShuffle provides comprehensive privacy (payer anonymity, payee anonymity, and payment value privacy) without breaking with fundamental design principles or features of the current Bitcoin system. Assuming that Confidential Transactions will be integrated in the Bitcoin protocol, ValueShuffle makes it possible to mix funds of different value as well as to mix and spend funds in the same transaction, which overcomes the two main limitations of previous coin mixing protocols.
Cryptographic agility is the ability to switch to larger cryptographic parameters or different algorithms in the case of security doubts. This very desirable property of cryptographic systems is inherently difficult to achieve in cryptocurrencies due to their permanent state in the blockchain: for example, if it turns out that the employed signature scheme is insecure, a switch to a different scheme can only protect the outputs of future transactions but cannot fix transaction outputs already recorded in the blockchain, exposing owners of the corresponding money to risk of theft. This situation is even worse with Confidential Transactions, a recent privacy-enhancing proposal to hide transacted monetary amounts in homomorphic commitments. If an attacker manages to break the computational binding property of a commitment, he can create money out of thin air, jeopardizing the security of the entire currency. The obvious solution is to use statistically or perfectly binding commitment schemes but they come with performance drawbacks due to the need for less efficient range proofs.

In this paper, our aim is to overcome this dilemma. We introduce switch commitments, which constitute a cryptographic middle ground between computationally binding and statistically binding commitments. The key property of this novel primitive is the possibility to switch existing commitments, e.g., recorded in the blockchain, from computational bindingness to statistical bindingness if doubts in the underlying hardness assumption arise. This switch trades off efficiency for security. We provide a practical and simple construction of switch commitments by proving that ElGamal commitments with a restricted message space are secure switch commitments.
We design a new McEliece-like rank metric based encryption scheme from Gabidulin codes. We explain why it is not affected by the invariant subspace attacks also known as Overbeck's attacks. The idea of the design mixes two existing approaches designing rank metric based encryption schemes. For a given security our public-keys are more compact than for the same security in the Hamming metric based settings.
In this article, a new oblivious transfer (OT) protocol, secure in the presence of erasure-free one-sided active adaptive adversaries is presented. The new bit OT protocol achieves better communication complexity than the existing bit OT protocol in this setting. The new bit OT protocol requires fewer number of public key encryption operations than the existing bit OT protocol in this setting. As a building block, a new two-party lossy threshold homomorphic public key cryptosystem is designed. It is secure in the same adversary model. It is of independent interest.
We develop foundations and several constructions for security protocols that can automatically detect, without false positives, if a secret (such as a key or password) has been misused. Such constructions can be used, e.g., to automatically shut down compromised services, or to automatically revoke misused secrets to minimize the effects of compromise. Our threat model includes malicious agents, (temporarily or permanently) compromised agents, and clones.

Previous works have studied domain-specific partial solutions to this problem. For example, Google's Certificate Transparency aims to provide infrastructure to detect the misuse of a certificate authority's signing key, logs have been used for detecting endpoint compromise, and protocols have been proposed to detect cloned RFID/smart cards. Contrary to these existing approaches, for which the designs are interwoven with domain-specific considerations and which usually do not enable fully automatic response (i.e., they need human assessment), our approach shows where automatic action is possible. Our results unify, provide design rationales, and suggest improvements for the existing domain-specific solutions.

Based on our analysis, we construct several mechanisms for the detection of misuse. Our mechanisms enable automatic response, such as revoking keys or shutting down services, thereby substantially limiting the impact of a compromise.

In several case studies, we show how our mechanisms can be used to substantially increase the security guarantees of a wide range of systems, such as web logins, payment systems, or electronic door locks. For example, we propose and formally verify an improved version of Cloudflare's Keyless SSL protocol that enables key misuse detection.
10 March 2017
Job Posting Security Researcher NEC Laboratories Europe
NEC Laboratories Europe is the European research center of NEC Corporation, a world leader in the computer and communications markets with a large world-wide base of R&D Laboratories. Top researchers from more than 20 countries develop, pilot and bring to reality technologies through open innovation.

We are looking for a Research Scientist / Senior Researcher to contribute to research and development in the areas of security and privacy with a special focus on applied cryptography, access control, cloud security, and distributed systems security. Our work ranges from foundational research and IPR creation to prototype development for NEC products and services. We support individual creativity, strong teamwork as well as scientific publications. English is the working language in the Laboratories. Initially, this position is limited to two years.

Applicants are sought with experience and skills in these areas:

- Excellent publication track record in security or applied cryptography.

- Strong experience in system security, distributed systems security, or software security.

- Strong experience in applied cryptography, cryptographic protocols, and security models.

- Proven experience in handling and managing large scale projects.

- Excellent interpersonal and communication skills in English. Knowledge of Japanese is a plus.

- Experience in software development including experience with programming languages, such as Golang, Java, or C/C++.

Candidates with a fresh Ph.D. in Security, Cryptography, Computer Science, or a closely related field, with a hands-on approach and proven skills in real-world problem solving are preferred.

Closing date for applications: 1 May 2017

Contact: Dr. Ghassan Karame, ghassan.karame (at) neclab.eu

Amardeo Sarma, amardeo.sarma (at) neclab.eu

More information: http://www.neclab.eu/jobs/openings/staff/NEC-NLE-1703-229-SEC-2-Security_Researcher.pdf

The Cryptography Research group at Microsoft Research in Redmond, Washington seeks outstanding students for 2017 summer internship projects on Homomorphic Encryption and Post-Quantum Cryptography. Developer skills or a background or interest in Machine Learning or Bioinformatics applications are desirable. PhD students in both mathematics and computer science are welcome to apply. Please submit resume, cover letter and reference(s).

Closing date for applications: 31 May 2017

Contact: Kristin Lauter, Research Manager

msrcryptointerns (at) outlook.com

More information: https://www.microsoft.com/en-us/research/project/homomorphic-encryption/

8 March 2017
Wee (TCC'14) and Attrapadung (Eurocrypt'14) introduced predicate and pair encodings, respectively, as a simple way to construct and analyze attribute-based encryption schemes, or more generally predicate encryption. However, many schemes do not satisfy the simple information theoretic property proposed in those works, and thus require much more complicated analysis. In this paper, we propose a new simple property for pair encodings called symbolic security. Proofs that pair encodings satisfy this property are concise and easy to verify. We show that this property is inherently tied to the security of predicate encryption schemes by arguing that any scheme which is not trivially broken must satisfy it. Then we use this property to discuss several ways to convert between pair encodings to obtain encryption schemes with different properties like small ciphertexts or keys. Finally, we show that any pair encoding satisfying our new property can be used to construct a fully secure predicate encryption scheme. The resulting schemes are secure under a new q-type assumption which we show follows from several of the assumptions used to construct such schemes in previous work.
The IACR Fellows Program recognizes outstanding IACR members for technical and professional contributions to the field of cryptology. Today we are pleased to announce five members that have been elevated to the rank of Fellow for 2017:

Jan Camenisch: For contributions to the theory and practice of privacy-preserving protocols and impact on government policy and industry.

Louis Guillou: For visionary actions that brought cryptography and smart cards to the real world, and for essential contributions to cryptographic standards.

Kwangjo Kim: For cryptographic design, education, and leadership, and for exemplary service to IACR and the Asia-Pacific cryptographic community.

Christof Paar: For founding CHES, service to the IACR, and for important contributions to secure and efficient implementation of cryptography.

Kenneth G. Paterson: For research and service contributions spanning theory and practice, and improving the security of widely deployed protocols.

Congratulations to the new fellows!
ePrint Report TwinsCoin: A Cryptocurrency via Proof-of-Work and Proof-of-Stake Alexander Chepurnoy, Tuyet Duong, Lei Fan, Hong-Sheng Zhou
We design and implement TwinsCoin, the first cryptocurrency based on a provably secure and scalable public blockchain design using both proof-of-work and proof-of-stake mechanisms. Different from the proof-of-work based Bitcoin, our construction uses two types of resources, computing power and coins~(i.e., stake). The blockchain in our system is more robust than that in a pure proof-of-work based system; even if the adversary controls the majority of mining power, we can still have the chance to secure the system by relying on honest stake. In contrast, Bitcoin blockchain will be insecure if the adversary controls more than 50\% of mining power. Our design follows a recent provably secure proof-of-work/proof-of-stake hybrid blockchain by Duong et al.~(ePrint 2016). In order to make our construction practical, we enhance Duong et al.'s design. In particular, we introduce a new strategy for difficulty adjustment in the hybrid blockchain and provide an analysis of it. We also show how to construct a light client for proof-of-stake cryptocurrencies and evaluate the proposal practically.

We implement our new design. Our implementation uses a recent modular development framework for blockchains, called Scorex. It allows us to change only certain parts of an application leaving other codebase intact. In addition to the blockchain implementation, a testnet is deployed. Source code is publicly available.
We propose a nonce misuse-resistant message authentication scheme called EHE (Encrypt-Hash-Encrypt). In EHE, a message-dependent polynomial is evaluated at the point which is an encrypted nonce. The resulting polynomial hash value is encrypted again and becomes an authentication tag. We prove the prf-security of the EHE scheme and extend it to two authenticated encryption modes which follow the "encrypt-then-authenticate" paradigm.
Despite their incentive structure flaws, mining pools account for more than 95% of Bitcoin's computation power. This paper introduces an attack against mining pools in which a malicious party pays pool members to withhold their solutions from their pool operator. We show that an adversary with a tiny amount of computing power and capital can execute this attack. Smart contracts enforce the malicious party's payments, and therefore miners need neither trust the attacker's intentions nor his ability to pay. Assuming pool members are rational, an adversary with a single mining ASIC can, in theory, destroy all big mining pools without losing any money (and even make some profit).
Several Multi-Prover Interactive Proofs (MIPs) found in the literature contain proofs of soundness that are lacking. This was first observed by Cr\'epeau, Salvail, Simard and Tapp who defined a notion of {Prover isolation} to partly address the issue. Furthermore, some existing Zero-Knowledge MIPs suffer from a catastrophic flaw: they outright allow the Provers to communicate via the Verifier. Consequently, their soundness claims are now seriously in doubt, if not plain wrong. This paper outlines the lack of isolation and numerous other issues found in the (ZK)MIP literature. A follow-up paper will resolve most of these issues in detail.
ePrint Report Efficient and Secure Outsourcing of Genomic Data Storage João Sá Sousa, Cédric Lefebvre, Zhicong Huang, Jean Louis Raisaro, Carlos Aguilar, Marc-Olivier Killijian, Jean-Pierre Hubaux
loud computing is becoming the preferred solution for efficiently dealing with the increasing amount of genomic data. Yet, outsourcing storage and processing of sensitive data, such as genomic data, comes with important concerns related to privacy and security. This calls for new sophisticated techniques that ensure data protection from untrusted cloud providers and still enables researchers to obtain useful information. We present a novel privacy-preserving algorithm for fully outsourcing the storage of large genomic data files to a public cloud and enable researchers to efficiently search for variants of interest. To preserve data and query confidentiality from possible leakage, our solution exploits optimal encoding for genomic variants and combines it with homomorphic encryption and private information retrieval. The proposed algorithm is implemented in C++ and evaluated on real data as part of the 2016 iDash genome privacy-protection challenge. Results show that our solution outperforms the state-of-the-art and enables researchers to search over millions of encrypted variants in a few seconds. As opposed to prior beliefs that sophisticated privacy-enhancing technologies (PETs) are unpractical for real operational settings, our solution demonstrates that, in the case of genomic data, PETs can represent very efficient enablers.
ePrint Report Towards Shared Ownership in the Cloud Hubert Ritzdorf, Claudio Soriente, Ghassan O. Karame, Srdjan Marinovic, Damian Gruber, Srdjan Capkun
Cloud storage platforms promise a convenient way for users to share files and engage in collaborations, yet they require all files to have a single owner who unilaterally makes access control decisions. Existing clouds are, thus, agnostic to the notion of shared ownership. This can be a significant limitation in many collaborations because, for example, one owner can delete files and revoke access without consulting the other collaborators.

In this paper, we first formally define a notion of shared ownership within a file access control model. We then propose two possible instantiations of our proposed shared ownership model. Our first solution, called Commune, relies on secure file dispersal and collusion-resistant secret sharing to ensure that all access grants in the cloud require the support of an agreed threshold of owners. As such, Commune can be used in existing clouds without modifications to the platforms. Our second solution, dubbed Comrade, leverages the blockchain technology in order to reach consensus on access control decision. Unlike Commune, Comrade requires that the cloud is able to translate access control decisions that reach consensus in the blockchain into storage access control rules, thus requiring minor modifications to existing clouds. We analyze the security of our proposals and compare/evaluate their performance through implementation integrated with Amazon S3.
LEGO-style cut-and-choose is known for its asymptotic efficiency in realizing actively-secure computations. The dominant cost of LEGO protocols is due to wire-soldering — the key technique enabling to put independently generated garbled gates together in a bucket to realize a logical gate. Existing wire-soldering constructions rely on homomorphic commitments and their security requires the majority of the garbled gates in every bucket to be correct.

In this paper, we propose an efficient construction of LEGO protocols that does not use homomorphic commitments but is able to guarantee security as long as at least one of the garbled gate in each bucket is correct. Additionally, the faulty gate detection rate in our protocol doubles that of the state-of-the-art LEGO constructions. We have implemented our protocol and our experiments on several benchmark applications show that the performance of our approach is highly competitive in comparison with existing implementations.
Cryptographic hash functions have wide applications including password hashing, pricing functions for spam and denial-of-service countermeasures and proof of work in cryptocurrencies. Recent progress on ASIC (Application Specific Integrated Circuit) hash engines raise concerns about the security of the above applications. This leads to a growing interest in ASIC resistant hash function and ASIC resistant proof of work schemes, i.e., those that do not give ASICs a huge advantage. The standard approach towards ASIC resistance today is through memory hard functions or memory hard proof of work schemes. However, we observe that the memory hardness approach is an incomplete solution. It only attempts to provide resistance to an ASIC's area advantage but overlooks the more important energy advantage. In this paper, we propose the notion of bandwidth hard functions to reduce an ASIC's energy advantage. CPUs cannot compete with ASICs for energy efficiency in computation, but we can rely on memory accesses to reduce an ASIC's energy advantage because energy costs of memory accesses are comparable for ASICs and CPUs. We propose a model for hardware energy cost that has sound foundations in practice. We then analyze the bandwidth hardness property of ASIC resistant candidates. We find scrypt, Catena-BRG and Balloon are bandwidth hard with suitable parameters. Lastly, we observe that a capacity hard function is not necessarily bandwidth hard, with a stacked double butterfly graph being a counterexample.
Achieving fully homomorphic encryption was a longstanding open problem in cryptography until it was resolved by Gentry in 2009. Soon after, several homomorphic encryption schemes were proposed. The early homomorphic encryption schemes were extremely impractical, but recently new implementations, new data encoding techniques, and a better understanding of the applications have started to change the situation. In this paper we introduce the most recent version (v2.1) of Simple Encrypted Arithmetic Library - SEAL, a homomorphic encryption library developed by Microsoft Research, and describe some of its core functionality.
Event date: 20 September to 22 September 2017
Submission deadline: 26 June 2017
Notification: 10 August 2017
6 March 2017
Job Posting PhD Students & Interns on Cyber Security Singapore University of Technology and Design (SUTD), Singapore
Singapore University of Technology and Design (SUTD) is a young university established in collaboration with MIT. Cyber security is one of its most important areas and grows very fast with rich research funding. It has the world’s best facilities in cyber physical systems including testbeds for Secure Water Treatment (SWaT), Water Distribution (WADI), Electric Power and Intelligent Control (EPIC), and IoT.

I am looking for promising PhD students who are interested in working in the area of cyber security. The position is fully funded up to 4 years with very competitive scholarship. Candidates should have an excellent background (with Bachelor or Master degree) in mathematics, computer science or electrical engineering and the ability to work on inter-disciplinary research projects. Acquaintance with cryptography and network/system security concepts as well as some programming skills will be considered as strong assets. More information of the PhD program is available at https://istd.sutd.edu.sg/phd/phd-overview/.

I am also looking for PhD interns on cyber security, especially on cyber-physical system security (IoT, autonomous vehicle, and power grid etc.). The attachment will be at least 6 months. Allowance will be provided for local expenses. More information of cyber-physical system security is available at http://jianying.space/cpss/.

Interested candidates please send your CV with a research statement to Prof. Jianying Zhou. Please also provide the names of two referees.

Closing date for applications: 30 April 2017

Contact: Contact: Prof. Jianying Zhou

Email: zhou_jianying (at) yahoo.com

Home: http://jianying.space/

More information: http://jianying.space/

5 March 2017
Event date: 28 June to 30 June 2017
Submission deadline: 30 April 2017
Notification: 31 May 2017
4 March 2017
ePrint Report 0-RTT Key Exchange with Full Forward Secrecy Felix Günther, Britta Hale, Tibor Jager, Sebastian Lauer
Reducing latency overhead while maintaining critical security guarantees like forward secrecy has become a major design goal for key exchange (KE) protocols, both in academia and industry. Of particular interest in this regard are 0-RTT protocols, a class of KE protocols which allow a client to send cryptographically protected payload in zero round-trip time (0-RTT) along with the very first KE protocol message, thereby minimizing latency. Prominent examples are Google's QUIC protocol and the upcoming TLS protocol version 1.3.

Intrinsically, the main challenge in a 0-RTT key exchange is to achieve forward secrecy and security against replay attacks for the very first payload message sent in the protocol. According to cryptographic folklore, it is impossible to achieve forward secrecy for this message, because the session key used to protect it must depend on a non-ephemeral secret of the receiver. If this secret is later leaked to an attacker, it should intuitively be possible for the attacker to compute the session key by performing the same computations as the receiver in the actual session.

In this paper we show that this belief is actually false. We construct the first 0-RTT key exchange protocol which provides full forward secrecy for all transmitted payload messages and is automatically resilient to replay attacks. In our construction we leverage a puncturable key encapsulation scheme which permits each ciphertext to only be decrypted once. Fundamentally, this is achieved by evolving the secret key after each decryption operation, but without modifying the corresponding public key or relying on shared state.

Our construction can be seen as an application of the puncturable encryption idea of Green and Miers (S&P 2015). We provide a new generic and standard-model construction of this tool that can be instantiated with any selectively secure hierarchical identity-based key encapsulation scheme.
ID based generalized signcryption can adaptively work as a signature scheme, an encryption scheme or a signcryption scheme and avoid weighty and complicated certificate management like Public Key Infrastructure. It has application in emerging paradigm big data security. Recently,Wei et al proposed a new ID based generalized signcryption scheme to obtain con…dentiality or/and authenticity in big data, and claimed that their scheme is provably secure in standard model. Unfortunately, by giving substantial attack, we indicate that Wei et al scheme suffer from compromise of Private Key Generator (PKG) master secret key and thus not hold the security of indistinguishability against adaptive chosen-ciphertext attacks (IND CCA) and existential unforgeability against adaptive chosen-message attacks(EUF 􀀀 CMA).
ePrint Report A Quantum Attack on LWE with Arbitrary Error Distribution Florian Göpfert, Christine van Vredendaal, Thomas Wunderer
Recently, an increasing amount of papers proposing post-quantum schemes also provide concrete parameter sets aiming for concrete post-quantum security levels. Security evaluations of such schemes need to include all possible attacks, in particular those by quantum adversaries. In the case of lattice-based cryptography, currently existing quantum attacks are mainly classical attacks, carried out with quantum basis reduction as subroutine. In this work, we propose a new quantum attack on the learning with errors (LWE) problem, whose hardness is the foundation for many modern lattice-based cryptographic constructions. Our quantum attack is based on Howgrave-Graham's Classical Hybrid Attack and is suitable for LWE instances in recent cryptocraphic proposals. We analyze its runtime complexity and optimize it over all possible choices of the attack parameters. In addition, we analyze the concrete post-quantum security levels of the parameter sets proposed for the New Hope and Frodo key exchance schemes, as well as several instances of the Lindner-Peikert encryption scheme. Our results show that - depending on the assumed basis reduction costs - our Quantum Hybrid Attack either significantly outperforms, or is at least comparable to all other attacks covered by Albrecht et al.'s work "On the concrete hardness of Learning with Errors". We further show that our Quantum Hybrid Attack improves upon the Classical Hybrid Attack in the case of LWE with binary error.
At CT-RSA 2017, List and Nandi proposed PMACx and PMAC2x which are variable input length pseudorandom functions (VO-PRFs) that use a tweakable block cipher (TBC) as the underlying primitive. These schemes are provably secure up to the query complexity of $2^n$, where $n$ denotes the block length of the TBC. In this paper, we falsify the provable security claims by presenting concrete attacks. We show that with the query complexity of $O(2^{n/2})$, i.e., with the birthday complexity, PMACx and PMAC2x are both insecure. Furthermore, we consider a deterministic authenticated encryption scheme called SIVx. This scheme is built on PMAC2x, and is provably secure up to the query complexity of $2^n$. However, we show a birthday complexity attack against it.
Ciphertext-policy attribute-based encryption (CP-ABE) is an access control mechanism where a data provider encrypts a secret message and then sends the ciphertext to the receivers according to the access policy which she/he decides. If the attributes of the receivers match the access policy, then they can decrypt the ciphertext. This paper shows a relation between ABE and identity-based encryption (IBE), and presents a bi-directional conversion between an access structure and identities. By the proposed conversion, the ABE scheme constructed from an IBE scheme will inherit the features, such as constant-size ciphertexts and anonymity, from the IBE scheme, and vice versa. It turns out that the proposed conversion also gives the first ABE achieving access structures with wildcard and constant-size ciphertexts/private keys. Finally, we prove the CCA security for confidentiality and anonymity.
In encryption schemes, the sender may not generate randomness properly if generating randomness is costly, and the sender is not concerned about the security of a message. The problem was studied by the first author (2016), and was formalized in a game-theoretic framework. In this work, we construct an encryption scheme with an optimal round complexity on the basis of the mechanism of repeated games.
In these years, the design of certificateless signature (CLS) scheme without bilinear pairings has been thoroughly investigated owing to its effectiveness on solving the key escrow problem in identity-based cryptography. In this paper, we identify that Wang et al.’s certificateless signature scheme cannot fulfil its security claims. We present a series of attack processes to demonstrate that Wang et al.’s scheme is insecure against a super type I adversary.
Uniform randomness beacons whose output can be publicly attested to be unbiased are required in several cryptographic protocols. A common approach to building such beacons is having a number parties run a coin tossing protocol with guaranteed output delivery (so that adversaries cannot simply keep honest parties from obtaining randomness, consequently halting protocols that rely on it). However, current constructions face serious scalability issues due to high computational and communication overheads. We present a coin tossing protocol for an honest majority that allows for any entity to verify that an output was honestly generated by observing publicly available information (even after the execution is complete), while achieving both guaranteed output delivery and scalability. The main building block of our construction is the first Publicly Verifiable Secret Sharing scheme for threshold access structures that requires only O(n) exponentiations. Previous schemes required O(nt) exponentiations (where t is the threshold) from each of the parties involved, making them unfit for scalable distributed randomness generation, which requires t=n/2 and thus O(n^2) exponentiations.

newer items   older items