Abstract
We review the representation problem based on factoring and show that this problem gives rise to alternative solutions to a lot of cryptographic protocols in the literature. And, while the solutions so far usually either rely on the RSA problem or the intractability of factoring integers of a special form (e.g., Blum integers), the solutions here work with the most general factoring assumption. Protocols we discuss include identification schemes secure against parallel attacks, secure signatures, blind signatures and (non-malleable) commitments.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Bellare, M. Fischlin, S. Goldwasser and S. Micali: Identification Protocols Secure Against Reset Attacks, Eurocrypt 2001, Lecture Notes in Computer Science, vol. 2045, pp. 495–511, Springer Verlag, 2001.
M. Bellare and O. Goldreich: On Defining Proofs of Knowledge, Crypto’ 92, Lecture Notes in Computer Science, vol. 740, pp. 390–420, 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.
S. Brands: Rapid Demonstration of Linear Relations Connected by Boolean Operators, Eurocrypt’ 97, Lecture Notes in Computer Science, vol. 1233, pp. 318–333, Springer-Verlag, 1997.
G. Brassard, D. Chaum and C. CrÉpeau: Minimum Disclosure Proofs of Knowledge, Journal Computing System Science, vol. 37(2), pp. 156–189, 1988.
D. Boneh and R. Venkatesan: Breaking RSA may Not be Equivalent to Factoring, Eurocrypt’ 98, Lecture Notes in Computer Science, vol. 1403, pp. 59–71, Springer Verlag, 1998.
G. Di Crescenzo, J. Katz, R. Ostrovsky and A. Smith: Efficient And Non-Interactive Non-Malleable Commitment, Eurocrypt 2001, Lecture Notes in Computer Science, vol. 2045, pp. 40–59, Springer Verlag, 2001.
I. DamgÅrd: Practical and Provable Secure Release of a Secret and Exchange of Signature, Journal of Cryptology, vol. 8, pp. 201–222, 1995.
D. Dolev, C. Dwork and M. Naor: Nonmalleable Cryptography, SIAM Journal on Computing, vol. 30(2), pp. 391–437, 2000.
U. Feige, A. Fiat and A. Shamir: Zero-Knowledge Proofs of Identity, Journal of Cryptology, vol. 1(2), pp. 77–94, 1988.
A. Fiat and A. Shamir: How to Prove Yourself: Practical Solutions to Identification and Signature Schemes, Crypto’ 86, Lecture Notes in Computer Science, vol. 263, Springer-Verlag, pp. 186–194, 1986.
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.
M. Fischlin and R. Fischlin: Efficient Non-Malleable Commitment Schemes, Crypto 2000, Lecture Notes in Computer Science, vol. 1880, pp. 414–432, Springer Verlag, 2000.
L.C. Guillou and J.-J. Quisquater: A Practical Zero-Knowledge Protocol Fitted to Security Microprocessors Minimizing Both Transmission and Memory, Eurocrypt’ 88, Lecture Notes in Computer Science, vol. 330, pp. 123–129, Springer Verlag, 1988.
S. Goldwasser, S. Micali and R.L. Rivest: A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, SIAM Journal of Computing, vol. 17(2), pp. 281–308, 1988.
S. Halevi: Efficient Commitment Schemes with Bounded Sender and Unbounded Receiver, Journal of Cryptology, vol. 12(2), pp. 77–90, 1999.
M. Naor and M. Yung: Universal Oneway Hash Functions and Their Cryptographic Applications, Proceedings of the 21st Annual ACM Symposium on the Theory of Computing (STOC), pp. 33–43, ACM Press, 1989.
H. Ong and C.P. Schnorr: Fast Signature Generation with as Fiat-Shamir-Like Scheme, Eurocrypt’ 90, Lecture Notes in Computer Science, vol. 473, pp. 432–440, Springer Verlag, 1991.
K. Ohta and T. Okamoto: A Modification of the Fiat-Shamir Scheme, Crypto’ 88, Lecture Notes in Computer Science, vol. 403, pp. 232–243, Springer Verlag, 1989.
T. Okamoto: Provable Secure and Practical Identification Schemes and Corresponding Signature Schemes, Crypto’ 92, Lecture Notes in Computer Science, vol. 740, pp. 31–53, Springer Verlag, 1993.
D. Pointcheval and J. Stern: New Blind Signatures Equivalent to Factorization, Proceedings of the 4th ACM Conference on Computer and Communications Security (CCS)’ 97, pp. 92–99, ACM Press, 1997.
D. Pointcheval and J. Stern: Security Arguments for Digital Signatures and Blind Signatures, Journal of Cryptology, vol. 13(3), pp. 361–396, 2000.
R.L. Rivest, A. Shamir and L. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, vol. 21, pp. 120–126, 1978.
C.P. Schnorr: Security of 2 t -Root Identification and Signatures, Crypto’ 96, Lecture Notes in Computer Science, vol. 1109, pp. 143–156, Springer Verlag, 1996.
C.P. Schnorr: Erratum: Security of 2 t -Root Identification and Signatures, in Crypto’ 97, Lecture Notes in Computer Science, vol 1294, page 540, Springer Verlag, 1997.
V. Shoup: On the Security of a Practical Identification Scheme, Journal of Cryptology, vol. 12, pp. 247–260, 1999.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fischlin, M., Fischlin, R. (2002). The Representation Problem Based on Factoring. In: Preneel, B. (eds) Topics in Cryptology — CT-RSA 2002. CT-RSA 2002. Lecture Notes in Computer Science, vol 2271. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45760-7_8
Download citation
DOI: https://doi.org/10.1007/3-540-45760-7_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43224-1
Online ISBN: 978-3-540-45760-2
eBook Packages: Springer Book Archive