Conference articles PUBLISHED

1. Andersen, G; Conitzer, V, ATUCAPTS: Automated tests that a user cannot pass twice simultaneously, IJCAI International Joint Conference on Artificial Intelligence, vol. 2016-January (January, 2016), pp. 3662-3669.
   (last updated on 2024/04/19)

   Abstract:
   In highly anonymous environments such as the Internet, many applications suffer from the fact that a single user can pose as multiple users. Indeed, presumably many potential applications do not even get off the ground as a result. Consider the example of an online vote. Requiring voters to provide identifying information, to the extent that this is even feasible, can significantly deter participation. On the other hand, not doing so makes it possible for a single individual to vote more than once, so that the result may become almost meaningless. (A quick web search will reveal many examples of Internet polls with bizarre outcomes.) CAPTCHAs may prevent running a program that votes many times, but they do nothing to prevent a single user from voting many times by hand. In this paper, we propose ATUCAPTS (Automated Tests That a User Cannot Pass Twice Simultaneously) as a solution. ATUCAPTS are automatically generated tests such that it is (1) easy for a user to pass one instance, but (2) extremely difficult for a user to pass two instances at the same time. Thus, if it is feasible to require all users to take such a test at the same time, we can verify that no user holds more than one account. We propose a specific class of ATUCAPTS and present the results of a human subjects study to validate that they satisfy the two properties above. We also introduce several theoretical models of how well an attacker might perform and show that these models still allow for good performance on both (1) and (2) with reasonable test lengths.