Immunizing Backdoored PRGs

Marshall Ball, Yevgeniy Dodis, Eli Goldin

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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. [22] 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, [22] 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≥ 2, which have an additional advantage of being deterministic (i.e., “seedless”). Indeed, prior work at CCS’17 [37] and CRYPTO’18 [8] gave supporting evidence that simple k-immunizers might exist, albeit in slightly different settings. Unfortunately, we show that simple standard model proposals of [8, 37] (including the XOR function [8]) 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.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 21st International Conference, TCC 2023, Proceedings
EditorsGuy Rothblum, Hoeteck Wee
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages30
ISBN (Print)9783031486203
StatePublished - 2023
Event21st International conference on Theory of Cryptography Conference, TCC 2023 - Taipei, Taiwan, Province of China
Duration: Nov 29 2023Dec 2 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14371 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference21st International conference on Theory of Cryptography Conference, TCC 2023
Country/TerritoryTaiwan, Province of China

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Immunizing Backdoored PRGs'. Together they form a unique fingerprint.

Cite this