Fiat-Shamir Identification Scheme Immune to the Hardware Fault Attacks

Abstract

The Fiat-Shamir identification scheme is popular for "light" consumer devices, such as smart cards, in a wide range of consumer services. However, it can be vulnerable to fault attacks, even though a cryptographic algorithm is theoretically secure. Thus, a study on cryptanalysis and countermeasures to fault attacks is crucial. This article proposes a secure and practical modification of the Fiat-Shamir identification scheme resistant against fault attacks. A straightforward protection is to check integrity of the intermediate values and outputs at each step. However, this approach may be a bottleneck of the entire scheme and are attained at the expense of increased computational overhead that is similar to the overhead of the identification scheme. The proposed scheme is designed to propagate faults induced in a target variable to other parts without conditional branches. Therefore, a relatively small overhead enables implementation of the proposed scheme in small cryptographic devices such as smart cards.