{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T23:36:38Z","timestamp":1769297798623,"version":"3.49.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,4,19]],"date-time":"2013-04-19T00:00:00Z","timestamp":1366329600000},"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":[[2014,7]]},"DOI":"10.1007\/s00145-013-9149-6","type":"journal-article","created":{"date-parts":[[2013,4,18]],"date-time":"2013-04-18T16:37:15Z","timestamp":1366303035000},"page":"429-451","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["Key-Dependent Message Security: Generic Amplification and Completeness"],"prefix":"10.1007","volume":"27","author":[{"given":"Benny","family":"Applebaum","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,4,19]]},"reference":[{"issue":"3","key":"9149_CR1","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s00145-007-0203-0","volume":"20","author":"M. Abadi","year":"2007","unstructured":"M. Abadi, P. Rogaway, Reconciling two views of cryptography (the computational soundness of formal encryption). J. Cryptol.\n                  20(3), 395 (2007)","journal-title":"J. Cryptol."},{"key":"9149_CR2","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-3-642-13190-5_21","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2010","author":"T. Acar","year":"2010","unstructured":"T. Acar, M. Belenkiy, M. Bellare, D. Cash, Cryptographic agility and its relation to circular encryption, in Advances in Cryptology\u2014EUROCRYPT 2010 (2010), pp.\u00a0403\u2013422"},{"issue":"5","key":"9149_CR3","doi-asserted-by":"crossref","first-page":"737","DOI":"10.3233\/JCS-2009-0358","volume":"17","author":"P. Ad\u00e3o","year":"2009","unstructured":"P. Ad\u00e3o, G. Bana, J. Herzog, A. Scedrov, Soundness and completeness of formal encryption: the cases of key cycles and partial information leakage. J. Comput. Secur.\n                  17(5), 737\u2013797 (2009)","journal-title":"J. Comput. Secur."},{"issue":"2","key":"9149_CR4","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s00037-006-0211-8","volume":"15","author":"B. Applebaum","year":"2006","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz, Computationally private randomizing polynomials and their applications. J. Comput. Complex.\n                  15(2), 115\u2013162 (2006)","journal-title":"J. Comput. Complex."},{"issue":"4","key":"9149_CR5","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/S0097539705446950","volume":"36","author":"B. Applebaum","year":"2006","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz, Cryptography in NC0. SIAM J. Comput.\n                  36(4), 845\u2013888 (2006)","journal-title":"SIAM J. Comput."},{"key":"9149_CR6","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/978-3-642-03356-8_35","volume-title":"Advances in Cryptology\u2014CRYPTO 2009","author":"B. Applebaum","year":"2009","unstructured":"B. Applebaum, D. Cash, C. Peikert, A. Sahai, Fast cryptographic primitives and circular-secure encryption based on hard learning problems, in Advances in Cryptology\u2014CRYPTO 2009 (2009), pp.\u00a0595\u2013618"},{"key":"9149_CR7","volume-title":"Proceedings of 20th IEEE Computer Security Foundation Symposium (CSF)","author":"M. Backes","year":"2007","unstructured":"M. Backes, B. Pfitzmann, A. Scedrov, Key-dependent message security under active attacks\u2014BRSIM\/UC-soundness of symbolic encryption with key cycles, in Proceedings of 20th IEEE Computer Security Foundation Symposium (CSF) (2007)"},{"key":"9149_CR8","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1007\/978-3-540-89255-7_31","volume-title":"Advances in Cryptology\u2014ASIACRYPT 2008","author":"M. Backes","year":"2008","unstructured":"M. Backes, M. D\u00fcrmuth, D. Unruh, OAEP is secure under key-dependent messages, in Advances in Cryptology\u2014ASIACRYPT 2008 (2008), pp.\u00a0506\u2013523"},{"key":"9149_CR9","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/978-3-642-13190-5_22","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2010","author":"B. Barak","year":"2010","unstructured":"B. Barak, I. Haitner, D. Hofheinz, Y. Ishai, Bounded key-dependent message security, in Advances in Cryptology\u2014EUROCRYPT 2010 (2010), pp.\u00a0423\u2013444"},{"issue":"2","key":"9149_CR10","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1006\/jcss.1999.1648","volume":"59","author":"A. Beimel","year":"1999","unstructured":"A. Beimel, A. G\u00e1l, On arithmetic branching programs. J. Comput. Syst. Sci.\n                  59(2), 195\u2013220 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"9149_CR11","first-page":"62","volume-title":"SAC 2002: 9th Annual International Workshop on Selected Areas in Cryptography","author":"J. Black","year":"2002","unstructured":"J. Black, P. Rogaway, T. Shrimpton, Encryption-scheme security in the presence of key-dependent messages, in SAC 2002: 9th Annual International Workshop on Selected Areas in Cryptography (2002), pp.\u00a062\u201375"},{"key":"9149_CR12","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-85174-5_7","volume-title":"Advances in Cryptology\u2014CRYPTO 2008","author":"D. Boneh","year":"2008","unstructured":"D. Boneh, S. Halevi, M. Hamburg, R. Ostrovsky, Circular-secure encryption from decision Diffie\u2013Hellman, in Advances in Cryptology\u2014CRYPTO 2008 (2008), pp.\u00a0108\u2013125"},{"key":"9149_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-14623-7_1","volume-title":"Advances in Cryptology\u2014CRYPTO 2010","author":"Z. Brakerski","year":"2010","unstructured":"Z. Brakerski, S. Goldwasser, Circular and leakage resilient public-key encryption under subgroup indistinguishability (or: Quadratic residuosity strikes back), in Advances in Cryptology\u2014CRYPTO 2010 (2010), pp.\u00a01\u201320"},{"key":"9149_CR14","first-page":"97","volume-title":"52nd Annual Symposium on Foundations of Computer Science (FOCS)","author":"Z. Brakerski","year":"2011","unstructured":"Z. Brakerski, V. Vaikuntanathan, Efficient fully homomorphic encryption from (standard) LWE, in 52nd Annual Symposium on Foundations of Computer Science (FOCS) (2011), pp.\u00a097\u2013106"},{"key":"9149_CR15","volume-title":"TCC 2011: 8th Theory of Cryptography Conference","author":"Z. Brakerski","year":"2011","unstructured":"Z. Brakerski, S. Goldwasser, Y. Kalai, Circular-secure encryption beyond affine functions, in TCC 2011: 8th Theory of Cryptography Conference (2011)"},{"key":"9149_CR16","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/3-540-44987-6_7","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2001","author":"J. Camenisch","year":"2001","unstructured":"J. Camenisch, A. Lysyanskaya, An efficient system for non-transferable anonymous credentials with optional anonymity revocation, in Advances in Cryptology\u2014EUROCRYPT 2001 (2001), pp.\u00a093\u2013118"},{"key":"9149_CR17","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-642-01001-9_20","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2009","author":"J. Camenisch","year":"2009","unstructured":"J. Camenisch, N. Chandran, V. Shoup, A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks, in Advances in Cryptology\u2014EUROCRYPT 2009 (2009), pp.\u00a0351\u2013368"},{"key":"9149_CR18","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1007\/3-540-39200-9_37","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2003","author":"R. Cramer","year":"2003","unstructured":"R. Cramer, S. Fehr, Y. Ishai, E. Kushilevitz, Efficient multi-party computation over rings, in Advances in Cryptology\u2014EUROCRYPT 2003 (2003), pp.\u00a0596\u2013613"},{"key":"9149_CR19","first-page":"542","volume-title":"23rd Annual ACM Symposium on Theory of Computing (STOC)","author":"D. Dolev","year":"1991","unstructured":"D. Dolev, C. Dwork, M. Naor, Non-malleable cryptography (extended abstract), in 23rd Annual ACM Symposium on Theory of Computing (STOC) (1991), pp.\u00a0542\u2013552"},{"key":"9149_CR20","doi-asserted-by":"crossref","unstructured":"S. Even, O. Goldreich, A. Lempel, A randomized protocol for signing contracts, Commun. Assoc. Comput. Mach. 28 (1985)","DOI":"10.1145\/3812.3818"},{"key":"9149_CR21","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1145\/1536414.1536440","volume-title":"41st Annual ACM Symposium on Theory of Computing (STOC)","author":"C. Gentry","year":"2009","unstructured":"C. Gentry, Fully homomorphic encryption using ideal lattices, in 41st Annual ACM Symposium on Theory of Computing (STOC) (2009), pp.\u00a0169\u2013178"},{"key":"9149_CR22","first-page":"107","volume-title":"52nd Annual Symposium on Foundations of Computer Science (FOCS)","author":"C. Gentry","year":"2011","unstructured":"C. Gentry, S. Halevi, Fully homomorphic encryption without squashing using depth-3 arithmetic circuits, in 52nd Annual Symposium on Foundations of Computer Science (FOCS) (2011), pp.\u00a0107\u2013109"},{"key":"9149_CR23","volume-title":"41st Annual Symposium on Foundations of Computer Science (FOCS)","author":"Y. Gertner","year":"2000","unstructured":"Y. Gertner, S. Kannan, T. Malkin, O. Reingold, M. Viswanathan, The relationship between public key encryption and oblivious transfer, in 41st Annual Symposium on Foundations of Computer Science (FOCS) (2000)"},{"key":"9149_CR24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891","volume-title":"Foundations of Cryptography: Basic Tools","author":"O. Goldreich","year":"2001","unstructured":"O. Goldreich, Foundations of Cryptography: Basic Tools (Cambridge University Press, Cambridge, 2001)"},{"key":"9149_CR25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography: Basic Applications","author":"O. Goldreich","year":"2004","unstructured":"O. Goldreich, Foundations of Cryptography: Basic Applications (Cambridge University Press, Cambridge, 2004)"},{"issue":"2","key":"9149_CR26","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S. Goldwasser","year":"1984","unstructured":"S. Goldwasser, S. Micali, Probabilistic encryption. J. Comput. Syst. Sci.\n                  28(2), 270\u2013299 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"9149_CR27","first-page":"202","volume-title":"TCC 2009: 6th Theory of Cryptography Conference","author":"I. Haitner","year":"2009","unstructured":"I. Haitner, T. Holenstein, On the (im)possibility of key dependent encryption, in TCC 2009: 6th Theory of Cryptography Conference (2009), pp.\u00a0202\u2013219"},{"key":"9149_CR28","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1145\/1315245.1315303","volume-title":"ACM CCS 07: 14th Conference on Computer and Communications Security","author":"S. Halevi","year":"2007","unstructured":"S. Halevi, H. Krawczyk, Security under key-dependent inputs, in ACM CCS 07: 14th Conference on Computer and Communications Security (2007), pp.\u00a0466\u2013475"},{"key":"9149_CR29","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-78967-3_7","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2008","author":"D. Hofheinz","year":"2008","unstructured":"D. Hofheinz, D. Unruh, Towards key-dependent message security in the standard model, in Advances in Cryptology\u2014EUROCRYPT 2008 (2008), pp.\u00a0108\u2013126"},{"key":"9149_CR30","first-page":"8","volume-title":"Advances in Cryptology\u2014CRYPTO\u201988","author":"R. Impagliazzo","year":"1988","unstructured":"R. Impagliazzo, S. Rudich, Limits on the provable consequences of one-way permutations, in Advances in Cryptology\u2014CRYPTO\u201988 (1988), pp.\u00a08\u201326"},{"key":"9149_CR31","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1109\/SFCS.2000.892118","volume-title":"41st Annual Symposium on Foundations of Computer Science (FOCS)","author":"Y. Ishai","year":"2000","unstructured":"Y. Ishai, E. Kushilevitz, Randomizing polynomials: a new representation with applications to round-efficient secure computation, in 41st Annual Symposium on Foundations of Computer Science (FOCS) (2000), pp.\u00a0294\u2013304"},{"key":"9149_CR32","first-page":"244","volume-title":"ICALP 2002: 29th International Colloquium on Automata, Languages and Programming","author":"Y. Ishai","year":"2002","unstructured":"Y. Ishai, E. Kushilevitz, Perfect constant-round secure computation via perfect randomizing polynomials, in ICALP 2002: 29th International Colloquium on Automata, Languages and Programming (2002), pp.\u00a0244\u2013256"},{"key":"9149_CR33","first-page":"427","volume-title":"22nd Annual ACM Symposium on Theory of Computing (STOC)","author":"M. Naor","year":"1990","unstructured":"M. Naor, M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, in 22nd Annual ACM Symposium on Theory of Computing (STOC) (1990), pp.\u00a0427\u2013437"},{"key":"9149_CR34","unstructured":"M. Rabin, Digitalized signatures and public key functions as intractable as factoring. Tech. Rep. 212, LCS, MIT, 1979"},{"key":"9149_CR35","first-page":"433","volume-title":"Advances in Cryptology\u2014CRYPTO\u201991","author":"C. Rackoff","year":"1991","unstructured":"C. Rackoff, D.R. Simon, Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack, in Advances in Cryptology\u2014CRYPTO\u201991 (1991), pp.\u00a0433\u2013444"},{"key":"9149_CR36","first-page":"5","volume-title":"52nd Annual Symposium on Foundations of Computer Science (FOCS)","author":"V. Vaikuntanathan","year":"2011","unstructured":"V. Vaikuntanathan, Computing blind folded: new developments in fully homomorphic encryption, in 52nd Annual Symposium on Foundations of Computer Science (FOCS) (2011), pp.\u00a05\u201316"},{"key":"9149_CR37","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1109\/SFCS.1986.25","volume-title":"27th Annual Symposium on Foundations of Computer Science (FOCS)","author":"A.C. Yao","year":"1986","unstructured":"A.C. Yao, How to generate and exchange secrets, in 27th Annual Symposium on Foundations of Computer Science (FOCS) (1986), pp.\u00a0162\u2013167"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-013-9149-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-013-9149-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-013-9149-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-013-9149-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:11:45Z","timestamp":1586333505000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-013-9149-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,19]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["9149"],"URL":"https:\/\/doi.org\/10.1007\/s00145-013-9149-6","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,19]]},"assertion":[{"value":"12 January 2012","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2013","order":2,"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"}]}}