# Provable safety

2021-09-15 04:28:54 PamShao

## Aggression

Encryption algorithm design , Security has been widely concerned , and Provable security theory As its related research field , Is the basic theory of constructing cryptographic schemes , It is also a hot spot in the field of public key cryptography . The core of provable security theory is to specify the security of encryption scheme to the difficulty of an algorithm , The difficulty of the algorithm is used to solve a specific example problem , This method is called the of encryption scheme The security protocol proves that .

In provable security theory , Semantic security Generally, the Indistinguishability game To give . The game model mainly includes opponents and challengers , The Challenger establishes an encryption scheme , The enemy attacked the encryption scheme , At the same time, the Challenger responds to the enemy's attack . In the process of proving safety , Usually, according to the attack ability of the attacker in the game model , Divide the indistinguishability game into Choose the indistinguishability of plaintext attacks （Indistinguishability Chosen Plaintext Attack,IND-CPA） and Choose the indistinguishability of ciphertext attacks （Indistinguishability Chosen Ciphertext Attack,IND-CCA）. Common attack methods can be divided into the following three categories ：

### Choose plaintext attack

Choose plaintext attack (Chosen Plaintext Atack, CPA). In the chosen plaintext attack , The enemy has the required plaintext , An enemy can access a black box , Black box can only perform encryption , Decryption cannot be performed . Except target plaintext , Anyone can generate plaintext ciphertext on , And use the plaintext ciphertext to complete the attack on the encryption scheme . In the process of practical use of password scheme ,CPA A weak attack behavior is simulated .

### Select ciphertext attack

Select ciphertext attack (Chosen Cipertext Accack, CCA1). Selective ciphertext attack is also called lunch attack , An enemy can access a black box , Decrypt the black box , At lunchtime, the enemy can choose a specific ciphertext other than the target ciphertext , Ask and decrypt by accessing the decryption Oracle , Access to the decryption prophecy machine will be completed at lunchtime . Because you can access the decryption Oracle ,CCA1 Make the enemy have more than CPA Stronger attack ability .

Adaptive selection ciphertext attack (Adaptive Chosen Cipertext Accack,CCA2). Adaptive selection ciphertext attack except target ciphertext , The enemy can choose any ciphertext to query the decryption box , At present, public key encryption algorithm is generally required to achieve polynomial security in adaptive ciphertext attack .CCA2 The enemy's attack ability and CCA1 More powerful than .

## Safety objectives

Safety objectives There are two kinds of ：

### Indistinguishability （IND）

Given a challenge ciphertext , The enemy cannot obtain any information corresponding to the plaintext . For bit based plaintext encryption scheme , The enemy gets the challenge ciphertext , The corresponding bit plaintext cannot be obtained correctly , In other words, the probability of success of the enemy's attack is 1/2.

### Non ductility （NM）

A scalable encryption scheme is not secure under adaptive selective ciphertext attack . Therefore, the scheme is required to be non ductile , Non malleability means that given a challenge ciphertext c , The corresponding plaintext is $\mu$, The enemy cannot get another ciphertext c', The plaintext corresponding to the ciphertext is $\mu '$, And two plaintext $\mu$ and $\mu '$ yes Mutually independent .

According to the difference between attack behavior and security target , You can get IND-CPA,IND-CCA1,INDCCA2,NM-CPA,NM-CCA1,NM-CCA2 Multiple security models . We call the encryption scheme secure , If the encryption scheme is provably secure under a certain security model . In general It can be proved that IND-CPA Security and semantic security are equivalent .

Several important definitions related to provable security are introduced below ：

## Calculation is indistinguishable

https://chowdera.com/2021/09/20210909112445621U.html