On the hardness of the sum of K mins problem
Data(s) |
01/10/2011
|
---|---|
Resumo |
The sum of k mins protocol was proposed by Hopper and Blum as a protocol for secure human identification. The goal of the protocol is to let an unaided human securely authenticate to a remote server. The main ingredient of the protocol is the sum of k mins problem. The difficulty of solving this problem determines the security of the protocol. In this paper, we show that the sum of k mins problem is NP-Complete and W[1]-Hard. This latter notion relates to fixed parameter intractability. We also discuss the use of the sum of k mins protocol in resource-constrained devices. |
Identificador | |
Publicador |
Oxford University Press |
Relação |
DOI:10.1093/comjnl/bxr070 Asghar, Hassan Jameel, Pieprzyk, Josef, & Wang, Huaxiong (2011) On the hardness of the sum of K mins problem. The Computer Journal, 54(10), pp. 1652-1660. |
Direitos |
© The Author 2011. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved. For Permissions, please email: journals.permissions@oup.com |
Fonte |
School of Electrical Engineering & Computer Science; Science & Engineering Faculty |
Palavras-Chave | #Computational complexity #Human identification protocols #NP-complete problems #Sum of k Mins |
Tipo |
Journal Article |