> _^;(
/0DTimes New Roman0:A 0DComic Sans MSn0:A 0B DWingdings MSn0:A 0C .
@n?" dd@ @@``
`Y_(U 2 50]A7%P/,,$B$$+|}~0e0e
A A> 8c8c
?1 d0u0@Ty2 NP'p<'pA)BCD|E||S"p33!33@Bʚ;F%6ʚ;g4BdBd :A 0ppp@<4!d!dL$ 0D3<4ddddL$ 0D3<4ddddL # 0U+80___PPT10
?%*Identity-Based Zero-Knowledge,
3-History: recall original ZK motivation of GMR..,Prover can interactively convince verifier that x is in L
Later, verifier can not convince someone else
This prevents off-line plagiarism (i.e. Verifier later claiming the proof as his own).
#What about on-line Adv?<Verifier can play man-in-the-middle
Handled by the designated verifier proofs
[Jackobson,Sako, Impagliazzo], others
This LIMITS the dissemination of proofs!6P&)P&)a3$What we want& lTo publish the proofs as widely as possible with the authors names
Prevent plagiarism
So, why not use NIZK?
mm%NIZK reminder [BFM]Common reference string (R.S.)
Prover sends a single message
Its transferable
Its ZK:
Can simulate the same view [BDPM]
Can simulate with the same R.S. [DDOPS]NVdJZV8&So are we done?Any verifier can take a NIZK proof, and either
change it a bit, but still keep it valid or
(The first point can be addressed with non-malleable NIZK [DDN][S][DDPOS])
claim it as his own and simply copyn[K$/#K#'Non-Malleable NIZKNon-malleability [DDN] can not constructed related encrypted msg
Non-malleability for NIZK [S][DDOPS] whatever the verifier can prove after seeing a prove, it can do without seeing the proof
Technical points:
(1) generation of CRS;
(2) 1 thm vs. many theorems;
(3) adaptivity;
(4) adv. challenges and the guarantees
So, use the strongest def, are we done?xZZZ,5\33)(*What is the def. of preventing plagiarism?++,You have an NP theorem and a witness
You want is transferable
You have your name (id) as part of it&
Want to bind the proof to your name (id) such that nobody can change the proof to a different id )ID-ZKThis talk we concentrate on NIZK (but the notion applies to interactive setting as well)
A new notion: NIZK with extractable identity:
Prover(id,x,w,CRS) proof
2 public algs:
check correctness
extract id from proof
ZK: for all x in L, and all id, can generate comp indist. View. (1 thm or multiple thms).
Sound (w.h.p. can not cheat )
Z)PzZq)y*Security of ID-ZKSound
Can not change identities
Informally: no poly-time Adv. Can take one or several ID-ZK proofs, and construct a proof for a new id of an interesting theorem
Interesting something can Adv. Could not do without any help.8d3+Security of ID-ZK (cont.)NIZK with extractable identity is ID-ZK if:
Adv asks for ID-ZK proofs of different theorems, and different id s
Adv comes up with a proof of a thm with a new id
Simulator can output comp. indist. Distribution of thms with new id without any ID-ZK proofs.
again several variants of what Adv can ask, the strongest is simulation-soundness
SdS6Remarks about the model(PK-infrastructure does it help? (i.e. what if the prover signs his proof?)
No, the adv can just get rid of the signature and substitute his own!$ZO(F(7Remarks about the model (cont.) ,NIZK with a single random string what does security mean? (since simulator must have a trapdoor info)
The point is that we can do the proof without the trapdoor if there is an adv who can cheat, the proof implies that we can use it to derive the contradiction! Zh8How easy is it to construct?,DAlso, what is the connection to NIZK in the non-interactive setting?,Why not use non-mall NIZK?,Claim 1: there exists non-malleable NIZK proofs which are not ID-ZK.
Claim2: there exists ID-ZK NIZK proofs that are not non-malleable NIZK.*CH-Why not use non-mall NIZK?,Claim 1: there exists non-malleable NIZK proofs which are not ID-ZK.
Standard non-mall NIZK do not have any ID. I can simply copy the proof and claim it as my own
Remark: [DDN] showed how with ID s non-mall NIZK is easier to build, this is different!
NdC^Y33.Why not use non-mall NIZK?,Claim2: there exists ID-ZK proofs that are not non-malleable.
Proof idea: take ID-ZK proof, where we attach the first (undetermined) bit. This is malleable, but can still be shown to be ID-ZK!">2*ID-ZK are closely related to non-mall NIZK++,Claim 3: assuming any non-mall NIZK we can construct ID-ZK NIZK.
Claim 4: assuming any ID-ZK NIZK, we can construct non-mall NIZK/*ID-ZK are closely related to non-mall NIZK++,TClaim 3: assuming any non-mall NIZK we can construct ID-ZK
given (x,w,id) we construct ID-ZK: as follows:
Define langue L (x,id): either x in L or (a new portion) of CRS is a commitment to id .
Send is ID-ZK (id, non-mall-NIZK for L ).
Intuition: if can create new id, violates non-malleability!D+d;<0*ID-ZK are closely related to non-mall NIZK++,Claim 4: assuming any ID-ZK we can construct non-mall NIZK
Proof idea: use as ID a signature public-key, i.e. id = PK.
Let B = id-zk(id,x in L)
Send (id; B; signpk(B))
Note: same proof-structure works for interactive case.dZ;n633CONCLUSIONSMany previous works (including DDN) used identities in constructions but this is the first formal definition of binding names to proofs.
Our definition is the most interesting part, seems to be a useful building block.
What about application-specific efficient implementations?
|ZyR
} ` ` ̙33` 333MMM` ff3333f` f` f` 3>?" dd@0?" dn(@ 5 d " @ ` n?" dd@ @@``PR @ ` `p>><4(
6d P
NClick to edit Master title
B
0 <$
0
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
0Й ``
>*
0
@*
H
0h ? ̙33og___PPT10G+FD
' =
@B D
' =
@BA?%,( <+O%,(
<+D ' =%(D ' =%(D' =ABBB@B0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*!%(D' =ABBB@B0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*!.%(D' =ABBB@B0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*.:%(D' =ABBB@B0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*:G%(D' =ABBB@B0B%())))?D' =1:Bvisible*o3>+B#style.visibility<*GS%(+8+0+ + Default Design P8(
P
P
0P* P
>*
P
0
@*
P
6(1 `P
>*
P
6p5 `
@*H
P0h ? ̙3380___PPT10.2i5-0t(
tr
t Sp
E
t
N>?"
wJonathan Katz Rafail Ostrovsky Michael Rabin
U. Maryland U.C.L.A. Harvard U.&xn9?
t
Z>?"@H
.n H
t0h ? ̙33y___PPT10Y+D=' =
@B +y
80(
8x
8 c$P
x
8 c$
H
80h ? ̙33y___PPT10Y+D=' =
@B +}
$(
r
S1P
r
S2
H
0h ? ̙33___PPT10i.4A+D=' =
@B +}
$(
r
S;P
r
S<
H
0h ? ̙33___PPT10i.R+D=' =
@B +}
$(
r
SAP
r
SxB
H
0h ? ̙33___PPT10i.(R+D=' =
@B +}
$(
r
SOP
r
SHؐ
H
0h ? ̙33___PPT10i.+D=' =
@B +}
$(
r
Sp[P
r
S0\
H
0h ? ̙33___PPT10i.0a+D=' =
@B +}
$(
r
ShP
r
S|k
H
0h ? ̙33___PPT10i.+D=' =
@B +}
$(
r
SrP
r
SPu
H
0h ? ̙33___PPT10i. E|+D=' =
@B +}
0$(
r
S耓P
r
S
H
0h ? ̙33___PPT10i.3k+D=' =
@B +}
@$(
r
SP
r
Sp
H
0h ? ̙33___PPT10i.+D=' =
@B +
T0(
Tx
T c$P
x
T c$
H
T0h ? ̙33___PPT10i.\Z+D=' =
@B +
X0(
Xx
X c$4P
x
X c$
H
X0h ? ̙33___PPT10i.\Z+D=' =
@B +}0 \$(
\r
\ S>
r
\ S `
H
\0h ? ̙33___PPT10i.]`\@+D=' =
@B +}
P$(
r
SēP
r
SXœ
H
0h ? ̙33___PPT10i.P#Y+D=' =
@B +
p0(
x
c$͓P
x
c$Γ
H
0h ? ̙33___PPT10i.P#Y+D=' =
@B +
0(
x
c$ݓP
x
c$Tޓ
H
0h ? ̙33___PPT10i.P#Y+D=' =
@B +
40(
4x
4 c$4P
x
4 c$
H
40h ? ̙33___PPT10i.+D=' =
@B +}
$$(
$r
$ SP
r
$ S
H
$0h ? ̙33___PPT10i.+D=' =
@B +
,0(
,x
, c$ P
x
, c$
H
,0h ? ̙33___PPT10i.+D=' =
@B +}
8$(
8r
8 SP
r
8 STPp
H
80h ? ̙33___PPT10i.߄@+D=' =
@B +r| ;^O~S#Z\_a)df3ik=nixz}&2 W60pSsum<8Oh+'0H`h|
ID-BASED ZKRafail OstrovskyeRafail Ostrovskye1098l OMicrosoft PowerPointP@aqJ@@0C~_7G.g d--@ !--'@Times New Roman-. 2
1."System-@BComic Sans MS-. 2
*Identity!$" ".-@BComic Sans MS-. 2
*-%.-@BComic Sans MS-. 2
**Basedi&""$.-@BComic Sans MS-.
2
sZero*" .-@BComic Sans MS-. 2
s-%.-@BComic Sans MS-. 2
s Knowledge% *"$!".-@BComic Sans MS-. [2
R8Jonathan Katz Rafail Ostrovsky Michael Rabin
.-@BComic Sans MS-. d2
7c>U. Maryland U.C.L.A. Harvard U.
.-՜.+,0P
On-screen ShowUCLAreec{
Times New RomanComic Sans MS
WingdingsDefault DesignIdentity-Based Zero-Knowledge.History: recall original ZK motivation of GMRWhat about on-line Adv?What we wantNIZK reminder [BFM]So are we done?Non-Malleable NIZK+What is the def. of preventing plagiarism?ID-ZKSecurity of ID-ZKSecurity of ID-ZK (cont.)Remarks about the model Remarks about the model (cont.)How easy is it to construct?Why not use non-mall NIZK?Why not use non-mall NIZK?Why not use non-mall NIZK?+ID-ZK are closely related to non-mall NIZK+ID-ZK are closely related to non-mall NIZK+ID-ZK are closely related to non-mall NIZKCONCLUSIONSFonts UsedDesign Template
Slide Titles(_Rafail OstrovskyRafail Ostrovsky
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEGHIJKLMOPQRSTUWXYZ[\]`Root EntrydO)Current UserVSummaryInformation(FPowerPoint Document(DocumentSummaryInformation8N