authored by Premmi and Beguène
Prerequisite : Logic Primer
We prove that a cryptographic construct is secure under certain assumptions using mathematical proofs called security proofs. Following is a list of various techniques used in constructing such proofs.
Proving Conditional Statements
Oftentimes, security proofs in cryptography involve proving the truth of some conditional statement. We will briefly discuss what a conditional statement is and the various ways to prove its correctness.
Conditional Statement
A truth value is either true or false, abbreviated T and F, respectively.
A statement is a sentence that is either true or false, but not both. It is also called a proposition.
A statement variable represents a statement and is often denoted by p, q \text{ or } r. It is also called a propositional variable.
A conditional statement is a statement of the form “If p, then q", where p \text{ and } q are sentences; p is called the premise and q, the conclusion. This statement can also be written as p \!\implies\! q.
If p \text{ and } q are statements, then the truth value (true or false) of the conditional statement p \!\implies\! q depends on the truth values of p \text{ and } q.
The conditional statement “If p, then q" means that q is true whenever p is true; it says nothing about the truth value of q when p is false. When p is false, the truth value of q cannot be determined; hence, the conditional statement is considered to be vacuously true or true by default. This is because when p is false, the conditional statement “If p, then q" is never contradicted irrespective of the truth value of q. Therefore, the conditional statement “If p, then q" is false only when p it true and q is false i.e., the premise is true and the conclusion is false; in all other cases, “If p, then q" is true.
The truth of a statement can be expressed by a Truth Table. A truth table for a given statement displays the resulting truth values for various combinations of truth values of its constituent statement variables.
The following diagram is the truth table for p \!\implies\! q.
Methods for proving conditional statements
An argument is a sequence of statements aimed at demonstrating the truth of a statement.
A mathematical proof is an argument that a certain statement is necessarily true.
We can prove the truth of a conditional statement either directly or through its logical equivalents as explained below.
Modus Ponens (Direct Proof)
A direct proof of a conditional statement is a demonstration that the conclusion of the conditional statement follows logically from the premise of the conditional statement.
In order to prove the conditional statement, “If p, then q", we only need to prove that q is true whenever p is true. This is because the conditional statement is always true when the premise i.e., p is false.
So in a direct proof of p \!\implies\! q, we assume that p is true and using this assumption, show through a logical sequence of steps that the conclusion q is also true.
Proving conditional statements through their logical equivalents
Sometimes it might be difficult to construct (or even comprehend) a direct proof of a conditional statement. In such a case we construct a statement that is a logical equivalent of the conditional statement and by proving that this statement is true, we prove that its logical equivalent namely, the conditional statement is true as well.
Modus Tollens (Proof by Contrapositive)
Let us reconsider the conditional statement p \!\implies\! q. This statement means that q is true whenever p is true. Suppose we observe that q is false, then it must be the case that p is also false, since had p been true then q would have also been true. Hence, we can see that p \!\implies\! q is logically equivalent to \neg q \!\implies\! \neg p.
The expression \neg q \!\implies\! \neg p is called the contrapositive form of p \!\implies\! q. The truth table shown below verifies this fact.
Now that we have established the fact that p \!\implies\! q is logically equivalent to \neg q \!\implies\! \neg p, in order to prove the conditional statement p \!\implies\! q it will suffice to prove its logical equivalent, namely, \neg q \!\implies\! \neg p. This method of proving conditional statements is called proof by contrapositive.
Proof by Contradiction
This method of proof is based on the fact that a statement can be either true or false but not both. Hence, we prove that the statement is true by showing that it cannot be false. We do this by assuming that the statement is false and proving that this leads to a contradiction.
In order to prove the conditional statement, p \!\implies\! q using proof by contradiction, we assume that p \!\implies\! q is false and show that this leads to a contradiction.
p \!\implies\! q is false only when p is true and q is false, as shown by the truth table below.
Since p \!\implies\! q is false only when p is true and q is false i.e., when p \wedge \neg q is true, this implies that the negation of p \!\implies\! q is true only when p \wedge \neg q is true and is false when p \wedge \neg q is false. Therefore, \neg\big(p \!\implies\! q\big) is logically equivalent to p \wedge \neg q. This is verified by the truth table below.
This logical equivalency, namely, \neg\big(p \!\implies\! q\big) \equiv p \wedge \neg q, shows that if we assume p \!\implies\! q to be false, then we are assuming p is true and q is false. If we can prove that this assumption leads to a contradiction, then we have shown that p \!\implies\! q cannot be false and hence must be true.
Which proof technique to use in security proofs?
If a security proof involves proving a conditional statement, we can use either one of the three methods discussed – direct proof, proof by contrapositive or proof by contradiction. Which particular method to use depends on personal preference. Our preference leans towards proof by contrapositive, as we feel it is the most intuitive proof and hence easiest to understand.
This is an example of a security proof that involves proving a conditional statement.
Proof by Counterexample
Oftentimes in cryptography we would like to know whether if a cipher is secure against a particular notion of security is it also secure against another notion of security i.e., we would like to know whether being secure against one notion of security implies being secure under another notion of security as well. For example, if a cipher is secure against message recovery is it also semantically secure?
We would like to know whether a conditional statement “If p, then q" is true? One way to test whether it is true is to try and disprove the statement by coming up with an example where the statement fails under the necessary assumptions of the statement. If we are able to show such an example then we have disproved the statement as we have shown that it does not hold for all cases. This method of proving that a conditional statement is false is called proof by counterexample.
Here is an example of a proof by counterexample.
In case no such counterexample can be found, then we can assume that the conditional statement is true and prove it using one of the methods as described in the previous section.
To be continued…