Abstract
Cryptographic accumulators are well-known to be useful in many situations. However, the most efficient accumulator (the RSA accumulator) it is not secure against a certificate authority who has herself selected the RSA modulus n. We generalize previous work and define the root accumulator in modules over Euclidean rings. We prove that the root accumulator is secure under two different pairs of assumptions on the module family and on the used hash function. Finally, we propose a new instantiation of the root accumulator, based on class groups of imaginary quadratic order, that combines the best properties of previous solutions. It has short (non)membership proofs like the RSA accumulator, and at the same time it is secure against a malicious certificate authority. Up to this point, this seems to be the only unique application of class groups of imaginary quadratic orders, and we hope that this paper will motivate more research on cryptography in the said groups.
Chapter PDF
Similar content being viewed by others
References
Barić, 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.C., 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)
Buchmann, J., Hamdy, S.: A Survey on IQ Cryptography. Technical Report TI-4/01, TU Darmstadt, Fachbereich Informatik (March 21, 2001)
Buchmann, J.A., Williams, H.C.: A Key-exchange System Based on Imaginary Quadratic Fields. Journal of Cryptology 1(2), 107–118 (1988)
Buldas, A., Laud, P., Lipmaa, H.: Accountable Certificate Management Using Undeniable Attestations. In: Jajodia, S., Samarati, P. (eds.) ACM CCS 2000, Athens, Greece, November 2-4, pp. 9–18. ACM Press (2000)
Buldas, A., Laud, P., Lipmaa, H.: Eliminating Counterevidence with Applications to Accountable Certificate Management. Journal of Computer Security 10(3), 273–296 (2002)
Buldas, A., Laud, P., Lipmaa, H., Villemson, J.: Time-Stamping with Binary Linking Schemes. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 486–501. Springer, Heidelberg (1998)
Buldas, A., Lipmaa, H., Schoenmakers, B.: Optimally Efficient Accountable Time-Stamping. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 293–305. Springer, Heidelberg (2000)
Camacho, P., Hevia, A., Kiwi, M., Opazo, R.: Strong Accumulators from Collision-Resistant Hashing. In: Wu, T.-C., Lei, C.-L., Rijmen, V., Lee, D.-T. (eds.) ISC 2008. LNCS, vol. 5222, pp. 471–486. Springer, Heidelberg (2008)
Camenisch, J., Kohlweiss, M., Soriente, C.: An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 481–500. Springer, Heidelberg (2009)
Camenisch, J., Lysyanskaya, A.: Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 61–76. Springer, Heidelberg (2002)
Cohen, H.: A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics. Springer (1995)
Damgård, I., Fujisaki, E.: A Statistically-Hiding Integer Commitment Scheme Based on Groups with Hidden Order. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 125–142. Springer, Heidelberg (2002)
Damgård, I., Koprowski, M.: Generic Lower Bounds for Root Extraction and Signature Schemes in General Groups. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 256–271. Springer, Heidelberg (2002)
Gennaro, R., Halevi, S., Rabin, T.: Secure Hash-and-Sign Signatures without the Random Oracle. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 123–139. Springer, Heidelberg (1999)
Groth, J., Sahai, A.: Efficient Non-interactive Proof Systems for Bilinear Groups. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415–432. Springer, Heidelberg (2008)
Haber, S., Stornetta, W.S.: How to Time-Stamp a Digital Document. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 437–455. Springer, Heidelberg (1991)
Hamdy, S.: Computations in Class Groups of Imaginary Quadratic Number Fields. In: Innovations in Information Technology, Dubai, UAE, November 19-21, pp. 1–5 (2006)
Hamdy, S., Möller, B.: Security of Cryptosystems Based on Class Groups of Imaginary Quadratic Orders. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 234–247. Springer, Heidelberg (2000)
Hühnlein, D., Takagi, T.: Reducing Logarithms in Totally Non-maximal Imaginary Quadratic Orders to Logarithms in Finite Fields. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 219–231. Springer, Heidelberg (1999)
Jacobson Jr., M.J.: Subexponential Class Group Computation in Quadratic Orders. PhD thesis, Technische Universität Darmstadt, Fachbereich Informatik, Darmstadt, Germany (1999)
Lenstra, A.K., Lenstra, J. H.W. (eds.): The Development of the Number Field Sieve. Lecture Notes in Mathematics, vol. 1554. Springer, Heidelberg (1993)
Li, J., Li, N., Xue, R.: Universal Accumulators with Efficient Nonmembership Proofs. In: Katz, J., Yung, M. (eds.) ACNS 2007. LNCS, vol. 4521, pp. 253–269. Springer, Heidelberg (2007)
Nguyen, L.: Accumulators from Bilinear Pairings and Applications. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 275–292. Springer, Heidelberg (2005)
Sander, T.: Efficient Accumulators without Trapdoor Extended Abstract. In: Varadharajan, V., Mu, Y. (eds.) ICICS 1999. LNCS, vol. 1726, pp. 252–262. Springer, Heidelberg (1999)
Sander, T., Ta-Shma, A., Yung, M.: Blind, Auditable Membership Proofs. In: Frankel, Y. (ed.) FC 2000. LNCS, vol. 1962, pp. 53–71. Springer, Heidelberg (2001)
Vollmer, U.: Asymptotically Fast Discrete Logarithms in Quadratic Number Fields. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 581–594. Springer, Heidelberg (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lipmaa, H. (2012). Secure Accumulators from Euclidean Rings without Trusted Setup. In: Bao, F., Samarati, P., Zhou, J. (eds) Applied Cryptography and Network Security. ACNS 2012. Lecture Notes in Computer Science, vol 7341. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31284-7_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-31284-7_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31283-0
Online ISBN: 978-3-642-31284-7
eBook Packages: Computer ScienceComputer Science (R0)