Securitatea semantică poate fi definită folosind experimentul/jocul de distingere, pe care îl amintim după cum urmează:
Lăsa $(E,D)$ să fie o schemă de criptare. După ce contestatorul alege un parametru de securitate $n$ și cheie aleatorie $k$, adversarul (de securitate semantică) alegând două mesaje $m_0, m_1$ care depind de $n$. Provocatorul alege un pic la întâmplare $b \în \{0,1\}$, prevede $E_k(m_b)$ adversarului care apoi trebuie să decidă dacă $b$ este $0$ sau $1$.
Întrebare: Mesajele $m_0$ și $m_1$ sunt de lungime polinomială în $n$, dar sunt ele de fapt funcții calculabile ale $n$? adică adversarul calculează $m_0$ și $m_1$ folosind o mașină Turing care rulează în timp polinomial?
Bănuiesc că răspunsul este nu, nu sunt calculabile (dar totuși lungimea polinomului). Mă bazez pe asta încercând să demonstrez proprietățile securității semantice, cum ar fi imposibilitatea ghicirii biților și a recuperării mesajelor etc. De asemenea, cred că acest lucru este precizat în cartea lui Goldreich, unde nu există generarea mesajelor și doar specificarea lungimii polinomului lor (dar el folosește în schimb familii de circuite cu care nu sunt familiarizat), dar în Katz-Lindell se pare că există o ambiguitate în această definiție.
