W10 - Post Quantum Crypto

Question 1

Corollary of the Cauchy-Shwartz Inequality

Answer 1

|v.u^T| <= n.|u|.|v|

Question 2

LWE

Answer 2

Given b, A
b = As + e

Question 3

Computational LWE

Answer 3

Find s’ s.t. b-As’ is short

Question 4

Decisional LWE

Answer 4

b = As+e looks the same as b<-Zmq

Question 5

Short Secret LWE

Answer 5

s is short

Question 6

Knapsack-LWE

Answer 6

A is wide
s includes error
Goal: Distinguish b and As

Question 7

LWE-based PKE

Answer 7

Enc:
r <- {0,1}^m
u = r.At
v = bt.c+μ.q/2
c = (u, v)
Dec:
0 is |v-st.u|<q/4