Proposal for Research on Fault Resistant Cryptography and the Hardness of Factoring

抗故障密码学和因式分解难度研究提案

• 批准号: 9700283
• 负责人: Richard Lipton
• 金额: $ 32.63万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-04-01 至 2001-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9700283&HistoricalAwards=false
• 关键词: Proposal; Research; Fault; Resistant; Cryptography

Recently, a new threat model has been discovered which can be used to break many existing cryptographic protocols. The threat is based on the fact that certain hardware may be induced to perform miscalculations. This scenario is applicable to tamper proof devices which can be made to miscalculate by operating them in an extreme physical environment. The possibility of attacking various cryptographic protocols using hardware faults raises many interesting open problems. First, it now becomes desirable to construct efficient schemes which are resistant to attacks using hardware faults. The project will develop the theory necessary to prove the fault resistance of certain schemes. Other cryptographic schemes will be analyzed to determine whether they are susceptible to the new attack. The hardness of factoring integers is a standard cryptographic assumption. Various mathematical implications of this assumption will be studied. The previous results show that the hardness of factoring implies that polynomials having many roots in low algebraic extensions of the rationals are hard to evaluate. Generally speaking, criteria for when polynomials are hard to evaluate are useful in many applications. Further applications of the hardness of factoring will be studied. Specifically, the goal is to construct new classes of polynomials which are hard to evaluate, unless factoring is easy. There are several such candidates, for example, certain polynomials which generate Galois extensions over the rationals. Estimating the difficulty of evaluating certain polynomials based on the type of number fields they generate is a promising area of research. Such results will hopefully shed light on the complexity of evaluating polynomials.***

最近，一种新的威胁模型被发现，它可以用来破解许多现有的密码协议。该威胁基于这样一个事实，即某些硬件可能会被诱导执行错误计算。这种情况适用于通过在极端物理环境中操作而导致误计算的防篡改设备。利用硬件故障攻击各种密码协议的可能性引发了许多有趣的公开问题。首先，现在需要构建能够抵抗使用硬件故障的攻击的高效方案。该项目将发展必要的理论来证明某些方案的故障电阻。将分析其他加密方案，以确定它们是否容易受到新的攻击。整数因式分解的难度是一个标准的密码学假设。我们将研究这一假设的各种数学含义。前人的结果表明，因式分解的难度意味着在有理数的低代数扩张中有多个根的多项式是很难求值的。一般而言，多项式何时难以计算的准则在许多应用中都是有用的。我们将进一步研究因式分解的硬度的应用。具体地说，目标是构造新的多项式类，这些多项式很难计算，除非因式分解很容易。有几个这样的候选者，例如，产生有理数上伽罗瓦扩张的某些多项式。根据某些多项式生成的数域的类型来估计它们的计算难度是一个很有前途的研究领域。这样的结果有望阐明多项式求值的复杂性。