A Sub-0.5V Lattice-Based Public-Key Encryption Scheme for RFID Platforms in 130nm CMOS

Yu Yao, Jiawei Huang, Sudhanshu Khanna, abhi shelat, Benton Highsmith Calhoun, John Lach, and David Evans
2011 Workshop on RFID Security (RFIDsec'11 Asia)
Wuxi, China
6-8 April 2011.

Abstract

Implementing public-key cryptography on passive RFID tags is very challenging due to the limited die size and power available. Typical public-key algorithms require complex logical components such as modular exponentiation in RSA. We demonstrate the feasibility of implementing public-key encryption on low-power, low cost passive RFID tags to large-scale private identification. We use Oded Regev's Learning-With-Error (LWE) cryptosystem, which is provably secure under the hardness assumption of classic lattice problems. The advantage of using the LWE cryptosystem is its intrinsic computational simplicity (the main operation is modular addition). We leverage the low speed of RFID application by using circuit design with supply voltage close to transistor threshold (Vt) to lower power. This paper presents protocols for using the LWE cipher to provide private identification, evaluates a design for implementing those protocols on passive RFID tags, and reports on simulation experiments that demonstrate the feasibility of this approach.

Keywords: RFID Privacy, Private Identification, LWE Public-Key Cryptosystems, Sub-Threshold Design, Lattice Encryption, Passive RFID

Paper

Full paper (19 pages): [PDF]
CS 655 David Evans - Publications
University of Virginia
Department of Computer Science
David Evans
evans@cs.virginia.edu