{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T02:27:32Z","timestamp":1791167252397,"version":"4.1.0"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>Physical computational devices leak side-channel information that may, and often does, reveal secret internal states. We present a general transformation that compiles any circuit into a circuit with the same functionality but resilience against well-defined classes of leakage. Our construction requires a small, stateless, and computation-independent leak-proof component that draws random elements from a fixed distribution. In essence, we reduce the problem of shielding arbitrarily complex circuits to the problem of shielding a single, simple component. Our approach is based on modeling the adversary as a powerful observer that inspects the device via a limited measurement apparatus. We allow the apparatus to access all the bits of the computation (except those inside the leak-proof component), and the amount of leaked information to grow unbounded over time. However, we assume that the apparatus is limited in the amount of output bits per iteration and the ability to decode certain linear encodings. While our results apply in general to such leakage classes, in particular, we obtain security against (a) constant-depth circuits leakage, where the leakage function is computed by an $\\mathsf{AC}^0$ circuit (composed of NOT gates and unbounded fan-in AND and OR gates); (b) noisy leakage, where the leakage function reveals all the bits of the internal state of the circuit, but each bit is perturbed by independent binomial noise---i.e., flipped with some probability $p$. Namely, for some number $p\\in(0,1\/2]$, each bit of the computation is flipped with probability $p$, and remains unchanged with probability $1-p$.<\/jats:p>","DOI":"10.1137\/120880343","type":"journal-article","created":{"date-parts":[[2014,9,17]],"date-time":"2014-09-17T10:44:32Z","timestamp":1410950672000},"page":"1564-1614","source":"Crossref","is-referenced-by-count":15,"title":["Protecting Circuits from Computationally Bounded and Noisy Leakage"],"prefix":"10.1137","volume":"43","author":[{"given":"Sebastian","family":"Faust","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tal","family":"Rabin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leonid","family":"Reyzin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eran","family":"Tromer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vinod","family":"Vaikuntanathan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,9,11]]},"reference":[{"key":"atypb1","first-page":"1","author":"Ajtai M.","year":"1993","journal-title":"RI"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"M. Ajtai,\n                      Secure computation with information leaking to an adversary\n                      , in STOC 11, L. Fortnow and S. P. Vadhan, eds., ACM, New York, 2011, pp. 715-724.","DOI":"10.1145\/1993636.1993731"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/2160158.2160159"},{"key":"atypb4","unstructured":"A. Beimel,\n                      Secure Schemes for Secret Sharing and Key Distribution\n                      , Ph.D. thesis, The Technion-Israel Institute of Technology, Haifa, Israel, 1996."},{"key":"atypb5","unstructured":"D. J. Bernstein,\n                      Cache-timing attacks on AES\n                      , http:\/\/cr.yp.to\/papers.html#cachetiming (2005)."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754401"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2005.01.010"},{"key":"atypb8","first-page":"398","author":"Chari S.","year":"1999","journal-title":"Berlin"},{"key":"atypb9","first-page":"711","author":"Dubrov B.","year":"2006","journal-title":"New York"},{"key":"atypb10","first-page":"423","author":"Duc A.","year":"2014","journal-title":"Berlin"},{"key":"atypb11","first-page":"702","author":"Dziembowski S.","year":"2011","journal-title":"Berlin"},{"key":"atypb12","first-page":"230","author":"Dziembowski S.","year":"2012","journal-title":"New York"},{"key":"atypb13","first-page":"293","author":"Dziembowski S.","year":"2008","journal-title":"NJ"},{"key":"atypb14","first-page":"343","author":"Faust S.","year":"2010","journal-title":"Berlin"},{"key":"atypb15","first-page":"135","author":"Faust S.","year":"2010","journal-title":"Berlin"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"atypb17","first-page":"182","author":"Goldreich O.","year":"1987","journal-title":"New York"},{"key":"atypb18","first-page":"248","author":"Goldreich O.","year":"2011","journal-title":"Berlin"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"atypb20","first-page":"59","author":"Goldwasser S.","year":"2010","journal-title":"Berlin"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"S. Goldwasser and G. N. Rothblum,\n                      How to compute in the presence of leakage\n                      , in FOCS, IEEE Computer Society, Los Alamitos, CA, 2012, pp. 31-40.","DOI":"10.1109\/FOCS.2012.34"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"J. Hastad,\n                      Almost optimal lower bounds for small depth circuits\n                      , in ACM Symposium on the Theory of Computing, ACM, New York, 1986.","DOI":"10.1145\/12130.12132"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"atypb24","first-page":"463","author":"Ishai Y.","year":"2003","journal-title":"Berlin"},{"key":"atypb25","unstructured":"Y. Ishai, A. Sahai, and D. Wagner,\n                      Private Circuits: Securing Hardware Against Probing Attacks\n                      , manuscript, https:\/\/www.princeton.edu\/\\string rblee\/ELE572Papers\/Fall04Readings\/privcirc-crypto03.pdf https:\/\/www.princeton.edu\/\u02dcrblee\/ELE572Papers\/Fall04Readings\/ (2003)."},{"key":"atypb26","first-page":"41","author":"Juma A.","year":"2010","journal-title":"Berlin"},{"key":"atypb27","first-page":"249","author":"Klivans A.","year":"2001","journal-title":"Berlin"},{"key":"atypb28","first-page":"388","author":"Kocher P. C.","year":"1999","journal-title":"Berlin"},{"key":"atypb29","unstructured":"M. G. Kuhn,\n                      Compromising Emanations: Eavesdropping Risks of Computer Displays\n                      , Ph.D. thesis, University of Cambridge, Cambridge, England, 2003."},{"key":"atypb30","first-page":"278","author":"Micali S.","year":"2004","journal-title":"Berlin"},{"key":"atypb31","first-page":"261","author":"Miles E.","year":"2014","journal-title":"New York"},{"key":"atypb32","first-page":"251","author":"Miles E.","year":"2013","journal-title":"New York"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/BF01375474"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"D. A. Osvik, A. Shamir, and E. Tromer,\n                      Cache attacks and countermeasures: The case of AES\n                      , in Topics in Cryptology-CT-RSA 2006, Springer, Berlin, pp. 1-20.","DOI":"10.1007\/11605805_1"},{"key":"atypb35","unstructured":"C. Percival,\n                      Cache missing for fun and profit\n                      , http:\/\/www.daemonology.net\/papers\/htt.pdf (2005)."},{"key":"atypb36","first-page":"462","author":"Pietrzak K.","year":"2009","journal-title":"Berlin"},{"key":"atypb37","first-page":"142","author":"Prouff E.","year":"2013","journal-title":"Berlin"},{"key":"atypb38","first-page":"200","author":"Quisquater J.-J.","year":"2001","journal-title":"Berlin"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"T. Rabin, ed.\n                      Advances in Cryptology-CRYPTO 2010\n                      , Lecture Notes in Comput. Sci. 6223, Springer, Berlin, 2010.","DOI":"10.1007\/978-3-642-14623-7"},{"key":"atypb40","first-page":"552","author":"Rothblum G. N.","year":"2012","journal-title":"Berlin"},{"key":"atypb41","unstructured":"A. Shamir and E. Tromer,\n                      Acoustic cryptanalysis: On nosy people and noisy machines\n                      , Eurocrypt 2004 rump session, http:\/\/tromer.org\/acoustic(2004)."},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"K. Tiri and I. Verbauwhede,\n                      A VLSI design flow for secure side-channel attack resistant ICs\n                      , in Design, Automation and Test in Europe, IEEE Computer Society, Los Alamitos, CA, 2005, pp. 58-63.","DOI":"10.1109\/DATE.2005.44"},{"key":"atypb43","unstructured":"S. Vadhan,\n                      A Study of Statistical Zero-Knowledge Proofs\n                      , Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, 1999."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120880343","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:00Z","timestamp":1787337420000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120880343"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":43,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/120880343"],"URL":"https:\/\/doi.org\/10.1137\/120880343","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}