Ad Hoc Multi-Input Functional Encryption (aMIFE)

Readings:

  1. Functional Encryption: Definitions and Challenges
  2. Multi-Input Functional Encryption
  3. Ad Hoc Multi-Input Functional Encryption

Overview:

In this paper, authors proved two main results:

  1. aMIFE for general functionality can be constructed by standard MIFE + general FE + function re-runnable two-round MPC.
  2. As a special case, aMIFE for the inner product functionality can be constructed from standard assumption: Learning From Error (LWE)

To figure out how it is achieved, we need to start from the building blocks:

Functional Encryption (FE):

Consider a cloud image storage service. Law enforcement may require the cloud to search for images containing a particular face. For protecting users’ privacy (if there is still any), the cloud needs a restricted secret key that only decrypts a target image, and only decrypts the target face in clear, while still keeps all other parts of the images blurred. In this scenario, the secret key only reveals a function of the plaintext image. We know traditional public key cryptography is an “all or nothing” scheme, which means either we can decrypt and read the entire plaintext, or we are not able to decrypt it and thus learn nothing about the plaintext. So here function encryption (FE) comes to rescue. Just as in traditional encryption, in FE, ciphertexts can be generated with an encryption key. However, each decryption key is associated with a function f, and decryption of an encryption of m using this key results in not m but f(m). Informally, the security definition of FE requires nothing more than f(m) can be learned from the encryption of m and the decryption key for f.

Multi-Input Functional Encryption (MIFE):

Note that FE only works for computing a function f on a single ciphertext. Moving one step further, what if we want to compute a function defined over multiple plaintexts given their ciphertexts each encrypted under a different key? Now we need to introduce MIFE. In MIFE, decryption keys allow computing joint functions of different plaintexts underlying multiple ciphertexts. That is, decryption takes a key for a function f and ciphertexts c_1, ... , c_n encrypting m_1, ... , m_n, and outputs f(m_1, ... , m_n). The interactive pattern of MIFE can be summarized into the following steps:

  1. Suppose there are l users involved. This number l is counted and sent to a trusted global setup. The global setup outputs a master secret key MSK, and a set of l encryption keys \{EK_1, EK_2, ..., EK_l\}, one for each user.
  2. The global setup picks a function f, and generates a decryption key DK_f using MSK and f. The subscript indicates this decryption key is associated with f.
  3. The global setup publishes the public parameters to all users, and distributes each encryption key EK_i to user with index i. Note that this step can be done in parallel with step 2.
  4. Each user encrypts their plaintext m_i upon receiving encryption key EK_i to get a ciphertext c_i.
  5. All users send their ciphertexts to the aggregator, who now computes the result y = f(m_1, m_2, ..., m_l) using the decryption key DK_f.

Motivation:

The motivation of aMIFE comes from these two drawbacks of the standard MIFE presented above:

  1. In MIFE, encryption and decryption keys are generated via a global setup procedure run by an external entity, called the “key authority”. This key authority is able to decrypt all the ciphertexts gathered from users. It also picks which function f to be computed. Therefore, it must be trusted to maintain the security of this scheme.
  2. In MIFE, the number of function arity must be declared at setup time. It does not support a dynamic setting in which users can join or leave.

Challenges:

Where is challenging part to improve these two drawbacks?

MPC:

For eliminating the key authority, a natural idea is to use MPC to replace it. However, naively using MPC as setup would introduce interaction between users, which MIFE doesn’t allow. Hence we can try Two-round MPC.

Two-round MPC:

Here is how it works:

  1. Round One: Assume the number of users n and the function to be computed f of arity n is predetermined. Each user feeds their index i and plaintext m into the first round MPC, and get the first round message \rho^{(1)} and a secret s.
  2. Round Two: All users publish their first round message \rho^{(1)}. Using all these first round messages, together with each secret s, each user computes the second round message \rho^{(2)}
  3. Compute Result: All users send their second round messages to an aggregator, and the aggregator computes the final result y.

However, naively using a two-round MPC does not suffice, as it introduces two issues:

  1. This template publishes fresh public parameters PP for each DK_f, but MIFE requires publishing PP only once.
  2. EK_i is not known given just the first round MPC messages, so users are not able to encrypt.

Solution to 1: Function re-runnable two-round MPC:

We require that the first round MPC message to be sent only once, and reused for all subsequent second round messages. This property is called “function re-runnable”. Moreover, we require the number of users to be declared during the second round of MPC, instead of at the time that the first round is sent. This property is called “function delayed”.

Solution to 2: Delaying Encryption:

We allow the users to delay encryption until EK_i are known. During the setup, each user runs a FE scheme to get the FE master key. This master key is used to compute the first round MPC message. Additionally, each user encrypts their input m_i using FE.Encrypt.

aMIFE Interaction Pattern:

We want to let each user run a local setup, which replaces the trusted global setup in standard MIFE. In addition, we want the number of users to be undetermined in the setup procedure, so that it allows users to join or leave in the computation process. For simplicity, we present the aMIFE in the private-key setting:

  1. Each user i runs a local setup to generate some public parameters and a private encryption key EK_i.
  2. Each user publishes their public parameters, and encrypts their input x using the private encryption key only, nothing else.
  3. Using their private encryption keys, users can issue partial decryption keys to the aggregator. Each partial decryption key is generated by the public parameters of l - 1 other users.
  4. If these l - 1 other users also issue the matching partial encryption keys for f to the aggregator, then the aggregator can decrypt the ciphertexts c_1, c_2, ..., c_l using all partial decryption keys PDK_{1,f}, PDK_{2,f}, ..., PDK_{l,f}. The final result is y = f(m_1, m_2, ..., m_l)

But how to replace the global setup using local setup? The idea is to nest FE, MIFE and Two Round MPC together.

aMIFE for General Functionalities:

Now we are ready to present the complete aMIFE scheme for general functionalities:

  1. Local Setup: Each user runs FE scheme to generate a FE master secret key MSK_{FE}. Feed this MSK_{FE} into the first round MPC to get the first round protocol message \rho^{(1)} and a secret s. Set public parameter PP = \rho^{(1)} and master secret key MSK = (MSK_{FE}, s). Note that the global setup in standard MIFE is bypassed using FE and first round MPC.
  2. Key Generation: Suppose l users are chosen to participate in the computation, then these l users publish their public parameters and master secret keys. Each user runs second round MPC to generated a second round message \rho^{(2)}, which is the partial decryption key PDK_i.
  3. Encryption:
  4. Decryption:

“Ad hoc Friendliness”:

We say a MIFE scheme is “ad hoc friendly” if it satisfies the following three conditions:

  1. Decentralized Setup: The encryption keys EK_i and the partial master secret key MSK_i for each user can be generated locally.
  2. Local Encryption: Each user is able to encrypt using their encryption key $EK_i$ and plaintext x, nothing else. The encryption process is fully independent from the number of users n.
  3. Piecewise Master Secret Key: If we restrict the master secret key MSK = \{MSK_1, MSK_2, ..., MSK_n\} to some subset S with |S| = l, the subset has the same distribution as a master secret key generated for functions of arity l.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s