Research Vignette: The Unlikely Friendship of Lattices and Elliptic Curves

by Shweta Agrawal (IIT Madras)

One of the most fascinating things about cryptography is its deeply paradoxical nature: among its early successes is the ability for two strangers to meet, generate a shared secret key, and thereon communicate privately — all of these performed entirely within a crowd. Over the last several decades, we have witnessed ever more surprising cryptographic protocols, achieving increasingly paradoxical properties, ranging from zero knowledge to fully homomorphic encryption. This article will focus on one such paradox, a new technical approach that has been unraveling surprising power, opening up avenues for hitherto unrealized cryptography. This is the unlikely friendship of two seemingly disparate mathematical structures and conjectured hard problems on these, namely, the hardness of finding short independent vectors in high-dimensional lattices and hardness assumptions on elliptic curves over finite fields. This topic is connected with what was explored during the Simons Institute's Spring 2020 program on Lattices: Algorithms, Complexity, and Cryptography — the interface of lattices with other mathematical structures and new cryptography that can emerge from it.

In more detail, our first assumption on high-dimensional lattices is the so-called learning with errors (LWE) proposed by Oded Regev in 2005 [21]. LWE conjectures that it is hard to recover a secret \(\mathbf{s}\in \mathbb{Z}_q^n\) from a sequence of noisy linear equations on \(\mathbf{s}\). In more detail, given a large prime \(q\) and polynomially many pairs \((\mathbf{a}_i, \langle \mathbf{a}_i,\;\mathbf{s}\rangle + e_i)\), where \(\mathbf{a}_i \in \mathbb{Z}_q^n\) are random and \(e_i \in \mathbb{Z}_q\) are “small” perturbations chosen from some appropriate distribution, the LWE problem asks to find \(\mathbf{s}\). For our second assumption, we require three cyclic groups of large prime order (\(q\), say), \(\mathbb{G}_1\), \(\mathbb{G}_2\), and \(\mathbb{G}_T\). Let \(e:\mathbb{G}_1\times \mathbb{G}_2 \to \mathbb{G}_T\) be a nondegenerate bilinear map or “pairing,” and \(g_1\) and \(g_2\) be the generators of \(\mathbb{G}_1\) and \(\mathbb{G}_2\), respectively. Then, by the bilinearity of the pairing, we have that \(e (\;g_1^a, \; g_2^b \;) = e(\;g_1,\; g_2\;)^{ab}\) for any \(a, b \in \mathbb{Z}_q\). We require that the group operations in \(\mathbb{G}_1\), \(\mathbb{G}_2\), and \(\mathbb{G}_T\) as well as the bilinear map \(e\) can be efficiently computed. In terms of hardness, we will roughly assume that the only information the adversary can learn is via legitimate group and pairing computations on the elements she receives. This strong security guarantee can be formalized in the so-called generic group model [22, 20]. We may think of \(a\) as a secret “message” that is encoded in the exponent of a group element \(g_1^a\). Both LWE and bilinear map–based assumptions have been studied extensively, and we have significant confidence in their hardness. These are also two of the most versatile tools in cryptography and have been used to construct breakthrough applications such as identity-based encryption [5], fully homomorphic encryption [14], and such others. Traditionally, these assumptions were used in mutual exclusion for any given construction, but recently we are learning to combine them in novel non-black-box ways to yield surprising results. In this article, I will describe a recent construction of the primitive of broadcast encryption in a joint work with Shota Yamada [2] where we leveraged a serendipitous interplay of these structures to obtain optimal parameters.

Before describing the construction, let us take a step back and examine why we may hope for this interplay to be fruitful. Syntactically, we see immediately that if we set the group order \(q\) for the elliptic curve groups to be the same as the modulus in which LWE is conjectured hard, then the elements encoded in the exponent can be set to be LWE samples. But what would be the point of this embedding? The answer is in the relatively orthogonal strengths that these two structures bring to the table of cryptographic construction. Over decades of extensive study, researchers developed powerful applications of pairings, often by using them in (initially) nonstandard ways and formulating new assumptions which were only justified in the generic group model. Over time we saw that with more work, these assumptions could often be reduced to standard assumptions, and when they could not, they nevertheless seemed to withstand attack. Thus, an informal rule of thumb that emerged is: “if a pairing-based scheme achieves functionality, and resists generic attacks, then it is likely to be secure even in the standard model.”

However, for the advanced applications of today, pairings are often insufficient for functionality as they are intrinsically limited to degree \(2\) computation. After one multiplication of messages in the exponent, the resultant encoding is in the target group \(\mathbb{G}_T\), the pairing is used up, and there is no way to “keep going.” Indeed, pairings can only be used to construct fully homomorphic encryption (FHE) for degree \(2\) polynomials [8]. In contrast, LWE can be used to construct FHE for all \({\sf P}\) [11, 10, 16]! In general, LWE does not suffer from the “degree 2” barrier — an application that can be made to work for degree \(2\) can likely be generalized to \({\mathsf{NC}}_1\) or even \({\sf P}\). However, many modern applications, such as the construction of multilinear maps [13, 15], use lattices in nonstandard ways that do not permit a reduction to LWE. Unfortunately, nonstandard methods of extending LWE have often resulted in devastating attacks, which have been fixed only to be attacked again (please see [3] for a summary). Thus, our confidence in nonstandard lattice assumptions is shaky, and the informal rule of thumb here is “if a lattice-based scheme is secure for degree \(2\), functionality can likely be extended to a higher degree.” The natural question is whether we can get the best of both. In some cases, such as for broadcast encryption and some recent constructions of obfuscation [1, 4, 18, 19], it turns out that we can.

Broadcast encryption (BE), introduced by Fiat and Naor [12], enables a sender to encrypt a message for a subset of users who are listening on a broadcast channel. In more detail, in a BE system, a sender can encrypt to any set \(S\) of its choice, and any user in \(S\) can decrypt the broadcast using its secret key. The system is said to be secure, or collusion resistant, if no collection of users outside \(S\) can pool together their keys to learn anything about the plaintext. The celebrated work of Boneh, Gentry, and Waters [7] obtained full collusion resistance along with short ciphertexts and secret keys but suffered from a large public key. The first construction with optimal parameters was provided by Boneh, Waters, and Zhandry [9] almost a decade later by relying on multilinear maps of logarithmic degree. In our work [2], we achieve the same performance from LWE and pairings.

Our starting observation was that the question of broadcast encryption can be restated in terms of the notion of ciphertext policy attribute-based encryption (CP-ABE). In a CP-ABE scheme, a ciphertext for a message \(m\) is labeled with a function (policy) \(f\), and secret keys are labeled with public attributes \(\mathbf{x}\) from the domain of \(f\). Decryption succeeds to yield the hidden message \(m\) if and only if the attribute satisfies the policy, namely \(f(\mathbf{x})=1\). To see BE as a special case of CP-ABE, note that the ciphertext may encode a circuit \(F_S\) that checks membership of a given user index in a set of recipients \(S\), and the attributes \(\mathbf{x}\) may encode user index in the set \(N\). Thus, a user \(i\) can use her CP-ABE secret key to test whether \(i\) is a member of the set \(S\) encoded in the ciphertext and recover the message \(m\) if and only if this is true. Then, a natural approach to construct BE is to leverage CP-ABE schemes. However, unsurprisingly, suitable constructions of CP-ABE have been elusive.

On the other hand, the celebrated works of Gorbunov et al. [17] and Boneh et al. [6] show how to construct the dual notion of key-policy ABE (KP-ABE) for all of \({\sf P}\) based on LWE. KP-ABE is the same as CP-ABE with the roles of circuit and attributes swapped. We notice that the KP-ABE by Boneh et al. (henceforth denoted as \(\mathsf{BGG}^{\mathsf +}\)) can be repurposed to achieve the functionality of CP-ABE but not collusion resistance — the scheme can be proved secure only in a weak game where the attacker is restricted to obtaining a single key for some attribute \(\mathbf{x}\). Here, not only can we not prove collusion resistance, but in fact, we can show a simple attack if the attacker obtains even two keys. In more detail, let us denote the ciphertext encoding corresponding to bit \(x_i\) in \(\mathsf{BGG}^{\mathsf +}\) as \(\psi_{i,x_i}\). Intuitively, obtaining keys for \(\mathbf{x}\) and \(\bar{\mathbf{x}}\) lets the attacker learn \(\psi_{i,0}\) as well as \(\psi_{i,1}\) for all \(i\), which completely breaks the security of \(\mathsf{BGG}^{\mathsf +}\). Thus, we can obtain functionality but not security from LWE.

The central new idea of our work is that to achieve security, we can turn to pairings. If we separate \(\psi_{i,x_i}\) and \(\psi_{i,\bar{x}_i}\) by masking them with different randomizers and lift them to the exponent of a bilinear group, then we can prevent the aforementioned attack. Indeed, with some more work, we can show that this trick allows us to resist all generic attacks. By the rule of thumb of pairing-based constructions, if we can achieve functionality and resist generic attacks, we are done. However, functionality is non-obvious: an immediate problem is how to check for membership in set \(S\) in the exponent, since this is in \({\mathsf{NC}}_1\). The answer lies in the specific structure of the \(\mathsf{BGG}^{\mathsf +}\) evaluation algorithm, which by happy coincidence is linear in the encodings and the secret key, even for a circuit in \({\sf P}\), followed by a final rounding step to remove the noise. Thus, we may perform the membership check computation in the exponent, recover the output via brute force discrete log, and then compute the rounding “downstairs” in the clear. Care needs to be taken to ensure that the final output in the exponent is polynomially bounded so that discrete log is feasible; however, by more happy (and nontrivial) coincidence, this can be ensured. The succinctness of the \(\mathsf{BGG}^{\mathsf +}\) key and ciphertext allows us to obtain optimal parameters.

To conclude, the composition of pairings and LWE was made possible in this context by a beautiful synergy of their respective properties and led to a significant weakening of the assumptions required for optimal broadcast encryption. Going forward, it would be interesting to see more applications of these ideas and to seek more connections that may lurk between seemingly diverse structures.

References
[1] Agrawal, Shweta. 2019. “Indistinguishability Obfuscation Without Multilinear Maps: New Techniques for Bootstrapping and Instantiation.” In Eurocrypt.