Title: Theory / Unimportant / CS / Fundamental / Complexity / Complexity Arora Barak/{ / Crypto
Tags: fromMath mathToDef automaticImplies mathToSee

Name: An encryption scheme
Definition: A pair of family of functions \(D_k(x)\) and \(E_k(x)\) such that \(D_k(E_k(x))=x\) for all \(k\).
Page: 174
Chapter: 9
Section: 1

Name: The cyphertex
Definition: \(E_k(x)\).
Page: 174
Chapter: 9
Section: 1
Variables: \((D,E)\) an encryption scheme.

Name: The decryption algorithm
Definition: \(D\).
Page: 174
Chapter: 9
Section: 1
Variables: \((D,E)\) an encryption scheme.

Name: The encryption algorithm
Definition: \(E\).
Page: 174
Chapter: 9
Section: 1
Variables: \((D,E)\) an encryption scheme.

Name: The plain text
Definition: \(x=D_k(E_k(x))\).
Page: 174
Chapter: 9
Section: 1
Variables: \((D,E)\) an encryption scheme.

Name: The key
Definition: The parameter \(k\) in \(x=D_
k(E_k(x))\).
Page: 174
Chapter: 9
Section: 1
Variables: \((D,E)\) an encryption scheme.

Name: The perfect secrecy property
Definition: An encryption scheme \((D,E)\) such that for every pair of messages \(x,x'\in\{0,1\}^m\), the distributions \(\text E_{U_n}(x)\) and \(\text E_{U_n}(x')\) are identical.
Page: 174
Chapter: 9
Section: 1
Kind: Def

Name: One time pad
Definition: The encryption scheme \((\oplus,\oplus)\).
Page: 175
Chapter: 9
Section: 1

Smaller0: they have perfect secrecy
Greater0: the size of the key is at least the size of the message
Page: 175
Chapter: 9
Section: 1
Variables: \((E,D)\) an encryption schema.

Q: \(f\) is [...] if [...].
A: negligible; \(f(n)=n^{-\omega(1)}\)
Page: 175
Chapter: 9
Section: 1
Variables: Let \(f:\mathbb N\to\mathbb N\)
Index: Def
Extra: 3

Smaller0: \(P=NP\)
Greater0: there exists an algorithm \(A\) and \(x_0,x_1\in\{0,1\}^m\) such that \(\text{Pr}_{b\in\{0,1\}, k\in\{0,1\}^n}[A(E_k(x_b))=b]\ge 3/4\)
Page: 175
Chapter: 9
Section: 1
Variables: \((E,D)\) an encryption schema, \(n<m\in\mathbb N\)
Index: 2
Kind: Lem