Modern computation is pervasive. Devices from employee ID badges to dog collars are now expected to securely communicate with their environment, often using a device with limited resources such as an RFID chip. To securely communicate, an RFID chip needs to perform authentication and encryption operations that often exceed its computational resources. One solution is to allow an RFID chip to outsource some of its costly computations to some other (potentially malicious) device in the environment, for example, a nearby computer.
In this talk, I will present a comprehensive security definition encapsulating what it means to securely outsource computations to a potentially malicious device. On the negative side, I will discuss some operating environments in which secure outsourcing is impossible to achieve. On the positive side, I will present outsourcing protocols for many desirable operating environments. In fact, we show that for any exponentiation-based cryptographic scheme with n-bit exponents, an RFID chip would normally have to perform O(n) modular multiplications, and yet when following our secure outsourcing protocol this load reduces to O(log2 n). For example, this may reduce an RFID’s work load from 1 million to 400 operations.
This is joint work with Anna Lysyanskaya (Brown University) that appeared in TCC 2005.