Semantic Security

# Definition

A cryptoscheme is semantically secure if it is secure against an adversary of polynomially bounded computing power.

For all probability distributions on the message space, whatever a passive adversary can compute in polynomial time about the plaintext given the ciphertext they could have also computed without the ciphertext.

Having the cipher test doesn't help one to learn anything about an encrypted message.

# Extended Definition

Like perfect security but we only allow adversaries with polynomially bounded computing power. Whatever an adversary can compute in polynomial time about the plaintext given the ciphertext, they should also be able to compute without the ciphertext. In other words having the ciphertext does not help finding anything about the message.

Suppose that the information we wish to compute on the message space is a single bit.

(1)
\begin{align} g \; : \; M \to \{0,1\} \end{align}
(2)
\begin{align} \forall \mathbb{P} \;\;\;\;\; p(g(m) = 1) = p(g(m) = 0) = 1/2 \end{align}

Where $len(m) = len(c)$

The adversary is an algorithm S, which takes ciphertext $c$ and public key $y$

(3)
\begin{align} S(c,y) \to \{0,1\} \end{align}

The adversary is successful if the probability of it being correct is greater than 1/2. An adversary is successful if it can do better after seeing the ciphertext. The advantage of the adversary is calculated by:

(4)
$$Adv_s = |p(S(c,y)=g(d_x(c)) - 1/2 |$$

where $d_x$ is the decryption under the secret key $x$ associated with the public key $y$.

A scheme is then said to be semantically secure if

(5)
where $p(k)$ is a polynomial function and $k$ is large.