The complexity of human computation via a concrete model with an application to passwords.
Proc Natl Acad Sci U S A
; 117(17): 9208-9215, 2020 04 28.
Article
em En
| MEDLINE
| ID: mdl-32291338
ABSTRACT
What can humans compute in their heads? We are thinking of a variety of cryptographic protocols, games like sudoku, crossword puzzles, speed chess, and so on. For example, can a person compute a function in his or her head so that an eavesdropper with a powerful computer-who sees the responses to random inputs-still cannot infer responses to new inputs? To address such questions, we propose a rigorous model of human computation and associated measures of complexity. We apply the model and measures first and foremost to the problem of 1) humanly computable password generation and then, consider related problems of 2) humanly computable "one-way functions" and 3) humanly computable "pseudorandom generators." The theory of human computability developed here plays by different rules than standard computability; the polynomial vs. exponential time divide of modern computability theory is irrelevant to human computation. In human computability, the step counts for both humans and computers must be more concrete. As an application and running example, password generation schemas are humanly computable algorithms based on private keys. Humanly computable and/or humanly usable mean, roughly speaking, that any human needing-and capable of using-passwords can if sufficiently motivated generate and memorize a secret key in less than 1 h (including all rehearsals) and can subsequently use schema plus key to transform website names (challenges) into passwords (responses) in less than 1 min. Moreover, the schemas have precisely defined measures of security against all adversaries, human and/or machine.
Palavras-chave
Texto completo:
1
Base de dados:
MEDLINE
Assunto principal:
Cognição
Idioma:
En
Ano de publicação:
2020
Tipo de documento:
Article