Paper 2004/138

How to Disembed a Program?

Benoit Chevallier-Mames, David Naccache, Pascal Paillier, and David Pointcheval


This paper presents the theoretical blueprint of a new secure token called the Externalized Microprocessor (XmP). Unlike a smart-card, the XmP contains no ROM at all. While exporting all the device's executable code to potentially untrustworthy terminals poses formidable security problems, the advantages of ROM-less secure tokens are numerous: chip masking time disappears, bug patching becomes a mere terminal update and hence does not imply any roll-out of cards in the field. Most importantly, code size ceases to be a limiting factor. This is particularly significant given the steady increase in on-board software complexity. After describing the machine's instruction-set we will introduce two XmP variants. The first design is a public-key oriented architecture which relies on a new RSA screening scheme and features a relatively low communication overhead at the cost of computational complexity, whereas the second variant is secret-key oriented and relies on simple MACs and hash functions but requires more communication. For each of these two designs, we propose two protocols that execute and dynamically authenticate arbitrary programs. We also provide a strong security model for these protocols and prove their security under appropriate complexity assumptions.

Available format(s)
Publication info
Published elsewhere. An extended abstract appears in CHES'04
Contact author(s)
pascal paillier @ gemplus com
2004-06-16: received
Short URL
Creative Commons Attribution


      author = {Benoit Chevallier-Mames and David Naccache and Pascal Paillier and David Pointcheval},
      title = {How to Disembed a Program?},
      howpublished = {Cryptology ePrint Archive, Paper 2004/138},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.