Abstract
We present a universal framework for tamper and leakage resilient computation on a random access machine (RAM). The RAM has one CPU that accesses a storage, which we call the disk. The disk is subject to leakage and tampering. So is the bus connecting the CPU to the disk. We assume that the CPU is leakage and tamper-free. For a fixed value of the security parameter, the CPU has constant size. Therefore the code of the program to be executed is stored on the disk, i.e., we consider a von Neumann architecture. The most prominent consequence of this is that the code of the program executed will be subject to tampering.
We construct a compiler for this architecture which transforms any keyed primitive into a RAM program where the key is encoded and stored on the disk along with the program to evaluate the primitive on that key. Our compiler only assumes the existence of a so-called continuous non-malleable code, and it only needs black-box access to such a code. No further (cryptographic) assumptions are needed. This in particular means that given an information theoretic code, the overall construction is information theoretic secure.
Although it is required that the CPU is tamper and leakage proof, its design is independent of the actual primitive being computed and its internal storage is non-persistent, i.e., all secret registers are reset between invocations. Hence, our result can be interpreted as reducing the problem of shielding arbitrary complex computations to protecting a single, simple yet universal component.
S. Faust and P. Mukherjee—Received funding from the Marie Curie IEF/FP7 project GAPS, grant number: 626467.
J.B. Nielsen—Partially supported by Danish Council for Independent Research via DFF Starting Grant 10-081612. Partially supported by the European Research Commission Starting Grant 279447.
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
Aggarwal, D., Dodis, Y., Lovett, S.: Non-malleable codes from additive combinatorics. IACR Cryptology ePrint Archive 2013:201 (2013)
Agrawal, S., Gupta, D., Maji, H.K., Pandey, O., Prabhakaran, M.: Explicit non-malleable codes resistant to permutations and perturbations. IACR Cryptology ePrint Archive 2014:316 (2014)
Bellare, Mihir, Cash, David: Pseudorandom functions and permutations provably secure against related-key attacks. In: Rabin, Tal (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 666–684. Springer, Heidelberg (2010)
Bellare, M., Kohno, T.: A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications. In: EUROCRYPT, pp. 491–506 (2003)
Bellare, Mihir, Paterson, Kenneth G., Thomson, Susan: RKA security beyond the linear barrier: IBE, encryption and signatures. In: Wang, Xiaoyun, Sako, Kazue (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 331–348. Springer, Heidelberg (2012)
Cheraghchi, M., Guruswami, V.: Capacity of non-malleable codes. In: ICS, pp. 155–168 (2014)
Cheraghchi, Mahdi, Guruswami, Venkatesan: Non-malleable coding against bit-wise and split-state tampering. In: Lindell, Yehuda (ed.) TCC 2014. LNCS, vol. 8349, pp. 440–464. Springer, Heidelberg (2014)
Coretti, S., Maurer, U., Tackmann, B., Venturi, D.: From single-bit to multi-bit public-key encryption via non-malleable codes. In: TCC (2015, To appear)
Coretti, S., Dodis, Y., Tackmann, B., Venturi, D.: Self-destruct non-malleability. IACR Cryptology ePrint Archive 2014:866 (2014)
Dachman-Soled, Dana, Kalai, Yael Tauman: Securing circuits against constant-rate tampering. In: Safavi-Naini, Reihaneh, Canetti, Ran (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 533–551. Springer, Heidelberg (2012)
Dachman-Soled, Dana, Kalai, Yael Tauman: Securing circuits and protocols against 1/poly(k) tampering rate. In: Lindell, Yehuda (ed.) TCC 2014. LNCS, vol. 8349, pp. 540–565. Springer, Heidelberg (2014)
Dachman-Soled, D., Liu, F.-H., Shi, E., Zhou, H.-S.: Locally decodable and updatable non-malleable codes and their applications. In: TCC (2015, To appear)
Damgård, Ivan, Faust, Sebastian, Mukherjee, Pratyay, Venturi, Daniele: Bounded tamper resilience: how to go beyond the algebraic barrier. In: Sako, Kazue, Sarkar, Palash (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 140–160. Springer, Heidelberg (2013)
Dziembowski, Stefan, Faust, Sebastian: Leakage-resilient circuits without computational assumptions. In: Cramer, Ronald (ed.) TCC 2012. LNCS, vol. 7194, pp. 230–247. Springer, Heidelberg (2012)
Dziembowski, Stefan, Kazana, Tomasz, Obremski, Maciej: Non-malleable codes from two-source extractors. In: Canetti, Ran, Garay, Juan A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 239–257. Springer, Heidelberg (2013)
Dziembowski, S., Pietrzak, K., Wichs, D.: Non-malleable codes. In: ICS, pp. 434–452 (2010)
Faust, Sebastian, Mukherjee, Pratyay, Nielsen, Jesper Buus, Venturi, Daniele: Continuous non-malleable codes. In: Lindell, Yehuda (ed.) TCC 2014. LNCS, vol. 8349, pp. 465–488. Springer, Heidelberg (2014)
Faust, S., Mukherjee, P., Nielsen, J.B., Venturi, D.: A tamper and leakage resilient von Neumann architecture. Cryptology ePrint Archive, Report 2014/338 (2014). http://eprint.iacr.org/
Faust, Sebastian, Mukherjee, Pratyay, Venturi, Daniele, Wichs, Daniel: Efficient non-malleable codes and key-derivation for poly-size tampering circuits. In: Nguyen, Phong Q., Oswald, Elisabeth (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 111–128. Springer, Heidelberg (2014)
Faust, Sebastian, Pietrzak, Krzysztof, Venturi, Daniele: Tamper-proof circuits: how to trade leakage for tamper-resilience. In: Aceto, Luca, Henzinger, Monika, Sgall, Jiří (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 391–402. Springer, Heidelberg (2011)
Faust, Sebastian, Rabin, Tal, Reyzin, Leonid, Tromer, Eran, Vaikuntanathan, Vinod: Protecting Circuits from Leakage: the Computationally-Bounded and Noisy Cases. In: Gilbert, Henri (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 135–156. Springer, Heidelberg (2010)
Goldwasser, S., Rothblum, G.N.:. How to compute in the presence of leakage. In: FOCS, pp. 31–40 (2012)
Ishai, Yuval, Prabhakaran, Manoj, Sahai, Amit, Wagner, David: Private circuits II: keeping secrets in tamperable circuits. In: Vaudenay, Serge (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 308–327. Springer, Heidelberg (2006)
Ishai, Yuval, Sahai, Amit, Wagner, David: Private circuits: securing hardware against probing attacks. In: Boneh, Dan (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 463–481. Springer, Heidelberg (2003)
Kalai, Yael Tauman, Kanukurthi, Bhavana, Sahai, Amit: Cryptography with tamperable and leaky memory. In: Rogaway, Phillip (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 373–390. Springer, Heidelberg (2011)
Kiayias, Aggelos, Tselekounis, Yiannis: Tamper resilient circuits: the adversary at the gates. In: Sako, Kazue, Sarkar, Palash (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 161–180. Springer, Heidelberg (2013)
Liu, Feng-Hao, Lysyanskaya, Anna: Tamper and leakage resilience in the split-state model. In: Safavi-Naini, Reihaneh, Canetti, Ran (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 517–532. Springer, Heidelberg (2012)
Miles, E., Viola, E.: Shielding circuits with groups. In: STOC, pp. 251–260 (2013)
Prouff, Emmanuel, Rivain, Matthieu: Masking against side-channel attacks: a formal security proof. In: Johansson, Thomas, Nguyen, Phong Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 142–159. Springer, Heidelberg (2013)
Wee, H.: Public key encryption against related key attacks. In: Public Key Cryptography, pp. 262–279 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 International Association for Cryptologic Research
About this paper
Cite this paper
Faust, S., Mukherjee, P., Nielsen, J.B., Venturi, D. (2015). A Tamper and Leakage Resilient von Neumann Architecture. In: Katz, J. (eds) Public-Key Cryptography -- PKC 2015. PKC 2015. Lecture Notes in Computer Science(), vol 9020. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46447-2_26
Download citation
DOI: https://doi.org/10.1007/978-3-662-46447-2_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46446-5
Online ISBN: 978-3-662-46447-2
eBook Packages: Computer ScienceComputer Science (R0)