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

Based on RSA and Factoring

Chunhui Wu, Qin Li, Dongyang Long

Published Jan 1, 2015• 0 citations
OpenAlex

Abstract

Abstract—Non-malleability is an important property in commitment schemes. It can resist to the person-in-the-middle (PIM) attacks within the interaction. In this paper, we focus on the non-malleability in ID-based trapdoor commitments. We first give two constructions of (full) ID-based trapdoor commitment schemes based on RSA and Factoring assumptions respectively and then extend them to non-malleable schemes. The formal proofs show that our proposed schemes satisfy all the desired security properties.

Related papers

Efficient ID-based Non-Malleable Trapdoor Commitments Based on RSA and Factoring

Chunhui Wu, Qin Li, Dongyang Long

Journal of Communications•Jan 1, 2015•0 citations

Efficient and Non-Interactive Non-Malleable Commitment.

Giovanni Di Crescenzo, Jonathan I. Katz, Rafail Ostrovsky +1 more

. We present new constructions of non-malleable commitment schemes, in the public parameter model (where a trusted party makes parameters available to all parties), based on the discrete logarithm or RSA assumptions. The main features of our schemes are: they achieve near-optimal communication for arbitrarily-large messages and are noninteractive. Previous schemes either required (several rounds of) interaction or focused on achieving non-malleable commitment based on general assumptions and were thus efficient only when committing to a single bit. Although our main constructions are for the case of perfectly-hiding commitment, we also present a communication-efficient, non-interactive commitment scheme (based on general assumptions) that is perfectly binding. 1

•Jan 1, 2001•1 citation

A Straight-Line Extractable Non-malleable Commitment Scheme

Seigo Arita

Non-malleability is an important security property of commitment schemes. The property means security against the man-in-the-middle attack, and it is defined and proved in the simulation paradigm using the corresponding simulator. Many known non-malleable commitment schemes have the common drawback that their corresponding simulators do not work in a straight-line manner, requires rewinding of the adversary. Due to this fact, such schemes are proved non-malleable only in the stand-alone cases. In the multiple-instances setting, i.e., when the scheme is performed concurrently with many instances of itself, such schemes cannot be proved non-malleable. The paper shows an efficient commitment scheme proven to be non-malleable even in the multiple-instances setting, based on the KEA1 and DDH assumptions. Our scheme has a simulator that works in a straight-line manner by using the KEA1-extractor instead of the rewinding strategy.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jul 1, 2007•1 citation

Concurrent Non-Malleable Commitments

Rafael Pass, Alon Rosen

We present a non-malleable commitment scheme that retains its security properties even when concurrently executed a polynomial number of times. That is, a man-in-the-middle adversary who is simultaneously participating in multiple concurrent commitment phases of our scheme, both as a sender and as a receiver cannot make the values he commits to depend on the values he receives commitments to. Our result is achieved without assuming an a-priori bound on the number of executions and without relying on any set-up assumptions. Our construction relies on the existence of standard collision resistant hash functions and only requires a constant number of communication rounds.

Annual Symposium on Foundations of Computer Science•Nov 15, 2005•122 citations

Constant-round Non-Malleable Commitments from Any One-Way Function.

Huijia Lin, Rafael Pass

We show unconditionally that the existence of commitment schemes implies the existence of constant-round non-malleable commitments; earlier protocols required additional assumptions such as collision resistant hash functions or subexponential one-way functions. Our protocol also satisfies the stronger notions of concurrent non-malleability and robustness. As a corollary, we establish that constant-round non-malleable zero-knowledge arguments for NP can be based on one-way functions and constant-round secure multi-party computation can be based on enhanced trapdoor permutations; also here, earlier protocols additionally required either collision-resistant hash functions or subexponential one-way functions.

•Jan 1, 2010•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)•Jun 9, 2003•117 citations
Abstract—Non-malleability is an important property in commitment schemes. It can resist to the person-in-the-middle (PIM) attacks within the interaction. In this paper, we focus on the non-malleability in ID-based trapdoor commitments. We first give two constructions of (full) ID-based trapdoor commitment schemes based on RSA and Factoring assumptions respectively and then extend them to non-malleable schemes. The formal proofs show that our proposed schemes satisfy all the desired security properties.
. We present new constructions of non-malleable commitment schemes, in the public parameter model (where a trusted party makes parameters available to all parties), based on the discrete logarithm or RSA assumptions. The main features of our schemes are: they achieve near-optimal communication for arbitrarily-large messages and are noninteractive. Previous schemes either required (several rounds of) interaction or focused on achieving non-malleable commitment based on general assumptions and were thus efficient only when committing to a single bit. Although our main constructions are for the case of perfectly-hiding commitment, we also present a communication-efficient, non-interactive commitment scheme (based on general assumptions) that is perfectly binding. 1
Non-malleability is an important security property of commitment schemes. The property means security against the man-in-the-middle attack, and it is defined and proved in the simulation paradigm using the corresponding simulator. Many known non-malleable commitment schemes have the common drawback that their corresponding simulators do not work in a straight-line manner, requires rewinding of the adversary. Due to this fact, such schemes are proved non-malleable only in the stand-alone cases. In the multiple-instances setting, i.e., when the scheme is performed concurrently with many instances of itself, such schemes cannot be proved non-malleable. The paper shows an efficient commitment scheme proven to be non-malleable even in the multiple-instances setting, based on the KEA1 and DDH assumptions. Our scheme has a simulator that works in a straight-line manner by using the KEA1-extractor instead of the rewinding strategy.
We present a non-malleable commitment scheme that retains its security properties even when concurrently executed a polynomial number of times. That is, a man-in-the-middle adversary who is simultaneously participating in multiple concurrent commitment phases of our scheme, both as a sender and as a receiver cannot make the values he commits to depend on the values he receives commitments to. Our result is achieved without assuming an a-priori bound on the number of executions and without relying on any set-up assumptions. Our construction relies on the existence of standard collision resistant hash functions and only requires a constant number of communication rounds.
We show unconditionally that the existence of commitment schemes implies the existence of constant-round non-malleable commitments; earlier protocols required additional assumptions such as collision resistant hash functions or subexponential one-way functions. Our protocol also satisfies the stronger notions of concurrent non-malleability and robustness. As a corollary, we establish that constant-round non-malleable zero-knowledge arguments for NP can be based on one-way functions and constant-round secure multi-party computation can be based on enhanced trapdoor permutations; also here, earlier protocols additionally required either collision-resistant hash functions or subexponential one-way functions.
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.