> `! o/.A.[H3#0=U
u_WZ<xڅTLU~&(C)Hُu5
R&5fђ0@Zm[H݁SԖIsYT*r!#i9/nsyWA!! c ?cf0CERmzixr6?a8QDa$&訊Fa$}^#u#3¡:0nqQOuV*q1c=t;#&?0lSNMyҽut>ʲAβ<Ӗ+o;/KFN^63UDQG'tԫ[h9JZTtU?b=hZӃLsXe3&{o:6{x+»m;f$Zjs6{>Ŷe]Igmw"\fSqV;{%Jcs3LIw^o0Ϳ;^*ɼf:
[aNV~::ݪ~y>ądU5_hЗ1;ymJ{첥_KrJ遧d UVUJ=/ՇW#*_NGSu&^됭~wy=>8$p@y*dJQ]_q6w6 s
np(vw҅KE)[G*o/y2OvF8lS4HfEBoeM :([˛ve1s'MT*$Ə㠫LU
Joi2XG)L9L!F%tRxw%eI6jNj4%+Z6+\OM{ZM#f,bYNwT7}_9I'Jΐq:_&Ry7/OJ۫}\;9f3迹\ϔY)w6ouG~p;W i04\
Order problemTheorem: In a WPFG, finding the order of a randomly chosen element is hard.
Proof: The equation ae = 1does not hold for any e in FA(a). No element other than 1 in a free group has finite order. C'=,x ?`Discrete logarithm problemTheorem: In a WPFG, DLP is hard.
Proof: The equation ae = bdoes not hold for any e in FA(a,b); a and b are distinct independent generators, one can not be power of other.'
C,M S_$Subgroups of PFG s
Subgroup Theorem for WPFG s: If G is a WPFG, and g is chosen at random from G, then <g> is a WPFG. [not in paper]
Proof sketch: Ability to find nontrivial identities in <g> can be shown to imply that g has finite order.
==> DLP is hard in WPFG even if we enforce promise that b is a (random) power of a .
Similar proof implies that QRn is WPFG when n = (2p +1)(2q +1).
PZ
,M
,D$XEquations in GroupsLet x, y, & denote variables in group.
Consider the equation x2 = a (*)This equation may be satisfiable in Zn* (when a is in QRn), but this equation is never satisfiable in a free group, since reduced form of x2 always has even length.
Exhibiting a solution to (*) in a group G is another way to demonstrate that G is not a free group.d^8
,
1&
YEquations in Free GroupsCan always be put into form: w = 1where w is sequence over symbols of group and variables.
It is decidable (Makanin 82) in PSPACE (Gutierrez 00) whether an equation is satisfiable in free group.
Multiple equations equivalent to single one.
For abelian free group it is in P. Also: if equation is unsatisfiable in FA() it is unsatisfiable in F().BaZ 3pZPseudofreeness.A family of computational groups { Gk } is pseudofree if for any poly s t(k), m(k) a PPT adversary has negl(k) chance of:
Accepting t(k) random elements of Gk,
Producing any equation E(a1,& ,at(k),x1,& ,xm(k)): w = 1with t(k) generator symbols and m(k) variables that is unsatisfiable over F(a1,& ,at(k))
Producing a solution to E over Gk, with given random elements substituted for generators.{!7
$
9I3M._[Main conjecture PConjecture: { Zn* } is a (strong) (abelian) pseudofree group
aka Superstrong RSA conjecture
What are implications of PFG assumption?VDL]IcRSA and Strong RSATheorem: In a PFG, RSA assumption and Strong RSA assumptions hold.
Proof: For e>1 the equation xe = ais not satisfiable in FA(a) (and also thus not in F(a)).
:%;>y]Taking square rootsRTheorem: In a PFG, taking square roots of randomly chosen elements is hard.
Proof: As noted earlier, the equation x2 = a (*) has no solution in FA(a) or F(a).
Note the importance of forcing adversary to solve (*) for a random a; it wouldn t do to allow him to take square root of, say, 4 .t*ZC%f
>,^<Computational DiffieHellman L*(((fCDH: Given g , a = ge, and b = gf, computing x = gef is hard.
Conjecture: CDH holds in a PFG.
Remark: This seems natural, since in a free group there is no element (other than 1) that is simultaneously a power of more than one generator. Yet the adversary merely needs to output x; there is no equation involving x that he must output.
gZ>$b
Open problemsShow factoring implies Zn* is PFG.
Show CDH holds in PFG s.
Show utility of PFG theory by simplifying known security proofs.
Determine is satisfiability of equation over free group is decidable when variables include exponents.
Extend theory to groups of known size (e.g. mod p), and adaptive attacks (adversary can get solution to some equations of his choice for free).
\vP
`6;= ( THE END )
Safe travels!/YP ` 33` Sf3f` 33g` f` www3PP` ZXdbmo` \ғ3y`Ӣ` 3f3ff` 3f3FKf` hk]wwwfܹ` ff>>\`Y{ff` R>& {p_/̴>?" dd@,?" dd@ " @ ` n?" dd@ @@``PR @ ` `p>>0(f(
(
(
6 `}
T Click to edit Master title style!
!
(
0 `
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
(
0 ^ `
>*
(
04 ^
@*
(
0 ^ `
@*H
(0h ? 33D<___PPT10..P3 Custom Design ` f3` f̙` 999___` f3f3f3!>?" dd@,?uKd@ d @uA` d n?" dd@ @@``PR @ ` `p>>zrL
(
L~B
L
Hp?"``
L
Zgֳgֳ ?"`
T Click to edit Master title style!
!H
L
TDgֳgֳ ?" @
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
L
`gֳgֳ ?"0P
>*
L
` gֳgֳ ?"0P
@*
L
`@gֳgֳ ?"0P
@*H
L0h? ? f3 Side Bar 3+P(
P~B
P
Hp?"pp
P
Z2gֳgֳ ?"p
T Click to edit Master title style!
!
P
TJgֳgֳ ?" `
W#Click to edit Master subtitle style$
$
P
`gֳgֳ ?"`
>*
P
`8Ngֳgֳ ?"`
@*
P
`4Rgֳgֳ ?"`
@*H
P0h? ? f3Z
0Pj(
TeKeK ?)
x*
G$$GGll
TeKeK ? F)
z*
G$$GGllp
01 ?C>
:
T<jl5jl5 ?
T
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
ZeKeK ?
x*
G$$GGll
ZeKeK ? F
z*
G$$GGllH
0j? ? ̙3380___PPT10.08p0(
H
0j ? ̙3380___PPT10.DB >(
#l[gֳgֳ ?PpP0@
#l\gֳgֳ ?P`
v
N?( H
0h ? f3y___PPT10Y+D=' =
@B +
0(
x
c$L`
x
c$pL @
H
0h ? f3___PPT10i.1+D=' =
@B +*
*(
x
c$L`
r
SL
H
0h ? f380___PPT10.Nf'
*
*(
x
c$L`
r
S
L
H
0h ? f380___PPT10.@*
*(
x
c$L`
r
SL>
H
0h ? f380___PPT10.Q`30
0(
x
c$X,L`
x
c$,L @
H
0h ? f380___PPT10.Vex0
0(
x
c$(sL`
x
c$sL @
H
0h ? f380___PPT10.W=*
*(
x
c$OL`
r
SPL 8
H
0h ? f380___PPT10.X&c6+**?R6*(
R
C*AJ0078622
Y8 %
P
`O1?T%X
31(xB
B
HDp?* xB
B
HDp?lB xB
B
HDp?L`jxB
HDp?* xB
HDp?N xB
HDp?XxB
HDp?l xB
HDp?xB
!
HDp?
j@xB
$B
HDp?~ xB
%B
HDp?FxB
&B
HDp?tRxB
'B
HDp?r@xB
(
HDp?R2
)
N1?"`%2
+
N1?"`+2
,
N1?"`<+
0
`X1?(s
3a
1
`]1?
3a
2
`_1?
3a
3
`c1? +
3a
4
``1?F
3a
5
`i1?xo}
3a
6
`n1?4
3a
;
`o1?JVs
3b
<
`t1? +
3b
=
`v1?4 @%
3b
>
`{1?4
3b
?
`y1?F
3b
@
`1?JV}
3b
A
`Xz1?F
3b E8 e1:
OsH
`p1?1
31(xB
B
HDp?Z xB
B
HDp? BxB
HDp?RH xB
HDp?p Z0xB
HDp?H HxB
#B
HDp?, @6

`1?O
3a
.
`\1?p
g
3a
/
`1? 1
3a
7
`\1?.:
3b
8
`,1?
3b
9
`H1?<
3b
:
`,1? 1
3b
C
B1CDEFp?WOT1@ "`eZf(
E
BCDEFAAp?7YlJ@ "`R~ <xB
F
HDp?.ffxB
G
HDp?hr6rxB
HB
HDp?>NxB
I
HDp?
J
`,1?
3a
K
`1?N<
E
3a
L
``1?X
3a
M
`1?>
3b
N
`ȷ1?`8l
3b
Q
`1?4X
hCayley graphof finite group$
R
`1?i
yW
fCayley graphof free group$H
0h ? f380___PPT10. ۾$
P`$(
`r
` SL`
r
` S\L
H
`0h ? f380___PPT10.\6
`d6(
d~
d s*pL`
x
d c$DL
H
d0h ? f380___PPT10.[h*
@*(
x
c$L`
r
SpL P
H
0h ? f380___PPT10._0q6
6(
~
s*<L`
x
c$lL P
H
0h ? f380___PPT10._0q0
p0(
x
c$L`
x
c$L &@
H
0h ? f380___PPT10.e@v*
*(
x
c$L`
r
StL
H
0h ? f380___PPT10.YJ*
*(
x
c$d/L`
r
S
L
H
0h ? f380___PPT10.Z*
*(
x
c$RL`
r
SpSL
H
0h ? f380___PPT10.[h*
0*(
x
c$@rL`
r
SrL
H
0h ? f380___PPT10.]'I$
0X$(
Xr
X SL`
r
X SL @
H
X0h ? f380___PPT10.z*
P*(
x
c$L`
r
SL >
H
0h ? f380___PPT10.b2*
`*(
x
c$L`
r
SL
H
0h ? f380___PPT10.bv$
T$(
Tr
T S[L`
r
T S\L x
H
T0h ? f380___PPT10.!yLsT*(
Tx
T c$iPp
r
T SjP `
H
T0h ? f3y___PPT10Y+D=' =
@B +
0@( 7k
X
CC>
SP
T
H
0j ? ̙33r0BqxyYcK}@rdX,W`j,R~m7(W({
Times New RomanArialComic Sans MSMonotype SortsSymbol
WingdingsCustom Design Side Bar%On the Notion of PseudoFree GroupsOutlineCryptographic assumptionsGroupsFree GroupsFree Group PropertiesAbelian Free GroupsPseudoFree Groups (Informal)Slide 9Two ways of distinguishingWeak PseudofreenessOrder problemDiscrete logarithm problemSubgroups of PFG’sEquations in GroupsEquations in Free GroupsPseudofreenessMain conjecture RSA and Strong RSATaking square roots!Computational DiffieHellman Open problems ( THE END )Fonts UsedDesign Template
Slide Titles(_Ronald L. RivestRonald L. Rivest@BComic Sans MS. 2
[Pseudo ! $ .ew Roman0:A 0 DComic Sans MSn0:A 0B0DMonotype Sorts0:A 0@DSymbole Sorts0:A 0PDWingdingsorts0:A 0C6.@ @@``
@n?" dd@ @@``d
w DBD% Z !"#$%&'()S3@ABCEF,2$o/.A.[H3#0=UsAA1? ffff@Tg4BdBd :A 0Bjppp@<4ddddL # 0<4!d!dL # 0g4;d;d :A 0Xpkp`ʚ;Mqe8ʚ;<4ddddLT# 080___PPT10
J___PPT9,/0{A0?O=H$On the Notion of PseudoFree Groups%$(ZRonald L. Rivest
MIT Computer Science and Artificial Intelligence Laboratory
TCC 2/21/2004[ZQOutlineAssumptions: complexitytheoretic, grouptheoretic
Groups: Math, Computational, BB, Free
Weak pseudofree groups
Equations over groups and free groups
Pseudofree groups
Implications of pseudofreeness
Open problemsSCryptographic assumptionsComputational cryptography depends on complexitytheoretic assumptions.
$ two types:
Generic: OWF, TDP, P!=NP, ...
Algebraic: Factoring, RSA, DLP, DH, Strong RSA, ECDLP, GAP, WPFG, PFG, &
We re interested in algebraic assumptions ( about groups )Uh;; 1
RGroupsFamiliar algebraic structure in crypto.
Mathematical group G = (S,*): binary operation * defined on (finite) set S: associative, identity, inverses, perhaps abelian. Example: Zn* (running example).
Computational group [G] implements a mathematical group G. Each element x in G has one or more representations [x] in [G]. E.g. [Zn*] via least positive residues.
Blackbox group: pretend [G] = G.
(,?
!!
TFree GroupsvGenerators: a1, a2, & , at
Symbols: generators and their inverses.
Elements of free group F(a1, a2, & , at) are reduced finite sequences of symbolsno symbol is next to its inverse. ab1a1bc is in F(a,b,c) ; abb1 is not.
Group operation: concatenation & reduction.
Identity: empty sequence (or 1).<
I
,1 UFree Group PropertiesDFree group is infinite.
In a free group, every element other than the identity has infinite order.
Free group has no nontrivial relationships.
Reasoning in a free group is relatively straightforward and simple; DolevYao for groups&
Every group is homomorphic image of a free group.
,#Z6 DVAbelian Free GroupsThere is also abelian free group FA(a1, a2, & , at), which is isomorphic to Z x Z x & x Z (t times).
Elements of FA(a1, a2, & , at) have simple canonical form: a1e1a2e2& atet
We will often omit specifying abelian; most of our definitions have abelian and nonabelian versions.
CZ
*
fhWPseudoFree Groups (Informal)(< A finite group is pseudofree if it can not be efficiently distinguished from a free group.
Notion first expressed, in simple form, in Susan Hohenberger s M.S. thesis.
We give two formalizations, and show that assumption of pseudofreeness implies many other wellknown assumptions.&Z
adTwo ways of distinguishingIn a weak pseudofree group (WPFG), adversary can t find any nontrivial identity involving supplied random elements: a2 b5 c1 = 1 (!)
In a (strong) pseudofree group (PFG), adversary can t solve nontrivial equations: x2 = a3 b^8eWeak Pseudofreeness A family of computational groups { Gk } is weakly pseudofree if for any polynomial t(k) a PPT adversary has negl(k) chance of:
Accepting t(k) random elements of Gk, a1, & ,at(k)
Producing any word w over the symbols a1, & ,at(k) a11, & ,at(k)1when interpreted as a pr
!"#$%&'()*+,./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstvxyz{}~wuRoot EntrydO)ս
PicturesCurrent User5PSummaryInformation(PowerPoint Document(,DocumentSummaryInformation8$84
/0DTimes New Roman0:A 0DArialNew Roman0:A 0 DComic Sans MSn0:A 0B0DMonotype Sorts0:A 0@DSymbole Sorts0:A 0PDWingdingsorts0:A 0C6.@ @@``
@n?" dd@ @@``d
w DBD% Z !"#$%&'()S3@ABCEF,2$o/.A.[H3#0=UsAA1? ffff@Tg4dddd :A 0j.ppp@<4ddddL # 0<4!d!dL # 0g4;d;d :A 0Xpkp`ʚ;Mqe8ʚ;<4ddddLT# 080___PPT10
J___PPT9,/0{A0?O=H$On the Notion of PseudoFree Groups%$(ZRonald L. Rivest
MIT Computer Science and Artificial Intelligence Laboratory
TCC 2/21/2004[ZQOutlineAssumptions: complexitytheoretic, grouptheoretic
Groups: Math, Computational, BB, Free
Weak pseudofree groups
Equations over groups and free groups
Pseudofree groups
Implications of pseudofreeness
Open problemsSCryptographic assumptionsComputational cryptography depends on complexitytheoretic assumptions.
$ two types:
Generic: OWF, TDP, P!=NP, ...
Algebraic: Factoring, RSA, DLP, DH, Strong RSA, ECDLP, GAP, WPFG, PFG, &
We re interested in algebraic assumptions ( about groups )Uh;; 1
RGroupsFamiliar algebraic structure in crypto.
Mathematical group G = (S,*): binary operation * defined on (finite) set S: associative, identity, inverses, perhaps abelian. Example: Zn* (running example).
Computational group [G] implements a mathematical group G. Each element x in G has one or more representations [x] in [G]. E.g. [Zn*] via least positive residues.
Blackbox group: pretend [G] = G.
(,?
!!
TFree GroupsvGenerators: a1, a2, & , at
Symbols: generators and their inverses.
Elements of free group F(a1, a2, & , at) are reduced finite sequences of symbolsno symbol is next to its inverse. ab1a1bc is in F(a,b,c) ; abb1 is not.
Group operation: concatenation & reduction.
Identity: empty sequence (or 1).<
I
,1 UFree Group PropertiesDFree group is infinite.
In a free group, every element other than the identity has infinite order.
Free group has no nontrivial relationships.
Reasoning in a free group is relatively straightforward and simple; DolevYao for groups&
Every group is homomorphic image of a free group.
,#Z6 DVAbelian Free GroupsThere is also abelian free group FA(a1, a2, & , at), which is isomorphic to Z x Z x & x Z (t times).
Elements of FA(a1, a2, & , at) have simple canonical form: a1e1a2e2& atet
We will often omit specifying abelian; most of our definitions have abelian and nonabelian versions.
CZ
*
fhWPseudoFree Groups (Informal)(< A finite group is pseudofree if it can not be efficiently distinguished from a free group.
Notion first expressed, in simple form, in Susan Hohenberger s M.S. thesis.
We give two formalizations, and show that assumption of pseudofreeness implies many other wellknown assumptions.&Z
adTwo ways of distinguishingIn a weak pseudofree group (WPFG), adversary can t find any nontrivial identity involving supplied random elements: a2 b5 c1 = 1 (!)
In a (strong) pseudofree group (PFG), adversary can t solve nontrivial equations: x2 = a3 b^8eWeak Pseudofreeness A family of computational groups { Gk } is weakly pseudofree if for any polynomial t(k) a PPT adversary has negl(k) chance of:
Accepting t(k) random elements of Gk, a1, & ,at(k)
Producing any word w over the symbols a1, & ,at(k) a11, & ,at(k)1when interpreted as a product in Gk using the obtained random values, yields the identity 1 , while w does not yield 1 in the free group.
Adversary may use compact notion (exponents, straightline programs) when describing w. B!
5
!
6jPT36>\
Order problemTheorem: In a WPFG, finding the order of a randomly chosen element is hard.
Proof: The equation ae = 1does not hold for any e in FA(a). No element other than 1 in a free group has finite order. C'=,x ?`Discrete logarithm problemTheorem: In a WPFG, DLP is hard.
Proof: The equation ae = bdoes not hold for any e in FA(a,b); a and b are distinct independent generators, one can not be power of other.'
C,M S_$Subgroups of PFG s
Subgroup Theorem for WPFG s: If G is a WPFG, and g is chosen at random from G, then <g> is a WPFG. [not in paper]
Proof sketch: Ability to find nontrivial identities in <g> can be shown to imply that g has finite order.
==> DLP is hard in WPFG even if we enforce promise that b is a (random) power of a .
Similar proof implies that QRn is WPFG when n = (2p +1)(2q +1).
PZ
,M
,D$XEquations in GroupsLet x, y, & denote variables in group.
Consider the equation x2 = a (*)This equation may be satisfiable in Zn* (when a is in QRn), but this equation is never satisfiable in a free group, since reduced form of x2 always has even length.
Exhibiting a solution to (*) in a group G is another way to demonstrate that G is not a free group.d^8
,
1&
YEquations in Free GroupsCan always be put into form: w = 1where w is sequence over symbols of group and variables.
It is decidable (Makanin 82) in PSPACE (Gutierrez 00) whether an equation is satisfiable in free group.
Multiple equations equivalent to single one.
For abelian free group it is in P. Also: if equation is unsatisfiable in FA() it is unsatisfiable in F().BaZ 3pZPseudofreeness.A family of computational groups { Gk } is pseudofree if for any poly s t(k), m(k) a PPT adversary has negl(k) chance of:
Accepting t(k) random elements of Gk,
Producing any equation E(a1,& ,at(k),x1,& ,xm(k)): w = 1with t(k) generator symbols and m(k) variables that is unsatisfiable over F(a1,& ,at(k))
Producing a solution to E over Gk, with given random elements substituted for generators.{!7
$
9I3M._[Main conjecture PConjecture: { Zn* } is a (strong) (abelian) pseudofree group
aka Superstrong RSA conjecture
What are implications of PFG assumption?VDL]IcRSA and Strong RSATheorem: In a PFG, RSA assumption and Strong RSA assumptions hold.
Proof: For e>1 the equation xe = ais not satisfiable in FA(a) (and also thus not in F(a)).
:%;>y]Taking square rootsRTheorem: In a PFG, taking square roots of randomly chosen elements is hard.
Proof: As noted earlier, the equation x2 = a (*) has no solution in FA(a) or F(a).
Note the importance of forcing adversary to solve (*) for a random a; it wouldn t do to allow him to take square root of, say, 4 .t*ZC%f
>,^<Computational DiffieHellman L*(((fCDH: Given g , a = ge, and b = gf, computing x = gef is hard.
Conjecture: CDH holds in a PFG.
Remark: This seems natural, since in a free group there is no element (other than 1) that is simultaneously a power of more than one generator. Yet the adversary merely needs to output x; there is no equation involving x that he must output.
gZ>$b
Open problemsShow factoring implies Zn* is PFG.
Show CDH holds in PFG s.
Show utility of PFG theory by simplifying known security proofs.
Determine is satisfiability of equation over free group is decidable when variables include exponents.
Extend theory to groups of known size (e.g. mod p), and adaptive attacks (adversary can get solution to some equations of his choice for free).
\vP
`6;= ( THE END )
Safe travels!/YPrm1(W(4
/0DTimes New Roman0:A 0DArialN
!"#%&'()*+,./012346Oh+'0
px
(
4@HRSA: 19771997 and beyondRonald L. Rivestnd onaRonald L. Rivestnd 274Microsoft PowerPoint 7.0d@p@Z{ɽ@@p/G\g =@ !'%wmw'@BComic Sans MS. 2
On the Notion of1 #!1 ."System @BComic Sans MS. 2
[Pseudo ! $ .@BComic Sans MS. 2
[&.@BComic Sans MS. 2
[Free Groups%!!) !.@BComic Sans MS. 2
QRonald L. Rivest
.@BComic Sans MS. =2
r$MIT Computer Science and Artificial '
"
.@BComic Sans MS. *2
EIntelligence Laboratory
.@BComic Sans MS. 2
Q
TCC 2/21/2004e
.@ ! $11'՜.+,0
Onscreen Show,oduct in Gk using the obtained random values, yields the identity 1 , while w does not yield 1 in the free group.
Adversary may use compact notion (exponents, straightline programs) when describing w. B!
5
!
6jPT36>\
Order problemTheorem: In a WPFG, finding the order of a randomly chosen element is hard.
Proof: The equation ae = 1does not hold for any e in FA(a). No element other than 1 in a free group has finite order. C'=,x ?`Discrete logarithm problemTheorem: In a WPFG, DLP is hard.
Proof: The equation ae = bdoes not hold for any e in FA(a,b); a and b are distinct independent generators, one can not be power of other.'
C,M S_$Subgroups of PFG s
Subgroup Theorem for WPFG s: If G is a WPFG, and g is chosen at random from G, then <g> is a WPFG. [not in paper]
Proof sketch: Ability to find nontrivial identities in <g> can be shown to imply that g has finite order.
==> DLP is hard in WPFG even if we enforce promise that b is a (random) power of a .
Similar proof implies that QRn is WPFG when n = (2p +1)(2q +1).
PZ
,M
,D$XEquations in GroupsLet x, y, & denote variables in group.
Consider the equation x2 = a (*)This equation may be satisfiable in Zn* (when a is in QRn), but this equation is never satisfiable in a free group, since reduced form of x2 always has even length.
Exhibiting a solution to (*) in a group G is another way to demonstrate that G is not a free group.d^8
,
1&
YEquations in Free GroupsCan always be put into form: w = 1where w is sequence over symbols of group and variables.
It is decidable (Makanin 82) in PSPACE (Gutierrez 00) whether an equation is satisfiable in free group.
Multiple equations equivalent to single one.
For abelian free group it is in P. Also: if equation is unsatisfiable in FA() it is unsatisfiable in F().BaZ 3pZPseudofreeness.A family of computational groups { Gk } is pseudofree if for any poly s t(k), m(k) a PPT adversary has negl(k) chance of:
Accepting t(k) random elements of Gk,
Producing any equation E(a1,& ,at(k),x1,& ,xm(k)): w = 1with t(k) generator symbols and m(k) variables that is unsatisfiable over F(a1,& ,at(k))
Producing a solution to E over Gk, with given random elements substituted for generators.{!7
$
9I3M._[Main conjecture PConjecture: { Zn* } is a (strong) (abelian) pseudofree group
aka Superstrong RSA conjecture
What are implications of PFG assumption?VDL]IcRSA and Strong RSATheorem: In a PFG, RSA assumption and Strong RSA assumptions hold.
Proof: For e>1 the equation xe = ais not satisfiable in FA(a) (and also thus not in F(a)).
:%;>y]Taking square rootsRTheorem: In a PFG, taking square roots of randomly chosen elements is hard.
Proof: As noted earlier, the equation x2 = a (*) has no solution in FA(a) or F(a).
Note the importance of forcing adversary to solve (*) for a random a; it wouldn t do to allow him to take square root of, say, 4 .t*ZC%f
>,^<Computational DiffieHellman L*(((fCDH: Given g , a = ge, and b = gf, computing x = gef is hard.
Conjecture: CDH holds in a PFG.
Remark: This seems natural, since in a free group there is no element (other than 1) that is simultaneously a power of more than one generator. Yet the adversary merely needs to output x; there is no equation involving x that he must output.
gZ>$b
Open problemsShow factoring implies Zn* is PFG.
Show CDH holds in PFG s.
Show utility of PFG theory by simplifying known security proofs.
Determine is satisfiability of equation over free group is decidable when variables include exponents.
Extend theory to groups of known size (e.g. mod p), and adaptive attacks (adversary can get solution to some equations of his choice for free).
\vP
`6;= ( THE END )
Safe travels!/YP >(
#l6gֳgֳ ?PpP0@
#ld7gֳgֳ ?P`
v
N?( H
0h ? f3y___PPT10Y+D=' =
@B +rB1am1(