公钥密码方案构造及安全证明的知识要点和方法论

Public-key cryptography (PKC) is an important branch of cryptography. The diversity of PKC scheme constructions and security proofs make the research in PKC a challenging task. This paper first summarizes the fundamental knowledge, which is required for provable security in the PKC settings, including basic concepts, mathematical foundation, easy and hard problems, algorithms, security models, and security reduction. Such knowledge is essential for the study of PKC scheme constructions and security proofs. This paper then presents the studies of methods for constructing a provably secure PKC schemes, including how to construct such a scheme, how to present security proofs, and how to construct such a scheme with provable security. 30 such schemes and their proofs for practices are illustrated. It also gives a summary of the way of thinking when studying PKC, which is helpful to further understand the techniques. This paper is expected to be helpful for the reader to understand how to construct provably secure public-key cryptographic schemes, especially for those with a weak cryptographic background.