Cryptology ePrint Archive: Report 2020/1316

Security of Public Key Encryption against Resetting Attacks

Juliane Krämer and Patrick Struck

Abstract: Ciphertext indistinguishability under chosen plaintext attacks is a standard security notion for public key encryption. It crucially relies on the usage of good randomness and is trivially unachievable if the randomness is known by the adversary. Yilek (CT-RSA'10) defined security against resetting attacks, where randomness might be reused but remains unknown to the adversary. Furthermore, Yilek claimed that security against adversaries making a single query to the challenge oracle implies security against adversaries making multiple queries to the challenge oracle. This is a typical simplification for indistinguishability security notions proven via a standard hybrid argument. The given proof, however, was pointed out to be flawed by Paterson, Schuldt, and Sibborn (PKC'14). Prior to this work, it has been unclear whether this simplification of the security notion also holds in case of resetting attacks. We remedy this state of affairs as follows. First, we show the strength of resetting attacks by showing that many public key encryption schemes are susceptible to these attacks. As our main contribution, we show that the simplification to adversaries making only one query to the challenge oracle also holds in the light of resetting attacks. More precisely, we show that the existing proof can not be fixed and give a different proof for the claim. Finally, we define real-or-random security against resetting attacks and prove it equivalent to the notion by Yilek which is of the form left-or-right.

Category / Keywords: public-key cryptography / Public Key Encryption, Resetting Attacks, Provable Security

Original Publication (with minor differences): 21st International Conference on Cryptology in India (INDOCRYPT 2020)

Date: received 21 Oct 2020, last revised 26 Oct 2020

Contact author: patrick at qpc tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20201026:093013 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]