fc0607 lect1

Foundations of CryptographyLecture 1: Introduction, Identification, One-way functions : 

Foundations of Cryptography Lecture 1: Introduction, Identification, One-way functions Lecturer: Moni Naor Weizmann Institute of Science

What is Cryptography? : 

What is Cryptography? Traditionally: how to maintain secrecy in communication Alice and Bob talk while Eve tries to listen Alice Bob Eve

History of Cryptography: 

History of Cryptography Very ancient occupation Biblical times - איך נלכדה ששך ותתפש תהלת כל הארץ איך היתה לשמה בבל בגויים Many interesting books and sources, especially about the Enigma David Kahn, The Codebreakers, 1967 Gaj and Orlowski, Facts and Myths of Enigma: Breaking Stereotypes Eurocrypt 2003 Not the subject of this course!

Modern Times: 

Modern Times Up to the mid 70’s - mostly classified military work Exception: Shannon, Turing* Since then - explosive growth Commercial applications Scientific work: tight relationship with Computational Complexity Theory Major works: Diffie-Hellman, Rivest, Shamir and Adleman (RSA) Recently - more involved models for more diverse tasks. How to maintain the secrecy, integrity and functionality in computer and communication system.

Cryptography and Complexity: 

Complexity Theory - Study the resources needed to solve computational problems computer time, memory Identify problems that are infeasible to compute. Cryptography - Find ways to specify security requirements of systems Use the computational infeasibility of problems in order to obtain security. The development of these two areas is tightly connected! Cryptography and Complexity

Key Idea of Cryptography: 

Key Idea of Cryptography Use the intractability of some problems for the advantage of constructing secure system Almost any cryptographic task requires using this idea. Our goal is to investigate this relationship

Administrivia: 

Administrivia Instructor: Moni Naor Grader: Gil Segev When:    Wednesday 16:00--18:00 Where:   Ziskind 1 Home page of the course: www.wisdom.weizmann.ac.il/~naor/COURSE/foundations_of_crypto.html METHOD OF EVALUATION: around 8 homework assignments and a final (in class) exam. Also must prepare notes for (at least) one lecture. Homework assignments should be turned in on time (usually two weeks after they are given)! Try and do as many problems from each set. You may discuss the problems with other students, but the write-up should be individual. There will also be reading assignments.

Official Description: 

Official Description Cryptography deals with methods for protecting the privacy, integrity and functionality of computer and communication systems. The goal of the course is to provide a firm foundation to the construction of such methods. In particular we will cover topics such as notions of security of a cryptosystem, proof techniques for demonstrating security and cryptographic primitives such as one-way functions and trapdoor permutations

What you will learn in this course: 

What you will learn in this course How to specify a cryptographic task How to specify a solution Relationship with complexity assumptions

Lectures Outline: 

Lectures Outline Identification, Authentication and encryption One-way functions and their essential role in cryptography Universal one-way functions, multiple identifications, Amplification: from weak to strong one-way functions Universal hashing and authentication. One-way hashing Signature Scheme: Existentially unforgeability Pseudo-random generators Hardcore predicates, Pseudo-Random Functions and Permutations. Semantic Security and Indistinguishability of Encryptions. Zero-Knowledge Proofs and Arguments Chosen ciphertext attacks and non-malleability Oblivous Transfer and Secure Function Evaluation

Three Basic Issues in Cryptography: 

Three Basic Issues in Cryptography Identification Authentication Encryption

Example: Identification: 

Example: Identification When the time is right, Alice wants to send an `approve’ message to Bob. They want to prevent Eve from interfering Bob should be sure that Alice indeed approves Alice Bob Eve

Rigorous Specification of Security: 

Rigorous Specification of Security To define security of a system must specify: What constitute a failure of the system The power of the adversary computational access to the system what it means to break the system.

Specification of the Problem: 

Specification of the Problem Alice and Bob communicate through a channel Bob has two external states {N,Y} Eve completely controls the channel Requirements: If Alice wants to approve and Eve does not interfere – Bob moves to state Y If Alice does not approve, then for any behavior from Eve, Bob stays in N If Alice wants to approve and Eve does interfere - no requirements from the external state

Can we guarantee the requirements?: 

Can we guarantee the requirements? No – when Alice wants to approve she sends (and receives) a finite set of bits on the channel. Eve can guess them. To the rescue - probability. Want that Eve will succeed only with low probability. How low? Related to the string length that Alice sends…

Identification: 

Identification Alice Bob Eve X X ??

Suppose there is a setup period: 

Suppose there is a setup period There is a setup where Alice and Bob can agree on a common secret Eve only controls the channel, does not see the internal state of Alice and Bob (only external state of Bob) Simple solution: Alice and Bob choose a random string X R {0,1}n When Alice wants to approve – she sends X If Bob gets any symbols on channel – compares to X If equal moves to Y If not equal moves permanently to N

Eve’s probability of success: 

Eve’s probability of success If Alice did not send X and Eve put some string X’ on the channel, then Bob moves to Y only if X= X’ Prob[X=X’] ≤ 2-n Good news: can make it a small as we wish What to do if Alice and Bob cannot agree on a uniformly generated string X?

Less than perfect random variables: 

Less than perfect random variables Suppose X is chosen according to some distribution Px over some set of symbols Γ What is Eve’s best strategy? What is her probability of success

(Shannon) Entropy: 

(Shannon) Entropy Let X be random variable over alphabet Γ with distribution Px The (Shannon) entropy of X is H(X) = - ∑ x Γ Px (x) log Px (x) Where we take 0 log 0 to be 0. Represents how much we can compress X

Examples: 

Examples If X=0 (constant) then H(x) = 0 Only case where H(x) = 0 is when x is constant All other cases H(x) >0 If X  {0,1} and Prob[X=0] = p and Prob[X=1]=1-p, then H(X) = -p log p + (1-p) log (1-p) ≡ H(p) If X  {0,1}n and is uniformly distributed, then H(X) = - ∑ x  {0,1}n 1/2n log 1/2n = 2n/2n n = n

Properties of Entropy: 

Properties of Entropy Entropy is bounded H(X) ≤ log | Γ | with equality only if X is uniform over Γ

Does High Entropy Suffice for Identification?: 

Does High Entropy Suffice for Identification? If Alice and bob agree on X  {0,1}n where X has high entropy (say H(X) ≥ n/2 ), what are Eve’s chances of cheating? Can be high: say Prob[X=0n ] = 1/2 For any x 1{0,1} n-1 Prob[X=x ] = 1/2n Then H(X) = n/2+1/2 But Eve can cheat with probability at least ½ by guessing that X=0n

Another Notion: Min Entropy: 

Another Notion: Min Entropy Let X be random variable over alphabet Γ with distribution Px The min entropy of X is Hmin(X) = - log max x Γ Px (x) The min entropy represents the most likely value of X Property: Hmin(X) ≤ H(X) Why?

High Min Entropy and Passwords: 

High Min Entropy and Passwords Claim: if Alice and Bob agree on such that Hmin(X) ≥ m, then the probability that Eve succeeds in cheating is at most 2-m Proof: Make Eve deterministic, by picking her best choice, X’ = x’. Prob[X=x’] = Px (x’) ≤ max x Γ Px (x) = 2 –Hmin(X) ≤ 2-m Conclusion: passwords should be chosen to have high min-entropy!

Slide26: 

Good source on Information Theory: T. Cover and J. A. Thomas, Elements of Information Theory

One-time vs. many times: 

One-time vs. many times This was good for a single identification. What about many sessions of identification? Later…

A different scenario – now Charlie is involved: 

A different scenario – now Charlie is involved Bob has no proof that Alice indeed identified If there are two possible verifiers, Bob and Charlie, they can each pretend to each other to be Alice Can each have there own string But, assume that they share the setup phase Whatever Bob knows Charlie know Relevant when they are many of possible verifiers!

The new requirement: 

The new requirement If Alice wants to approve and Eve does not interfere – Bob moves to state Y If Alice does not approve, then for any behavior from Eve and Charlie, Bob stays in N Similarly if Bob and Charlie are switched Alice Bob Eve Charlie

Can we achieve the requirements?: 

Can we achieve the requirements? Observation: what Bob and Charlie received in the setup phase might as well be public Therefore can reduce to the previous scenario (with no setup)… To the rescue - complexity Alice should be able to perform something that neither Bob nor Charlie (nor Eve) can do Must assume that the parties are not computationally all powerful!

Function and inversions: 

Function and inversions We say that a function f is hard to invert if given y=f(x) it is hard to find x’ such that y=f(x’) x’ need not be equal to x We will use f-1(y) to denote the set of preimages of y To discuss hard must specify a computational model Use two flavors: Concrete Asymptotic

Computational Models: 

Computational Models Asymptotic: Turing Machines with random tape For classical models: precise model does not matter up to polynomial factor Random tape 0 0 0 1 1 1 1 Input tape Both algorithm for evaluating f and the adversary are modeled by PTM

One-way functions - asymptotic: 

One-way functions - asymptotic A function f: {0,1}* → {0,1}* is called a one-way function, if f is a polynomial-time computable function Also polynomial relationship between input and output length for every probabilistic polynomial-time algorithm A, every positive polynomial p(.), and all sufficiently large n’s Prob[ A(f(x))  f-1(f(x)) ] ≤ 1/p(n) Where x is chosen uniformly in {0,1}n and the probability is also over the internal coin flips of A

Computational Models: 

Computational Models Concrete : Boolean circuits (example) precise model makes a difference Time = circuit size Output Input

One-way functions – concrete version: 

One-way functions – concrete version A function f:{0,1}n → {0,1}n is called a (t,ε) one-way function, if f is a polynomial-time computable function (independent of t) for every t-time algorithm A, Prob[A(f(x))  f-1(f(x)) ] ≤ ε Where x is chosen uniformly in {0,1}n and the probability is also over the internal coin flips of A Can either think of t and ε as being fixed or as t(n), ε(n) circuit

Complexity Theory and One-way Functions: 

Complexity Theory and One-way Functions Claim: if P=NP then there are no one-way functions Proof: for any one-way function f: {0,1}n → {0,1}n consider the language Lf : Consisting of strings of the form {y, b1, b2,…,bk} There is an x  {0,1}n such that y=f(x) and The first k bits of x are b1, b2…bk Lf is NP – guess x and check If Lf is P then f is invertible in polynomial time: Self reducibility

A few properties and questions concerning one-way functions: 

A few properties and questions concerning one-way functions Major open problem: connect the existence of one-way functions and the P=NP? question. If f is one-to-one it is a called a one-way permutation. In what complexity class does the problem of inverting one-way permutations reside? good exercise! If f’ is a one-way function, is f’ where f’(x) is f(x) with the last bit chopped a one-way function? If f is a one-way function, is fL where fL(x) consists of the first half of the bits of f(x) a one-way function? good exercise! If f is a one way function is g(x) = f(f(x)) necessarily a one-way function? good exercise!

Solution to the password problem: 

Solution to the password problem Assume that f: {0,1}n → {0,1}n is a (t,ε) one-way function Adversary’s run times is bounded by t Setup phase: Alice chooses xR {0,1}n computes y=f(x) Gives y to Bob and Charlie When Alice wants to approve – she sends x If Bob gets any symbols on channel – call them z; compute f(z) and compares to y If equal moves to state Y If not equal moves permanently to state N

Eve’s and Charlie’s probability of success: 

Eve’s and Charlie’s probability of success If Alice did not send x and Eve (Charlie) put some string x’ on the channel to Bob, then: Bob moves to state Y only if f(x’)=y=f(x) But we know that Prob[A[f(x)]  f-1(f(x)) ] ≤ ε or else we can use Eve to break the one-way function Good news: if ε can be made as small as we wish, then we have a good scheme. Can be used for monitoring Similar to the Unix password scheme f(x) stored in login file DES used as the one-way function. y y x’ y x’ Eve A’ The time and probability of success of breaking the identification scheme by Eve same as The time and probability of inverting f by A’

Reductions: 

Reductions This is a simple example of a reduction Simulate Eve’s algorithm in order to break the one-way function Most reductions are much more involved Do not preserve the parameters so well

Cryptographic Reductions: 

Cryptographic Reductions Show how to use an adversary for breaking primitive 1 in order to break primitive 2 Important Run time: how does T1 relate to T2 Probability of success: how does 1 relate to 2 Access to the system 1 vs. 2

Examples of One-way functions: 

Examples of One-way functions Examples of hard problems: Subset sum Discrete log Factoring (numbers, polynomials) into prime components How do we get a one-way function out of them? Easy problem

Subset Sum: 

Subset Sum Subset sum problem: given n numbers 0 ≤ a1, a2 ,…, an ≤ 2m Target sum T Find subset S⊆ {1,...,n} ∑ i S ai,=T (n,m)-subset sum assumption: for uniformly chosen a1, a2 ,…, an R{0,…2m -1} and S⊆ {1,...,n} For any probabilistic polynomial time algorithm, the probability of finding S’⊆ {1,...,n} such that ∑ i S ai= ∑ i S’ ai is negligible, where the probability is over the random choice of the ai‘s, S and the inner coin flips of the algorithm Not true for very small or very large m Subset sum one-way function f:{0,1}mn+n → {0,1}mn+m f(a1, a2 ,…, an , b1, b2 ,…, bn ) = (a1, a2 ,…, an , ∑ i=1n bi ai mod 2m ) Assumption  f is one way

Exercise: 

Exercise Show a function f such that if f is polynomial time invertible on all inputs, then P=NP f is not one-way

Discrete Log Problem: 

Discrete Log Problem Let G be a group and g an element in G. Let y=gz and x the minimal non negative integer satisfying the equation. x is called the discrete log of y to base g. Example: y=gx mod p in the multiplicative group of Zp In general: easy to exponentiate via repeated squaring Consider binary representation What about discrete log? If difficult, f(g,x) = (g, gx ) is a one-way function

Integer Factoring: 

Integer Factoring Consider f(x,y) = x • y Easy to compute Is it one-way? No: if f(x,y) is even can set inverse as (f(x,y)/2,2) If factoring a number into prime factors is hard: Specifically given N= P • Q , the product of two random large (n-bit) primes, it is hard to factor Then somewhat hard – there are a non-negligible fraction of such numbers ~ 1/n2 from the density of primes Hence a weak one-way function Alternatively: let g(r) be a function mapping random bits into random primes. The function f(r1,r2) = g(r1) • g(r2) is one-way