31 results sorted by ID
Universally Composable SNARKs with Transparent Setup without Programmable Random Oracle
Christian Badertscher, Matteo Campanelli, Michele Ciampi, Luigi Russo, Luisa Siniscalchi
Cryptographic protocols
Non-interactive zero-knowledge (NIZK) proofs allow a prover to convince a verifier about the validity of an NP-statement by sending a single message and without disclosing any additional information (besides the validity of the statement). Single-message cryptographic proofs are very versatile, which has made them widely used both in theory and in practice. This is particularly true for succinct proofs, where the length of the message is sublinear in the size of the NP relation. This...
Efficient online and Non-Interactive Threshold Signatures with Identifiable Aborts for Identity-Based Signatures in the IEEE P1363 Standard
Yan Jiang, Youwen Zhu, Jian Wang, Yudi Zhang
Cryptographic protocols
Identity-based threshold signature (IDTS) enables the generation of valid signatures without revealing cryptographic keys in the signing process. While current protocols have achieved much progress in their efficiency, many schemes easily suffer from denial-of-service attacks in which misbehaving parties could keep from generating signatures without being caught. The identifiable abort property is designed to withstand such an attack in some recent IDTS protocols. However, all these schemes...
SPRINT: High-Throughput Robust Distributed Schnorr Signatures
Fabrice Benhamouda, Shai Halevi, Hugo Krawczyk, Yiping Ma, Tal Rabin
Cryptographic protocols
We describe high-throughput threshold protocols with guaranteed output delivery for generating Schnorr-type signatures. The protocols run a single message-independent interactive ephemeral randomness generation procedure (e.g., DKG) followed by a \emph{non-interactive} multi-message signature generation procedure. The protocols offer significant increase in throughput already for as few as ten parties while remaining highly-efficient for many hundreds of parties with thousands of signatures...
Witness-Succinct Universally-Composable SNARKs
Chaya Ganesh, Yashvanth Kondi, Claudio Orlandi, Mahak Pancholi, Akira Takahashi, Daniel Tschudi
Foundations
Zero-knowledge Succinct Non-interactive ARguments of Knowledge (zkSNARKs) are becoming an increasingly fundamental tool in many real-world applications where the proof compactness is of the utmost importance, including blockchains. A proof of security for SNARKs in the Universal Composability (UC) framework (Canetti, FOCS'01) would rule out devastating malleability attacks. To retain security of SNARKs in the UC model, one must show their simulation-extractability such that the knowledge...
Efficient and Universally Composable Non-Interactive Zero-Knowledge Proofs of Knowledge with Security Against Adaptive Corruptions
Anna Lysyanskaya, Leah Namisa Rosenbloom
Foundations
Non-interactive zero-knowledge proofs of knowledge (NIZKPoK) serve as a key building block in many important cryptographic constructions. Achieving universally composable NIZKPoK secure against adaptive corruptions was a long-standing open problem, recently solved by Canetti, Sarkar, and Wang (Asiacrypt'22). This sole known construction requires heavy cryptographic machinery such as correlation-intractable hash functions, and is not ready for use in practice. In this paper, we give...
Universally Composable Sigma-protocols in the Global Random-Oracle Model
Anna Lysyanskaya, Leah Namisa Rosenbloom
Foundations
Numerous cryptographic applications require efficient non-interactive zero-knowledge proofs of knowledge (NIZKPoK) as a building block. Typically they rely on the Fiat-Shamir heuristic to do so, as security in the random-oracle model is considered good enough in practice. However, there is a troubling disconnect between the stand-alone security of such a protocol and its security as part of a larger, more complex system where several protocols may be running at the same time. Provable...
Decentralized Multi-Authority ABE for NC^1 from Computational-BDH
Pratish Datta, Ilan Komargodski, Brent Waters
Public-key cryptography
Decentralized multi-authority attribute-based encryption (𝖬𝖠-𝖠𝖡𝖤) is a strengthening of standard ciphertext-policy attribute-based encryption so that there is no trusted central authority: any party can become an authority and there is no requirement for any global coordination other than the creation of an initial set of common reference parameters. Essentially, any party can act as an authority for some attribute by creating a public key of its own and issuing private keys to different...
UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts
Ran Canetti, Rosario Gennaro, Steven Goldfeder, Nikolaos Makriyannis, Udi Peled
Cryptographic protocols
We present a distributed ECDSA protocol, for any number of signatories. The protocol improves on that of the authors (CCS'20), which in turn builds on the Gennaro & Goldfeder and Lindell & Nof protocols (CCS '18). Specifically:
** Only the last round of the protocol requires knowledge of the message, and the other rounds can take place in a preprocessing stage, lending to a non-interactive threshold ECDSA protocol.
** The protocol withstands adaptive corruption of signatories....
Decentralized Multi-Authority ABE for DNFs from LWE
Pratish Datta, Ilan Komargodski, Brent Waters
Public-key cryptography
We construct the first decentralized multi-authority attribute-based encryption
(MA-ABE) scheme for a non-trivial class of access policies whose security is
based (in the random oracle model) solely on the Learning With Errors (LWE)
assumption. The supported access policies are ones described by DNF
formulas. All previous constructions of MA-ABE schemes supporting any
non-trivial class of access policies were proven secure (in the random oracle
model) assuming various assumptions on...
Efficient Composable Oblivious Transfer from CDH in the Global Random Oracle Model
Bernardo David, Rafael Dowsley
Cryptographic protocols
Oblivious Transfer (OT) is a fundamental cryptographic protocol that finds a number of applications, in particular, as an essential building block for two-party and multi-party computation. We construct the first universally composable (UC) protocol for oblivious transfer secure against active static adversaries based on the Computational Diffie-Hellman (CDH) assumption. Our protocol is proven secure in the observable Global Random Oracle model. We start by constructing a protocol that...
Universal Composition with Global Subroutines: Capturing Global Setup within plain UC
Christian Badertscher, Ran Canetti, Julia Hesse, Björn Tackmann, Vassilis Zikas
Foundations
The Global and Externalized UC frameworks [Canetti-Dodis-Pass-Walfish, TCC 07] extend the plain UC framework to additionally handle protocols that use a ``global setup'', namely a mechanism that is also used by entities outside the protocol. These frameworks have broad applicability: Examples include public-key infrastructures, common reference strings, shared synchronization mechanisms, global blockchains, or even abstractions such as the random oracle. However, the need to work in a...
New Methods and Abstractions for RSA-Based Forward Secure Signatures
Susan Hohenberger, Brent Waters
Public-key cryptography
We put forward a new abstraction for achieving forward-secure
signatures that are (1) short, (2) have fast update and signing and (3) have
small private key size. Prior work that achieved these parameters was pioneered by
the pebbling techniques of Itkis and Reyzin (CRYPTO 2001) which showed a process for generating
a sequence of roots $h^{1/e_1}, h^{1/e_2}, \dots, h^{1/e_T}$ for a group element $h$ in
$\mathbb{Z}_N^*$. However, the current state of the art has limitations.
First, while...
ALBATROSS: publicly AttestabLe BATched Randomness based On Secret Sharing
Ignacio Cascudo, Bernardo David
Cryptographic protocols
In this paper we present ALBATROSS, a family of multiparty randomness generation protocols with guaranteed output delivery and public verification that allows to trade off corruption tolerance for a much improved amortized computational complexity. Our basic stand alone protocol is based on publicly verifiable secret sharing (PVSS) and is secure under in the random oracle model under the decisional Diffie-Hellman (DDH) hardness assumption.
We also address the important issue of constructing...
UC Non-Interactive, Proactive, Threshold ECDSA
Ran Canetti, Nikolaos Makriyannis, Udi Peled
Cryptographic protocols
Building on the Gennaro & Goldfeder and Lindell & Nof protocols (CCS ’18), we present a threshold ECDSA protocol, for any number of signatories and any threshold, that improves as follows over the state of the art:
* Signature generation takes only 4 rounds (down from the current 8 rounds), with a comparable computational cost. Furthermore, 3 of these rounds can take place in a preprocessing stage before the signed message is known, lending to a non-interactive threshold ECDSA protocol.
*...
Black-box use of One-way Functions is Useless for Optimal Fair Coin-Tossing
Hemanta K. Maji, Mingyuan Wang
Foundations
A two-party fair coin-tossing protocol guarantees output delivery to the honest party even when the other party aborts during the protocol execution. Cleve (STOC--1986) demonstrated that a computationally bounded fail-stop adversary could alter the output distribution of the honest party by (roughly) $1/r$ (in the statistical distance) in an $r$-message coin-tossing protocol. An optimal fair coin-tossing protocol ensures that no adversary can alter the output distribution beyond $1/r$.
In a...
Blazing Fast OT for Three-Round UC OT Extension
Ran Canetti, Pratik Sarkar, Xiao Wang
Cryptographic protocols
Oblivious Transfer (OT) is an important building block for multi-party computation (MPC). Since OT requires expensive public-key operations, efficiency-conscious MPC protocols use an OT extension (OTE) mechanism [Beaver 96, Ishai et al. 03] to provide the functionality of many independent OT instances with the same sender and receiver, using only symmetric-key operations plus few instances of some base OT protocol. Consequently there is significant interest in constructing OTE friendly...
Perfect Forward Security of SPAKE2
Michel Abdalla, Manuel Barbosa
Cryptographic protocols
SPAKE2 is a balanced password-authenticated key exchange (PAKE) protocol, proposed by Abdalla and Pointcheval at CTRSA 2005. Due to its simplicity and efficiency, SPAKE2 is one of the balanced PAKE candidates currently under consideration for standardization by the CFRG, together with SPEKE, CPace, and J-PAKE. In this paper, we show that SPAKE2 achieves perfect forward security in the random-oracle model under the Gap Diffie-Hellman assumption. Unlike prior results, which either did not...
UC-Commitment Schemes with Phase-Adaptive Security from Trapdoor Functions
Pedro Branco, Manuel Goulão, Paulo Mateus
Foundations
We propose a generic framework for perfectly hiding UC-Commitment schemes in the Global Random Oracle model of Canetti \textit{el at.} (CCS 14). The main building block of our construction is a novel primitive called Sampleable-Range Trapdoor Function, that is, a trapdoor function for which there is a non-negligible probability of finding preimages when given a uniformly chosen element of its codomain and the corresponding trapdoor. To show the versatility of the framework, we give concrete...
Threshold ECDSA from ECDSA Assumptions: The Multiparty Case
Jack Doerner, Yashvanth Kondi, Eysa Lee, abhi shelat
Cryptographic protocols
Cryptocurrency applications have spurred a resurgence of interest in the computation of ECDSA signatures using threshold protocols---that is, protocols in which the signing key is secret-shared among $n$ parties, of which any subset of size $t$ must interact in order to compute a signature. Among the resulting works to date, that of Doerner et al. requires the most natural assumptions while also achieving the best practical signing speed. It is, however, limited to the setting in which the...
A Post-Quantum UC-Commitment Scheme in the Global Random Oracle Model from Code-Based Assumptions
Pedro Branco
Cryptographic protocols
In this work, we propose the first post-quantum UC-commitment scheme in the Global Random Oracle Model, where only one non-programmable random oracle is available. The security of our proposal is based on two well-established post-quantum hardness assumptions from coding theory: The Syndrome Decoding and the Goppa Distinguisher. We prove that our proposal is perfectly hiding and computationally binding. The scheme is secure against static malicious adversaries.
The Wonderful World of Global Random Oracles
Jan Camenisch, Manu Drijvers, Tommaso Gagliardoni, Anja Lehmann, Gregory Neven
The random-oracle model by Bellare and Rogaway (CCS'93) is an indispensable tool for the security analysis of practical cryptographic protocols. However, the traditional random-oracle model fails to guarantee security when a protocol is composed with arbitrary protocols that use the same random oracle. Canetti, Jain, and Scafuro (CCS'14) put forth a global but non-programmable random oracle in the Generalized UC framework and showed that some basic cryptographic primitives with composable...
Synchronized Aggregate Signatures from the RSA Assumption
Susan Hohenberger, Brent Waters
Public-key cryptography
In this work we construct efficient aggregate signatures from the RSA assumption in the synchronized setting.
In this setting, the signing algorithm takes
as input a (time) period $t$ as well the secret key and message. A signer should sign at most once
for each $t$. A set of signatures can be aggregated so long as they were all created for the same
period $t$. Synchronized aggregate signatures are useful in systems where there is a natural
reporting period such as log and sensor data, or...
Fast and Universally-Composable Oblivious Transfer and Commitment Scheme with Adaptive Security
Megha Byali, Arpita Patra, Divya Ravi, Pratik Sarkar
Cryptographic protocols
Adaptive security embodies one of the strongest notions of security that allows an adversary to corrupt parties at any point during protocol execution and gain access to its internal state. Since it models real-life situations such as ``hacking", efficient adaptively-secure multiparty computation (MPC) protocols are desirable. Such protocols demand primitives such as oblivious transfer (OT) and commitment schemes that are adaptively-secure as building blocks. Efficient realizations of these...
Bitcoin as a Transaction Ledger: A Composable Treatment
Christian Badertscher, Ueli Maurer, Daniel Tschudi, Vassilis Zikas
Foundations
Bitcoin is one of the most prominent examples of a distributed cryptographic protocol that is extensively used in reality. Nonetheless, existing security proofs are property-based, and as such they do not support composition. In this work, we put forth a universally composable treatment of the Bitcoin protocol. We specify the goal that Bitcoin aims to achieve as an instance of a parameterizable ledger functionality and present a UC abstraction of the Bitcoin blockchain protocol. Our ideal...
Constant Round Adaptively Secure Protocols in the Tamper-Proof Hardware Model
Carmit Hazay, Antigoni Polychroniadou, Muthuramakrishnan Venkitasubramaniam
Achieving constant-round adaptively secure protocols (where all parties can be corrupted) in the plain model is a notoriously hard problem. Very recently, three works published in TCC 2015 (Dachman-Soled et al., Garg and Polychroniadou, Canetti et al.), solved the problem in the Common Reference String (CRS) model. In this work, we present a constant-round adaptive UC-secure computation protocol for all well-formed functionalities in the tamper-proof hardware model using stateless tokens...
Practical UC security with a Global Random Oracle
Ran Canetti, Abhishek Jain, Alessandra Scafuro
Foundations
We show that there exist commitment, zero-knowledge and general function evaluation protocols with universally composable security, in a model where all parties and all protocols have access to a single, global, random oracle and no other trusted setup. This model provides significantly stronger composable security guarantees than the traditional random oracle model of Bellare and Rogaway [CCS’93] or even the common reference string model. Indeed, these latter models provide no security...
Multi-Channel Broadcast Encryption
Duong Hieu Phan, David Pointcheval, Viet Cuong Trinh
Cryptographic protocols
Broadcast encryption aims at sending a content to a large arbitrary group of users at once. Currently, the most efficient schemes provide constant-size headers, that encapsulate ephemeral session keys under which the payload is encrypted. However, in practice, and namely for pay-TV, providers have to send various contents to different groups of users. Headers are thus specific to each group, one for each channel: as a consequence, the global overhead is linear in the number of channels....
Sequential Aggregate Signatures with Lazy Verification from Trapdoor Permutations
Kyle Brogle, Sharon Goldberg, Leonid Reyzin
Public-key cryptography
Sequential aggregate signature schemes allow n signers, in order, to sign a message each, at a lower total cost than the cost of n individual signatures. We present a sequential aggregate signature scheme based on trapdoor permutations (e.g., RSA). Unlike prior such proposals, our scheme does not require a signer to retrieve the keys of other signers and verify the aggregate-so-far before adding its own signature. Indeed, we do not even require a signer to know the public keys of other...
2011/051
Last updated: 2011-06-18
Towards Strong Adaptive Corruption Security of Authenticated Key Exchange
Zheng Yang
In this paper we study strong adaptive corruption security definitions for authenticated key exchange (AKE) protocols. Many recent protocols for Authenticated Key Exchange have been proven correct in the CK01 or eCK security model. The new model is suggested to be at least as strong as previous models for authenticated key exchange protocols. However, we observe that there are several kinds of attacks on existing AKE protocols that beyond the current class of security definitions which...
Decentralizing Attribute-Based Encryption
Allison Lewko, Brent Waters
We propose a Multi-Authority Attribute-Based Encryption (ABE) system.
In our system, any party can become an authority and there is no
requirement for any global coordination other than the creation of an
initial set of common reference parameters. A party can simply act as
an ABE authority by creating a public key and issuing private keys to
different users that reflect their attributes. A user can encrypt
data in terms of any boolean formula over attributes issued from any
chosen set of...
Key Derivation and Randomness Extraction
Olivier Chevassut, Pierre-Alain Fouque, Pierrick Gaudry, David Pointcheval
Cryptographic protocols
Key derivation refers to the process by which an agreed upon large
random number, often named master secret, is used to derive keys to
encrypt and authenticate data. Practitioners and standardization
bodies have usually used the random oracle model to get key material
from a Diffie-Hellman key exchange. However, proofs in the standard model
require randomness extractors to formally extract the entropy of the
random master secret into a seed prior to derive other keys.
This paper first deals...
Non-interactive zero-knowledge (NIZK) proofs allow a prover to convince a verifier about the validity of an NP-statement by sending a single message and without disclosing any additional information (besides the validity of the statement). Single-message cryptographic proofs are very versatile, which has made them widely used both in theory and in practice. This is particularly true for succinct proofs, where the length of the message is sublinear in the size of the NP relation. This...
Identity-based threshold signature (IDTS) enables the generation of valid signatures without revealing cryptographic keys in the signing process. While current protocols have achieved much progress in their efficiency, many schemes easily suffer from denial-of-service attacks in which misbehaving parties could keep from generating signatures without being caught. The identifiable abort property is designed to withstand such an attack in some recent IDTS protocols. However, all these schemes...
We describe high-throughput threshold protocols with guaranteed output delivery for generating Schnorr-type signatures. The protocols run a single message-independent interactive ephemeral randomness generation procedure (e.g., DKG) followed by a \emph{non-interactive} multi-message signature generation procedure. The protocols offer significant increase in throughput already for as few as ten parties while remaining highly-efficient for many hundreds of parties with thousands of signatures...
Zero-knowledge Succinct Non-interactive ARguments of Knowledge (zkSNARKs) are becoming an increasingly fundamental tool in many real-world applications where the proof compactness is of the utmost importance, including blockchains. A proof of security for SNARKs in the Universal Composability (UC) framework (Canetti, FOCS'01) would rule out devastating malleability attacks. To retain security of SNARKs in the UC model, one must show their simulation-extractability such that the knowledge...
Non-interactive zero-knowledge proofs of knowledge (NIZKPoK) serve as a key building block in many important cryptographic constructions. Achieving universally composable NIZKPoK secure against adaptive corruptions was a long-standing open problem, recently solved by Canetti, Sarkar, and Wang (Asiacrypt'22). This sole known construction requires heavy cryptographic machinery such as correlation-intractable hash functions, and is not ready for use in practice. In this paper, we give...
Numerous cryptographic applications require efficient non-interactive zero-knowledge proofs of knowledge (NIZKPoK) as a building block. Typically they rely on the Fiat-Shamir heuristic to do so, as security in the random-oracle model is considered good enough in practice. However, there is a troubling disconnect between the stand-alone security of such a protocol and its security as part of a larger, more complex system where several protocols may be running at the same time. Provable...
Decentralized multi-authority attribute-based encryption (𝖬𝖠-𝖠𝖡𝖤) is a strengthening of standard ciphertext-policy attribute-based encryption so that there is no trusted central authority: any party can become an authority and there is no requirement for any global coordination other than the creation of an initial set of common reference parameters. Essentially, any party can act as an authority for some attribute by creating a public key of its own and issuing private keys to different...
We present a distributed ECDSA protocol, for any number of signatories. The protocol improves on that of the authors (CCS'20), which in turn builds on the Gennaro & Goldfeder and Lindell & Nof protocols (CCS '18). Specifically: ** Only the last round of the protocol requires knowledge of the message, and the other rounds can take place in a preprocessing stage, lending to a non-interactive threshold ECDSA protocol. ** The protocol withstands adaptive corruption of signatories....
We construct the first decentralized multi-authority attribute-based encryption (MA-ABE) scheme for a non-trivial class of access policies whose security is based (in the random oracle model) solely on the Learning With Errors (LWE) assumption. The supported access policies are ones described by DNF formulas. All previous constructions of MA-ABE schemes supporting any non-trivial class of access policies were proven secure (in the random oracle model) assuming various assumptions on...
Oblivious Transfer (OT) is a fundamental cryptographic protocol that finds a number of applications, in particular, as an essential building block for two-party and multi-party computation. We construct the first universally composable (UC) protocol for oblivious transfer secure against active static adversaries based on the Computational Diffie-Hellman (CDH) assumption. Our protocol is proven secure in the observable Global Random Oracle model. We start by constructing a protocol that...
The Global and Externalized UC frameworks [Canetti-Dodis-Pass-Walfish, TCC 07] extend the plain UC framework to additionally handle protocols that use a ``global setup'', namely a mechanism that is also used by entities outside the protocol. These frameworks have broad applicability: Examples include public-key infrastructures, common reference strings, shared synchronization mechanisms, global blockchains, or even abstractions such as the random oracle. However, the need to work in a...
We put forward a new abstraction for achieving forward-secure signatures that are (1) short, (2) have fast update and signing and (3) have small private key size. Prior work that achieved these parameters was pioneered by the pebbling techniques of Itkis and Reyzin (CRYPTO 2001) which showed a process for generating a sequence of roots $h^{1/e_1}, h^{1/e_2}, \dots, h^{1/e_T}$ for a group element $h$ in $\mathbb{Z}_N^*$. However, the current state of the art has limitations. First, while...
In this paper we present ALBATROSS, a family of multiparty randomness generation protocols with guaranteed output delivery and public verification that allows to trade off corruption tolerance for a much improved amortized computational complexity. Our basic stand alone protocol is based on publicly verifiable secret sharing (PVSS) and is secure under in the random oracle model under the decisional Diffie-Hellman (DDH) hardness assumption. We also address the important issue of constructing...
Building on the Gennaro & Goldfeder and Lindell & Nof protocols (CCS ’18), we present a threshold ECDSA protocol, for any number of signatories and any threshold, that improves as follows over the state of the art: * Signature generation takes only 4 rounds (down from the current 8 rounds), with a comparable computational cost. Furthermore, 3 of these rounds can take place in a preprocessing stage before the signed message is known, lending to a non-interactive threshold ECDSA protocol. *...
A two-party fair coin-tossing protocol guarantees output delivery to the honest party even when the other party aborts during the protocol execution. Cleve (STOC--1986) demonstrated that a computationally bounded fail-stop adversary could alter the output distribution of the honest party by (roughly) $1/r$ (in the statistical distance) in an $r$-message coin-tossing protocol. An optimal fair coin-tossing protocol ensures that no adversary can alter the output distribution beyond $1/r$. In a...
Oblivious Transfer (OT) is an important building block for multi-party computation (MPC). Since OT requires expensive public-key operations, efficiency-conscious MPC protocols use an OT extension (OTE) mechanism [Beaver 96, Ishai et al. 03] to provide the functionality of many independent OT instances with the same sender and receiver, using only symmetric-key operations plus few instances of some base OT protocol. Consequently there is significant interest in constructing OTE friendly...
SPAKE2 is a balanced password-authenticated key exchange (PAKE) protocol, proposed by Abdalla and Pointcheval at CTRSA 2005. Due to its simplicity and efficiency, SPAKE2 is one of the balanced PAKE candidates currently under consideration for standardization by the CFRG, together with SPEKE, CPace, and J-PAKE. In this paper, we show that SPAKE2 achieves perfect forward security in the random-oracle model under the Gap Diffie-Hellman assumption. Unlike prior results, which either did not...
We propose a generic framework for perfectly hiding UC-Commitment schemes in the Global Random Oracle model of Canetti \textit{el at.} (CCS 14). The main building block of our construction is a novel primitive called Sampleable-Range Trapdoor Function, that is, a trapdoor function for which there is a non-negligible probability of finding preimages when given a uniformly chosen element of its codomain and the corresponding trapdoor. To show the versatility of the framework, we give concrete...
Cryptocurrency applications have spurred a resurgence of interest in the computation of ECDSA signatures using threshold protocols---that is, protocols in which the signing key is secret-shared among $n$ parties, of which any subset of size $t$ must interact in order to compute a signature. Among the resulting works to date, that of Doerner et al. requires the most natural assumptions while also achieving the best practical signing speed. It is, however, limited to the setting in which the...
In this work, we propose the first post-quantum UC-commitment scheme in the Global Random Oracle Model, where only one non-programmable random oracle is available. The security of our proposal is based on two well-established post-quantum hardness assumptions from coding theory: The Syndrome Decoding and the Goppa Distinguisher. We prove that our proposal is perfectly hiding and computationally binding. The scheme is secure against static malicious adversaries.
The random-oracle model by Bellare and Rogaway (CCS'93) is an indispensable tool for the security analysis of practical cryptographic protocols. However, the traditional random-oracle model fails to guarantee security when a protocol is composed with arbitrary protocols that use the same random oracle. Canetti, Jain, and Scafuro (CCS'14) put forth a global but non-programmable random oracle in the Generalized UC framework and showed that some basic cryptographic primitives with composable...
In this work we construct efficient aggregate signatures from the RSA assumption in the synchronized setting. In this setting, the signing algorithm takes as input a (time) period $t$ as well the secret key and message. A signer should sign at most once for each $t$. A set of signatures can be aggregated so long as they were all created for the same period $t$. Synchronized aggregate signatures are useful in systems where there is a natural reporting period such as log and sensor data, or...
Adaptive security embodies one of the strongest notions of security that allows an adversary to corrupt parties at any point during protocol execution and gain access to its internal state. Since it models real-life situations such as ``hacking", efficient adaptively-secure multiparty computation (MPC) protocols are desirable. Such protocols demand primitives such as oblivious transfer (OT) and commitment schemes that are adaptively-secure as building blocks. Efficient realizations of these...
Bitcoin is one of the most prominent examples of a distributed cryptographic protocol that is extensively used in reality. Nonetheless, existing security proofs are property-based, and as such they do not support composition. In this work, we put forth a universally composable treatment of the Bitcoin protocol. We specify the goal that Bitcoin aims to achieve as an instance of a parameterizable ledger functionality and present a UC abstraction of the Bitcoin blockchain protocol. Our ideal...
Achieving constant-round adaptively secure protocols (where all parties can be corrupted) in the plain model is a notoriously hard problem. Very recently, three works published in TCC 2015 (Dachman-Soled et al., Garg and Polychroniadou, Canetti et al.), solved the problem in the Common Reference String (CRS) model. In this work, we present a constant-round adaptive UC-secure computation protocol for all well-formed functionalities in the tamper-proof hardware model using stateless tokens...
We show that there exist commitment, zero-knowledge and general function evaluation protocols with universally composable security, in a model where all parties and all protocols have access to a single, global, random oracle and no other trusted setup. This model provides significantly stronger composable security guarantees than the traditional random oracle model of Bellare and Rogaway [CCS’93] or even the common reference string model. Indeed, these latter models provide no security...
Broadcast encryption aims at sending a content to a large arbitrary group of users at once. Currently, the most efficient schemes provide constant-size headers, that encapsulate ephemeral session keys under which the payload is encrypted. However, in practice, and namely for pay-TV, providers have to send various contents to different groups of users. Headers are thus specific to each group, one for each channel: as a consequence, the global overhead is linear in the number of channels....
Sequential aggregate signature schemes allow n signers, in order, to sign a message each, at a lower total cost than the cost of n individual signatures. We present a sequential aggregate signature scheme based on trapdoor permutations (e.g., RSA). Unlike prior such proposals, our scheme does not require a signer to retrieve the keys of other signers and verify the aggregate-so-far before adding its own signature. Indeed, we do not even require a signer to know the public keys of other...
In this paper we study strong adaptive corruption security definitions for authenticated key exchange (AKE) protocols. Many recent protocols for Authenticated Key Exchange have been proven correct in the CK01 or eCK security model. The new model is suggested to be at least as strong as previous models for authenticated key exchange protocols. However, we observe that there are several kinds of attacks on existing AKE protocols that beyond the current class of security definitions which...
We propose a Multi-Authority Attribute-Based Encryption (ABE) system. In our system, any party can become an authority and there is no requirement for any global coordination other than the creation of an initial set of common reference parameters. A party can simply act as an ABE authority by creating a public key and issuing private keys to different users that reflect their attributes. A user can encrypt data in terms of any boolean formula over attributes issued from any chosen set of...
Key derivation refers to the process by which an agreed upon large random number, often named master secret, is used to derive keys to encrypt and authenticate data. Practitioners and standardization bodies have usually used the random oracle model to get key material from a Diffie-Hellman key exchange. However, proofs in the standard model require randomness extractors to formally extract the entropy of the random master secret into a seed prior to derive other keys. This paper first deals...