Research On Public Key Cryptographic Algorithm Against Subversion Attack

In recent years,with the continuous outbreak of a series of mass-surveillance events,such as the “Prism” incident,people have gradually realized a new method of attacking cryptographic algorithms called Subversion Attack(SA).SA is a common method used to implement mass-surveillance to steal private information.Specifically,SA means that the attacker could embed some secret information or trapdoor information that is only known to himself in the process of designing or implementing a cryptographic algorithm.That is,the attacker could set up some backdoors to facilitate subsequent decryption of all collected encrypted information,so as to obtain users' private information,and ultimately achieve the purpose of collecting intelligence.SA's attack targets include not only the cryptographic algorithm itself,but also the cryptographic components used in the algorithm.The emergence of SA has brought new threats and challenges to the research in the field of cryptography.Therefore,how to make cryptographic algorithms resistant to SA is also a problem that has attracted much attention in the field of cryptography in recent years.By summarizing the existing research results,we find that there are three main types of the public key cryptography algorithms protecting against subversion attack.Namely,public key cryptography algorithms that resist backdoored PRNG,public key cryptography algorithms that resist system parameter subversion attack and public key cryptography algorithms that resist algorithm substitution attack.Here,the backdoored PRNG refers to the attacker's secretly embedded trapdoor information in the Pseudorandom Number Generator(PRNG)used by the cryptographic algorithm,like the typical Dual EC PRNG;the parameter subversion attack(PSA)means that the public system parameters(such as security parameters,primes,elliptic curves,etc.)in the cryptographic algorithm are subverted by the attacker,that is,the attacker has maliciously manipulated these public parameters involved in the cryptographic algorithm;the algorithm substitution attack(ASA)refers to an attack implemented by an attacker in the actual deployment of cryptographic algorithms.Based on these three research directions of public key cryptography algorithms resistant to subversion attack,in this thesis,we mainly complete the following three aspects of contribution:(1)Nonce-based key agreement protocol against randomness failure.In this part of our work,we first take a key agreement protocol that has been proven to meet forward security as an example to analyze the security threat caused by the randomness failure on the protocol.Secondly,combined with the nonce-based public key encryption system,we improved the protocol and proposed a noncebased key agreement protocol(NKA)against randomness failure.More importantly,we give a formal definition of the security of the NKA protocol,including the Nonce-based Privacy One(NBP1)and Nonce-based Privacy Two(NBP2).Moreover,it is proved that the NKA protocol satisfies the security of NBP1 and NBP2 under the random oracle model.(2)Selective-opening security for public-key encryption in the presence of parameter subversion attack.In this part of our work,we mainly studied the public key encryption algorithm that can resist parameter subversion attacks and selective open attacks at the same time.In order to define the security that can simultaneously characterize these two attacks,we propose a new security property called indistinguishability under selective opening attacks and parameter subversion attacks(IND-SO-PSA).To achieve this goal,we first constructed a specific All-ButMany lossy trapdoor function using a new mathematical tool that can resist system parameter subversion attacks(i.e.,efficient embeddable groups),and proved that this function satisfies security under system parameter subversion attack.Because the All-But-Many lossy trapdoor function is a cryptographic primitive that can resist selective opening attacks,we use this new All-But-Many lossy trapdoor function and efficient embeddable group to construct a public Key encryption scheme,and prove that the scheme satisfies the IND-SO-PSA security.(3)Cryptographic reverse firewalls for digital signatures and non-interactive zero knowledge proof system.Cryptographic Reverse Firewall(CRF)is an efficient method to resist the algorithm substitution attack.We first constructed a cryptographic reverse firewall(CRF)on the signer's side for a re-randomizable signature algorithm(PS algorithm)to resist the algorithm substitution attack on the digital signature algorithm that exists on the signer's side.On the other hand,in order to resist the algorithm substitution attack on the prover side in the noninteractive zero-knowledge proof system,we constructed a password reverse firewall on the prover side for the re-randomizable non-interactive zero-knowledge proof system.Moreover,we consider the instantiation of CRF for non-interactive zero-knowledge proof system.