Algorithmic Tamper Proof (ATP) Counter Units for Authentication Devices Using PIN

Though Gennaro et al. discussed the algorithmic tamper proof (ATP) devices using the personal identification number (PIN) with less tamper-proof devices, and proposed counter units which count the number of wrong attempts in user authentication; however, as for the counter unit, they only constructed one which counts the

total

number of wrong attempts. Although large number for the limit of wrong attempts is required for usability, it allows an attacker to search PIN up to the limit and degrades the security. The construction of secure counter units which count the number of

consecutive

wrong attempts remains as an open problem. In this paper, we first formalize the ATP security of counter units, and propose two constructions of counter unit which count the number of consecutive wrong attempts. The security of each construction can be proven under the assumptions of secure signature scheme and random function. The former one is required to store two states in secure memory area (

RP

 − 

Mem

) with low computation cost; and the latter one has high computation cost but is required to store only one state in

RP

 − 

Mem

. This shows the trade-off between the costs of hardware and algorithm.