Abstract
Motivated by the problem of protecting cryptographic hardware, we continue the investigation of private circuits initiated in [16]. In this work, our aim is to construct circuits that should protect the secrecy of their internal state against an adversary who may modify the values of an unbounded number of wires, anywhere in the circuit. In contrast, all previous works on protecting cryptographic hardware relied on an assumption that some portion of the circuit must remain completely free from tampering.
We obtain the first feasibility results for such private circuits. Our main result is an efficient transformation of a circuit C, realizing an arbitrary (reactive) functionality, into a private circuit C′ realizing the same functionality. The transformed circuit can successfully detect any serious tampering and erase all data in the memory. In terms of the information available to the adversary, even in the presence of an unbounded number of adaptive wire faults, the circuit C′ emulates a black-box access to C.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-540-34547-3_36
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Anderson, R., Kuhn, M.: Tamper Resistance—A Cautionary Note. In: USENIX E-Commerce Workshop, pp. 1–11. USENIX Press (1996)
Anderson, R., Kuhn, M.: Soft Tempest: Hidden Data Transmission Using Electromagnetic Emanations. In: Proc. 2nd Workshop on Information Hiding. Springer, Heidelberg (1998)
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 1. Springer, Heidelberg (2001)
Ben-Or, M., Goldwasser, S., Widgerson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proc. of 20th STOC (1988)
Biham, E., Shamir, A.: Differential fault analysis of secret key cryptosystems. In: McCurley, K.S., Ziegler, C.D. (eds.) Advances in Cryptology 1981 - 1997. LNCS, vol. 1440. Springer, Heidelberg (1999)
Boneh, D., Demillo, R.A., Lipton, R.J.: On the Importance of Checking Cryptographic Protocols for Faults. In: McCurley, K.S., Ziegler, C.D. (eds.) Advances in Cryptology 1981 - 1997. LNCS, vol. 1440, pp. 37–51. Springer, Heidelberg (1999)
Chari, S., Jutla, C.S., Rao, J.R., Rohatgi, P.: Towards Sound Approaches to Counteract Power-Analysis Attacks. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 398–412. Springer, Heidelberg (1999)
Chaum, D., Crepeau, C., Damgård, I.: Multiparty unconditional secure protocols. In: Proc. of 20th STOC (1988)
Coron, J.-S., Goubin, L.: On Boolean and Arithmetic Masking against Differential Power Analysis. In: Paar, C., Koç, Ç.K. (eds.) CHES 2000. LNCS, vol. 1965, pp. 231–237. Springer, Heidelberg (2000)
Daemen, J., Rijmen, V.: Resistance Against Implementation Attacks: A Comparative Study of the AES Proposals. In: AES 1999 (March 1999)
Gandolfi, K., Mourtel, C., Olivier, F.: Electromagnetic Analysis: Concrete Results. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, p. 251. Springer, Heidelberg (2001)
Gennaro, R., Lysyanskaya, A., Malkin, T., Micali, S., Rabin, T.: Algorithmic Tamper-Proof (ATP) Security: Theoretical Foundations for Security against Hardware Tampering. In: Proceedings of Theory of Cryptography Conference (2004)
Goldreich, O.: Foundations of Cryptography: Basic Applications. Cambridge University Press, Cambridge (2004)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game (extended abstract). In: Proc. of 19th STOC (1987)
Goubin, L., Patarin, J.: DES and Differential Power Analysis—The Duplication Method. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 158–172. Springer, Heidelberg (1999)
Ishai, Y., Sahai, A., Wagner, D.: Private Circuits: Protecting Hardware against Probing Attacks. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145–161. Springer, Heidelberg (2003)
Kahn, D.: The Codebreakers. The MacMillan Company, Basingstoke (1967)
Kelsey, J., Schneier, B., Wagner, D.: Side Channel Cryptanalysis of Product Ciphers. In: Quisquater, J.-J., Deswarte, Y., Meadows, C., Gollmann, D. (eds.) ESORICS 1998. LNCS, vol. 1485, pp. 97–110. Springer, Heidelberg (1998)
Kocher, P.: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)
Kocher, P., Jaffe, J., Jun, B.: Differential Power Analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999)
Messerges, T.S.: Securing the AES Finalists Against Power Analysis Attacks. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, p. 150. Springer, Heidelberg (2001)
Micali, S., Reyzin, L.: Physically Observable Cryptography. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 278–296. Springer, Heidelberg (2004)
Ostrovsky, R., Yung, M.: How to Withstand Mobile Virus Attacks (Extended Abstract). In: Proc. of PODC 1991, pp. 51–59 (1991)
Page, D.: Theoretical Use of Cache Memory as a Cryptanalytic Side-Channel. Tech. report CSTR-02-003, Computer Science Dept., Univ. of Bristol (June 2002)
Pfitzmann, B., Schunter, M., Waidner, M.: Secure Reactive Systems. IBM Technical report RZ 3206 (93252) (May 2000)
Pippenger, N.: On Networks of Noisy Gates. In: Proc. of FOCS 1985, pp. 30–38 (1985)
Quisquater, J.-J., Samyde, D.: Eddy current for Magnetic Analysis with Active Sensor. In: Esmart 2002 (September 2002)
Quisquater, J.-J., Samyde, D.: ElectroMagnetic Analysis (EMA): Measures and Counter-Measures for Smart Cards. In: Attali, S., Jensen, T. (eds.) E-smart 2001. LNCS, vol. 2140, p. 200. Springer, Heidelberg (2001)
Rao, J.R., Rohatgi, P.: EMpowering Side-Channel Attacks. IACR ePrint (2001/037) (2001)
US Air Force, Air Force Systems Security Memorandum 7011—Emission Security Countermeasures Review (May 1,1998)
van Eck, W.: Electromagnetic Radiation from Video Display Units: An Eavesdropping Risk. Computers & Security 4, 269–286 (1985)
Wright, D.: Spycatcher. Viking Penguin Inc. (1987)
Younis, S.G., Knight Jr., T.F.: Asymptotically Zero Energy Split-Level Charge Recovery Logic. In: Proceedings of 1994 International Workshop on Low Power Design, Napa, CA (1994)
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ishai, Y., Prabhakaran, M., Sahai, A., Wagner, D. (2006). Private Circuits II: Keeping Secrets in Tamperable Circuits. In: Vaudenay, S. (eds) Advances in Cryptology - EUROCRYPT 2006. EUROCRYPT 2006. Lecture Notes in Computer Science, vol 4004. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11761679_19
Download citation
DOI: https://doi.org/10.1007/11761679_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34546-6
Online ISBN: 978-3-540-34547-3
eBook Packages: Computer ScienceComputer Science (R0)