CT-ISG: On Imperfect Randomness and Exposure-Resilient Cryptography

随机化已被证明是构建基本上任何类型的安全密码系统的重要组成部分：密钥应该是随机生成的，大多数密码原语（如加密）必须是概率性的。作为一种常见的抽象，通常假设理想的随机性对系统的所有参与者都是可用的。在许多情况下，这种假设是非常不现实的，密码系统必须建立在不完美的随机性来源的基础上。该项目的智力价值：该研究将解决这样一个问题，即密码协议在多大程度上可以适应不完美的随机性来源。特别是，它将集中在密码学的可行性，不完美的随机性来源和安全弹性密码学。对于第一个主题，PI将解决这样一个问题：对于构建各种加密原语（如加密和身份验证），是否需要近乎理想的随机性，或者，也许，可以将这些应用程序建立在更现实的不完美源上。对于第二个主题，在许多情况下，对手可以获得某些秘密信息的部分知识（例如，密码密钥）。这种知识的确切性质往往是未知的，除了它是“有界的”。 因此，即使秘密最初是随机的，它看起来像一个不完美的随机源的对手，鉴于他的部分知识的秘密。PI将设计新的协议，这是弹性的部分信息泄漏在最近提出的Bounded Retrieval Model.Broader项目的影响：理想的随机性的可用性是一个常见的假设，不仅在密码学，但在许多其他领域的计算机科学，和工程一般。质疑这一假设的有效性，并设计技术，使给定的系统基于更弱、更现实的假设，这在许多其他学科中肯定是有用的。此外，鉴于病毒、因特网蠕虫和特洛伊木马的日益蔓延，使用具有安全弹性的协议将使应用程序环境更加稳定和安全。此外，由于该项目的研究将使用信息论和伪随机性的工具来解决密码学问题，这将有助于找到这些领域之间的新联系。PI还定期教授密码学和网络安全课程，并将能够将新成果融入这些课程。 此外，该项目还有一个重要的研究生培训部分。

Randomization has proved to be a vital part in building essentially any kind of secure cryptographic system: secret keys should be randomly generated and most cryptographic primitives, such as encryption, must be probabilistic. As a common abstraction, it is typically assumed that ideal randomness is available to all the participants of the system. In many situations, this assumption is highly unrealistic, and cryptographic systems have to be built based on *imperfect* sources of randomness.Intellectual Merits of the Project: The research will address the question as to what extent cryptographic protocols can be adapted to work with imperfect sources of randomness. In particular, it will concentrate on the feasibility of cryptography imperfect sources of randomness and exposure-resilient cryptography. For the first topic, the PI will address the question if nearly ideal randomness is *necessary* for building various cryptographic primitives, such as encryption and authentication, or, perhaps, one can base such applications on more realistic imperfect sources. For the second topic, in many settings the adversary can gain partial knowledge of some secret information (e.g., a cryptographic key). The exact nature of this knowledge is often unknown, except that it is ``bounded''. Therefore, even if the secret was originally random, it looks like an imperfect random source to the adversary, given his partial knowledge about the secret. The PI will design novel protocols which are resilient to such leakage of partial information in the recently proposed Bounded Retrieval Model.Broader Impacts of the Project: The availability of ideal randomness is a common assumption used not only in cryptography, but in many other areas of computer science, and engineering in general. Questioning the validity of this assumption and designing techniques to base a given system on weaker, more *realistic* assumptions will surely be useful in many other disciplines. Additionally, given the increasing spread of viruses, Internet worms and Trojan horses, the use of exposure-resilient protocols will result in more stable and secure application environments. Furthermore, because the research in this project will use tools from information theory and pseudorandomness to solve cryptographic questions, it will help find new connections among these fields.The PI also regularly teaches courses on cryptography and network security, and will be able to incorporate the new results into such courses. In addition, the project has a significant graduate student training component.