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

随机化已被证明是构建基本上任何类型的安全密码系统的关键部分：密钥应该随机生成，并且大多数密码原语(如加密)必须是概率的。作为一种常见的抽象，通常假设理想随机性对系统的所有参与者都是可用的。在许多情况下，这种假设是非常不现实的，密码系统必须建立在不完美的随机源的基础上。该项目的智力优势：该研究将解决密码协议可以在多大程度上适应不完美的随机源的问题。特别是，它将集中在密码学的可行性，不完美的随机性来源和抗曝光密码学。对于第一个主题，PI将解决这样一个问题：对于构建各种密码原语，例如加密和认证，是否需要近乎理想的随机性，或者，也许，人们可以将这种应用建立在更现实的不完美的来源上。对于第二个主题，在许多设置中，对手可以获得某些秘密信息(例如，密码密钥)的部分知识。这种知识的确切性质通常是未知的，除了它是“有界的”。因此，即使秘密最初是随机的，但对于对手来说，考虑到他对该秘密的部分了解，它看起来像是一个不完美的随机来源。PI将设计新的协议，这些协议对最近提出的有界检索模型中的部分信息泄漏具有弹性。该项目的广泛影响：理想随机性的可用性是一个常见的假设，不仅用于密码学，而且用于计算机科学的许多其他领域，以及一般的工程。质疑这一假设的有效性，并设计基于更弱、更现实*假设的给定系统的技术，肯定会在许多其他学科中有用。此外，鉴于病毒、互联网蠕虫和特洛伊木马的传播日益频繁，使用抗暴露协议将带来更稳定、更安全的应用环境。此外，由于这个项目的研究将使用信息论和伪随机性的工具来解决密码学问题，这将有助于找到这些领域之间的新联系。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.