Abstract
In 1994 Benaloh and de Mare introduced the notion of one way accumulators that allow to construct efficient protocols for proving membership in a list and related problems like time stamping and authentication. As required by Benaloh et al. unlike in signature based protocols no central trusted authority is (should be) needed. Accumulator based protocols do further improve on hash tree based protocols for proving membership in a list as verification and storage requirements are independent of the number of items in the list. Benaloh’s et al. accumulator construction was based on exponentiation modulo a RSA modulus N=PQ.
As already noted by Benaloh et al. the party (or parties) who generated the needed RSA modulus N during system set up knows a factorization of N. This knowledge allows this party to completely bypass the security of accumulator based protocols. For example a time stamping agency could forge time stamps for arbitrary documents.
Thus these parties need to be trusted in (at least) two ways. First that they do not abuse their knowledge of the trapdoor and secondly to have had adequate security in place during system set up, which prevented outside attackers from getting hold of P and Q.
In this paper we describe a way to construct (generalized) RSA moduli of factorization unknown to anybody. This yields (theoretically) efficient accumulators such that “nobody knows a trapdoor” and the two above mentioned trust requirements in the parties who set up the system can be removed.
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
Baric, N., Pfitzmann, B.: Collision-free accumulators and fail-stop signature schemes without trees. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 480–494. Springer, Heidelberg (1997)
Benaloh, J., de Mare, M.: One-way accumulators: A decentralized alternative to digital signatures. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 274–285. Springer, Heidelberg (1994)
Camenisch, J., Michels, M.: A group signature scheme with improved efficiency. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 160–174. Springer, Heidelberg (1998)
Fujisaki, E., Okamoto, T.: Statistical zero knowledge protocols to prove modular polynomial relations. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 16–30. Springer, Heidelberg (1997)
Hardy, G., Wright, E.: An introduction to the theory of numbers, 5th edn. Oxford University Press, Oxford (1985)
Jakobsson, M., Yung, M.: Revokable and versatile electronic mony. In: Neuman, C. (ed.) 3rd ACM Conference on Computer and Communications Security, New Delhi, India, pp. 76–87. ACM Press, New York (1996)
Merkle, R.: Protocols for public key cryptosystems. In: IEEE (ed.) Proceedings of the 1980 Symposium on Security and Privacy, Oakland, California, April 14-16, IEEE Computer Society Press, Los Alamitos (1980)
Nyberg, K.: Fast accumulated hashing. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 83–87. Springer, Heidelberg (1996)
Sander, T., Ta-Shma, A.: Auditable, anonymous electronic cash. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, p. 555. Springer, Heidelberg (1999)
Shamir, A.: On the generation of cryptographically strong pseudorandom sequen-ces. ACM Transactions on Computer Systems 1(1), 38–44 (1983)
von Solms, S., Naccache, D.: On blind signatures and perfect crimes. Computers and Security 11(6), 581–583 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sander, T. (1999). Efficient Accumulators without Trapdoor Extended Abstract. In: Varadharajan, V., Mu, Y. (eds) Information and Communication Security. ICICS 1999. Lecture Notes in Computer Science, vol 1726. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-47942-0_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-47942-0_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66682-0
Online ISBN: 978-3-540-47942-0
eBook Packages: Springer Book Archive