Paper 2023/1778

Immunizing Backdoored PRGs

Marshall Ball, New York University
Yevgeniy Dodis, New York University
Eli Goldin, New York University
Abstract

A backdoored Pseudorandom Generator (PRG) is a PRG which looks pseudorandom to the outside world, but a saboteur can break PRG security by planting a backdoor into a seemingly honest choice of public parameters, $pk$, for the system. Backdoored PRGs became increasingly important due to revelations about NIST’s backdoored Dual EC PRG, and later results about its practical exploitability. Motivated by this, at Eurocrypt'15 Dodis et al. [21] initiated the question of immunizing backdoored PRGs. A $k$-immunization scheme repeatedly applies a post-processing function to the output of $k$ backdoored PRGs, to render any (unknown) backdoors provably useless. For $k=1$, [21] showed that no deterministic immunization is possible, but then constructed "seeded" $1$-immunizer either in the random oracle model, or under strong non-falsifiable assumptions. As our first result, we show that no seeded $1$-immunization scheme can be black-box reduced to any efficiently falsifiable assumption. This motivates studying $k$-immunizers for $k\ge 2$, which have an additional advantage of being deterministic (i.e., "seedless"). Indeed, prior work at CCS'17 [37] and CRYPTO'18 [7] gave supporting evidence that simple $k$-immunizers might exist, albeit in slightly different settings. Unfortunately, we show that simple standard model proposals of [37, 7] (including the XOR function [7]) provably do not work in our setting. On a positive, we confirm the intuition of [37] that a (seedless) random oracle is a provably secure $2$-immunizer. On a negative, no (seedless) $2$-immunization scheme can be black-box reduced to any efficiently falsifiable assumption, at least for a large class of natural $2$-immunizers which includes all "cryptographic hash functions." In summary, our results show that $k$-immunizers occupy a peculiar place in the cryptographic world. While they likely exist, and can be made practical and efficient, it is unlikely one can reduce their security to a "clean" standard-model assumption.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in TCC 2023
Keywords
PRGImmunizingCombinersBackdoorsRandom OracleBlack Box Separation
Contact author(s)
marshall @ cs columbia edu
dodis @ cs nyu edu
eli goldin @ nyu edu
History
2023-11-17: approved
2023-11-16: received
See all versions
Short URL
https://ia.cr/2023/1778
License
Creative Commons Attribution-ShareAlike
CC BY-SA

BibTeX

@misc{cryptoeprint:2023/1778,
      author = {Marshall Ball and Yevgeniy Dodis and Eli Goldin},
      title = {Immunizing Backdoored {PRGs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1778},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1778}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.