According to   : 9  even with full confidence in cloud-supplied layers, cloud security engineering requires careful teamwork between the outsourcing vendor and the customer. The security featured of vendor -supplied layers and customer-supplied layers must mesh without a flaw when they are used to implement a solution together. Moreover, as it stays in   : 7  public clouds are threatened by hackers due to the much larger target they present. Owners of sensitive data must take into account also other participants in cloud ecosystem - cloud neighbors and administrators. Insiders such as data center administrative staff can easily access private data that has been outsourced. Such attacks are realistic and have already been reported. In several publish attacks one stage of the attack is becoming the cloud neighbor of the target (see   : 11 ) Thus users should take precautions to ensure the confidentiality and privacy of their sensitive cloud data.

Such a solution has however one serious drawback - outsourcing the management of huge datasets and downloading the entire dataset each time before use is simply impractical. In case of databases we often have queries which return relatively small (to the size of the whole database) results. Here instead of returning a small answer, first the entire database would need to be download.

Such a solution allows computation over the data and is especially useful against physical attacks (like stolen disk drive). Unfortunately it does not protect data in use and requires a decryption key to be stored in the cloud. As it stays in   : 9  many attacks are aimed exactly at obtaining the decryption key. Furthermore the moment the query hits a cloud application, data is decrypted and brought into the cloud memory as plaintext. Thus the attackers do not actually need to obtain the key to defeat data at rest encryption (they simply need to exfiltrate plaintext from cloud memory).

According to   : 9  homomorphic cryptosystems promise the best of two worlds:

1. The ability to expose neither plaintext data nor decryption keys in clouds.
2. The ability for applications to nonetheless compute over encrypted data while it resides in the remote cloud.

Cryptosystems

Cryptosystems are valued primarily for their ability to secure information. As a side-effect, however, operations on their corresponding ciphertexts in some cryptosystems correspond to useful operations on plaintexts, which is called a homomorphism. For example:

• Pailier cryptosystem (see Pailier in Additional materials) is additively homomorphic, because: \[E(m_1) \cdot E(m_2) = E(m_1 + m_2)\]
• RSA cryptosystem is multiplicatively homomorphic, because: \[E(m_1) \cdot E(m_2) = m_1^d\cdot m_2^d = (m_1\cdot m_2)^d = E(m_1 \cdot m_2) \]
• ElGamal cryptosystem is multiplicatively homomorphic, because: \[E(m_1) \cdot E(m_2) = \\ (m_1 \cdot y^{r_1}, g^{r_1}) \cdot (m_2 \cdot y^{r_2}, g^{r_2}) = (m_1 \cdot m_2 \cdot y^{r_1+r_2}, g^{r_1+r_2}) = E(m_1 \cdot m_2) \]

The question naturally arises as to whether any cryptosystem is fully homomorphic?

The fully homomorphic encryption problem (FHE) was an open problem for over 30 years. In 2009 Craig Gentry   : 5  proposed a fully homomorphic and semantically secure cryptosystem. Its performance degrades sharply with its security parameter (performance is estimated to be as bad as 10 orders of magnitude worse than the corresponding plaintext operations; such that one second computation would take over three centuries!). Although the research on FHE is now very active we should have in mind that an efficient FHE implementation would not immediately enable users to execute conventional queries in cloud based Databases.

Even if we assume that encryption of data at rest gives data confidentiality, it is worth to stress that it is not sufficient in the field of privacy. Namely, the subsequent data access patterns can leak information about the user. Thats why retrieval of sensitive data from databases or web services, such as medical databases or patent databases implies concerns on user privacy exposure. For example, if the outsourced data in question contains encrypted patient records, the cloud provider might learn that a patient has been diagnosed with cancer when it sees that the patient's records have been retrieved by an oncologist. In general, it is hard to assess which information may be leaked, what inferences an adversary may make, and what risks the leakage may incur. Solutions to the information leakage problem that hide access patterns and are independent of an encryption mechanism offer private information retrieval (PIR) schemes.

Many PIR schemes have been developed so far. Interested readers are referred to a survey   : 4  for a thorough review. Generally, depending on whether the scheme utilizes some trusted hardware or not, the PIR schemes can be divided into two categories:

• traditional PIR schemes and
• hardware-based PIR schemes.

Another classification divides PIR protocols into:

• those that provide privacy guarantees based on the computational limitations of servers (CPIR),
• those that rely on multiple servers not colluding for privacy (IT-PIR).

Challenges for PIR schemes are to achieve scalability and minimize the communication and computation complexity.

Authors of   : 7  have implemented (the source code is available for download from   http://pasmac.ccs.neu.edu   PIRMAP that is usable in real-world MapReduce clouds today, e.g., Amazon. They evaluated PIRMAP, first, in their own (tiny) local cloud and, second, with Amazon's cloud. They also verified its practicality by scaling up to 1 TByte of data in Amazon's cloud setting. PIRMAP can be used with any additively homomorphic encryption scheme.

PIRMAP details

As it stays in   : 7  PIRMAP assumes that the cloud user has already uploaded its files into the cloud using the interface provided by the cloud provider. Thus during the query procedure we get the following assumptions: data set holds \(n\) files, each of \(l\) bits length (to accommodate variable length files the padding should be used). Additional parameter \(k\) specifies the block size of a cipher utilized. PIRMAP is summarized as follows:

1. User side: if the user wishes to retrieve file \(1 \leq x \leq n\), he executes Query:
   • creates a vector \(v = (v_1, \ldots, v_n)\), where:
     • \(v_x = E(1)\)
     • \(\forall_{i \neq x}{v_i = E(0)}\) and
     • \(E\) denotes additively homomorphic encryption scheme,
   • sends \(v\) to the MapReduce cloud.
2. Cloud side:
   • Each mapper nodes evaluates Multiply on its locally stored file \(i\):
     • the file \(i\) is divided into \(\frac{k}{l}\) blocks \(\{B_{i,1} ,\ldots , B_{i,\frac{l}{k}}\}\),
     • each block is multiplied by \(v_i\),
     • the following key-values pairs are generated for the reducer \( (1, v_i \cdot B_{i,1}), \ldots, (1, v_i \cdot B_{i,\frac{l}{k}}) \).
   • Reducer evaluates Sum: all values with the same key are added.
   • One result vector of values \(r = (r_1, \ldots, r_{\frac{l}{k}})\) is sent to the user.

Summarizing, in PIRMAP protocol the cloud arranges \(n\) files into a following table \(T\): \[ \begin{array}{c | c c c c} & 1 & 2 & \ldots & \frac{l}{k}\\ \hline \\ file_1 & B_{1,1} & B_{1,2} & \ldots & B_{1, \frac{l}{k}}\\ file_2 & B_{2,1} & B_{2,2} & \ldots & B_{2, \frac{l}{k}}\\ \ldots & & & \ldots & \\ file_n & B_{n,1} & B_{n,2} & \ldots & B_{n, \frac{l}{k}} \end{array} \] Then the cloud performs the vector-matrix multiplication: \(r = v \cdot T\). The user receives \(\frac{l}{k}\) values of size \(k\) and decrypts it to get \(file_x\).

PIRMAP privacy

There are two pieces of information that the adversary has access to:

• the set of uploaded files and
• the vector \(v\) of PIR values.

The uploaded files are independent of any encryption used in the PIR protocol and can be efficiently simulated by the adversary. Therefore, privacy depends only on \(v\). Vector \(v\) contains many encryptions of "\(0\)" and one encryption of "\(1\)". The problem of determining which file was selected is then equivalent to distinguishing between encryptions of "\(0\)" and encryptions of "\(1\)" in the underlying encryption. However, the scheme that is used is provably secure against distinguishing under the Trapdoor Group Assumption. Consequently, PIRMAP preserves user privacy.

PIRMAP advantages and disadvantages

As it is summarized in   : 3  Goldberg scheme:

1. Makes use of Shamir's Secret Sharing to ensure the privacy of fetched information. Suppose we have a secret \(\sigma\) in some field \(F\), then we create a random function \(f\) of degree at most $\(t\) that encodes the secret so that \(f (0) = \sigma\). We then create a set of shares \(\{(\alpha_1, f(\alpha_ 1)), (\alpha_2, f(\alpha_ 2)), \dots, (\alpha_l, f(\alpha_ l))\}\) with \(\alpha_1,\dots , \alpha_l \in F\) and \(\alpha_i \neq 0\) and distribute them to a set of servers. As long as no more than \(t\) of the servers are colluding, none of them will be able to determine the secret.
2. Assumes that the database is an \(r \times s\) matrix \(D\) and that each of servers have a copy of \(D\). Each row of the database represents a record. If we want the record at row \(\beta, D_\beta\), we create the elementary vector \(e_\beta = \langle 0, 0, \dots, 1, \dots, 0\rangle \in F^r\), where the \(1\) is in the \(\beta^{\mbox{th}}\) position, and multiply by \(D\): \(D_\beta = e_\beta \cdot D\).
3. In order to hide \(\beta\) from the database operators we use Shamir's Secret Sharing to create \(l\) shares of \(e_\beta\): \(v_1, v_2, \dots, v_l \in F^r\), and send query vector \(v_i\) to server \(i\). Each server computes a response vector \(r_i = v_i \cdot D\) and returns it to the client.
4. As long as enough servers send their response, the client can recover the database record since \(r_1, r_2, \dots, r_l\) are Shamir's Secret Shares for \(D_\beta\).
5. As long as no more than \(t\) servers collude, none of the servers can determine any information about the record that was fetched.

Goldberg's scheme is implemented in the open source project Percy++ (available at   http://percy.sourceforge.net  ).

As it stays in   : 3  the vector-by-matrix multiplication computation for one of the PIR servers can be split up over a number of workers (a cluster of workers represents one PIR server). First the database \(D\) needs to be split into parts. It can be done in three ways (see below)

We have one master server that coordinates the workers. When all workers are done the vector-by-matrix multiplication on their portion of the database, the master respectively adds or concatenates all of the worker's responses together and sends the result to the requesting client.