Cryptology ePrint Archive: Report 2021/912

On the looseness of FO derandomization

Daniel J. Bernstein

Abstract: This paper proves, for two examples of a randomized ROM PKE C, that derandomizing C degrades ROM OW-CPA security by a factor close to the number of hash queries. The first example can be explained by the size of the message space of C but the second cannot. This paper also gives a concrete example of a randomized non-ROM PKE C that appears to have the same properties regarding known attacks.

Category / Keywords: public-key cryptography / public-key encryption, Fujisaki–Okamoto transformation, T transformation

Date: received 5 Jul 2021

Contact author: authorcontact-footloose at box cr yp to

Available format(s): PDF | BibTeX Citation

Version: 20210705:185547 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]