On the looseness of FO derandomization

Daniel J.  Bernstein

Paper 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: public-key encryption Fujisaki–Okamoto transformation T transformation
Contact author(s): authorcontact-footloose @ box cr yp to
History: 2021-07-05: received
Short URL: https://ia.cr/2021/912
License: CC BY

BibTeX

@misc{cryptoeprint:2021/912,
      author = {Daniel J.  Bernstein},
      title = {On the looseness of FO derandomization},
      howpublished = {Cryptology ePrint Archive, Paper 2021/912},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/912}},
      url = {https://eprint.iacr.org/2021/912}
}