An algebraic framework for Diffie-Hellman assumptions

An Algeb aic F amewo k o Di ie-Hellman Assump ions
Alex Escala1, Go ied He old∗2, Eike Kil z†2, Ca la R`a ols2, and Jo ge Villa ‡1
1Uni e si a Poli `ecnica de Ca alunya, Spain, {alex.escala,j illa }@ma4.upc.edu
2Ho s -G¨o z Ins i u e o IT Secu i y and Facul y o Ma hema ics, Ruh -Uni e si ¨a
Bochum, Ge many, {go ied.he old,eike.kil z,ca la. a ols}@ ub.de
Abs ac
We pu o wa d a new algeb aic amewo k o gene alize and analyze Di ie-Hellman like Decisional
Assump ions which allows us o a gue abou secu i y and applica ions by conside ing only algeb aic
p ope ies. Ou D`,k-MDDH assump ion s a es ha i is ha d o decide whe he a ec o in
G
`is
linea ly dependen o he columns o some ma ix in
G
`×ksampled acco ding o dis ibu ion D`,k. I
co e s known assump ions such as DDH, 2-Lin (linea assump ion), and k-Lin ( he k-linea assump ion).
Using ou algeb aic iewpoin , we can ela e he gene ic ha dness o ou assump ions in m-linea g oups
o he i educibili y o ce ain polynomials which desc ibe he ou pu o D`,k. We use he ha dness esul s
o ind new dis ibu ions o which he D`,k-MDDH-Assump ion holds gene ically in m-linea g oups. In
pa icula , ou new assump ions 2-SCasc and 2-ILin a e gene ically ha d in bilinea g oups and, compa ed
o 2-Lin, ha e sho e desc ip ion size, which is a ele an pa ame e o e iciency in many applica ions.
These esul s suppo using ou new assump ions as na u al eplacemen s o he 2-Lin Assump ion which
was al eady used in a la ge numbe o applica ions.
To illus a e he concep ual ad an ages o ou algeb aic amewo k, we cons uc se e al undamen al
p imi i es based on any MDDH-Assump ion. In pa icula , we can gi e many ins an ia ions o a p imi i e
in a compac way, including public-key enc yp ion, hash-p oo sys ems, pseudo- andom unc ions, and
G o h-Sahai NIZK and NIWI p oo s. As an independen con ibu ion we gi e mo e e icien NIZK
and NIWI p oo s o membe ship in a subg oup o
G
`. The esul s imply e y signi ican e iciency
imp o emen s o a la ge numbe o schemes.
Keywo ds: Di ie-Hellman Assump ion, Gene ic Ha dness, G o h-Sahai p oo s, Hash P oo Sys ems,
Public-key Enc yp ion.
∗Funded by ERC G an ERC307952 Fas and Sound C yp og aphy.
†Funded by a So ja Ko ale skaja Awa d o he Alexande on Humbold Founda ion and he Ge man Fede al Minis y o
Educa ion and Resea ch.
‡Funded by he Spanish esea ch p ojec MTM2013-41426-R.
Con en s
1 In oduc ion 1
1.1 The Ma ix Di ie-Hellman Assump ion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 BasicApplica ions .......................................... 3
2 P elimina ies 4
2.1 No a ion................................................ 4
2.2 Rep esen ing Elemen s in G oups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 S anda d Di ie-Hellman Assump ions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4 KeyEncapsula ionMechanisms................................... 5
2.5 HashP oo Sys ems ......................................... 6
2.6 Pseudo-RandomFunc ions...................................... 6
3 Ma ix DH assump ions 6
3.1 De ini ion ............................................... 6
3.2 BasicP ope ies ........................................... 7
3.3 Gene icHa dnesso Ma ixDH................................... 8
3.4 Examples o D`,k-MDDH ....................................... 9
4 Uniqueness o One-Pa ame e Ma ix DH P oblems 10
4.1 Ha dness ............................................... 11
4.2 Isomo phicP oblems......................................... 12
5 Basic Applica ions 13
5.1 Public-KeyEnc yp ion........................................ 13
5.2 HashP oo Sys ems ......................................... 14
5.3 Pseudo-RandomFunc ions...................................... 14
5.4 G o h-Sahai Non-in e ac i e Ze o-Knowledge P oo s . . . . . . . . . . . . . . . . . . . . . . . 16
6 Mo e E icien P oo s o Some CRS Dependen Languages 19
6.1 Mo e E icien Subg oup Membe ship P oo s . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.2 O he CRS Dependen Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
A P oo o Theo em 7 27
B P oo s o he Gene ic Ha dness esul s 28
B.1 P oo o Theo em3.......................................... 29
B.2 P oo o Theo em 4 and Gene aliza ions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
C P oo o Theo em 10 32
D Subg oup Membe ship P oo s o 2-Lin 33
E Conc e e Examples om he k-SCasc Assump ion 34
E.1 KeyEncapsula ion.......................................... 34
E.2 Pseudo-RandomFunc ion ...................................... 35
1 In oduc ion
A guably, one o he mos impo an c yp og aphic ha dness assump ions is he Decisional Di ie-Hellman
(DDH) Assump ion. Fo a ixed addi i e g oup
G
o p ime o de qand a gene a o Po
G
, we deno e
by [a] := aP ∈
G
he implici ep esen a ion o an elemen a∈
Z
q. The DDH Assump ion s a es ha
([a],[ ],[a ]) ≈c([a],[ ],[z]) ∈
G
3, whe e a, , z a e uni o m elemen s in
Z
qand ≈cdeno es compu a ionally
indis inguishabili y o he wo dis ibu ions. I has been used in nume ous impo an applica ions such as
secu e enc yp ion [12], key-exchange [20], hash-p oo sys ems [13], pseudo- andom unc ions [37], and many
mo e.
Bilinea G oups and he Linea Assump ion. Bilinea g oups (i.e., g oups
G
,
G
To p ime o de q
equipped wi h a bilinea map e:
G
×
G
→
G
T) [4, 24] e olu ionized c yp og aphy in ecen yea s and
and a e he basis o a la ge numbe o c yp og aphic p o ocols. Howe e , ela i e o a (symme ic) bilinea
map, he DDH Assump ion is no longe ue in he g oup
G
. (This is since e([a],[ ]) = e([1],[a ]) and hence
[a ] is no longe pseudo andom gi en [a] and [ ].) The need o an “al e na i e” decisional assump ion in
G
was quickly add essed wi h he Linea Assump ion (2-Lin) in oduced by Boneh, Boyen, and Shacham [3]. I
s a es ha ([a1],[a2],[a1 1],[a2 2],[ 1+ 2]) ≈c([a1],[a2],[a1 1],[a2 2],[z]) ∈
G
5, whe e a1, a2, 1, 2, z ←
Z
q.
2-Lin holds in gene ic bilinea g oups [3] and i has i ually become he s anda d decisional assump ion in
he g oup
G
in he bilinea se ing. I has ound applica ions o enc yp ion [5, 7, 29, 38], signa u es [3], ze o-
knowledge p oo s [21], pseudo andom unc ions [6] and many mo e. Mo e ecen ly, he 2-Lin Assump ion was
gene alized o he (k-Lin)k∈
N
Assump ion amily [23, 45] (1-Lin =DDH), a amily o inc easingly (s ic ly)
weake Assump ions which a e gene ically ha d in k-linea maps.
Subg oup Membe ship P oblems. Since he wo k o C ame and Shoup [13] i has been ecognized
ha i is use ul o iew he DDH Assump ion as a ha d subg oup membe ship p oblem in
G
2. In his
o mula ion, he DDH Assump ion s a es ha i is ha d o decide whe he a gi en elemen ([ ],[ ]) ∈
G
2
is con ained in he subg oup gene a ed by ([1],[a]). Simila ly, in his language he 2-Lin Assump ion says
ha i is ha d o decide whe he a gi en ec o ([ ],[s],[ ]) ∈
G
3is in he subg oup gene a ed by he ec o s
([a1],[0],[1]),([0],[a2],[1]). The same holds o he (k-Lin)k∈
N
Assump ion amily: o each k, he k-Lin
assump ion can be na u ally w i en as a ha d subg oup membe ship p oblem in
G
k+1. This al e na i e
o mula ion has concep ual ad an ages o some applica ions, o ins ance, i allowed o p o ide mo e in-
s an ia ions o he o iginal DDH-based scheme o C ame and Shoup and i is also he mos na u al poin
o iew o ansla ing schemes o iginally cons uc ed in composi e o de g oups in o p ime o de g oups
[18, 36, 43, 44].
Linea Algeb a in Bilinea G oups. In i s o mula ion as subg oup decision membe ship p oblem, he
k-Lin assump ion can be seen as he p oblem o deciding linea dependence “in he exponen .” Recen ly, a
numbe o wo ks ha e illus a ed he use ulness o a mo e algeb aic poin o iew on decisional assump ions
in bilinea g oups, like he Dual Pai ing Vec o Spaces o Okamo o and Takashima [40] o he Subspace
Assump ion o Lewko [32]. Al hough hese new decisional assump ions educe o he 2-Lin Assump ion,
hei lexibili y and hei algeb aic desc ip ion ha e p o en o be c ucial in many wo ks o ob ain complex
p imi i es in s ong secu i y models p e iously un ealized in he li e a u e, like A ibu e-Based Enc yp ion,
Unbounded Inne P oduc Enc yp ion and many mo e (see [32, 41, 42], jus o name a ew).
This Wo k. Mo i a ed by he success o his algeb aic iewpoin o decisional assump ions, in his pape we
explo e new insigh s esul ing om in e p e ing he k-Lin decisional assump ion as a special case o wha we
call a Ma ix Di ie-Hellman Assump ion. The gene al p oblem s a es ha i is ha d o dis inguish whe he
a gi en ec o in
G
`is con ained in he space spanned by he columns o a ce ain ma ix [A]∈
G
`×k, whe e
Ais sampled acco ding o some dis ibu ion D`,k. We ema k ha e en hough all ou esul s a e s a ed in
symme ic bilinea g oups, hey can be na u ally ex ended o he asymme ic se ing.
1.1 The Ma ix Di ie-Hellman Assump ion
A New F amewo k o DDH-like Assump ions. Fo in ege s ` > k le D`,k be an (e icien ly samplable)
dis ibu ion o e
Z
`×k
q. We de ine he D`,k-Ma ix DH (D`,k-MDDH) Assump ion as he ollowing subg oup
1
decision assump ion:
D`,k-MDDH : [A||A~ ]≈c[A||~u]∈
G
`×(k+1),(1)
whe e A∈
Z
`×k
qis chosen om dis ibu ion D`,k,~ ←
Z
k
q, and ~u ←
G
`. The (k-Lin)k∈
N
amily co esponds
o his p oblem when `=k+ 1, and D`,k is he speci ic dis ibu ion Lk( o mally de ined in Example 2).
Gene ic Ha dness. Due o i s linea i y p ope ies, he D`,k-MDDH Assump ion does no hold in (k+
1)-linea g oups. In Sec ion 3.3 we gi e wo di e en heo ems which s a e su icien condi ions o he
D`,k-MDDH Assump ion o hold gene ically in m-linea g oups. Theo em 3 is e y simila o he Ube -
Assump ion [2, 9] ha cha ac e izes ha dness in bilinea g oups (i.e., m= 2) in e ms o linea independence
o polynomials in he inpu s. We gene alize his o a bi a y musing a mo e algeb aic language. This
algeb aic o mula ion has he ad an age ha one can use addi ional ools (e.g. G ¨obne bases o esul an s)
o show ha a dis ibu ion D`,k mee s he condi ions o Theo em 3, which is specially impo an o la ge m.
I also allows o p o e a comple ely new esul , namely Theo em 4, which s a es ha a ma ix assump ion
wi h `=k+ 1 is gene ically ha d i a ce ain de e minan polynomial is i educible.
New Assump ions o Bilinea G oups. We p opose o he amilies o gene ically ha d decisional
assump ions ha did no p e iously appea in he li e a u e, e.g., hose associa ed o Ck,SCk,ILkde ined
below. Fo he mos impo an pa ame e s k= 2 and `=k+ 1 = 3, we conside he ollowing examples o
dis ibu ions:
C2:A=

a10
1a2
0 1 
SC2:A=

a0
1a
0 1
L2:A=

a10
0a2
1 1 
IL2:A=

a0
0a+ 1
1 1 
,
o uni o m a, a1, a2∈
Z
qas well as U3,2, he uni o m dis ibu ion in
Z
3×2
q(al eady conside ed in [5, 19, 38,
46]). All assump ions a e ha d in gene ic bilinea g oups. I is easy o e i y ha L2-MDDH = 2-Lin. We de-
ine 2-Casc := C2-MDDH (Cascade Assump ion), 2-SCasc := SC2-MDDH (Symme ic Cascade Assump ion),
and 2-ILin := IL2-MDDH (Inc emen al Linea Assump ion). In Sec ion 3.4, we show ha 2-SCasc ⇒2-Casc,
2-ILin ⇒2-Lin and ha U3,2-MDDH is he weakes o hese assump ions (which ex ends he esul s o
[18, 19, 46] o 2-Lin). Al hough o iginally [16] 2-ILin and 2-SCasc we e hough o be incompa able assump-
ions, in Sec ion 4 we show ha 2-SCasc and 2-ILin a e indeed equi alen assump ions. The equi alence
esul , oge he wi h he ac ha 2-ILin ⇒2-Lin, imply ha 2-SCasc is a s onge assump ion han 2-Lin.
E iciency Imp o emen s. As a measu e o e iciency, we de ine he ep esen a ion size RE
G
(D`,k) o an
D`,k-MDDH assump ion as he minimal numbe o g oup elemen s needed o ep esen [A] o any A← D`,k.
This pa ame e is impo an since i a ec s he pe o mance ( ypically he size o public/sec e pa ame e s) o
schemes based on a Ma ix Di ie-Hellman Assump ion. 2-Lin and 2-Casc ha e ep esen a ion size 2 (elemen s
([a1],[a2])), while 2-SCasc only 1 (elemen [a]). Hence ou new assump ions di ec ly ansla e in o sho e
pa ame e s o a la ge numbe o applica ions (see he Applica ions in Sec ion 5). Fu he , ou esul poin s
ou a adeo be ween e iciency and ha dness which ques ions he ole o 2-Lin as he “s anda d decisional
assump ion” o e a bilinea g oup
G
.
New Families o Weake Assump ions. By de ining app op ia e dis ibu ions Ck,SCk,ILko e
Z
(k+1)×k
q, o any k∈
N
, one can gene alize all h ee new assump ions na u ally o k-Casc,k-SCasc, and
k-ILin wi h ep esen a ion size k, 1, and 1, espec i ely. Using ou esul s on gene ic ha dness, i is easy o
e i y ha all h ee assump ions a e gene ically ha d in k-linea g oups. Ac ually, in Sec ion 4 we show ha
k-SCasc, and k-ILin a e equi alen o e e y k. Since all hese assump ions a e alse in (k+ 1)-linea g oups
his gi es us h ee new amilies o inc easingly s ic ly weake assump ions1. In pa icula , he k-SCasc
(equi alen ly, k-ILin) assump ion amily is o g ea in e es due o i s compac ep esen a ion size o only 1
elemen .
Rela ions o O he S anda d Assump ions. Su p isingly, he new assump ion amilies can also be
ela ed o s anda d assump ions. The k-Casc Assump ion is implied by he (k+ 1)-Pa y Di ie-Hellman
1We ac ually assume ha kand `a e conside ed as cons an s, i.e. hey do no depend on he secu i y pa ame e . O he wise,
o a gene al D`,k i is no so easy o sol e he D`,k-MDDH p oblem wi h he only help o a (k+ 1)-linea map, because
de e minan s o size k+ 1 could no be compu able in polynomial ime.
2
Assump ion ((k+ 1)-PDDH) [7] which s a es ha ([a1],...,[ak+1],[a1· · · ak+1]) ≈c([a1],...,[ak+1],[z]) ∈
G
k+2. Simila ly, k-SCasc is implied by he (k+1)-Exponen Di ie-Hellman Assump ion ((k+1)-EDDH) [28]
which s a es ha ([a],[ak+1]) ≈c([a],[z]) ∈
G
2. Figu e 1 on page 11 gi es an o e iew o e he ela ions
be ween he di e en assump ions.
Uniqueness o One-Pa ame e Family. The mos na u al and use ul D`,k-MDDH assump ions a e
hose wi h `=k+ 1 and he en ies o he ma ices gene a ed by D`,k a e polynomials o deg ee one
in some pa ame e s. Among hem, he mos compac co epond o he one-pa ame e dis ibu ions. As
no el con ibu ion wi h espec o [16], in Sec ion 4 we show ha k-ILin and k-SCasc a e igh ly equi alen .
Mo eo e , we p o e ha e e y Dk-MDDH assump ion de ined by uni a ia e polynomials o deg ee one is
igh ly equi alen o k-SCasc, so we can see k-SCasc as a so o canonical compac Ma ix DH assump ion.
F om he equi alence p oo be ween k-ILin and k-SCasc one can easily cons uc a educ ion om k-SCasc
o k-Lin.
1.2 Basic Applica ions
We belie e ha all schemes based on 2-Lin can be shown o wo k o any Ma ix Assump ion. Consequen ly,
a la ge class o known schemes can be ins an ia ed mo e e icien ly wi h he new mo e compac decisional
assump ions, while o e ing he same gene ic secu i y gua an ees. To suppo his belie , in Sec ion 5 we
show how o cons uc some undamen al p imi i es based on any Ma ix Assump ion. All cons uc ions a e
pu ely algeb aic and he e o e e y easy o unde s and and p o e.
•Public-key Enc yp ion. We build a key-encapsula ion mechanism wi h secu i y agains passi e
ad e sa ies om any D`,k-MDDH Assump ion. The public-key is [A], he ciphe ex consis s o he
i s kelemen s o [z] = [A~ ], he symme ic key o he las `−kelemen s o [z]. Passi e secu i y
immedia ely ollows om D`,k-MDDH.
•Hash P oo Sys ems. We build a smoo h p ojec i e hash p oo sys em (HPS) om any D`,k-MDDH
Assump ion. I is well-known ha HPS imply chosen-ciphe ex secu e enc yp ion [13], passwo d-
au hen ica ed key-exchange [20], ze o-knowledge p oo s [1], and many o he hings.
•Pseudo-Random Func ions. Gene alizing he Nao -Reingold PRF [6, 37], we build a pseudo- andom
unc ion PRF om any D`,k-MDDH Assump ion. The sec e -key consis s o ans o ma ion ma ices
T1,...,Tn(de i ed om independen ins ances Ai,j ← D`,k) plus a ec o ~
ho g oup elemen s. Fo
x∈ {0,1}nwe de ine PRFK(x) = hQi:xi=1 Ti·~
hi. Using he andom sel - educibili y o he D`,k-
MDDH Assump ion, we gi e a igh secu i y p oo .
•G o h-Sahai Non-In e ac i e Ze o-Knowledge P oo s. G o h and Sahai [21] p oposed e y ele-
gan and e icien non-in e ac i e ze o-knowledge (NIZK) and non-in e ac i e wi ness-indis inguishable
(NIWI) p oo s ha wo k di ec ly o a wide class o languages ha a e ele an in p ac ice. We show
how o ins an ia ia e hei p oo sys em based on any D`,k-MDDH Assump ion. While he size o he
p oo s depends only on `and k, he CRS and e i ica ion depends on he ep esen a ion size o he
Ma ix Assump ions. The e o e ou new ins an ia ions o e imp o ed e iciency o e he 2-Lin-based
cons uc ion om [21]. This applica ion in pa icula highligh s he use ulness o he Ma ix Assump-
ion o desc ibe in a compac way many ins an ia ions o a scheme: ins ead o ha ing o speci y he
cons uc ions o he DDH and he 2-Lin assump ions sepa a ely [21], we can eco e hem as a special
case o a gene al cons uc ion.
Mo e E icien P oo s o CRS Dependen Languages. In Sec ion 6 we p o ide mo e e icien
NIZK p oo s o conc e e na u al languages which a e dependen on he common e e ence s ing. Mo e
speci ically, he common e e ence s ing o he D`,k-MDDH ins an ia ion o G o h-Sahai p oo s o Sec ion
5.4 includes as pa o he commi men keys he ma ix [A], whe e A∈
Z
`×k
q← D`,k. We gi e mo e
e icien p oo s o se e al languages ela ed o A. Al hough a i s glance he languages conside ed may
3

seem qui e es ic ed, hey na u ally appea in many applica ions, whe e ypically Ais he public key o
some enc yp ion scheme and one wan s o p o e s a emen s abou ciphe ex s. Mo e speci ically, we ob ain
imp o emen s o se e al kinds o s a emen s, namely:
•Subg oup Membe ship P oo s. We gi e mo e e icien p oo s in he language LA,
G
,P:= {[A~ ],~ ∈
Z
k
q} ⊂
G
`. To quan i y some conc e e imp o emen , in he 2-Lin case, ou p oo s o membe ship a e
hal o he size o a s anda d G o h-Sahai p oo and hey equi e only 6 g oups elemen s. We s ess
ha his imp o emen is ob ained wi hou in oducing any new compu a ional assump ion. As an
example o applica ion, conside o ins ance he enc yp ion scheme de i ed om ou KEM based on
any D`,k-MDDH Assump ion, whe e he public key is some ma ix [A], A← D`,k. To see which kind
o s a emen s can be p o ed using ou esul , no e ha a ciphe ex is a e andomiza ion o ano he
one only i hei di e ence is in LA,
G
,P. The same holds o p o ing ha wo commi men s wi h he
same key hide he same alue o o showing in a publicly e i iable manne ha he ciphe ex o
ou enc yp ion scheme opens o some known message [m]. This imp o emen has a signi ican impac
on ecen esul s, like [17, 35], and we hink many mo e examples can be ound. In e es ingly, in
independen wo k, a numbe o esul s ([25, 26, 31, 34]) ha e cons uc ed e en mo e e icien p oo s
in linea subspaces by also exploi ing he dependency o he common e e ence s ing and he ma ix
which gene a es he space. We no e ha al hough in all hese wo ks p oo s a e sho e , his is a
he cos o ha ing only compu a ionally sound p oo s, while ou esul s e ain he pe ec soundness
inhe i ed om G o h Sahai p oo s.
•Ciphe ex Validi y and Plain ex Equali y. Simila echniques apply o ge mo e e icien p oo s
o s a emen s which na u ally appea when one wan s o p o e ha a ciphe ex is alid and ha wo
ciphe ex s enc yp ed wi h di e en public keys open o he same plain ex , e.g., when using Nao -Yung
echniques o ob ain chosen-ciphe ex secu i y [39], like in he enc yp ion schemes o [10, 15, 22, 27].
2 P elimina ies
2.1 No a ion
Fo n∈
N
, we w i e 1n o he s ing o nones. Mo eo e , |x|deno es he leng h o a bi s ing x, while |S|
deno es he size o a se S. Fu he , s←Sdeno es he p ocess o sampling an elemen s om Suni o mly
a andom. Fo an algo i hm A, we w i e z←A(x, y, . . .) o indica e ha Ais a (p obabilis ic) algo i hm
ha ou pu s zon inpu (x, y, . . .). I Ais a ma ix we deno e by aij he en ies and ~ai he column ec o s.
2.2 Rep esen ing Elemen s in G oups
Le Gen be a p obabilis ic polynomial ime (pp ) algo i hm ha on inpu 1λ e u ns a desc ip ion G=
(
G
, q, P) o a cyclic g oup
G
o o de q o a λ-bi p ime qand a gene a o Po
G
. Mo e gene ally, o any
ixed k≥1, le MGenkbe a pp algo i hm ha on inpu 1λ e u ns a desc ip ion MGk= (
G
,
G
Tk, q, ek,P),
whe e
G
and
G
Tka e cyclic addi i e g oups o p ime-o de q,Pa gene a o o
G
, and ek:
G
k→
G
Tk
is a (non-degene a ed, e icien ly compu able) k-linea map. Fo k= 2 we de ine PGen := MGen2 o be a
gene a o o a bilinea g oup PG = (
G
,
G
T, q, e, P).
Fo an elemen a∈
Z
qwe de ine [a] = aPas he implici ep esen a ion o ain
G
. Mo e gene ally, o a
ma ix A= (aij)∈
Z
n×m
qwe de ine [A] as he implici ep esen a ion o Ain
G
and [A]Tkas he implici
ep esen a ion o Ain
G
Tk:
[A] := 

a11P... a1mP
an1P... anmP
∈
G
n×m,[A]Tk:= 

a11PTk... a1mPTk
an1PTk... anmPTk

∈
G
n×m
Tk,
whe e PTk=ek(P,...,P)∈
G
Tk.
4
When alking abou elemen s in
G
and
G
Tkwe will always use his implici no a ion, i.e., we le [a]∈
G
be an elemen in
G
o [b]Tkbe an elemen in
G
Tk. No e ha om [a]∈
G
i is gene ally ha d o compu e
he alue a(disc e e loga i hm p oblem in
G
). Fu he , om [b]Tk∈
G
Tki is ha d o compu e he alue
b∈
Z
q(disc e e loga i hm p oblem in
G
Tk) o he alue [b]∈
G
(pai ing in e sion p oblem). Ob iously,
gi en [a]∈
G
, [b]Tk∈
G
Tk, and a scala x∈
Z
q, one can e icien ly compu e [ax]∈
G
and [bx]Tk∈
G
Tk.
Also, all unc ions and ope a ions ac ing on
G
and
G
Tkwill be de ined implici ly. Fo example, when
e alua ing a bilinea pai ing e:
G
×
G
→
G
Tin [a],[b]∈
G
we will use again ou implici ep esen a ion
and w i e [z]T:= e([a],[b]). No e ha e([a],[b]) = [ab]T, o all a, b ∈
Z
q.
2.3 S anda d Di ie-Hellman Assump ions
Le Gen be a pp algo i hm ha on inpu 1λ e u ns a desc ip ion G= (
G
, q, P) o cyclic g oup
G
o
p ime-o de qand a gene a o Po
G
. Simila ly, le PGen be a pp algo i hm ha e u ns a desc ip ion
PG = (
G
,
G
T, q, e, P) o a pai ing g oup. We in o mally ecall a numbe o p e iously conside ed Decisional
Di ie-Hellman Assump ions.
•Di ie-Hellman (DDH) Assump ion. I is ha d o dis inguish (G,[x],[y],[xy]) om (G,[x],[y],[z]),
o G= (
G
, q, P)←Gen,x, y, z ←
Z
q.
•k-Linea (k-Lin) Assump ion [3, 23, 45]. I is ha d o dis inguish (G,[x1],[x2], . . . [xk],[ 1x1],
[ 2x2], . . . [ kxk],[ 1+· · · + k]) om (G,[x1],[x2], . . . [xk],[ 1x1],[ 2x2], . . . [ kxk],[z]), o G ← Gen,
x1, . . . , xk, 1, . . . , k, z ←
Z
q. Clea ly, 1-Lin =DDH.
•Bilinea Di ie-Hellman (BDDH) Assump ion [4]. I is ha d o dis inguish (PG,[x],[y],[z],[xyz]T)
om (PG,[x],[y],[z],[w]T), o PG ← PGen,x, y, z, w ←
Z
q.
•k-Mul ilinea Di ie-Hellman (k-MLDDH) Assump ion [8]. Gi en k-linea g oup gene a o
MGenki is ha d o dis inguish (MGk,[x1], . . . [xk+1],[x1· · · xk+1]Tk) om (MGk,[x1], . . . [xk+1],[z]Tk),
o MGk←MGenk,x1, . . . , xk+1, z ←
Z
q. Clea ly, 2-MLDDH =BDDH.
•k-Pa y Di ie-Hellman (k-PDDH) Assump ion. I is ha d o dis inguish (G,[x1],[x2], . . . [xk],[x1· · · xk])
om (G,[x1],[x2],...,[xk],[z]), o G ← Gen,x1, . . . , xk, z ←
Z
q. 2-PDDH =DDH and 3-PDDH was
p oposed in [7].
•k-Exponen Di ie-Hellman (k-EDDH) Assump ion [28, 47]. I is ha d o dis inguish (G,[x],[xk])
om (G,[x],[z]), o G ← Gen,x, z ←
Z
q.
2.4 Key Encapsula ion Mechanisms
Akey-encapsula ion mechanism KEM = (Gen,Enc,Dec) wi h key-space K(λ) consis s o h ee polynomial-
ime algo i hms (PTAs). Via (pk,sk)←Gen(1λ) he andomized key-gene a ion algo i hm p oduces pub-
lic/sec e keys o secu i y pa ame e λ∈
N
; ia (K, c)←Enc(pk) he andomized encapsula ion algo i hm
c ea es a uni o mly dis ibu ed symme ic key K∈ K(λ) oge he wi h a ciphe ex c; ia K←Dec(sk, c)
he possesso o sec e key sk dec yp s ciphe ex c o ge back a key Kwhich is an elemen in Ko a
special ejec ion symbol ⊥. Fo consis ency, we equi e ha o all λ∈
N
, and all (K, c)←Enc(pk) we ha e
P [Dec(sk, c) = K] = 1, whe e he p obabili y is aken o e he choice o (pk,sk)←Gen(1λ), and he coins
o all he algo i hms in he exp ession abo e.
Fo IND-CPA secu i y we equi e ha he dis ibu ion (pk,(c, K)) is compu a ionally indis inguishable
om (pk,(c, K0)), whe e (pk,sk)←Gen(1λ), (K, c)←Enc(pk), and K0← K(λ). An IND-CPA secu e KEM
implies an IND-CPA secu e publick-key enc yp ion (PKE) scheme by combining i wi h a one- ime secu e
symme ic ciphe (DEM).
5
2.5 Hash P oo Sys ems
We ecall he no ion o hash p oo sys ems as in oduced by C ame and Shoup [13].
Le C,Kbe se s and V ⊂ C a language. In he con ex o public-key enc yp ion (and iewing a hash
p oo sys em as a key encapsula ion mechanism (KEM) [14] wi h “special algeb aic p ope ies”) one may
hink o Cas he se o all ciphe ex s,V ⊂ C as he se o all alid (consis en ) ciphe ex s, and Kas he
se o all symme ic keys. Le Λsk :C → K be a hash unc ion indexed wi h sk ∈ SK, whe e SK is a se . A
hash unc ion Λsk is p ojec i e i he e exis s a p ojec ion µ:SK → PK such ha µ(sk)∈ PK de ines he
ac ion o Λsk o e he subse V. Tha is, o e e y c∈ V, he alue K= Λsk (c) is uniquely de e mined by
µ(sk) and c. In con as , no hing is gua an eed o c∈ C V, and i may no be possible o compu e Λsk (c)
om µ(sk) and c. The p ojec i e hash unc ion is (pe ec ly) uni e sal1i o all c∈ C V,
(pk,Λsk (c)) ≡(pk, K) (2)
whe e in he abo e pk =µ(sk) o sk ← SK and K← K, and he symbol ≡s ands o equali y o he wo
dis ibu ions.
A hash p oo sys em HPS = (Pa am,Pub,P i ) consis s o h ee algo i hms whe e he andomized algo-
i hm Pa am(1λ) gene a es ins ances o pa ams = (S,K,C,V,PK,SK,Λ(·):C → K, µ :SK → PK), whe e S
may con ain some addi ional s uc u al pa ame e s such as he g oup desc ip ion. The de e minis ic public
e alua ion algo i hm Pub inpu s he p ojec ion key pk =µ(sk), c∈ V and a wi ness wo he ac ha c∈ V
and e u ns K= Λsk (c). The de e minis ic p i a e e alua ion algo i hm inpu s sk ∈ SK and e u ns Λsk (c),
wi hou knowing a wi ness. We u he assume he e a e e icien algo i hms gi en o sampling sk ∈ SK
and sampling c∈ V uni o mly oge he wi h a wi ness w.
As compu a ional p oblem we equi e ha he subse membe ship p oblem is ha d in HPS which means
ha he wo elemen s cand c0a e compu a ionally indis inguishable, o uni o m c∈ V and uni o m c0∈ C V.
2.6 Pseudo-Random Func ions
A pseudo- andom unc ion PRF = (Gen,F) wi h espec o ange R=R(λ) and message space M=M(λ)
consis s o wo algo i hms, whe e he andomized algo i hm Gen(1λ) gene a es a symme ic key Kand he
de e minis ic e alua ion algo i hm FK(x) ou pu s a alue in R, o all x∈ M. Fo secu i y we equi e ha
an ad e sa y making polynomially many que ies o an o acle O(·), he ou pu o o acle O(x) = FK(x) o a
ixed key K←Gen(1λ) is compu a ionally indis inguishable om O(x) = (x), whe e is chosen uni o mly
om all unc ions om mapping M o R(i.e., (x) ou pu s uni o m elemen s in R).
3 Ma ix DH assump ions
3.1 De ini ion
De ini ion 1. Le `, k ∈
N
wi h `>k. We call D`,k a ma ix dis ibu ion i i ou pu s (in poly ime, wi h
o e whelming p obabili y) ma ices in
Z
`×k
qo ull ank k. We de ine Dk:= Dk+1,k.
Fo simplici y we will also assume ha , wlog, he i s k ows o A← D`,k o m an in e ible ma ix.
We de ine he D`,k-ma ix p oblem as o dis inguish he wo dis ibu ions ([A],[A~w]) and ([A],[~u]), whe e
A← D`,k,~w ←
Z
k
q, and ~u ←
Z
`
q.
De ini ion 2 (D`,k-Ma ix Di ie-Hellman Assump ion D`,k-MDDH).Le D`,k be a ma ix dis ibu ion.
We say ha he D`,k-Ma ix Di ie-Hellman (D`,k-MDDH) Assump ion holds ela i e o Gen i o all pp
ad e sa ies D,
Ad D`,k ,Gen(D) = P [D(G,[A],[A~w]) = 1] −P [D(G,[A],[~u]) = 1] = negl(λ),
whe e he p obabili y is aken o e G= (
G
, q, P)←Gen(1λ),A← D`,k, ~w ←
Z
k
q, ~u ←
Z
`
qand he coin osses
o ad e sa y D.
6
De ini ion 3. Le D`,k be a ma ix dis ibu ion. Le A0be he i s k ows o Aand A1be he las `−k
ows o A. The ma ix T∈
Z
(`−k)×k
qde ined as T=A1A−1
0is called he ans o ma ion ma ix o A.
We no e ha using he ans o ma ion ma ix, one can al e na i ely de ine he ad an age om De ini-
ion 2 as
Ad D`,k ,Gen(D) = P [D(G,A0
TA0,"~
h
T~
h#) = 1] −P [D(G,A0
TA0,"~
h
~u#) = 1],
whe e he p obabili y is aken o e G= (
G
, q, P)←Gen(1λ), A← D`,k,~
h←
Z
k
q, ~u ←
Z
`−k
qand he coin
osses o ad e sa y D.
3.2 Basic P ope ies
We can gene alize De ini ion 2 o he m- old D`,k-MDDH Assump ion as ollows. Gi en W←
Z
k×m
q o
some m≥1, we conside he p oblem o dis inguishing he dis ibu ions ([A],[AW]) and ([A],[U]) whe e
U←
Z
`×m
qis equi alen o mindependen ins ances o he p oblem (wi h he same Abu di e en ~wi).
This can be p o ed h ough a hyb id a gumen wi h a loss o min he educ ion, o , wi h a igh educ ion
(independen o m) ia andom sel - educibili y.
Lemma 1 (Random sel educibili y).Fo any ma ix dis ibu ion D`,k,D`,k-MDDH is andom sel - educible.
Conc e ely, o any m,
Ad m
D`,k,Gen(D0)≤


m·Ad D`,k ,Gen(D) 1 ≤m≤`−k
(`−k)·Ad D`,k ,Gen(D) + 1
q−1m>`−k,
whe e
Ad m
D`,k,Gen(D0) = P [D0(G,[A],[AW]) = 1] −P [D0(G,[A],[U]) = 1],
and he p obabili y is aken o e G= (
G
, q, P)←Gen(1λ),A← D`,k,W←
Z
k×m
q,U←
Z
`×m
qand he coin
osses o ad e sa y D0.
P oo . The case 1 ≤m≤`−kcomes om a na u al hyb id a gumen , while he case m>`−kis ob ained
om he inequali y
Ad m
D`,k,Gen(D0)≤Ad `−k
D`,k,Gen(D) + 1
q−1.
To p o e i , we show ha he e exis s an e icien ans o ma ion o any ins ance ([A],[Z]) o he (`−k)- old
D`,k-MDDH p oblem in o ano he ins ance ([A],[Z0]) o he m- old p oblem, wi h o e whelming p obabili y.
In pa icula , we se Z0=AR +ZC, o andom ma ices R←
Z
k×m
qand C←
Z
(`−k)×m
q. On he one
hand, i Z=AW hen Z0=AW0 o W0=R+WC, which is uni o mly dis ibu ed in
Z
k×m
q. On he
o he hand, i Z=Uis uni o m hen A|Uis ull- ank wi h p obabili y a leas 1 −1/(q−1). In ha case,
Z0=AR +UC is uni o mly dis ibu ed in
Z
`×m
q, which p o es he abo e inequali y.
We ema k ha , gi en [A],[~z] he abo e lemma can only be used o e- andomize he alue [~z]. In o de
o e- andomize he ma ix [A] we need ha one can sample ma ices Land Rsuch ha A0=LAR looks
like an independen ins ance A0← D`,k. In all o ou example dis ibu ions we a e able o do his.
Due o i s linea i y p ope ies, he D`,k-MDDH assump ion does no hold in (k+1)-linea g oups, assuming
ha kis cons an , i.e. i does no depend on he secu i y pa ame e 2.
Lemma 2. Le D`,k be any ma ix dis ibu ion. Then he D`,k-Ma ix Di ie-Hellman Assump ion is alse
in (k+ 1)-linea g oups.
2I kg ows linea ly wi h he secu i y pa ame e , compu ing de e minan s o size k+1 in
G
could in gene al ake exponen ial
ime. Howe e , o he pa icula ma ices in he o hcoming examples (excep o he uni o m dis ibu ion) he associa ed
de e minan s a e s ill e icien ly compu able, and he Ma ix DH Assump ion is also alse in (k+ 1)-linea g oups.
7
5.2 Hash P oo Sys ems
Le D`,k be a ma ix dis ibu ion. We build a uni e sal1hash p oo sys em HPS = (Pa am,Pub,P i ), whose
ha d subse membe ship p oblem is based on he D`,k Ma ix Di ie-Hellman Assump ion.
•Pa am(1λ) uns G ← Gen(1λ) and picks A← D`,k. De ine he language
V=VA={[~c]=[A~w]∈
G
`:~w ∈
Z
k
q}⊆C=
G
`.
The alue ~w ∈
Z
k
qis a wi ness o [~c]∈ V. Le SK =
Z
`
q,PK =
G
k, and K=
G
. Fo sk =~x ∈
Z
`
q,
de ine he p ojec ion µ(sk)=[~x>A]∈
G
k. Fo [~c]∈ C and sk ∈ SK we de ine
Λsk ([~c]) := [~x>·~c].(3)
The ou pu o Pa am is pa ams =S= (G,[A]),K,C,V,PK,SK,Λ(·)(·), µ(·).
•P i (sk,[~c]) compu es [K]=Λsk ([~c]).
•Pub(pk,[~c], ~w). Gi en pk =µ(sk) = [~x>A], [~c]∈ V and a wi ness ~w ∈
Z
k
qsuch ha [~c] = [A·~w] he
public e alua ion algo i hm Pub(pk,[~c], ~w) compu es [K]=Λsk ([~c]) as
[K] = [(~x>·A)·~w].
Co ec ness ollows by (3) and he de ini ion o µ. Clea ly, unde he D`,k-Ma ix Di ie-Hellman Assump ion,
he subse membe ship p oblem is ha d in HPS.
We now show ha Λ is a uni e sal1p ojec i e hash unc ion. Le [~c]∈ C V be an elemen ou side o he
language. Then he ma ix (A||~c)∈
Z
`×(k+1)
qis o ull ank k+1 and consequen ly (~x>·A||~x>·~c)≡(~x>A||u)
o ~x ←
Z
k
qand u←
Z
q. Hence, (pk,Λsk ([~c]) = ([~x>A],[~x>~c]) ≡([~x>A],[u]) = ([~x>A],[K]).
We ema k ha Λ can be ans o med in o a uni e sal2p ojec i e hash unc ion by applying a ou -wise
independen hash unc ion [30]. Al e na i ely, one can cons uc a compu a ional e sion o a uni e sal2
p ojec i e hash unc ion as ollows. Le SK = (
Z
`
q)2,PK = (
G
k)2, and K=
G
. Fo sk = (~x1, ~x2)∈(
Z
`
q)2,
de ine he p ojec ion µ(sk)=[~x>
1A, ~x>
2A]∈(
G
k)2. Fo [~c]∈ C and sk ∈ SK, de ine Λsk ([~c]) := [( ~x>
1+~x>
2)·~c],
whe e =H(~c) and H:C →
Z
qis a collision- esis an hash unc ion. The co esponding P i and Pub
algo i hms a e adap ed acco dingly. I is easy o e i y ha o all alues [~c1],[~c2]∈ C V wi h H(~c1)6=H(~c2),
we ha e (pk,Λsk ([~c1],Λsk ([~c2]) ≡(pk,[K1],[K2]), o K1, K2←
Z
q.
5.3 Pseudo-Random Func ions
Le Gen be a g oup gene a ing algo i hm and D`,k be a ma ix dis ibu ion ha ou pu s a ma ix o e
Z
`×k
q
such ha he i s k- ows o m an in e ible ma ix wi h o e whelming p obabili y. We de ine he ollowing
pseudo- andom unc ion PRFGen,D`,k = (Gen,F) wi h message space M={0,1}nand ange R=
G
k. Fo
simplici y we assume ha `−kdi ides k.
•Gen(1λ) uns G ← Gen(1λ), ~
h∈
Z
k
q, and Ai,j ← D`,k o i= 1, . . . , n and j= 1, . . . , := k/(`−k)
and compu es he ans o ma ion ma ices Ti,j ∈
Z
(`−k)×k
qo Ai,j ∈
Z
`×k
q(c . De ini ion 3). Fo
i= 1, . . . , n de ine he agg ega ed ans o ma ion ma ices
Ti=


Ti,1
.
.
.
Ti,


∈
Z
k×k
q
The key is de ined as
K= (G,~
h, T1,...,Tn).
14

•FK(x) compu es
FK(x) = "Y
i:xi=1
Ti·~
h#∈
G
k.
PRFGen,Lk(i.e., se ing D`,k =Lk) is he PRF om Lewko and Wa e s [33]. A mo e e icien PRF om he
k-SCasc Assump ion is gi en in Appendix E.2.
No e ha he elemen s T1,...,T o he sec e -key consis o he ans o ma ion ma ices o indepen-
den ly sampled ma ices Ai,j. In e es ingly, o a numbe o dis ibu ions D`,k he dis ibu ion o he
ans o ma ion ma ix Tis he same. Fo example, he ans o ma ion ma ix o Lkconsis s o a uni o m
ow ec o , so does he ans o ma ion ma ix o Ckand o Uk+1,k. Consequen ly, PRFGen,Ck=PRFGen,Lk=
PRFGen,Uk+1,k and in ligh o he heo em below, PRFGen,Lkp oposed by Lewko and Wa e s can also be p o ed
on he Uk+1,k-MDDH assump ion, he weakes among all MDDH assump ions o ma ching dimensions.
Theo em 12. Unde he D`,k-MDDH Assump ion PRFGen,D`,k is a secu e pseudo- andom unc ion.
The p oo is based on he augmen ed cascade cons uc ion o Boneh e al. [6]. He e we gi e a di ec
sel -con ained p oo . We i s s a e and p o e he ollowing lemma.
Lemma 13. Le Qbe a polynomial. Unde he D`,k-MDDH Assump ion,
" ~
h1
ˆ
T~
h1!,..., ~
hQ
ˆ
T~
hQ!#∈
G
2k×Q
is compu a ionally indis inguishable om a uni o m [H]∈
G
2k×Q, whe e ~
hi←
Z
k
q,
ˆ
T=


ˆ
T1
.
.
.
ˆ
T


∈
Z
k×k
q,
and ˆ
Tj(1≤j≤ ) a e he ans o ma ion ma ices o Aj← D`,k.
P oo . By a hyb id a gumen o e j= 1, . . . , i is su icien o show ha
" ~
h1
ˆ
T1~
h1!,..., ~
hQ
ˆ
T1~
hQ!#∈
G
`×Q
is compu a ionally indis inguishable om a uni o m [H1]←
G
`×Q, i.e., o one single ans o ma ion ma ix
ˆ
T1o A1← D`,k. This in u n ollows di ec ly by Lemma 1 ( andom sel - educibili y o D`,k-MDDH). No e
ha he o e all loss in he secu i y educ ion is k= ·(`−k), whe e he ac o s ems om he hyb id
a gumen and he ac o `−ks ems om Lemma 1.
P oo o Theo em 12. Fo x∈ {0,1}nand 0 ≤µ≤n, de ine su ixµ(x) as he µ- h su ix o x, i.e.,
su ixµ(x) := (xn−µ+1, . . . , xn). We make he con en ion ha su ix0(x) = ε, he emp y s ing.
We will use a hyb id a gumen o e n, he bi leng h o x. In Hyb id µ(0 ≤µ≤n), le RFµ:{0,1}µ→
Z
k
q
be a uly andom unc ion and de ine he o acle
Oµ(x) = 

Y
1≤i≤n−µ
i:xi=1
Ti·RFµ(su ixµ(x))

∈
G
k,
whe e he Tia e de ined as in he eal scheme. Wi h his de ini ion we ha e ha O0(x) = FK(x) (by
de ining RF(ε) := ~
h) and On(x) is a uly andom unc ion. I lea es o show ha he ou pu o o acle
15
Oµ(·) is compu a ionally indis inguishable om Oµ+1(·). Fo he educ ion we use Lemma 13, whe e Qis
he maximal numbe o que ies o o acle Omade by he PRF ad e sa y. I inpu s
" ~
h1
0
~
h1
1!,..., ~
hQ
0
~
hQ
1!#,
whe e ~
hj
1=ˆ
T~
hj
0o uni o mly andom. Nex , i picks Ti(1 ≤i≤n−µ) and implici ly de ines Tn−µ=ˆ
T.
On he j- h que y xj= (xj
1, . . . , xj
n) (1 ≤j≤Qand wlog all que ies a e dis inc ) o o acle O, i e u ns
O(xj) = 


Y
1≤i≤n−µ−1
i:xj
i=1
Ti·~
hj
xj
n−µ



.
I ~
hj
1=ˆ
T~
hj
0, hen
RFµ(su ixµ(xj)) = ~
hj
0
is a andom unc ion on µbi s and
O(xj) = 


Y
1≤i≤n−µ
i:xj
i=1
Ti·~
hj
0


=


Y
1≤i≤n−µ
i:xj
i=1
Ti·RFµ(su ixµ(xj))



pe ec ly simula es o acle Oµ om Hyb id µ.
I ~
hj
1is uni o m and independen om ~
hj
0, hen
RFµ+1(su ixµ+1(xj)) = ~
hj
xj
n−µ
is a andom unc ion on µ+ 1 bi s and
O(xj) = 


Y
1≤i≤n−µ−1
i:xj
i=1
Ti·RFµ+1(su ixµ+1(xj))



pe ec ly simula es o acle Oµ+1 om Hyb id µ+ 1.
We ema k ha he loss in he educ ion is independen o he numbe o que ies Q o o acle O, i.e., he
educ ion loses a ac o o nk, whe e he ac o ns ems om he abo e hyb id a gumen , and he ac o k
om Lemma 13.
5.4 G o h-Sahai Non-in e ac i e Ze o-Knowledge P oo s
G o h and Sahai ga e a me hod o cons uc non-in e ac i e wi ness-indis inguishable (NIWI) and non-
in e ac i e ze o-knowledge (NIZK) p oo s o sa is iabili y o a se o equa ions in a bilinea g oup PG. (Fo
o mal de ini ions o NIWI and NIZK p oo s we e e o [21].) The equa ions in he se can be o di e en
ypes, bu hey can be w i en in a uni ied way as
n
X
j=1
(aj,yj) +
m
X
i=1
(xi, bi) +
m
X
i=1
n
X
j=1
(xi, γijyj) = , (4)
whe e A1, A2, ATa e
Z
q-modules, ~
x∈Am
1,~
y∈An
2a e he a iables, ~a ∈An
1,~
b∈Am
2,Γ= (γij)∈
Z
m×n
q,
∈ATa e he cons an s and :A1×A2→ATis a bilinea map. Mo e speci ically, conside ing only
symme ic bilinea g oups, equa ions a e o one o hese ypes:
16
i) Pai ing p oduc equa ions, wi h A1=A2=
G
,AT=
G
T, ([x],[y]) = [xy]T∈
G
T.
ii) Mul i-scala mul iplica ion equa ions, wi h A1=
Z
q,A2=AT=
G
, (x,[y]) = [xy]∈
G
.
iii) Quad a ic equa ions in
Z
q, wi h A1=A2=AT=
Z
q, (x,y) = xy ∈
Z
q.
O e iew. The GS p oo sys em allows o cons uc NIWI and NIZK p oo s o sa is iabili y o a se o
equa ions o he ype (4), i.e., p oo s ha he e is a choice o a iables — he wi ness — sa is ying all
equa ions simul aneously. The p o e gi es o he e i ie a commi men o each elemen o he wi ness
and some addi ional in o ma ion, he p oo . Commi men s and p oo sa is y some ela ed se o equa ions
compu able by he e i ie because o hei algeb aic p ope ies. We s ess ha o compu e he p oo , he
p o e needs he andomness which i used o c ea e he commi men s. To gi e new ins an ia ions o GS
p oo s we need o speci y he dis ibu ion o he common e e ence s ing, which includes he commi men
keys and some maps whose pu pose is oughly o gi e some algeb aic s uc u e o he commi men space.
Commi men s. We will now cons uc commi men s o elemen s in
Z
qand
G
. The commi men key
[U] = ([~u1],...,[~uk+1]) ∈
G
`×(k+1) is o he o m
[U] = ([A||A~w] binding key (soundness se ing)
[A||A~w −~z] hiding key (WI se ing) ,
whe e A← D`,k,~w ←
Z
k
q, and ~z ∈
Z
`
q,~z /∈Im(A) is a ixed, public ec o . The wo ypes o commi men
keys a e compu a ionally indis inguishable based on he D`,k-MDDH Assump ion.
To commi o [y]∈
G
using andomness ~ ←
Z
k+1
qwe de ine maps ι:
G
→
Z
`
qand p:
G
`→
Z
qas
ι([y]) = y·~z, p([~c]) = ~
ξ>·~c, de ining com[U],~z([y]; ~ ) := [ι([y]) + U~ ]∈
G
`,
whe e ~
ξ∈
Z
`
qis an a bi a y ec o such ha ~
ξ>A=~
0 and ~
ξ>·~z = 1. No e ha , gi en [y], ι([y]) is
no e icien ly compu able, bu [ι([y])] is, and his su ices o compu e he commi men . On a binding key
(soundness se ing) we ha e ha p([ι([y])]) = y o all [y]∈
G
and ha p([~ui]) = 0 o all i= 1 . . . k + 1. So
p(com[U],~z([y];~ )) = ~
ξ>(~zy+U~ ) = ~
ξ>~zy+~
ξ>(A||A~w)~ =yand he commi men is pe ec ly binding. On
a hiding key (WI se ing), ι([y]) ∈Span(~u1, . . . , ~uk+1) o all [y]∈
G
which implies ha he commi men s
a e pe ec ly hiding.
To commi o a scala x∈
Z
qusing andomness ~s ←
Z
k
qwe de ine he maps ι0:
Z
q→
Z
`
qand p0:
G
`→
Z
q
as
ι0(x) = x·(~uk+1 +~z), p0([~c]) = ~
ξ>~c, de ining com0
[U],~z(x;~s) := [ι0(x) + A~s]∈
G
`.
whe e ~
ξis de ined as abo e. No e ha , gi en x,ι(x) is no e icien ly compu able, bu [ι(x)] is, and his
su ices o compu e he commi men . On a binding key (soundness se ing) we ha e ha p0([ι0(x)]) = x o
all x∈
Z
qand p0([~ui]) = 0 o all i= 1 . . . k so he commi men is pe ec ly binding. On a hiding key (WI
se ing), ι0(x)∈Span(~u1, . . . , ~uk) o all x∈
Z
q, which implies ha he commi men is pe ec ly hiding.
I will also be con enien o de ine a ec o o commi men s as com[U],~z([~
y]; R) = [ι([~
y>]) + UR] and
com0
[U],~z(~
x;S)=[ι0(~
x>) + AS], whe e [~
y]∈
G
m,~
x∈
Z
n
q,R←
Z
(k+1)×m
q,S←
Z
k×n
qand he inclusion maps
a e de ined componen -wise.
Inclusion and P ojec ion Maps. As we ha e seen, commi men s a e elemen s o
G
`. The main idea
o GS NIWI and NIZK p oo s is o gi e some algeb aic s uc u e o he commi men space (in his case,
G
`) so ha he commi men s o a solu ion in A1, A2o a ce ain se o equa ions sa is y a ela ed se o
equa ions in some la ge modules. Fo his pu pose, i [~
x]∈
G
`and [~
y]∈
G
`, we de ine he bilinea map
˜
F:
G
`×
G
`→
Z
`×`
qde ined implici ly as:
˜
F([~
x],[~
y]) = ~
x·~
y>,
17
as well as i s symme ic a ian F([~
x],[~
y]) = 1
2˜
F([~
x],[~
y])+ 1
2˜
F([~
y],[~
x]). Addi ionally, o any wo ow ec o s o
elemen s o
G
`o equal leng h [X]=[~
x1,...,~
x ] and [Y] = [~
y1,...,~
y ], we de ine he maps ˜
•,•associa ed
wi h ˜
Fand Fas [X]˜
•[Y]=[P
i=1 ˜
F([~
xi],[~
yi])]Tand [X]•[Y]=[P
i=1 F([~
xi],[~
yi])]T. To comple e he de ails
o he new ins an ia ion, we mus speci y o each ype o equa ion, o bo h F0=Fand F0=˜
F:
a) some maps ιTand pTsuch ha o all x∈A1,y∈A2,[~
x]∈
G
`,[~
y]∈
G
`,
F0([ι1(x)],[ι2(y)]) = ιT( (x,y)) and pT([F0([~
x],[~
y])]T) = (p1([~
x]), p2([~
y])),
whe e ι1,ι2a e ei he ιo ι0and p1,p2ei he [p] o p0, acco ding o he app op ia e A1, A2 o each
equa ion,
b) ma ices H1,...,Hη∈
Z
k1×k2
q, whe e k1,k2a e he numbe o columns o U1,U2 espec i ely and
which, in he wi ness indis inguishabili y se ing, a e a basis o all he ma ices which a e a solu ion o
he equa ion [U1H]•[U2]=[0]Ti F0=Fo [U1H]˜
•[U2]=[0]Ti F0=˜
F, whe e U1,U2a e ei he
Uo A, depending on he modules A1, A2. These ma ices a e necessa y o andomize he NIWI and
NIZK p oo s.
To p esen he ins an ia ions in concise o m, in he ollowing H ,s,m,n = (hij)∈
Z
m×n
qdeno es he ma ix
such ha h s =−1, hs = 1 and hij = 0 o (i, j)/∈ {( , s),(s, )}. In summa y, he elemen s which mus be
de ined a e:
•Pai ing p oduc equa ions. In his case, A1=A2=
G
,AT=
G
T,ι1=ι2=ι,p1=p2= [p],
U1=U2=Uand bo h o F0=Fand F0=˜
F,
ιT([z]T) = z·~z ·~z>∈
Z
`×`
qpT([Z]T)=[~
ξ>Z~
ξ]T,
whe e Z= (Zij)1≤i,j≤`∈
Z
`×`
q.The equa ion [UH]˜
•[U] = [0]Tadmi s no solu ion, while all he
solu ions o [UH]•[U]=[0]Ta e gene a ed by H ,s,k+1,k+11≤ <s≤k+1.
•Mul i-scala mul iplica ion equa ions. In his case, A1=
Z
q,A2=AT=
G
,ι1=ι0, ι2=ι,
p1=p0,p2= [p], U1=A,U2=Uand o bo h F0=˜
Fand F0=F,
ιT([z]) = F0([ι0(1)],[ι([z])]) pT([Z]T) = [~
ξ>Z~
ξ].
The equa ion [AH]˜
•[U] = [0]Tadmi s no solu ion, while all he solu ions o [AH]•[U] = [0]Ta e
gene a ed by H ,s,k,k+11≤ <s≤k.
•Quad a ic equa ions. In his case, A1=A2=AT=
Z
q,ι1=ι2=ι0,p1=p2=p0and
U1=U2=A, o bo h F0=˜
Fand F0=F, we de ine
ιT(z) = F0([ι0(1)],[ι0(z)]) pT([Z]T) = ~
ξ>Z~
ξ.
The equa ion [AH]˜
•[A] = [0]Tadmi s no solu ion, while all he solu ions o [AH]•[A] = [0]Ta e
gene a ed by H ,s,k,k1≤ <s≤k.
To a gue ha he equa ion [U1H]˜
•[U2] = [0]Tadmi s no solu ion, o each o he cases abo e, i is
su icien o a gue ha he ec o s ˜
F([~ui],[~uj]) a e linea ly independen . This holds ega dless o he ma ix
dis ibu ion D`,k om basic linea algeb a, since ˜
F([~ui],[~uj]) was de ined as he implici ep esen a ion o
he ou e p oduc o ~uiand ~ujand ~u1, . . . ,~uk+1 a e linea ly independen .
P oo and Ve i ica ion. Fo comple eness, we now desc ibe how do he p o e and he e i ie p oceed.
De ine k1, k2as he numbe o columns o U1,U2 espec i ely. On inpu PG, [U], ~z, a se o equa ions and
a se o wi nesses ~
x∈Am
1,~
y∈An
2 he p o e p oceeds as ollows:
18
D`,k-MDDH ins an ia ion elemen s o
G
elemen s o
Z
q
Commi men o a Va iable `0
Pai ing p oduc equa ion `(k+ 1) 0
- Linea equa ion: k+ 1 0
Mul i-scala mul iplica ion equa ion `(k+ 1) 0
- Linea equa ion wi h a iables in
G
0k+ 1
- Linea equa ion wi h a iables in
Z
qk0
Quad a ic equa ion `k 0
- Linea equa ion 0 k
Table 1: Size o he p oo s based on he D`,k-MDDH Assump ion.
1. Commi o ~
xand ~
yas
[C]=[ι1(~
x>) + U1R],[D]=[ι2(~
y>) + U2S]
whe e R←
Z
k1×m
q,S←
Z
k2×n
q.
2. Fo each equa ion o he ype (4), pick T←
Z
k1×k2
q, i←
Z
qand ou pu ([Π],[Θ]), de ined as:
[Π] := [ι2(~
b>)R>+ι2(~
y>)Γ>R>+U2SΓ>R>−U2T>+X
1≤i≤η
iU2H>
i]
[Θ] := [ι1(~a>)S>+ι1(~
x>)ΓS>+U1T]
The p oo desc ibed abo e is o a gene al equa ion, he same op imiza ions o special ypes o equa ion as
in he ull e sion o [21] apply. In pa icula , when he map used is he symme ic map F, he size o he
p oo can be educed. In addi ion, he size o he p oo can also be educed when all he elemen s in ei he
A1o A2a e cons an s. Taking hese op imiza ions in o accoun , we gi e he size o he commi men s and
he p oo o he di e en ypes o equa ions in Table 1.
To e i y a p oo , on inpu he commi men s [C], [D] and a p oo ([Π],[Θ]), he e i ie checks i
[ι1(~a>)] •0[D]+[C]•0[ι2(~
b>)] + [C]•0[DΓ>] = [ιT( )]T+ [U1]•0[Π]+[Θ]•0[U2],
whe e •0is ei he •o ˜
•, depending on whe he F0is Fo ˜
F. I he equa ion is sa is ied, he e i ie accep s
he p oo o his equa ion and ejec s o he wise. In gene al, he e i ica ion cos depends on `and k,
hough a bi migh be gained in pai ing compu a ions when using ba ch e i ica ion echniques and i some
componen s o he commi men keys a e i ial o a e epea ed, i.e. i he D`,k admi s sho ep esen a ion.
E iciency. We emphasize ha o D`,k =L2and ~z = (0,0,1)>and o D`,k =DDH and ~z = (0,1)>
(in he na u al ex ension o asymme ic bilinea g oups), we eco e he 2-Lin and he SXDH ins an ia ions
o [21]. While he size o he p oo s depends only on `and k, bo h he size o he CRS and he cos o
e i ica ion inc ease wi h RE
G
(D`,k). In pa icula , in e ms o e iciency, he SC2Assump ion is p e e able
o he 2-Lin Assump ion bu he main eason o conside mo e ins an ia ions o GS p oo s is o ob ain mo e
e icien p oo s o a la ge class o languages in Sec ion 6.
6 Mo e E icien P oo s o Some CRS Dependen Languages
Le [U] be he commi men key de ined in las sec ion as pa o a D`,k-MDDH ins an ia ion, o some
A← D`,k. In his sec ion, we show how o ob ain sho e p oo s o some languages ela ed o A. The
common idea o all he imp o emen s is o exploi he special s uc u e o he homomo phic commi men s
used in G o h-Sahai p oo s.
19

6.1 Mo e E icien Subg oup Membe ship P oo s
We i s show how o ob ain sho e p oo s o membe ship in he language LA,PG := {[A~ ],~ ∈
Z
k
q} ⊂
G
`.
In ui ion. Ou p oo s implici ly use he GS amewo k, al hough we ha e p e e ed o gi e he p oo s
wi hou using he GS no a ion. Indeed, he idea behind ou imp o emen is o exploi he special algeb aic
s uc u e o commi men s in GS p oo s, namely he obse a ion ha i [~
Φ] = [A~ ]∈ LA,PG hen [~
Φ] =
com0
[U],~z(0;~ ). The e o e, o p o e ha [~
Φ] ∈ LA,PG, we p oceed as i we we e gi ing a GS p oo o sa is abili y
o he equa ion x= 0 whe e he andomness used o he commi men o xis ~ . In pa icula , no commi men s
ha e o be gi en in he p oo , which esul s in sho e p oo s. To p o e ze o-knowledge we ew i e he
equa ion x= 0 as x·δ= 0. The eal p oo is jus a s anda d GS p oo wi h he commi men o δ= 1 being
ι0(1) = com[U](1;~
0), while in he simula ed p oo he apdoo allows o open ι0(1) as a commi men o 0,
so we can p oceed as i he equa ion was he i ial one x·0 = 0, o which i is easy o gi e a p oo o
sa is iabili y.
Rela ed Wo k. I is in e es ing o compa e in de ail wi h a ecen line o wo k aiming a ob aining e y
e icien a gumen s o membe ship in linea subspaces ([25, 26, 31, 34]) which also exploi s he dependency
o he common e e ence s ing and he space whe e one wan s o p o e membe ship in. Mo e speci ically,
hese wo ks cons uc NIZK a gumen s o membe ship in he space gene a ed by [A]∈
G
`×k, wi h pe ec
ze o-knowledge and compu a ional soundness. We compa e ou esul s wi h [31], who gi e wo di e en
cons uc ions which gene alize and simpli y p e ious esul s. In hei wo k, compu a ional soundness is
based on any Dm-MDDH Assump ion7. In he i s cons uc ion, he p oo size is m+ 1, he common
e e ence s ing mus include m` + (m+ 1)k+RE
G
(Dm) g oup elemen s and a desc ip ion o [A]. In he
second cons uc ion, which assumes ha [A] is d awn om a wi ness samplable dis ibu ion, he p oo size
is mand he common e e ence s ing mus include m`+mk +RE
G
(Dm) g oup elemen s, whe e Dmdeno es
he dis ibu ion o he i s m ows o he ma ices sampled acco ding o Dm, and a desc ip ion o [A].
Ou p oo , on he o he hand, has pe ec soundness, composable ze o-knowledge unde he D`,k-MDDH
Assump ion, p oo o size `k and apa om a desc ip ion o [A], he common e e ence s ing consis s o
only `elemen s o
G
.
6.1.1 Cons uc ion
De ine H:= {H∈
Z
k×k
q:H+H>=0}. Following he in ui ion gi en abo e, he ac ual cons uc ion looks
as ollows:
Se up. A he se up s age, some g oup PG = (
G
,
G
T, q, e, P)←PGen(1λ) is speci ied.
Common e e ence s ing. We de ine [U] = ([~u1],...,[~uk+1]) as [A||A~w +~z] in he soundness se ing
and [A||A~w] in he wi ness indis inguishabili y se ing, whe e A← D`,k,~w ←
Z
k
q, and ~z ∈
Z
`
q,~z /∈Im(A).
The common e e ence s ing is σ:= (PG,[U], ~z).
Simula ion apdoo . The simula ion apdoo τis he ec o ~w ∈
Z
k
q.
P o e . On inpu σ, a ec o [~
Φ] = [A~ ]∈ LA,PG and he wi ness ~ ∈
Z
k
q, he p o e chooses a ma ix
H← H and compu es
[Π] = [~uk+1~ >+AH].
Ve i ie . On inpu σ, [~
Φ],[Π], he e i ie checks i [~
Φ~u>
k+1 +~uk+1~
Φ>]T= [ΠA>+AΠ>]T.
Simula o . On inpu σ, [~
Φ], τ he simula o picks a ma ix H0← H and compu es
[Πsim]=[~
Φ~w>+AH0].
Theo em 14. Le A← D`,k, whe e D`,k is a ma ix dis ibu ion. The e exis s a Non-In e ac i e Ze o-
Knowledge P oo o he language LA,PG, wi h pe ec comple eness, pe ec soundness and composable ze o-
knowledge o k` g oup elemen s based on he D`,k-MDDH Assump ion.
7Ac ually, o be p ecise, soundness is based on a compu a ional a ian o he Dm-MDDH Assump ion.
20
The p oo ollows di ec ly by implici ly econs uc ing he same a gumen s which p o e he same p op-
e ies o he GS p oo sys em.
P oo . Fi s , i is clea ha unde he D`,k-MDDH Assump ion, he soundness and he WI se ing a e
compu a ionally indis inguishable.
Comple eness. To see comple eness, we see ha a eal p oo sa is ies he e i ica ion equa ion. Indeed,
in he soundness se ing, he le e m o he e i ica ion equa ion is:
[~
Φ~u>
k+1 +~uk+1~
Φ>]T= [A~ (A~w +~z)>+ (A~w +~z)(A~ )>]T
= [A(~ ~w>+~w~ >)A>+A~ ~z>+~z~ >A>]T
while he igh e m in he eal p oo is:
[ΠA>+AΠ>]T= [A(~w~ >+~w~ >)A>+A(H+H>)A>+A~ ~z>+~z~ >A>]T(5)
= [A(~ ~w>+~w~ >)A>+A~ ~z>+~z~ >A>]T.(6)
This p o es pe ec comple eness.
Soundness. Le ~
ξ∈
Z
`
qbe any ec o such ha ~
ξ>A=~
0, ~
ξ>~z = 1. This implies ha in he soundness
se ing, ~
ξ>~uk+1 = 1. The e o e, i [Π] is any p oo ha sa is ies he e i ica ion equa ion, mul iplying on
he le by ~
ξ>and he igh by ~
ξ,
~
ξ>[~
Φ~u>
k+1 +~uk+1~
Φ>]T~
ξ=~
ξ>[ΠA>+AΠ>]T~
ξ,
we ob ain
[~
ξ>~
Φ + ~
Φ>~
ξ]T= [0]T.(7)
Since [~
ξ>~
Φ + ~
Φ>~
ξ]T= 2[~
ξ>~
Φ]T, om his las equa ion i ollows ha [~
ξ>~
Φ]T= [0]T. This holds o any
ec o ~
ξsuch ha ~
ξ>A=~
0 and ~
ξ>~z = 1, which implies ha [Φ] ∈ LA,PG, which p o es pe ec soundness.
Composable Ze o-Knowledge. We will now see ha , in he wi ness indis inguishabili y se ing, bo h a
eal p oo and a simula ed p oo ha e he same dis ibu ion when [Φ] ∈ LA,PG. We i s no e ha hey bo h
sa is y he e i ica ion equa ion. Indeed, he le e m o he e i ica ion equa ion in he WI se ing is
[~
Φ~u>
k+1 +~uk+1~
Φ>]T= [A(~ ~w>+~w~ >)A>]T,
which is ob iously equal o he igh e m o he e i ica ion equa ion o he eal p oo ( ew i e equa ion
(5) in he WI se ing). On he o he hand, i [Φ] ∈ LA,PG, he igh e m o he e i ica ion equa ion o a
simula ed p oo is:
[ΠsimA>+AΠ>
sim]T= [A(~ ~w>+~w~ >)A>+A(H0+ (H0)>)A>]T
= [A(~ ~w>+~w~ >)A>]T,
o some H0∈ H.
We now a gue ha an hones ly gene a ed p oo [Π] and a simula ed p oo [Πsim] ha e he same dis i-
bu ion. By cons uc ion, he e exis some ma ices Θand Θ0such ha [Π] = [AΘ] and [Πsim] = [AΘ0].
Now, i [Π1] = [AΘ1] and [Π2] = [AΘ2] a e wo p oo s, eal o simula ed, which sa is y he e i ica ion
equa ion, hen necessa ily [(Π1−Π2)A>+A(Π1−Π2)]T= [A((Θ1−Θ2)+(Θ1−Θ2)>)A>]T= 0.
Since wi h o e whelming p obabili y, Ahas ank k, i mus hold ha (Θ1−Θ2)+ (Θ1−Θ2)>= 0, ha
is, i mus hold ha (Θ1−Θ2)∈ H. By cons uc ion, bo h o hones ly gene a ed p oo s [Π] and simula ed
p oo s hese di e ence is uni o mly dis ibu ed in H.
21
6.1.2 E iciency Compa ison and Applica ions
Fo he 2-Lin Assump ion, (`= 3, k = 2) ou p oo consis s o only 6 g oup elemen s, whe eas wi hou using
ou echnique he p oo consis s o 12 elemen s.8Mo e gene ally, To p o e ha [~
Φ] ∈ LA,PG, o some
A← D`,k wi h a GS ins an ia ion based on a (possibly un ela ed) D`0,k0-ma ix DH p oblem using s anda d
GS p oo s, one would p o e ha he ollowing equa ion is sa is iable o all i= 1 . . . `:
1[u1,i] + . . . + k[uk,i] = [Φi],(8)
ha is, one needs o p o e ha `linea equa ions wi h k a iables a e sa is ied. The e o e, acco ding o
Table 1, he e i ie mus be gi en k`0elemen s o
G
o he commi men s and `k0elemen s o
G
o he
p oo . On he o he hand, p o ing [~
Φ] ∈ LA,PG using ou app oach equi es `k elemen s o
G
, co esponding
o he size o he p oo o one quad a ic equa ion.
Applica ions. Fo a ypical applica ion scena io o Theo em 14, hink o [A] as pa o he public pa ame-
e s o he hash p oo sys em o Sec ion 5.2. P o ing ha a ciphe ex is well- o med is p o ing membe ship
in LA,PG. Ano he applica ion is o show ha wo ciphe ex s enc yp he same message unde he same
public key, a common p oblem in elec onic o ing o anonymous c eden ials. The e a e many o he se ings
in which subg oup membe ship p oblems na u ally appea , o ins ance he p oblem o ce i ying public keys
o gi en some plain ex m, he p oblem o p o ing ha a ce ain ciphe ex is an enc yp ion o [m]. We s ess
ha in ou cons uc ion he se up o he CRS can be buil on op o he enc yp ion key so ha p oo s can
be simula ed wi hou he dec yp ion key, which is essen ial o many o hese applica ions. Mo e conc e ely,
below we gi e wo applica ion examples.
Applica ion Example 1. The s anda d p oo o membe ship in LA,PG, when A←2-Lin based on he
same assump ion (wi h `=`0= 3, k=k0= 2), equi es 12 g oup elemen s, while wi h ou app oach only
6 elemen s a e equi ed9. This educes he ciphe ex size o one o he ins an ia ions o [35] om 15 o 9
g oup elemen s.
Applica ion Example 2. Wi h ou esul s we can also gi e a mo e e icien p oo o co ec opening o
he C ame Shoup ciphe ex . We b ie ly ecall he CS enc yp ion scheme based on he 2-Lin-Assump ion
([23, 45]). The public key consis s o he desc ip ion o some g oup Gand a uple [a1, a2, X1, X2, X3, X4, X5, X6]∈
G
8. Gi en a message [m]∈
G
, a ciphe ex is cons uc ed by picking andom , s ∈
Z
qand se ing
C:= [ (a1,0,1, X5, X1+αX3) + s(0, a2,1, X6, X2+αX4) + (0,0, m, 0,0)],
whe e αis he hash o some componen s o he ciphe ex and possibly some label. To p o e ha a ciphe ex
opens o a (known) message [m], subs ac [m] om he hi d componen o he ciphe ex and p o e
membe ship in LAα,PG, whe e Aαis de ined as:
Aα:= 





a10
0a2
1 1
X5X6
X1+αX3X2+αX4






=





100000
010000
001000
000100
00001α














a10
0a2
1 1
X5X6
X1X2
X3X4








.
Deno e Mα,C, he wo ma ices o he igh e m o he p e ious equa ion such ha Aα=MαC. The
ma ix Aαdepends on αand is di e en o each ciphe ex , so i canno be included in he CRS. Ins ead,
we include he ma ix [UC] := [C||C~w+~zC] in he soundness se ing and [UC] := [C||C~w] in he WI se ing,
o ~zC/∈Im(C), o ins ance ~z>
C:= (0,0,0,0,1,0). To p o e membe ship in LAα,PG as we explained, we
would make he p oo wi h espec o he CRS [Uα] := [MαUC]. Clea ly, i ~z>:= (0,0,0,0,1), [Uα] =
[Aα||Aα~w +~z] in he soundness se ing and [Uα] = [Aα||Aα~w] in he WI, as equi ed. The esul ing p oo
consis s o 10 g oup elemen s, as opposed o 16 using s anda d GS p oo s. This applies o he esul o [17],
Sec ion 3.
8Fo comple eness, a de ailed compa ison o he 2-Lin case can be ound in appendix D.
9A de ailed compa ison o 2-Lin case is gi en in Appendix D. The same esul s hold o he Symme ic 2-cascade assump ion.
22
6.2 O he CRS Dependen Languages
The echniques o he p e ious sec ion can be ex ended o o he languages, namely:
•A p oo o alidi y o a ciphe ex , ha is, gi en [A], A← D`,k, and some ec o ~z ∈
Z
`
q,~z /∈Im(A),
one can use he same echniques o gi e a mo e e icien p oo o membe ship in he space:
LA,~z,PG ={[~c] : ~c =A~ +m~z} ⊂
G
`,
whe e (~ , [m]) ∈
Z
k
q×
G
is he wi ness. This is also a p oo o membe ship in he subspace o
G
`
spanned by he columns o [A] and he ec o ~z, bu pa o he wi ness, [m], is in he g oup
G
and
no in
Z
q, while pa o he ma ix gene a ing he subspace is in
Z
q. Howe e , i is no ha d o modi y
he subg oup membe ship p oo s as desc ibed in Sec ion 6.1 o accoun o his. In pa icula , since
GS a e non-in e ac i e ze o-knowledge p oo s o knowledge when he wi nesses a e g oup elemen s, he
p oo gua an ees bo h ha [~c] is well- o med and ha he p o e knows [m]. In a ypical applica ion,
[~c] will be he ciphe ex o some enc yp ion scheme, in which case ~ will be he ciphe ex andomness
and [m] he message.
•A p oo o plain ex equali y. The enc yp ion scheme de i ed om he KEM gi en in Sec ion 5.1
co esponds o a commi men in GS p oo s — excep ha he commi men is always binding. Tha
is, i pkA= (G,[A]∈
G
`×k), o some A← D`,k, gi en ~ ∈
Z
k
q,
EncpkA([m];~ )=[~c]=[A~ + (0,...,0, m)>] = [A~ +m·~z] = com[A||A~w]([m];~s),
whe e ~s>:= (~ >,0) and ~z := (0,...,0,1)>. The e o e, gi en wo (po en ially dis inc ) ma ix dis i-
bu ions D`1,k1,D0
`2,k2and A← D`1,k1,B← D0
`2,k2, p o ing equali y o plain ex s o wo ciphe ex s
enc yp ed unde pkA, pkB, co esponds o p o ing ha wo commi men s unde di e en keys open
o he same alue. One can gain in e iciency wi h espec o he s anda d use o GS p oo s because
one does no need o gi e any commi men s as pa o he p oo , since he ciphe ex s hemsel es play
his ole. Mo e speci ically, gi en [~cA] = EncpkA([m]) and [~cB] = EncpkB([m]), one can ea [~cA] as
a commi men o he a iable [x]∈A1=
G
and [~cB] as a commi men o he a iable [y]∈A2=
G
and p o e ha he quad a ic equa ion e([x],[1]) ·e([−1],[y]) = [0]Tis sa is ied. The p oblem is only
how o cons uc he simula o o he NIZK p oo sys em, since commi men s a e always binding. Fo
his, one uses a simila ick as in he membe ship p oo s, namely o le he ze o-knowledge simu-
la o open ι1([1]), ι2([−1]) as commi men s o he [0] a iable and simula e a p oo o he equa ion
e([x],[0])·e([0],[y]) = [0]T, which is i ially sa is iable and can be simula ed. In [27], we educe he size
o he p oo by 4 g oup elemen s om 18 o 22, while in [22] we sa e 9 elemen s al hough hei p oo is
qui e ine icien al oge he . We no e ha e en i bo h pape s gi e a p oo ha wo ciphe ex s unde
wo di e en 2-Lin public keys co espond o he same alue, he p oo in [22] is mo e ine icien because
i mus use GS p oo s o pai ing p oduc equa ions ins ead o mul i-scala mul iplica ion equa ions.
O he examples include [10, 15].
Acknowledgemen s
We hank Duong Hieu Phan o poin ing ou a small mis ake in a p e ious d a .
Re e ences
[1] O. Blazy, D. Poin che al, and D. Ve gnaud. Round-op imal p i acy-p ese ing p o ocols wi h smoo h
p ojec i e hash unc ions. In R. C ame , edi o , TCC 2012, olume 7194 o LNCS, pages 94–111,
Tao mina, Sicily, I aly, Ma . 19–21, 2012. Sp inge , Be lin, Ge many. 3
23
Fu he mo e, D’s iew can only depend on bi we ha e ki−kj≡0 mod I0bu ki−kj6≡ 0 mod I1(o he
analogous in Q0) o some elemen s ki,kjcons uc ed by D. We know ha any kio k0
iis in S≤m. So, since
I0∩ S≤m= (J0)≤m= (J1)≤m=I1∩ S≤m,D’s iew (wi h he eplaced o acles) does no depend on b.
Fo he o he di ec ion o he heo em, no e ha i he e exis s k∈(J0)≤m (J1)≤m hen i is easy o
cons uc a pp dis inguishe D ha compu es h= [k(ai,j, zi)]T∈
G
T. I b= 0, we always ha e h= [0]T
whe eas i b= 1, we ha e h= [0]Tonly wi h p obabili y a mos (deg+1)m
q= negl(λ).
The ideals J0and J1can be compu ed om I0and I1using elimina ion heo y. I we use G ¨obne bases
o ha , he condi ion (J0)≤m= (J1)≤mcan be eph ased as ollows:
Lemma 20. Le no a ion be as be o e and m > 0. Le <be an elimina ion o de on he monomials o R
such ha any monomial con aining any Tio Wiis la ge han any monomial om S. Fu he assume ha ,
es ic ed o he monomials o S,<so s by o al deg ee i s . Le H0 espec i ely H1be educed G ¨obne
bases o I0 espec i ely I1w. . . <. Then he ollowing a e equi alen :
1. (J0)≤m= (J1)≤m
2. H0∩ S≤m=H1∩ S≤m
3. H0∩ S≤mdoes no in ol e any Zi’s.
4. The e exis s a no necessa ily educed G ¨obne basis H0
0 o I0such ha H0
0∩ S≤mdoes no in ol e
any Zi’s.
P oo . Fi s , no e ha by he elimina ion heo em o G ¨obne bases [11], Jbis an ideal o e Swi h educed
G ¨obne basis Hb∩ S.
(1) ⇒(2) : Assume (J0)≤m= (J1)≤m. Le h∈H0∩ S≤m, bu assume owa ds a con adic ion
h/∈H1∩ S≤m. Since h∈ I1∩ S≤m, he e mus be some k∈H1∩ S,k6=hsuch ha he leading e m o
kdi ides he leading e m o h. By assump ion, <so s by o al deg ee i s , so he o al deg ee o kis a
mos m. Hence k∈ I0∩ S≤mwi h leading e m di ing ha o h, con adic ing he educedness o H0∩ S.
The o he inclusion H1∩ S≤m⊂H0∩ S≤mis analogous.
(2) ⇒(3) : H1does no in ol e any Zi’s, since he gene a ing se G1does no .
(3) ⇒(4) : Ob ious.
(4) ⇒(1) : Assume H0
0∩ S≤mdoes no in ol e any Zi. We i s show ha o any h∈H0
0∩ S≤mwe
ha e h∈ I1. To see his, w i e h=Pi,j ci,j i,j +Pidigias a linea combina ion in ou o iginal gene a o s
G0wi h polynomial coe icien s ci,j ,di∈ R. Plugging in 0 o all Wi’s and Zi’s in o his equa ion does no
a ec hby assump ion and elimina es all gi, so we ob ain h=Pi,j c0
i,j i,j o some c0
i,j showing h∈ I1.
Now le k∈ I0∩S≤m= (J0)≤mbe a bi a y. Since H0
0∩S is a G ¨obne basis w. . o <, which so s by o al
deg ee i s , we ha e k=Pieihi o some ei∈ S and hi∈H0
0∩ S≤deg k. Since we ha e shown ha all he hi
ha appea he e a e in I1, we ha e k∈ I1, showing (J0)≤m⊂(J1)≤m. The o he inclusion is i ial.
B.2 P oo o Theo em 4 and Gene aliza ions
Theo em 4 will ollow as a co olla y om he ollowing lemma, which is a gene aliza ion o non-linea pi,j
and non-i educible d:
Lemma 21. Le no a ion be as be o e. We assume ha `=k+ 1 and Acan be ull ank o some alues o
~
. Le dbe he de e minan o (p(~
T)k~
Z)as a polynomial in ~
Z, ~
Tand conside he ideal J:= I0∩
Z
q[~
A, ~
Z, ~
T]
o e
Z
q[~
A, ~
Z, ~
T]. Then he e exis s a unique (up o scala ) decomposi ion d=c·d0o e
Z
q, whe e conly
in ol es he ~
Tand d0is i educible o e he algeb aic closu e
Z
q. Fu he mo e, Jis gene a ed by G1and
d0.
P oo . Since Acan be ull ank, he e exis s some ~z,~
wi h d(~z,~
)6= 0, so dis no he ze o polynomial. Fo
he exis ence and uniqueness o cand d0, conside he (up o scala ) unique decomposi ion d=ce1
1ce2
2· · · ces
so
30

din o dis inc i educible polynomials ciin
Z
q[~
Z, ~
T]. Since dis linea in he Zi’s, only one ac o , w.l.o.g. cs
wi h es= 1, can con ain any o he Zi’s. No e ha his implies ha csis linea in he Zi’s as well. So we
ha e he up o scala unique decomposi ion d(~
Z, ~
T) = c(~
T)d0(~
Z, ~
T) wi h d0=csand c=ce1
1· · · ces−1
s−1, which
has he desi ed p ope ies, p o ided ha d0and cac ually ha e coe icien s in he base ield
Z
q a he han
Z
q.
To show he la e , w i e d=PiaiZiwi h ai∈
Z
q[~
T]. By cons uc ion, cdi ides dand cin ol es no ~
Z.
Plugging in Zi= 1 o i=i0and Zi= 0 o i6=i0in o d=c·d0shows ha c, and consequen ly cej
j,
di ides ai0. So, o all 1 ≤i≤`, 1≤j≤s−1 we ha e ai=cej
j·bi,j o some bi,j ∈
Z
q[~
T] and indeed cis
no hing bu he gcd o he ai. Since ai∈
Z
q[~
T], i ollows ha σ(ai) = ai=σ(cj)ej·σ(bi,j), whe e σis he
(coe icien -wise) F obenius. So σ(cj)ejdi ides each ai, hence e e y F obenius-conjuga e mus appea (up
o scala ) in he decomposi ion c=ce1
1· · · ces−1
s−1wi h he same mul iplici y. This shows ha we can choose
c∈
Z
q[~
T] a e adjus ing scala s. I ollows ha d0=d
cis also in he base ield.
Fo he second pa o he lemma, we i s obse e ha bo h ideals I0and I1a e adical: Since hey
can be gene a ed by polynomials o he o m Ai,j −pi,j (~
T), Zi−qi(~
T, ~
W) exp essing one se o a iables as
unc ions o ano he disjoin se o a iables, he quo ien R/I0 espec i ely R/I1is isomo phic o
Z
q[~
T, ~
W]
espec i ely
Z
q[~
Z, ~
T, ~
W]. Since hese quo ien s ha e no nilpo en elemen s, he ideals I0,I1a e adical. I
ollows ha Jis adical, since in e sec ion wi h a polynomial sub ing p ese es being adical. Since d0is
i educible, he quo ien
Z
q[~
A, ~
Z, ~
T]/(G1,d0), which is isomo phic o
Z
q[~
Z, ~
T]/(d0), con ains no nilpo en
elemen s, hence he ideal gene a ed by I1and d0in
Z
q[~
A, ~
Z, ~
T] is adical. I hus su ices o conside
he co esponding a ie ies (all a ie ies a e o e he algeb aic closu e
Z
q)V(G1,d0) and V(J) by he
Nulls ellensa z. Le V(I1) be he a ie y associa ed o I1. By he Closu e Theo em [11], he a ie y V(J)
associa ed o Jis gi en by he Za iski closu e o {(~a,~z,~
)∈V(I1)| ∃~ω, s. . zi=Pjωjai,j}. Le us s a
by showing V(G1,d0)⊂V(J):
I o some alue o ~
,c(~
) = 0, hen de (p(~
)k~z) = 0 o all alues o ~z, hence p(~
) has ank < k. Conside
he a ie y Vbad o all (~a, ~z,~
)∈V(I1) such ha A= (ai,j) has ank < k, which is indeed an algeb aic
se (conside de (Ak~ei) = 0 o canonical basis ec o s ~ei) and Vbad ⊃V(c,I1). Ou side o his bad se ,
A=p(~
) has ull ank kand hence he e exis s ~ω such ha ~z =A·~ω i and only i de (Ak~z) = 0, o
equi alen ly, since c(~
)6= 0, d0(~z,~
) = 0. I ollows ha V(G1,d0) Vbad ⊂V(J). By he same a gumen as
in he p e ious pa ag aph, since d0is i educible o e
Z
q, he quo ien
Z
q[~
A, ~
Z, ~
T]/(G1,d0)∼
=
Z
q[~
Z, ~
T]/(d0)
has no ze o di iso s and so V(G1,d0) is i educible. Since (~a,~
0,~
)∈V(G1,d0) o any ~
wi h p(~
) ull ank,
we ha e Vbad +V(G1,d0). F om his and he i educibili y o V(G1,d0), we can hen deduce ha he Za iski
closu e o V(G1,d0) Vbad ⊂V(J) is all o V(G1,d0), so we ha e V(G1,d0)⊂V(J)
Fo he o he di ec ion, conside (~a, ~z,~
) such ha ~a =~
p(~
) and he e exis s ~ω wi h zi=Pjωjai,j.
We need o show d0(~z,~
) = 0. Fo his, no e ha de (p(~
T)kPjWjpi,j(~
T)) is he ze o polynomial. So
d(PjWjpi,j(~
T),~
T) = c(~
T)·d0(PjWjpi,j(~
T)) is he ze o polynomial. Since c(~
T) is no he ze o polynomial,
as o he wise d(~
Z, ~
T) would be he ze o polynomial, we ha e ha d0(PjWjpi,j(~
T),~
T) is he ze o polynomial.
I ollows ha d0(~z,~
) = d0(Pjωjpi,j(~
),~
) = 0, inishing he p oo o V(G1,d0)⊃V(J).
This lemma allows us o easily p o e Theo em 4, which s a es:
Le `=k+ 1 and Dk+1,k be a ma ix dis ibu ion, which ou pu s ma ices A=p(~
) o uni o m ~
. Le
dbe he de e minan o (p(~
T)k~
Z) as a polynomial in ~
Z, ~
T.
1. I he ma ices ou pu by Dk+1,k always ha e ull ank (no jus wi h o e whelming p obabili y), e en
o i om he algeb aic closu e
Z
q, hen dis i educible o e
Z
q.
2. I all pi,j ha e deg ee a mos 1, dis i educible o e
Z
qand he o al deg ee o dis k+ 1, hen he
Dk+1,k-MDDH assump ion holds in gene ic k-linea g oups.
P oo . Le no a ion be as in he lemmas abo e.
(1): I cis non-cons an , i would ha e some oo s (~z,~
) in
Z
q. A hese oo s p(~
) can’ ha e ull ank, since
31
de (p(~
)k~z) = 0 o all ~z. Hence d=d0, which is i educible o e
Z
q.
(2): W.l.o.g. we may assume ha ~
pis injec i e (o he wise we d op some T- a iables), so we can exp ess he
Ti’s as linea polynomials in he Ai,j’s. Compu ing a G ¨obne basis ( o an app op ia e elimina ion o de ing)
o J0=J ∩ S om Jjus means exp essing all Ti’s by Ai,j’s. Since Jis gene a ed by d=d0and G1by
he abo e Lemma 21, a G ¨obne basis o J0is jus gi en by G1and d, exp essed by he Ai,j ’s. Since his
in e ible linea a iable subs i u ion does no change o al deg ee, he heo em ollows.
C P oo o Theo em 10
The p oo is a he echnical because we need an explici cons uc ion o a sequence o subspaces wi h
special p ope ies. The key idea is using a consequence o Lemma 9: o any non i ial subspace U⊂
Z
k
q,
dim( 0(U)+ 1(U)) >dim U, and o any non i ial subspace V⊂ 0(
Z
k
q)∩ 1(
Z
k
q), dim( −1
0(V)+ −1
1(V)) >
dim V. This allows us o build a sequence o subspaces wi h s ic ly inc easing dimensions ha ing some
in e es ing p ope ies. We will hen use hese subspaces o build he bases claimed in he heo em.
Conside he ollowing sequences o subspaces, o a sui able alue o m∈
Z
U1⊂U2⊂ · · · ⊂ Um=
Z
k
q;V1⊂V2⊂ · · · ⊂ Vm⊂
Z
k+1
q
such ha Vi= 0(Ui)∩ 1(Ui) and Ui−1= −1
0(Vi)∩ −1
1(Vi). The sequences a e well de ined because we
know ha Vi⊂ 0(Ui) and Ui−1⊂ −1
0(Vi), and hen Ui−1⊂ −1
0(Vi)⊂ −1
0( 0(Ui)) = Ui, since 0is
injec i e, and simila ly Vi−1⊂ 0(Ui−1)⊂ 0( −1
0(Vi)) ⊂Vi. On he o he hand, om he injec i i y o he
maps dim Ui= dim 0(Ui) = dim 1(Ui) and dim Vi= dim −1
0(Vi) = dim −1
1(Vi). Now, by Lemma 9 we
know ha 0(Ui)6= 1(Ui), i Uiis non i ial, and simila ly −1
0(Vi)6= −1
1(Vi), i Viis non i ial. The e o e,
i dim Vi>0 hen
dim Ui−1= dim( −1
0(Vi)∩ −1
1(Vi)) <dim Vi
and i dim Ui>0 hen
dim Vi= dim( 0(Ui)∩ 1(Ui)) <dim Ui
On he o he hand, since −1
0(Vi)⊂Uiand −1
1(Vi)⊂Ui hen −1
0(Vi) + −1
1(Vi)⊂Ui, and analogously
0(Ui) + 1(Ui)⊂Vi+1. Pu ing all equa ions oge he , i Uiis non i ial,
1≤dim Ui−dim Vi= dim Ui−dim( 0(Ui)∩ 1(Ui)) = dim( 0(Ui) + 1(Ui)) −dim Ui≤dim Vi+1 −dim Ui
and simila ly, i Viis non i ial, 1 ≤dim Vi−dim Ui−1≤dim Ui−dim Vi. Bu
dim Um−dim Vm= dim( 0(Um) + 1(Um)) −dim Um= dim
Z
k+1
q−dim
Z
k
q= 1
and hen all he equali ies hold. As a consequence, i kis e en, aking k= 2mwe ha e shown ha
dim Vi= 2i−1 and dim Ui= 2i. O he wise, we ake k= 2m−1 and dim Vi= 2i−2 and dim Ui= 2i−1
(hence, V1is i ial he e).
In addi ion, he p e ious equali ies o dimensions imply he co esponding equali ies o subspaces Ui=
−1
0(Vi) + −1
1(Vi) and Vi+1 = 0(Ui) + 1(Ui), which in pa icula mean ha a gene a ing se o Uican be
cons uc ed by compu ing he p eimages o a gene a ing se in Vi o bo h 0and 1( hese p eimages always
exis o ec o s in any Vi⊂Vm= 0(Um)∩ 1(Um)). Simila ly, we can build a gene a ing se o Vi+1 by
applying 0and 1 o a gene a ing se o Ui. We will also use he ac ha
Z
m+1
q= 0(Um) + 1(Um) o
comple e a basis o
Z
k+1
q.
A his poin , we ha e cons uc ed wo sequences o subspaces which dimensions g ow egula ly, and we
can build bases o he spaces by cle e ly picking ec o s om hem. We conside sepa a ely he cases ke en
and kodd.
Fo k= 2m, we know ha dim V1= 1. Le ~y ∈
Z
k+1
qbe a nonze o ec o in V1. Then, ~x0= −1
0(~y) and
~x1= −1
1(~y) o m a basis o U1, since i is a gene a ing se and dim U1= 2. Simila ly, we build a gene a ing
se { 1(~x0), 0(~x0), 1(~x1), 0(~x1)}o V2, bu ac ually 0(~x0) = 1(~x1) = ~y. Since dim V2= 3 we know ha
32
he h ee di e en ec o s o m a basis. Obse e ha we can w i e i as {( 1◦ −1
0)(~y), ~y, ( 0◦ −1
1)(~y)},
whe e −1
0(and simila ly −1
1) deno es he e he in e se map o 0 es ic ed o i s image 0(
Z
k
q), so i is well
de ined on any subspace Vi. Now, compu ing he p eimages o 0and 1and emo ing he epea ed ec o s
we can build a basis o U2. Following he same p ocedu e i e a i ely, we can build he bases
B1={( −1
0◦ 1)m−1(~x0),...,( −1
0◦ 1)(~x0), ~x0, ~x1,( −1
1◦ 0)(~x1),...,( −1
1◦ 0)m−1(~x1)}
and
B2={( 1◦ −1
0)m(~y),...,( 1◦ −1
0)(~y), ~y, ( 0◦ −1
1)(~y),...,( 0◦ −1
1)m(~y)}
o
Z
k
qand
Z
k+1
q, espec i ely, wi h he p ope y ha he images o he ec o s in B1by 0a e exac ly he
las k ec o s in B2, and he images o he ec o s in B1by 1a e exac ly he i s k ec o s in B2. This is
he same as saying ha 0and 1a e ep esen ed in hose bases by he ma ices J0and J1, espec i ely.
The p oo o he odd case k= 2m−1 p oceeds simila ly, bu s a ing om a nonze o ec o ~x ∈U1,
compu ing he wo images ~y0= 0(~x) and ~y1= 1(~x), and hen applying he same i e a i e p ocedu e as
be o e o ob ain he bases
B1={( −1
0◦ 1)m−1(~x),...,( −1
0◦ 1)(~x), ~x, ( −1
1◦ 0)(~x),...,( −1
1◦ 0)m−1(~x)}
and
B2={( 1◦ −1
0)m(~y1),...,( 1◦ −1
0)(~y1), ~y1, ~y0,( 0◦ −1
1)(~y0),...,( 0◦ −1
1)m(~y0)}
o
Z
k
qand
Z
k+1
q, espec i ely, wi h exac ly he same p ope y as be o e.
D Subg oup Membe ship P oo s o 2-Lin
In his sec ion we exempli y ou app oach om Sec ion 6.1 o he 2-Lin case. Le
A=

a10
0a2
1 1 
= (~u1, ~u2),A← L2,
and
[u3] = ([w1~u1+w2~u2] binding key (soundness se ing)
[w1~u1+w2~u2−(0,0,1)>] hiding key (WI se ing) ,
o w1, w2←
Z
q. We exempli y ou new app oach o p o e [Φ] ∈ LA,PG ⊂
G
3. To simpli y he no a ion we
de ine ~ := ~u3+ (0,0,1)>. Wi h his no a ion, [ι0(x)] := [x~ ].
S anda d G o h-Sahai p oo . In he s anda d app oach, used o ins ance in [35], he p o e will show
ha he e a e wo alues 1, 2∈
Z
qsuch ha he ollowing equa ions hold:
[ 1a1] = [Φ1] (9)
[ 2a2] = [Φ2] (10)
[ 1+ 2] = [Φ3].(11)
The e o e, we a e in he se ing o mul iscala mul iplica ion wi h A1=
Z
qand A2=
G
. The p oo consis s
o he commi men s o 1, 2, which a e wo ec o s [~c 1],[~c 2]∈
G
3such ha
(~c 1,~c 2)=(ι0( 1), ι0( 2)) + As11 s12
s21 s22= ( 1~ , 2~ ) + As11 s12
s21 s22
and he ec o
[~π( 1, 2)] = (a1,0)S>,(0, a2)S>,(1,1)S>= ([s11a1],[s21a1],[s12a2],[s22a2],[s11 +s12],[s21 +s22]).
33
The e o e, in o al, he p oo equi es 12 g oup elemen s.
To simula e he p oo , we p oceed as i we we e p o ing ha he equa ions
[ 1a1] = [δΦ1]
[ 2a2] = [δΦ2]
[ 1+ 2] = [δΦ3],
a e sa is ied by he all ze o wi ness, wi h he commi men o δ= 0 being com0
[U],~z(0; (w1, w2)>), which, in
he wi ness indis inguishabili y se ing, is equal o [ι0(1)] = [~ ]=[A~w].
New app oach. To cons uc he p oo , he p o e needs o sample uni o mly a andom om he space
H:= {H∈
Z
2×2
q:H+H>=0}. To sample H← H, pick a andom alue h←
Z
qand de ine H=
0h
−h0. The p oo is hen de ined as:
[Π]=[~u3( 1, 2) + AH] = 

[ 1 1] [ 2 1+ha1]
[ 1 2−a2h] [ 2 2]
[ 1 3−h] [ 2 3+h]

The p oo consis s o 6 g oup elemen s, as claimed.
Fo simula ion, we sample some H0← H as be o e and we de ine:
[Πsim]=[~
Φ(w1, w2) + AH0].
E Conc e e Examples om he k-SCasc Assump ion
As we p omo e he k-SCasc Assump ion as a eplacemen o he k-Lin Assump ion, we gi e wo conc e e
ins an ia ions o a KEM and a PRF based on i .
E.1 Key Encapsula ion
We build a KEMGen,SCk om k-SCasc (Example 4).
•Gen(1λ) uns G ← Gen(1λ) and picks a←
Z
q. The public/sec e -key is
pk = (G,([a]) ∈
G
),sk =a∈
Z
q.
•Encpk picks ~w ←
Z
k
q. The ciphe ex /key pai is
[~c] = ([aw1],[w1+aw2]. . . , [wk−1+awk])T∈
G
k,[K]=[wk]∈
G
.
•Decsk ([~c]∈
G
k) ecompu es he key as
[K]=[~x>~c]∈
G
,
whe e he ans o ma ion ec o ~x ∈
Z
k
qis compu ed om aas xi=(−1)k−i
ak−i(such ha ~x>A0=
(0,...,0,1)Twhe e A0consis s o he op k ows o ma ix A om Example 4).
Secu i y o KEMGen,SCk ollows om Theo em 11. No e ha he size o he public/sec e key is cons an ,
compa ed o linea (in k) o he k-Lin-based KEM [23, 45]. The ciphe ex size emains he same, howe e .
34
E.2 Pseudo-Random Func ion
We build PRFGen,SCk= (Gen,F) om k-SCasc.
•Gen(1λ) uns G ← Gen(1λ) and picks ai,j ←
Z
q o 1 ≤i≤n, 1 ≤j≤kand ~
h←
Z
k
q. The sec e -key
is K= ((ai,j),~
h).
•FK(x) compu es
FK(x) = "Y
i:xi=1
Ti·~
h#∈
G
k,
whe e
Ti=




(−1)k−1
ak
i,1
. . . −1
a2
i,1
1
ai,1
.
.
..
.
..
.
.
(−1)k−1
ak
i,k
. . . −1
a2
i,k
1
ai,k





∈
Z
k×k
q,
whe e he ans o ma ion ma ices Ti,j o Ai,j ← SCka e he ow ec o s o Ti. Secu i y o PRFGen,SCk
ollows om Theo em 12. No e ha he size o he sec e -key Kis nk, compa ed o nk2 o he k-Lin-based
PRF [6].
Obse e ha i we add he es ic ion ai,j 6= 0, we can ew i e Tias
Ti=−


bk
i,1. . . b2
i,1bi,1
.
.
..
.
..
.
.
bk
i,k . . . b2
i,k bi,k


,
whe e now bi,j =−1
ai,j a e andom nonze o elemen s. I we associa e ~
h= (h1, h2, . . . , hk) o he polynomial
h=h1Xk+. . .+hk−1X2+hkX∈
Z
q[X], hen Ti~
h=−(h(bi,1),...,h(bi,k)), and he PRF can be in e p e ed
as a sequence o ans o ma ions applied o a andom polynomial. Mo e speci ically, o e e y bi xi= 1, he
i- h s ep eplaces he coe icien s o a polynomial by i s e alua ions (up o he sign) a some andom poin s
bi,1, . . . , bi,k.
35