Abstract
In this paper we explore a powerful extension of the notion of pseudo-free groups, proposed by Rivest at TCC 2004. We identify, motivate, and study pseudo-freeness in face of adaptive adversaries who may learn solutions to other non-trivial equations before having to solve a new non-trivial equation.
We present a novel, carefully crafted definition of adaptive pseudo-freeness that walks a fine line between being too weak and being unsatisfiable. We show that groups that satisfy our definition yield, via a generic construction, digital and network coding signature schemes.
Finally, we obtain concrete constructions of such schemes in the RSA group by showing this group to be adaptive pseudo-free. In particular, we demonstrate the generality of our framework for signatures by showing that most existing schemes are instantiations of our generic construction.
A full version of this paper is available at http://eprint.iacr.org/2011/053
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
Abadi, M., Rogaway, P.: Reconciling two views of cryptography (the computational soundness of formal encryption). Journal of Cryptology 20(3), 395 (2007)
Backes, M., Pfitzmann, B., Waidner, M.: A composable cryptographic library with nested operations. In: ACM CCS 2003, Washington D.C., USA, October 27-30, pp. 220–230. ACM Press, New York (2003)
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM CCS 1993, Fairfax, Virginia, USA, November 3-5, pp. 62–73. ACM Press, New York (1993)
Boneh, D., Freeman, D., Katz, J., Waters, B.: Signing a linear subspace: Signature schemes for network coding. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 68–87. Springer, Heidelberg (2009)
Cachin, C., Micali, S., Stadler, M.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999)
Camenisch, J., Lysyanskaya, A.: A signature scheme with efficient protocols. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol. 2576, pp. 268–289. Springer, Heidelberg (2003)
Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: 42nd FOCS, Las Vegas, Nevada, USA, October 14-17, pp. 136–145. IEEE Computer Society Press, Los Alamitos (2001)
Cramer, R., Shoup, V.: Signature schemes based on the strong RSA assumption. In: ACM CCS 1999, Kent Ridge Digital Labs, Singapore, November 1-4, pp. 46–51. ACM Press, New York (1999)
Dolev, D., Yao, A.C.: On the security of public key protocols. In: FOCS, pp. 350–357 (1981)
Fischlin, M.: The Cramer-Shoup strong-RSA signature scheme revisited. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 116–129. 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)
Gennaro, R., Katz, J., Krawczyk, H., Rabin, T.: Secure network coding over the integers. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 142–160. Springer, Heidelberg (2010)
Hofheinz, D., Kiltz, E.: Programmable hash functions and their applications. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 21–38. Springer, Heidelberg (2008)
Hohenberger, S.: The cryptographic impact of groups with infeasible inversion. Master’s thesis, Massachusetts Institute of Technology, EECS Dept. (2003)
Krawczyk, H., Rabin, T.: Chameleon signatures. In: NDSS 2000, San Diego, California, USA, February 2-4. The Internet Society, San Diego (2000)
Micciancio, D.: The RSA group is pseudo-free. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 387–403. Springer, Heidelberg (2005)
Micciancio, D., Warinschi, B.: Soundness of formal encryption in the presence of active adversaries. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 133–151. Springer, Heidelberg (2004)
Rivest, R.L.: On the notion of pseudo-free groups. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 505–521. Springer, Heidelberg (2004)
Zhu, H.: New digital signature scheme attaining immunity to adaptive chosen-message attack. Chinese Journal of Electronics 10(4), 484–486 (2001)
H. Zhu. A formal proof of Zhu’s signature scheme. Cryptology ePrint Archive, Report 2003/155 (2003), http://eprint.iacr.org/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 International Association for Cryptologic Research
About this paper
Cite this paper
Catalano, D., Fiore, D., Warinschi, B. (2011). Adaptive Pseudo-free Groups and Applications. In: Paterson, K.G. (eds) Advances in Cryptology – EUROCRYPT 2011. EUROCRYPT 2011. Lecture Notes in Computer Science, vol 6632. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20465-4_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-20465-4_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20464-7
Online ISBN: 978-3-642-20465-4
eBook Packages: Computer ScienceComputer Science (R0)