• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Theory of cryptography >Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms
【24h】

Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms

机译：Goldreich的单向函数候选和近视回溯算法

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Goldreich (ECCC 2000) proposed a candidate one-way function construction which is parameterized by the choice of a small predicate (over d = O(1) variables) and of a bipartite expanding graph of right-degree d. The function is computed by labeling the n vertices on the left with the bits of the input, labeling each of the n vertices on the right with the value of the predicate applied to the neighbors, and outputting the n-bit string of labels of the vertices on the right.rnInverting Goldreich's one-way function is equivalent to finding solutions to a certain constraint satisfaction problem (which easily reduces to SAT) having a "planted solution," and so the use of SAT solvers constitutes a natural class of attacks.rnWe perform an experimental analysis using MiniSat, which is one of the best publicly available algorithms for SAT. Our experiment shows that the running time required to invert the function grows exponentially with the length of the input, and that such an attack becomes infeasible already with small input length (a few hundred bits).rnMotivated by these encouraging experiments, we initiate a rigorous study of the limitations of back-tracking based SAT solvers as attacks against Goldreich's function. Results by Alekhnovich, Hirsch and Itsyk-son imply that Goldreich's function is secure against "myopic" backtracking algorithms (an interesting subclass) if the 3-ary parity predicate P(x_1,x_2, x_3) = x_1 ⊕ x_2 ⊕ x_3 is used. One must, however, use non-linear predicates in the construction, which otherwise succumbs to a trivial attack via Gaussian elimination.rnWe generalized the work of Alekhnovich et al. to handle a more general class of predicates, and we present a lower bound for the construction that uses the predicate P_d(x_1,... ,x_d) := x_1⊕x_2⊕??? ⊕x_(d-2)⊕(x_(d-1)∧x_d) and a random graph.
机译：Goldreich（ECCC 2000）提出了一种候选单向函数构造，该构造通过选择一个小的谓词（在d = O（1）变量上）和一个右度为d的二部展开图进行参数化。通过使用输入的位标记左侧的n个顶点，使用应用于邻居的谓词的值标记右侧的n个顶点中的每个，并输出n位的标签字符串来计算函数。反转Goldreich的单向函数等效于找到具有“已植入解决方案”的某个约束满足问题（很容易简化为SAT）的解决方案，因此使用SAT解算器构成了自然的攻击类别。 rn我们使用MiniSat进行实验分析，MiniSat是SAT公开最好的算法之一。我们的实验表明，反转功能所需的运行时间随输入长度的增长而呈指数增长，并且这种攻击在输入长度较小（几百个比特）的情况下就变得不可行了。在这些令人鼓舞的实验的激励下，我们发起了严格的研究基于回溯的SAT求解器作为对Goldreich函数的攻击的局限性。 Alekhnovich，Hirsch和Itsyk-son的结果表明，如果使用三元奇偶性谓词P（x_1，x_2，x_3）= x_1 x_2⊕x_3，则Goldreich函数对于“近视”回溯算法是安全的。但是，必须在构造中使用非线性谓词，否则它会通过高斯消除而导致微不足道的攻击。我们对Alekhnovich等人的工作进行了概括。来处理更通用的谓词类，我们给出了使用谓词P_d（x_1，...，x_d）的构造的下界：=x_1⊕x_2⊕??? ⊕x_（d-2）⊕（x_（d-1）∧x_d）和一个随机图。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号