KHAP: Using Keyed Hard AI Problems to Secure Human Interfaces

  • Jeff King Georgia Institute of Technology
  • Andre dos Santos Georgia Institute of Technology
  • Chaoting Xuan Georgia Institute of Technology


There is often a need for users to securely interact with a remote computing system. Typical solutions assume that a local trusted computing platform is available, but this is often not the case. We introduce KHAP, a protocol for using hard artificial intelligence problems to provide message authentication checks centered around a human verifier. We also formally introduce the notion of a keyed hard AI problem, which is one that uses an authentication key to prove the source and integrity of a message. We give examples of some keyed hard AI problems, as well as examples of KHAP’s applicability to the specific problem domains of Internet voting and the use of smartcards for digital signatures.


ATM machines rigged (newspaper article). The Globe and Mail, August 12, 2003,

Istvn Zsolt Berta and Istvn Vajda. Documents from malicious terminals., 2003.

H. Gobioff, S. Smith, J. Tygar, and B. Yee. Smartcards in hostile environments. In Proceedings of the Second USENIX Workshop on Electronic Commerce, 1996.

Nicholas J. Hopper and Manuel Blum. Secure human identification protocols. Lecture Notes in Computer Science, 2248, 2001.

G. Kochanski, D. Lopresti, and C Shih. A reverse turing test using speech. In Proceedings of the International Conferences on Spoken Language Processing, Denver, Colorado, September 2002.

Umesh Maheshwari and Radek Vingralek. How to build a trusted database system on untrusted storage. In Proceedings of the 4th Symposium on Operating Systems Design and Implementation, San Diego, October 2000.

T. Matsumoto and H. Imai. Human identification through insecure channel. Advances in Cryptology - EUROCRYPT 91. Lecture Notes in Computer Science, 547, 1991.

Fabian Monrose, Michael K. Reiter, Qi Li, and Susanne Wetzel. Cryptographic key generation from voice. In Proceedings of the IEEE Symposium on Security and Privacy, Oakland, California, May 2001.

Moni Naor and Benny Pinkas. Visual authentication and identification. Lecture Notes in Computer Science, 1294, 1997.

E. Rescorla. HTTP over TLS. IETF RFC 2818.

L. von Ahn, M. Blum, N. Hopper, and J. Langford. CAPTCHA: Using hard AI problems for security. In Proceedings of Eurocrypt 2003, 2003.

B. S. Yee. Using Secure Coprocessors. PhD thesis, Carnegie Mellon University, 1994.
KING, Jeff; SANTOS, Andre dos; XUAN, Chaoting. KHAP: Using Keyed Hard AI Problems to Secure Human Interfaces. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 4. , 2004, Gramado. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2004 . p. 232-243. DOI: