Practical Yet Provably Secure Public-Key Primitives

NSF建议0310297实用但可证明安全的公钥原语Victor Shoup这项研究解决了公钥密码学的基本构建块或原语，并试图设计和分析通过提高效率或增强安全性来改进技术状态的新原语。目标是设计新的原稿，适合在学术期刊上发表，并提交给相关的标准机构。所使用的方法包括(1)现代密码学的“简化论”方法，其中方案的安全性被形式地归结为假定的难以解决的研究得很好的数学问题(例如，因式分解)，以及(2)来自数论和代数的算法技术。公钥密码术在保护计算机和通信网络安全方面发挥着至关重要的作用。两个基本的公钥原语是公钥加密和数字签名。第一个原语允许发送者将消息正确地传输到接收者，其中发送者只需要知道公钥(每个人都知道)，而只有接收者需要知道对应的秘密密钥。第二个原语允许签名者使用私钥在消息上生成数字签名，以便签名之后可以由任何一方使用相应的公钥进行验证。尽管近年来在这些问题上已经取得了实质性的进展，但在提高方案的效率、降低难解性假设的强度、提高安全性降低的质量以及开发这些方案的实际分布式版本以避免单点故障方面，仍有更多的工作要做。这些都是本研究承担的具体任务。

NSF Proposal 0310297Practical yet Provably Secure Public-Key PrimitivesVictor ShoupThis research addresses the fundamental building blocks, or primitives, ofpublic-key cryptography, and attempts to design and analyze new primitivesthat improve the state of the art, either through increased efficiency orincreased security. The objectives are to design new primitives suitable forpublication in academic journals, as well as for submission to relevantstandards bodies. The methods used include (1) the "reductionist" approach ofmodern cryptography, whereby the security of a scheme is formally reduced tothe presumed intractability of well-studied mathematical problems (e.g.,factoring), and (2) algorithmic techniques from number theory and algebra. Public-key cryptography plays an essential role in securing computers andcommunication networks. The two basic public-key primitives are public-keyencryption and digital signatures. The first primitive allows a sender tosecretly transmit a message to a receiver, where the sender only needs to knowa public key (known to everyone), while only the receiver needs to know the corresponding secret key. The second primitive allows a signer, using a secretkey, to generate a digital signature on a message so that the signature canlater be verified by any party using a corresponding public key.Although substantial progress has been made in recent years on these problems, there is still more work to do, in terms of improving the efficiency of theschemes, reducing the strength of the intractability assumptions, improvingthe quality of the security reductions, and in developing practical distributedversions of these schemes so as to avoid a single point of failure. These arethe specific tasks taken on by this research.