{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,15]],"date-time":"2026-08-15T11:46:04Z","timestamp":1786794364236,"version":"build-2736575974"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,10,5]],"date-time":"2016-10-05T00:00:00Z","timestamp":1475625600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,10,5]],"date-time":"2016-10-05T00:00:00Z","timestamp":1475625600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["1217821"],"award-info":[{"award-number":["1217821"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1350939"],"award-info":[{"award-number":["1350939"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Microsoft New Faculty Fellowship"},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["1217821"],"award-info":[{"award-number":["1217821"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["0746990"],"award-info":[{"award-number":["0746990"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1214844"],"award-info":[{"award-number":["1214844"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"name":"AFOSR YIP","award":["FA9550-10-1-0093"],"award-info":[{"award-number":["FA9550-10-1-0093"]}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100006602","name":"Air Force Research Laboratory","doi-asserted-by":"crossref","award":["FA8750-11-2- 0211."],"award-info":[{"award-number":["FA8750-11-2- 0211."]}],"id":[{"id":"10.13039\/100006602","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.1007\/s00453-016-0219-7","type":"journal-article","created":{"date-parts":[[2016,10,5]],"date-time":"2016-10-05T14:36:34Z","timestamp":1475678194000},"page":"1052-1101","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On the Impossibility of Cryptography with Tamperable Randomness"],"prefix":"10.1007","volume":"79","author":[{"given":"Per","family":"Austrin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kai-Min","family":"Chung","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6839-4697","authenticated-orcid":false,"given":"Mohammad","family":"Mahmoody","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karn","family":"Seth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,10,5]]},"reference":[{"key":"219_CR1","doi-asserted-by":"crossref","unstructured":"Akavia, A., Goldwasser, S., Vaikuntanathan, V.: Simultaneous hardcore bits and cryptography against memory attacks. In: Reingold, O. (ed.) Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, March 15-17, 2009. Proceedings, volume 5444 of Lecture Notes in Computer Science, pp. 474\u2013495. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-00457-5_28"},{"key":"219_CR2","unstructured":"Anderson, R., Kuhn, M.: Tamper resistance\u2014a cautionary note. In: Proceedings of the Second USENIX Workshop on Electronic Commerce, pp. 1\u201311, November (1996)"},{"key":"219_CR3","unstructured":"One, A.: Smashing the stack for fun and profit. Phrack Magazine, 7(49):File 14 (1996)"},{"key":"219_CR4","doi-asserted-by":"crossref","unstructured":"Boneh, D., DeMillo, R.A., Lipton, R.J.: On the importance of checking cryptographic protocols for faults. In: EUROCRYPT: Advances in Cryptology: Proceedings of EUROCRYPT (1997)","DOI":"10.1007\/3-540-69053-0_4"},{"key":"219_CR5","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Kalai, Y.\u00a0T., Katz, J., Vaikuntanathan, V.: Overcoming the hole in the bucket: public-key cryptography resilient to continual memory leakage. In: FOCS, pp. 501\u2013510. IEEE Computer Society (2010)","DOI":"10.1109\/FOCS.2010.55"},{"key":"219_CR6","doi-asserted-by":"crossref","unstructured":"Beimel, A., Malkin, T., Micali, S.: The all-or-nothing nature of two-party secure computation. In CRYPTO, pp. 80\u201397 (1999)","DOI":"10.1007\/3-540-48405-1_6"},{"key":"219_CR7","doi-asserted-by":"crossref","unstructured":"Bellare, M., Paterson, K.G., Rogaway, P.: Security of symmetric encryption against mass surveillance. In: Advances in Cryptology\u2013CRYPTO 2014, pp. 1\u201319. Springer (2014)","DOI":"10.1007\/978-3-662-44371-2_1"},{"key":"219_CR8","doi-asserted-by":"crossref","unstructured":"Biham, E., Shamir, A.: Differential fault analysis of secret key cryptosystems. In: CRYPTO: Proceedings of Crypto (1997)","DOI":"10.1007\/BFb0052259"},{"key":"219_CR9","doi-asserted-by":"crossref","unstructured":"Canetti, R., Goldreich, O., Goldwasser, S., Micali, S.: Resettable zero-knowledge (extended abstract). In: STOC, pp. 235\u2013244 (2000)","DOI":"10.1145\/335305.335334"},{"key":"219_CR10","doi-asserted-by":"crossref","unstructured":"Choi, S.G., Kiayias, A., Malkin, T.: BiTR: Built-in tamper resilience. In: Lee, D.H., Wang, X. (eds.) Advances in Cryptology\u2014ASIACRYPT 2011\u201417th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4\u20138, 2011. Proceedings, Volume 7073 of Lecture Notes in Computer Science, pp. 740\u2013758. Springer (2011)","DOI":"10.1007\/978-3-642-25385-0_40"},{"key":"219_CR11","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Goldwasser, S., Kalai, Y.T., Peikert, C., Vaikuntanathan, V.: Public-key encryption schemes with auxiliary inputs. In: Micciancio, Daniele (ed.) Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, February 9\u201311, 2010. Proceedings, volume 5978 of Lecture Notes in Computer Science, pp. 361\u2013381. Springer (2010)","DOI":"10.1007\/978-3-642-11799-2_22"},{"key":"219_CR12","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Haralambiev, K., L\u00f3pez-Alt, A., Wichs, D.: Cryptography against continuous memory attacks. In: FOCS, pp. 511\u2013520. IEEE Computer Society (2010)","DOI":"10.1109\/FOCS.2010.56"},{"key":"219_CR13","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Oliveira, R.: On extracting private randomness over a public channel. In: RANDOM: International Workshop on Randomization and Approximation Techniques in Computer Science. LNCS (2003)","DOI":"10.1007\/978-3-540-45198-3_22"},{"key":"219_CR14","unstructured":"Dodis, Y., Ong, S.J., Prabhakaran, M., Sahai, A.: On the (im)possibility of cryptography with imperfect randomness. In: FOCS: IEEE Symposium on Foundations of Computer Science (FOCS) (2004)"},{"key":"219_CR15","doi-asserted-by":"crossref","unstructured":"Dziembowski, S., Pietrzak, K.: Leakage-resilient cryptography. In: FOCS, pp. 293\u2013302. IEEE Computer Society (2008)","DOI":"10.1109\/FOCS.2008.56"},{"key":"219_CR16","first-page":"434","volume-title":"ICS","author":"S Dziembowski","year":"2010","unstructured":"Dziembowski, S., Pietrzak, K., Wichs, D.: Non-malleable codes. In: Chi-Chih Yao, A. (ed.) ICS, pp. 434\u2013452. Tsinghua University Press, Tsinghua (2010)"},{"key":"219_CR17","first-page":"366","volume":"2012","author":"D Dachman-Soled","year":"2012","unstructured":"Dachman-Soled, D., Kalai, Y.T.: Securing circuits against constant-rate tampering. IACR Cryptol. ePrint Arch. 2012, 366 (2012). (informal publication)","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"219_CR18","unstructured":"Feldman, A.J., Benaloh, J.: On subliminal channels in encrypt-on-cast voting systems. In: Proceedings of the 2009 Conference on Electronic Voting Technology\/Workshop on Trustworthy Elections, EVT\/WOTE\u201909, pp. 12\u201312, Berkeley, CA, USA, 2009. USENIX Association"},{"key":"219_CR19","first-page":"391","volume":"1","author":"S Faust","year":"2011","unstructured":"Faust, S., Pietrzak, K., Venturi, D.: Tamper-proof circuits: how to trade leakage for tamper-resilience. ICALP 1, 391\u2013402 (2011)","journal-title":"ICALP"},{"key":"219_CR20","unstructured":"Frykholm, N.: Countermeasures against buffer overflow attacks. Technical report, RSA Data Security, Inc., pub-RSA:adr (November 2000)"},{"key":"219_CR21","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Lysyanskaya, A., Malkin, T., Micali, S., Rabin, T.: Al-gorithmic tamper-proof (atp) security: theoretical foundations for security against hardware tampering. In: Naor, M. (ed.) TCC, Volume 2951 of Lecture Notes in Computer Science, pp. 258\u2013277. Springer (2004)","DOI":"10.1007\/978-3-540-24638-1_15"},{"issue":"2","key":"219_CR22","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S Goldwasser","year":"1984","unstructured":"Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270\u2013299 (1984)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"219_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00195207","volume":"7","author":"O Goldreich","year":"1994","unstructured":"Goldreich, O., Oren, Y.: Definitions and properties of zero-knowledge proof systems. J. Cryptol. 7(1), 1\u201332 (1994)","journal-title":"J. Cryptol."},{"issue":"5","key":"219_CR24","doi-asserted-by":"publisher","first-page":"1480","DOI":"10.1137\/130931461","volume":"44","author":"S Goldwasser","year":"2015","unstructured":"Goldwasser, S., Rothblum, G.N.: How to compute in the presence of leakage. SIAM J. Comput. 44(5), 1480\u20131549 (2015)","journal-title":"SIAM J. Comput."},{"key":"219_CR25","unstructured":"Heninger, N., Durumeric, Z., Wustrow, E., Halderman, J.A.: Mining your Ps and Qs: detection of widespread weak keys in network devices. In: Proceedings of the 21st USENIX Security Symposium (August 2012)"},{"issue":"4","key":"219_CR26","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"key":"219_CR27","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pp. 230\u2013235 (1989)","DOI":"10.1109\/SFCS.1989.63483"},{"key":"219_CR28","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Prabhakaran, M., Sahai, A., Wagner, D.: Private circuits II: keeping secrets in tamperable circuits. In: Vaudenay, S. (ed.) Advances in Cryptology\u2014EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28\u2013June 1, 2006, Proceedings, Volume 4004 of Lecture Notes in Computer Science, pp. 308\u2013327. Springer (2006)","DOI":"10.1007\/11761679_19"},{"key":"219_CR29","doi-asserted-by":"crossref","unstructured":"Kamara, S., Katz, J.: How to encrypt with a malicious random number generator. In: Fast Software Encryption, pp. 303\u2013315. Springer (2008)","DOI":"10.1007\/978-3-540-71039-4_19"},{"key":"219_CR30","doi-asserted-by":"crossref","unstructured":"Kalai, Y.T., Kanukurthi, B., Sahai, A.: Cryptography with tamperable and leaky memory. In: CRYPTO, pp. 373\u2013390 (2011)","DOI":"10.1007\/978-3-642-22792-9_21"},{"key":"219_CR31","doi-asserted-by":"crossref","unstructured":"Kalai, Y.T., Li, X., Rao, A. 2-source extractors under computational assumptions and cryptography with defective randomness. In: FOCS, pp. 617\u2013626. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.61"},{"key":"219_CR32","doi-asserted-by":"crossref","unstructured":"Kalai, Y.T., Lewko, A., Rao, A.: Formulas resilient to short-circuit errors. In: Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pp. 490\u2013499. IEEE (2012)","DOI":"10.1109\/FOCS.2012.69"},{"key":"219_CR33","doi-asserted-by":"crossref","unstructured":"Lenstra, A.K., Hughes, J.P., Augier, M., Bos, J.W., Kleinjung, T., Wachter, C.: Public keys. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO, Volume 7417 of Lecture Notes in Computer Science, pp. 626\u2013642. Springer (2012)","DOI":"10.1007\/978-3-642-32009-5_37"},{"key":"219_CR34","unstructured":"Lenstra, A.K., Hughes, J.P., Augier, M., Bos, J.W., Kleinjung, T., Wachter, C.: Ron was wrong, whit is right. Cryptology ePrint Archive, Report 2012\/064, 2012. \n                    http:\/\/eprint.iacr.org\/"},{"key":"219_CR35","doi-asserted-by":"crossref","unstructured":"Liu, F.-H., Lysyanskaya, A.: Algorithmic tamper-proof security under probing attacks. In: SCN, pp. 106\u2013120 (2010)","DOI":"10.1007\/978-3-642-15317-4_8"},{"key":"219_CR36","doi-asserted-by":"crossref","unstructured":"Liu, F.-H., Lysyanskaya, A.: Tamper and leakage resilience in the split-state model. In: Crypto (2012)","DOI":"10.1007\/978-3-642-32009-5_30"},{"key":"219_CR37","doi-asserted-by":"crossref","unstructured":"Micali, S., Reyzin, L.: Physically observable cryptography (extended abstract). In: Theory of Cryptography Conference (TCC), LNCS, vol.\u00a01 (2004)","DOI":"10.1007\/978-3-540-24638-1_16"},{"issue":"4","key":"219_CR38","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1109\/MSP.2004.36","volume":"2","author":"JD Pincus","year":"2004","unstructured":"Pincus, J.D., Baker, B.: Beyond stack smashing: recent advances in exploiting buffer overruns. IEEE Secur. Priv. 2(4), 20\u201327 (2004)","journal-title":"IEEE Secur. Priv."},{"key":"219_CR39","doi-asserted-by":"crossref","unstructured":"Rothblum, G.N.: How to compute under $${\\cal AC}^{0}$$ leakage without secure hardware. In: Safavi-Naini, R., Canetti, R. (ed.) CRYPTO, Volume 7417 of Lecture Notes in Computer Science, pp. 552\u2013569. Springer (2012)","DOI":"10.1007\/978-3-642-32009-5_32"},{"issue":"2","key":"219_CR40","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"RL Rivest","year":"1978","unstructured":"Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120\u2013126 (1978)","journal-title":"Commun. ACM"},{"issue":"4","key":"219_CR41","first-page":"15","volume":"5","author":"GJ Simmons","year":"1994","unstructured":"Simmons, G.J.: Subliminal channels; past and present. ETT 5(4), 15 (1994)","journal-title":"ETT"},{"issue":"1","key":"219_CR42","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0022-0000(86)90044-9","volume":"33","author":"M Santha","year":"1986","unstructured":"Santha, M., Vazirani, U.V.: Generating quasi-random sequences from semi-random sources. J. Comput. Syst. Sci. 33(1), 75\u201387 (1986)","journal-title":"J. Comput. Syst. Sci."},{"key":"219_CR43","doi-asserted-by":"crossref","unstructured":"Young, A., Yung, M.: The dark side of \u2018black-box\u2019 cryptography, or: Should we trust capstone?. In: CRYPTO: Proceedings of Crypto (1996)","DOI":"10.1007\/3-540-68697-5_8"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0219-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0219-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0219-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:23:39Z","timestamp":1589696619000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0219-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,5]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["219"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0219-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,5]]},"assertion":[{"value":"16 August 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 September 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 October 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}