Abstract
Kurosawa showed how one could design multi-receiver encryption schemes achieving savings in bandwidth and computation relative to the naive methods. We broaden the investigation. We identify new types of attacks possible in multi-recipient settings, which were overlooked by the previously suggested models, and specify an appropriate model to incorporate these types of attacks. We then identify a general paradigm that underlies his schemes and also others, namely the re-use of randomness: ciphertexts sent to different receivers by a single sender are computed using the same underlying coins. In order to avoid case by case analysis of encryption schemes to see whether they permit secure randomness re-use, we provide a condition, or test, that when applied to an encryption scheme shows whether or not the associated randomness re-using version of the scheme is secure. As a consequence, our test shows that randomness re-use is secure in the strong sense for asymmetric encryption schemes such as El Gamal, Cramer-Shoup, DHIES, and Boneh and Franklin's escrow El Gamal.
Chapter PDF
Similar content being viewed by others
References
O. Baudron, D. Pointcheval and J. Stern, “Extended notions of security for multicast public key cryptosystems.” ICALP 2000 86, 87, 91, 92, 93
M. Abdalla, M. Bellare, and P. Rogaway, “The Oracle Diffie-Hellman Assumptions and an Analysis of DHIES,” CT-RSA 01, Lecture Notes in Computer Science Vol. 2020, D. Naccache ed, Springer-Verlag, 2001. 88, 96
M. Bellare, A. Boldyreva, and S. Micali, “Public-key Encryption in a Multi-User Setting: Security Proofs and Improvements,” Advances in Cryptology–Eurocrypt’ 00, LNCS Vol. 1807, B. Preneel ed., Springer-Verlag, 2000 86, 87, 88, 89, 91, 92, 93, 95
M. Bellare, A. Boldyreva, and J. Staddon “Randomness Re-Use in Multi-Recipient Encryption Schemes”, Full version of this paper. Available at http:// www-cse.ucsd.edu/users/aboldyre 89, 90, 94, 95, 96, 97
M. Bellare, A. Desai, D. Pointcheval and P. Rogaway, “Relations among notions of security for public-key encryption schemes,” Advances in Cryptology–Crypto’ 98, LNCS Vol. 1462, H. Krawczyk ed., Springer-Verlag, 1998.
M. Bellare and O. Goldreich, “On defining proofs of knowledge,” Advances in Cryptology–Crypto’ 92, LNCS Vol. 740, E. Brickell ed., Springer-Verlag, 1992. 94
S. Berkovits, “How to Broadcast a Secret”, Advances in Cryptology–Eurocrypt’ 91, LNCS Vol. 547, D. Davies ed., Springer-Verlag, 1991.
M. Blum and S. Micali, “How to generate cryptographically strong sequences of pseudo-random bits,” SIAM J. on Computing Vol. 13, No. 4, November 1984.
D. Boneh. “Simpli.ed OAEP for the RSA and Rabin Functions,” Advances in Cryptology–Crypto’ 01, LNCS Vol. 2139, J. Kilian ed., Springer-Verlag, 2001.
D. Boneh and M. Franklin. “Identity-based encryption from the Weil Pairing,” Advances in Cryptology–Crypto’ 01, LNCS Vol. 2139, J. Kilian ed., Springer-Verlag, 2001. 89, 97
J. Camenisch and M. Michels, “Confirmer signature schemes secure against adaptive adversaries,” Advances in Cryptology–Eurocrypt’ 00, LNCS Vol. 1807, B. Preneel ed., Springer-Verlag, 2000.
R. Canetti,, “Towards Realizing Random Oracles: Hash Functions that Hide All Partial Information,”,Advances in Cryptology–Crypto’ 97, LNCS Vol. 1294, B. Kaliski ed., Springer-Verlag, 1997 95
R. Cramer and V. Shoup, “A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack,” Advances in Cryptology–Crypto’ 98, LNCS Vol. 1462, H. Krawczyk ed., Springer-Verlag, 1998. 86, 88, 95, 96
T. ElGamal, “A public key cryptosystem and signature scheme based on discrete logarithms,” IEEE Transactions on Information Theory, vol 31, 1985.
A. Fiat and M. Naor, “Broadcast Encryption”, Advances in Cryptology–Crypto’ 93, LNCS Vol. 773, D. Stinson ed., Springer-Verlag, 1993.
E. Fujisaki, T. Okamoto, D. Pointcheval and J. Stern, “RSA-OAEP is Secure under the RSA Assumption,” Advances in Cryptology–Crypto’ 01, LNCS Vol. 2139, J. Kilian ed., Springer-Verlag, 2001. 91
S. Goldwasser and S. Micali, “Probabilistic encryption,” Journal of Computer and System Science, Vol. 28, 1984, pp. 270–299.
O. Goldreich, S. Goldwasser and S. Micali, “How to construct random functions,”Journal of the ACM, Vol. 33, No. 4, 210–217, (1986).
J. HÅstad, “Solving simultaneous modular equations of low degree,” SIAM J. on Computing Vol. 17, No. 2, April 1988. 87
J. HÅstad, R. Impagliazzo, L. Levin, and M. Luby, “A pseudorandom generation from any one-way function,” SIAM Journal on Computing, Vol. 28, No. 4, 1364–1396, 1999.
R. Impagliazzo and M. Luby, “One-way functions are essential for complexity based cryptography,” Proceedings of the 30th Symposium on Foundations of Computer Science, IEEE, 1989
K. Kurosawa, “Multi-Recipient Public-Key Encryption with Shortened Ciphertext,” Proceedings of the Fifth International workshop on practice and theory in Public Key Cryptography (PKC’02). 86, 87, 88, 89, 92, 93, 95, 96
S. Micali, C. Rackoff and R. H. Sloan, “The notion of security for probabilistic cryptosystems,” Advances in Cryptology–Crypto’ 86, LNCS Vol. 263, A. Odlyzko ed., Springer-Verlag, 1986.
M. Naor and O. Reingold, “Number-theoretic constructions of efficient pseudo-random functions,” Proceedings of the 38th Symposium on Foundations of Computer Science, IEEE, 1997. 88, 95
C. Rackoff and D. Simon, “Non-interactive zero-knowledge proof of knowledge and chosen-ciphertext attack,” Advances in Cryptology–Crypto’ 91, LNCS Vol. 576, J. Feigenbaum ed., Springer-Verlag, 1991.
V. Shoup, “On formal models for secure key exchange, ” Theory of Cryptography Library Record 99-12, http://philby.ucsd.edu/cryptolib/. 88
M. Stadler, “Publicly verifiable secret sharing,” Advances in Cryptology–Eurocrypt’ 96, LNCS Vol. 1070, U. Maurer ed., Springer-Verlag, 1996. 88
Y. Tsiounis and M. Yung, “On the security of El Gamal based encryption,” Proceedings of the First International workshop on practice and theory in Public Key Cryptography (PKC’98), Lecture Notes in Computer Science Vol. 1431, H. Imai and Y. Zheng eds., Springer-Verlag, 1998. 95
D. Wallner, E. Harder and R. Agee, “Key Management for Multicast: Issues and Architectures,” Internet Request for Comments, 2627 (June 1999). Available http://ftp.ietf.org/rfc/rfc2627.txt.
A. C. Yao. “Theory and application of trapdoor functions,” Proceedings of the 23rd Symposium on Foundations of Computer Science, IEEE, 1982
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bellare, M., Boldyreva, A., Staddon, J. (2003). Randomness Re-use in Multi-recipient Encryption Schemeas. In: Desmedt, Y.G. (eds) Public Key Cryptography — PKC 2003. PKC 2003. Lecture Notes in Computer Science, vol 2567. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36288-6_7
Download citation
DOI: https://doi.org/10.1007/3-540-36288-6_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00324-3
Online ISBN: 978-3-540-36288-3
eBook Packages: Springer Book Archive