Public-Key Cryptography in the Fine-Grained Setting
Public-Key Cryptography in the Fine-Grained Setting
复制标题
细粒度环境中的公钥密码学
DOI：
10.1007/978-3-030-26954-8_20
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Vassilevska Williams, V.
中科院分区：
文献类型：
--
作者：
LaVigne, R.;Lincoln, A.;Vassilevska Williams, V.
密码学很大程度上基于未经证实的假设，这些假设虽然可信，但可能会失败。值得注意的是，如果或者如果我们住在佩西兰，那么当前所有的加密假设都将被打破。一个引人注目的问题是 Pessiland 中是否可能存在任何有趣的密码学。解决这个问题的一个自然方法是将密码学建立在细粒度复杂性的假设之上。 Ball、Rosen、Sabin 和 Vasudevan [BRSV’17] 从流行的硬度假设（例如正交向量 (OV) 猜想）出发尝试了这一点。他们得到了平均来说很难的问题，假设 OV 和其他问题在最坏的情况下是困难的。他们获得了工作证明，并希望利用平均情况下的难题来构建细粒度的单向函数。不幸的是，他们证明使用他们的方法构建一个将违反流行的硬度假设。这激发了对其他细粒度平均情况难题的研究。本文的主要目标是为细粒度平均情况假设确定足够的属性，该假设隐含密码原语，例如细粒度公钥密码术（PKC）。我们的主要贡献是加密密钥交换的新颖构造，以及少量相对较弱的结构属性的定义，这样，如果计算问题满足它们，我们的密钥交换就具有基于该问题的难度的可证明的细粒度安全保证。然后，我们证明，来自细粒度复杂性的关键问题 Zero-k-Clique 的自然且合理的平均情况假设满足我们的属性。即使在这些较弱的假设下，我们也开发了细粒度的单向函数和硬核位。以前的工作必须假设随机预言或存在强大的单向函数才能在 O(n) 时间内获得可计算的密钥交换以对抗对手（参见 [Merkle’78] 和 [BGI’08]），而我们的假设似乎要弱得多。我们的密钥交换在诚实方和对手的计算之间与之前的工作有类似的差距，同时是非交互式的，这意味着细粒度的 PKC。
Cryptography is largely based on unproven assumptions, which, while believable, might fail. Notably if, or if we live in Pessiland, then all current cryptographic assumptions will be broken. A compelling question is if any interesting cryptography might exist in Pessiland.A natural approach to tackle this question is to base cryptography on an assumption from fine-grained complexity. Ball, Rosen, Sabin, and Vasudevan [BRSV’17] attempted this, starting from popular hardness assumptions, such as the Orthogonal Vectors (OV) Conjecture. They obtained problems that are hard on average, assuming that OV and other problems are hard in the worst case. They obtained proofs of work, and hoped to use their average-case hard problems to build a fine-grained one-way function. Unfortunately, they proved that constructing one using their approach would violate a popular hardness hypothesis. This motivates the search for other fine-grained average-case hard problems.The main goal of this paper is to identify sufficient properties for a fine-grained average-case assumption that imply cryptographic primitives such as fine-grained public key cryptography (PKC). Our main contribution is a novel construction of a cryptographic key exchange, together with the definition of a small number of relatively weak structural properties, such that if a computational problem satisfies them, our key exchange has provable fine-grained security guarantees, based on the hardness of this problem. We then show that a natural and plausible average-case assumption for the key problem Zero-k-Clique from fine-grained complexity satisfies our properties. We also develop fine-grained one-way functions and hardcore bits even under these weaker assumptions.Where previous works had to assume random oracles or the existence of strong one-way functions to get a key-exchange computable inO(n) time secure againstadversaries (see [Merkle’78] and [BGI’08]), our assumptions seem much weaker. Our key exchange has a similar gap between the computation of the honest party and the adversary as prior work, while being non-interactive, implying fine-grained PKC.
登录
查看更多内容
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
Yehuda Lindell
通讯作者：
Yehuda Lindell
3SUM 的次二次算法
影响因子：
1.1
作者：
Ilya Baran;E. Demaine;M. Patrascu
通讯作者：
M. Patrascu
影响因子：
2.5
作者：
Russell, A;Wang, H
通讯作者：
Wang, H
DOI：
10.1137/090766991
发表时间：
2009-01
期刊：
--
影响因子：
--
作者：
Elad Hazan;Robert Krauthgamer
通讯作者：
Elad Hazan;Robert Krauthgamer
并行重复是否会降低计算合理协议中的错误？
DOI：
--
发表时间：
1997
期刊：
Proceedings 38th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
M. Bellare;R. Impagliazzo;M. Naor
通讯作者：
M. Naor