Public Key Encryption

elgamal-pke rsa

TODO:

• Probabilistic encryption
  • GM82
  • El-gamal
  • Pailier
• trapdoor permutation
• [ ]

Public Key encryption scheme: $\text{Gen,Enc,Dec}$:

• $\text{Gen}(1^n)\to (sk,pk)$: public key defines the message space ${\mathcal{M}}_{pk}$
• $\text{Enc}(sk,m)\to c$: takes secret key and message $m\in {\mathcal{M}}_{pk}$ and outputs a ciphertext $c$.
• $\text{Dec}(pk,c)\to m$

CPA security

eavesdropping indistinguishability experiment ${\text{PubK}}_{\mathcal{A},\Pi }^{\text{eav}}(n)$:

• $\text{Gen}(1^n)\to sk,pk$
• $\mathcal{A}$ is given pk, outputs a pair of messages $m_0,m_1$
• uniform bit $b$ is chosen and challenge ciphertext $c\leftarrow {\text{Enc}}_{sk}(m_b)$ is given to $\mathcal{A}$.
• $\mathcal{A}$ outputs bit b’.
• experiment succeeds if $b^{\prime }=b$ and outputs 1.

$\mathrm{Pr}[{\text{PubK}}_{\mathcal{A},\Pi }^{\text{eav}}=1]\le \frac{1}{2}+\text{negl}(n)$

No Deterministic public-key encryption is CPA-secure.

Proven in GM82, that any information that a adversary is able to gain about plaintext from ciphertext, it can gain that knowledge without ciphertext. Thus, any protocol designed on deterministic PK encryption is insecure. This includes, RSA without padding, block ciphers without IV.

TODO, read the paper in more detail.

CPA security for multiple encryption:

Prove that any CPA secure PK encryption scheme is also secure for multiple encryptions (adversary is given access to LR oracle ${\text{LR}}_{pk,b}(\cdot ,\cdot )$ that encrypts left or right message depending on the bit).

Informal proof using reduction approach:

• Create a new experiment $\text{LR-cpa2}$, that allows maximum 2 oracle queries.
• $\mathcal{A}$ selects two sets of message pairs: $m_{1,0},m_{1,1}$ and $m_{2,0},m_{2,1}$, and gets back ciphertext $c_1,c_2$ that can be either equal to $m_{1,0},m_{2,0}$ or $m_{1,1},m_{2,1}$ from oracle, and need to differentiate between the two.
• Let ${\overrightarrow{C}}_0$ denote distribution of messages in first pair, and ${\overrightarrow{C}}_1$ denote second pair.
• Prove: $\mathrm{Pr}[\mathcal{A}(pk,m_{1,0},m_{2,0})=1]-\mathrm{Pr}[\mathcal{A}(pk,m_{2,0},m_{2,1})=1]\le \text{negl}(n)$.
• Create a new adversary ${\mathcal{A}}^{\prime }$ that simulates oracle for $\mathcal{A}$, but fixes first message, i.e. $\mathcal{A}$ receives either $m_{1,0},m_{2,0}$ or $m_{1,0},m_{2,1}$. Let this distribution be denoted as ${\overrightarrow{C}}_{01}$
• If $\mathcal{A}$ can distinguish between ${\overrightarrow{C}}_0,{\overrightarrow{C}}_{01}$, then it can distinguish between ${\overrightarrow{C}}_{01},{\overrightarrow{C}}_1$. By simple linear algebra, it can distinguish between ${\overrightarrow{C}}_0,{\overrightarrow{C}}_1$.
• Due to CPA security of $\Pi$, view of $\mathcal{A}$ running as a subroutine by $\mathcal{A}$ will be equal to that of ${\text{PubK}}_{\mathcal{A},\Pi }^{\text{LR-cpa}}$. So, if ${\mathcal{A}}^{\prime }$ is able to distinguish between, $m_{2,0},m_{2,1}$ due to $\mathcal{A}$, then it will break CPA security. Since, this probability is negligible, $\mathcal{A}$ can’t distinguish.

Formal proof using hybrid argument approach:

• TODO: need to read more about hybrid argument approach, but the experiment is again choosing an adversary ${\mathcal{A}}^{\prime }$ that is able to break CPA security of $\Pi$ if $\mathcal{A}$ outputs correct bit.
• let $t$ be the maximum oracle queries $\mathcal{A}$ can make, and t is polynomially bounded.
• ${\mathcal{A}}^{\prime }$ chooses a random index: $1\le i\le t$.
• For jth encrpytion:
  • if j<i, then send $c_j\leftarrow Enc(m_{j,0})$, else if $j>i⟹Enc(m_{j,1})$
  • if j=i, then output $m_{i,0},m_{i,1}$, receive challenge ciphertext $c$, send to $\mathcal{A}$
• ${\mathcal{A}}^{\prime }$ outputs $b^{\prime }$ by $\mathcal{A}$. experiment succeeds if $b^{\prime }=b$.
• Now, using a hybrid argument prove that probability of $\mathrm{Pr}[{\mathcal{A}}^{\prime }(\cdot )=1]=\frac{1}{2}\cdot \mathrm{Pr}[{\mathcal{A}}^{\prime }(\cdot )=1|b=0]+\frac{1}{2}\cdot \mathrm{Pr}[{\mathcal{A}}^{\prime }(\cdot )=1|b=1]$

CCA security

analogous to CCA security for CCA security, in PK encryption, adversary gets access to a decryption oracle and can query any ciphertext other than the challenge ciphertext. It can be proven that any PK encryption that’s CCA secure for single encryption is CCA secure for multiple encryption as well.

Examples where CCA encryption is needed:

• In a private auction, where an adversary can look at other bids as ciphertext, and instead send ciphertext $c^{\prime }=\text{Enc}(m+1)$. This property is known as malleability.
• modifying an encrypted message $c:=\text{Enc}(m)\to c^{\prime }$. If it receives any error, or a response quoting $m^{\prime }$, then $\mathcal{A}$ has now decrypted c’.

KEM

set of algorithms:

• $Gen(1^n)\to (pk,sk)$
• ${\text{Encaps}}_{pk}(1^n)\to (c,k)$: gives a uniform key $\in \{0,1{\}}^n$
• ${\text{Decaps}}_{sk}(c)\to k$

can be combined with a private key encryption to create a hybrid encryption scheme: ${\Pi }_{\text{hy}}:{\Pi }_{\text{KEM}},{\Pi }^{\prime }$:

• $Gen(1^n)\to (sk,pk)$
• ${\text{Enc}}_{pk}^{\prime }(m)\to (c,c^{\prime })$: $(c,k)\leftarrow {\text{Encaps}}_{pk}(1^n)$, and $c^{\prime }\leftarrow {\text{Enc}}_k(m)$
• ${\text{Dec}}^{\prime }(c,c^{\prime })\to m$: ${\text{Decaps}}_{sk}(c)\to k;{\text{Dec}}_k(c^{\prime })\to m$.

security

If KEM is CPA secure, and $\Pi$ is EAV-secure, then ${\Pi }^{\prime }$ is CPA secure PK encryption scheme.

Proof: TODO

If KEM is CCA secure, and $\Pi$ is CCA secure, then ${\Pi }^{\prime }$ is CCA secure encryption scheme.

CCA security for KEM: $\mathrm{Pr}[{\text{KEM}}_{\mathcal{A},\Pi }^{\text{cca}}(n)]$:

• $\text{Gen}(1^n)\to (pk,sk);\text{Encaps}(1^n)\to (c,k\in \{0,1{\}}^n)$
• $b\in \{0,1\}$ is chosen, if $b=0⟹\hat{k}=k$ else $\hat{k}\in \{0,1{\}}^n$
• $\mathcal{A}$ is given $(pk,c,\hat{k})$, and access to ${\text{Decaps}}_{sk}(\cdot )$ oracle, but can’t query decaps for challenge ciphertext $c$ itself.
• $\mathcal{A}\to b^{\prime }\in \{0,1\}$, if $b=b$ output 1, else 0.

$\mathrm{Pr}[{\text{KEM}}_{\mathcal{A},\Pi }^{\text{cca}}(n)=1]\le \frac{1}{2}+\text{negl}(n)$.

• If ${\Pi }^{\prime }$ is not CCA secure then, adversary can just modify ciphertext c’, as $c^{\prime }\oplus m^{\prime }$.
• For ${\Pi }_{KEM}$ to be CCA secure, give $\mathcal{A}$ access to decaps oracle which allows it to decapsulate any ciphertext and get key of its choice.

ElGamal KEM

• $\text{Gen}(1^n)\to (pk,sk)$: Choose $\mathbb{G},g,q$, then choose a uniform $x\in {\mathbb{Z}}_q$, set $h:=g^x$. Specify a function $H:\mathbb{G}\to \{0,1{\}}^{l(n)}$. Outputs $pk=(\mathbb{G},g,q,h,H),sk=(\mathbb{G},g,q,x)$.
• $\text{Encaps}(pk)$: choose a $y\in {\mathbb{Z}}_q$, output $c=g^y$ and calculate $k=H(h^y))$
• $\text{Decaps}(sk,(c,k))$: compute key as $k:=H(c^x)$.

Above model is CPA secure, if DDH problem is hard.

CDH based KEM in ROM

If $H$ is modelled as a random oracle, then above KEM is CPA secure, if CDH problem is hard.

CDH is a stronger security assumption that deals with extractability, i.e. adversary has to find out $h^y$.

CCA security for Hybrid encryption

Gap-CDH assumption

For any adversary, it remains infeasible to compute $g^{xy}$ even when given access to a oracle ${\mathcal{O}}_y(U,V)$ that returns 1 only when $V=U^y$. Informally, CDH problems remains hard even when an oracle that solved DDH is given.

ElGamal KEM as stated above is CCA secure if the Gap-CDH assumption is hard.

Thus, to create a CCA secure hybrid encryption, one needs to use a CCA private-key encryption scheme. Alternatively, a CPA secure encryption scheme, and CPA secure MAC leads to a CCA secure PK scheme.