# Efficient Asymmetric Index Encapsulation Scheme for Anonymous Content Centric Networking

Authors: Rong Ma; Zhenfu Cao; Xingkai Wang
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Content Centric Networking (CCN) is an effective communication paradigm that well matches the features of wireless environments. To be considered a viable candidate in the emerging wireless networks, despite the clear benefits of location-independent security, CCN must at least have parity with existing solutions for confidential and anonymous communication. This paper designs a new cryptographic scheme, called Asymmetric Index Encapsulation (AIE), that enables the router to test whether an encapsulated header matches the token without learning anything else about both of them. We suggest using the AIE as the core protocol of anonymous Content Centric Networking. A construction of AIE which strikes a balance between efficiency and security is given. The scheme is proved to be secure based on the DBDH assumption in the random oracle with tight reduction, while the encapsulated header and the token in our system consist of only three elements.


---

## Body

## 1. Introduction

Conventional networking protocols designed to support end-to-end communications between nodes which are uniquely identified through an IP address may fail in wireless environments due to dynamic changes caused by the mobility. Content Centric Networking is an emerging networking architecture with the goal of becoming an alternative to the IP-based Internet. Communication in CCN adheres to the pull model. Its primary characteristic is that content and routable content in the network are always named. Interests represent the willingness of the consumer to retrieve certain content, independently of its location. A consumer who wishes to obtain content first issues an interest by name, which is then routed to the producer or router that is capable of satisfying the request. The corresponding content carrying the same name is then sent to the consumer along the reverse path.The CCN architecture has some innate privacy friendly features; for example, the source addresses of contents are hard to trace. However, support for name privacy is not a standard feature. Names reveal significantly more information about content than IP addresses [1].ANDaNA [2] and AC3N [3] are the initial attempt to provide anonymous communication in CCN. They are inspired by Tor, using onion-like encryption to wrap interests, and forwarded by participating anonymizing routers. However, caching mechanism as one of the most important features of CCN could not be used in these designs due to the lack of an cryptographic primitive keeping the name private while ensuring accessibility and routability.In this paper we propose a new cryptographic scheme called Asymmetric Index Encapsulation (AIE) to hide the name except the entity which is given appropriate token. Token can be viewed as a kind of encrypted interest; it can only be generated from the authorized consumers and the functionality of the token kept secret even during the name and interest match procedure. We believe AIE is a positive answer to the open question raised in [1, 4]. AIE is proved to be secure based on the DBDH/CDH assumption in the random oracle with tight reduction, while the encapsulated header and the token in our system consist of only three elements. Moreover, AIE is applicable in any CCN incarnation, for example, CCNx and NDN [5].


### 1.1. Organization

The rest of this paper is organized as follows. The next section shows the related work of our paper. Section3 gives an overview of CCN. The scheme description is presented in Section 4. Definitions of security model are given and discussed in Section 5. The reduction proofs are shown in Sections 6 and 7. Then we show implementation and provide an analysis of the performances of the proposed schema in Section 8. Finally, we conclude with related work and future work in Section 9.


## 1.1. Organization

The rest of this paper is organized as follows. The next section shows the related work of our paper. Section3 gives an overview of CCN. The scheme description is presented in Section 4. Definitions of security model are given and discussed in Section 5. The reduction proofs are shown in Sections 6 and 7. Then we show implementation and provide an analysis of the performances of the proposed schema in Section 8. Finally, we conclude with related work and future work in Section 9.


## 2. Related Work

Symmetric searchable encryption with adaptive security against chosen-keyword attacks was first considered explicitly in [6], where symmetric index encapsulation was first considered explicitly by [7]. Unlike in asymmetric settings, securely encapsulating a single keyword/index is nearly trivial in symmetric settings. In these schemes and subsequent work [8–11], researchers focus on how to handle full text indices and try to improve efficiency. Another line of work uses deterministic encryption [8, 12]. It only provides security for data and queries that have high entropy.Starting with the work of Boneh et al. [13–15], searchable encryption has also been considered in the public key setting [10, 16–19]. The early works lack function privacy until the first definition was suggested very recently by Boneh et al. [20].One of the key goals of CCN projects is “security by design” [21]. In contrast to today’s Internet, where security problems were identified along the way, the research community stresses both awareness of issues and support for features and countermeasures from the outset. To this end, a few of papers investigate various attacks and solutions in CCN or CON [1, 2, 5]. However, to the best of our knowledge, there is an absence of cryptographic perspective. The major contribution of our paper is in defining a new cryptographic primitive known as Asymmetric Index Encapsulation scheme.A preliminary version of this paper [22], which concentrated on solving the related fundamental cryptographic problem, appeared at ProvSec 2016, while this paper focuses more on solving practical problem of CCN network. The extra contents mainly are shown in Sections 8 and 9.


## 3. CCN Overview

We now review the building blocks of Content Centric Networking. There are three types of entities in CCN:(i)
Consumer which issues interests for content(ii)
Producer which generates and publishes content to the network(iii)
Routers which forward interest messages and content between consumers and producersCCN supports two types of packets:(i)
Named content: in CNN, contents are always named to facilitate data dissemination and search. A content name is a URI-like string composed of one or more variable-length segments.(ii)
Interest: to obtain content, consumer issues a request, called an interest message, with the name of the desired content. This interest will be satisfied by either a router or the content producer.Name and interest matching in CCN is exact, for example, an interest for “/2017/news.txt” can only be satisfied by a content object named “/2017/news.txt.”Each CCN entity should maintain the following components:(i)
Forwarding Interest Base (FIB): this includes a lookup table used to determine entities for forwarding incoming interests.(ii)
Pending Interest Table (PIT): this include a lookup table of outstanding pending interests and a set of corresponding incoming entities.(iii)
Content Store (CS): this is a buffer used for content caching and retrieval. Each network entity can provide content caching, which is limited only by resource availability. Note that this is different from packet buffers in today’s routers, as cache size is expected to be several orders of magnitude bigger in CCN.All CCN communication is initiated by a consumer that sends an interest for a specific content [23]. When a router receives an interest, it looks up its PIT to determine whether an interest for the content is pending:(i)
If the desired name in the PIT, the interest does not need to be forwarded further. If the arrival entity is new, the router just updates the PIT entry by adding a new incoming entity.(ii)
Otherwise, the router looks up its CS for a matching content. If it succeeds, the cached content is returned and no new PIT entry is needed. If no matching content is found, the router creates a new PIT entry and forwards the interest using its FIB.During receipting of the interest, the producer distributes requested content among the network, thus satisfying the interest. Then, the content is forwarded towards the consumer, by the path of the preceding interest, in reverse.


## 4. Scheme Description

Formally, AIE is specified by a quadruple of probabilistic polynomial-time algorithms:(i)
The setup algorithmSetup is run by the central authority, takes a security parameter 1λ, and outputs the public system parameters pp together with a master secret key mk. The system parameters will be publicly known, while the master key will be known only to the key generation algorithm.(ii)
The index (a.k.a. name) encapsulation algorithmEnc is run by the producer, takes as input an index x, and outputs encapsulated header hdx.(iii)
The token generation algorithmGen is run by the central authority, takes as input the master secret key mk and an interest y, and outputs a related token tky.(iv)
The test algorithmTest is run by the router, takes as input a header hdx and a token tky, and outputs a value which indicates the matching relationship between tky and hdx, “1” for matching and “0” on the contrary. Usage of this algorithm is to show the linkability between headers and tokens.To deploy AIE in CCN, we should introduce a trusted central authority which is in charge of issuing token. As illustrated in Figure1, if a consumer plans to request a content named x, instead of sending the plain interest packet, it should use the token issued by Gen(x) from the central authority. Token is like a private key of public encryption scheme. However, its functionality is not decrypting but testing.Figure 1
Instantiating AIE in anonymous CCN.When a producer generates new content namedy, it encrypts the content at first. The encryption algorithm used by consumers to conceal content should be secure against adaptive chosen ciphertext (CCA) attacks. Then, the producer runs encapsulation algorithm Enc to encapsulate the name y. We call the output of Enc(y) the encapsulated header of y. Finally, a signature binds the encrypted content with its encapsulated header and provides origin authentication no matter how or from where it is retrieved. For any adversary without the correct token, this signed and encrypted packet will lose no information under our security model (discussed in Section 5.4).When a token is received and there are no same pending tokens in its cache, router runsTest algorithm to find an encapsulated header which matches the token. If there is no such encapsulated header, the router forwards this new token to the neighbor routers. When the desired content is returned or there is already an encapsulated header matching this token in the cache, the router forwards it out on all neighbors and flushes the corresponding cache entry.Since adversary can mount a guessing attack, exhaustively testing the known token, we give a reasonable security model in Section5.5 to ensure that there is no more obviously effective attack better than the brute force method.


### 4.1. Construction

LetGroupGen be a probabilistic polynomial-time algorithm taking 1λ as security parameter and outputs (G,GT,p,g,e), where G and GT are groups of prime order p, 2λ<p<2λ+1, g is a generator of group G, and e:G×G→GT is a nondegenerate efficiently computable bilinear map. See [24] for a description of the properties of such pairings. We present AIE scheme as follows; the design inspiration comes from [20, 25].(i)
Setup(1λ): on input security parameter 1λ, the setup algorithm works as follows:
(1)
Generate(p,G,GT,g,e)←GroupGen(1λ).(2)
Randomly samplea←Zp∗.(3)
Computega←ga.(4)
Choose two cryptographic hash functionsH and F:0,1∗→G. The security analysis will view H, F as random oracles.(5)
Outputa as master key and (g,ga) as public parameters.(ii)
Enc(pp,x): given x, the index encapsulation algorithm does the following:
(1)
Randomly samplingr←Zp∗(2)
Computingc←gr, T←e(ga,H(x))r, and R←e(ga,F(x))r(3)
Outputting(c,T,R) as an encapsulated header(iii)
Gen(mk,y): on input master key a and an index y, the token generation algorithm does the following:
(1)
If the same query fory is repeated twice, then the same token is provided.(2)
It randomly choosesu,v←Zp∗.(3)
It computesd←(H(y)uF(y)v)a.(4)
It outputs and records(d,u,v) as the token of y.(iv)
Test(hd,tk): given an encapsulated header hd and a token tk, the test algorithm does the following:
(1)
It parseshd as (c,T,R) and tky as (d,u,v).(2)
It checks if the following equation holds true:(1)ec,d=Tu·Rv,and  if it holds, output “1,” meaningtk matches hd; else output “0.”Correctness. For any index x, we need to guarantee Test(hdx,tkx)=1, where hdx←Enc(x,pp) and tkx←Gen(x,mk). Denoting hdx=(c,T,R) and tkx=(d,u,v), that is clear since (2)ec,d=egs,HxuFxva=egs,Hxauegs,Fxav=ega,Hxsuega,Fxsv=Tu·Rv.


## 4.1. Construction

LetGroupGen be a probabilistic polynomial-time algorithm taking 1λ as security parameter and outputs (G,GT,p,g,e), where G and GT are groups of prime order p, 2λ<p<2λ+1, g is a generator of group G, and e:G×G→GT is a nondegenerate efficiently computable bilinear map. See [24] for a description of the properties of such pairings. We present AIE scheme as follows; the design inspiration comes from [20, 25].(i)
Setup(1λ): on input security parameter 1λ, the setup algorithm works as follows:
(1)
Generate(p,G,GT,g,e)←GroupGen(1λ).(2)
Randomly samplea←Zp∗.(3)
Computega←ga.(4)
Choose two cryptographic hash functionsH and F:0,1∗→G. The security analysis will view H, F as random oracles.(5)
Outputa as master key and (g,ga) as public parameters.(ii)
Enc(pp,x): given x, the index encapsulation algorithm does the following:
(1)
Randomly samplingr←Zp∗(2)
Computingc←gr, T←e(ga,H(x))r, and R←e(ga,F(x))r(3)
Outputting(c,T,R) as an encapsulated header(iii)
Gen(mk,y): on input master key a and an index y, the token generation algorithm does the following:
(1)
If the same query fory is repeated twice, then the same token is provided.(2)
It randomly choosesu,v←Zp∗.(3)
It computesd←(H(y)uF(y)v)a.(4)
It outputs and records(d,u,v) as the token of y.(iv)
Test(hd,tk): given an encapsulated header hd and a token tk, the test algorithm does the following:
(1)
It parseshd as (c,T,R) and tky as (d,u,v).(2)
It checks if the following equation holds true:(1)ec,d=Tu·Rv,and  if it holds, output “1,” meaningtk matches hd; else output “0.”Correctness. For any index x, we need to guarantee Test(hdx,tkx)=1, where hdx←Enc(x,pp) and tkx←Gen(x,mk). Denoting hdx=(c,T,R) and tkx=(d,u,v), that is clear since (2)ec,d=egs,HxuFxva=egs,Hxauegs,Fxav=ega,Hxsuega,Fxsv=Tu·Rv.


## 5. Security Models

We give the precise formal definitions based on the above discussion.


### 5.1. Notation

We denote byX=(X1,X2,…,Xq) a joint distribution of q random variables, and by x=(x1,x2,…,xq) a sample drawn from X. The min-entropy of a random variable X is H∞(X)=-log2(maxxPr[X=x]). A k-source is a random variable X with H∞(X)≥k. A (q,k)-block-source is a random variable X=(X1,X2,…,Xq), where, for each i∈1,2,…,q, (x1,…,xi-1) holds that XiX1=x1,…,Xi-1=xi-1 is k-source. The statistical distance between two random variables X and Y over a finite domain S is defined as(3)SDX,Y=12∑x∈SPr⁡X=x-Pr⁡Y=x.


### 5.2. DBDH and CDH Assumption

Decisional bilinear Diffie-Hellman (DBDH) problem is to distinguish two distributionsPBDH=(gα,gβ,gγ,e(g,g)αβγ) and RBDH=(gα,gβ,gγ,R) for random α, β, γ, and R. Computational Diffie-Hellman (CDH) problem is to compute gαβ given gα and gβ. To state the assumption asymptotically we rely on the bilinear group generator algorithm GroupGen(1λ).Definition 1.
LetGroupGen(1λ) be a bilinear group generator. The DBDH assumption holds for GroupGen(1λ) if, for all probabilistic polynomial-time algorithm B, its BDDH advantage, denoted by(4)AdvBDBDHλ=Pr⁡Bgα,gβ,gγ,eg,gαβγ=1-PrBgα,gβ,gγ,R=1,is a negligible function of λ, where the probability is over (G,GT,p,g,e)←GroupGen(1λ), α,β,γ←Zp∗, R←GT.Definition 2.
LetGroupGen(1λ) be a bilinear group generator. The CDH assumption holds for GroupGen(1λ) if, for all probabilistic polynomial-time algorithm B, its CDH advantage, denoted by(5)AdvBCDHλ=PrBgα,gβ=gαβ,is a negligible function of λ, where the probability is over (G,GT,p,g,e)←GroupGen(1λ), α,β←Zp∗.


### 5.3. The Leftover Hash Lemma

Definition 3 (universal hash function).
A collectionH of function H with form U→V is universal if for any x,x′∈U such that x≠x′ the following holds:(6)PrH←H⁡Hx=Hx′=1V.Theorem 4 (leftover hash lemma for block-source; see [20]).
LetH be a universal collection of functions H:U→V; let X=(X1,X2,…,Xq) be (q,k)-block-source where k≥log⁡V+2log⁡(1/ϵ)+Θ(1). Then there exists the distribution(7)H1,H1X1,H2,H2X2,…,Hq,HqXq,where (H1,H2,…,Hq)←Hq is ϵq-close to the uniform distribution over (H×V)q.


### 5.4. Security Model for Anonymity

AIE is anonymous ifEnc(pp,x) leaks no information about x. To capture the anonymity properties formally, a game between a challenger and an adversary A is defined as follows:(i)
Setup Phase: the challenger runsSetup(1λ) and sends pp to adversary A and keeps mk to itself.(ii)
Prechallenge Phase: in this phase, adversaryA is allowed to make token extraction query. The challenger responds to the query about index y by sending A to the output of Gen(mk,y).(iii)
Challenge Phase:A submits two indices x0, x1, which is restricted to the indices that he did not request in prechallenge phase. The challenger flips a fair binary coin b and returns Enc(pp,xb) as challenge header.(iv)
Postchallenge Phase: this phase is repeat of prechallenge phase. The adversary issues additional adaptive queries with the restriction where it can not request token ofx0 or x1.(v)
Guess Phase: finally,A submits a guess b′ of b. The adversary wins if b′=b.Definition 5 (anonymity of AIE).
AIE is anonymous if, for any probabilistic polynomial-time algorithmA, its ANON advantage, denoted by(8)AdvAANONλ=Prb′=b-12,is a negligible function of λ, where the probability is over the random bits used by the challenger and the adversary.


### 5.5. Security Model for Function Privacy

Formalizing such a notion is not straightforward since adversary can mount a guessing attack. If adversary has some knowledge that the token comes from a small set, it can encapsulate each candidate index and run the legitimateTest procedure to learn the function embedded inside the token. We adapt the notion from [20] which requires that Gen(mk,y) is indistinguishable from a random token if y is chosen from a sufficiently high min-entropy distribution. The following security game parameterized by a distribution D helps us capture properties of function privacy:(i)
Setup Phase: the challenger runsSetup(1λ) and sends both master secret key mk and public parameters pp to adversary A.(ii)
Challenge Phase: in this phase, the challenger samples an indices vector(x1,x2,…,xq) from the distribution D and then, for every i∈1,2,…,n, computes tki=Gen(mk,xi) and returns (tk1,…,tkq) to A.(iii)
Guess Phase: finally,A submits a guess of the distribution challenger has used. It outputs “0” standing for uniform distribution; otherwise it outputs “1.”Definition 6 (privacy of AIE).
AIE says private function if, for any probabilistic polynomial-time algorithmA and any (q,k)-block-source distribution D where q,k is a polynomial of λ, its PRIV advantage, denoted by(9)AdvAPRIVλ=PrΨDλ=1-PrΨRλ=1,is a negligible function of λ where R stands for uniform distribution.To gain reasonable high min-entropy in anonymous CCN, we suggest that data provider should assign a complicated name of the encrypted data. Since adversary can mount a guessing attack (exhaustively testing the token by using pairings), the definition of privacy actually guarantees that there is no more obviously effective attack better than the brute force method.


## 5.1. Notation

We denote byX=(X1,X2,…,Xq) a joint distribution of q random variables, and by x=(x1,x2,…,xq) a sample drawn from X. The min-entropy of a random variable X is H∞(X)=-log2(maxxPr[X=x]). A k-source is a random variable X with H∞(X)≥k. A (q,k)-block-source is a random variable X=(X1,X2,…,Xq), where, for each i∈1,2,…,q, (x1,…,xi-1) holds that XiX1=x1,…,Xi-1=xi-1 is k-source. The statistical distance between two random variables X and Y over a finite domain S is defined as(3)SDX,Y=12∑x∈SPr⁡X=x-Pr⁡Y=x.


## 5.2. DBDH and CDH Assumption

Decisional bilinear Diffie-Hellman (DBDH) problem is to distinguish two distributionsPBDH=(gα,gβ,gγ,e(g,g)αβγ) and RBDH=(gα,gβ,gγ,R) for random α, β, γ, and R. Computational Diffie-Hellman (CDH) problem is to compute gαβ given gα and gβ. To state the assumption asymptotically we rely on the bilinear group generator algorithm GroupGen(1λ).Definition 1.
LetGroupGen(1λ) be a bilinear group generator. The DBDH assumption holds for GroupGen(1λ) if, for all probabilistic polynomial-time algorithm B, its BDDH advantage, denoted by(4)AdvBDBDHλ=Pr⁡Bgα,gβ,gγ,eg,gαβγ=1-PrBgα,gβ,gγ,R=1,is a negligible function of λ, where the probability is over (G,GT,p,g,e)←GroupGen(1λ), α,β,γ←Zp∗, R←GT.Definition 2.
LetGroupGen(1λ) be a bilinear group generator. The CDH assumption holds for GroupGen(1λ) if, for all probabilistic polynomial-time algorithm B, its CDH advantage, denoted by(5)AdvBCDHλ=PrBgα,gβ=gαβ,is a negligible function of λ, where the probability is over (G,GT,p,g,e)←GroupGen(1λ), α,β←Zp∗.


## 5.3. The Leftover Hash Lemma

Definition 3 (universal hash function).
A collectionH of function H with form U→V is universal if for any x,x′∈U such that x≠x′ the following holds:(6)PrH←H⁡Hx=Hx′=1V.Theorem 4 (leftover hash lemma for block-source; see [20]).
LetH be a universal collection of functions H:U→V; let X=(X1,X2,…,Xq) be (q,k)-block-source where k≥log⁡V+2log⁡(1/ϵ)+Θ(1). Then there exists the distribution(7)H1,H1X1,H2,H2X2,…,Hq,HqXq,where (H1,H2,…,Hq)←Hq is ϵq-close to the uniform distribution over (H×V)q.


## 5.4. Security Model for Anonymity

AIE is anonymous ifEnc(pp,x) leaks no information about x. To capture the anonymity properties formally, a game between a challenger and an adversary A is defined as follows:(i)
Setup Phase: the challenger runsSetup(1λ) and sends pp to adversary A and keeps mk to itself.(ii)
Prechallenge Phase: in this phase, adversaryA is allowed to make token extraction query. The challenger responds to the query about index y by sending A to the output of Gen(mk,y).(iii)
Challenge Phase:A submits two indices x0, x1, which is restricted to the indices that he did not request in prechallenge phase. The challenger flips a fair binary coin b and returns Enc(pp,xb) as challenge header.(iv)
Postchallenge Phase: this phase is repeat of prechallenge phase. The adversary issues additional adaptive queries with the restriction where it can not request token ofx0 or x1.(v)
Guess Phase: finally,A submits a guess b′ of b. The adversary wins if b′=b.Definition 5 (anonymity of AIE).
AIE is anonymous if, for any probabilistic polynomial-time algorithmA, its ANON advantage, denoted by(8)AdvAANONλ=Prb′=b-12,is a negligible function of λ, where the probability is over the random bits used by the challenger and the adversary.


## 5.5. Security Model for Function Privacy

Formalizing such a notion is not straightforward since adversary can mount a guessing attack. If adversary has some knowledge that the token comes from a small set, it can encapsulate each candidate index and run the legitimateTest procedure to learn the function embedded inside the token. We adapt the notion from [20] which requires that Gen(mk,y) is indistinguishable from a random token if y is chosen from a sufficiently high min-entropy distribution. The following security game parameterized by a distribution D helps us capture properties of function privacy:(i)
Setup Phase: the challenger runsSetup(1λ) and sends both master secret key mk and public parameters pp to adversary A.(ii)
Challenge Phase: in this phase, the challenger samples an indices vector(x1,x2,…,xq) from the distribution D and then, for every i∈1,2,…,n, computes tki=Gen(mk,xi) and returns (tk1,…,tkq) to A.(iii)
Guess Phase: finally,A submits a guess of the distribution challenger has used. It outputs “0” standing for uniform distribution; otherwise it outputs “1.”Definition 6 (privacy of AIE).
AIE says private function if, for any probabilistic polynomial-time algorithmA and any (q,k)-block-source distribution D where q,k is a polynomial of λ, its PRIV advantage, denoted by(9)AdvAPRIVλ=PrΨDλ=1-PrΨRλ=1,is a negligible function of λ where R stands for uniform distribution.To gain reasonable high min-entropy in anonymous CCN, we suggest that data provider should assign a complicated name of the encrypted data. Since adversary can mount a guessing attack (exhaustively testing the token by using pairings), the definition of privacy actually guarantees that there is no more obviously effective attack better than the brute force method.


## 6. Proof of Anonymity

We use reduction to prove anonymity of our scheme under the DBDH assumption.Lemma 7.
Suppose there is an adversaryA that can win the anonymity game with advantage ϵ(λ). Then there is an algorithm B which solves the DBDH problem with advantage ϵ(λ).Given a tuple(gα,gβ,gγ,Z), which is either sampled from PBDH or from RBDH, algorithm B interacts with adversary A as follows.Setup Phase. B sets up public parameter pp=gα.Programming the Random Oracle. B simulates the random oracle for A as follows.If the same query is repeated twice, then the same return value is provided, on issuing a fresh query forH(x), and B
(1)
samplest1←Zp∗, t2←Zp∗,(2)
stores tuple(x,t1,t2) in table LH,(3)
returnsH(x)=(gβ)t1gt2,On issuing a fresh query forF(x), B
(1)
samplest3←Zp∗, t4←Zp∗,(2)
stores tuple(x,t3,t4) in table LF,(3)
returnsF(x)=(gβ)t3gt4.Prechallenge Phase. On A issuing a token for index y, algorithm B does the following:(1)
If the same query fory is repeated twice, then the same token is provided.(2)
IfA has not made a query for H(y) and/or F(y), it programs H(y) and/or F(y) as mentioned above.(3)
It retrieves(y,t1,t2) from LH and (y,t3,t4) from LF.(4)
It samplesu←Zp∗ and computes v←-u·t1/t3. That is, it randomly samples u and v such that u·t1+v·t2=0.(5)
It computesd←(gα)ut2+vt4.(6)
It returns(d,u,v).Correctness of Simulation. We argue that (d,u,v) is always a proper token corresponding to y since (10)HyuFyvα=gβt1gt2ugβt3gt4vα=gβut1+vt3gut2+vt4α=gαut2+vt4=d.Challenge Phase. After A sends x0 and x1, algorithm B does the following:(1)
It picks a random bitb←0,1.(2)
IfA has not made a query for H(xb) and/or F(xb), it programs H(xb) and/or F(xb) as mentioned above.(3)
It retrieves(xb,s1,s2) from LH and (xb,s3,s4) from LF.(4)
It computesc←gγ, T←Zs1e(gα,gγ)s2, W←Zs3e(gα,gγ)s4.(5)
It returns(c,T,W) as challenge header.Postchallenge Phase. B responds as before in prechallenge phase.Guess Phase. Finally A outputs a guess b′ of b. B concludes its own game by outputting a guess as follows. if b′=b, B returns 1, else returns 0.Analysis ofℬ’s Behavior. Denote γ=logggγ. If Z is sampled from PBDH, that is, Z=e(gα,gβ)γ, then (c,T,W) is a perfectly legitimate header of xb since (11)egα,Hxγ=egα,gβs1gs2γ=egα,gβγs1egα,gs2γ=Zs1egα,gγs2=T,egα,Fxγ=egα,gβs3gs4γ=egα,gβγs3egα,gs4γ=Zs3egα,gγs4=W.Therefore, B simulates a perfect environment of A, and the probability of the event A winning the game is identical to ϵ. However, when Z is uniformly random, the challenge header will not be legitimate. This is not a problem, and indeed it is crucial to the proof of security.Lemma 8.
IfZ is sampled from uniform random, the distribution of b is independent of the adversary’s view, so the probability of event A winning the game is identical to 1/2.Proof.
Consider the joint distribution of the adversary’s view. Note that the adversary is not allowed to make a token query forx0 and x1; from his view, only H(xb), F(xb), T, and W may leak information about b. What we need to prove is that, for any fixed gα, gβ, gγ, T, W, H(x0), F(x0), H(x1), and F(x1),(12)PrZr1egα,gγr2=TZr3egα,gγr4=Wgβr1gr2=Hx0gβr3gr4=Fx0=PrZr1egα,gγr2=TZr3egα,gγr4=Wgβr1gr2=Hx1gβr3gr4=Fx1,where the probability is over r1, r2, r3, r4, and Z. That is clear because the four equations are linearly independent since, for any fixed T, W, f, and h,(13)PrZr1egα,gγr2=TZr3egα,gγr4=Wgβr1gr2=hgβr3gr4=f=1G2.That concludes that A learns nothing about b.To summarize, when the input tuple is sampled fromPBDH, then adversary’s view is identical to its view in a real security game and therefore A satisfies Pr[b′=b]-1/2≥ϵ. When the input tuple is sampled from RBDH, then Pr[b′=b]=1/2. Therefore, we have that(14)AdvBDBDHλ=PrBPBDH=1-PrBRBDH=1≥12±ϵ-12=ϵ.We present our conclusion as the following statement.Theorem 9.
The AIE scheme one proposed is anonymous, assuming the DBDH assumption holds for the bilinear group generated byGroupGen.


## 7. Proof of Function Privacy

Proof.
DenoteViewD by the distribution of A’s view in the game ΨD(λ) and ViewR by the distribution of A’s view in the game ΨR(λ). We prove that ViewD is statistically close to ViewR even for arbitrary fixed public parameters.
SupposeA received tokens corresponding to (x1,x2,…,xq) in the challenge phase. As A knows the master key and having fixed pp, we can assume that ViewD is equivalent to(15)u1,v1,h1u1f1v1,u2,v2,h2u2f2v2,…,uq,vq,hquqfqvq,where hi=H(xi) and fi=F(xi) for each i∈1,…,q.
Without loss of generality, we can assume thatH and F are injective since they are modeled as random oracle. Assuming that H and F are injective guarantees that for any (q,k)-block-source X over 0,1λq the fact that ((h1,f1),…,(hq,fq)) is also a (q,k)-block-source over G2q holds.
Note that the collection of functionsgu,v:G2→Gu,v∈Zp∗ defined by gu,v(h,f)=hufv are universal (see [26]). This enables us to directly apply the leftover hash lemma on block-source, implying that the statistical distance between ViewD and the uniform distribution is negligible in λ. The same holds also for ViewR since R is a (q,k)-block-source in particular. This completes the proof of function privacy.We present our conclusion as the following statement.Theorem 10.
The AIE scheme one proposed is (computational) function privacy under random oracle model.


## 8. Implementation and Performance

We implement our AIE schema by JPBC Library [27]. JPBC Library provides cryptographic interface to perform the mathematical operations underlying pairing-based cryptosystems. Our experiments were deployed on Intel Xeon E3-1231, a 4-core 3.40 GHz CPU, with 8 GB of RAM. We calculate the average time cost of each algorithm run on security parameters with different length. The result is shown in Table 1.Table 1
Average time cost (ms) of each algorithm.
Length
Setup
Enc
Gen
Test
120
5.41
36.46
39.09
4.61
160
10.08
68.88
74.16
8.08
200
17.47
117.12
127.34
13.84
240
29.04
187.74
207.54
21.08As we introduced in Section3, Setup is run by the central authority only once, when deploying the environment. When the producer generates new content, Enc is run by producer once. When a consumer plans to request a content, Gen is run by the central authority and Test is run by each router. Thus, the extra time a consumer would spend for AIE is no more than Time(Gen)+n·Time(Test), where n represents the hop count. Taking 120-bit security parameter as an example, assuming the hop count is 5 on average [2], the total extra time cost for a consumer is 39.09+4.61×5=62.14 ms on average. AIE schema brings only less than 5 ms latency on each hop.The relationship between time cost and the length of security parameter is shown in Figure2. The comparison of four groups of data with different length of security parameter is shown in the graph horizontally. Each bar represents an algorithm in AIE, which is Setup, Enc, Gen, and Test from left to right. The vertical axis represents the average time cost of each experiment. It concludes that the performance of AIE is satisfying with small size of security parameter. But the time cost increases by a large margin with the increase of security parameter size. However, it is not necessary to choose too large security parameter since no one can break DBDH and CDH assumption up to the present.Figure 2
Comparison of time cost on 120-, 160-, 200- and 240-bit security parameter over AIE.Finally we turn to study the stability of our protocols run time. Figures3 and 4 show time cost of each independent call of Gen and Test with 240-bit security parameter. x-axis represents the index of each call and y-axis represents the time cost. Each point in the graph represents a result of one experiment. As expected, the result shows most calls of Gen and Test are very close to the average time cost.Figure 3
Time cost of 100 experiments forGen on 240-bit security parameter.Figure 4
Time cost of 100 experiments forTest on 240-bit security parameter.The experimental results are quite different from other approaches [2, 3]. The main time costs of [2, 3] are used in the transmission of data. But since our scheme decouples index from data, the run time costs are used in encapsulating the index, and the performance of our scheme can be seen as a negligible constant, which is uncorrelated with the data size.


## 9. Conclusion

This work presents an initial attempt to provide privacy and anonymity in CCN by cryptographic protocol. We embed AIE scheme in the CCN to provide comparable anonymity with lower relative overhead.AIE is a new cryptographic primitive. There are at least two differences between Asymmetric Index Encapsulation and PEKS or identity based searchable encryption [13, 20]. Firstly, the goal of AIE scheme is to decouple index hiding and searching procedure from encryption scheme. There are independent application scenarios of index encapsulation. Identity based searchable encryption can be replaced by any combination of AIE and anonymous identity based encryption. Secondly, Asymmetric Index Encapsulation scheme does not imply public key encryption or identity based encryption. There is possibility of getting better security reduction and efficiency.The security of our scheme relies on the DBDH/CDH assumption in prime-order groups and random oracle. An encapsulated header in our system consists of only three elements, while a token in our system also consists of only three elements. Besides the acceptable efficiency in practice, the scheme has tight security reduction against all kinds of adversaries. (A security reduction is said to be tight when breaking the scheme is exactly as hard as solving the underlying problem.)We introduce new adversarial models for anonymous CCN. The anonymity model captures the intuitive notion that an adversary should not be able to distinguish between the encapsulated header of two challenge indices of his choice, even if it is allowed to obtain tokens for any other indices. The privacy model requires any token belonging to indexx to be indistinguishable from a random token if x is chosen from a sufficiently high min-entropy distribution.An interesting open problem is to construct AIE schemes for other classes of functions. A possible starting point is to consider simple functionalities, such as wildcard [28] and inner-product testing [29]. Another fascinating open problem is to design a scheme which is secure in the standard model as well as keeping the token size and header size constant. Finally, we leave it as an open problem to design an AIE scheme without pairing.



---

*Source: 9248654-2017-09-11.xml*