Abstract
We present efficient non-malleable commitment schemes based on standard assumptions such as RSA and Discrete-Log, and under the condition that the network provides publicly available RSA or Discrete-Log parameters generated by a trusted party. Our protocols require only three rounds and a few modular exponentiations. We also discuss the difference between the notion of non-malleable commitment schemes used by Dolev, Dwork and Naor [DDN00] and the one given by Di Crescenzo, Ishai and Ostrovsky [DIO98].
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M. Bellare AND O. Goldreich: On Defining Proofs of Knowledge, Advances in Cryptology — Proceedings Crypto’ 92, Lecture Notes in Computer Science, vol. 740, pp. 390–420, Springer Verlag, 1993.
M. Bellare AND P. Rogaway: Optimal Asymmetric Encryption, Advances in Cryptology — Proceedings Eurocrypt’ 94, Lecture Notes in Computer Science, vol. 950, pp. 92–111, Springer Verlag, 1993.
M. Bellare AND P. Rogaway: Random Oracles are Practical: a Paradigm for Designing Efficient Protocols, First ACM Conference on Computer and Communication Security, ACM Press, pp. 62–73, 1993.
D. Boneh: Finding Smooth Integers Using CRT Decoding, to appear in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), ACM Press, 2000.
G. Brassard, D. Chaum AND C. Crépeau: Minimum Disclosure Proofs of Knowledge, Journal of Computer and Systems Science, vol. 37(2), pp. 156–189, 1988.
R. Cramer AND V. Houp: A Practical Public Key Cryptosystem Provable Secure Against Adaptive Chosen Ciphertext Attack, Advances in Cryptology — Proceedings Crypto’ 98, Lecture Notes in Computer Science, vol. 1492, pp. 13–25, Springer Verlag, 1998.
R. Cramer AND V. Shoup: Signature Schemes Based on the Strong RSA Assumption, ACM Conference on Computer and Communication Security, ACM Press, 1999.
G. Di Crescenzo, Y. Ishai AND R. Ostrovsky: Non-interactive and Non-Malleable Commitment, Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 141–150, ACM Press, 1998.
D. Dolev, C. Dwork AND M. Naor: Non-Malleable Cryptography, manuscript, to appear in SIAM Jornal on Computing, January 2000. Preliminary version in Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pp. 542–552, ACM Press, 1991.
U. Feige, A. Fiat AND A. Shamir: Zero-Knowledge Proofs of Identity, Journal of Cryptology, vol. 1(2), pp. 77–94, Springer-Verlag, 1988.
A. Fiat AND A. Shamir: Witness Indistinguishable and Witness Hiding Protocols Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing (STOC), pp. 416–426, ACM Press, 1990.
O. Goldreich: Foundations of Cryptography, Fragments of a Book, Version 2.03, 1998.
O. Goldreich, D. Ron AND M. Sudan: Chinese Remainder With Errors, Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 225–234, ACM Press, 1999.
D.E. Knuth: Seminumerical Algorithms, The Art of Computer Programming, vol. 2, 3rd edition, Addison Wesley, 1998.
Y. Lindell: Personal communication, based on work on authenticated key-exchange with Oded Goldreich. May 2000.
U. Maurer: Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters, Journal of Cryptology, vol. 8, pp. 123–155, Springer-Verlag, 1995.
T. Okamoto: Provable Secure and Practical Identification Schemes and Corresponding Signature Schemes, Advances in Cryptology — Proceedings Crypto’ 92, Lecture Notes in Computer Science, vol. 740, pp. 31–53, Springer Verlag, 1993.
T.P. Pedersen: Non-Interactive and Information-Theoretical Secure Verifiable Secret Sharing, Crypto’ 91, Lecture Notes in Computer Science, Vol. 576, Springer-Verlag, pp. 129–140, 1991.
R. Rivest, A. Shamir AND L. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptoystems, Communication of the ACM, vol. 21(2), pp. 120–126, 1978.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fischlin, M., Fischlin, R. (2000). Efficient Non-malleable Commitment Schemes. In: Bellare, M. (eds) Advances in Cryptology — CRYPTO 2000. CRYPTO 2000. Lecture Notes in Computer Science, vol 1880. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44598-6_26
Download citation
DOI: https://doi.org/10.1007/3-540-44598-6_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67907-3
Online ISBN: 978-3-540-44598-2
eBook Packages: Springer Book Archive