On the Hardness of the Sum of k Mins Problem
On the Hardness of the Sum of k Mins Problem
复制标题
关于k分钟和问题的难度
DOI：
10.1093/comjnl/bxr070
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Huaxiong Wang
中科院分区：
文献类型：
--
作者：
H. Asghar;J. Pieprzyk;Huaxiong Wang
kmins和协议是由Hopper和Blum提出的一种安全身份认证协议。该协议的目标是让一个独立的人安全地认证到远程服务器。该协议的主要组成部分是k mins问题的总和。解决这个问题的难度决定了协议的安全性。本文证明了k mins求和问题是NP-完全的，且是W[1]-困难的.后一个概念涉及固定参数的棘手性。我们还讨论了在资源受限的设备中使用的k分钟协议的总和。
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.