Related randomness attacks for public key crypto systems

Abstract

We initiate the study of related randomness attack in the face of a number of practical attacks in public key cryptography, ranges from active attacks like fault-injection, to passive attacks like software (mis)implementation on choosing random numbers. Our new definitions cover the well-known related-key attacks (RKA) where secret keys are related, and a number of new attacks, namely, related encryption randomness attacks, related signing randomness attacks, and related public key attacks. We provide generic constructions for security against these attacks, which are efficiently built upon normal encryption and signature schemes, leveraging RKA-secure pseudorandom function and generator.