Non-interactive and reusable non-malleable commitment schemes
- 9 June 2003
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 2003, 426-437
- https://doi.org/10.1145/780542.780605
Abstract
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.Keywords
This publication has 7 references indexed in Scilit:
- Universally composable two-party and multi-party secure computationPublished by Association for Computing Machinery (ACM) ,2002
- Prime NumbersPublished by Springer Science and Business Media LLC ,2001
- Nonmalleable CryptographySIAM Journal on Computing, 2000
- Non-interactive and non-malleable commitmentPublished by Association for Computing Machinery (ACM) ,1998
- One-way functions are necessary and sufficient for secure signaturesPublished by Association for Computing Machinery (ACM) ,1990
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989
- Limits on the provable consequences of one-way permutationsPublished by Association for Computing Machinery (ACM) ,1989