Pseudo random Number generators

Question 1

If families of UOWHF exist

Answer 1

then signature schemes existentially unforgeable under adaptive chosen message attacks exist

Question 2

If one-way permutations exist

Answer 2

then signature schemes existentially unforgeable under adaptive chosen message attacks exist.

Question 3

If one-time public-key identification is possible (equivalent to existence of one-way functions)

Answer 3

then signature schemes existentially unforgeable under adaptive chosen message attacks exist.

Question 4

Trapdoor function

Answer 4

In theoretical computer science and cryptography, a trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its inverse) without special information, called the “trapdoor”. Trapdoor functions are a special case of one-way functions and are widely used in public-key cryptography.

Question 5

Pseudo-random generators

Answer 5

Definition: a function g:{0,1}* → {0,1}* is said to be a (cryptographic) pseudo-random generator if
It is polynomial time computable
It stretches the input |g(x)|>|x|

If the input (seed) is random, then the output is indistinguishable from random

Question 6

Hardcore Predicate

Answer 6

Definition: for f:{0,1}* → {0,1}* we say that h:{0,1}* → {0,1} is a hardcore predicate for f if:
h is polynomial time computable
For any probabilistic polynomial time adversary A that receives input y=f(x) and tries to compute h(x) for any polynomial p(n) and sufficiently large n

|Prob[A(y)=h(x)] - 1/2| < 1/p(n)
where the probability is over the choice x and the random coins of A

Sources of hardcoreness:
not enough information about x
not of interest for generating pseudo-randomness
enough information about x but hard to compute it

Question 7

Hardcore Predicate Layman’s definition

Answer 7

Recall that f(x) does not necessarily hide everything about x even if f is a one-way function. E.g. if f is the RSA function then it preserves the Jacobi symbol of x, and if f is the discrete logarithm function EXP then it is easy to compute the least significant bit of x from f(x) by a simple Legendre symbol calculation. Yet, it seems likely that there is at least one bit about x which is hard to “guess” from f(x), given that x in its entirety is hard to compute. The question is: can we point to specific bits of x which are hard to compute, and how hard to compute are they. The answer is encouraging. A number of results are known which give a particular bit of x which is hard to guess given f(x) for some particular f’s such as RSA and the discrete logarithm function. We will survey these results in subsequent sections.

More generally, we call a predicate about x which is impossible to compute from f(x) better than guessing it at random a hard-core predicate for f.

Question 8

Hybrid argument - show pseudo randomness

Answer 8

To prove that two distributions D and D’ are indistinguishable:
suggest a collection of distributions
D= D0, D1,… Dk =D’

If D and D’ can be distinguished, then there is a pair Di and Di+1 that can be distinguished.
Advantage ε in distinguishing between D and D’ means advantage ε/k between some Di and Di+1

Use a distinguisher for the pair Di and Di+1 to derive a contradiction

Question 9

Next-bit Test - show pseudorandomness

Answer 9

Definition: a function g:{0,1}* → {0,1}* is said to pass the next bit test if:
It is polynomial time computable
It stretches the input |g(x)|>|x|
denote by ℓ(n) the length of the output on inputs of length n
If the input (seed) is random, then the output passes the next-bit test
For any prefix 0≤ i< ℓ(n), for any probabilistic polynomial time adversary A that is a predictor: receives the first i bits of y= g(x) and tries to guess the next bit, for any polynomial p(n) and sufficiently large n

|Prob[A(y1,y2,…, yi) = yi+1] – 1/2 | < 1/p(n)

Theorem: a function g:{0,1}* → {0,1}* passes the next bit test if
and only if it is a pseudo-random generator

Question 10

Components of a Signature Scheme

Answer 10

• public and private key
• Signing algorith,, given a message m Alice can produce signature s
• anyone who is given Alice’s public key and the (message, signature) can verify it.
• all algorithms should be polynomial time

Question 11

Single bit expansion

Answer 11

-Let f:{0,1}^n → {0,1}^n be a one-way permutation
-Let h:{0,1}^n → {0,1} be a hardcore predicate for f
Consider g:{0,1}n → {0,1}n+1 where
g(x)=(f(x), h(x))

Claim: g is a pseudo-random generator
Proof: can use a distinguisher for g to guess h(x)

Question 12

Theorem Hill

Answer 12

if one-way functions exist, then pseudo-random generators exist.

Question 13

Goldreich Levin Theorem

Answer 13

It is clear that if a one-to-one function has a hard-core predicate, then it must be one way.

Oded Goldreich and Leonid Levin (1989) showed how every one-way function can be trivially modified to obtain a one-way function that has a specific hard-core predicate.[5] Let f be a one-way function. Define g(x,r) = (f(x), r) where the length of r is the same as that of x. Let xj denote the jth bit of x and rj the jth bit of r. Then

b(x,r):=dotproduct(x,r)=xor_j x_{j}r_{j}}b(x,r):=dotproduct(x,r) =xor_j x_{j}r_{j}}

is a hard core predicate of g.

Question 14

one way functions imply

Answer 14

p not equal np

Question 15

all imply both ways

Answer 15

Universal one way hash function <=>
Signature Schemes<=>
one way functions <=>
Pseudo random number generators <=>
two gaurd indentification problem

Question 16

Identification: remote login using pseudo-random sequence

Answer 16

A and B share a key Sin {0,1}^m
In order for A to identify itself to B
Generate sequence G_n(S)

For each identification session: send next block of Gn(S)

Question 17

Challenge-Response Protocol

Answer 17

B selects a random location and sends to A

A sends value at random location

Question 18

challenge response desired properties

Answer 18

Very long string - prevent repetitions

Random access to the sequence

Unpredictability - cannot guess the value at a random location
even after seeing values at many parts of the string to the adversary’s choice.
pseudo-randomness implies unpredictability
Not the other way around for blocks!

Question 19

Challenge Response Message Authenticating

Answer 19

A wants to send message Min {0,1}^n to B
B should be confident that A is indeed the sender of M

One-time application:
S =(a, b): where a, binR {0,1}^n
To authenticate M: append aM+ b to message
Computation is done in GF[2^n]

Question 20

Encryption of Messages - shared pseudo random

Answer 20

A wants to send message Min{0,1}^n to B
only B should be able to learn M

One-time application:
S = a: where a in_R {0,1}^n
To encrypt M send a xor M

Question 21

Applications of Psudeo-random Functions

Answer 21

Any setting where huge shared random string is usefull - what happens when seed is made public?

Question 22

Pseudo Random Permutations

Answer 22

Block Ciphers

-shared Key encryption schemes where:
The encryption of every plaintext block is a ciphertext of the same length

Question 23

Block Ciphers

Answer 23

Advantages
Saves up on memory and communication bandwidth
Easy to incorporate within existing systems.

Main Disadvantage
Every block is always encrypted in the same way.

Important Examples: DES, AES

Question 24

Construction of Pseudo-Random Permutations

Answer 24

Possible to construct
pseudo-random permutations
from
pseudo-random functions (and vice versa …)

Based on 4 Feistel Permutations

Question 25

Feistal Permutation

Answer 25

Any function f :{0,1}^n –> {0,1}^n defines a Feistel Permutation {0,1}^2n –> {0,1}^2n
Df(L,R)=(R, L xor f(R))

Feistel permutations are as easy to invert as to compute:
Df-1(L,R)=(R xor f(L),L)

Many Block Cipher are based on such permutations, where the function f is derived from a secret key

Question 26

Feistal permuation proccess

Answer 26

split to left (L1) and right(R1)

R2=f(R1) xor L1
L2= R1

Question 27

Feistal permuation Main Construction

Answer 27

Let F1, F2 ,F3 ,F4 in_R PRF, then the composition of DF1 , DF2 , DF3 , DF4 is a pseudo-random permutation.
Each Fi :{0,1}^n –> {0,1}^n.
Resulting Permutation {0,1}^2n –> {0,1}^2n.

F1 and F4 can be ``combinatorial”:
pair-wise independent
low probability of collision on first block