Data structures meet cryptography: 3SUM with preprocessing
Data structures meet cryptography: 3SUM with preprocessing
复制标题
数据结构与密码学的结合：带预处理的 3SUM
DOI：
10.1145/3357713.3384342
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Vaikunathan, Vinod.
中科院分区：
文献类型：
--
作者：
Golovnev, Alexander;Guo, Siyao;Horel, Thibaut;Park, Sunoo;Vaikunathan, Vinod.
本文展示了数据结构问题与密码学对抗预处理攻击之间的几种联系。我们的结果跨越了数据结构上界、密码学应用和数据结构下界，如下所述。首先，我们应用Fiat-Naor反演，一种起源于密码学的技术，来获得数据结构上界。特别是，我们的技术产生了一套算法的空间和（在线）时间T的预处理版本的N-输入3SUM问题，其中S3·T=O（N6）。这反驳了一个强有力的猜想（Goldstein等人，WADS 2017）指出，对于S =N2−δ和T =N1−δ，对于任何常数δ> 0，没有数据结构可以解决这个问题。其次，我们证明了一大类（静态）数据结构问题的下界与随机预言模型中的单向函数之间的等价性，这些函数可以抵抗非常强的预处理攻击。具体地说，给定一个随机函数F：[N] → [N]（作为一个oracle访问），我们展示了如何将其编译成一个函数GF：[N2] → [N2]，它可以抵抗在查询时间T中运行的S位预处理攻击，其中ST =O（N2−ε）（假设3SUM上有一个相应的数据结构下界）。相反，Hellman的一个经典结果告诉我们，F本身可以更容易地被反转，比如在N2/3时间内用N2/3位预处理。我们还表明，更强的下限遵循硬度kSUM。我们的结果可以被等效地解释为对对手的安全性是非常不均匀的，或有大的辅助输入，或作为一个强大的后门随机oracle. Third面对的安全性，我们给3SUM的非自适应下界匹配的最佳已知的静态数据结构问题的下界。此外，我们表明，我们的下限推广到一系列的几何问题，如三点一条线，多边形包容，和其他。
This paper shows several connections between data structure problems and cryptography against preprocessing attacks. Our results span data structure upper bounds, cryptographic applications, and data structure lower bounds, as summarized next.First, we apply Fiat-Naor inversion, a technique with cryptographic origins, to obtain a data structure upper bound. In particular, our technique yields a suite of algorithms with spaceSand (online) timeTfor a preprocessing version of theN-input 3SUM problem whereS3·T=O(N6). This disproves a strong conjecture (Goldstein et al., WADS 2017) that there is no data structure that solves this problem forS=N2−δandT=N1−δfor any constant δ>0.Secondly, we show equivalence between lower bounds for a broad class of (static) data structure problems and one-way functions in the random oracle model that resist a very strong form of preprocessing attack. Concretely, given a random functionF: [N] → [N] (accessed as an oracle) we show how to compile it into a functionGF: [N2] → [N2] which resistsS-bit preprocessing attacks that run in query timeTwhereST=O(N2−ε) (assuming a corresponding data structure lower bound on 3SUM). In contrast, a classical result of Hellman tells us thatFitself can be more easily inverted, say withN2/3-bit preprocessing inN2/3time. We also show that much stronger lower bounds follow from the hardness of kSUM. Our results can be equivalently interpreted as security against adversaries that are very non-uniform, or have large auxiliary input, or as security in the face of a powerfully backdoored random oracle.Thirdly, we give non-adaptive lower bounds for 3SUM which match the best known lower bounds for static data structure problems. Moreover, we show that our lower bound generalizes to a range of geometric problems, such as three points on a line, polygon containment, and others.
登录
查看更多内容
系统线性数据结构与矩阵刚性的等价
DOI：
--
发表时间：
2019
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Sivaramakrishnan Natarajan Ramamoorthy;Cyrus Rashtchian
通讯作者：
Cyrus Rashtchian
是的，有一个不经意的 RAM 下界！
DOI：
--
发表时间：
2018
期刊：
IACR Cryptology ePrint Archive
影响因子：
--
作者：
Kasper Green Larsen;J. Nielsen
通讯作者：
J. Nielsen
正交向量索引
DOI：
10.4230/lipics.isaac.2017.40
发表时间：
2017
期刊：
ArXiv
影响因子：
--
作者：
Isaac Goldstein;Moshe Lewenstein;E. Porat
通讯作者：
E. Porat
空间/时间权衡的条件下界
DOI：
--
发表时间：
2017
期刊：
Workshop on Algorithms and Data Structures
影响因子：
--
作者：
Isaac Goldstein;T. Kopelowitz;Moshe Lewenstein;E. Porat
通讯作者：
E. Porat
用于快速二面旋转的预处理链是困难的，甚至是不可能的
DOI：
--
发表时间：
2002
期刊：
Computational geometry
影响因子：
--
作者：
Michael A. Soss;Jeff Erickson;M. Overmars
通讯作者：
M. Overmars