We construct t-non-malleable extractors—which allow an attacker to tamper with a source t times—for high min-entropy sources samplable by poly-time hierarchy circuits and for tampering classes corresponding to poly-time hierarchy functions from derandomization-type assumptions. We then show an application of this new object to ruling out constructions of succinct, non-interactive, arguments (SNARGs) secure against uniform adversaries from uniform falsifiable assumptions via a class of black-box reductions that has not been previously considered in the literature. This class of black-box reductions allows the reduction to arbitrarily set the coins, as well as the input, of the uniform adversary it interacts with. The class of reductions we consider is restricted in allowing only non-adaptive queries to the adversary.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Uniform Black-Box Separations via Non-malleable Extractors

  • Marshall Ball,
  • Dana Dachman-Soled

摘要

We construct t-non-malleable extractors—which allow an attacker to tamper with a source t times—for high min-entropy sources samplable by poly-time hierarchy circuits and for tampering classes corresponding to poly-time hierarchy functions from derandomization-type assumptions. We then show an application of this new object to ruling out constructions of succinct, non-interactive, arguments (SNARGs) secure against uniform adversaries from uniform falsifiable assumptions via a class of black-box reductions that has not been previously considered in the literature. This class of black-box reductions allows the reduction to arbitrarily set the coins, as well as the input, of the uniform adversary it interacts with. The class of reductions we consider is restricted in allowing only non-adaptive queries to the adversary.