Two Applications of Multilinear Maps: Group Key
Exchange and Witness Encryption
Seiko Arita

Sari Handa

Institute of Information Security
Kanagawa, Japan

Institute of Information Security
Kanagawa, Japanarita@iisec.ac.jp

mgs125502@iisec.ac.jp

ABSTRACTconstruct multilinear maps from abelian varieties, but they
concluded such maps should be hard to construct[BS03]. Recently, the first construction of multilinear maps has been
described by Garg, Gentry and Halevi based on ideal lattices [GGH13]. After this breakthrough, various new cryptographic systems have been proposed today. The system
realizing multilinear maps is called ”graded encoding system”. The encodings have homomorphic addition and multiplication and they introduce the concept of level into theencodings. This concept of level making the encoding system interesting, here we describe two of its interesting properties. First, an encoding is probabilistic, that is, encodingsof a same plaintext are diﬀerent because of included randomness, but at only a specified level, a deterministic value
can be extracted from the random encodings of the sameplaintext. Second property is that a rerandomized encoding
is not allowed to be divided by some other encodings, so an
encoding is unable to downgrade to the lower levels. Applications use these properties. For example, in the group key
exchange on N parties [GGH13] [CLT13], each party createsa level-(N − 1) encoding from its own encoding and others,
and they extract a same value as a sheared group key at thelevel-(N − 1). In witness encryption [GGSW], an encryptor and a decryptor generate a same level encoding for eachby diﬀerent way and extracts a same value from their own
created encodings. The second property brings one-wayness
and means a strong tool for cryptosystems. In the work of
attribute based encryption for circuit [GGHSW13], authors
use this one-wayness to prevent a back tracking attack andachieved to treat circuits with multi fun-out gates.
Our result. We have studied applications of multilinear
maps. In this work we propose two such applications: GroupKey Exchange and Witness Encryption. A one-round group
key exchange protocol is described in the work [GGH13][CLT13], in which each party collects encodings of all otherparties and multiplies its own encoding and them one-byone. We design a GKE protocol in which one encoding iscommunicated on each upflow and downflow, in which parties’s secret are piled up gradually. The number of encodings
communicated in a session of the GKE protocol per party
does not depend on the number of parties. Also its computation cost per party is independent of the number of parties
because each party only multiplies a received encoding by
its own encoding.
Witness encryption is a new type of cryptosystem thatcan be achieved using multilinear maps [GGSW]. The witness encryption of [GGSW] uses EXACT-COLVER Problem
as NP-complete language. We try to construct based on an-

Constructing multilinear maps has been long-standing open
problem, before recently the first construction based on ideal
lattices has been proposed by Garg et al. After this breakthrough, various new cryptographic systems have been proposed. They introduce the concept of level into the encodings, and the system has a function that extracts a deterministic value at only a specific level, and the encodings areunable to downgrade to the lower levels. These properties
are useful for cryptography. We study how this graded encoding system be applied to cryptosystems, and we propose
two protocols, group key exchange and witness encryption.
In our group key exchange, we achieve the communication
size and the computation costs per party are both O(1) withrespect to the number of parties by piling the encodings ofpassed parties in one encoding. A witness encryption is a
new type cryptosystem using NP-complete problem. The
first construction is based on EXACT-COVER problem. We
construct it based on another NP-complete Hamilton Cycle
problem, and prove its security under the Generic Cyclic
Colored Matrix Model.

Categories and Subject Descriptors
E.3 [Data] [Data Encryption]: [public key cryptosystems]

General Terms
Theory,Security

Keywords
multilinear maps, group key exchange, witness encryption,
hamilton cycle problem

1. INTRODUCTION
Multilinear maps have been desired to be constructed because if it exists it would enable many interesting cryptographic applications. Boneh and Silverberg attempted toPermission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others thanACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
AsiaPKC’14, June 3, 2014, Kyoto, Japan.
Copyright 2014 ACM 978-1-4503-2801-2/14/06 ...$15.00.
http://dx.doi.org/10.1145/2600694.2600699.

13

Encoding. The enc(params, i, a) takes i ∈ [n] and a level(α)
zero encoding a ∈ S0 for some α ∈ R, and outputs a level-i(α)
encoding u ∈ Si for the same α.
Re-Randomization. The reRand(params, i, u)
re-randomizes encodings to the same level i, as long as theinitial encoding u is under a given noise bound.
Addition and negation. Given params and two en(α )(α )codings at the same level, u1 ∈ Si 1 and u2 ∈ Si 2 , it
(α1 +α2 )holds add(params, u1 , u2 ) ∈ Si
, and neg(params, u1 ) ∈(−α )Si 1 , subject to bounds on the noise.
(α )
(α )
Multiplication. For u1 ∈ Si1 1 ,u2 ∈ Si2 2 , such that

other NP-complete problem, Hamilton Cycle Problem. The
two problems have in common with a task of collecting justN element with no duplication, and this situation matches
the property of the graded encoding system that extracts adeterministic value only from the specified level-N encodings. The diﬀerence is that in the case of Hamilton Cycle
Problem, elements are connected by edges and a cycle follows the adjacent edges sequentially. We take in a tool ofadjacent matrices for managing edge adjacency and manages non-commutativity of vertices in a cycle by matrix’s
non-commutativity. We proved the security of our scheme
based on our generic cyclic colored matrix model that is avariant of a generic colored matrix model defined by workof indistinguishability obfuscation [GGH13+].

(α α )

2. PRELIMINARIES
2.1 Approximate Multilinear Maps
Gentry et al. defined their notion of a approximate multilinear maps, which they call graded encoding schemes [GGH13].
They view group element in multilinear map schemes as justa convenient mechanism of encoding the exponent: Typicalapplication of bilinear maps use α · gi as an encoding of theplaintext integer α ∈ Zp . In their setting, they retain theconcept of a somewhat homomorphic encoding, and have an
algebraic ring (or field) R playing the role of the exponent
space Zp .

2.1.1 Definition of Graded Encoding Schemes

1 2
i1 + i2 ≤ n, we have mult(params, u1 , u2 ) ∈ Si1 +i.
2
Zero-test. The procedure isZero(params, pzt , u) outputs(0)
1 if u ∈ Sn and 0 otherwise. Note that in conjunction
with the procedure for subtracting encodings, this gives us
an equality test.
Extraction. This procedure extracts a ”canonical” and”random” representation of ring elements from their leveln encoding. Namely ext(params, pzt , u) outputs (say) K ∈{0, 1}λ , such that:(a) With overwhelming probability over the choice of α ∈ R,(α)
for any two u1 , u2 ∈ Sn , ext(params, pzt , u1 ) = ext(params,
pzt , u2 ),(α)(b) The distribution {ext(params, pzt , u) : α ∈ R, u ∈ Sn }λis statistically uniform over {0, 1} .

2.1.2

Graded Decisional Diffie-Hellman Problem

Garg et al. [GGH13] and Coron et al. [CLT13] define
Graded DDH Problem (GDDHProblem), as following process:Definition 1. (κ-Graded Encoding System [GGH13]). A
κ-Graded Encoding System consists of a ring R and a sys(α)
tem of sets S = {Si ⊂ {0, 1}∗ : i ∈ [0, κ], α ∈ R}, with thefollowing properties:(α)
1. For every fixed index i ∈ [0, κ], the sets {Si : α ∈ R}(α)
are disjoint. The set Si consists of the ”level-i encodingsof α”.
2. There is an associative binary operation ”+” and a selfinverse unary operation ”-” (on {0, 1}∗ ) such that for every(α )α1 , α2 ∈ R, every index i ≤ κ, and every u1 ∈ Si 1 and(α2 )(α1 +α2 )u2 ∈ Si , it holds that u1 +u2 ∈ Si
and −u1 ∈ Si−α1
where α1 + α2 and −α1 are addition and negation in R.
3. There is an associative binary operation ”×” (on {0, 1}∗ )such that for every α1 , α2 ∈ R, every i1 , i2 with i1 + i2 ≤ κ,
(α )
(α )
and every u1 ∈ Si1 1 and u2 ∈ Si2 2 , it holds that u1 × u2 ∈1. (params, pzt ) ← InstGen(1λ , 1κ )2. Choose aj ← samp(params) for all 1 ≤ j ≤ κ + 1
3. Set uj ← reRand(params, 1, enc(params, 1, aj )) for all
1≤j ≤κ+1
4. Choose b ← samp(params)
5. Set ũ = aκ+1 × Πκi=1 ui
6. Set û = b × Πκi=1 ui
The GDDH distinguisher is given as input the κ + 1 levelone encodings uj and either ũ (encoding the right product)or û (encoding a random product), and must decide whichis the case.
Graded Decisional Diﬃe-Hellman Assumption (GDDH
Assumption) The Graded Decisional Diﬃe-Hellman Assumption is that the advantage of any eﬃcient adversary is
negligible in the security parameter against Graded Decisional Diﬃe-Hellman Problem.

(α α )

1 2
Si1 +i. Here α1 · α2 is multiplication in R, and i1 + i2 is
2integer addition.

The n-graded encoding system of [GGH13] for a ring R(α)
includes a system of sets S = {Si ⊂ {0, 1}∗ : i ∈ [0, n], α ∈(α)
R} such that, for every fixed i ∈ [0, n], the sets {Si:(α)α ∈ R} are disjoint. The set Si consists of the ”level-i
encodings of α”.
Instance Generation. The randomized InstGen(1λ , 1n )takes as inputs the security parameter λ and integer n. The
procedure outputs (params, pzt ), where params is a description of an n-graded encoding system, and pzt is a level-n”zero-test parameter”.
Ring Sampler. The randomized samp(params) outputsa ”level-zero encoding” a ∈ S0 , such that the induced distri(α)
bution on α such that a ∈ S0 is statistically uniform.

3.

GROUP KEY EXCHANGE USING MULTILINEAR MAPS

The graded encoding system has a function that extracts adeterministic value associated with a plaintext from a specified level encodings and the level is specified at the instancegeneration. This functionality fits with a group key exchange (GKE) because the shared key should be generated
from secrets of all parties. We construct a GKE protocol
which communication type is (N-1)-round 2-way of upflow
and downflow. The construction is simple, each party multiplies a received encoding by own encoding and sends the14oracles accept with the same session group key.

Table 1: Comparison of performance with respect
to the number of parties (per party)
SchemeComm. Comp.
One-round using MM [GGH13]
O(N )
O(N )
upflow/downflow no MM [STW96]
O(N )
O(N )
upflow/downflow using MM (ours)
O(1)
O(1)

Definition 3 (AKE Security). Protocol P is called
AKE-secure if advantage of any eﬃcient A in the following
game GameAKE (A) is negligible.
GameAKE : Adversary A can ask queries except Test manytimes, and once, A sends a Test-query to a fresh oracle ( aoracle is fresh if nobody has been asked for Corrupt-queryat that moment, and no Reveal-query is asked to the oracle
or its partners). A gets back its session key or a random
string. The adversary wins if she correctly guesses the bit b
used in the above game, and the advantage is probability of
win minus 1/2, taken over all bit tosses.

result encoding to the next party. In the communicated encoding, secrets of passed parties are piled up, so the message
complexity per party does not depend on the number of parties. Also, the computation cost for each party is O(1).
In Table 1, we compare our GKE scheme with two otherschemes in terms of their performance with respect to thenumber of parties, ’N’ means the number of parties, ’Comm.’
is communication size and ’Comp.’ is computation cost. The
first scheme is one-round GKE using Multilinear Maps in[GGH13]. In this scheme, communicated encodings are notproduct, so the number of encodings per party is O(N ) andthe cost one party multiplies received encodings is O(N ).
The second scheme [STW96] is upflow/downflow type likeours but it does not use Multilinear Maps. The number ofcommunicated group elements per party is O(N ) and thecomputation cost per party is also O(N ).
In our protocol, we design the shared group key as output
value of pseudo-random function which seed is a level-(N −1) encoding generated by above process and which input
value is a session ID. We use graded encoding system forthe session ID to achieve theoretically that the conputation
cost and communication size per party are O(1). So we maketwo instances of graded encoding system for level-(N − 1)and level-N .
We prove our protocol under GDDH assumption using
security model proposed by Bresson et al [BCPQ].

3.2

Our Construction

Our scheme consists of PPT algorithms Setup, Upflow,
Downflow and KeyGen, and parties are indexed Party1 to
PartyN , and Partyi is connected to Partyi+1 (1 ≤ i ≤ N −1).
This GKE protocol first executes the Setup algorithm andthe resulting public information should be shared among
parties. Party1 executes Upflow1 without input value. Then,
Partyi executes Upflowi , receiving the outputs (cur , dur , σur )of its precedent Upflowi−1 as inputs, sequentailly for i = 2
to N . Then, PartyN executes DownfowN without input
value and Partyi executes Downflowi , receiving the outputs(cdr , ddr , σdr ) of the precedent Downflowi+1 as inputs, alsosequentailly for i = (N − 1) to 1. In the Downflow sequence,each Downflowi invokes the algorithm Keygen to computethe shared session-key ξ among the parties.
Building blocks are multilinear maps MM, EUF-CMA secure signature scheme Σ and pseudo random function Hseed .
In the following algorithm, a· b denotes mult(params, a, b).
Setup. The algorithm Setup takes security parameter λand number of parties N as input, makes two sets of MM
parameter by instance generation specifying level N − 1 andN , respectively. Then it generates N pairs of signing key
ski and verification key vki by key generation of Σ, and sets
signing keys to each parties. The algorithm outputs two setsof parameter of MM and all verification keys {vki } as publicparameter.

3.1 BCPQ Model : Security Model for GKE

BCPQ Model is a formal model for Group Key Exchange
protocol (GKE) proposed by Bresson, Chevassut, Pointcheval,and Quisquater [BCPQ]. In their model, the adversary A
controls all communication between player instances andasks an instance to release session key or long-lived key. A
set ID of n players in protocols P is fixed. A player Ui ∈ ID
Setup(1λ , 1N )can have many instances called oracles, involved in distinct(params1 , pzt1 ) ← MM.InstGen(1λ , 1N −1 )concurrent execution of P . An instance s of player Ui is(params2 , pzt2 ) ← MM.InstGen(1λ , 1N )denoted as oracle Πsi .
ssfor i = 1 to N
SessionIDS. Session id for oracle Πi is defined as SIDS(Πi ) =(vki , ski ) ← Σ.KeyGen(1λ ){SIDSij : j ∈ ID} where SIDSij is the concatenation of
Sets ski to Ui
all flows that Πsi exchanges with Πtj in an execution of P .
return (params1 , pzt1 , params2 , pzt2 , vki (1 ≤ i ≤ N ))Adversary A listens on the wire and can constructs SIDS.
Oracle Queries. Adversaries can send following queries
Upflow. The algorithm Upflow takes encoding cur , dur andto oracles:
signature σur as input and verifies them on sender’s verifica·Send(ΠsU , m):Adversary A gets the response which ΠsU havetion key vki−1 . Then it creates a secret level-0 encoding ai
generated in processing incoming-message m.
and upgrades to level-1 and rerandomizes that using param1 .
·Reveal(ΠsU ):This query forces ΠsU to release its session key.
The algorithm creates one more level-1 encoding d1 for ses·Corrupt(U ):Adversary A gets long-lived key LLU of U but
sionID using param2 . Then, multiplies them by received
does not get the internal data of instance of U.
encoding and outputs the two encodings with its signature·Test(ΠsU ):A gets back session key or random string from
σus .
ΠsU .
Definition 2 (Correctness). A GKE protocol iscorrect if for any operation execution between the oracles
ΠsU1 , · · · , ΠsUN with the same session ids sid = SIDS(Πsi ) all

Upflowi (cur , dur , σur )if i ̸= 1 and Σ.verify(vki−1 , cur ∥dur , σur )=false then abortai ← MM.samp(params1 )15

ci ← MM.reRand(params1 , 1, MM.enc(params1 , 1, ai ))di ← MM.reRand(params2 , 1, MM.enc(params2 , 1, MM.samp(params2 )))if i ̸= N thenif i = 1 then cus := cidus := dielse
cus := cur · ci dus := dur · diσus ← Σ.sign(ski , cus ∥dus )return (cus , dus , σus )and return (cus , dus , σus ).
–Send(Πsi , Downflow(cdr , ddr ,σdr ))Follow the instruction of the Downflowi algorithm to compute and return (cds , dds , σds ) and local output ξ.
–Reveal(Πsi ): return ξ–Corrupt(Ui ): return ski

Downflow. The algorithm Downflow takes encodings cdr ,ddr
and signature σdr as input and verifies them on sender’s verification key vki+1 . Then it generates a session key ξ by key
generation algorithm, and multiplies own two encoding ci
and di by received encoding cdr and ddr respectively, andoutputs the result encodings with its signature σds .

–Test(Πsi )Downflowi (cdr , ddr , σdr )if i ̸= N and Σ.verify(vki+1 , cdr ∥ddr , σdr )=false then abort
if i ̸= 1 thenif i = N then cds := ci
dds := dielse
cds := cdr · ci dds := ddr · diσds ← Σ.Sign(ski , cds ∥dds )ξ ← KeyGen(ai , cur , cdr , di , dur , ddr )return (cds , dds , σds ) as message and ξ as local output.

We define Si to be the event that b = b̂ in Gamei.

$b ← {0, 1}
if b = 0 then return ξ$else return r ← {0, 1}λThen adversary A outputs guess of b as b̂ .

Game1: We make a transition into Game1: Abort if message is fabricated.
–Send(Πsi , Upflow(cur , dur ,σ))if cur ∥dur ∈/ m′ and Σ.verify(vki−1 , cur ∥dur , σur )=true
then abort
if i ̸= 1 and Σ.verify(vki−1 , cur ∥dur , σur )=false then abort

KeyGen. The algorithm KeyGen takes encodings ai , cur , cdr, di , dur , ddr as input, multiplies ai , cur , cdr for seed of H
and di , dur , ddr for sessionID. MM.ext extracts a deterministic value from level-(N − 1) encoding c′i , and KeyGen algorithm sets it to seed of H. A deterministic value fromlevel-N encoding d′i is sessionID and input to H.

m′ := m′ ∥cur ∥dur// following is same as Game0–Send(Πsi , Downflow(cdr , ddr ,σ))if cdr ∥ddr ∈/ m′ and Σ.verify(vki+1 , cdr ∥ddr , σdr )=true
then abort
if i ̸= N and Σ.verify(vki+1 , cdr ∥ddr , σdr )=false then abort

KeyGeni (ai , cur , cdr , di , dur , ddr )c′i := ai · cur · cdr d′i := di · dur · ddrδ ← MM.ext(params1 , pzt1 , c′i )sessionID ← MM.ext(params2 , pzt2 , d′i )return ξ ← Hδ (sessionID)m′ := m′ ∥cdr ∥ddr// following is same as Game0

Correctness. We show all parties share a same session
key string. Considering output string from H in KeyGen algorithm, seed δ of H is the product of own private level-0
encoding and level-1 encodings of all other parties. MM.ext
outputs the same string that is a deterministic value of product of plaintexts ai of all parties. SessionID is product oflevel-1 encodings di of all parties, so MM.ext outputs thesame value for each parties.

Claim 1. If the signature scheme Σ is EUF-CMA secure,then | Pr[S0 ] − Pr[S1 ] |≤ negl(λ).
Sketch of Proof. Let c and d be received encodings,
m′ be a set of messages that had been verified, vk be averification key and σ be a signature. We define failure
event F that ”(c, d) ∈/ m′ and Σ.verify(vk, c∥d, σ) = true”.
Then, S0 ∧ ¬F ⇔ S1 ∧ ¬F . Let A be an adversary thatcan get an advantage in distinguishing between Game0 and
Game1. We construct a forger F from A.
Forger F. F guesses a party j whose signature A will
forge. In Setup algorithm, F sets input vk to vkj of party j.
A sends Send-query to Πsi , if i=j and event F then F outputs
the ((c, d), σ). F calls signing oracle to get signature of j.
The probability of F successes in above game is 1/N ·Pr[F ] and signature scheme Σ is EUF-CMA, so Pr[F ] ≤negl(λ). From Diﬀerence Lemma defined by Shoup in Sequence of Games [Shoup], |Pr[S0 ]−Pr[S1 ] |≤Pr[F ].
∴ |Pr[S0 ]−Pr[S1 ] |≤ negl(λ).
23.3 Proof of Security
Theorem 1. Our protocol is AKE secure under the GDDH
Assumption (see Section A.2), and the assumptions that thesignature scheme Σ is EUF-CMA and the function H is secure PSF.
Proof. We prove the security of our protocol based on
BCPQ security model.
Game0: Original Security game for our protocol–Send(null,”start”)
Follow the instruction of the Setup algorithm to computeand return (params1 , pzt1 , params2 , pzt2 , vki (1 ≤ i ≤ N )).

Game2: We make a transition into Game2. In this game,seed of H is changed into random encoding which is formed
by GDDH Problem instance.

–Send(Πsi , Upflow(cur , dur ,σur ))Follow the instruction of the Upflowi algorithm to compute–Test(Πsi )16$b ← {0, 1}
if b = 0 thena′ ← MM.samp(params1 )–Corrupt(Ui ): return ski–Test(Πsi )if s ̸= s∗i then abort with a random bit

c′i := a′ · cur · cdr

d′i := di · dur · ddrδ ← MM.ext(params1 , pzt1 , c′i )$b ← {0, 1}
if b = 0 thend′i := di · dur · ddrδ ← MM.ext(params1 , pzt1 , T )sessionID ← MM.ext(params2 , pzt2 , d′i )ξ ← Hδ (sessionID)
return ξ$else return r ← {0, 1}λsessionID ← MM.ext(params2 , pzt2 , d′i )return ξ ← Hδ (sessionID)

Claim 2. Under GDDH the assumption,| Pr[S1 ] − Pr[S2 ] |≤ negl(λ).

$

else return r ← {0, 1}λThe advantage of D is AdvD = | Pr[D(uj , T )=1 | T = ũ]- Pr[D(uj , T )=1| T = û] |. Now we describe Pr[D(uj , T )=1 |T = ũ] as Pr[D(ũ)=1], Pr[D(uj , T )=1| T = û] as Pr[D(û)=1].

Proof. We construct a distinguisher D of GDDH Problem from adversary A against our protocol. D guesses aparty whom A will ask Test-query. Its instance and partner
instances are denoted by Πs∗i . We define a event Guess thatis ”All Πs∗
i are correct”. If input of D is ũ then the view of
A in D is view of A in Game1, and if input of D is û thenthat is view of A in Game2.
Algorithm D(uj (1 ≤ j ≤ N ), T = ũ or û)Pr[D(ũ)=1] = Pr[D(ũ)=1 ∧ ¬ Guess] + Pr[D(ũ)=1 ∧ Guess]=1/2 + Pr[Guess]Pr[D(ũ)=1 | Guess]=1/2 + Pr[Guess]Pr[S1 ]Pr[D(û)=1] = Pr[D(û)=1 ∧ ¬ Guess] + Pr[D(û)=1 ∧ Guess]=1/2 + Pr[Guess]Pr[D(û)=1 | Guess]=1/2 + Pr[Guess]Pr[S2 ]s∗i ←[1,S] //S is upper bound of numbers of instances A
creates.
$–Send(Πsi , Upflow(cur , dur , σ))if s = s∗i thenif cur ∥dur ∈/ m′ and Σ.verify(vki−1 , cur ∥dur , σur )=true
then abort
if i ̸= 1 and Σ.verify(vki−1 , cur ∥dur , σur )=false thenabortm′ := m′ ∥cur ∥durci ← uidi ← MM.reRand(params2 , 1, MM.enc(params2 , 1, MM.samp(params2 )))if i ̸= N thenif i = 1 then cus := cidus := dielse
cus := cur · ci dus := dur · diσus ← Σ.Sign(ski , cus ∥dus )return (cus , dus , σus )else // s ̸= s∗i , following is same as Game1

AdvD = | Pr[D(ũ)=1] - Pr[D(û)=1] | = Pr[Guess]·(Pr[S1 ]Pr[S2 ])From GDDH assumption AdvD ≤ negl(λ), and Pr[Guess] is
1/poly(λ). Therefore |Pr[S1 ]-Pr[S2 ]| ≤ negl(λ).
2Game3: We make a transition into Game3. In this game,the value of H is changed into a random string.
–Test(Πsi )$b ← {0, 1}
if b = 0 then return r′ ← {0, 1}λ$$else return r ← {0, 1}λClaim 3. If H is secure then | Pr[S2 ] − Pr[S3 ] |≤ negl(λ).
Proof. Immediate from security of pseudo-random function.
2
The advantage of A is clearly negligible in Game3 andfrom Claim1,Claim2,Claim3, the advantage of A of real isalso negligible.
2–Send(Πsi , Downflow(cdr , ddr , σ))if s = s∗i thenif cdr ∥ddr ∈/ m′ and Σ.verify(vki+1 , cdr ∥ddr , σdr )=true
then abort
if i ̸= N and Σ.verify(vki+1 , cdr ∥ddr , σdr )=false thenabortm′ := m′ ∥cdr ∥ddr
if i ̸= 1 thenif i = N then cds := ci
dds := dielse
cds := cdr · ci dds := ddr · diσds ← Σ.Sign(ski , cds ∥dds )// MM.KeyGen is not called.
return (cds , σds )else // s ̸= s∗i , following is same as Game2

4.

WITNESS ENCRYPTION USING MULTILINEAR MAPS

4.1

Preliminaries

4.1.1

Witness Encryption

A witness encryption scheme [GGSW] for an NP language
L(with corresponding witness relation R) consists of the following two polynomial-time algorithms:
Encryption. The algorithm Encrypt(1λ , x, m) takes as
input a security parameter λ, an unbounded-length stringx, and a message m ∈ M , and outputs a ciphertext CT .
Decryption. The algorithm Decrypt(CT, w) takes as input a ciphertext CT and an unbounded-length string w, andoutputs a message m or the symbol ⊥.

–Reveal(Πsi )if s = s∗i then abort with a random bit
return ξ

17the oracle looks up the records corresponding to h1 , h2 inthe database. If such records exists, then if (m1 , LC1 ) =(m2 , LC2 ) and (n1 , RC1 ) = (n2 , RC2 ) then the oracle computes their sum M = M1 + M2 . If the database already contains the matrix (M, (m1 , LC1 ), (n1 , RC1 )) then oracle returns its handle. Otherwise, the oracle assigns a new handle
h′ and inserts into the database (h′ , M, (m1 , LC1 ), (n1 , RC1 ))and returns the new handle.
Multiplication. When the adversary makes query mult(h1 ,h2 ), the oracle looks up the records corresponding to h1 , h2
in the database. If such records exists, then if (n1 , RC1 ) =(m2 , LC2 ) then the oracle computes their product M =M1 M2 . If the database already contains the matrix (M, (m1 ,LC1 ), (n2 , RC2 )) then oracle returns its handle. Otherwise,
the oracle assigns a new handle h′ and inserts into the database(h′ , M, (m1 , LC1 ), (n2 , RC2 )) and returns the new handle.

· Correctness. For any security parameter λ, for any mand for any x ∈ L s.t. R(x, w) holds, we have that Pr[
Decrypt(Encrypt(1λ , x, m), w) = m] = 1 − negl(λ).
· Soundness Security. For any x ∈/ L, for any PPT adversary
A and messages m0 , m1 ∈ M,
| Pr[ A(Encrypt(1λ , x, m0 )) = 1] - Pr[ A(Encrypt(1λ , x,m1 )) = 1] |≤ negl(λ).
The Security-Correctness Gap. Correctness requires
an algorithm can decrypt if x ∈ L and it knows w s.t.
R(x, w). Soundness Security requires if x ∈/ L then no PPT
algorithm can decrypt. This security does not define on thecase when x ∈ L. But since distinguishing x ∈ L and x ∈/L
is NP-complete, decryption would be diﬃcult even if x ∈ L.

4.1.2 Definition of Graph and Hamilton Cycle Problem

4.2

A graph G = (V, E) is a pair of a set of vertices V anda set of edges E associated with pairs of vertices, both being assumed finite. Let V (G) = {v1 , v2 , · · · , vn }, E(G) ={e1 , e2 , · · · , em }, |V | = n, |E| = m. We will describe an edge
between vertex vi and vertex vj as ei,j . A walk of length kfrom v0 to vk is P = (V, E) with V = {v0 , v1 , · · · , vk }, E ={e0,1 , · · · , ek−1,k }. A path is a walk with all diﬀerent vertices. A cycle is a path which start vertex is equal to thegoal vertex. A cycle that visits all vertices of V is calleda Hamilton Cycle (HC). A directed graph is a graph where
each edge has a direction, in such graph, ei→j denotes anedge from vertex vi to vertex vj . An undirected graph is one
where every edge has both ei→j and ej→i . A simple graphis one which has no self-loop or multiple edges.
The Hamilton Cycle Problem (HCP) is that, given a graph
G = (V, E), decide whether G has a HC or not. A graph witha HC is called Hamiltonian Graph. HCP is NP-complete
both for directed graphs and undirected graphs.

Design Principle

We use a directed hamiltonian graph to construct our witness encryption. First, we consider design of blinding factor
which hides plain text. HC passes every vertex in a graphexactly once , so we assign a secret to every vertex and set
some value storing the secret to every edge. We generatea blinding factor from these secrets of all vertices and hidea message by the blinding factor and make it a ciphertext.
Another components of ciphertext are edge secrets. One
who knows a HC can collect all secrets from ciphertext using the knowledge of HC and he can recover the blinding
factor. Diﬃculty of designing such blinding factor is that,during decrypt one who knows HC can generate the blinding factor and during encrypt the encryptor creates the samevalue without knowledge of HC.
We adopt to use high-dimensional matrix for achieving
this restriction of ordering on decryption because of matrix
holds non-commutative. We assign an adjacency matrix toeach edge, in which we set a secret of starting vertex, andput these adjacency matrices of all edges in the ciphertext.
A decryptor who knows the HC can multiply all adjacency
matrices in the order of the given HC and can make a product of the secrets of all vertices in the graph. The productvalue has no order, so the encryptor also can make the samevalue.
Detail of the design. We name vertices by its index
like 1, 2, · · · , n and let Pi→j be a matrix assigned to an edge
ei→j . We set a secret si of vertex i to the (i, j)-th elementin Pi→j . An element of (i, j) in a product matrix of two
adjacent matrices Pi and Pj is a product si sj . By multiplying matrices of edge in order of the given HC which starts
and goals at vertex i, the element of (i, i) in the productmatrix is Πj∈[n] sj . This value is independent of the order ofvertices, so encryptor also can make this value from secrets
assigning to vertices.
To prevent pulling out a secret si in the edge matrix Pi→j ,it is necessary to randomize edge matrices. For this, we takein a technique of oblivious transfer proposed by Joe Kilian[Kil88]. We assign a randomized matrix Ri and its inverse
Ri−1 to each vertex and set Ri−1 Pi→j Rj be a new edge matrix. When multiply these new matrix of adjacency edge,
e.g. Ri−1 Pi→j Rj and Rj−1 Pj→k Rk , the product Rj Rj−1 becomes identity matrix, so the connected edge matrices becomes Ri−1 Pi→j Pj→k Rk . This works sequentially, a productmatrix of connected edge matrices in a path that starts vertex i and goals vertex x becomes Ri−1 Pi→j · · · P(x−1)→x Rx .

4.1.3 Generic Colored Matrix Model
Garg et al. defined a generic colored matrix model in[GGH13+] that captures attacks where the adversary is only
allowed to add/multiply matrices in the correct order. They
represent this restriction as color assigned to left and right ofmatrix and handle. For every matrix M , the corresponding
record is (h, M, (m, LC), (n, RC)) where h is handle, M ism × n matrix, LC is left color, and RC is right color.
Setup. The represent oracle choose an initial set of lcolored matrices and assigns to them the handle, inserts into
the database the record {(hi , Mi , (mi , LCi ), (ni , RCi ))}li=1 ,and sends {(hi , (mi , LCi ), (ni , RCi ))}li=1 to the adversary
but not the matrix M .
The adversary sends queries through two handles. A represent oracle, who performs generic computation to the adversary, looks up records corresponding the two handles inthe database and if their color and row/column size satisfy the order restriction of addition or multiplication thenthe oracle adds or multiplies the two matrices. If the result record is not in the database then the oracle inserts therecord with new handle h′ into database. Then the oracle
returns a contained or new handle. The adversary being unable to get matrix, he can only adds and multiplies throughgiven handles. The following is the process of representation
oracle.
Addition. When the adversary makes query add(h1 , h2 ),

18

x−1
If i ̸= x then, the secret Πx−1
k=i sk in the matrix Πk=i Pk is
randomized, so it is impossible to pull out the secret. The
other hand, if i = x then, the product is Ri−1 Pi→j · · · Py→i Ri
and it is possible to pull out a trace Πyk=i sk of this product.
This means that this construction has a problem that one
who does not know HC can make blinding factor Πj∈[n] sj
from traces of partial cycles. We call partial cycle as ”shortcycle”.

Encrypt(1λ , G, m) → CT(params, pzt ) ← MM.InstGen(1λ , 1n )for i ∈[n] // all vertices
Ri ← sampMatrix(n)if i = 1 then R1′ ← sampMatrix(n)else create a invert matrix Ri−1 from Riri ← samp() si ← samp()
for i ∈[n]for j s.t. edges i → j are out-edges of vertex i in G
create a n × n matrix Pi→j
(Pi→j )1,1 := ri (Pi→j )i,j := si(Pi→j )x,y := 0 if (x, y) ̸= (1, 1) and (i, j)
if i = 1 then Ei→j := R1′ P1→j Rj // level-0
else
Ei→j := Ri−1 Pi→j Rj // level-0
Êi→j ← encodeMatrix(1, Ei→j ) // level-1
Create an n × n matrix P ′(P ′ )1,1 := Πi∈[n] ri + Πi∈[n] si(P ′ )x,y := 0 if (x, y) ̸= (1, 1)
for i, j ∈ [n]u := u||MM.ext(pzt , MM.enc(n, (R1′ P ′ R1 )i,j ))C := m ⊕ ext(u)return CT = (C, {Êi→j }(i,j)∈E(G) , G)

Definition 4 (Short Cycle). We call a cycle ”shortcycle” if the cycle satisfies:
1. The cycle does not pass all vertices in a graph.
2. Each vertices in the cycle is passed only once.
In other words, ”short cycle” is a cycle except HC.
We assign one more secret ri to each vertex i and set
that to the (1, 1)-th element of every edge matrix Pi→j . A(1, 1)-th element of a product matrix of edge matrices in acycle that starts and goals vertex 1 becomes Πri + Πsi . We
regard HC as a cycle that starts and goals vertex 1, so aelement (1, 1) in product of edge matrices in HC becomesΠj∈[n] rj + Πj∈[n] sj . This value is unable to be calculated
from traces, that are Πr+Πs from a short cycle not including
vertex 1.
For the purpose of security proof, we assign another matrix R1′ instead of R1−1 s.t. R1′ R1 ̸= identity matrix. In a
product of in-edge matrix and out-edge matrix about vertex 1, R1−1 R1′ is not canceled, so it prevent pulling out a
trace. The blinding factor is now changed to R1′ (Πj∈[n] rj +
Πj∈[n] sj )R1 .
Every values assigned to vertex (i.e., secrets si , ri andall elements of random matrices Ri , Ri−1 and R1′ ) are encoded at level-0 by sampling algorithm of multilinear maps.
During making edge matrix in encrypt algorithm, all components in edge matrix Ri−1 Pi→j Rj are encoded to level-1
and rerandomized, the rerandomized encoding keeps additive and multiplicative homomorphism but does not keep
homomorphism divisionally. We set up this encoding system with level-n. Using this zero-test parameter, we canextract a deterministic string from level-n encoding of eachelement in R1′ (Πj∈[n] rj +Πj∈[n] sj )R1 . We concatenate these
extracted values and extract a random value of this concatenation by a strong randomness extractor. The extracted
value is finally our blinding factor.

sampMatrix(n) → M
create a n × n matrix M
for i, j ∈ [n]Mi,j ← MM.samp() // level-0
return M
encodeMatrix(k, M ) → M
for i, j ∈ [n]Mi,j ← MM.reRand(k, MM.enc(k, Mi,j )) //level-k
return M
Decryption. Decryption algorithm takes as input a ciphertext CT and a hamilton cycle HC as witness. We can
suppose the first vertex of HC is vertex 1. The algorithmchooses edge matrix in CT in the order of HC and multiplies them. Then it extracts a deterministic string for every
element in the product by MM.ext and it concatenates allof the strings. Here j = HC(i) denotes a next vertex to i in
HC {· · · , i, j, · · · } .
Decrypt(CT, HC)
M := Ê1→HC(1) ÊHC(1)→HC 2 (1) · · · ÊHC n−1 (1)→1
for i, j ∈ [n]u := u||MM.ext(pzt , MM.enc(n, Mi,j ))return m := C ⊕ ext(u)4.3 Our Construction
In our scheme of witness encryption, a NP-complete language is Hamilton Cycle Problem, and a statement is a graph
G. As building blocks, we use a multilinear map MM and arandomness extractor ext. Notations: The symbol || denotes
to concatenate strings. We omit ”params” for simplicity inthe following algorithms.

4.3.2

Correctness

Now we show a blinding factor u recovered in the decryption algorithm is the same as u in the encryption algorithm.
First, we evaluate M in the decryption. Every element in M
is rerandomized encoding and we can homomorphically add
and multiply them. So M is equivalent to level-n encodingof the following product.

4.3.1 Concrete Construction
Encryption. Encryption algorithm takes as input security
parameter λ, a graph G of n vertices as statement of language, and a message m. First, it generates parameters ofM M specifying level-n. Next, creates a level-0 encoded random matrix Ri and samples two level-0 encodings ri and si
for every vertices i in G. Then it creates matrix Pi→j foredge ei→j and set ri and si to the matrix. A public matrix
Êi→j is product of Ri−1 , Pi→j and Ri , whose elements are
encoded level-1. Last, it creates blinding factor from all si
and ri and hides a message m.

−1(R1′ P1→2 R2 )(R2−1 P2→3 R3 ) · · · (R(n−1)
P(n−1)→1 R1 )′= R1 P1→2 P2→3 · · · P(n−1)→1 R1′′
Let P ′′ be P1→2 P2→3 · · · P(n−1)→1 , then P1,1
= Πi∈[n] ri +′′Πi∈[n] si and Px,y = 0 for (x, y) ̸= (1, 1). So P ′′ is equal toP ′ calculated in the encryption algorithm. For each elementin P ′ and P ′′ , their output values by MM.ext are the same.

19

Therefore the blinding factor made by the encryption algorithm and the decryption algorithm are the same.

ored matrix model for our witness encryption using multilinear maps. In our witness encryption, a matrix assigned toeach edge corresponds to one record in the generic cyclic colored matrix model. To multiply two colored matrices(h1 , M1 ,(m1 , LC1 ), (n1 , RC1 )) and (h2 , M2 , (m2 , LC2 ), (n2 , RC2 )) bymult(h1 , h2 ) means to make a path by connecting two edges,
and if LC1 = RC2 , it means that the start vertex and thegoal vertex are the same, in other words, a path becomesa cycle in our scheme. So, in the security game, the representation oracle returns a handle of trace if the result ofmult(h1 , h2 ) becomes a cycle. Exceptionally, a random matrix R1′ , which is not a inverse of R1 , is assigned to out-edgesof vertex 1, so the left and right colors are diﬀerent and theoracle does not return a handle of trace in this case.
Details of the Security Game for our Witness Encryption.
Setup. The oracle is given a graph G, it makes matrix type
records for all edges in G and inserts into database them andreturns their representations {(h, (m, LC), (n, RC))} without giving matrix M itself to the adversary. To say moredetails, the oracle samples two level-0 encoded secrets ri
and si by MM.samp() for each vertex i. For every edge
ei→j , it sets the secrets to a adjacent matrix Mi→j where(Mi→j )1,1 = ri and (Mi→j )i,j = si , and inserts into the
database those records {(h, Mi→j , (n, i), (n, j))}. Then it
gives {(h, (n, i), (n, j))} to the adversary.
Addition. When the adversary makes query add(h1 , h2 ),the oracle looks up the records corresponding to h1 , h2 inthe database. If such records exists then, if (m1 ̸= m2 ) or
(LC1 ̸= LC2 ) or (n1 ̸= n2 ) or (RC1 ̸= RC2 ) then return bot.
Otherwise, it adds M = M1 + M2 and looks up the record(M, (m, LC), (n, RC)), if it exists in the database then returns the handle, otherwise the oracle inserts the record(h, M, (m, LC), (n, RC)) with new handle h and returns thehandle.
Multiplication. When the adversary makes query mult(h1 ,h2 ), the oracle looks up the records corresponding to h1 , h2
in the database. If such records exists, if n1 ̸= m2 or RC1 ̸=
LC2 then return bot. Otherwise, it multiplies M = M1 M2and looks up the record (M, (m1 , LC1 ), (n2 , RC2 )), if it exists in the database then returns the handle, otherwise theoracle inserts the record (h, M, (m1 , LC1 ), (n2 , RC2 )) withnew handle h and returns the handle. If the matrices corresponding to h1 , h2 are both matrix type and they starts
and goals at same vertex such that the vertex is not 1 thenthe oracle computes a trace of M and puts the trace to1 × 1 matrix M and inserts into the scalar type record(h, M, (1, 0), (1, 0)) and returns its handle to the adversary.
Scalar Multiplication. When the adversary makes query
scalar mult(h1 , h2 ), the oracle looks up the records corresponding to h1 , h2 in the database. If such records exists,
let first record to be matrix type, second record to be scalar
type, then the oracle multiplies M = (M2 )1,1 M1 and looks
up the record (M, (m1 , LC1 ), (n1 , RC1 )), if it exists in the
database then returns the handle, otherwise the oracle inserts the record (h, M, (m1 , LC1 ), (n1 , RC1 )) with new handle h and returns the handle.

4.4 Proof of Security: Soundness Security
First we define a variant of generic colored matrix model:
a generic cyclic colored matrix model, and then define a security game based on the model.

4.4.1 Generic Cyclic Colored Matrix Model
We define a generic cyclic colored matrix model by expanding a generic colored matrix model defined by Garg etal. in [GGH13+] that captures attacks where the adversary
only adds and multiplies matrices in the correct order.
A matrix in our ciphertext is sandwiched in between two
random matrices, when multiply adjacent edge matrices,such random matrices are canceled. But when multiply
not-adjacent edge matrices, they are not canceled and randomization remains . The generic colored matrix model[GGH13+] modeled this situation as colored matrix: an adversary multiply matrices only if he queries two matrices
such that RC1 is the same as LC2 . Since our ciphertexts
are encoded, we can add and multiply elements in matrices
homomorphically but we can not divide one by another. In
the generic colored matrix model [GGH13+], a adversary
queries add and mult using handle, so, this models our encoding restriction.
If the LC and RC of a result matrix M are same thena trace of matrix M is possible to be pulled out. In theoracle’s process in our model, when such case, the oraclecomputes a trace of the result matrix M , and returns arecord additionally for the trace. In our model, there are tworecord types: ”Matrix Type” and ”Scalar Type”. We add aquery scalar mult that multiplies a trace value in a ”Scalar
Type” record by a matrix in a ”Matrix Type” record.
We does not return a handle of a eigenvalue of a matrix, because computing the eigenvalue needs division during Gaussian elimination, but the division is not provided
on the encoding system used in our scheme.
Detail of The Generic Cyclic Colored Matrix Model
Setup and Addition algorithms are the same as the original
generic colored matrix model. In Multiplication algorithm,
the following process is executed after Multiplication processof the original model. If the types of record corresponding
h1 and h2 are both matrix type and LC1 and RC2 of result
matrix are the same then the oracle computes a trace M ′of the result matrix. If the trace is in the database then returns its handle, otherwise inserts into the database the newrecord with new handle (h′′ , M ′ , (1, 0), (1, 0)) and returns its
handle.
Scalar Multiplication. When the adversary makes query
scalar mult(h1 , h2 ), the oracle looks up the records corresponding to h1 , h2 in the database. If such records exists, we view the first record as matrix type and the second record as scalar type, then the oracle computes product
M =trace×M1 . If the database already contains the matrix(M, (m, LC), (n, RC)) then oracle returns its handle. Otherwise, the oracle assigns a new handle h′ and inserts into
the database (h′ , M, (m1 , LC1 ), (n1 , RC1 )) and returns the
new handle.

4.4.3

4.4.2 Definition of Security Game for Witness Encryption using Multilinear Maps

Proof of Security

Theorem 2. Our witness encryption based on HC is soundness secure in the generic cyclic colored matrix model.

We define a security game based on the generic cyclic col-20

M = M1 · M2h ← db.select(M, (m1 , LC1 ), (n2 , RC2 ))if h does not exist in database thenh := new handle
db.insert(h, M, (m1 , LC1 ), (n2 , RC2 ))if types of h1 , h2 are matrix type and (LC1 = RC2 ) and(LC1 ̸= 1) thencreate 1 × 1 matrix Mt(Mt )1,1 = M1,1 + MLC1 ,RC2
ht ← db.select(Mt , (1, 0), (1, 0))
if ht does not exist in database thenht := new handle
db.insert(ht , Mt , (1, 0), (1, 0))
return (h, ht )else return hMore precisely, the probability that an adversary distinguishes a real model and a simulation is bounded above
T 3 /p from the Schwartz-Zippel lemma [S80] [Z79] where an
adversary receives at most T handles from the oracle and thesecrets r, s are independently and uniformly chosen from Zp .
T 3 means a number of handles × a number of combinationsof r, s.
Proof. We make simulator which input is a graph which
does not have any HC, and show that there is no handleof the matrix corresponding to the ”full cycle”:Πj∈[n] rj +
Πj∈[n] sj in a view of the adversary.
Algorithm of Simulator. We assume there are t shortcycles which does include vertex 1 in a given graph G. Let
sc be a set of vertices of a short cycle. Input values to asimulator is a graph G. When simulator needs to return ahandle of trace, it calculates a trace from the result matrix,
then returns the result’s handle.
Notations:
A given graph G has n vertices. A record reci denotes therecord (hi , Mi , (mi , LCi ), (ni , RCi )) in the database.
Setup. A simulator makes edge matrices for all edges
in given graph G, and inserts into the database those edge
matrices and sends representations of edge without matrix
M to the adversary.

Scalar Multiplication. It multiplies a trace value inscalar type record by a matrix in a matrix type record andinserts the result record into database and returns the handle.
scalar mult(h1 , h2 )rec1 = db.select(h1 ) rec2 = db.select(h2 )let rec1 be a n × n edge matrix.
let rec2 be a 1 × 1 trace matrix.
if not above then return ⊥M = (M2 )1,1 · M1h ← db.select(M, (m1 , LC1 ), (n1 , RC1 ))if h does not exist in database thenh := new handle
db.insert(h, M, (m1 , LC1 ), (n1 , RC1 ))return h

for i ∈[n] // all vertices
create a variable Ri Si
for j s.t. edges i → j are out-edges of vertex icreate a n × n matrix Mi→j
(Mi→j )1,1 := Ri (Mi→j )i,j := Si(Mi→j )x,y := 0 if (x, y) ̸= (1, 1) and (i, j)
hk := new handle
db.insert(hk , Mi→j , (n, i), (n, j))give {(hk , (n, i), (n, j))} to the adversary.

Analysis. We discuss about diﬀerence of distributions ofadversary’s view between real model and simulation. The
simulator replaces random elements of edge matrices into
variables, so it’s possible that result of calculation of theelements is in database at real model but not in database atsimulation. In such a case, he returns existing handle at realmodel and returns new handle at simulation, so the view ofadversary is diﬀerent. But its provability is bounded above
T 3 /p from the Schwartz-Zippel lemma [S80] [Z79] where an
adversary receives at most T handles from the oracle and thesecrets r, s are independently and uniformly chosen from any
finite setS, |S| = p.
We show there is no record of our blinding factor in asimulator’s database. Now we recall that our blinding factor is concatenation of all elements in the product matrix
R1′ (Πj∈[n] rj + Πj∈[n] sj )R1 . We confirm about edge matrix
records at each query. After setup, value in matrix column is
M s.t. M1,1 = Ri and Mi,j = Si for every edge ei→j . Whentwo matrices M1 and M2 are added by add query, the result
matrix M is such that M1,1 = (M1 )1,1 + (M2 )1,1 , Mi,j =(M1 )i,j + (M2 )i,j and other elements are all zero. When two
matrices M1 and M2 are multiplied by mult query, if LC1 ̸=
1′ or RC2 ̸= 1 then the result matrix M is such that M1,1 =(M1 )1,1 (M2 )1,1 , Mi,k = (M1 )i,j (M2 )j,k and other elements
are all zero. If LC1 = 1′ and RC2 = 1 then the result matrix M is such that M1,1 = (M1 )1,1 (M2 )1,1 + (M1 )i,j (M2 )j,k
and other elements are all zero. When a trace v and matrix M1 are multiplied by scalar mult, the result matrix M
is such that M1,1 = v(M1 )1,1 , Mi,j = v(M1 )i,j and otherelements are all zero. We notice that elements in M1 andAddition. If types of associated h1 , h2 are both matrix
type, if their start vertices are same and their goal vertices
are also same then the simulator adds two matrices and inserts its record into database and returns the handle.
add(h1 , h2 )rec1 = db.select(h1 ) rec2 = db.select(h2 )if (m1 ̸= m2 ) or (LC1 ̸= LC2 ) or (n1 ̸= n2 ) or (RC1 ̸=
RC2 ) then return ⊥M = M1 + M2
h ← db.select(M, (m1 , LC1 ), (n1 , RC1 ))if h does not exist in database thenh := new handle
db.insert(h, M, (m1 , LC1 ), (n1 , RC1 ))return hMultiplication. If types of associated h1 , h2 are bothmatrix type, if first goal vertex and second start vertices are
same, and first col size and second row size are same thenthe simulator multiplies the two matrices. If start and goal
are same but not 1 then it calculates a trace from the result
matrix M , and inserts its record into database and returns
the handle.
mult(h1 , h2 )rec1 = db.select(h1 ) rec2 = db.select(h2 )if (n1 ̸= m2 ) or (RC1 ̸= LC2 ) then return ⊥21

M2 in above queries may be multiplied by some traces byscalar mult queries.
Now we consider whether there is a record of matrix M ′′s.t. M1,1= Πi∈[n] Ri + Πi∈[n] Si and other elements are all
zero for our blinding factor.

others are level-1, and extracts a same group key from that.
The piling encodings mechanism is useful in some cases toreduce a lot of traﬃc in the one-round GKE or existing GKEthat does not use multilinear maps. In our witness encryption scheme, we expressed Hamilton Cycle, that visits eachvertex in the graph exactly once, using this piling encodings
mechanism. We proved its soundness security based on our
Generic Cyclic Colored Matrix Model.

Claim 4. In the database, if there is records where LC =1′ and RC = 1 and M1,1 has some value v and Mi,j (i, j ̸=1) is zero then6.

v = Σsc (Πsc′i (Πj∈sc′i Rj + Πj∈sc′i Sj ))(Πj∈sc Rj + Πj∈sc Sj ),· · · Eq(1)REFERENCES[BCPQ] E. Bresson, O. Chevassut, D. Pointcheval, and J.
J. Quisquater. Provably authenticated groupdiﬃe-hellman key exchange. In proceedings of 8th
ACM Conference on CCS E., pages 255-264, 2001.
[BS03] Dan Boneh and Alice Silverberg. Applications ofmultilinear forms to cryptography. In Contemporary
Mathematics 324, pages 71-90, 2003.
[CLT13] Jean-S é bastien Coron, Tancr è de Lepoint,
Mehdi Tibouchi. Practical Multilinear Maps over the
Integers. In CRYPTO 2013, pages 476-493.
[GGH13] Sanjam Garg, Craig Gentry, and Shai Halevi.
Candidate multilinear maps from ideal lattices andapplications. In EUROCRYPT 2013, Lecture Notes in
Computer Science. Springer, 2013. Cryptology ePrint
Archive, Report 2012/610.
[GGH13+] Sanjam Garg, Craig Gentry, Shai Halevi,
Mariana Raykova, Amit Sahai, Brent Waters.
Candidate Indistinguishability Obfuscation andFunctional Encryption for all Circuits. In FOCS 2013,
pages 40-49.
[GGHSW13] Sanjam Garg, Craig Gentry, Shai Halevi,
Amit Sahai, and Brent Waters. Attributebased
encryption for circuits from multilinear maps. In
Cryptology ePrint Archive, Report 2013/128, 2013.
[GGSW] Sanjam Garg, Craig Gentry, Amit Sahai and
Brent Waters. Witness Encryption and its
Applications. In STOC, pages 467-476, 2013.
[Kil88] Joe Kilian. Founding cryptography on oblivioustransfer. In Janos Simon, editor, In STOC, pages
20-31. ACM, 1988.
[S80] T.Schwartz. Fast probabilistic algorithms forverification of polynomial identities. In Journal of theACM 27: pages 701 ‒ 717, 1980.
[Shoup] V. Shoup. Sequences of Games: A Tool for
Taming Complexity in Security Proofs. In Cryptology
ePrint Archive, Report 2004/332, 2004.
[STW96] M. Steiner, G. Tsudik, and M. Waidner.
Diﬃe-Hellman Key Distribution Extended to Group
Communication. In Proceedings of the 3rd ACM
Conference on Computer and Communications
Security, pages 31-37. ACM Press, 1996.
[Z79] R. Zippel. Probabilistic algorithms for sparse
polyno-mials. In Proceedings of EUROSAM, Springer
Lecture Notes in Computer Science Vol.72, pages 216‒ 226, 1979.

where sc denotes a short cycle which starts and goals at vertex 1, sc′ denotes a short cycle which does not include vertex
1.
Proof. A trace is registered into database when a shortcycle which does not include vertex 1 is made by mult query.
After the trace is registered, a matrix may be scalar multiplied by scalar mult query. Those matrices may be added
and multiplied by add and mult. Using such two matrices,
when a short cycle which starts and goals at vertex 1 is madeby mult, a record where LC = 1′ and RC = 1 and M1,1 hassome value v and Mi,j (i, j ̸= 1) is zero is registered. The
form of v is v = (Σsc Πsc′i (Πj∈sc′i Rj + Πj∈sc′i Sj ))(Πj∈sc Rj +
Πj∈sc Sj ). From the observation before Claim 4, add andscalar mult does not change the color and element positionof the result matrix, so records where LC = 1′ and RC = 1
must be made from records where LC = 1′ and RC = 1
by add or scalar mult. The result M1,1 has a form v =Σsc (Πsc′i (Πj∈sc′i Rj + Πj∈sc′i Sj ))(Πj∈sc Rj + Πj∈sc Sj ).
2Claim 5. The Eq(1) never equals to Πi∈[n] Ri + Πi∈[n] Si .
Proof. To make Πi∈[n] Ri +Πi∈[n] Si , it is necessary to multiply one (Πj∈sc Rj +Πj∈sc Sj ) and some (Πj∈sc′i Rj +Πj∈sc′i Sj )because the input graph does not contain any Hamilton Cycle. The result has cross terms of Rj Sj , and for canceling this cross terms it needs a new product of (Πj∈sc Rj +
Πj∈sc Sj ) and (Πj∈sc′i Rj + Πj∈sc′i Sj ) of smaller short cycles.
Then the result has their new cross terms. To cancel thosecross terms recursively, finally it becomes sums of productsof (Πj∈sc Rj + Πj∈sc Sj ) and (Πj∈sc′i Rj + Πj∈sc′i Sj ) of minimum short cycles, and their cross terms are unable to becanceled. Therefor the Eq(1) never equals to Πi∈[n] Ri +Πi∈[n] Si .
2
Now the proof of Theorem 2 is complete.
2

5. CONCLUSION
We proposed two applications of multilinear maps, GKE
and witness encryption. The communication structure ofthese schemes are both formed like that some pre-specified
number of points are connected by communication lines, andthese schemes share a common mechanism. The mechanismis that, each point has a secret level-0 encoding and its level1 encodings are piled up in a product one by one along thelines. Eventually a specified level encoding is generated, anda deterministic value is extracted from the encoding.
The security of our GKE scheme is based on GDDH assumption. Each party generates a level-(N-1) encoding, in
its source encodings only its own encoding is level-0 and

22