Theory of Cryptography - 20th International Conference, TCC 2022, Chicago, IL, USA, November 7-10, 2022, Proceedings, Part III
Theory of Cryptography - 20th International Conference, TCC 2022, Chicago, IL, USA, November 7-10, 2022, Proceedings, Part III
复制标题
密码学理论 - 第 20 届国际会议，TCC 2022，美国伊利诺伊州芝加哥，2022 年 11 月 7-10 日，会议记录，第三部分
DOI：
10.1007/978-3-031-22368-6_8
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Bauer B
中科院分区：
文献类型：
--
作者：
Bauer B
通用群模型（general -group model， GGM）在分析许多密码假设和协议方面非常成功。然而，众所周知，GGM是“不可实例化的”，也就是说，GGM中有一些安全的协议，在使用任何真实世界的组时都是不安全的。这激发了对标准模型概念的研究，将现实世界的群体在某种意义上“看起来很一般”。我们引入了一个称为伪泛型群（PGG）的标准模型定义，在这个定义中，我们需要使用基数和（最初）未知的群生成器进行幂运算，以得到看起来随机的群元素。从本质上讲，我们的框架巧妙地将Bellare， Hoang和Keelveedhi （BHK, CRYPTO 2013）的通用计算提取器（Universal Computational Extractors）的有影响力的概念提升到一个基础理想参考对象是通用组的设置。我们得到的定义同时推广了Uber假设族，因为不再需要对群指数进行多项式归纳。我们的定义贡献的核心是代数不可预测性的新概念，它将标准的施瓦茨-齐佩尔引理重新解释为对源的限制。我们在有辅助输入的GGM （AI-GGM）中证明了我们定义的正确性。我们剩下的结果集中在pgg的应用上。我们首先证明了pg确实是Uber的泛化。然后，我们提出了在指数不是多项式诱导的情况下的一些应用。特别地，我们证明了ElGamal的简单变体满足了以前只有通过复杂和低效的方案才能实现的几个高级安全目标。我们还展示了pgg意味着分割源的uce，这在几个应用程序中已经足够了。作为我们的AI-GGM可行性的推论，我们在存在预处理攻击的情况下获得了所有这些应用程序的安全性。我们的一些含义利用了一种新型的哈希函数，我们称之为线性相关驱逐舰（ldd），并使用它将标准不可预测性转换为代数不可预测性。我们给出了低度源的LDD，并通过压缩论证表明随机函数符合此定义，从而建立了它们对所有源的合理性。
The generic-group model (GGM) has been very successful in making the analyses of many cryptographic assumptions and protocols tractable. It is, however, well known that the GGM is “uninstantiable,” i.e., there are protocols secure in the GGM that are insecure when using any real-world group. This motivates the study of standard-model notions formalizing that a real-world group in some sense “looks generic.”We introduce a standard-model definition calledpseudo-generic group (PGG), where we require exponentiations with base an (initially) unknown group generator to result in random-looking group elements. In essence, our framework delicately lifts the influential notion of Universal Computational Extractors of Bellare, Hoang, and Keelveedhi (BHK, CRYPTO 2013) to a setting where the underlying ideal reference object is a generic group. The definition we obtain simultaneously generalizes the Uber assumption family, as group exponents no longer need to be polynomially induced. At the core of our definitional contribution is a new notion ofalgebraic unpredictability, which reinterprets the standard Schwartz–Zippel lemma as a restriction on sources. We prove the soundness of our definition in the GGM with auxiliary-input (AI-GGM).Our remaining results focus on applications of PGGs. We first show that PGGs are indeed a generalization of Uber. We then present a number of applications in settings where exponents are not polynomially induced. In particular we prove that simple variants of ElGamal meet several advanced security goals previously achieved only by complex and inefficient schemes. We also show that PGGs imply UCEs for split sources, which in turn are sufficient in several applications. As corollaries of our AI-GGM feasibility, we obtain the security of all these applications in the presence of preprocessing attacks.Some of our implications utilize a novel type of hash function, which we calllinear-dependence destroyers(LDDs) and use to convert standard into algebraic unpredictability. We give an LDD for low-degree sources, and establish their plausibility for all sources by showing, via a compression argument, that random functions meet this definition.