# A PEKS-Based NDN Strategy for Name Privacy
## 2 Background and Related Work
### Public Key Encryption with Keyword Search  
An encryption scheme supporting a search mechanism is called searchable encryption. Symmetric Searchable Encryption (SSE) and Public Key with Keyword Search (PEKS) are the most popular Searchable Encryption (SE) techniques. A Searchable Encryption Scheme (SSE) [19] proposed in 2000, solves the problem of searching encrypted data on the storage servers. The SSE allows the user to upload data to the cloud with provable secrecy by issuing an isolated and hidden query. The hidden and isolated query allows the server to learn nothing about the plaintext except for the ciphertext. The query is running as an encrypted query which is called trapdoor. Trapdoors are always generated using a secret key. It has the following limitations: While the construction is proven to be a secure encryption scheme, it is not proven to be a secure searchable encryption scheme; the distribution of the underlying plaintexts is vulnerable to statistical attacks; searching is linear in the length of the document collection [20]. Furthermore, the scheme suffers from a complicated secret key distribution [21]. On the other hand, the PEKS scheme introduced by [PERSON] et al. in 2004 allows one to search encrypted documents on the untrusted server without revealing any information as shown in Figure 4. This scheme overcomes the secret key distribution issue in the SSE. In order to enhance name privacy in NDN, we adopt the PEKS scheme. The PEKS scheme [22] by [PERSON] et al. incorporates keyword search functionality into public key encryption and it is secure based on the Bilinear Diffie-Hellman assumption in the random oracle model. In the PEKS scheme, three parties, [PERSON], [PERSON], and [PERSON], are involved. [PERSON] wants to share sensitive data with [PERSON]. He uses [PERSON]'s public key \(A_{pub}\) to encrypt a message \(msg\) with keywords \(W_{1}\),..., \(W_{k}\). The following ciphertext (1), which is generated by [PERSON], is sent to the server. \[Ciphertext=[E_{A_{pub}}(msg),PEKS(A_{pub},W_{1}),...,PEKS(A_{pub},W_{k})] \tag{1}\]  
Figure 3: NDN packet forwarding process (reproduced according to “Name Data Networking”) [2]. where \(E_{A_{pub}}(msg)\) is the encrypted message and PEKS(\(A_{pub}\), \(W_{k}\)) is a ciphertext obtained by encrypting \(W_{k}\) under \(A_{pub}\) using PEKS algorithm. When [PERSON] wants to download the ciphertext containing the keyword she specifies, she generates trapdoors \(T_{W}\) by using her secret key and keyword. She then sends it to the server. The server gets no information about the message inside the ciphertext but is able to search a specific keyword by using the trapdoor \(T_{W}\). When matching ciphertexts are found, the server sends those ciphertexts to [PERSON]. She can decrypt the ciphertext using her private key \(A_{priv}\). The details of the PEKS scheme are described as follows. The scheme uses two groups \(G_{1}\), \(G_{2}\) with a prime order p and a bilinear map e: \(G_{1}\times G_{1}\to G_{2}\) between them. The map satisfies the following properties:  
* Computable: Given \(g,h\in G_{1}\) there is a polynomial time algorithm to compute \(e(g,h)\in G_{2}\). * Bilinear: For any integers \(x,y\in[1,p]\) we have \(e(g^{x},g^{y})=e(g,g)^{xy}\). * Non-degenerate: If g is a generator of \(G_{1}\) then \(e(g,g)\) is a generator of \(G_{2}\). Two hash functions are given as \(H_{1}:\{0,1\}^{*}\to G_{1}\) and \(H_{2}\): \(G_{2}\rightarrow\{0,1\}^{logp}\). The PEKS scheme uses the following four polynomial-time algorithms:  
* \(KeyGen(1^{k}):\) The input security parameter determines the size of p and the groups \(G_{1}\), \(G_{2}\). The algorithm picks a random \(\alpha\in Z_{p}^{*}\) and a generator g of \(G_{1}\). It outputs \(A_{pub}=[\text{g},h=g^{\alpha}]\) and \(A_{priv}=\alpha\). * PEKS(\(A_{pub}\), W): First compute t = e(\(H_{1}\)(W), \(h^{r}\)) for \(r\in Z_{p}^{*}\).