{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T10:58:30Z","timestamp":1777546710088,"version":"3.51.4"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,4,19]],"date-time":"2017-04-19T00:00:00Z","timestamp":1492560000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s00145-017-9252-1","type":"journal-article","created":{"date-parts":[[2017,4,19]],"date-time":"2017-04-19T17:56:08Z","timestamp":1492624568000},"page":"134-161","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Incremental Deterministic Public-Key Encryption"],"prefix":"10.1007","volume":"31","author":[{"given":"Ilya","family":"Mironov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Omkant","family":"Pandey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Omer","family":"Reingold","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gil","family":"Segev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,4,19]]},"reference":[{"key":"9252_CR1","doi-asserted-by":"crossref","unstructured":"M.\u00a0Abadi, D.\u00a0Boneh, I.\u00a0Mironov, A.\u00a0Raghunathan, and G.\u00a0Segev. Message-locked encryption for lock-dependent messages. In Advances in Cryptology\u2014RYPTO \u201913, pp. 374\u2013391, 2013.","DOI":"10.1007\/978-3-642-40041-4_21"},{"issue":"4","key":"9252_CR2","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/S0097539705446950","volume":"36","author":"B Applebaum","year":"2006","unstructured":"B.\u00a0Applebaum, Y.\u00a0Ishai, and E.\u00a0Kushilevitz. Cryptography in $$NC^{{0}}$$ N C 0 . SIAM Journal on Computing, 36(4):845\u2013888, 2006.","journal-title":"SIAM Journal on Computing"},{"key":"9252_CR3","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, Z.\u00a0Brakerski, M.\u00a0Naor, T.\u00a0Ristenpart, G.\u00a0Segev, H.\u00a0Shacham, and S.\u00a0Yilek. Hedged public-key encryption: how to protect against bad randomness. In Advances in Cryptology\u2014ASIACRYPT \u201909, pp. 232\u2013249, 2009.","DOI":"10.1007\/978-3-642-10366-7_14"},{"key":"9252_CR4","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, A.\u00a0Boldyreva, and A.\u00a0O\u2019Neill. Deterministic and efficiently searchable encryption. In Advances in Cryptology\u2014CRYPTO \u201907, pp. 535\u2013552, 2007.","DOI":"10.1007\/978-3-540-74143-5_30"},{"key":"9252_CR5","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, M.\u00a0Fischlin, A.\u00a0O\u2019Neill, and T.\u00a0Ristenpart. Deterministic encryption: definitional equivalences and constructions without random oracles. In Advances in Cryptology\u2014CRYPTO \u201908, pp. 360\u2013378, 2008.","DOI":"10.1007\/978-3-540-85174-5_20"},{"key":"9252_CR6","doi-asserted-by":"crossref","unstructured":"A.\u00a0Boldyreva, S.\u00a0Fehr, and A.\u00a0O\u2019Neill. On notions of security for deterministic encryption, and efficient constructions without random oracles. In Advances in Cryptology\u2014CRYPTO \u201908, pp. 335\u2013359, 2008.","DOI":"10.1007\/978-3-540-85174-5_19"},{"key":"9252_CR7","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, O.\u00a0Goldreich, and S.\u00a0Goldwasser. Incremental cryptography: the case of hashing and signing. In Advances in Cryptology\u2014CRYPTO \u201994, pp. 216\u2013233, 1994.","DOI":"10.1007\/3-540-48658-5_22"},{"key":"9252_CR8","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, O.\u00a0Goldreich, and S.\u00a0Goldwasser. Incremental cryptography and application to virus protection. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pp. 45\u201356, 1995.","DOI":"10.1145\/225058.225080"},{"key":"9252_CR9","doi-asserted-by":"crossref","unstructured":"D.\u00a0Boneh, S.\u00a0Halevi, M.\u00a0Hamburg, and R.\u00a0Ostrovsky. Circular-secure encryption from Decision Diffie\u2013Hellman. In Advances in Cryptology\u2014CRYPTO \u201908, pp. 108\u2013125, 2008.","DOI":"10.1007\/978-3-540-85174-5_7"},{"key":"9252_CR10","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, S.\u00a0Keelveedhi, and T.\u00a0Ristenpart. Message-locked encryption and secure deduplication. In Advances in Cryptology\u2014EUROCRYPT \u201913, pp. 296\u2013312, 2013.","DOI":"10.1007\/978-3-642-38348-9_18"},{"key":"9252_CR11","doi-asserted-by":"crossref","unstructured":"E.\u00a0Buonanno, J.\u00a0Katz, and M.\u00a0Yung. Incremental unforgeable encryption. In Proceedings of the 8th International Workshop on Fast Software Encryption, pp. 109\u2013124, 2001.","DOI":"10.1007\/3-540-45473-X_9"},{"key":"9252_CR12","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare and D.\u00a0Micciancio. A new paradigm for collision-free hashing: Incrementality at reduced cost. In Advances in Cryptology\u2014EUROCRYPT \u201997, pp. 163\u2013192, 1997.","DOI":"10.1007\/3-540-69053-0_13"},{"key":"9252_CR13","doi-asserted-by":"crossref","unstructured":"Z.\u00a0Brakerski and G.\u00a0Segev. Better security for deterministic public-key encryption: The auxiliary-input setting. In Advances in Cryptology\u2014CRYPTO \u201911, pp. 543\u2013560, 2011.","DOI":"10.1007\/978-3-642-22792-9_31"},{"key":"9252_CR14","doi-asserted-by":"crossref","unstructured":"J.\u00a0R. Douceur, A.\u00a0Adya, W.\u00a0J. Bolosky, D.\u00a0Simon, and M.\u00a0Theimer. Reclaiming space from duplicate files in a serverless distributed file system. In Proceedings of the 22nd International Conference on Distributed Computing Systems, pp. 617\u2013624, 2002.","DOI":"10.1109\/ICDCS.2002.1022312"},{"issue":"1","key":"9252_CR15","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1137\/060651380","volume":"38","author":"Y Dodis","year":"2008","unstructured":"Y.\u00a0Dodis, R.\u00a0Ostrovsky, L.\u00a0Reyzin, and A.\u00a0Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM Journal on Computing, 38(1):97\u2013139, 2008.","journal-title":"SIAM Journal on Computing"},{"key":"9252_CR16","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Dodis and A.\u00a0Smith. Entropic security and the encryption of high entropy messages. In Proceedings of the 2nd Theory of Cryptography Conference, pp. 556\u2013577, 2005.","DOI":"10.1007\/978-3-540-30576-7_30"},{"issue":"1","key":"9252_CR17","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s00145-011-9112-3","volume":"26","author":"DM Freeman","year":"2013","unstructured":"D.\u00a0M. Freeman, O.\u00a0Goldreich, E.\u00a0Kiltz, A.\u00a0Rosen, and G.\u00a0Segev. More constructions of lossy and correlation-secure trapdoor functions. Journal of Cryptology, 26(1):39\u201374, 2013.","journal-title":"Journal of Cryptology"},{"key":"9252_CR18","doi-asserted-by":"crossref","unstructured":"M.\u00a0Fischlin. Incremental cryptography and memory checkers. In Advances in Cryptology\u2014EUROCRYPT \u201997, pp. 293\u2013408, 1997.","DOI":"10.1007\/3-540-69053-0_27"},{"key":"9252_CR19","doi-asserted-by":"crossref","unstructured":"M.\u00a0Fischlin. Lower bounds for the signature size of incremental schemes. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, pp. 438\u2013447, 1997.","DOI":"10.1109\/SFCS.1997.646132"},{"key":"9252_CR20","doi-asserted-by":"crossref","unstructured":"B.\u00a0Fuller, A.\u00a0O\u2019Neill, and L.\u00a0Reyzin. 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\u2013599, 2012.","DOI":"10.1007\/978-3-642-28914-9_33"},{"issue":"2","key":"9252_CR21","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S Goldwasser","year":"1984","unstructured":"S.\u00a0Goldwasser and S.\u00a0Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270\u2013299, 1984.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"9252_CR22","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J H\u00e5stad","year":"1999","unstructured":"J.\u00a0H\u00e5stad, R.\u00a0Impagliazzo, L.\u00a0A. Levin, and M.\u00a0Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364\u20131396, 1999.","journal-title":"SIAM Journal on Computing"},{"key":"9252_CR23","doi-asserted-by":"crossref","unstructured":"D.\u00a0Micciancio. Oblivious data structures: applications to cryptography. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, pp. 456\u2013464, 1997.","DOI":"10.1145\/258533.258638"},{"issue":"4","key":"9252_CR24","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1137\/100813464","volume":"41","author":"M Naor","year":"2012","unstructured":"M.\u00a0Naor and G.\u00a0Segev. Public-key cryptosystems resilient to key leakage. SIAM Journal on Computing, 41(4):772\u2013814, 2012.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"9252_CR25","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1006\/jcss.1996.0004","volume":"52","author":"N Nisan","year":"1996","unstructured":"N.\u00a0Nisan and D.\u00a0Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43\u201352, 1996.","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"9252_CR26","doi-asserted-by":"publisher","first-page":"1803","DOI":"10.1137\/080733954","volume":"40","author":"C Peikert","year":"2011","unstructured":"C.\u00a0Peikert and B.\u00a0Waters. Lossy trapdoor functions and their applications. SIAM Journal on Computing, 40(6):1803\u20131844, 2011.","journal-title":"SIAM Journal on Computing"},{"key":"9252_CR27","doi-asserted-by":"crossref","unstructured":"A.\u00a0Raghunathan, G.\u00a0Segev, and S.\u00a0Vadhan. Deterministic public-key encryption for adaptively chosen plaintext distributions. In Advances in Crytology\u2014EUROCRYPT \u201913, pp. 93\u2013110, 2013.","DOI":"10.1007\/978-3-642-38348-9_6"},{"issue":"3","key":"9252_CR28","doi-asserted-by":"publisher","first-page":"1130","DOI":"10.1109\/TIT.2005.864438","volume":"52","author":"A Russell","year":"2006","unstructured":"A.\u00a0Russell and H.\u00a0Wang. How to fool an unbounded adversary with a short key. IEEE Transactions on Information Theory, 52(3):1130\u20131140, 2006.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"9252_CR29","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00145-003-0237-x","volume":"17","author":"SP Vadhan","year":"2004","unstructured":"S.\u00a0P. Vadhan. Constructing locally computable extractors and cryptosystems in the bounded-storage model. Jounal of Cryptology, 17(1):43\u201377, 2004.","journal-title":"Jounal of Cryptology"},{"key":"9252_CR30","doi-asserted-by":"crossref","unstructured":"H.\u00a0Wee. Dual projective hashing and its applications\u2014lossy trapdoor functions and more. In Advances in Cryptology\u2014EUROCRYPT \u201912, pp. 246\u2013262, 2012.","DOI":"10.1007\/978-3-642-29011-4_16"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-017-9252-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-017-9252-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-017-9252-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:12:18Z","timestamp":1750201938000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-017-9252-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,19]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["9252"],"URL":"https:\/\/doi.org\/10.1007\/s00145-017-9252-1","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,19]]},"assertion":[{"value":"4 June 2012","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 January 2017","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}