Abstract
We strengthen the foundations of deterministic public-key encryption via definitional equivalences and standard-model constructs based on general assumptions. Specifically we consider seven notions of privacy for deterministic encryption, including six forms of semantic security and an indistinguishability notion, and show them all equivalent. We then present a deterministic scheme for the secure encryption of uniformly and independently distributed messages based solely on the existence of trapdoor one-way permutations. We show a generalization of the construction that allows secure deterministic encryption of independent high-entropy messages. Finally we show relations between deterministic and standard (randomized) encryption.
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
Bellare, M.: The Goldreich-Levin Theorem (manuscript), http://www-cse.ucsd.edu/users/mihir/papers/gl.pdf
Bellare, M., Boldyreva, A., Micali, S.: Public-key encryption in a multi-user setting: Security proofs and improvements. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 259–274. Springer, Heidelberg (2000)
Bellare, M., Boldyreva, A., O’Neill, A.: Deterministic and efficiently searchable encryption. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 535–552. Springer, Heidelberg (2007)
Bellare, M., Fischlin, M., O’Neill, A., Ristenpart, T.: Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles. Full version of this paper. IACR ePrint archive (2008) http://eprint.iacr.org/
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: Conference on Computer and Communications Security – CCS 1993, pp. 62–73. ACM, New York (1993)
Bellare, M., Rogaway, P.: Robust computational secret sharing and a unified account of classical secret-sharing goals. In: Conference on Computer and Communications Security – CCS 2007, pp. 172–184. ACM, New York (2007)
Bellare, M., Rogaway, P.: The security of triple encryption and a framework for code-based game-playing proofs. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 409–426. Springer, Heidelberg (2006)
Bellare, M., Sahai, A.: Non-malleable encryption: Equivalence between two notions, and an indistinguishability-based characterization. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 519–536. Springer, Heidelberg (1999)
Blum, L., Blum, M., Shub, M.: A simple unpredictable pseudo-random number generator. SIAM Journal on Computing 15, 364–383 (1986)
Blum, M., Goldwasser, S.: An efficient probabilistic public-key encryption scheme which hides all partial information. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 289–302. Springer, Heidelberg (1984)
Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudorandom bits. SIAM Journal on Computing 13, 850–864 (1984)
Boldyreva, A., Fehr, S., O’Neill, A.: On notions of security for deterministic encryption, and efficient constructions without random oracles. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 335–359. Springer, Heidelberg (2008)
Boneh, D., Di Crescenzo, G., Ostrovsky, R., Persiano, G.: Public key encryption with keyword search. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 506–522. Springer, Heidelberg (2004)
Canetti, R.: Towards realizing random oracles: Hash functions that hide all partial information. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 455–469. Springer, Heidelberg (1997)
Canetti, R., Micciancio, D., Reingold, O.: Perfectly one-way probabilistic hash functions (Preliminary version). In: Symposium on the Theory of Computation – STOC 1998, pp. 131–141 (1998)
Damgaard, I., Hofheinz, D., Kiltz, E., Thorbek, R.: Public-key encryption with non-interactive opening. In: Malkin, T. (ed.) CT-RSA 2008. LNCS, vol. 4964, pp. 239–255. Springer, Heidelberg (2008)
Desrosiers, S.: Entropic security in quantum cryptography. arXiv e-Print quant-ph/0703046 (2007), http://arxiv.org/abs/quant-ph/0703046
Desrosiers, S., Dupuis, F.: Quantum entropic security and approximate quantum encryption. arXiv e-Print quant-ph/0707.0691 (2007), http://arxiv.org/abs/0707.0691
Dodis, Y., Smith, A.: Entropic security and the encryption of high entropy messages. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 556–577. Springer, Heidelberg (2005)
El Gamal, T.: A public-key cryptosystem and a signature scheme based on discrete logarithms. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985)
Goldreich, O.: A uniform complexity treatment of encryption and zero-knowledge. Journal of Cryptology 6, 21–53 (1993)
Goldreich, O., Levin, L.: A hard-core predicate for all one-way functions. In: Symposium on the Theory of Computation – STOC 1989, pp. 25–32. ACM, New York (1989)
Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and Systems Sciences 28(2), 412–426 (1984)
Micali, S., Rackoff, C., Sloan, R.: The notion of security for probabilistic cryptosystems. SIAM Journal on Computing 17(2), 412–426 (1988)
Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: Symposium on the Theory of Computing – STOC 2008, pp. 187–196. ACM, New York (2008)
Russell, A., Wang, H.: How to fool an unbounded adversary with a short key. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 133–148. Springer, Heidelberg (2002)
Song, D., Wagner, D., Perrig, A.: Practical techniques for searches on encrypted data. In: Symposium on Security and Privacy, pp. 44–55. IEEE, Los Alamitos (2000)
Yao, A.: Theory and applications of trapdoor functions. In: Symposium on Foundations of Computer Science – FOCS 1982, pp. 80–91. IEEE, Los Alamitos (1982)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bellare, M., Fischlin, M., O’Neill, A., Ristenpart, T. (2008). Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles. In: Wagner, D. (eds) Advances in Cryptology – CRYPTO 2008. CRYPTO 2008. Lecture Notes in Computer Science, vol 5157. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85174-5_20
Download citation
DOI: https://doi.org/10.1007/978-3-540-85174-5_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85173-8
Online ISBN: 978-3-540-85174-5
eBook Packages: Computer ScienceComputer Science (R0)