🌑

Explore / Study / Computer Science / Cryptography 1.2k words | 7 minutes

§3 Shannon’s Theorem and Computational Security

  1. Shannon’s Theorem
    1. Shannon’s Theorem
  2. Computational Security
    1. Security Parameter nnn
    2. Efficient (Probabilistic Polynomial Time) Adversary
    3. Negligible Success Probability: Negligible Functions
    4. Closure Properties of Negligible Functions
    5. Computational Security: Asymptotic Approach
    6. Redefining Private Key Encryption
    7. Adversarial Indistinguishability Experiment PrivK⁡A,Πeav(n)\operatorname{PrivK}_{\mathscr{A}, \Pi}^{\mathrm{eav}}(n)PrivKA,Πeav​(n)
    8. Computational Indistinguishability or EAV-security

Shannon’s Theorem

Shannon’s Theorem

  • Theorem. (Shannon’s Theorem). Let (Gen,Enc,Dec)(Gen, Enc, Dec) be an encryption scheme with message space M\mathscr M for which M=K=C|\mathscr M| = |\mathscr K| = | \mathscr C |. The scheme is perfectly secret if and only if
    1. Every key kKk \in \mathscr K is chosen with equal probability 1/K1/ |\mathscr K| by the GenGen algorithm.
    2. For every mMm \in \mathscr M and every cCc \in \mathscr C there exists a unique key kKk \in \mathscr K such that Enck(m)Enc_k(m) outputs cc.

Computational Security

Security Parameter nn

  • Let us introduce an integer-valued security parameter nn chosen by honest parties before they begin a cryptographic scheme.

    Typically nn will correspond to the length of the key.

    The security parameter nn is assumed to be known to the adversary.

Efficient (Probabilistic Polynomial Time) Adversary

  • An algorithm AA runs in polynomial time if there exists a polynomial pp such that for every input x{0,1}x \in \{0,1\}^* the computation of A(x)A(x) terminates within at most p(x)p (|x|) steps.
  • A probabilistic (randomized) algorithm is one that has the capability of “tossing coins”, i.e. the algorithm has access to a source of randomness that yields unbiased random bits that are
    independently equal to 11 with probability 1/21/2 and to 00 with probability 1/21/2.
  • The adversary is said to be efficient or Probabilistic Polynomial Time (PPT) if it is using a randomized (probabilistic) algorithm running in time polynomial in nn.

Negligible Success Probability: Negligible Functions

  • Definition. A function f:NRf : \mathbb{N} → \mathbb{R} is polynomially bounded if there exist constants c,dR+c, d \in \mathbb{R}_+ such that for all positive integers nn, we have f(n)nc+d| f(n) | ≤ n^c + d.

  • Definition. A function f:NR0f : \mathbb{N} \rightarrow \mathbb{R}_{\ge 0} is negligible if for every positive polynomial pp there is an NN such that for all integers n>Nn > N it holds that f(n)<1p(n)\displaystyle f(n) < \frac{1}{p(n)}, i.e.,

    p,N s.t. f(n)<1p(n) for n>N\forall p, \exists N \text { s.t. } f(n)<\frac{1}{p(n)} \text { for } n>N

  • Equivalently, function f:NR0f : \mathbb{N} \rightarrow \mathbb{R}_{\ge 0} is negligible if for all constants cc there exists an NN such that for all n>Nn > N it holds that f(n)<ncf(n) < n^{-c}. We usually denote a negligible function by negl or by ϵ(n)\epsilon(n).

  • Equivalently, a function f:NR0f : \mathbb{N} \rightarrow \mathbb{R}_{\ge 0} is negligible if and only if for all c>0c > 0, we have limnf(n)nc=0\displaystyle \lim _{n \rightarrow \infty} f(n) n^{c}=0.

Closure Properties of Negligible Functions

  • Theorem. If f1(n)f_1(n) and f2(n)f_2(n) are negligible functions, then the following hold:
    1. The function f3(n)=f1(n)+f2(n)f_3(n) = f_1(n) + f_2(n) is a negligible function,
    2. For any positive polynomial p, the function f4(n)=p(n)f1(n)f_4(n) = p(n) ⋅ f_1(n) is negligible.

Computational Security: Asymptotic Approach

  • A scheme is secure if for every probabilistic polynomial-time adversary A\mathscr A carrying out an attack of some formally specified type, and for every positive polynomial pp, there exists integer NN such that when n>Nn > N the probability that A\mathscr A succeeds in this attack is less than 1p(n)\displaystyle \frac{1}{p(n)}.

Redefining Private Key Encryption

  • Definition. A private-key encryption scheme is a tuple of probabilistic polynomial-time algorithms (Gen,Enc,Dec)(Gen, Enc, Dec) such that:
    1. The key-generation algorithm GenGen takes as input 1n1^n and outputs a key kk, i.e., kGen(1n)k \leftarrow Gen(1^n). We assume wlog that any key kk output by Gen(1n)Gen(1^n) satisfies kn|k| \ge n.
    2. The encryption algorithm EncEnc takes as input a key kk and a plaintext message m{0,1}m \in \{0,1\}^*, and outputs a ciphertext cc, i.e. cEnck(m)c \leftarrow Enc_k(m).
    3. The decryption algorithm DecDec takes as input a key kk and a ciphertext cc, and outputs a message mm or error \perp. We write m:=Deck(c)m := Dec_k(c) when DecDec does not return an error.

Adversarial Indistinguishability Experiment PrivKA,Πeav(n)\operatorname{PrivK}_{\mathscr{A}, \Pi}^{\mathrm{eav}}(n)

  1. The adversary A\mathscr A is given input 1n1^n and outputs a pair of messages m0m_0, m1m_1 with m0=m1|m_0| = |m_1|.
  2. A key kk is generated by running Gen(1n)Gen (1^n) and a uniform bit b{0,1}b \in \{0,1\} is chosen. Challenge ciphertext cEnck(mb)c \leftarrow Enc_k (m_b) is computed and given to A\mathscr A.
  3. Adversary A\mathscr A outputs a bit b{0,1}b' \in \{0,1\}.
  4. The adversary A\mathscr A succeeds and the output of the experiment is defined to be 11 if b=bb = b' and 00 otherwise, i.e., we set PrivKA,Πeav(n)=1\operatorname{PrivK}_{\mathscr{A}, \Pi}^{\mathrm{eav}}(n) = 1 if adversary succeeds in guessing the bit.

Computational Indistinguishability or EAV-security

  • Definition. A private-key encryption scheme Π=(Gen,Enc,Dec)\Pi = (Gen, Enc, Dec) has indistinguishable encryptions in the presence of an eavesdropper, or is EAV-secure, if for all probabilistic polynomial-time adversaries A\mathscr A there is a negligible function ϵ\epsilon such that for all nn,

    Pr[PrivKA,Πeav(n)=1]12+ϵ(n)\operatorname{Pr}\left[\operatorname{PrivK}_{\mathscr{A}, \Pi}^{\mathrm{eav}}(n)=1\right] \leq \frac{1}{2}+\epsilon(n)

— Feb 1, 2023

Creative Commons License
§3 Shannon’s Theorem and Computational Security by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.