# Introduction to provable security and its application in searchable encryption

PROVABLE SECURITY, as the name suggests, it is a type of security that can be proved. Generally, it employs mathematical proofs, and most of the security proofs are done using a reduction approach. The reduction approach used in encryption schemes is very similar to NP-completeness reductions, but more complicated. We will explain the reduction approach comprehensively manner and then present an example where we prove the security of an encryption scheme against a straightforward eavesdropper attack. With the help of examples and insights about the reductionist approach and how we can reason the security of a scheme, we can easily apply the explained approach to any system, including searchable encryption; after all, a searchable encryption scheme is also a type of encryption.

## Security Definition

An encryption scheme is said to be complete or fully defined when, in addition to the algorithms like key generation (Gen), encryption (Enc) and decryption (Dec), we define all the spaces like the keyword space, message space and ciphertext space that will be implicitly used in these algorithms. Let the following represent a symmetric encryption scheme, for which we will define correctness and security definitions:

The key generation algorithm takes security parameter in unary format because we want to run this algorithm in polynomial time with respect to n. The key generation algorithm implicitly uses the key space, which is a set of all the keys that can be generated by this algorithm. Similarly, the encryption and the decryption algorithms also use the ciphertext space and message space implicitly.

The correctness of an encryption scheme is defined in terms of the following probability:

It states that we conduct an experiment where we have generated a secret key and, using this secret key, we have properly encrypted a message to get its ciphertext, and then this ciphertext is given to the decryption algorithm which also takes the same key. If the probability of getting m = m' is 1, then we say our scheme is always correct. Now, we know where key and ciphertext came from, but we have not said anything about the message, where does this m came from? This m is chosen from the message space and the above defined probability must hold for all messages in the message space. Hence, we say Vm 6 M, if Pr[k Gen( 1"); c <— Enc(k,m); m' Dec(k, c): m = m' = 1,

then our scheme is always correct. Now we will define what it means for an encryption scheme to be secure.

### Probabilistic And Game-based Security Definition

To clearly understand the entire security mechanism, we will start by the security ciphertext-only attack which is also called the security against potential eavesdroppers. All further discussion in this chapter will consider the eavesdropper security.

First of all, we will define the probabilistic security definition and then convert it into the game-based definition.

Consider an experiment where we generate a secret key, k, using the Gen algorithm which takes security parameter, Г. Now, we will pass on the security parameter to the adversary and keep the key to ourselves as it is a secret. The adversary now outputs two messages, m0, mx and we will allow the adversary to keep a state, which she needs later. Given these messages, we will pick a random bit, b <— {0,1), and encrypt one of the messages, mh, to generate ciphertext, c, and give it back to the adversary. The adversary can now continue from the state she left and she now knows the ciphertext which we have given her. Using this information, the adversary outputs her guess, b', and wins if b' = b. Since b is just a single bit which can always be guessed correctly with probability 1/2, the adversary must do more than just 1/2, if she actually wants to break the scheme. But we do not want her to do much more than a neg(n) (negligible in security parameter n) because we want our scheme to be secure. Formally, this entire experiment can be stated mathematically by the following equation, given VPPT (probabilistic-polynomial time) adversaries, A, 3 a negligible function in n, neg(n), such that:

In most encryption schemes today the length of the message is not hidden in the ciphertext, therefore, the chosen message m0, m{ by the adversary must have equal length. Otherwise, they can be easily distinguishable.

This probabilistic security definition can also be described as a game between the challenger and the adversary as shown in Figure 4.1.

In this game between the challenger and the adversary, we say that adversary wins if b' = b and we say that our scheme is secure if VPPT A,

• 1
• 3neg(n): Pr[A wins the game} = —+neg(n). From this probability, if we subtract the trivial component, i.e. 1/2, then what we get is technically called the advantage of adversary in winning the game, and for a scheme to be secure this advantage should be negligible.

Figure 4.1 Game-based security definition.