arXiv:2507.05972cs.CCcs.CR2025-07中稿 · TCC 2025被引 6

统一证明了计算难与伪熵的等价关系,适用于多种熵定义。

Generalized and Unified Equivalences between Hardness and Pseudoentropy

  • 用统一函数同时刻画计算难与随机性
  • 对字母表大小的依赖从多项式变为指数级提升
  • 适合理论计算机与密码学研究者阅读

伪熵表征为计算难与计算随机性之间的关系提供了精确量化描述。我们证明了一个统一的伪熵表征,推广并强化了均匀与非均匀计算模型中的先前结果。该表征适用于一类广义熵概念,包括香农熵和最小熵作为特例。不同熵定义的表征可由单一通用函数同时实现,该函数同时捕捉计算难与计算随机性。关键技术洞察是:权重受限校准(源自算法公平性最新文献)与标准计算不可区分性(公平性文献中称为多准确性)足以证明一般熵概念的伪熵表征。为此,我们证明了泄漏模拟引理的增强版本,进一步将复杂性理论正则性引理(从布尔函数扩展到大字母表函数)。该增强版引理使我们对字母表大小的依赖实现指数级改进,优于基于更强多校准概念的Casacuberta、Dwork和Vadhan(2024)的结果。我们还证明,对于多校准甚至更弱的校准多准确性,这种指数依赖是不可避免的。

原文摘要 · Abstract (English)

Pseudoentropy characterizations give quantitatively precise formulations of the relationship between computational hardness and computational randomness. We prove a unified pseudoentropy characterization that generalizes and strengthens previous results in both uniform and nonuniform models of computation. Our characterization applies to a general family of entropy notions, including Shannon entropy and min-entropy as special cases. Moreover, the characterizations for these different entropy notions can be witnessed simultaneously by a single universal function, which captures both computational hardness and computational randomness. A key technical insight is that weight-restricted calibration, from the recent literature on algorithmic fairness, together with standard computational indistinguishability (known as multiaccuracy in the fairness literature), suffices for proving pseudoentropy characterizations for general entropy notions. To obtain this combination of properties, we prove an enhanced version of the Leakage Simulation Lemma (Jetchev and Pietrzak, 2014), which in turn extends the Complexity Theoretic-Regularity Lemma (Trevisan, Tulsiani, and Vadhan, 2009) from boolean functions to ones over a larger alphabet. Our Enhanced Regularity/Leakage-Simulation Lemma enables us to obtain an exponential improvement in the dependence on the alphabet size compared with the pseudoentropy characterizations of Casacuberta, Dwork, and Vadhan (2024), which are based on the stronger notion of multicalibration. We also show that this exponential dependence on the alphabet size is inevitable for multicalibration and even for the weaker notion of calibrated multiaccuracy.

伪熵计算复杂性正则性引理密码学

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。