Cryptonite: A Framework for Flexible Time-Series Secure Aggregation with Non-interactive Fault Recovery

Private stream aggregation (PSA) allows an untrusted data aggregator to compute statistics over a set of multiple participants’ data while ensuring the data remains private. Existing works rely on a trusted third party to enable an aggregator to achieve fault tolerance, that requires interactive recovery, but in the real world this may not be practical or secure. We develop a new formal framework for PSA that accounts for user faults, and can support non-interactive recovery, while still supporting strong individual privacy guarantees. We first must define a new level of security in the presence of faults and malicious adversaries because the existing definitions do not account for faults and the security implications of the recovery. After this we develop the first protocol that provably reaches this level of security, i.e., individual inputs are private even after the aggregator’s recovery, and reach new levels of scalability and communication efficiency over existing work seeking to support fault tolerance. The techniques we develop are general, and can be used to augment any PSA scheme to support non-interactive fault recovery.

This work was supported by Facebook as a winner of the Role of Applied Cryptography in a Privacy-Focused Advertising Ecosystem Facebook RFP. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect those of the sponsor.

Authors and Affiliations

1. University of Notre Dame, Notre Dame, IN, 46556, USA

   Ryan Karl, Jonathan Takeshita & Taeho Jung

Corresponding author

Correspondence to Taeho Jung .

Editors and Affiliations

1. Télécom SudParis, Institut Polytechnique de Paris, Palaiseau, France

   Joaquin Garcia-Alfaro

2. University of Kent Canterbury, Canterbury, Kent, UK

   Shujun Li

3. University of Washington, Seattle, WA, USA

   Radha Poovendran

4. Télécom SudParis, Institut Polytechnique de Paris, Palaiseau, France

   Hervé Debar

5. Google Inc., New York, NY, USA

   Moti Yung

A Proof of Fault Tolerable Aggregator Obliviousness

Theorem 1

Assuming that the Decisional Diffie-Hellman problem is hard in the group G and that the hash function H is a random oracle, then the above construction satisfies aggregator oblivious security with fault tolerance, as described in Definition 2.

Proof

First, we prove that the following intermediate game is difficult to win, given that Decisional Diffie-Hellman is hard. Let \(\mathbb {G}\) be a group of prime order p.

Setup: The challenger picks random generators \(g, h \in \) \(\mathbb {G},\) and random \(\alpha _{0}, \alpha _{1}, \ldots , \alpha _{n} \in \mathbb {Z}_{p}\) such that \(\sum _{i=0}^n \alpha _{i}=0 .\) The challenger gives the adversary: \(g, h, g^{\alpha _{0}}, g^{\alpha _{2}}, \ldots , g^{\alpha _{n}}\).

Queries: The adversary can compromise users adaptively and ask for the value of \(\alpha _{i}\). The challenger returns \(\alpha _{i}\) to the adversary when queried.

Challenge: The adversary selects an uncompromised set \(Q \subseteq \{0, \ldots , N\}\), and specifies a subset of Q denoted Y of users they claim faulted, where \(J = Y\) for the duration of the game. The challenger flips a random bit b. If \(b=0,\) the challenger returns to the adversary \(\left\{ h^{\alpha _{q}} \mid q \in Q \backslash Y\right\} , \left\{ h^{\alpha _{y}} \mid y \in Y\right\} \). If \(b=1,\) the challenger picks |Q|/|Y| random elements \(h_{q}^{\prime }\), for \(q \in Q/Y\) and |Y| random elements \(h_{y}^{\prime }\), for \(y \in Y\) from the group \(\mathbb {G},\) such that \(\sum _{q \in Q} h_{q}^{\prime } + \sum _{y \in Y} h_{y}^{\prime } =\sum _{q \in Q} h^{\alpha _{q}} + \sum _{y \in Y} h^{\alpha _{y}}\). The challenger returns \(h_{q}^{\prime }\), for \(q \in Q/Y\) and \(h_{y}^{\prime }\), for \(y \in Y\) to the adversary. The adversary can make additional compromise queries, as described in the above step as they see fit.

Guess: The adversary guesses either \(b=0\) or 1. The adversary wins if they have not asked for any \(\alpha _{q}\) for \(q \in Q,\) \(Y = J\), and if they successfully guess b.

Lemma 1

The above game is difficult for computationally bounded adversaries assuming Decisional Diffie Hellman is hard for group \(\mathbb {G}\).

We define the following sequence of hybrid games, and assume that the set Q specified by the adversary in the challenge stage is \(Q=\left\{ q_{1}, q_{2}, \ldots , q_{m}\right\} \). For simplicity, we write \(\left( \beta _{1}, \ldots , \beta _{m}\right) \) := \(\left( \alpha _{q_{1}}, \ldots , \alpha _{q_{m}}\right) ,\) and include Y within Q to save space. In \(Game_{d},\) the challenger sends the following to the adversary: \(R_{1}, R_{2}, \ldots , R_{d},\) \(h^{\beta _{d+1}},\) ..., \(h^{\beta _{m}}\). Here, each \(R_{q}(q \in [d])\) means an independent fresh random number, and the following condition holds: \(\prod _{1 \le q \le d} R_{q}=\prod _{1 \le q \le d} h^{\beta _{q}}\). Clearly \(Game_{1}\) is equivalent to the case when \(b=0\), and \(Game_{m-1}\) is equivalent to the case when \(b=1\). With the hybrid argument we can show that games \(Game_{d-1}\) and \(Game_{d}\) are computationally indistinguishable. To demonstrate this, we show that if, for some d,  there exists a polynomial-time adversary \(\mathcal {A}\) who can distinguish between \(Game_{d-1}\) and \(Game_{d},\) we can then construct an algorithm \(\mathcal {B}\) which can solve the DDH problem.

Suppose \(\mathcal {B}\) obtains a DDH tuple \(\left( g, g^{x}, g^{l}, T\right) \). \(\mathcal {B}\)’s task is to decide whether \(T=g^{x l}\) or whether T is a random element from \(\mathbb {G}\). Now \(\mathcal {B}\) randomly guesses two indices e and b to be the \(d^{\mathrm {th}}\) and the \((d+1)^{\mathrm {th}}\) values of the set Q specified by the adversary in the challenge phase. The guess is correct with probability \(\frac{1}{N^{2}},\) and in case the guess is wrong, the algorithm \(\mathcal {B}\) aborts. Now \(\mathcal {B}\) picks random exponents \(\left\{ \alpha _{q}\right\} _{q \ne e, q \ne b}\) and sets \(\alpha _{b}=x\) and \(\alpha _{e}=-\sum _{q \ne e} \alpha _{q}\). Notice that \(\mathcal {B}\) does not know the values of \(\alpha _{e}\) and \(\alpha _{b},\) however, it can compute the values of \(g^{\alpha _{b}}=g^{x}\) and \(g^{\alpha _{e}}=\left( \prod _{q \ne e} g^{\alpha _{q}}\right) ^{-1}=\left( g^{x}\right) ^{-1}\). \(\prod _{q \ne e, q \ne b} g^{\alpha _{q}} \cdot \mathcal {B}\) gives \(\mathcal {A}\) the tuple \(\left( g, h=g^{l}, g^{\alpha _{1}}, \ldots , g^{\alpha _{n}}\right) \). If \(\mathcal {A}\) asks for any exponent except \(\alpha _{e}\) and \(\alpha _{b}, \mathcal {B}\) returns the corresponding \(\alpha _{q}\) value to \(\mathcal {A}\); if \(\mathcal {A}\) asks for \(\alpha _{e}\) or \(\alpha _{b},\) the algorithm \(\mathcal {B}\) aborts.

In the challenge phase, \(\mathcal {A}\) submits a set \(Q=\) \( \{q_{1}, q_{2}, \ldots q_{m} \} .\) If e and b are not the \(d^{\mathrm {th}}\) and the \((d+1)^{\mathrm {th}}\) values of the set Q,  i.e., if \(q_{d} \ne e\) or \(q_{d+1} \ne b,\) the algorithm \(\mathcal {B}\) aborts. If \(q_{d}=e\) and \(q_{d+1}=b,\) then \(\mathcal {B}\) returns to \(\mathcal {A}\): \( R_{1}, R_{2}, \ldots , R_{d-1}\), \( (\prod _{q \notin \{q_{1}, \ldots , q_{d+1} \}} (g^{l} )^{\alpha _{q}} \cdot \prod _{q=1}^{d-1} R_{q} \cdot T )^{-1}\), T, and \( (g^{l} )^{\alpha _{{q}_{d+2}}, \ldots , (g^{l} )^{\alpha _{q_{m}}}}\). Clearly if \(T=g^{x l}\), then the above game is equivalent to \(Game_{d-1}\). Otherwise, if \(T \in _{R} \mathbb {G}\), then the above game is equivalent to \(Game_{d}\). Thus, if \(\mathcal {A}\) has a non-negligible advantage in guessing whether it is playing \(Game_{d-1}\) or \(Game_{d}\) and \(\mathcal {B}\) could solve the DDH problem with non-negligible advantage.

Now to prove the theorem, we will modify the aggregator oblivious security game. In the Encrypt queries, if the adversary submits a request for some tuple \((q, x, t^{*} )\) where \(t^{*}\) is the time step specified in the Challenge phase, the challenger treats this as a Compromise query, and simply returns the \(sk_{q}\) to the adversary. Given \(sk_{q},\) the adversary can compute the requested ciphertext. The adversary has access to a the functionality, FaultRecover, that can only be called once (since this is enforced via trusted hardware), which takes in a set of users that have not been compromised (\(j \in J\)), and returns the set of ciphertexts that correspond to those users encrypting 0. Note that this modification actually gives more power to the adversary. From now on, we will assume that the adversary does not make any Encrypt queries for the time \(t^{*}\).

Let \(K \subseteq N\) denote the set of compromised participants. Let \(\bar{K}:=N \backslash K\) denote the set of uncompromised participants. Since we assume the aggregator is untrusted, we are interested in the case where \(Q=\bar{K}\) or the aggregator key has been compromised. We must show that the adversary cannot distinguish whether the challenger returns a true encryption of the plaintext submitted in the challenge stage, or a random tuple with the same aggregation.

Given an adversary \(\mathcal {A}\) who can break the PSA game with non-negligible probability, we construct an algorithm \(\mathcal {B}\) that can solve the above intermediate problem with non-negligible probability. \(\mathcal {B}\) obtains from the challenger \(\mathcal {C}\) the tuple \(g, h, g^{\alpha _{0}}, g^{\alpha _{1}}, \ldots , g^{\alpha _{n}}\). \(\mathcal {B}\) sets \(\alpha _{0}\) to be the aggregator’s key, and \(\alpha _{1}, \ldots , \alpha _{n}\) to be the secret keys of participants 1 through n respectively. Note param is g.

Let \(q_{H}\) denote the total number of oracle queries made by the adversary \(\mathcal {A}\) and by the algorithm \(\mathcal {B}\) itself. \(\mathcal {B}\) guesses at random an index \(b \in \left[ q_{H}\right] \). Suppose the input to the \(b^{\text {th}}\) random oracle query is \(t^{*}\). The algorithm \(\mathcal {B}\) assumes that \(t^{*}\) will be the challenge time step. If the guess is found to be wrong later, \(\mathcal {B}\) aborts.

Hash Function Simulation: The adversary submits a hash query for the integer t. \(\mathcal {B}\) first checks the list \(\mathcal {L}\) to see if t has appeared in any entry (t, z) . If so, \(\mathcal {B}\) returns \(g^{z}\) to the adversary. Otherwise, if this is not the \(b^{\text {th}}\) query, \(\mathcal {B}\) picks a random exponent z and returns \(g^{z}\) to the adversary, and saves (t, z) to a list \(\mathcal {L}.\) For the \(b^{\text {th}}\) query, \(\mathcal {B}\) returns h.

Then the following Queries can take place:

• \(\mathbf{Encrypt} \): The adversary \(\mathcal {A}\) submits an Encrypt query for the tuple (q, x, t) . In the modified version of the game, we ensure that \(t \ne t^{*},\) as otherwise, we simply treat it as a Compromise query. \(\mathcal {B}\) checks if a hash query has been made on t, and if not, \(\mathcal {B}\) makes a hash oracle query on t. Thus, \(\mathcal {B}\) learns the discrete log of H(t). Now \(H(t)=g^{z},\) so \(\mathcal {B}\) knows z, and since \(\mathcal {B}\) also knows \(g^{\alpha _{q}}, \mathcal {B}\) can compute the ciphertext \(g^{x} \cdot \left( g^{z}\right) ^{\alpha _{q}} \text{ as } g^{x} \cdot \left( g^{\alpha _{q}}\right) ^{z}\).

• \(\mathbf{Compromise} \): \(\mathcal {B}\) forwards \(\mathcal {A}\)’s query to its own challenger \(\mathcal {C},\) and forwards the answer \(\alpha _{q}\) to \(\mathcal {A}\).

• \(\mathbf{FaultRecover} \): \(\mathcal {B}\) forwards \(\mathcal {A}\)’s query to its own challenger \(\mathcal {C},\) and forwards the set of ciphertexts (i.e. \(\forall j \in J\), \(c \longleftarrow g^{0} \cdot H(t)^{s k_{j}}\))) to \(\mathcal {A}\).

Challenge: The adversary \(\mathcal {A}\) submits a set \(N = J \cup Q\) and a time \(t^{*},\) as well as plaintexts \(\left\{ x_{q} \mid q \in N\right\} \). If \(t^{*}\) does not agree with the value submitted in the \(b^{\text {th}}\) hash query, then \(\mathcal {B}\) aborts. \(\mathcal {B}\) submits the set Q in a Challenge query to its own challenger, and it obtains a tuple \(\left\{ T_{q}\right\} _{q \in N}\). The challenger returns the following ciphertexts to the adversary: \( \forall q \in Q: g^{x_{q}} \cdot T_{q}\) (i.e. \(c \longleftarrow g^{x_q} \cdot H(t)^{sk_{q}} \cdot T_q\)).

More Queries: Same as the Query stage.

Guess: If the adversary \(\mathcal {A}\) guesses that \(\mathcal {B}\) has returned a random tuple then \(\mathcal {B}\) guesses \(b^{\prime }=1\). Otherwise, \(\mathcal {B}\) guesses that \(b^{\prime }=0\)

If the challenger \(\mathcal {C}\) returns \(\mathcal {B}\) a faithful Diffie-Hellman tuple \(\forall q \in Q: T_{q}=h^{\alpha _{q}},\) then the ciphertext returned to the adversary \(\mathcal {A}\) is a true encryption of the plaintext submitted by the adversary. Otherwise, if the challenger returns to \(\mathcal {B}\) a random tuple, then the ciphertext returned to \(\mathcal {A}\) is random under the product constraint.

Reprints and permissions

© 2021 ICST Institute for Computer Sciences, Social Informatics and Telecommunications Engineering

Policies and ethics