Abstract

Forgery and counterfeiting are emerging as serious security risks in low-cost pervasive computing devices. These devices lack the computational, storage, power, and communication resources necessary for most cryptographic authentication schemes. Surprisingly, low-cost pervasive devices have similar computational capabilities as human beings.

These similarities motivate the adoption of techniques from human-computer security to the pervasive computing setting. One particular human-to-computer authentication protocol designed by Hopper and Blum (HB) [4] [5] is shown to be practical for low-cost pervasive devices in [6]. We offer an improved, concrete proof of security against passive adversaries in [3].

We also offers a new, augmented version of the HB protocol, named HB+, that is secure against active adversaries in [3]. HB+ is a novel, symmetric authentication protocol with a simple, low-cost implementation. We prove the security of the HB+ protocol against active adversaries based on the hardness of the Learning Parity with Noise (LPN) problem.

We will continue to improve the concrete security analysis of the HB and HB+ protocols and investigate the underlying hardness of the Learning Parity with Noise problem. We will also analyze the practical cost of attacks using the best know algorithm due to Blum et al. [2]. Finally, we will investigate other human-computer or learning-based primitives, like those in [1], that may be suitable for the pervasive computing setting.

References

[1] Avrim Blum, Merrick Furst, Michael Kearns, and Richard J. Lipton. Cryptographic Primitives Based on Hard Learning Problems. In Advances in Cryptology Ð CRYPTOÕ93 (1994), vol. 773 of Lecture Notes in Computer Science, pp. 278Ð291.

[2] Avrim Blum, Adam Kalai, and Hal Wasserman, H. Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model. In Journal of the ACM 50, 4 (July 2003), 506Ð519.

[3] Ari Juels and Stephen A. Weis. Authenticating Pervasive Devices with Human Protocols. In submission, 2005.

[4] Nicholas Hopper and Manuel Blum. A Secure Human-Computer Authentication Scheme. Tech. Rep. CMU-CS-00-139, Carnegie Mellon University, 2000.

[6] Nicholas Hopper and Manuel Blum. Secure Human Identification Protocols. In Advances in Cryptology - ASIACRYPT (2001), vol. 2248 of Lecture Notes in Computer Science, pp. 52Ð66.

[7] Stephen A. Weis. Security Parallels Between People and Pervasive Devices. In IEEE Conference on Pervasive Computing and Communication. March 2005.