Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Adaptively Secure Feldman VSS and Applications to Universally-Composable Threshold Cryptography

Masayuki Abe, Masayuki Abe, Serge Fehr

Published Jan 1, 2004• 0 citations
OpenAlex

Abstract

Abstract. We propose the first distributed discrete-log key generation (DLKG) protocol from scratch which is adaptively-secure in the nonerasure model, and at the same time completely avoids the use of interactive zero-knowledge proofs. As a consequence, the protocol can be proven secure in a universally-composable (UC) like framework which prohibits rewinding. We prove the security in what we call the singleinconsistent-player UC model, which guarantees arbitrary composition as long as all protocols are executed by the same players. As an application, we propose a fully UC threshold Schnorr signature scheme. Our results are based on a new adaptively-secure Feldman VSS scheme. Although adaptive security was already addressed by Feldman in the original paper, the scheme requires secure communication, secure erasure, and either a linear number of rounds or digital signatures to resolve disputes. Our scheme overcomes all of these shortcomings, but on the other hand requires some restriction on the corruption behavior of the adversary, which however disappears in some applications including our new DLKG protocol. We also propose several new adaptively-secure protocols, which may find other applications, like a sender non-committing encryption scheme, a distributed trapdoor-key generation protocol for Pedersen’s commitment scheme, or distributed-verifier proofs for proving relations among commitments or even any NP relations in general. 1

Related papers

UC-Secure Non-interactive Public-Key Encryption

Jan L. Camenisch, Anja Lehmann, Gregory Neven +1 more

The universal composability (UC) framework enables the modular design of cryptographic protocols by allowing arbitrary compositions of lower-level building blocks. Public-key encryption is unarguably a very important such building block. However, so far no UC-functionality exists that offers non-interactive encryption necessary for modular protocol construction. We provide an ideal functionality for non-committing encryption (i.e., public-key encryption secure against adaptive corruptions) with locally generated, and therefore non-interactive, ciphertexts. As a sanity check, we also provide a property-based security notion that we prove to be equivalent to the UC notion. We then show that the encryption scheme of Camenisch et al. (SCN '16) based on trapdoor permutations securely implements our notion in the random-oracle model without assuming secure erasures. This is the best one can hope to achieve as standard-model constructions do not exist due to the uninstantiability of round-optimal adaptively secure message transfer in the standard model (Nielsen, Crypto '02). We illustrate the modular reusability of our functionality by constructing the first non-interactive signcryption scheme secure against adaptive corruptions without secure erasures in the UC framework.

IEEE Computer Security Foundations Workshop (CSFW)•Aug 1, 2017•7 citations

A Framework for Efficient Fully-Equipped UC Commitments.

Eiichiro Fujisaki

We present a general framework for constructing non-interactive universally composable (UC) commitment schemes that are secure against adaptive adversaries in the non-erasure setting under a single re-usable common reference string. Previously, such “fully-equipped ” UC commitment schemes are only known in [8, 9], with an unavoidable overhead of O(κ) in the sense of communication and computational complexities; meaning that to commit λ bits, the communication and computational costs require O(λκ), where κ denotes the security parameter. Efficient construction of a fully-equipped UC commitment scheme was a long-standing open problem. We introduce a cryptographic primitive, called all-but-many encryptions (ABMEs), and prove that it is a translation of fully-equipped UC commitment in the primitive level. We then construct ABMEs from cryptographic primitives that we call a probabilistic pseudo random function family and extractable sigma protocols – the former is a probabilistic version of a pseudo random function family and the latter is a special kind of sigma (i.e., canonical 3-round public-coin HVSZK) protocols with some extractability. We provide fully-equipped UC commitment schemes from ABMEs under DDH and DCR-based assumptions, respectively. In particular, the DCR-based scheme is the first fully-equipped UC commitment scheme with optimal expansion factor Ω(1); to commit κ bits, the communication and computational costs are Ω(κ). We further construct a fully-equipped UC commitment scheme from a general assumption (in which trap-door permutations exist), which is far more efficient than the previous construction [9], because, unlike [9], our construction does not require non-interactive zero-knowledge proof systems. 1

•Jan 1, 2012•1 citation

All-But-Many Encryption A New Framework for Fully-Equipped UC Commitments

Eiichiro Fujisaki

We present a general framework for constructing non-interactive universally composable (UC) commitment schemes that are secure against adaptive adversaries in the non-erasure model under a re-usable common reference string. Previously, such “fully-equipped” UC commitment schemes have been known only in [CF01,CLOS02], with strict expansion factor O(κ); meaning that to commit λ bits, communication strictly requires O(λκ) bits, where κ denotes the security parameter. Efficient construction of a fully-equipped UC commitment scheme is a long-standing open problem. We introduce new abstraction, called all-but-many encryption (ABME), and prove that it captures fully-equipped UC commitment schemes. We propose the first fully-equipped UC commitment scheme with optimal expansion factor O(1) from our ABME scheme related to the DCR assumption. We also provide an all-but-many lossy trapdoor function (ABM-LTF) [Hof12] from our DCR-based ABME scheme, with a better lossy rate than [Hof12].

•Jan 1, 2014•1 citation

A new approach for UC security concurrent deniable authentication

Feng Li

Deniable authentication protocols allow a sender to authenticate a message for a receiver, in a way which the receiver cannot convince a third party that such au- thentication ever took place. When we consider an asynchronous multi-party net- work with open communications and an adversary that can adaptively corrupt as many parties as it wishes, we present a new approach to solve the problem of concurrent deniable authentication within the framework of universally compos- able (UC) security. We formulate a definition of an ideal functionality for deniable authentication. Our constructions rely on a modification of the verifiably smooth projective hashing (VSPH) with projection key function by trapdoor commitment. Our protocols are forward deniable and UC security against adaptive adversaries in the common reference string model. A new approach implies that security is pre- served under concurrent composition of an unbounded number of protocol execu- tions; it implies non-malleability with respect to arbitrary protocols and more. The novelty of our schemes is the use of witness indistinguishable protocols and the security is based on the decisional composite residuosity (DCR) assumption. This new approach is practically relevant as it leads to more efficient protocols and se-curity reductions.

Science China Information Sciences•Jan 1, 2008•0 citations

Analysis and Improvement of Lindell's UC-Secure Commitment Schemes.

Olivier Blazy, Céline Chevalier, David Pointcheval +1 more

Abstract. In 2011, Lindell proposed an efficient commitment scheme, with a non-interactive opening algorithm, in the Universal Composability (UC) framework. He recently acknowledged a bug in its security analysis for the adaptive case. We analyze the proof of the original paper and propose a simple patch of the scheme. More interestingly, we then modify it and present a more efficient commitment scheme secure in the UC framework, with the same level of security as Lindell’s protocol: adaptive corruptions, with erasures. The security is proven in the standard model (with a Common Reference String) under the classical Decisional Diffie-Hellman assumption. Our proposal is the most efficient UC-secure commitment proposed to date (in terms of computational workload and communication complexity).

•Jan 1, 2013•0 citations

An Efficient Non-interactive Universally Composable String-Commitment Scheme

Ryo Nishimaki, Eiichiro Fujisaki, Keisuke Tanaka

This paper presents a new non-interactive string-commitment scheme that achieves universally composable security. Security is proven under the decisional composite residuosity (DCR) assumption (or the decisional Diffie-Hellman (DDH) assumption) in the common reference string (CRS) model. The universal composability (UC) is a very strong security notion. If cryptographic protocols are proven secure in the UC framework, then they remain secure even if they are composed with arbitrary protocols and polynomially many copies of the protocols are run concurrently. Many UC commitment schemes in the CRS model have been proposed, but they are either interactive commitment or bit-commitment (not string-commitment) schemes. We note, however, that although our scheme is the first non-interactive UC string-commitment scheme, a CRS is not reusable. We use an extension of all-but-one trapdoor functions (ABO-TDFs) proposed by Peikert and Waters at STOC 2008 as an essential building block. Our main idea is to extend (original deterministic) ABO-TDFs to probabilistic ones by using the homomorphic properties of their function indices. The function indices of ABO-TDFs consist of ciphertexts of homomorphic encryption schemes (such as ElGamal, and Damgård-Jurik encryption). Therefore we can re-randomize the output of ABO-TDFs by re-randomization of ciphertexts. This is a new application of ABO-TDFs.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2012•5 citations
Abstract. We propose the first distributed discrete-log key generation (DLKG) protocol from scratch which is adaptively-secure in the nonerasure model, and at the same time completely avoids the use of interactive zero-knowledge proofs. As a consequence, the protocol can be proven secure in a universally-composable (UC) like framework which prohibits rewinding. We prove the security in what we call the singleinconsistent-player UC model, which guarantees arbitrary composition as long as all protocols are executed by the same players. As an application, we propose a fully UC threshold Schnorr signature scheme. Our results are based on a new adaptively-secure Feldman VSS scheme. Although adaptive security was already addressed by Feldman in the original paper, the scheme requires secure communication, secure erasure, and either a linear number of rounds or digital signatures to resolve disputes. Our scheme overcomes all of these shortcomings, but on the other hand requires some restriction on the corruption behavior of the adversary, which however disappears in some applications including our new DLKG protocol. We also propose several new adaptively-secure protocols, which may find other applications, like a sender non-committing encryption scheme, a distributed trapdoor-key generation protocol for Pedersen’s commitment scheme, or distributed-verifier proofs for proving relations among commitments or even any NP relations in general. 1
The universal composability (UC) framework enables the modular design of cryptographic protocols by allowing arbitrary compositions of lower-level building blocks. Public-key encryption is unarguably a very important such building block. However, so far no UC-functionality exists that offers non-interactive encryption necessary for modular protocol construction. We provide an ideal functionality for non-committing encryption (i.e., public-key encryption secure against adaptive corruptions) with locally generated, and therefore non-interactive, ciphertexts. As a sanity check, we also provide a property-based security notion that we prove to be equivalent to the UC notion. We then show that the encryption scheme of Camenisch et al. (SCN '16) based on trapdoor permutations securely implements our notion in the random-oracle model without assuming secure erasures. This is the best one can hope to achieve as standard-model constructions do not exist due to the uninstantiability of round-optimal adaptively secure message transfer in the standard model (Nielsen, Crypto '02). We illustrate the modular reusability of our functionality by constructing the first non-interactive signcryption scheme secure against adaptive corruptions without secure erasures in the UC framework.
We present a general framework for constructing non-interactive universally composable (UC) commitment schemes that are secure against adaptive adversaries in the non-erasure setting under a single re-usable common reference string. Previously, such “fully-equipped ” UC commitment schemes are only known in [8, 9], with an unavoidable overhead of O(κ) in the sense of communication and computational complexities; meaning that to commit λ bits, the communication and computational costs require O(λκ), where κ denotes the security parameter. Efficient construction of a fully-equipped UC commitment scheme was a long-standing open problem. We introduce a cryptographic primitive, called all-but-many encryptions (ABMEs), and prove that it is a translation of fully-equipped UC commitment in the primitive level. We then construct ABMEs from cryptographic primitives that we call a probabilistic pseudo random function family and extractable sigma protocols – the former is a probabilistic version of a pseudo random function family and the latter is a special kind of sigma (i.e., canonical 3-round public-coin HVSZK) protocols with some extractability. We provide fully-equipped UC commitment schemes from ABMEs under DDH and DCR-based assumptions, respectively. In particular, the DCR-based scheme is the first fully-equipped UC commitment scheme with optimal expansion factor Ω(1); to commit κ bits, the communication and computational costs are Ω(κ). We further construct a fully-equipped UC commitment scheme from a general assumption (in which trap-door permutations exist), which is far more efficient than the previous construction [9], because, unlike [9], our construction does not require non-interactive zero-knowledge proof systems. 1
We present a general framework for constructing non-interactive universally composable (UC) commitment schemes that are secure against adaptive adversaries in the non-erasure model under a re-usable common reference string. Previously, such “fully-equipped” UC commitment schemes have been known only in [CF01,CLOS02], with strict expansion factor O(κ); meaning that to commit λ bits, communication strictly requires O(λκ) bits, where κ denotes the security parameter. Efficient construction of a fully-equipped UC commitment scheme is a long-standing open problem. We introduce new abstraction, called all-but-many encryption (ABME), and prove that it captures fully-equipped UC commitment schemes. We propose the first fully-equipped UC commitment scheme with optimal expansion factor O(1) from our ABME scheme related to the DCR assumption. We also provide an all-but-many lossy trapdoor function (ABM-LTF) [Hof12] from our DCR-based ABME scheme, with a better lossy rate than [Hof12].
Deniable authentication protocols allow a sender to authenticate a message for a receiver, in a way which the receiver cannot convince a third party that such au- thentication ever took place. When we consider an asynchronous multi-party net- work with open communications and an adversary that can adaptively corrupt as many parties as it wishes, we present a new approach to solve the problem of concurrent deniable authentication within the framework of universally compos- able (UC) security. We formulate a definition of an ideal functionality for deniable authentication. Our constructions rely on a modification of the verifiably smooth projective hashing (VSPH) with projection key function by trapdoor commitment. Our protocols are forward deniable and UC security against adaptive adversaries in the common reference string model. A new approach implies that security is pre- served under concurrent composition of an unbounded number of protocol execu- tions; it implies non-malleability with respect to arbitrary protocols and more. The novelty of our schemes is the use of witness indistinguishable protocols and the security is based on the decisional composite residuosity (DCR) assumption. This new approach is practically relevant as it leads to more efficient protocols and se-curity reductions.
Abstract. In 2011, Lindell proposed an efficient commitment scheme, with a non-interactive opening algorithm, in the Universal Composability (UC) framework. He recently acknowledged a bug in its security analysis for the adaptive case. We analyze the proof of the original paper and propose a simple patch of the scheme. More interestingly, we then modify it and present a more efficient commitment scheme secure in the UC framework, with the same level of security as Lindell’s protocol: adaptive corruptions, with erasures. The security is proven in the standard model (with a Common Reference String) under the classical Decisional Diffie-Hellman assumption. Our proposal is the most efficient UC-secure commitment proposed to date (in terms of computational workload and communication complexity).
This paper presents a new non-interactive string-commitment scheme that achieves universally composable security. Security is proven under the decisional composite residuosity (DCR) assumption (or the decisional Diffie-Hellman (DDH) assumption) in the common reference string (CRS) model. The universal composability (UC) is a very strong security notion. If cryptographic protocols are proven secure in the UC framework, then they remain secure even if they are composed with arbitrary protocols and polynomially many copies of the protocols are run concurrently. Many UC commitment schemes in the CRS model have been proposed, but they are either interactive commitment or bit-commitment (not string-commitment) schemes. We note, however, that although our scheme is the first non-interactive UC string-commitment scheme, a CRS is not reusable. We use an extension of all-but-one trapdoor functions (ABO-TDFs) proposed by Peikert and Waters at STOC 2008 as an essential building block. Our main idea is to extend (original deterministic) ABO-TDFs to probabilistic ones by using the homomorphic properties of their function indices. The function indices of ABO-TDFs consist of ciphertexts of homomorphic encryption schemes (such as ElGamal, and Damgård-Jurik encryption). Therefore we can re-randomize the output of ABO-TDFs by re-randomization of ciphertexts. This is a new application of ABO-TDFs.