International Association
for Cryptologic Research

This paper studies the hardness of decision Module Learning with Errors (MLWE) under linear leakage, which has been used as a foundation to derive more efficient lattice-based zero-knowledge proofs in a recent paradigm of Lyubashevsky, Nguyen, and Seiler (PKC 21). Unlike in the plain LWE setting, it was unknown whether this problem remains provably hard in the module/ring setting. This work shows a reduction from the search MLWE to decision MLWE with linear leakage. Thus, the main problem remains hard asymptotically as long as the non-leakage version of MLWE is hard. Additionally, we also refine the paradigm of Lyubashevsky, Nguyen, and Seiler (PKC 21) by showing a more fine-grained tradeoff between efficiency and leakage. This can lead to further optimizations of lattice proofs under the paradigm.

<jats:title>Abstract</jats:title><jats:p>Non-malleable codes were introduced by Dziembowski et al. (in: Yao (ed) ICS2010, Tsinghua University Press, 2010), and its main application is the protection of cryptographic devices against tampering attacks on memory. In this work, we initiate a comprehensive study on non-malleable codes for the class of partial functions, that read/write on an arbitrary subset of codeword bits with specific cardinality. We present two constructions: the first one is in the CRS model and allows the adversary to selectively choose the subset of codeword bits, while the latter is in the standard model and adaptively secure. Our constructions are efficient in terms of information rate, while allowing the attacker to access asymptotically almost the entire codeword. In addition, they satisfy a notion which is stronger than non-malleability, that we call non-malleability with manipulation detection, guaranteeing that any modified codeword decodes to either the original message or to <jats:inline-formula><jats:alternatives><jats:tex-math>$$\bot $$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>⊥</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>. We show that our primitive implies All-Or-Nothing Transforms (AONTs), and as a result our constructions yield efficient AONTs under standard assumptions (only one-way functions), which, to the best of our knowledge, was an open question until now. Furthermore, we construct a notion of continuous non-malleable codes (CNMC), namely CNMC with light updates, that avoids the full re-encoding process and only uses shuffling and refreshing operations. Finally, we present a number of additional applications of our primitive in tamper resilience.</jats:p>

Functional bootstrapping seamlessly integrates the benefits of homomorphic computation using a look-up table and the noise reduction capabilities of bootstrapping. Its wide-ranging applications in privacy-preserving protocols underscore its broad impacts and significance. In this work, our objective is to craft more efficient and less restricted functional bootstrapping methods for general functions within a polynomial modulus. We introduce a series of novel techniques, proving that functional bootstrapping for general functions can be essentially as efficient as regular FHEW/TFHE bootstrapping. Our new algorithms operate within the realm of prime-power and odd composite cyclotomic rings, offering versatility without any additional requirements on input noise and message space beyond correct decryption.

In this series of work, we aim at improving the bootstrapping paradigm for fully homomorphic encryption (FHE). Our main goal is to show that the amortized cost of bootstrapping within a polynomial modulus only requires $\tilde O(1)$ FHE multiplications. To achieve this, we develop substantial algebraic techniques in two papers. Particularly, the first one (this work) proposes a new mathematical framework for batch homomorphic computation that is compatible with the existing bootstrapping methods of AP14/FHEW/TFHE. To show that our overall method requires only a polynomial modulus, we develop a critical algebraic analysis over noise growth, which might be of independent interest. Overall, the framework yields an amortized complexity $\tilde O(\sep^{0.75})$ FHE multiplications, where $\sep$ is the security parameter. This improves the prior methods of AP14/FHEW/TFHE, which required $O(\sep)$ FHE multiplications in amortization. Developing many substantial new techniques based on the foundation of this work, the sequel (\emph{Bootstrapping II}, in Eurocrypt 2023) shows how to further improve the recursive bootstrapping method of MS18 (Micciancio and Sorrell, ICALP 2018), whose amortized efficiency is $O(3^{1/\epsilon} \cdot \sep^{\epsilon})$ FHE multiplications for any arbitrary constant $\epsilon >0$. The dependency on $\epsilon$ posts an inherent tradeoff between theory and practice -- theoretically, smaller $\epsilon$'s are better under the asymptotic measure, but the constant $3^{1/\epsilon}$ would become prohibitively large as $\epsilon$ approaches $0$. Our new methods can break the tradeoff and achieve $\tilde O(1)$ amortized complexity. This is a substantial theoretical improvement and can potentially lead to more practical methods.

This work continues the exploration of the batch framework proposed in \emph{Batch Bootstrapping I} (Liu and Wang, Eurocrypt 2023). By further designing novel batch homomorphic algorithms based on the batch framework, this work shows how to bootstrap $\sep$ LWE input ciphertexts within a polynomial modulus, using $\tilde O(\sep)$ FHE multiplications. This implies an amortized complexity $\tilde O(1)$ FHE multiplications per input ciphertext, significantly improving our first work (whose amortized complexity is $\tilde O(\sep^{0.75})$) and another theoretical state of the art MS18 (Micciancio and Sorrell, ICALP 2018), whose amortized complexity is $O(3^{1/\epsilon} \cdot \sep^{\epsilon})$, for any arbitrary constant $\epsilon$. We believe that all our new homomorphic algorithms might be useful in general applications, and thus can be of independent interests.

We derive the first adaptively secure \ibe~and \abe for t-CNF, and selectively secure \abe for general circuits from lattices, with $1-o(1)$ leakage rates, in the both relative leakage model and bounded retrieval model (\BRM). To achieve this, we first identify a new fine-grained security notion for \abe~-- partially adaptive/selective security, and instantiate this notion from \LWE. Then, by using this notion, we design a new key compressing mechanism for identity-based/attributed-based weak hash proof system (\ib/\ab-\whps) for various policy classes, achieving (1) succinct secret keys and (2) adaptive/selective security matching the existing non-leakage resilient lattice-based designs. Using the existing connection between weak hash proof system and leakage resilient encryption, the succinct-key \ib/\ab-\whps~can yield the desired leakage resilient \ibe/\abe schemes with the optimal leakage rates in the relative leakage model. Finally, by further improving the prior analysis of the compatible locally computable extractors, we can achieve the optimal leakage rates in the \BRM.

We give the first constructions in the plain model of 1) nonmalleable digital lockers (Canetti and Varia, TCC 2009) and 2) robust fuzzy extractors (Boyen et al., Eurocrypt 2005) that secure sources with entropy below 1/2 of their length. Constructions were previously only known for both primitives assuming random oracles or a common reference string (CRS). We define a new primitive called a nonmalleable point function obfuscation with associated data. The associated data is public but protected from all tampering. We construct a digital locker using a similar paradigm. Our construction achieves nonmalleability over the output point by placing a CRS into the associated data and using an appropriate non-interactive zero-knowledge proof. Tampering is protected against the input point over low-degree polynomials and over any tampering to the output point and associated data. Our constructions achieve virtual black box security. These constructions are then used to create robust fuzzy extractors that can support low-entropy sources in the plain model. By using the geometric structure of a syndrome secure sketch (Dodis et al., SIAM Journal on Computing 2008), the adversary's tampering function can always be expressed as a low-degree polynomial; thus, the protection provided by the constructed nonmalleable objects suffices.

This work proposes a new lattice two-stage sampling technique, generalizing the prior two-stage sampling method of Gentry, Peikert, and Vaikuntanathan (STOC '08). By using our new technique as a key building block, we can significantly improve security and efficiency of the current state of the arts of simulation-based functional encryption. Particularly, our functional encryption achieves $(Q,\poly)$ simulation-based semi-adaptive security that allows arbitrary pre- and post-challenge key queries, and has succinct ciphertexts with only an additive $O(Q)$ overhead. %This significantly improves the current research frontier of simulation-based functional encryption. Additionally, our two-stage sampling technique can derive new feasibilities of indistinguishability-based adaptively-secure $\IB$-$\FE$ for inner products and semi-adaptively-secure $\AB$-$\FE$ for inner products, breaking several technical limitations of the recent work by Abdalla, Catalano, Gay, and Ursu (Asiacrypt '20).

In this work, we first present general methods to construct information rate-1 PKE that is $\KDM^{(n)}$-secure with respect to \emph{block-affine} functions for any unbounded polynomial $n$. To achieve this, we propose a new notion of extractor that satisfies \emph{reusability}, \emph{homomorphic}, and \emph{security against correlated-source attacks}, and show how to use this extractor to improve the information rate of the \KDM-secure PKE of Brakerski et al.~(Eurocrypt 18). Then, we show how to amplify \KDM~security from block-affine function class into general bounded size circuits via a variant of the technique of Applebaum (Eurocrypt 11), achieving better efficiency. Furthermore, we show how to generalize these approaches to the IBE setting. Additionally, our PKE and IBE schemes are also leakage resilient, with leakage rates $1-o(1)$ against a slightly smaller yet still general class -- block leakage functions. We can instantiate the required building blocks from $\LWE$ or $\DDH$.

This work constructs an identity based encryption from the ring learning with errors assumption (RLWE), with shorter master public keys and tighter security analysis. To achieve this, we develop three new methods: (1) a new homomorphic equality test method using nice algebraic structures of the rings, (2) a new family of hash functions with natural homomorphic evaluation algorithms, and (3) a new insight for tighter reduction analyses. These methods can be used to improve other important cryptographic tasks, and thus are of general interests. Particularly, our homomorphic equality test method can derive a new method for packing/unpacking GSW-style encodings, showing a new non-trivial advantage of RLWE over the plain LWE. Moreover, our new insight for tighter analyses can improve the analyses of all the currently known partition-based IBE designs, achieving the best of the both from prior analytical frameworks of Waters (Eurocrypt ’05) and Bellare and Ristenpart (Eurocrypt ’09).

Non-malleable codes, introduced as a relaxation of error-correcting codes by Dziembowski, Pietrzak, and Wichs (ICS ’10), provide the security guarantee that the message contained in a tampered codeword is either the same as the original message or is set to an unrelated value. Various applications of non-malleable codes have been discovered, and one of the most significant applications among these is the connection with tamper-resilient cryptography. There is a large body of work considering security against various classes of tampering functions, as well as non-malleable codes with enhanced features such as leakage resilience . In this work, we propose combining the concepts of non-malleability , leakage resilience , and locality in a coding scheme. The contribution of this work is threefold: 1. As a conceptual contribution, we define a new notion of locally decodable and updatable non-malleable code that combines the above properties. 2. We present two simple and efficient constructions achieving our new notion with different levels of security. 3. We present an important application of our new tool—securing RAM computation against memory tampering and leakage attacks. This is analogous to the usage of traditional non-malleable codes to secure implementations in the circuit model against memory tampering and leakage attacks.

In this work, we conduct a comprehensive study on establishing hardness reductions for (Module) Learning with Rounding over rings (RLWR). Towards this, we present an algebraic framework of LWR, inspired by a recent work of Peikert and Pepin (TCC '19). Then we show a search-to-decision reduction for Ring-LWR, generalizing a result in the plain LWR setting by Bogdanov et al. (TCC '15). Finally, we show a reduction from Ring-LWE to Module Ring-LWR (even for leaky secrets), generalizing the plain LWE to LWR reduction by Alwen et al. (Crypto '13). One of our central techniques is a new ring leftover hash lemma, which might be of independent interests.

Achieving tight security is a fundamental task in cryptography. While one of the most important purposes of this task is to improve the overall efficiency of a construction (by allowing smaller security parameters), many current lattice-based instantiations do not completely achieve the goal. Particularly, a super-polynomial modulus seems to be necessary in all prior work for (almost) tight schemes that allow the adversary to conduct queries, such as PRF, IBE, and Signatures. As the super-polynomial modulus would affect the noise-to-modulus ratio and thus increase the parameters, this might cancel out the advantages (in efficiency) brought from the tighter analysis. To determine the full power of tight security/analysis in lattices, it is necessary to determine whether the super-polynomial modulus restriction is inherent. In this work, we remove the super-polynomial modulus restriction for many important primitives – PRF, IBE, All-but-many Lossy Trapdoor Functions, and Signatures. The crux relies on an improvement over the framework of Boyen and Li (Asiacrypt 16), and an almost tight reduction from LWE to LWR, which improves prior work by Alwen et al. (Crypto 13), Bogdanov et al. (TCC 16), and Bai et al. (Asiacrypt 15). By combining these two advances, we are able to derive these almost tight schemes under LWE with a polynomial modulus.

In this work, we revisit the primitive functional encryption (FE) for inner products and show its application to decentralized attribute-based encryption (ABE). Particularly, we derive an FE for inner products that satisfies a stronger notion, and show how to use such an FE to construct decentralized ABE for the class $$\{0,1\}$$-$$\mathsf {LSSS} $$ against bounded collusions in the plain model. We formalize the FE notion and show how to achieve such an FE under the LWE or DDH assumption. Therefore, our resulting decentralized ABE can be constructed under the same standard assumptions, improving the prior construction by Lewko and Waters (Eurocrypt 2011). Finally, we also point out challenges to construct decentralized ABE for general functions by establishing a relation between such an ABE and witness encryption for general NP statements.

The literature on leakage-resilient cryptography contains various leakage models that provide different levels of security. In the bounded leakage model (Akavia et al.—TCC 2009 ), it is assumed that there is a fixed upper bound L on the number of bits the attacker may leak on the secret key in the entire lifetime of the scheme. Alternatively, in the continual leakage model (Brakerski et al.—FOCS 2010 , Dodis et al.—FOCS 2010 ), the lifetime of a cryptographic scheme is divided into “time periods” between which the scheme’s secret key is updated. Furthermore, in its attack the adversary is allowed to obtain some bounded amount of leakage on the current secret key during each time period. In the continual leakage model, a challenging problem has been to provide security against leakage on key updates , that is, leakage that is a function of not only the current secret key but also the randomness used to update it. We propose a modular approach to overcome this problem based on program obfuscation. Namely, we present a compiler that transforms any public key encryption or signature scheme that achieves a slight strengthening of continual leakage resilience, which we call consecutive continual leakage resilience, to one that is continual leakage resilient with leakage on key updates, assuming indistinguishability obfuscation (Barak et al.—CRYPTO 2001 , Garg et al.—FOCS 2013 ). Under stronger forms of obfuscation, the leakage rate tolerated by our compiled scheme is essentially as good as that of the starting scheme. Our compiler is derived by making a connection between the problems of leakage on key updates and so-called sender-deniable encryption (Canetti et al.—CRYPTO 1997 ), which was recently constructed based on indistinguishability obfuscation by Sahai and Waters (STOC 2014 ). In the bounded leakage model, we give an approach to constructing leakage-resilient public key encryption from program obfuscation based on the public key encryption scheme of Sahai and Waters (STOC 2014 ). In particular, we achieve leakage-resilient public key encryption tolerating L bits of leakage for any L from $${\mathsf {iO}} $$ iO and one-way functions. We build on this to achieve leakage-resilient public key encryption with optimal leakage rate of $$1-o(1)$$ 1 - o ( 1 ) based on stronger forms of obfuscation and collision-resistant hash functions. Such a leakage rate is not known to be achievable in a generic way based on public key encryption alone. We then develop additional techniques to construct public key encryption that is (consecutive) continual leakage resilient under appropriate assumptions, which we believe is of independent interest.

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs (ICS ’10) and its main application is the protection of cryptographic devices against tampering attacks on memory. In this work, we initiate a comprehensive study on non-malleable codes for the class of partial functions, that read/write on an arbitrary subset of codeword bits with specific cardinality. Our constructions are efficient in terms of information rate, while allowing the attacker to access asymptotically almost the entire codeword. In addition, they satisfy a notion which is stronger than non-malleability, that we call non-malleability with manipulation detection, guaranteeing that any modified codeword decodes to either the original message or to $$\bot $$⊥. Finally, our primitive implies All-Or-Nothing Transforms (AONTs) and as a result our constructions yield efficient AONTs under standard assumptions (only one-way functions), which, to the best of our knowledge, was an open question until now. In addition to this, we present a number of additional applications of our primitive in tamper resilience.

Order-revealing encryption (ORE) is a primitive for outsourcing encrypted databases which allows for efficiently performing range queries over encrypted data. Unfortunately, a series of works, starting with Naveed et al. (CCS 2015), have shown that when the adversary has a good estimate of the distribution of the data, ORE provides little protection. In this work, we consider the case that the database entries are drawn identically and independently from a distribution of known shape, but for which the mean and variance are not (and thus the attacks of Naveed et al. do not apply). We define a new notion of security for ORE, called parameter-hiding ORE, which maintains the secrecy of these parameters. We give a construction of ORE satisfying our new definition from bilinear maps.