Research On Asymmetric Encryption Algorithms Against Key-Leakage/Tampering Attacks

As one of the important research topics in modern cryptography,provable security has been used to analyze securities of various kinds of cryptographic algorithms.Traditionally,in the proof we always assume that the random numbers used in algorithms are perfectly generated,and that the adversary can only observe the input and output behaviors of the algorithms and has no means to access or tamper with any their internal states.In our real life,however,the above assumptions always do not hold.Actually,recent research works on side-channel attacks have demonstrated that attackers not only can learn partial secret information through characteristics of cryptographic devices,but also can use new techniques like fault injection to tamper with and induce modifications to the internal states and obtain some information about the states by observing the outcome of the algorithms under the modified states.In addition,in some high-level applications the attacker even can break the system's security by tampering with the public key of the system.With the development of these new attacks,many cryptographic algorithms proven secure in the traditional model may become broken in current application scenarios.Hence,taking into account these realistic attacks when establishing security notions and designing provable secure cryptographic algorithms even against such attacks are very meaningful both from a theoretical as well as a practical perspective.Considering that pubic key encryption?PKE?and identity-based encryption?IBE?are widely deployed in practice,in this dissertation we mainly investigate how to design these two kinds of most basic asymmetric encryption algorithms in the attack scenarios above.In particular,the main contributions made in this dissertation are summarized as follows:1.In the leakage-resilience setting,we first present a practical leakage-resilient and chosen-ciphertext secure IBE scheme based on Gentry's scheme.In contrast to Alwen et al.' scheme,this new scheme successfully avoids the drawback that the amount ? of key-leakage and the message length m depends on each other,i.e.,? + m ? log p-??log ??.Moreover,it can not only encrypt a longer message but also tolerate a larger amount of key-leakage.Thus,it enjoys both a better performance and a higher security.Then,based on Alwen et al.'s scheme we propose another leakage-resilient IBE scheme.Although this scheme has the same leakage parameter as Alwen et al.',but it has a better efficiency and a higher leakage ratio.As far as we know,it is the first practical leakage-resilient and chosen-ciphertext secure IBE scheme with leakage ratio up to 1/4.2.Recently,Fujisaki and Xagawa introduced a new and broad related-key derivation function class called ?_aInv,which consists of almost all efficiently invertible functions.First,we present a generic construction of public key encryption against such a broad function class ?_aInvbased on a chosen-chiphertext secure PKE and at SE-NIZK proof system.Then,by exploiting KEM/DEM-like approach we give two practical concrete constructions against the same function class,where DEM is only required to be one-time chosen-plaintext secure.Compared with related works,they can not only resist to a larger class of related-key attacks but also encrypt messages with arbitrary length.3.Complete non-malleability is a much stronger security notion than regular non-malleability, which is inspired by the scenarios where attackers have the ability to tamper with the public key or generate a new one on-the-fly.To withstand such attacks,we put forward a simple and efficient PKE scheme in the common reference string?CRS?model,which can be proven secure based on the standard assumptions.In contrast to related works,the well-formed public keys and ciphertexts in our construction could be publicly recognized without drawing support from non-interactive zero knowledge proofs or one-time signatures,thus it achieves a better performance.Simultaneously,the scheme is shown to be completely non-malleable secure against adaptive chosen ciphertext attacks in the standard model.Thus,it would be more suitable for higher-level applications where both efficiency and security are extensively concerned.4.Completely non-malleable security captures tampering attacks on the public keys of high-level systems,while related-key attack security captures similar tampering attacks on the internal secret state of cryptographic implementations.Motivated by the fact that both kinds of attacks may occur in complex applications of our real life,we further propose an efficient PKE scheme on the basis of complete non-malleability,and show that it can achieve both kinds of securities in the standard model.With regards to the related-key attack security,it is realized by relying on properties of complete non-malleability to some extent.Moreover,to achieve security against polynomial functions of bounded degree d,we introduce a new hardness assumption termed d-m EDBDH assumption.In comparison with related works,it is not only quite practical but also proven secure against both kinds of tampering attacks.Hence,it can provide a stronger security guarantee for real applications.5.As two types of basic side-channel attacks,key-leakage attacks and tampering attacks may happen simultaneously in cryptographic implementations.Inspired by this problem,we for-malize a notion of chosen ciphertext security against key-leakage and tampering attacks,then we introduce the concept of key-homomorphic hash proof systems and present a generic construction of PKE based on this new primitive and t SE-NIZK proof system.Our construction,compared with previous works,realizes leakage-resilience and tampering-resilience simultaneously but completely independently,so it can be instantiated with more flexibility.Moreover,it can tolerate a larger amount of bounded-memory leakage and allows for an unbounded number of affine-tampering queries,even after the challenge phase.With slight adaptations,our construction also achieves chosen-ciphertext security against auxiliary-input leakage attacks and a polynomial of affine-tampering attacks.Thus,we get the first PKE scheme that is secure against both auxiliary-input leakage and tampering attacks.