Monday, August 31st, 2020

Research Vignette: The Unlikely Friendship of Lattices and Elliptic Curves

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.

Our assumptions

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.

Two halves make a whole?

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.

Optimal broadcast encryption from pairings and LWE

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.

[2] Agrawal, Shweta, and Shota Yamada. 2020. “Optimal Broadcast Encryption from Pairings and Lwe.” In Eurocrypt.

[4] Ananth, Prabhanjan, Aayush Jain, Huijia Lin, Christian Matt, and Amit Sahai. 2019. “Indistinguishability Obfuscation Without Multilinear Maps: IO from Lwe, Bilinear Maps, and Weak Pseudorandomness.” In Crypto.

[5] Boneh, Dan, and Matthew K. Franklin. 2001. “Identity-Based Encryption from the Weil Pairing.” In CRYPTO, 213–29.

[6] Boneh, Dan, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, and Dhinakaran Vinayagamurthy. 2014. “Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits.” In EUROCRYPT, 533–56.

[7] Boneh, Dan, Craig Gentry, and Brent Waters. 2005. “Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys.” In Proceedings of the 25th Annual International Conference on Advances in Cryptology. CRYPTO’05.

[8] Boneh, Dan, Eu-Jin Goh, and Kobbi Nissim. 2005. “Evaluating 2-Dnf Formulas on Ciphertexts.” In Theory of Cryptography Conference, 325–41. Springer.

[9] Boneh, Dan, Brent Waters, and Mark Zhandry. 2014. “Low Overhead Broadcast Encryption from Multilinear Maps.” In Advances in Cryptology – Crypto 2014, edited by Juan A. Garay and Rosario Gennaro.

[10] Brakerski, Zvika, Craig Gentry, and Vinod Vaikuntanathan. 2012. “(Leveled) Fully Homomorphic Encryption Without Bootstrapping.” In ITCS, 309–25.

[11] Brakerski, Zvika, and Vinod Vaikuntanathan. 2011. “Efficient Fully Homomorphic Encryption from (Standard) LWE.” In FOCS.

[12] Fiat, Amos, and Moni Naor. 1994. “Broadcast Encryption.” In Advances in Cryptology — Crypto’ 93, edited by Douglas R. Stinson.

[13] Garg, Sanjam, Craig Gentry, and Shai Halevi. 2013. “Candidate Multilinear Maps from Ideal Lattices.” In Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, 1–17.

[14] Gentry, Craig. 2009. “Fully Homomorphic Encryption Using Ideal Lattices.” In STOC, 169–78.

[15] Gentry, Craig, Sergey Gorbunov, and Shai Halevi. 2015. “Graph-Induced Multilinear Maps from Lattices.” In TCC.

[16] Gentry, Craig, Amit Sahai, and Brent Waters. 2013. “Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based.” In CRYPTO.

[17] Gorbunov, Sergey, Vinod Vaikuntanathan, and Hoeteck Wee. 2013. “Attribute Based Encryption for Circuits.” In STOC.

[18] Jain, Aayush, Huijia Lin, Christian Matt, and Amit Sahai. 2019. “How to Leverage Hardness of Constant-Degree Expanding Polynomials over R to Build iO.” In EUROCRYPT, 19–23.

[19] Jain, Aayush, Huijia Lin, and Amit Sahai. 2019. “Simplifying Constructions and Assumptions for $i\mathcal{O}$.” Cryptology ePrint Archive, Report 2019/1252.

[20] Maurer, Ueli. 2005. “Abstract Models of Computation in Cryptography.” In IMA Int. Conf., 3796:1–12. Lecture Notes in Computer Science. Springer.

[21] Regev, Oded. 2009. “On Lattices, Learning with Errors, Random Linear Codes, and Cryptography.” J.ACM 56 (6).

[22] Shoup, Victor. 1997. “Lower Bounds for Discrete Logarithms and Related Problems.” In EUROCRYPT, edited by Walter Fumy, 256–66. Lecture Notes in Computer Science. Springer Berlin Heidelberg.