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

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

An Efficient Adaptive-Deniable-Concurrent Non-malleable Commitment Scheme

Seiko Arita

Published Jan 1, 2011• 0 citations
Publisher

Abstract

It is known that composable secure commitments, that is, concurrent non-malleable commitments exist in the plain model, based only on standard assumptions such as the existence of claw-free permutations or even one-way functions. Since being based on the plain model, the deniability of them is trivially satisfied, and especially the latter scheme satisfies also adaptivity, hence it is adaptive-deniable-concurrent non-malleable. However, those schemes cannot be said to be practically efficient. We show a practically efficient (string) adaptive-deniable-concurrent commitment scheme is possible under a global setup model, called the Global CRS-KR model.

DOI
10.1587/transfun.e94.a.367

Related papers

An Efficient Adaptive-Deniable-Concurrent Non-malleable Commitment Scheme.

Seiko Arita

Abstract. It is known that composable secure commitments, that is, concurrent non-malleable com-mitments exist in the plain model, based only on standard assumptions such as the existence of claw-free permutations or even one-way functions. Since being based on the plain model, the deniability of them is trivially satisfied, and especially the latter scheme satisfies also adaptivity, hence it is adaptive-deniable-concurrent non-malleable. However, those schemes cannot be said to be practically efficient. We show a practically efficient (string) adaptive-deniable-concurrent commitment scheme is possible under a global setup model, called global CRS-KR model.

•Jan 1, 2009•0 citations

Non-interactive and reusable non-malleable commitment schemes

Ivan Damgård, Jens Groth

We consider non-malleable (NM) and universally composable (UC) commitment schemes in the common reference string (CRS) model. We show how to construct non-interactive NM commitments that remain non-malleable even if the adversary has access to an arbitrary number of commitments from honest players - rather than one, as in several previous schemes. We show this is a strictly stronger security notion. Our construction is the first non-interactive scheme achieving this that can be based on the minimal assumption of existence of one-way functions. But it can also be instantiated in a very efficient version based on the strong RSA assumption. For UC commitments, we show that existence of a UC commitment scheme in the CRS model (interactive or not) implies key exchange and - for a uniform reference string - even implies oblivious transfer. This indicates that UC commitment is a strictly stronger primitive than NM. Finally, we show that our strong RSA based construction can be used to improve the most efficient known UC commitment scheme so it can work with a CRS of size independent of the number of players, without loss of efficiency.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 2003•14 citations

Non-interactive and reusable non-malleable commitment schemes

Ivan Damgård, Jens Groth

We consider non-malleable (NM) and universally composable (UC) commitment schemes in the common reference string (CRS) model. We show how to construct non-interactive NM commitments that remain non-malleable even if the adversary has access to an arbitrary number of commitments from honest players - rather than one, as in several previous schemes. We show this is a strictly stronger security notion. Our construction is the first non-interactive scheme achieving this that can be based on the minimal assumption of existence of one-way functions. But it can also be instantiated in a very efficient version based on the strong RSA assumption. For UC commitments, we show that existence of a UC commitment scheme in the CRS model (interactive or not) implies key exchange and - for a uniform reference string - even implies oblivious transfer. This indicates that UC commitment is a strictly stronger primitive than NM. Finally, we show that our strong RSA based construction can be used to improve the most efficient known UC commitment scheme so it can work with a CRS of size independent of the number of players, without loss of efficiency.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2003•117 citations

Adaptive and Concurrent Secure Computation from New Notions of Non-Malleability.

Dana Dachman-Soled, Tal Malkin, Mariana Raykova +1 more

We present a unified framework for obtaining general secure computation that achieves adaptive-Universally Composable (UC)-security. Our framework captures essentially all previous results on adaptive concurrent secure computation, both in relaxed models (e.g., quasi-polynomial time simulation), as well as trusted setup models (e.g., the CRS model, the imperfect CRS model). This provides conceptual simplicity and insight into what is required for adaptive and concurrent security, as well as yielding improvements to set-up assumptions and/or computational assumptions. Moreover, using our framework we provide first constructions of concurrent secure computation protocols that are adaptively secure in the timing model, and in the non-uniform simulation model. Conceptually, our framework can be viewed as an adaptive analogue to the recent work of Lin, Pass and Venkitasubramaniam [STOC ‘09], who considered only non-adaptive adversaries. Their main insight was that stand-alone non-malleability was sufficient for UC-security. A main conceptual contribution of this work is, quite surprisingly, that it is indeed the case even when considering adaptive security. A key element in our construction is a commitment scheme that satisfies a new notion of nonmalleability.

•Jan 1, 2011•2 citations

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

Concurrent Non-Malleable Zero Knowledge

Boaz Barak, Manoj Prabhakaran, Amit Sahai

We provide the first construction of a concurrent and non-malleable zero knowledge argument for every language in NP. We stress that our construction is in the plain model with no common random string, trusted parties, or super-polynomial simulation. That is, we construct a zero knowledge protocol Pi such that for every polynomial-time adversary that can adaptively and concurrently schedule polynomially many executions of Pi, and corrupt some of the verifiers and some of the provers in these sessions, there is a polynomial-time simulator that can simulate a transcript of the entire execution, along with the witnesses for all statements proven by a corrupt prover to an honest verifier Our security model is the traditional model for concurrent zero knowledge, where the statements to be proven by the honest provers are fixed in advance and do not depend on the previous history (but can be correlated with each other); corrupted provers, of course, can chose the statements adaptively. We also prove that there exists some functionality F (a combination of zero knowledge and oblivious transfer) such that it is impossible to obtain a concurrent non-malleable protocol for F in this model. Previous impossibility results for composable protocols ruled out existence of protocols for a wider class of functionalities {including zero knowledge!) but only if these protocols were required to remain secure when executed concurrently with arbitrarily chosen different protocols (Lindell, FOCS 2003) or if these protocols were required to remain secure when the honest parties' inputs in each execution are chosen adaptively based on the results of previous executions (Lindell, TCC2004). We obtain an Otilde(n) -round protocol under the assumption that one-to-one one-way functions exist. This can be improved to Otilde(k log n) rounds under the assumption that there exist k-round statistically hiding commitment schemes. Our protocol is a black-box zero knowledge protocol

Annual Symposium on Foundations of Computer Science•Oct 1, 2006•86 citations
It is known that composable secure commitments, that is, concurrent non-malleable commitments exist in the plain model, based only on standard assumptions such as the existence of claw-free permutations or even one-way functions. Since being based on the plain model, the deniability of them is trivially satisfied, and especially the latter scheme satisfies also adaptivity, hence it is adaptive-deniable-concurrent non-malleable. However, those schemes cannot be said to be practically efficient. We show a practically efficient (string) adaptive-deniable-concurrent commitment scheme is possible under a global setup model, called the Global CRS-KR model.
Abstract. It is known that composable secure commitments, that is, concurrent non-malleable com-mitments exist in the plain model, based only on standard assumptions such as the existence of claw-free permutations or even one-way functions. Since being based on the plain model, the deniability of them is trivially satisfied, and especially the latter scheme satisfies also adaptivity, hence it is adaptive-deniable-concurrent non-malleable. However, those schemes cannot be said to be practically efficient. We show a practically efficient (string) adaptive-deniable-concurrent commitment scheme is possible under a global setup model, called global CRS-KR model.
We consider non-malleable (NM) and universally composable (UC) commitment schemes in the common reference string (CRS) model. We show how to construct non-interactive NM commitments that remain non-malleable even if the adversary has access to an arbitrary number of commitments from honest players - rather than one, as in several previous schemes. We show this is a strictly stronger security notion. Our construction is the first non-interactive scheme achieving this that can be based on the minimal assumption of existence of one-way functions. But it can also be instantiated in a very efficient version based on the strong RSA assumption. For UC commitments, we show that existence of a UC commitment scheme in the CRS model (interactive or not) implies key exchange and - for a uniform reference string - even implies oblivious transfer. This indicates that UC commitment is a strictly stronger primitive than NM. Finally, we show that our strong RSA based construction can be used to improve the most efficient known UC commitment scheme so it can work with a CRS of size independent of the number of players, without loss of efficiency.
We consider non-malleable (NM) and universally composable (UC) commitment schemes in the common reference string (CRS) model. We show how to construct non-interactive NM commitments that remain non-malleable even if the adversary has access to an arbitrary number of commitments from honest players - rather than one, as in several previous schemes. We show this is a strictly stronger security notion. Our construction is the first non-interactive scheme achieving this that can be based on the minimal assumption of existence of one-way functions. But it can also be instantiated in a very efficient version based on the strong RSA assumption. For UC commitments, we show that existence of a UC commitment scheme in the CRS model (interactive or not) implies key exchange and - for a uniform reference string - even implies oblivious transfer. This indicates that UC commitment is a strictly stronger primitive than NM. Finally, we show that our strong RSA based construction can be used to improve the most efficient known UC commitment scheme so it can work with a CRS of size independent of the number of players, without loss of efficiency.
We present a unified framework for obtaining general secure computation that achieves adaptive-Universally Composable (UC)-security. Our framework captures essentially all previous results on adaptive concurrent secure computation, both in relaxed models (e.g., quasi-polynomial time simulation), as well as trusted setup models (e.g., the CRS model, the imperfect CRS model). This provides conceptual simplicity and insight into what is required for adaptive and concurrent security, as well as yielding improvements to set-up assumptions and/or computational assumptions. Moreover, using our framework we provide first constructions of concurrent secure computation protocols that are adaptively secure in the timing model, and in the non-uniform simulation model. Conceptually, our framework can be viewed as an adaptive analogue to the recent work of Lin, Pass and Venkitasubramaniam [STOC ‘09], who considered only non-adaptive adversaries. Their main insight was that stand-alone non-malleability was sufficient for UC-security. A main conceptual contribution of this work is, quite surprisingly, that it is indeed the case even when considering adaptive security. A key element in our construction is a commitment scheme that satisfies a new notion of nonmalleability.
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.
We provide the first construction of a concurrent and non-malleable zero knowledge argument for every language in NP. We stress that our construction is in the plain model with no common random string, trusted parties, or super-polynomial simulation. That is, we construct a zero knowledge protocol Pi such that for every polynomial-time adversary that can adaptively and concurrently schedule polynomially many executions of Pi, and corrupt some of the verifiers and some of the provers in these sessions, there is a polynomial-time simulator that can simulate a transcript of the entire execution, along with the witnesses for all statements proven by a corrupt prover to an honest verifier Our security model is the traditional model for concurrent zero knowledge, where the statements to be proven by the honest provers are fixed in advance and do not depend on the previous history (but can be correlated with each other); corrupted provers, of course, can chose the statements adaptively. We also prove that there exists some functionality F (a combination of zero knowledge and oblivious transfer) such that it is impossible to obtain a concurrent non-malleable protocol for F in this model. Previous impossibility results for composable protocols ruled out existence of protocols for a wider class of functionalities {including zero knowledge!) but only if these protocols were required to remain secure when executed concurrently with arbitrarily chosen different protocols (Lindell, FOCS 2003) or if these protocols were required to remain secure when the honest parties' inputs in each execution are chosen adaptively based on the results of previous executions (Lindell, TCC2004). We obtain an Otilde(n) -round protocol under the assumption that one-to-one one-way functions exist. This can be improved to Otilde(k log n) rounds under the assumption that there exist k-round statistically hiding commitment schemes. Our protocol is a black-box zero knowledge protocol