Public-key Encryption:KDM Security And Rka Security

Public-key encryption(PKE)enables ones to transmit messages privately and communicate confidentially over public channels,without sharing any secret information in advance.Nowa-days,PKE is ubiquitous in the age of Internet and plays a key role in providing data secrecy.On the other hand,with the advent of complicate application scenarios and novel cryptanalysis techniques,attackers may launch new types of attacks on PKE schemes,for example:Key-Dependent Message Attack(KDM),In the scenario of hard disk encryptions,due to the careless design of software or the habits of users,the encryption software may encrypt the key together with the disk content.A typical example is the BitLocker disk encryption utility used in Windows Vista.Consequently,the attacker is able to obtain the encryptions of key-dependent messages.Related-Key Attack(RKA).Through tampering and fault injection techniques,the at-tacker can interfere with hardware devices(such as heating or cutting wires),and force the scheme to operate under a different but related/modified key.As a result,the attacker is able to observe the input-output behavior of the cryptographic scheme under related/-modified keys.In the presence of these attacks,many PKE schemes designed in the traditional security model become completely insecure and inapplicable,or it is hard for us to prove their security.To resist these new types of attacks,we have to re-design PKE schemes for these specific scenarios and prove their security mathematically and rigorously.In this dissertation,we mainly investigate the design of KDM-secure PKE and RKA-secure PKE schemes,which are immune to KDM attacks and RKA attacks respectively.Our results are summarized as follows:1.Effncient KDM-CCA Secure PKE Scheme for Polynomial Functions.KDM[F]-CCA secure PKE scheme protects the security of messages f(sk),with f ? F,that are com-puted directly from the secret key sk,even if the adversary has access to a decryption oracle.The larger F is,the stronger the KDM-CCA security is.To the best of our knowl-edge,for all the existing efricient KDM[F]-CCA secure PKE schemes,the function sets F do not go beyond the set of affine functions Faff.We design the first efficient KDM[Fpolyd]-CCA secure PKE for polynomial functions of bounded degree d.Our scheme has almost compact ciphertexts.The number of group elements in a ciphertext is polynomial in d,independent of the security parameter.2.KDM-CPA Secure PKE Scheme from Constant-Noise LPN.The learning parity with noise(LPN)problem enjoys conjectured post-quantum hardness and simple algebraic structure.Recently,Dottling(PKC 2015)proposed the first KDM-CPA secure PKE scheme from low-noise LPN.Compared with low-noise LPN,the constant-noise LPN problem is mostly believed to be more intractable,thus providing more security con-fidence.However,the problem of constructing KDM-secure PKE from constant-noise LPN has remained open.We design the first KDM[Faff]-CPA secure PKE scheme for affine functions assum-ing certain sub-exponential hardness of constant-noise LPN.This makes our scheme a promising candidate for post-quantum cryptography.Besides,our scheme is neat and ef-ficient.The computations in our scheme are simply bitwise operations between binary strings.3.Super-Strong RKA-CCA Security Model for PKE,and Super-Strong RKA-CCA Se-cure PKE Scheme.The RKA-security for PKE protects the privacy of messages even if the scheme is operating under related/modified keys.The security model of RKA in-cludes RKA-CCA and strong RKA-CCA.However,in these two models,there are some unrealistic and artificial restrictions imposed on the adversary s decryption oracle access.We formalize a new RKA security model for PKE,namely super-strong RKA-CCA.Our security model removes the artificial restrictions on the adversary's decryption oracle access,thus turns out to be the strongest among existing RKA security notions for PKE.We present a generic paradigm for constructing super-strong RKA-CCA secure PKE,and give two instantiations based on the matrix DDH assumption and the DCR assumption respectively.Our PKE schemes are the first ones possessing super-strong RKA[Fraff]-CCA security for restricted affine functions.Moreover,our schemes are free of pairing and fully compact.In particular,the public keys,secret keys and ciphertexts of our schemes all consist of only a constant number of group elements.4.RKA-CCA Secure PKE Scheme with Tight Security Reduction.For a tightly secure PKE scheme,the security loss of the security reduction depends only on the security parameter,and is independent of the number of encryption queries Qe and the number of decryption queries Qd Thus,a tight security reduction allows us to choose a small security parameter,and makes the PKE scheme flexible and suitable for settings of large scales.The-state-of-the-art of PKE in the multi-challenge setting is that,all the existing RKA-CCA secure PKE schemes suffer a security loss of at least Qe.We design the first tightly RKA[Fraff]-CCA secure PKE scheme for restricted affine functions.The RKA-CCA security of our scheme is tightly reduced to the standard s-Linear assumption.Besides,we also prove the tight RKA-CCA security of our PKE scheme in the super-strong RKA-CCA security model.