TAMC 筆記

week 3

Hardness Amplification(Concrete ver.)

By reduction, suppose

fk is not
(t,ϵ)OW
. That is
Advfk
break
(t,ϵ)OW
for
fk
. Construct R to break
(t,ϵ)OW
for
f
.

Reduction

i[k], let
yi=y,xi{0,1}n(k1)
, let
yi=f(xi)
. Compute
x=Advfk(y)
for
2knγ
times for each
i
. If
Advfk
wins, or
fk(x)=y
, then
R(y)=x
and
R
wins.

Obs

for

i[k],
x{0,1}n,yi=f(x)
.
If
For x,Pr[Advfk(yi,yi) wins]γ2k

Pr[Advfk fails in all 2knγ tries]en

Define a good set

Define good set

Gi{0,1}n as:
Gi{x{0,1}n|Pr[Advfk(yi,yi) wins]γ2k}

xGiR can win w.h.p. 1en

(w.h.p.=with high probability)
WTS
i[k]
s.t.
Gi
is large enough.

Claim

i[k] s.t. for x,
Pr[xGi](1+δ)ϵ
. Then
Pr[R wins]Pr[R winsxGi]=Pr[R wins|xGi]Pr[xGi]>(1en)(1+δ)ϵ>ϵ

Proof of Claim:

Suppose not.

i[k],
Pr[xGi]<(1+δ)ϵ

we show
Pr[Advfk wins]<ϵ=[(1+δ)ϵ]k+γ

Pr[Advfk wins]=Pr[Advfk wins(i,xiGi)]+Pr[Advfk wins(i,xiGi)]<[(1+δ)ϵ]k+γ2

Computation time of
R
:

  • Call
    Advfk
    2k2nγ
    times
    O(2k2nγt)
    time.
  • Call
    f(x)
    to validate the answer:
    O(2k3nγ)
    times
    2k2nγt+2k3nγ×tf<t

    t=O(γk3nt)
    provided that
    tktf
    , where
    tf
    is the computation time of
    f
    .

Computational Indistinguishability and Pseudorandomness

Some distributions:

  • uniform dist.
    Un
    :
    Pr[Un=x]=2nx
  • random image. for some
    f:{0,1}n{0,1}m
    ,
    f(Un)
  • uniform over
    S
    :
    US

    Pr[US=x]={1/|S|xS0otherwise

Definition of comp. indist. (Concrete ver.)

X,Y dist. over
{0,1}n
is
(t,ϵ)
-comp. indist. if
PPT distinguisher
D
running in
t
,
|Pr[xX:D(x)=1]Pr[yY:D(y)=1]|ϵ

denoted as
Xt,ϵY

Definition of Pseudorandom (Concrete ver.)

X dist. over
{0,1}n
is
(t,ϵ)
-pseudorandom if
Xt,ϵUn

Fun fact

S{0,1}n,
|S|=20.1n
. s.t.
US
is
(nlogn,nlogn)
-pseudorandom.

Definition of comp. indist.

Xn,Yn is comp. indist. if
PPT distinguisher
D
,
neglν
s.t.
suff. large n,
|Pr[xX:D(x)=1]Pr[yY:D(y)=1]|ν(n)

denoted as
{Xn}c{Yn}

Definition of Pseudorandom Generator(PRG)

Gn:{0,1}n{0,1}m(n) is PRG if

  • Efficiency:
    G
    can be computed efficiently
  • Expansion:
    m(n)>n
  • Pseudorandom:
    {Gn(Un)}nc{Um(n)}n

week 4

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

week 6

oracle

An oracle

O is a (potentially randomized) “black-box” function
{On:{0,1}n{0,1}m(n)}nN
that can be queried by an algorithm. Specifically, on input query x, the oracle
O
returns
y=O(x)
.

Oracle algorithm

An oracle algorithm

AO is an algorithm that is given oracle access to an oracle
O
. Namely,
A
can make an arbitrary number of oracle queries
x
to
O
and receive answers
y=O(x)
during its computation.

keyed function

f:{0,1}l(n)×{0,1}n{0,1}n
fk(x)=f(k,x)

PRF(Pseudorandom Function)

A keyed function

f:{0,1}l(n)×{0,1}n{0,1}n is PRF if for a fixed
k
, f(k,x) is pseudorandom
(not possible because there are exponential
k
's, even only checking all
f(k,x)
in linear time will cost exponential time).
The correct definition:
|Pr[k{0,1}l(n):Dfk(1n)=1]Pr[HRFn:DH(1n)=1]|μ(n)

RFn
is the uniform distribution of uniformly random functions that maps n-bit strings to n-bit strings.
In the form of a game:

  • Ch samples
    b{0,1}
    • if
      b=0, fRFn
      .
    • if
      b=1, kUl(n), f=fk
  • Adv can query polynomial times of f(x).
  • If Adv returns
    b=b
    , then Adv wins.

thm: PRG implies PRF

GGM's construction

GGM(Goldreich-Goldwasser-Micali) is a way to construct PRF
Let PRG

G:{0,1}n{0,1}2n,
G(x)=G0(x)|G1(x)
.
Input:
x{0,1}n
, sample
kUn
, and output
fk(x)=Gxn1Gx0(k)

Hybrid argument

GOAL: show that

G(Un(0))||G(Un(t)) and
Un(0)||Un(t)
are indistinguishable.
Define
Hybi:

  • if
    1i<t
    ,
    k1,,kiU2n
    , and
    ki+1,,ktUn
    . Output
    (k1,,ki,G(ki+1),,G(kt))
  • Define
    Hyb0=G(Un(0))||G(Un(t)
  • Define
    Hybt=Un(0)||Un(t)

Let

Pi=Pr[D(Hybi)=1]
Suppose for contradiction that
|P0Pt|>1nc
, where
1nc
is non-negligible.
By triangle inequality,
|P0Pt|=|P0P1+P1P2++Pt1Pt||P0P1|++|Pt1Pt|

By averaging argument, there exists an
0it1
such that
|PiPi+1|>1nct
. This breaks the assumption that
G
is a PRG.
Note: t mustn't be exponential of n, otherwise
1nct
is negligible.

GGM analysis

Hint: construct a polynomial number of Hybrids.
Observation: GGM is a binary tree with height

n, so there are
2n
leaf nodes of n-bits string.

  • First attempt:
    Hybi
    means the i's leaf nodes are replaced with
    Un
    . This won't work because there is an exponential number of Hybrids.

Correct attempt:
Hybi
means:

  • g:{0,1}i{0,1}n,y{0,1}i,g(y)Un
  • if
    i=0
    , normal GGM.
    kUn
    ,
    f(x)=Gxn1Gx0(k).
  • if
    0<i<n
    ,
    f(x)=Gxn1Gxi(g(xi1x0))
  • if
    i=n
    , f(x)=g(x)

Equivalent to replacing the i-th layer of the tree to be all independent

Un. Upper layers(0~i-1) don't matter.

Construct a reduction

  • Ch samples
    b{0,1}
    • if
      b=0
      ,
      i[t],kiUn,si=G(ki)
    • if
      b=1
      ,
      i[t],siUn
  • R:
    • si0=si[1:n/2],si1=si[n/2+1:n]
    • For each

week 7

PKE(Public key encryption)

PKE=(KeyGen,Enc,Dec)

Alice Bob
(pk,sk)Gen(1n)
pk->
ct=Encpk(m)
m'=Dec{sk}(ct) <-ck

ct:cipher text,

ctCn
The channel(pk,ct) may be public(everyone can access it), but assumed to be authenticated(no one can modify content).
Enc
may have randomness:
Encpk(m;r)

Dec
is deterministic, outputting m or
(invalid)

Property: Correctness

μ=negl(n),s.t.nN,mMn
Pr[(pk,sk)Gen(1n),Decsk(Encpk(m))=m]1μ(n)

Different security definition

OW-CPA

CPA: Chosen-Plaintext Attack

Ch Adv
(pk,sk)Gen(1n)
mMn
ct=Encpk(m)
pk,ct->
m=Adv(pk,ct)
Adv wins if
m=m
<-m'

Secure if

 negl μ,s.t.nN,Pr[Adv wins]μ(n)+1|Mn|

Problem

保證的是不能還原全部訊息,但如果被還原部分訊息還是很危險。

IND-CPA

Ch Adv
(pk,sk)Gen(1n)
pk->
b{0,1}
<-
m0,m1Mn
ct=Encpk(mb)
ct->
Adv
wins if
b=b
<-b'

Secure if

 negl μ,s.t.PPTAdv,nN,Pr[Adv wins]12+μ(n)

Problem

Some other people (Eve) may ask Alice what

m corresponds to a cipher text
ct
. And find some patterns in its reaction.

IND-CCA

CCA: Chosen-Ciphertext Attack

Ch Adv
(pk,sk)Gen(1n)
pk->
<-
cti
(Multiple times)
mi=Decsk(cti)
->
b{0,1}
<-
m0,m1Mn
ct=Encpk(mb)
ct->
<-
cti
(Multiple times)
mi=Decsk(cti)
->
Adv
wins if
b=b
<-b'

先試很多次再收問題,然後可以再試很多次。
Secure定義和IND-CPA一樣
限制

ctict
等價定義:Adv given access to an oracle
O(ct)=Decsk(ct)

Assumptions

  • Group-based: 量子電腦可破解
  • Lattice-based: 後量子都可以用

Group-based Assumption

cyclic group:

(G,q,g), which includes ${id,g,g2,g3,\ldots,g^{q-1}}
Ex:
Zp={1,g,g2,,gp2}
, where
p
is a prime.
不care group的細節,但大概會是從elliptic curve group來
Suppose some efficient operations:
gh,ggt,g1

Hard operation problems:

  • ex: discrete log
    • input:
      h=gx
    • output:
      x

DL assumption for
(G,q,g)

Ch Adv
xZq
h=gx
->
Adv wins if
x=x
<-x'

PPT Adv,negl μ,s.t.n,Pr[Adv wins]μ(n)

某些prime簡單,某些prime難

最弱的assumption,要造PKE需要更強的assumption

DDH assumption for
(G,q,g)

DDH: decisional Diffie–Hellman problem

  • sample
    x,y,zZq
  • (g,gx,gy,gxy)c(g,gx,gy,gz)

Can distinguish

gxy and
gz
given
g,gx,gy
.
Game就不寫了
滿好用的,可以造PKE

Search version:CDH(computational Diffie–
Hellman)
Given

g,gx,gy, compute
gxy
.

PKE from DDH for
(G,q,g)

El Gamal PKE=

(Gen,Enc,Dec)

  • Gen(1n)(pk,sk)
    • sample
      sZq
    • output
      sk=s,pk=gs
      (sk is hidden from pk)
  • Encpk(m)ct
    ,
    Mn=G
    • sample
      rZq
    • ct=(gr,pkrm) (=(gr,gsrm))
  • Decsk(ct)
    :
    • input
      ct=(u,v)
    • output
      vusk

Correctness:

ct=(gr,gsrm)
vusk=(gsrm)(gr)s=m

Thm: Assume DDH, El Gamel PKE is IND-CPA-secure

Suppose not,

PPT Adv breaks IND-CPA-secure. That is,
ϵ(n)=1poly(n)
, such that

Ch Adv
(s,gs)Gen(1n)
pk=gs
->
m1G(=Mn)
<-
m0
b{0,1}
ct=Encpk(mb)
ct=(gr,gsrm)
->
Adv wins if
b=b
<-
b

Pr[Adv wins]12+ϵ(n)
Claim: 給Adv選
m0,m1
和只給他選
m0
m1
隨機選是等價的

Construct a reduction R to break DDH

Ch R Adv
x,y,zZq
b{0,1}
w0=gxy,w1=gz
(g,gx,gy,wb)
->
pk=gx
->
<-
m0
ct=(gy,wbm0)
->
<-
b
<-
b

week 9

Lattice-based Assumption

Learning with error(LWE) problem

Let

nN be the security parameter,
q(n)
be a modulus(poly or
nω(1)
),
m(n)>Ω(nlogn)
and
χ
be an error probability distrubution over
Zq
(usually discrete Gaussian distribution).

A sample from LWE distribution

LWEn,m,q,χZqm×n×Zqm is generated by:

  • AZqm×n
  • sχnZqn
    (直接從
    Zqn
    也可以)
  • eχmZqm

Output

(A,b=As+e)

χ
over discrete Gaussian distribution

胖度

αq: discrete Gaussian distribution 中間高起來的寬度(幾標準差)
qαq>2n

LWE assumption

  • AZqm×n
  • uZqm

(A,b)c(A,u)

comment

If

b=As, we can easily distinguish them by trying to solve s.
s
is
n
-dimensional and we map to
b
, so
b
is also
n
-dimensional.
u
is
m
-dimensional, so it's unlikely to be solved.
直覺:
χ
越胖越難解

SKE from LWE

會比較簡單一點

SKE=(Gen,Enc,Dec)

  • Gen(1n)
    • Output
      sk=sχqn
  • Encsk(m)
    ,
    m{0,1}
    • Sample
      aZqn
      ,
      eχ
    • Let
      b=as+e
    • Output
      ct=(a,b+mq2)
  • Decsk(ct)
    ,
    ct=(u,v)
    • Let
      z=vusk
    • Output
      {0, if z[q4,q4]1, otherwise

Correctness

z=vusk=(b+mq2)as=mq2+e
因此不會與
m
差太多

Regev's PKE

PKE=(Gen,Enc,Dec)

  • Gen(1n)
    ,
    q=q(n),m=m(n),χ=Ψα(n)
    • Sample
      AZqm×n
    • Sample
      sχn,eχm
    • Let
      pk=(A,b=As+e),sk=s
  • Encpk(m)
    ,
    m{0,1}
    • Sample
      r{0,1}m
      ,
      eχ
    • Output
      ct=(rTA,(rTb)+mq2)
  • Decsk(ct)
    ,
    ct=(u,v)
    • Let
      z=vusk
    • Output
      {0, if z[q4,q4]1, otherwise

Correctness

ct=(rTA,(rTb)+mq2)
z=vusk=(rTb+mq2)rTAs=(rTAs+rTe+mq2)rTAs=rTe+mq2mq2

Thm: Regev's PKE is IND-CPA secure

Suppose not,

PPT Adv breaks IND-CPA-secure. That is,
ϵ(n)=1poly(n)
, such that

Ch Adv
(pk,sk)Gen(1n)
pk=(A,b)
->
B{0,1}
<-
m0=0,m1=1
ct=Encpk(mB)
ct
->
Adv wins iff
B=B
<-
B

Pr[Adv wins]12+ϵ(n)

Adversary's view

Adv is given
(A,b,m0,m1,rTA,(rTb)+mBq2)

Hybrid argument Step 1

Think of LWE assumption, change the public key given to Adv from

(A,b) to
(A,u)
, where
uZqm
.
Claim:
(A,b,m0,m1,rTA,(rTb)+mBq2)
c(A,u,m0,m1,rTA,(rTu)+mBq2)

So given
(A,u)
,
Adv
can also win with a non-negligible advantage.

Hybrid argument Step 2

Claim:

rTA and
rTu
are pseudorandom.
(A,u,m0,m1,rTA,(rTu)+mBq2)
s(A,u,m0,m1,u1,u2)

where
u1Zqn,u2Zq
.
Given the cipher text is random,
Adv
can also solve the message. Impossible!

Leftover hash lemma

Let

AZqm×n,
ϵ>0
,
r{0,1}m
,
uZqn

where
mnlogq+2log1ϵ+O(1)

Then
Δ((A,rTA,),(A,u))ϵ

For the Hybrid argument Step 2

[rT][Au]=[u1Tu2]
Increase
n
by 1, the result still holds.

Problem

The public key includes a

A:m×n matrix, which may be too expensive.
It can be solved by Ring LWE instead of Module LWE.

week 10 FO transformation

El Gamel's and Regev's PKE are not IND-CCA-secure.
Assuming RO(Random oracle), given an OW-CPA/IND-CPA-secure PKE, we can transform it into an IND-CCA-secure PKE. Practically, we will simulate the RO with a hash function. For post-quantum security, we need quantum RO.

INDCPAT TransOWCCAU TransINDCCA(KEM)
KEM:可以想像成先用PKE產生一個雙方都知道的random key,然後用SKE。

RO Model

RO: a deterministic random function, for each input the output is uniformly random. Deterministic means the same input will always lead to the same output.
所有人都共用一個RO

Lazy Sampling

As in GGM. Initialize an empty table. For each query, output the entry if there is, otherwise sample one and return it.

RO Heuristic

OW-CCA

和OW-CPA很像,但加上adversary可以query

Decsk(ct),但
ctct

更強的版本: 可以call
G(m)
(Enc的隨機性來源)

T Transform

For an IND-CPA PKE

(Gen,Enc,Dec), with a random oracle, we can construct an OW-CCA PKE
(Gen,Enc,Dec)
.

  • Gen=Gen
  • Encpk(m)=Encpk(m;G(m))
  • Let
    m=Decsk(ct)
    • If
      m≠⊥
      and
      Encpk(m;G(m))=ct
      , return
      ct
      . (the )
    • Otherwise

Note that the T transform outputs a deterministic PKE.

reduction

R用Adv(breaks OW-CCA) break IND-CPA:

  • How to decide
    m0,m1
    ?

    Because R has no information,
    m0,m1M
  • R has no access to RO but needs to simulate RO
    By lazy sampling
  • How does R decide answer?
    If Adv wins,
    m=m0/m1
    , so output
    0/1
    (II)
    else output a random bit. (III)
  • What if Adv queries
    m0
    or
    m1
    ?

    Since R doesn't know
    b
    or the
    r
    that Ch uses, it cannot just randomly sample the answer, otherwise, the distribution is wrong(G(m_b) for Ch is not the same as for Adv).
    If get
    m0/m1
    , output
    0/1
    . See it as the Adv finds the answer and ensures it's true. (I)

For the

U Transform

week 11 Digital Signature

Signature

避免攻擊者傳送偽造或變造的訊息給接收者

Definition

digital signature scheme=

(Gen,Sign,Vrfy) Vrfy=Verify

Signer Verifier
(pk,sk)Gen(1n)
pk->
σSign(sk,m)
σ,m
->
0/1=Vrfy(pk,m,σ)

Completeness:

m, Pr[Vrfy(pk,m,Sign(sk,m))=1]=1negl(n)

EUF-CMA Secure

Adv 給定

pk,可以 query Ch 很多次
mi
,並得到對應的
σi
,最後若能給出一對
m,σ
使得
Vrfy(pk,σ,m)=1
m
沒有出現過,則 Adv 成功偽造(Forge)了一個簽章。這個機率要是negligible(
σ
的 space 很大)

DL assumption to Schnorr Signature Scheme

DL(discrete log) assumption

Schnorr signature scheme(in ROM) is group-based:

Signer Verifier
sZq,pk=gs
(G,g,pk)
->
kZq
σ=(gk,H(gk,m),ksc)
σ,m
->
check if
c=H(gk,m)
&
gz=gkpkc

直覺會覺得要破Schnorr無論如何都需要破discrete log
證明需要許多步驟:

Sigma Protocol

NP relation

An NP relation is a binary relation

RX×Y. Elements of X are called statements. If
(x,y)R
, y is called a witness for x.

Example:

  1. The three coloring problem. X=graph, Y=coloring,則 R 就是 (graph,對應的合法塗色方式) 的集合。
  2. Discrete log problem.
    R={(x,y)|x=(g,gs),y=s}
    is a NP-relation.

Prover想證明對於某個問題的某個x,他有答案y,但不想把答案透漏給Verifier,因此:

Prover Verifier
Commit(Com) ->
<- Challenge(Ch)
Response(Resp) ->
0/1=Vrfy(x,Com,Ch,Resp)

當y真的是答案(is a witness for x)

(x,y)R,V永遠輸出1:
Pr[P(x,y),V(x)=1]1negl(n)

角括號代表兩者互動過程中V的輸出

Special Soundness

一個(P,V)有special soundness,如果有一個PPT algorithm Ext(a witness extractor) such that 若input為 x,與對應的任兩個相異(

ChCh)互動過程
(Com,Ch,Resp),(Com,Ch,Resp)
,Ext可以輸出正確的y,即
(x,y)R

Note: 但是要有同樣的
Com

Honest Verifier Zero Knowledge(HVZK)

一個(P,V)是HVZK,如果有一個PPT algorithm Sim,input x,輸出

(Com,Ch,Resp)的分布與
(P,V)
互動過程一樣。
Ex: DL problem:
(r,c,z)
當中,原本
r=gk
c
是 uniformly random,而
z=ksc
是兩者 deterministically 決定。但其實
(c,z)
的 marginal probability 也是 uniform 的,所以我們可以先 sample
(c,z)
再算出
r

已知
g,gs
,所以
r=gk=gz+sc=gz(gs)c

且輸出的 distribution 與原本的相同(都是 uniform)

HVZK 的意思是在 verifier 是誠實(c 確實是 random)的情況下,會是 zero knowledge。

Note: 有 Simulator 也不能 forge signature,因為 Verifier 問的 Ch 幾乎不會是 Simulator 生出來的。

DL Assumption to DL Relation is Avg-Hard

week 12 Lattice Signature

Digital Signature conti.

Sigma protocol for average hard NP relation to ID scheme security

Reduction by rewinding
Suppose

Adv breaks ID scheme security with advantage
1nc
, we can construct a reduction
R
that breaks the average hard NP relation.
如果能夠用同樣的 commit 叫
Adv
兩次,就能用 special soundness 的 Ext 來找出 witness。
所以需要 rewinding,因為
Adv
是一個 PPT algorithm,假設它由兩部分組成,且隨機性是給定的,因此變成 deterministic:
P1(x;r)=x,r,Com

P2(x,Ch;r)=Resp

用 good

(x,r):
Pr[Adv wins|input (x,r)]12nc

Pr[good (x,r)]12nc

Fiat-Shamir transformation in ROM

Given RO

H, we can construct a Signature scheme from an ID scheme. In other words, suppose there's an
Adv
that breaks the EUF-CMA of the transformed signature scheme(acts as a Prover), we can construct a reduction
R
that breaks the ID scheme.
Adv
is given access to a RO
H
and a signature oracle
Signsk
,
R
simulate them by:

  • RO: lazy sampling
  • Signsk
    : use
    Transsk
    oracle.

The key problem is that we need to answer to an interactive transcript but the

Adv can only generate a fixed transcript. So, a trivial solution doesn't work, and we have to generate a
Com
earlier.

The method is similar to that of FO transformation. Since

Adv wins if
ch=H(Com,m)
, it very likely needs to query
H
for the the
ch
. So
R
sends one
com
(
i[qH]
) from the queries of the
H
and set the result to be
ch
from
Ch
.

Lattice-based Signature

SIS(Short Integer Solution) assumption

Ch Adv
$A\overset{$}\gets \mathbb{Z}_q^{n\times m}$
A
->
wins iff
Av=0modq
<-
vZqm

Additional requirements:

  • trivially,
    v0
  • v
    很短,
    v2β

This can be reduced to Lattice problems that are proven to be NP-hard.

n is the security parameter,
m
should be sufficiently large(so that there's a solution),
q
is a modulus(suff. large),
β
is the shortness parameter.
q>βpoly(n)

不只找到

Av=0 是 hard,找到隨便一個
Av=t
也是 hard。
Informal notes:
Prover works in plaintext space, Verifier works in the ciphertext space.

Compare to Schnorr signature scheme(sigma protocol, based on DL assumption)

(use non-homogeneous SIS)

  • Hide
    sk
    and send
    pk
    • DL hides
      s
      in
      pk=gs
      .
    • SIS hides
      s
      (short) in
      t=As
      .
  • Sigma protocal
    (com,ch,resp)
    • DL:
      kZq
      ,
      com=r=gk
      ->
      <-
      ch=cZq

      resp=z=ksc
      ->
    • SIS:
      kDσm
      ,
      com=Ak
      ->(discrete Gaussian)
      <-
      c=[d,,d]

      resp=z=kcs
      ->
      accept iff
      Az=rc(As)
      and
      z
      is short

However, the SIS Sigma protocol is not a sigma protocol (no special soundness, no HVZK). So, we need to make a version with abort and achieve a type 1 ID scheme.

ID scheme from SIS

(Gen,P1,P2,V)

  • Gen(1n)
    • $A\overset{$}\gets\mathbb{Z}_q^{n\times m}$
    • s[d,,d]m
    • pk=(A,t=As),sk=(A,s)
  • P
    and
    V
    : as in the comparison part

Reduction:
Use a similar special soundness argument.
Suppose a

Adv breaks the ID scheme, we can construct a reduction
R
that breaks the SIS assumption.
R
samples a
s
by himself and send
t=As
.
Adv
similarly supports rewinding. So
R
queries for a same
com=r
and get
(c1,z1),(c2,z2)
, such that
Az1=rtc1
and
Az2=rtc2
.
Therefore,
R
can get a
v
by:
A(z1z2)=t(c1c2)=As(c1c2)A(z1z2+s(c1c2))=0

So
R
can simply outputs
v=z1z2+s(c1c2)
.
A problem is that
v
may not be short and
v
maybe 0.(ignore this)
Another problem is that multiple
s
may correspond to the same
t
. Somehow this can be solved.

HVZK

Simulate 出來的

(com,ch,resp)=(r,c,z) 要 hide
k
,否則無法在不知道
k
的情況下 simulate 出來。
但 SIS-based
z=ksc
中,
k
是 mean 0 的 discrete Gaussian,所以
z
相當於被平移
sc
,所以
z
可能包含一些
k
的資訊。
解決的關鍵:with abort version。

week 13 Zero Knowledge

Σ-protocal for
RDL
(honest verifier)

  • Prover has
    (s,gs)
    , Verifier has
    (G,g,gs)
  • Prover samples
    kZq
  • Prover sends
    r=gk
  • Verifier sends
    cZq
  • Prover sends
    z=ksc
  • Verifier checks if
    gz=r(gs)c

For some dishonest verifier, it may get

k from
r=gk
, and sends
c=k
. Therefore it can know
s
from
z
. 這個互動過程就無法 simulate,因為
k
決定後,
z
就會被
s
決定,但
Sim
不知道
s

definition of ZK

A interactive protocal

(P,V) for a NP relation R is ZK if
(x,y)R
,
PPT V,Sims.t.
the interaction of
(P,V)
and the output of
Sim
is computationally indistinguishable(or statistically indistinguishable).
可以互動很多次

NP language

For an NP language L,

polynomial time
V
s.t.
xL,
witness
w
s.t.
V(x,w)=1
. And
xL,
witness
w
V(x,w)=0
.

example 3 coloring

LG3C={G=(V,E)|G is 3 colorable}
LNP
, witness is a map
ϕ:V1,2,3

ZK for NP language L

互動多次

P(w),V(x)

  • Completeness:
    xL
    and a valid witness
    w
    ,
    Pr[P(w),V(x)=accept]1negl(|x|)
  • ϵ
    -soundness: 壞人 prover 不能說服 verifier。
    malicious
    P
    ,
    Pr[P,V(x)=accept]ϵ(|x|)
    • If only for PPT
      P
      , comp. soundness
    • If for unbounded
      P
      , stat. soundness
  • ZK:
    malicious
    V
    ,
    Sim
    s.t.
    V
    's view from
    P(w),V(x)Sim(x)
    • V
      必須是 PPT,不然自己就知道 witness,
      Sim
      也是一樣的道理
    • 但兩個分布不可區分可以是 comp. 或 stat.

commitment scheme

Com=(C,R), committer(sender) and receiver
直覺理解: committer 傳送放在箱子裡的 m,receiver 不能打開,但在驗證階段(reveil phase),committer 把鑰匙給 receiver,receiver 可以驗證當初傳的確實是 m。

  • Binding: 不同的 m 對應到不同箱子
  • Hiding: 只看到箱子不知道裡面裝什麼

正式定義:

  • Commit phase: C sends c to R(with decommitment d, maybe random tape),可以很多次
  • Reveil phase: C sends m,d to R, open(m,c,d)=acc/rej
  • Binding:
    adversary as malicious C, it wins iff
    open(m0,c,d0)=open(m1,c,d1)
    =accept.
    Pr[it wins]
    is negligible.
  • Hiding(IND-based): 對於任何兩個 messages
    m0,m1
    ,
    R
    view(C(m0),R)cview(C(m1),R)

一樣 binding, hiding 都有可能是 PPT 或 unbounded。但是不能兩個都 unbounded(left as exercise)

A construction from OWP

For a OWP

f with its hardcore predicate
h
, we can construct a commitment scheme for 1 bit.
Com(b),b{0,1}

  • sample
    r{0,1}n
  • output
    c=(f(r),h(r)b)
    , keep
    d=r

open(b,c,d)

  • acc iff
    c=(f(d),h(d)b)

這會是 stat.(perfect) binding,因為一個 adversary 想找出

(c0=0,d0),(c1=1,d1),但是
d=r
決定後,
f(r)
h(r)
都決定。
comp. binding,因為如果能區分
c0,c1
會 break HC,而 unbounded adversary 可以直接算出
r
再算
h(r)

ZK protocol for
LG3C

Related material

用一個上面的 commitment scheme

P(G,ϕ)

  • πS3
    , 三種顏色隨機的排序
  • ψ=π(ϕ)
  • vV,(cv,dv)Com(ϕv)
  • sends
    Com(ϕ)

V(G)

  • eE
  • sends
    e=(u,v)
  • gets
    ψu,du,ψv,dv
  • accept iff
    open(ψu,cu,du)open(ψv,cv,dv)ψuψv

Security

  • Completeness: yes
  • Soundness:
    (11|E|)
    -soundness
  • ZK
    V
    的 view 是
    (G,com(ψ),V(com(ψ))=e=(u,v),ψu,du,ψv,dv)

    對於一個圖
    G
    Sim
    隨便找一個邊亂塗不同顏色,其他點甚至可以都塗一樣的顏色,造出
    ψ
    ,期待 verifier 剛好問到那條邊。如果不是的話,就 rewind 多試幾次。
    直覺想為何 comp. indis.:
    com(ψ)
    如果與真正沒亂塗的 commitment 可分辨會 break commitment scheme 的 hiding。
    ψu,du,ψv,dv
    是真的從 commitment 來的,所以好像也沒問題。

Hybrid argument: 從有 witness 的

Hybreal 到沒有 witness 的
Sim

  • Hybreal
    : 原本的定義
  • Hyb1
    : 指定一條邊
    e
    ,若
    ee
    就 rewind。
    因為邊
    e
    還是隨機的,所以 view 的分布一模一樣。
  • Hyb2
    : 把
    ψ
    改得與
    ψ
    近一點。與 real 一樣
    ψ=π(ϕ)
    ,
    ψu=ψu,ψv=ψv
    ,但
    ψw
    隨便塗一個顏色(1)。
    view 裡的
    ψ
    都改成奇怪的
    ψ
    ,所以被改掉的只有
    com(ψ)
    ,裡面被改掉了很多點的 color。偷懶的講法:
    Hyb1
    Hyb2
    中間可以再有很多 hybrids,慢慢把
    ψw
    改掉。如果能 break 的話就會 break commitment scheme 的 hiding。

week 14 Fully Homomorphic Encryption