Weitere Artikel dieser Ausgabe durch Wischen aufrufen
Communicated by Rabin.
A preliminary version of this work appeared in Advances in Cryptology – EUROCRYPT ’12, pages 628–644, 2012. Most of this work was done at Microsoft Research Silicon Valley.
Gil Segev: Supported by the European Union’s 7th Framework Program (FP7) via a Marie Curie Career Integration Grant, by the Israel Science Foundation (Grant No. 483/13), by the Israeli Centers of Research Excellence (I-CORE) Program (Center No. 4/11), by the US-Israel Binational Science Foundation (Grant No. 2014632), and by a Google Faculty Research Award.
Motivated by applications in large storage systems, we initiate the study of incremental deterministic public-key encryption. Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O’Neill (CRYPTO ’07), provides an alternative to randomized public-key encryption in various scenarios where the latter exhibits inherent drawbacks. A deterministic encryption algorithm, however, cannot satisfy any meaningful notion of security for low-entropy plaintexts distributions, but Bellare et al. demonstrated that a strong notion of security can in fact be realized for relatively high-entropy plaintext distributions. In order to achieve a meaningful level of security, a deterministic encryption algorithm should be typically used for encrypting rather long plaintexts for ensuring a sufficient amount of entropy. This requirement may be at odds with efficiency constraints, such as communication complexity and computation complexity in the presence of small updates. Thus, a highly desirable property of deterministic encryption algorithms is incrementality: Small changes in the plaintext translate into small changes in the corresponding ciphertext. We present a framework for modeling the incrementality of deterministic public-key encryption. Our framework extends the study of the incrementality of cryptography primitives initiated by Bellare, Goldreich and Goldwasser (CRYPTO ’94). Within our framework, we propose two schemes, which we prove to enjoy an optimal tradeoff between their security and incrementality up to lower-order factors. Our first scheme is a generic method which can be based on any deterministic public-key encryption scheme, and, in particular, can be instantiated with any semantically secure (randomized) public-key encryption scheme in the random-oracle model. Our second scheme is based on the Decisional Diffie–Hellman assumption in the standard model. The approach underpinning our schemes is inspired by the fundamental “sample-then-extract” technique due to Nisan and Zuckerman (JCSS ’96) and refined by Vadhan (J. Cryptology ’04), and by the closely related notion of “locally computable extractors” due to Vadhan. Most notably, whereas Vadhan used such extractors to construct private-key encryption schemes in the bounded-storage model, we show that techniques along these lines can also be used to construct incremental public-key encryption schemes.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
M. Abadi, D. Boneh, I. Mironov, A. Raghunathan, and G. Segev. Message-locked encryption for lock-dependent messages. In Advances in Cryptology—RYPTO ’13, pp. 374–391, 2013.
M. Bellare, Z. Brakerski, M. Naor, T. Ristenpart, G. Segev, H. Shacham, and S. Yilek. Hedged public-key encryption: how to protect against bad randomness. In Advances in Cryptology—ASIACRYPT ’09, pp. 232–249, 2009.
M. Bellare, A. Boldyreva, and A. O’Neill. Deterministic and efficiently searchable encryption. In Advances in Cryptology—CRYPTO ’07, pp. 535–552, 2007.
M. Bellare, M. Fischlin, A. O’Neill, and T. Ristenpart. Deterministic encryption: definitional equivalences and constructions without random oracles. In Advances in Cryptology—CRYPTO ’08, pp. 360–378, 2008.
A. Boldyreva, S. Fehr, and A. O’Neill. On notions of security for deterministic encryption, and efficient constructions without random oracles. In Advances in Cryptology—CRYPTO ’08, pp. 335–359, 2008.
M. Bellare, O. Goldreich, and S. Goldwasser. Incremental cryptography: the case of hashing and signing. In Advances in Cryptology—CRYPTO ’94, pp. 216–233, 1994.
M. Bellare, O. Goldreich, and S. Goldwasser. Incremental cryptography and application to virus protection. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pp. 45–56, 1995.
D. Boneh, S. Halevi, M. Hamburg, and R. Ostrovsky. Circular-secure encryption from Decision Diffie–Hellman. In Advances in Cryptology—CRYPTO ’08, pp. 108–125, 2008.
M. Bellare, S. Keelveedhi, and T. Ristenpart. Message-locked encryption and secure deduplication. In Advances in Cryptology—EUROCRYPT ’13, pp. 296–312, 2013.
E. Buonanno, J. Katz, and M. Yung. Incremental unforgeable encryption. In Proceedings of the 8th International Workshop on Fast Software Encryption, pp. 109–124, 2001.
M. Bellare and D. Micciancio. A new paradigm for collision-free hashing: Incrementality at reduced cost. In Advances in Cryptology—EUROCRYPT ’97, pp. 163–192, 1997.
Z. Brakerski and G. Segev. Better security for deterministic public-key encryption: The auxiliary-input setting. In Advances in Cryptology—CRYPTO ’11, pp. 543–560, 2011.
J. R. Douceur, A. Adya, W. J. Bolosky, D. Simon, and M. Theimer. Reclaiming space from duplicate files in a serverless distributed file system. In Proceedings of the 22nd International Conference on Distributed Computing Systems, pp. 617–624, 2002.
Y. Dodis and A. Smith. Entropic security and the encryption of high entropy messages. In Proceedings of the 2nd Theory of Cryptography Conference, pp. 556–577, 2005.
M. Fischlin. Incremental cryptography and memory checkers. In Advances in Cryptology—EUROCRYPT ’97, pp. 293–408, 1997.
M. Fischlin. Lower bounds for the signature size of incremental schemes. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, pp. 438–447, 1997.
B. Fuller, A. O’Neill, and L. Reyzin. A unified approach to deterministic encryption: new constructions and a connection to computational entropy. In Proceedings of the 9th Theory of Cryptography Conference, pp. 582–599, 2012.
D. Micciancio. Oblivious data structures: applications to cryptography. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, pp. 456–464, 1997.
A. Raghunathan, G. Segev, and S. Vadhan. Deterministic public-key encryption for adaptively chosen plaintext distributions. In Advances in Crytology—EUROCRYPT ’13, pp. 93–110, 2013.
H. Wee. Dual projective hashing and its applications—lossy trapdoor functions and more. In Advances in Cryptology—EUROCRYPT ’12, pp. 246–262, 2012.
- Incremental Deterministic Public-Key Encryption
- Springer US
Neuer Inhalt/© ITandMEDIA, Product Lifecycle Management/© Eisenhans | vege | Fotolia