Abstract
Tamper-proof devices are pretty powerful. They can be used to have better security in applications. In this work we observe that they can also be maliciously used in order to defeat some common privacy protection mechanisms. We propose the theoretical model of trusted agent to formalize the notion of programmable secure hardware. We show that protocols not using tamper-proof devices are not deniable if malicious verifiers can use trusted agents. In a strong key registration model, deniability can be restored, but only at the price of using key escrow. As an application, we show how to break invisibility in undeniable signatures, how to sell votes in voting schemes, how to break anonymity in group/ring signatures, and how to carry on the Mafia fraud in non-transferable protocols. We conclude by observing that the ability to put boundaries in computing devices prevents from providing full control on how private information spreads: the concept of sealing a device is in some sense incompatible with privacy.
A preliminary version of this paper was presented as a poster at EUROCRYPT’09.
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
Barak, B., Canetti, R., Nielsen, J.B., Pass, R.: Universally composable protocols with relaxed set-up assumptions. In: Annual ACM Symposium on Theory of Computing: FOCS 2004, pp. 186–195. IEEE Computer Society Press, Los Alamitos (2004)
Camenisch, J.L., Michels, M.: Confirmer signature schemes secure against adaptive adversaries (Extended abstract). In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 243–258. Springer, Heidelberg (2000)
Canetti, R.: Obtaining universally composable security: Towards the bare bones of trust. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 88–112. Springer, Heidelberg (2007)
Canetti, R., Fischlin, M.: Universally composable commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 19–40. Springer, Heidelberg (2001)
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: Annual ACM Symposium on Theory of Computing: STOC 2002, pp. 494–503. ACM Press, New York (2002)
Chaum, D., Van Antwerpen, H.: Undeniable signatures. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 212–216. Springer, Heidelberg (1990)
Cramer, R.: Modular design of secure, yet practical cryptographic protocols. Phd thesis, University of Amsterdam (1996)
Damgård, I.: On Σ-protocols. Lecture notes, University of Aahrus (2005), http://www.daimi.au.dk/%7Eivan/Sigma.pdf
Desmedt, Y.: Major security problems with the unforgeable (feige)-fiat-shamir proofs of identity and how to overcome them. In: The 6th Worldwide Congress on Computer and Communications Security and Protection: Securicom 1988, pp. 147–149. SEDEP (1988)
Desmedt, Y.G., Quisquater, J.-J.: Public-key systems based on the difficulty of tampering. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 111–117. Springer, Heidelberg (1987)
Desmedt, Y.G., Yung, M.: Weaknesses of undeniable signature schemes. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 205–220. Springer, Heidelberg (1991)
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC 1985, pp. 291–304. ACM Press, New York (1985)
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM Journal of Computing 18(1), 186–208 (1989)
Gratzer, V., Naccache, D.: Alien vs. quine, the vanishing circuit and other tales from the industry’s crypt. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 48–58. Springer, Heidelberg (2006)
Jakobsson, M.: Blackmailing using undeniable signatures. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 425–427. Springer, Heidelberg (1995)
Jakobsson, M., Sako, K., Impagliazzo, R.: Designated verifier proofs and their applications. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 143–154. Springer, Heidelberg (1996)
Katz, J.: Universally composable multi-party computation using tamper-proof hardware. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 115–128. Springer, Heidelberg (2007)
Mateus, P.: Attacking zero-knowledge proof systems. Habilitation thesis, Department of Mathematics, Instituto Superior Técnico, 1049-001 Lisboa, Portugal, 2005. Awarded the Portuguese IBM Scientific Prize (2005) ( in Portuguese)
Mateus, P., Moura, F., Rasga, J.: Transferring proofs of zero-knowledge systems with quantum correlations. In: Dini, P., et al. (eds.) Proceedings of the First Workshop on Quantum Security: QSec 2007, p. 9. IEEE Computer Society Press, Los Alamitos (2007)
Monnerat, J., Vaudenay, S.: Short 2-move undeniable signatures. In: Nguyen, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 19–36. Springer, Heidelberg (2006)
Pass, R.: On deniability in the common reference string and random oracle model. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 316–337. Springer, Heidelberg (2003)
Ristenpart, T., Yilek, S.: The power of proofs-of-possession: Securing multiparty signatures against rogue-key attacks. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 228–245. Springer, Heidelberg (2007)
Rivest, R.L., Shamir, A., Tauman, Y.: How to leak a secret. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 552–565. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mateus, P., Vaudenay, S. (2009). On Tamper-Resistance from a Theoretical Viewpoint. In: Clavier, C., Gaj, K. (eds) Cryptographic Hardware and Embedded Systems - CHES 2009. CHES 2009. Lecture Notes in Computer Science, vol 5747. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04138-9_29
Download citation
DOI: https://doi.org/10.1007/978-3-642-04138-9_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04137-2
Online ISBN: 978-3-642-04138-9
eBook Packages: Computer ScienceComputer Science (R0)