(1) Unconditional security
This evaluation method considers the assumption that the attacker has unlimited computing resources, but still This cryptosystem cannot be deciphered.
(2) Computational security
This method means that the calculation required to break it using the best current method far exceeds the attacker's computing resource level, then it can be defined This cryptographic system is secure.
(3) Provable security
This method attributes the security of the cryptosystem to a well-researched mathematical problem (such as large integer prime factorization, calculation discrete logarithms, etc.), mathematical puzzles that proved difficult to solve. The problem with this evaluation method is that it only shows that the security of this cryptographic method is related to a certain difficult problem, but does not fully prove the security of the problem itself and give proof of their equivalence.
2. Actual security
For cryptographic systems in practical applications, since there is at least one deciphering method, namely the brute force attack method, it cannot satisfy unconditional security. Provides computational security only. For a cryptographic system to achieve practical security, it must meet the following criteria:
(1) The actual amount of calculation (including calculation time or cost) to decipher the cryptosystem is so huge that it is practically impossible to achieve of.
(2) The computing time required to decipher the cryptosystem exceeds the useful life cycle of the encrypted information. For example, combat orders to launch combat attacks in war only need to be kept secret until the battle begins; important news information needs to be kept secret for only a few hours before being publicly reported.
(3) The cost of deciphering the cryptosystem exceeds the value of the encrypted information itself.
If a cryptographic system can meet one of the above criteria, it can be considered to meet practical security.
3. Provable security 3.1 Three major elements of a provable security system
In a provable security system, there are three major elements: security model, security definition and difficulty question.
The security model is divided into security objectives and adversary capabilities. The security goal describes the degree of security that the security model should achieve, for example, indistinguishability (IND) for encryption algorithms, existence and unforgeability (Existable Unforgeble (EU) for signature algorithms), etc.
Indistinguishability (IND) is also called semantic security (Semantic scurity), which is defined as follows. Even if the adversary obtains the ciphertext, he cannot obtain any information corresponding to the plaintext, even 1 bit of information. Its formal expression is: given m0, m1 and Cb=Enc(pk, mb), where m0 is either m0 or m1, that is, Cb is the ciphertext of one of m0 and m1, and the adversary cannot effectively Determine whether b is 0 or 1 during the encryption process.
3.2? Security Definition
There are four main categories to describe the adversary’s capabilities, Chosen Plaintext Attack (CPA for short), Chosen Ciphertext Attack (CCA for short) ), Ciphertext-Only Attack, and Known Plaintext Attack. Commonly used to describe the adversary's capabilities are the first two categories. Selected plaintext attack (CPA) means that the adversary selects plaintext and can obtain the corresponding ciphertext. Chosen ciphertext attack (CCA) means that the adversary can not only select the plaintext to obtain the ciphertext, but also select a limited number of ciphertexts to obtain the corresponding plaintext. CCA has a stronger ability to describe the adversary than CPA.
The following introduces commonly used security definitions.
CPA Security. We describe the chosen plaintext attack (CPA) as a game to facilitate our better understanding. First of all, it should be stated that the purpose of this game is to break the indistinguishability of the system under the premise of selected plaintext attack, so this game is referred to as IND-CPA below.
Secondly, two roles, challenger C and adversary A, must be defined. The challenger's role is to act as a referee, presiding over the game and providing feedback on the opponent's actions. As the name suggests, the adversary is to attack the current system, and for this game, it uses a selected plaintext attack method to attack. The game is described as follows:?
A. Initialization: Challenger C creates the IND-CPA system and sends the public key to adversary A. ?
B. Adversary A selects two plaintexts of the same length, m0 and m1, and sends them to challenger C. The challenger C randomly selects b∈{0,1}, encrypts mb as cb, and then sends the ciphertext cb to the adversary A.
C. Adversary A? Guess whether the plaintext encrypted by challenger C in the previous step is m0 or m1, and output the guess result, and the output result is recorded as b‘. If b‘=b, then the opponent’s attack is successful.
The advantage of an adversary attack can be defined as the following function: ? where w is the length of the encryption scheme key. Because a random guess has a 1/2 probability of winning the IND-CPA game. Therefore
It is the advantage that the opponent obtains through hard work. If there is a negligible advantage σ over any polynomial-time adversary A such that
Then the encryption algorithm is said to be indistinguishable under a chosen-plaintext attack, or IND-CPA secure. 3.3? Hard problems
With the security model and security definition, the method of reducing the hard problem to the hard problem is usually used to prove the security. Commonly used difficult problems in cryptography include discrete logarithm problem (DLP), CDH problem (Computational Diffie-Hellman), DDH problem (Decisional Diffie-Hellman) and BDH problem (Bilinear Diffie-Hellman). ?
3.4? Provable security theory
With the security model, security definition, and difficult problems described above, it can be proven that with the security model described above, security Definition, difficult problems, provable security systems become feasible. Provable security refers to the use of "reduction" methods to reduce the method of attacking cryptographic algorithms or security protocols to a difficult attack problem. First, determine the security goal of the encryption system. For example, the security goal of the signature system is the unforgeability of the signature (Existable Unforgeble), and the security goal of the encryption system is the indistinguishability of the information. A security model is then constructed based on the security definition to determine the adversary's capabilities.
Reduction is a concept in complexity theory. Reduction of a problem P1 to problem P2 means that, given the algorithm M1 that solves problem P1, we can construct another algorithm M2, and M2 can use M1 as a subroutine. , used to solve problem P2.
Apply the reduction method to the security proof of cryptographic algorithms or security protocols. For example, you can reduce the adversary’s attacks on cryptographic algorithms or security protocols (P1) to some difficult problems that have been studied in depth. (P2). That is, if the adversary can launch an effective attack on the algorithm or protocol, the adversary can be used to construct an algorithm to break the difficult problem. However, the difficult problem has been proven to be unbreakable, so a contradiction arises. According to the method of proof by contradiction, the adversary can break the algorithm or the protocol, assuming that it is not true, and the proof is completed.
Generally speaking, in order to prove the security of scheme 1, we can reduce scheme 1 to scheme 2, that is, if adversary A can attack scheme 1, then adversary B can also attack scheme 2, and scheme 2 2 has been proven safe or is a problem.
The proof process is described through a thinking game. First, the challenger creates plan 2, B represents the adversary in plan 2, and A represents the adversary in plan 1. In order to break scheme 2, B uses A as a subroutine to attack scheme 1. If B wants to take advantage of A, it needs to train A, so B simulates A's challenger.