Fine-Grained Non-interactive Key-Exchange: Constructions and Lower Bounds
Fine-Grained Non-interactive Key-Exchange: Constructions and Lower Bounds
复制标题
细粒度非交互式密钥交换：构造和下界
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Elahe Sadeghi
中科院分区：
文献类型：
--
作者：
Abtin Afshar;Geoffroy Couteau;Mohammad Mahmoody;Elahe Sadeghi
． 在这项工作中，我们在细粒度设置中启动了K -NIKE协议的研究，其中诚实方的运行时间与对手的运行时间之间存在多项式差距。我们的目标是证明在K≥3时，基于比K -NIKE更弱的假设的这种协议的可能性，或者不可能性。我们的贡献是三重的。我们证明了随机预言可以用于获得每个常数K的细粒度K - nike协议。特别是，我们展示了如何将Merkle的两方协议推广到K方，以这样的方式，诚实的一方每个请求n次查询，而对手需要n K/ (K−1)次查询随机oracle才能找到密钥。-然后通过进一步使用代数结构来提高安全性，同时避免了配对。特别是，我们展示了在Shoup的通用组模型中存在一个4方NIKE，诚实方的查询数量与对手的查询数量之间存在二次差。-最后，我们证明了使用纯代数方法获得3-NIKE的局限性。特别地，我们证明了Maurer泛型群模型中的任何n -查询3-NIKE协议都可以被O (n 2)-查询攻击者破坏。与Shoup的GGM相比，Maurer的GGM对双方和对手都更有限，因为没有明确的群体元素标签。尽管有更多的限制，这个模型仍然捕获了Diffie Hellman协议。在我们的工作之前，可以使用任何多项式数量的查询来破坏Maurer模型中的3-NIKE协议。
. In this work, we initiate a study of K -NIKE protocols in the fine-grained setting, in which there is a polynomial gap between the running time of the honest parties and that of the adversary. Our goal is to show the possibility, or impossibility, of basing such protocols on weaker assumptions than those of K -NIKE for K ≥ 3. Our contribution is threefold. – We show that random oracles can be used to obtain fine-grained K -NIKE protocols for every constant K . In particular, we show how to generalize Merkle’s two-party protocol to K parties in such a way that the honest parties ask n queries each, while the adversary needs n K/ ( K − 1) queries to the random oracle to find the key. – We then improve the security by further using algebraic structures, while avoiding pairings. In particular, we show that there is a 4-party NIKE in Shoup’s generic group model with a quadratic gap between the number of queries by the honest parties vs. that of the adversary. – Finally, we show a limitation of using purely algebraic methods for obtaining 3-NIKE. In particular, we show that any n -query 3-NIKE protocol in Maurer’s generic group model can be broken by a O ( n 2 )-query attacker. Maurer’s GGM is more limited compared with Shoup’s both for the parties and the adversary, as there are no explicit labels for the group elements. Despite being more limited, this model still captures the Diffie Hellman protocol. Prior to our work, it was open to break 3-NIKE protocols in Maurer’s model with any polynomial number of queries.
细粒度环境中的公钥密码学
DOI：
10.1007/978-3-030-26954-8_20
发表时间：
2019
期刊：
Advances in Cryptology {\textendash} {CRYPTO} 2019
影响因子：
--
作者：
LaVigne, R.;Lincoln, A.;Vassilevska Williams, V.
通讯作者：
Vassilevska Williams, V.