Esperimento $PrivK^{eav}_{A, \Pi}(n)$

<aside> 💡

$PrivK^{eav}_{A, \Pi}(n)$

• $A$ ottiene $1^n$ e dà in output $m_0, m_1$ tali che $|m_0|=|m_1|$
• il challenger calcola $c \leftarrow Enc_k(m_b)$ dove $b \leftarrow \{0,1\}$ e $k \leftarrow Gen(1^n)$
• $A(1^n)$ riceve $c$ e dà in output $b' \in \{0,1\}$
• se $b=b'$ l’output dell’esperimento è $1$ e $A(1^n)$ vince, altrimenti $0$ </aside>

EAV-sicuro

Uno schema di cifratura a chiave privata $\Pi= (Gen, Enc, Dec)$ ha cifrature indistinguibili in presenza di un eavesdropper (EAV-sicuro) se per ogni Adv $A$ PPT esiste una funzione trascurabile $negl$ tale che:

<aside> 💡

$Pr[PrivK^{eav}_{A, \Pi}(n) = 1]\leq \frac{1}2 + negl(n)$

</aside>

dove la probabilità è calcolata su

• randomness usata da $A$
• randomness usata nell’esperimento
  • scelta della chiave
  • scelta del bit $b$
  • random bit usati da $Enc_k(\cdot )$

Sicurezza semantica

Dovrebbe essere impraticabile per un Adv acquisire alcuna informazione aggiuntiva sul messaggio in chiaro dal cifrato

Semanticamente sicuro

Uno schema di cifratura a chiave privata $\Pi = (Gen, Enc, Dec)$ è semanticamente sicuro in presenza di un eavesdropper se per ogni Adv $A$ PPT esiste un Adv $A'$ PPT tale che per qualsiasi $Samp(1^n)$ PPT e per ogni coppia di funzioni $f$ ed $h$ calcolabili in tempo polinomiale esiste una funzione trascurabile $negl$ per cui si ha:

<aside> 💡

$|Pr[A(1^n,Enc_k(m), h(m)) = f(m)] -Pr[A'(1^n,|m|,h(m)) = f(m) ]| \leq negl(n)$

</aside>

Teoremi intermedi

L’indistinguibilità implica che:

1. il cifrato non rivela alcuna informazione sui singoli bit del messaggio in chiaro
2. il cifrato non aiuta un Adv PPT nel calcolo di qualsiasi funzione del messaggio in chiaro

che sono esattamente i requisiti della sicurezza semantica

Teorema