Security of Okamoto Identification Scheme - a Defense against 
                              Ephemeral Key Leakage and Setup


                         Lukasz Krzywiecki and  Miroslaw Kutylowski
       
                        Faculty of Fundamental Problems of Technology,
                         Wroclaw University of Science and Technology
       

We consider a framework, where an adversary may learn the ephemeral values used by the prover 
within an identification protocol, aiming to get the secret keys of the user, or just to  
impersonate the prover subsequently. Unfortunately, most classical cryptographic identification 
protocols are exposed to such attacks, which might be  quite realistic in case of either weak or 
malicious (pseudo)random number generators implemented in hardware. 

We focus on the Okamoto \textit{Identification} \textit{Scheme} ($\is$), and show how to make it
immune to such threats. For that purpose we use the model proposed recently which regards a scheme 
as secure, if the malicious verifier, allowed to set the prover's ephemerals in the query stage, 
cannot impersonate the prover later on. Thereby, by proving our scheme secure in that model, 
we increase the practical security level in case of lack of sufficient control over the production process 
of devices, where the scheme is implemented, and where erroneous/malicious/weak (pseudo)random 
number generators make such attacks possible. This addresses also the problems related to aging of 
these generators. 

Keywords: identification scheme; Okamoto scheme, ephemeral random values; leakage; security; 
impersonation; provable security; simulatability

to appear in AsiaCCS-SCC 2017