# Lightweight, Secure, Similar-Document Retrieval over Encrypted Data
## 4 Scheme Overview
### Initialization Stage
#### 5.1.1 Secure Inverted Index. Our proposed secure DSD is based on the inverted index structure to privately retrieve the documents with the top-\(h\) scores. The secure inverted index is constructed using the following two steps. 1. Fingerprint generation: Given the document collection \(D=\{d_{1},d_{2},\ldots,d_{m}\}\). The data owner _[PERSON]_ generates the fingerprint for each document \(d_{i}\), as explained in the \"Document fingerprinting\" section. Recall that the fingerprint is a set of integer numbers (terms). We define \(F=\{f_{1},f_{2},\ldots,f_{l}\}\) to be the union set of all the fingerprint terms of the document collection. The inverted index \(I\) includes a set of fingerprint items \(f_{j}\) and their corresponding posting lists \(P_{j}\) i.e., \(I=\{(f_{j},P_{j}),j=1,\ldots,l\}\). The posting list refers to the set of document IDs that contains the term \(f_{j}\). The posting list \(P_{j}\) is simply a bit vector of size \(m\), where \(m\) is the total number of _[PERSON]_'s collection \(D\). Given that \(ID(d_{i})\) is the identifier of the document \(d_{i}\), the element vector \(P_{j}[ID(d_{i})]=1\) if, and only if \(d_{i}\) includes the fingerprint term \(f_{j}\). Table 1 shows a simple index of five fingerprint terms that were derived from 14 documents. For example, the term 500 appears in five documents \((d_{1},d_{2},d_{4},d_{6},\) and \(d_{14})\). 2. Inverted index encryption: In this stage, the inverted index is transformed into a secure index by encrypting the terms of fingerprints and their relevant posting vectors. Fingerprint terms (numbers) should be encrypted such that only the authorized users can generate valid queries. Otherwise, the third-party server could learn the fingerprint terms of a given document. Similarly, the posting vectors should be encrypted to hide the number of documents in a given fingerprint item, of which information may be used to conduct a frequency attack. Our solution to protect the fingerprint terms is to consider the parameters \(b\) and \(M\) of Equations (1) and (3) as a secret key \(K_{1}=(b,M)\), such that only the authorized users who have the secret key \(K_{1}\) can generate a valid fingerprint. Encrypting the posting vectors is more difficult. This is because such vectors have to be encrypted, while preserving their ability to rank the retrieved documents. In this paper, we utilize the attractive feature of the Paillier cryptosystem [35] to alleviate this challenge. Paillier is a secure semantic and additive homomorphic asymmetric encryption scheme. The semantically secure feature ensures that repeatedly encrypting the same number (0 and 1 in our case) will generate different ciphers. Let \(Enc_{kpub}\) and \(Dec_{kpriv}\) be Paillier encryption and decryption functions with the public and private keys _kpub_ and _kpriv_, respectively. Thus, if \(m_{1}=m_{2}\) are equal messages, then \(Enc_{kpub}(m_{1})\
eq Enc_{kpub}(m_{2})\). However, \(Dec_{kpriv}(m_{1})=Dec_{kpriv}(m_{2})\). The additive homomorphic property means that \(Enc_{kpub}(m_{1}+m_{2})=Enc_{kpub}(m_{1})\times Enc_{kpub}(m_{2})\). Given a constant \(c\) and a ciphertext \(Enc_{kpub}(m)\), the multiplicative property can be defined as: \(Enc_{kpub}(m)^{c}=Enc_{kpub}(c\times m)\). We use the Paillier cryptosystem to encrypt each bit of the posting vectors, such that if \(P_{j}[ID(d_{i})]=1\), then we store \(Enc_{kpub}(1)\). Otherwise, we store \(Enc_{kpub}(0)\). Algorithm 1 shows the generation for the secure searchable inverted index built by the proposed method. It must be acknowledged that, since Paillier is a secured encryption method with regard to semantics, every encrypted zero and one value is distinct. As soon as the encryption process is complete, falsified data must be inserted as noise into the inventory in order to obscure the quantity of fingerprint items within the collection. REMARK: For more clarity that the inverted index is secure, it consists mainly of a set of fingerprint terms and the corresponding posting lists.