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.

With the goal of ensuring availability of security services such as encryption and authentication, we initiate the study of leakage-resilient threshold cryptography, for achieving formal security guarantee under various key-exposure attacks. A distinctive property of threshold cryptosystems is that a threshold number of secret keys are used in the main cryptographic function such as decryption or signing. Even though some existing security models allow leakages of multiple keys of different users, these keys are not used simultaneously to decrypt a ciphertext or sign a message.