Study On Provable Security Of Public-Key And Hybrid Encryptions

Provable Security is a formal method for proving the security of cryptographic schemes, in which the difficulty of breaking a particular scheme is formally related to that of solving a widely believed computational hard problem. Provable security has already become an important theme of theoretical researches in modern cryptography. This dissertation investigates the provable security of public-key encryptions and hybrid encryptions of asymmetric and symmetric encryptions. This includes the various formal security notions and the constructions can be proved to achieve them. Among the constructions, hybrid encryptions are themselves an important way to obtain public-key encryption schemes with chosen ciphertext security. The main results are as follows:(1) The one-wayness of the trapdoor one-way function in NTRU depends on the randomness of the session key, which is different from previous ones. Based on this observation, a new kind of trapdoor one-way function, trapdoor one-way functions with an auxiliary random variable is proposed. By the new functions, the trapdoor one-way function model of public-key encryptions can be extended. The function is extended to the situation of higher dimensions with a discussion of the possible cryptographic applications.(2) By proving the simulator-based and comparison-based definitions of semantic security both equivalent to the indistinguishability we obtain the equivalence of the two definitions. This conflicts with the conclusion of Watanabe, et al. The reason lies in that in the simulation-based definition they used, the adversary and its simulator are allowed to choose by themselves the auxiliary partial information about the plaintext to be input, which results in that the information chosen by them can be different. This makes the definition even not equivalent to the indistinguishability, which contradicts with what has been widely acknowledged.(3) One-time and multi-message hybrid encryptions is separated, especially the security definitions for them. For the most direct paradigm of hybrid encryption PKE+SKE, the IND-CCA_I security when it is a one-time one and the IND-CCA5 security when it is a multi-message one are proved respectively. For both of them, the necessity of the security requirement for PKE and SKE is discussed.(4) For the KEM+SKE multi-message hybrid paradigm, i.e. the KEM scheme in the KEM+DEM paradigm is used to encapsulate the symmetric key for a multi-message hybrid encryption, IND-CCAs security is proved. An instantiation is presented to show the requirement of IND-CCA2 security for KEM is not essential.(5) Several constructions for the Tag-KEM schemes is presented, among which the construction based on public-key encryptions with short plaintext is the first IND-CCA secure Tag-KEM scheme without any validity checking mechanism for the tag part. This decreases the redundancy of the ciphertext.(6) For the unsuitabihty of the Tag-KEM/DEM to be used as multi-message hybrid encryptions, a new hybrid paradigm, KEM/Tag-DEM, is proposed with its security proof. For the corresponding multi-message hybrid paradigm, KEM/Tag-SKE, security is also proved. Two constructions for IND-CCA secure Tag-DEMs are proposed with the security proof.