Practical Key Recovery for Discrete-Logarithm Based Authentication Schemes from Random Nonce Bits

被引:1
作者
Bauer, Aurelie [1 ]
Vergnaud, Damien [2 ]
机构
[1] Agence Natl Securite Syst Informat, 51 Blvd Tour Maubourg, F-75700 Paris 07, France
[2] Ecole Normale Super, CNRS, INRIA, F-75230 Paris 05, France
来源
CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS - CHES 2015 | 2015年 / 9293卷
关键词
Schnorr identification; Girault-Poupard-Stern identification; Girault-Poupard-Stern signatures; Statistical cryptanalysis; SECURITY;
D O I
10.1007/978-3-662-48324-4_15
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
We propose statistical cryptanalysis of discrete-logarithm based authentication schemes such as Schnorr identification scheme or Girault-Poupard-Stern identification and signature schemes. We consider two scenarios where an adversary is given some information on the nonces used during the signature generation process or during some identification sessions. In the first scenario, we assume that some bits of the nonces are known exactly by the adversary, while no information is provided about the other bits. We show, for instance, that the GPS scheme with 128-bit security can be broken using only 710 signatures assuming that the adversary knows (on average) one bit per nonce. In the second scenario, we assume that all bits of the nonces are obtained from the correct ones by independent bit flipping with some small probability. A detailed heuristic analysis is provided, supported by extensive experiments.
引用
收藏
页码:287 / 306
页数:20
相关论文
共 22 条