Cumulatively All-Lossy-But-One Trapdoor Functions from Standard Assumptions

Abstract

Chakraborty, Prabhakaran, and Wichs (PKC’20) recently introduced a new tag-based variant of lossy trapdoor functions, termed cumulatively all-lossy-but-one trapdoor functions (CALBO-TDFs). Informally, CALBO-TDFs allow defining a public tag-based function with a (computationally hidden) special tag, such that the function is lossy for all tags except when the special secret tag is used. In the latter case, the function becomes injective and efficiently invertible using a secret trapdoor. This notion has been used to obtain advanced constructions of signatures with strong guarantees against leakage and tampering, and also by Dodis, Vaikunthanathan, and Wichs (EUROCRYPT’20) to obtain constructions of randomness extractors with extractor-dependent sources. While these applications are motivated by practical considerations, the only known instantiation of CALBO-TDFs so far relies on the existence of indistinguishability obfuscation.

In this paper, we propose the first two instantiations of CALBO-TDFs based on standard assumptions. Our constructions are based on the LWE assumption with a sub-exponential approximation factor and on the DCR assumption, respectively, and circumvent the use of indistinguishability obfuscation by relying on lossy modes and trapdoor mechanisms enabled by these assumptions.

1 Introduction

As introduced by Peikert and Waters [48], lossy trapdoor functions (LTDFs) are function families where evaluation keys can be sampled in two modes: In the injective mode, a function $F_{\textsf {ek}}(\cdot )$ is injective and can be inverted using a trapdoor $\textsf {tk}$ that comes with the evaluation key $\textsf {ek}$; In the lossy mode, a function $F_{\textsf {ek}}(\cdot )$ has a much smaller image size and thus loses a certain amount of information about its input. The standard security of an LTDF requires that the two modes be indistinguishable. That is, no efficient distinguisher can tell apart lossy evaluation keys from injective ones.

Lossy trapdoor functions have been built from a variety of standard cryptographic assumptions, such as the Decisional Diffie-Hellman (DDH) [25, 29, 48] and Learning with Errors (LWE) assumptions [2, 8, 48], the Quadratic Residuosity (QR) [24, 25, 37] and Composite Residuosity (DCR) assumptions [25], the Phi-hiding assumption [3, 41] and more [46, 53]. They have found numerous applications in cryptography, including chosen-ciphertext security, trapdoor functions with many hard-core bits, collision-resistant hash functions, oblivious transfer [48], deterministic [9, 50] and hedged public-key encryption [6, 52] in the standard model, instantiability of RSA-OAEP [41], computational extractors [23, 27], pseudo-entropy functions [18], selective-opening security [7], and more.

Several generalizations of LTDFs have been considered. Of particular interest are the tag-based variants, where algorithms take an additional tag as input. In all-but-one LTDFs [48] for instance, the evaluation key obtained by running the sampling algorithm with a special tag $\textsf {tag}^*$ is such that the function $F_{\textsf {ek}}(\cdot ,\textsf {tag})$ is injective for all tags $\textsf {tag}\ne \textsf {tag}^*$, but the function $F_{\textsf {ek}}(\cdot ,\textsf {tag}^*)$ is lossy. All-but-one LTDFs have been generalized to all-but-N LTDFs [36] (which admit $N>1$ lossy tags) or all-but-many lossy trapdoor functions (where arbitrarily many lossy tags can be adaptively created). The latter notion notably found applications to selective-opening chosen-ciphertext security with compact ciphertexts [14, 39, 43].

In a setting where multiple lossy evaluations are provided (e.g., for multiple lossy evaluation keys in the context of standard LTDFs or for multiple lossy tags in the context of tag-based LTDFs), one may want to guarantee that multiple lossy evaluations on the same input x do not reveal more information about x than a single evaluation. This additional property was termed cumulative lossiness in [19] where it was formalized by requiring the existence of a (possibly inefficient) algorithm that starts with some fixed, partial information about x and recovers the entire information provided by the multiple lossy evaluations. The fact that all these evaluations can be recovered (even inefficiently) from the same amount of partial information on x then guarantees that multiple lossy evaluations on the same input x preserve the entropy of x. In particular, they do not end up leaking x entirely.

In this paper, we investigate the notion of cumulatively all-lossy-but-one trapdoor functions, suggested by Chakraborty, Prabharkaran and Wichs [19], which considers the case where all tags are lossy, except one. This notion has been used to obtain advanced constructions of randomness extractors [23] and signatures in the leakage and tampering model [19].

Cumulatively All-Lossy-But-One Lossy Trapdoor Functions. A cumulatively all-lossy-but-one trapdoor functions (CALBO-TDFs) is a tag-based LTDFs where the function $F_{\textsf {ek}}(\cdot ,\textsf {tag})$ is lossy for any tag $\textsf {tag}$ except one special injective tag $\textsf {tag}^*$, for which $F_{\textsf {ek}}(\cdot ,\textsf {tag}^*)$ is invertible using a trapdoor $\textsf {td}$ associated with $\textsf {ek}$. In addition, the lossiness is required to be cumulative in the sense that multiple evaluations $F_{\textsf {ek}}(x,\textsf {tag}_i)$ for lossy tags $\textsf {tag}_i \ne \textsf {tag}^*$ always leak the same information about x. Finally, the evaluation key should computationally hide the special injective tag and evaluation keys generated with distinct injective tags are required to be (computationally) indistinguishable.

In [23], the notion of CALBO-TDFs was relaxed by not requiring the existence of a trapdoor for the injective tag $\textsf {tag}^*$. This relaxed notion, termed CALBO functions (or CALBOs for short), is also implicit in [18, 26]. By dropping the trapdoor requirement, these works obtained CALBOs from standard lossy functions (without trapdoor). Therefore it has been possible to construct CALBOs from many standard assumptions such as DDH, LWE, or DCR.

The design of CALBO-TDFs, for which a trapdoor is required in injective mode, is much harder. Indeed, the only known instantiation so far [19] relies on the existence of indistinguishability obfuscation [28] (iO) besides the DDH (or LWE) assumption. At a high level, the construction of [19] starts with cumulative LTDFs (C-LTDFs), which can be built from LWE or DDH, and combines it with iO and puncturable PRFs [13, 15, 40]. The idea of [19] is to generate a CALBO-TDF evaluation key as an obfuscated program in which the special injective tag $\textsf {tag}^*$ is hard-wired together with an injective evaluation key for the underlying C-LTDF. This program, on input $\textsf {tag}$, outputs the hard-wired injective evaluation key if $\textsf {tag}=\textsf {tag}^*$; Otherwise, it samples a lossy evaluation key using randomness derived from a puncturable PRF (of which the key is also hard-wired in the program) evaluated on the input $\textsf {tag}$, and finally returns the resulting evaluation key. When it comes to evaluating a function for an input x and a tag $\textsf {tag}$, [19] evaluates the underlying C-LTDF on input x using the evaluation key obtained by running the obfuscated program on input $\textsf {tag}$. The injectivity on the special tag $\textsf {tag}^*$ and the cumulative lossiness property immediately follow from the same properties in the underlying C-LTDF. Indistinguishability of evaluation keys simply follows from the security of iO, the pseudorandomness of the puncturable PRF when puncturing the tags, and the indistinguishability of lossy and injective keys in the underlying C-LTDF.

In [19], CALBO-TDFs served as a building block to construct leakage and tamper resilient signature schemes with a deterministic signing algorithm, a notion that provides a natural solution to protect signature schemes against leakage, e.g. physical analysis and timing measurements, or tampering attacks, where the adversary deliberately targets the randomness used by the algorithms. The complexity of the CALBO-TDF candidate of [19] motivates the search for simpler, more efficient instantiations of CALBO-TDFs that avoid the use of heavy hammers like obfuscation and rely on more standard assumptions.

1.1 Our Contributions

We present two constructions of CALBO-TDFs based solely on standard assumptions. Our first construction relies on the LWE assumption [51] with sub-exponential approximation factor in reducing LWE to a worst-case lattice problem¹, while our second construction relies on Paillier’s Composite Residuosity assumption [47] (DCR).

We thus avoid the use of indistinguishability obfuscation (which was used to hide the hard-wired values including the special tag and the injective evaluation key) by relying on lossy modes and trapdoor mechanisms enabled by LWE and DCR. The first construction uses the lossy mode and trapdoor mechanism of LWE in a similar way to [2, 32, 45]. By exploiting ideas from [44], it achieves a mildly relaxed notion of cumulative lossiness, where cumulative lossiness only holds with overwhelming probability over the choice of (non-injective) tags. The same relaxed notion was used in the LWE+iO-based construction of [19]. This relaxation does not hurt any of the applications, as shown [19]. Our second construction relies on the lossiness and trapdoor mechanism of the Decision Composite Residuosity (DCR) assumption. In particular, it uses the Damgård-Jurik cryptosystem [20] in a similar way to the LTDF of Freeman et al. [25].

1.2 Technical Overview

Relaxed CALBO-TDFs from LWE. We start from the observation that CALBOs (without a trapdoor) can be viewed as selectively secure unpredictable functions when the key of the function is the CALBO’s input and the input of the function serves as the CALBO’s tag. We then upgrade the $\textsf {LWE}$-based PRF of Libert, Stehlé and Titiu [44] whose security proof precisely relies on the cumulative lossiness of the LWE function (in its derandomized version based on the rounding technique of [4]) for an appropriate choice of parameters. The LWE function (which maps a pair of short integer column-vectors $(\mathbf {s},\mathbf {e}) \in \mathbb {Z}^n \times \mathbb {Z}^m$ to $\mathbf {s}^\top \mathbf {A} + \mathbf {e}^\top$, for a random matrix $\mathbf {A} \in \mathbb {Z}_q^{n \times m}$) is known [32] to provide a lossy function, and even a lossy trapdoor function for an appropriate choice of parameters [2, 8]. The PRF of [44] interprets a variant of the key-homomorphic PRF of [11] as a lossy function in its security proof. More specifically, letting $\left\lfloor \cdot \right\rfloor _p : \mathbb {Z}_q \rightarrow \mathbb {Z}_p$ denote the rounding function of [4] for moduli $p<q$ defined as $\left\lfloor \mathbf {x} \right\rfloor _p = \lfloor (p/q) \cdot \mathbf {x} \rfloor$, the function mapping $\mathbf {x} \in \mathbb {Z}^n_q$ to $\left\lfloor \mathbf {x}^\top \cdot \mathbf {A} \right\rfloor _p$ is injective when $\mathbf {A}\in \mathbb {Z}^{n\times m}_q$ is uniformly random and lossy (as shown in [2]) when $\mathbf {A}$ is of the form $\mathbf {D}^\top \cdot \mathbf {B} + \mathbf {E}$ for some random $\mathbf {B} \in \mathbb {Z}^{\ell \times m}_q, \mathbf {D} \in \mathbb {Z}^{\ell \times n}_q$, $\ell \ll n$, and some small-norm matrix $\mathbf {E}$. The PRF of [44] maps an input x to $\lfloor \mathbf {s}^\top \mathbf {A}(x) \rfloor _p$, where $\mathbf {s} \in \mathbb {Z}^n$ is the secret key and $\mathbf {A}(x) \in \mathbb {Z}_q^{n \times m}$ is an input-dependent matrix derived from public matrices. The latter matrix is actually obtained using fully homomorphic encryption techniques, by multiplying Gentry-Sahai-Waters (GSW) ciphertexts [31] indexed by the bits of x. The security proof of [44] “programs” $\mathbf {A}(x)$ in such a way that all evaluation queries reveal a lossy function of the secret key $\mathbf {s}$ while the challenge evaluation reveals a non-lossy function $\lfloor \mathbf {s}^\top \mathbf {A}(x^\star ) \rfloor _p$ of $\mathbf {s}$. By choosing a large enough ratio q/p, they show that all evaluation queries reveal the same information about the secret key $\mathbf {s}$, which is exactly what we need to prove cumulative lossiness in the CALBO setting. At the same time, [44] shows that $\lfloor \mathbf {s}^\top \mathbf {A}(x^\star ) \rfloor _p$ retains a large amount of entropy conditionally on the information revealed by all evaluation queries.

We introduce two modifications in the function of [44]. First, we only need a selectively secure version of their PRF since the injective tag $\textsf {tag}^*$ is known ahead of time in the security experiment whereas [44] has to prove adaptive security using an admissible hash function [10]. We thus remove the admissible hash function and directly compute $\mathbf {A}(x)$ as a product of public GSW ciphertexts indexed by the tag bits without encoding them first. As a second modification w.r.t [44], we need to extend the tag-dependent matrix $\mathbf {A}(x)$ so as to ensure invertibility in injective mode.

Our CALBO construction can be outlined as follows. Given the injective tag $\textsf {tag}^* \in \{0,1\}^t$, the setup algorithm first generates $\mathbf {A}=\mathbf {D}^\top \cdot \mathbf {B} + \mathbf {E} \in \mathbb {Z}_q^{n \times m}$ as a lossy matrix, where $\mathbf {B} \in \mathbb {Z}_q^{\ell \times m}$, $\mathbf {D} \in \mathbb {Z}_q^{\ell \times n}$ and $\mathbf {E} \in \mathbb {Z}^{n \times m}$, with $\ell \ll n <m$. Then, the setup algorithm embeds $(\mathbf {A},\mathbf {B})$ in the evaluation key $\textsf {ek}$ via a set of GSW ciphertexts [31]

$$\begin{aligned} \mathbf {A}_{i,b} = \mathbf {A} \cdot \mathbf {R}_{i,b} + \delta _{b,\textsf {tag}^*_i} \cdot \mathbf {G} \qquad \quad \forall i \in [t],\,b \in \{0,1\}\end{aligned}$$

(1)

where $\textsf {tag}^*_{i}$ denotes the i-th bit of $\textsf {tag}^*$, $\delta _{b,\textsf {tag}^*_i}= (b {\mathop {=}\limits ^{ {\tiny ?}}}\textsf {tag}^*_i)$, $\mathbf {G} \in \mathbb {Z}_q^{n \times \lceil n \cdot \log q \rceil }$ is the gadget matrix of Micciancio and Peikert [45], and $\mathbf {R}_{i,b} \in \{0,1\}^{m \times \lceil n \cdot \log q \rceil }$ for each $i\in [t]$. The trapdoor $\textsf {tk}$ (which allows inverting in injective mode) contains $\{\mathbf {R}_{i,b}\}_{i\in [t],b\in \{0,1\}}$. The computational indistinguishability of keys for different injective tags follows from the LWE assumption. The latter implies that the lossy matrix $\mathbf {A}=\mathbf {D}^\top \cdot \mathbf {B} + \mathbf {E}$ is indistinguishable from a uniform matrix in $\mathbb {Z}_q^{n \times m}$. When $\mathbf {A}$ is uniform, the Leftover Hash Lemma implies that each product $\mathbf {A} \cdot \mathbf {R}_{i,b}$ is statistically close to the uniform distribution $U(\mathbb {Z}_q^{n \times m})$. This ensures that matrices (1) statistically hide $\textsf {tag}^*$ as they are statistically indistinguishable from i.i.d. random matrices over $\mathbb {Z}_q$.

In order to evaluate the function on an input $\mathbf {x}$ for a tag $\textsf {tag}$, the evaluation algorithm computes a product of GSW ciphertexts $\{\mathbf {A}_{i,\textsf {tag}_i} \}_{i=1}^t$ chosen among $\{(\mathbf {A}_{i,0},\mathbf {A}_{i,1})\}_{i=1}^t$ and then obtains a ciphertext $\mathbf {A}(\textsf {tag})$ encrypting the logical $\mathsf {AND}$ $C_{\textsf {tag}}(\textsf {tag}^*) \triangleq \bigwedge _{i=1}^t (\textsf {tag}_i = \textsf {tag}_i^*)$, where $\{\textsf {tag}_i\}_{i=1}^t$ are the bits of $\textsf {tag}$. Said otherwise, the tag-dependent matrix $\mathbf {A}(\textsf {tag}) = \mathbf {A}\cdot \mathbf {R}_{\textsf {tag}} + C_{\textsf {tag}^*}(\textsf {tag})\cdot \mathbf {G}$ is an encryption of $C_{\textsf {tag}}(\textsf {tag}^*) = \prod ^t_{i=1} \delta _{\textsf {tag}_i,\textsf {tag}^*_i},$ where the circuit $C_{\textsf {tag}}(\cdot )$ is homomorphically evaluated by computing a subset product of GSW ciphertexts in the most sequential way (according to the terminology in [5]) so as to minimize the noise growth. This is done by making sure that each multiplication always involves a fresh GSW ciphertext.

Finally, the output of the evaluation is $\left\lfloor \mathbf {x}^\top \cdot [\mathbf {A}\,|\,\mathbf {A}(\textsf {tag})] \right\rfloor _p$. Here, we slightly modify [44] where the challenge evaluation is of the form $\left\lfloor \mathbf {x}^\top \mathbf {A}(\textsf {tag}) \right\rfloor _p$. The reason is that, in order to ensure invertibility for the injective tag $\textsf {tag}^*$, we need to exploit the fact that $\mathbf {A}(\textsf {tag}^*)$ depends on $\mathbf {G}$. To this end, we need an injective evaluation of $\mathbf {x}$ to be of the form

$$\left\lfloor \mathbf {x}^\top \cdot [\mathbf {A}\,|\,\mathbf {A}(\textsf {tag}^*)] \right\rfloor _p = \left\lfloor \mathbf {x}^\top \cdot [\mathbf {A}\,|\, \mathbf {A} \cdot \mathbf {R}_{\textsf {tag}^*} + \mathbf {G} ] \right\rfloor _p $$

for some small-norm matrix $\mathbf {R}_{\textsf {tag}^*} \in \mathbb {Z}^{n \times \lceil n \cdot \log q \rceil }$. In this case, the binary matrices $\mathbf {R}_{i,b}$ contained in $\textsf {tk}$ can be used to compute $\mathbf {R}_{\textsf {tag}^*}$, which is a Micciancio-Peikert trapdoor [45] for the matrix $[\mathbf {A}\,|\,\mathbf {A}(\textsf {tag}^*)]$ and allows inverting the function $\mathbf {x} \rightarrow \left\lfloor \mathbf {x}^\top \cdot [\mathbf {A}\,|\,\mathbf {A}(\textsf {tag}^*)] \right\rfloor _p$ in the same way as in the LTDF of [2].

In lossy mode (when $\textsf {tag}$ differs from $\textsf {tag}^*$ in at least one bit), we can achieve cumulative lossiness only for a fixed input, due to the error introduced by the rounding operation. The argument is essentially the same as that in [44]: We exploit the lossy form of $\mathbf {A}$ and the fact that, for any lossy tag $\textsf {tag}\ne \textsf {tag}^*$, the matrix $[\mathbf {A}\,|\,\mathbf {A}(\textsf {tag})]= [\mathbf {A}\,|\, \mathbf {A} \cdot \mathbf {R}_{\textsf {tag}} ]$ does not depend on $\mathbf {G}$. Then, with overwhelming probability, evaluations $\left\lfloor \mathbf {x}^\top \cdot [\mathbf {A}\,|\, \mathbf {A} \cdot \mathbf {R}_{\textsf {tag}} ] \right\rfloor _p$ always reveal the same information about $\mathbf {x} \in \mathbb {Z}^n$ since w.h.p. we have

$$\left\lfloor \mathbf {x}^\top \cdot [\mathbf {A}\,|\, \mathbf {A} \cdot \mathbf {R}_{\textsf {tag}} ] \right\rfloor _p = \left\lfloor \mathbf {x}^\top \cdot \mathbf {D}^\top \cdot \mathbf {B} \mid (\mathbf {x}^\top \cdot \mathbf {D}^\top \cdot \mathbf {B} ) \cdot \mathbf {R}_{\textsf {tag}} ] \right\rfloor _p $$

when q/p is sufficiently large. Hence, evaluations $\left\{ \left\lfloor \mathbf {x}^\top \cdot [\mathbf {A}\,|\, \mathbf {A}(\textsf {tag}) ] \right\rfloor _p \right\} _{\textsf {tag}\ne \textsf {tag}^*}$ do not reveal any more information than $\mathbf {D} \cdot \mathbf {x} \in \mathbb {Z}_q^{\ell }$. Concerning the relaxation of cumulative lossiness, Chakraborty et al. [19] have the same restriction in their use of the LWE assumption. However, as discussed in [19, Apppendix A], this relaxed notion is not a problem in their applications of CALBO-TDFs.

CALBO-TDFs from DCR. We give a construction of CALBO-TDFs based on the Damgård-Jurik homomorphic encryption scheme [20] with additional insights from [21, 22]. The construction is obtained by composing together multiple instances of the DCR-based lossy trapdoor permutation of Freeman et al. [25], which is index-dependent as its domain depends on the evaluation key. Recall that the Damgård-Jurik cryptosystem uses the group $\mathbb {Z}^*_{N^{\zeta +1}}$, where $N = pq$ is an RSA modulus and $\zeta \ge 1$ is some natural number. Given an injective tag $\textsf {tag}^*\in \{0,1\}^t$, the evaluation key $\textsf {ek}$ of our CALBO-TDFs includes $(N,\zeta )$ and the following Damgård-Jurik ciphertexts

$$\begin{aligned} g_{i,b} = (1+N)^{\delta _{b,\textsf {tag}^*_i}} \cdot \alpha _{i,b}^{N^{\zeta }} \bmod N^{\zeta +1} \qquad \forall (i,b) \in [t] \times \{0,1\}, \end{aligned}$$

where $\alpha _{i,b} \hookleftarrow U( \mathbb {Z}_{N}^*)$ for each $i \in [t]$, $b \in \{0,1\}$, $\delta _{b,\textsf {tag}^*_i} = (b {\mathop {=}\limits ^{ {\tiny ?}}}\textsf {tag}^*_i)$ and $\textsf {tag}^*_{i}$ denotes the i-th bit of $\textsf {tag}^*$. The trapdoor $\textsf {tk}$ consists of the Damgård-Jurik decryption key.

For an evaluation of an input $x\in \mathbb {Z}_{N^{\zeta +1}}$ given a tag $\textsf {tag}$, we first write $x_0 {:}{=}x = y_0\cdot N + z_0$ for $(y_0,z_0) \in \mathbb {Z}_{N^\zeta }\times \mathbb {Z}_N$. Then, we iterate for $i\in [t]$ and, at each iteration, we compute a Damgård-Jurik ciphertext $x_i$ of $y_{i-1}$:

$$\begin{aligned} x_i = g_{i,\textsf {tag}_i}^{y_{i-1}} \cdot z_{i-1}^{N^\zeta } \bmod N^{\zeta +1}. \end{aligned}$$

The output of the function consists of $x_t$.

In the injective mode (where $\textsf {tag}= \textsf {tag}^*$), we have that $g_{i,\textsf {tag}^*_i}$ is an encryption of 1 for each $i\in [t]$. Then, each $x_{i}$ is an encryption of $y_{i-1}$. Using $\textsf {tk}$, the inverter can thus recover $(y_{i-1},z_{i-1})$ from $x_{i}$ and eventually recover $(y_0,z_0)$ and $x=x_0$ as long as $z_{i-1} \in \mathbb {Z}_N^*$ at each iteration. For any input x such that $z_{i-1} \notin \mathbb {Z}_N^*$ at some iteration, the evaluation algorithm outputs 0 (analogously to an index-dependent DCR-based LTDF proposed by Auerbach et al. [3, Sect. 6.1]). We note that our DCR-based construction is not perfectly invertible injective mode, the fraction of inputs for which the function is not invertible is overwhelming. Moreover, finding such inputs is as hard as factoring N and thus contradicts the DCR assumption.

In the lossy mode (where $\textsf {tag}\ne \textsf {tag}^*$), let the smallest index $i \in [t]$ such that $\textsf {tag}_i\ne \textsf {tag}^*$. For this index i, $g_{i,\textsf {tag}_i}$ is a Damgård-Jurik encryption of 0, and so is $x_{i}$ at the i-th evaluation step. This implies that $x_i$ loses information about $y_{i-1}$ as it can take at most $\varphi (N)$ values.

We then observe that injectivity and indistinguishability follow from the correctness and semantic security of Damgård-Jurik. Cumulative lossiness can be argued using the same arguments as in the CALBO function of [23, Sect. 5.3.1]. At each evaluation step, the information $(y_{i-1},z_{i-1}) \in \mathbb {Z}_{N^\zeta } \times \mathbb {Z}_N$ about x is fully carried over to the next step of the evaluation if $\textsf {tag}_i = \textsf {tag}^*_i$ and $z_{i-1} \in \mathbb {Z}_N^*$. As soon as $\textsf {tag}_i$ differs from $\textsf {tag}_i^*$, the information about $y_{i-1}$ is lost and subsequent evaluation steps (and therefore the final output of the evaluation) only depend on at most $\log \varphi (N) < \log N$ bits of x. Since there are t positions where a lossy tag can differ from $\textsf {tag}^*$ for the first time, the function $\{ F_{\mathsf {ek}}( \cdot ,\textsf {tag}) \}_{\textsf {tag}\ne \textsf {tag}^*}$ has image size $\le \varphi (N)^t$. So, the union of all lossy evaluations $\{ F_{\mathsf {ek}}(x,\textsf {tag}) \}_{\textsf {tag}\ne \textsf {tag}^*}$ on some input x reveals at most $\log (\varphi (N)^t) < t \cdot \log N$ bits about x.

1.3 Related Work

Dodis, Vaikuntanathan and Wichs [23, Sect. 5.3.1] considered a notion of cumulatively all-lossy-but-one (CALBO) functions without trapdoor, which they used to extract randomness from extractor-dependent sources. They showed that CALBOs can be generically realized from standard lossy functions by relaxing the injectivity property. Due to their relaxed notion of injectivity, their construction is not invertible in injective mode. Our DCR-based CALBO-TDF is inspired by their construction (which is itself similar to the pseudo-entropy function of Braverman et al. [18]) with the difference that we do not need to compose a standard lossy function with a compressing d-wise independent function at each iterative evaluation step. This is the reason why our injective mode is invertible.

In a recent work, Quach, Waters, and Wichs [49] introduced a new notion of targeted lossy functions (TLFs), where lossy evaluations only lose information on some targeted inputs and no trapdoor allows efficiently inverting in the injective mode. Quach et al. [49] also extended TLFs to targeted all-lossy-but-one (T-ALBOs) and targeted all-injective-but-one (T-AIBOs) variants. Interestingly, it was shown in [49] that, in contrast with lossy trapdoor functions, TLFs, T-ALBOs, and T-AIBOs can be realized in Minicrypt. We can also consider the relaxation of targeted lossiness alone, while still asking for a trapdoor in the injective mode. This notion was discussed in [29] where a construction based on the Computational Diffie-Hellman assumption was given.

Lossy algebraic filters (LAFs) [38, 42] are tag-based lossy functions that were used to construct public-key encryption schemes with circular chosen-ciphertext security [38]. They provide similar functionalities to CALBO in that they explicitly require multiple evaluations $\{ F_{\mathsf {ek}}(x,\textsf {tag}_i) \}_i$ on distinct lossy tags to always leak the same information about x. One difference is that LAFs admit arbitrarily many injective tags and arbitrarily many lossy tags. The requirement is that lossy tags should be hard to find without a trapdoor key. In contrast with CALBO-TDF, LAFs do not support efficient inversion on injective tags.

2 Background

We write [n] to denote the set $\{1, 2, \dots , n\}$ for an integer n. For any $q\ge 2$, we let $\mathbb {Z}_q$ denote the ring of integers with addition and multiplication modulo q, containing the representatives in the interval $(-q/2,\,q/2)$. We always set q as a prime integer. For $2\le p < q$ and $x \in \mathbb {Z}_q$, we define $\lfloor x \rfloor _p {:}{=}\lfloor (p/q) \cdot x \rfloor \in \mathbb {Z}_p$ where the operator $\lfloor y \rfloor$ means taking the largest integer less than or equal to y. This notation is readily extended to vectors over $\mathbb {Z}_q$. Given a distribution D, we write $x \sim D$ to denote a random variable x distributed according to D. For a finite set S, we let U(S) denote the uniform distribution over S. If X and Y are distributions over the same domain $\mathcal {D}$, then $\varDelta (X,Y)$ denotes their statistical distance. We write $\textsf {ppt}$ as a shorthand for “probabilistic polynomial-time” when considering the complexity of algorithms. We use a generalized version of the Leftover Hash Lemma [35].

Lemma 1

([1], Lemma 14). Let $\mathcal {H}= \{h: X \rightarrow Y\}_{h\in \mathcal {H}}$ be a family of universal hash functions. Let $f : X \rightarrow Z$ be some function. Let $T_1,\dots ,T_k$ be k independent random variables over X and we define $\gamma {:}{=}\max _{k}\gamma (T_i)$ where $\gamma (T_i) {:}{=}\max _{t\in X}\Pr [T_i = t]$. Then, we have

$$\begin{aligned} \varDelta \Big ( ~\left( h, h(T_1), f(T_1),\dots , h(T_k), f(T_k)\right) ; \left( h, U^{(1)}_Y, f(T_1),\dots , U^{(k)}_Y, f(T_k)\right) ~\Big ) \\ \qquad \le \frac{k}{2}\sqrt{\gamma \cdot |Y|\cdot |Z|} \end{aligned}$$

where $U^{(1)}_Y,\dots ,U^{(k)}_Y$ denote k uniformly random variables over Y.

2.1 Cumulatively All-Lossy-But-One Trapdoor Functions

We now recall the definition of cumulatively all-lossy-but-one trapdoor functions (CALBO-TDFs), a notion recently introduced in [19, 23] as an extension of lossy trapdoor functions. We also recall its variant with relaxed cumulative lossiness that we achieve assuming LWE. We refer the reader to the introduction for an overview of these notions in the general context of lossy trapdoor functions.

Definition 1 (CALBO-TDF)

Let $\lambda \in \mathbb {N}$ be a security parameter and $\ell , \alpha : \mathbb {N}\rightarrow \mathbb {N}$ be functions. Let $\mathcal {T}= \{\mathcal {T}_\lambda \}_{\lambda \in \mathbb {N}}$ be a family of sets of tags. An $(\ell , \alpha )$-cumulatively-all-lossy-but-one trapdoor function family (CALBO-TDF) with respect to the tag family $\mathcal {T}$ is a triple of algorithms $(\textsf {Sample}, \textsf {Eval}, \textsf {Invert})$, where the first is probabilistic and the latter two are deterministic:

• $\textsf {Sample}(1^\lambda , \textsf {tag}^*)$: on inputs $1^\lambda$ and $\textsf {tag}^* \in \mathcal {T}_\lambda$, sample and output $(\textsf {ek},\, \textsf {tk})$.

• $\textsf {Eval}(\textsf {ek}, \textsf {tag}, x)$: on inputs $x \in \{0,1\}^{\ell (\lambda )}$, an evaluation key $\textsf {ek}$ and $\textsf {tag}$, output an element y in some set $\mathcal {R}$ of images.

• $\textsf {Invert}(\textsf {tk}, \textsf {tag}, y)$: on inputs $y\in \mathcal {R}$, a trapdoor key $\textsf {tk}$, and $\textsf {tag}$, output $x' \in \{0,1\}^{\ell (\lambda )}$.

We require the following properties:

• (Injectivity) There exists a negligible function $\mathsf {negl}: \mathbb {N}\rightarrow \mathbb {N}$ such that for all $\lambda \in \mathbb {N}$, $\textsf {tag}^* \in \mathcal {T}_\lambda$, $(\textsf {ek}, \textsf {tk}) \!\leftarrow \!\textsf {Sample}(1^\lambda , \textsf {tag}^*)$ we have

  $$ \frac{|\{x \in \{0,1\}^{\ell (\lambda )}\,:\,\textsf {Invert}(\textsf {tk}, \textsf {tag}^*, \textsf {Eval}(\textsf {ek}, \textsf {tag}^*, x)) = x\}|}{2^{\ell (\lambda )}} \ge 1 - \mathsf {negl}(\lambda ). $$

• ($\alpha$-cumulative lossiness) For all $\lambda \in \mathbb {N}$, all tags $\textsf {tag}^* \in \mathcal {T}_\lambda$, and all $(\textsf {ek}, \textsf {tk})\!\leftarrow \!\textsf {Sample}(1^\lambda , \textsf {tag}^*)$, there exists a (possibly inefficient) function $\textsf {compress}_{\textsf {ek}}: \{0,1\}^{\ell (\lambda )} \rightarrow \mathcal {R}_{\textsf {ek}}$ where $|\mathcal {R}_{\textsf {ek}}| \le 2^{\ell (\lambda ) - \alpha (\lambda )}$ such that for all $\textsf {tag}\ne \textsf {tag}^*$ and $x\in \{0,1\}^{\ell (\lambda )}$, there exists a (possibly inefficient) function $\textsf {expand}_{\textsf {ek}, \textsf {tag}}: \mathcal {R}_{\textsf {ek}} \rightarrow \mathcal {R}$ satisfying

  $$\begin{aligned} \textsf {Eval}(\textsf {ek}, \textsf {tag}, x) = \textsf {expand}_{\textsf {ek}, \textsf {tag}}(\textsf {compress}_{\textsf {ek}}(x)). \end{aligned}$$

  (2)

• (Indistinguishability) For all $\textsf {tag}^*_0, \textsf {tag}^*_1 \in \mathcal {T}_\lambda$, the two ensembles

  $$\begin{aligned}&\{\textsf {ek}_0:(\textsf {ek}_0, \textsf {tk}_0) \!\leftarrow \!\textsf {Sample}(1^\lambda , \textsf {tag}^*_0)\}_{\lambda \in \mathbb {N}}\\&\{\textsf {ek}_1:(\textsf {ek}_1, \textsf {tk}_1) \!\leftarrow \!\textsf {Sample}(1^\lambda , \textsf {tag}^*_1)\}_{\lambda \in \mathbb {N}} \end{aligned}$$

  are computationally indistinguishable.

An alternative, relaxed notion of CALBO-TDFs was also proposed in [19, 23]. In this relaxed variant, cumulative lossiness is slightly simplified by requiring Equation (2) to only hold with overwhelming probability over the choice of tags. This minor relaxation does not impact applications, as the relaxed notion was proven sufficient for all known applications of CALBO-TDFs in [19, Appendix A]. We use this relaxation in our LWE-based construction in Sect. 3.1, and recall it below. We refer to this notion as relaxed CALBO-TDFs.

• (relaxed $\alpha$-cumulative lossiness) There exists a negligible function $\textsf {negl}:\mathbb {N}\rightarrow (0,1)$ and for sufficiently large $\lambda \in \mathbb {N}$, for any $\textsf {tag}^* \in \mathcal {T}_\lambda$, for all $(\textsf {ek}, \textsf {tk})\!\leftarrow \!\textsf {Sample}(1^\lambda , \textsf {tag}^*)$, there exists a (possibly inefficient) function $\textsf {compress}_{\textsf {ek}}: \{0,1\}^{\ell (\lambda )} \rightarrow \mathcal {R}_{\textsf {ek}}$ where $|\mathcal {R}_{\textsf {ek}}| \le 2^{\ell (\lambda ) - \alpha (\lambda )}$ such that for any fixed randomly chosen $x \in \{0,1\}^{\ell (\lambda )}$, there exists a (possibly inefficient) function $\textsf {expand}_{\textsf {ek}, \textsf {tag}}: \mathcal {R}_{\textsf {ek}} \rightarrow \mathcal {R}$ satisfying

  $$\begin{aligned} \Pr [\textsf {Eval}(\textsf {ek}, \textsf {tag}, x) = \textsf {expand}_{\textsf {ek}, \textsf {tag}}(\textsf {compress}_{\textsf {ek}}(x))] \ge 1 - \textsf {negl}(\lambda ), \end{aligned}$$

  where the probability is taken over the choices of $\textsf {tag}\ne \textsf {tag}^*$. We call $\textsf {negl}(\lambda )$ the lossiness error of the CALBO-TDF.

Lossiness Rate. We define the lossiness rate of an $(\ell , \alpha )$-CALBO-TDF by the rate of bits lost on lossy tags, namely $1 - (\ell - \alpha )/\ell = \alpha /\ell$. This is similar to the notion of lossiness rate used in [29, 48]. Ideally, we want this rate to be as close to 1 as possible, for example $1 - o(1)$.

2.2 Lattices

Unless stated otherwise, we write vectors as column vectors. For a full-row rank matrix $\mathbf {A} \in \mathbb {Z}_q^{n \times m}$, we define the lattice $\varLambda (\mathbf {A})$ admitting $\mathbf {A}$ as a basis by $\varLambda (\mathbf {A}) = \{\mathbf {s}^\top \cdot \mathbf {A} \,:\, \mathbf {s} \in \mathbb {Z}^{n}_q\}$. We also define the lattice $\varLambda ^\perp (\mathbf {A}) = \{\mathbf {x}\in \mathbb {Z}^m: \mathbf {A} \mathbf {x} = \mathbf {0} \bmod q\}$. Given a vector $\mathbf {x} \in \mathbb {Z}^n_q$, we define its $\ell _\infty$-norm as $\Vert \mathbf {x}\Vert _\infty = \max _{i\in [n]} |\mathbf {x}[i]|$ where $\mathbf {x}[i]$ denotes the i-th coordinate of $\mathbf {x}$. We let $\Vert \mathbf {x}\Vert _2 = \sqrt{\mathbf {x}[1]^2 + \dots + \mathbf {x}[n]^2}$ denote the Euclidean norm of $\mathbf {x}$. The minimum distance measured in $\ell _\infty$-norm of a lattice $\varLambda$ is given by $\lambda ^\infty _1(\varLambda ) {:}{=}\min _{\mathbf {x}\ne \mathbf {0}} \Vert \mathbf {x}\Vert _\infty$. For a basis $\mathbf {B}$ of $\mathbb {R}^n$, the origin-centered parallelepiped is defined as $\mathcal {P}_{1/2}(\mathbf {B}) {:}{=}\mathbf {B} \cdot \left[ -1/2,1/2\right) ^n$. We also use the following infinity norm for matrices $\mathbf {B} \in \mathbb {Z}^{n\times m}$:

$$ \Vert \mathbf {B}\Vert _\infty = \max _{i\in [n]} \left( \sum ^m_{j=1} |\mathbf {B}_{i,j}| \right) . $$

Let $\mathbf {\Sigma } \in \mathbb {R}^{n \times n}$ be a symmetric positive definite matrix and $\mathbf {c} \in \mathbb {R}^n$ be a vector. We define the Gaussian function over $\mathbb {R}^n$ by $\rho _{\mathbf {\Sigma },\,\mathbf {c}}(\mathbf {x}) = \exp (-\pi (\mathbf {x} - \mathbf {c})^\top \mathbf {\Sigma }^\text {-1}(\mathbf {x} - \mathbf {c}))$ and if $\mathbf {\Sigma } = \sigma ^2 \cdot \mathbf {I}_n$ and $\mathbf {c} = \mathbf {0}$, we write $\rho _{\sigma }$ for $\rho _{\mathbf {\Sigma },\,\mathbf {c}}$. For any discrete set $\varLambda \subset \mathbb {R}^n$, the discrete Gaussian distribution $D_{\varLambda , \mathbf {\Sigma }, \mathbf {c}}$ has probability mass $\Pr _{X \sim D_{\varLambda , \mathbf {\Sigma }, \mathbf {c}}}[X = \mathbf {x}] = \frac{\rho _{\mathbf {\Sigma },\,\mathbf {c}}(\mathbf {x})}{\rho _{\mathbf {\Sigma },\,\mathbf {c}}(\varLambda )} ,$ for any $\mathbf {x} \in \varLambda$. When $\mathbf {c} = \mathbf {0}$ and $\mathbf {\Sigma } = \sigma ^2 \cdot \mathbf {I}_n$ we denote $D_{\varLambda , \mathbf {\Sigma }, \mathbf {c}}$ by $D_{\varLambda , \sigma }$.

Learning-with-Errors Assumption. Our first CALBO-TDF relies on the $\textsf {LWE}$ assumption.

Definition 2

Let $\alpha : \mathbb {N}\rightarrow (0,1)$ and $m\ge n \ge 1$, $q\ge 2$ be functions of a security parameter $\lambda \in \mathbb {N}$. The Learning with Errors $(\textsf {LWE})$ problem consists in distinguishing between the distributions $(\textbf{A}, \textbf{s}^\top \textbf{A} + \textbf{e}^\top )$ and $U(\mathbb {Z}_q^{n \times m}\times \mathbb {Z}_q^{m})$, where $\textbf{A} \sim U(\mathbb {Z}_q^{n \times m})$, $\textbf{s} \sim U(\mathbb {Z}_q^n)$ and $\textbf{e} \sim D_{\mathbb {Z}^m, \alpha q}$. For an algorithm $\mathcal {A}:\mathbb {Z}_q^{n \times m}\times \mathbb {Z}_q^{m} \rightarrow \{0,1\}$, we define

$$ \mathbf {Adv}_{q,m,n,\alpha }^{\textsf {LWE}}(\mathcal {A}) = \left| \Pr [ \mathcal {A}\left( \textbf{A}, \textbf{s}^\top \textbf{A} + \textbf{e}^\top \right) = 1] - \Pr [ \mathcal {A}\left( \textbf{A}, \textbf{u}\right) =1 \right| , $$

where the probabilities are over $\textbf{A} \sim U(\mathbb {Z}_q^{n \times m})$, $\textbf{s} \sim U(\mathbb {Z}_q^n)$, $\textbf{u} \sim U(\mathbb {Z}_q^m)$ and $\textbf{e} \sim D_{\mathbb {Z}^m, \alpha q}$ and the internal randomness of $\mathcal {A}$. We say that $\textsf {LWE}_{q,m,n,\alpha }$ is hard if for all $\textsf {ppt}$ algorithm $\mathcal {A}$, the advantage $\mathbf {Adv}_{q,m,n,\alpha }^{\textsf {LWE}}(\mathcal {A})$ is negligible in $\lambda$.

We require that $\alpha \ge 2\sqrt{n}/q$ for the reduction from worst-case lattice problems and refer the readers to, e.g., [17] for more details.

We will need the techniques for homomorphic encryption (HE) [31] in order to build CALBO-TDFs from $\textsf {LWE}$. In this paper, we consider only binary circuits with fan-in-2 gates for homomorphic evaluation. We use the terms size and depth of a circuit to refer to the number of its gates and the length of its longest input-to-output path, respectively. We note that in our construction from $\textsf {LWE}$, we do not need the general fully homomorphic encryption thanks to the fact that all evaluated circuits have bounded depths, for the sole purpose of comparing tags. Hence, leveled homomorphic encryption suffices for our purposes.

Gadget Matrix. We recall the “gadget matrix” from [45] and their homomorphic properties. The technique is later developed further in [12, 33, 34]. For an integer modulus q, the gadget vector over $\mathbb {Z}_q$ is defined as $\mathbf {g} = (1, 2, 4, \dots , 2^{\lceil \log q\rceil - 1} ).$ The gadget matrix $\mathbf {G}_n$ is the tensor (or Kronecker) product $\mathbf {I}_n \otimes \mathbf {g} \in \mathbb {Z}^{n \times n'}_q$ where $n' = \lceil n \log q \rceil$. There exists an efficiently computable function $\mathbf {G}^{\text {-1}}_n: \mathbb {Z}^{n \times n'}_q \rightarrow \{0,1\}^{n' \times n'}$ such that $\mathbf {G}_n\cdot \mathbf {G}^{\text {-1}}_n(\mathbf {A}) = \mathbf {A}$ for all $\mathbf {A} \in \mathbb {Z}^{n \times n'}_q$. In particular, we can define $\mathbf {G}^\text {-1}_n$ to be the entry-wise binary decomposition of matrices in $\mathbb {Z}^{n \times n'}_q$. In the following, we omit the subscript n and write $\mathbf {G}$ when it is clear from context. Lemma 2 helps bound the noise of the output ciphertext after homomorphically evaluating a depth-$\tau$ circuit C containing only AND gates. This will affect our parameter choices for the $\textsf {LWE}$-based CALBO-TDFs as well as our later argument for its relaxed cumulative lossiness.

Lemma 2

(Adapted from [12, 16, 31]). Let $\lambda \in \mathbb {N}$ and $m = m(\lambda ),n = n(\lambda )$. We define $n' {:}{=}\lceil n \log q \rceil$. Let $C: \{0,1\}^{t} \rightarrow \{0,1\}$ be a AND Boolean circuit of depth $\tau$. Let $\mathbf {A}_i = {\mathbf {A}} \cdot \mathbf {R}_i + b_i \cdot \mathbf {G} \in \mathbb {Z}_q^{n \times m}$ with ${\mathbf {A}} \in \mathbb {Z}_q^{n \times m}$, $\mathbf {R}_i \in \{-1,1\}^{ m \times n'}$ and $b_i \in \{0,1\}$, for $i\le t$. There exist deterministic algorithms $\mathsf {FHEval}$ and $\mathsf {EvalPriv}$ with running time $\mathsf {poly}(4^\tau ,t, m,n,\log q)$ that satisfy:

$$\mathsf {FHEval}(C,(\mathbf {A}_i)_i) = {\mathbf {A}} \cdot \mathbf {R}_C + C(b_1,\ldots ,b_{t}) \cdot \mathbf {G} = {\mathbf {A}} \cdot \mathbf {R}_C + \bigwedge ^t_{i=1} b_i\cdot \mathbf {G},$$

where $\mathbf {R}_C = \mathsf {EvalPriv} \big (C,((\mathbf {R}_i,b_i))_i \big )$ and $\Vert \mathbf {R}_C \Vert _\infty \le \max _{i}\{\Vert \mathbf {R}_i\Vert _\infty \}\cdot (n'+1)^\tau .$

Lossy mode of $\textsf {LWE}$. We recall the $\textsf {Lossy}$ sampler for $\textsf {LWE}$ that is introduced by Goldwasser et al. in [32] and later developed by Alwen et al. in [2].

Definition 3

Let $\chi = \chi (\lambda )$ be an efficiently sampleable distribution over $\mathbb {Z}$. We define an efficient lossy sampler $(\mathbf {A},\,\mathbf {B}) \!\leftarrow \!\textsf {Lossy}(1^m, 1^n, 1^\ell , q, \chi )$ via:

• $\textsf {Lossy}(1^m, 1^n, 1^\ell , q, \chi )$: Sample $\mathbf {B} \hookleftarrow U(\mathbb {Z}^{\ell \times m}_q), \mathbf {D} \hookleftarrow U(\mathbb {Z}^{\ell \times n}_q), \mathbf {E} \hookleftarrow \chi ^{n \times m}$, where $\ell \ll n$, and output $\mathbf {A} = \mathbf {D}^\top \cdot \mathbf {B} + \mathbf {E} \in \mathbb {Z}^{n \times m}_q$ together with $\mathbf {B}$.

We remark that the lossy sampler reveals the coefficient matrix $\mathbf {B}$ along with $\mathbf {A}$ but as long as the secret matrix $\mathbf {D}$ is not leaked, this does not compromise the pseudorandomness of $\mathbf {A}$. Indeed, it can be shown that under the $\textsf {LWE}_{q, m, \ell , \alpha }$ assumption, $\mathbf {A}$ is computationally indistinguishable from a uniformly random matrix. Intuitively, the dimension of the secret is now $\ell$ and we view each row of $\mathbf {D}^\top$ as a secret vector, $\mathbf {B}$ as the uniform coefficients and each row of $\mathbf {A}$ as the resulting $\textsf {LWE}$ vector. Formally, we have the following lemma:

Lemma 3

([32]). Let a random matrix $\tilde{\mathbf {A}} \hookleftarrow U(\mathbb {Z}^{n \times m}_q)$ and let a pair $(\mathbf {A},\,\mathbf {B}) \!\leftarrow \!\textsf {Lossy}(1^m, 1^n, 1^\ell , q, \chi )$, where $\chi = D_{\mathbb {Z}, \alpha q}$ is an error distribution. Then, under the $\textsf {LWE}_{q, m, \ell , \alpha }$ assumption, the following two distributions are computationally indistinguishable: $\mathbf {A} {\mathop {\approx }\limits ^{comp }} \tilde{\mathbf {A}}$.

Trapdoor Mechanisms for$\textsf {LWE}$. Micciancio and Peikert [45] introduced a trapdoor mechanism for $\textsf {LWE}$. Their technique makes use of the “gadget matrix” $\mathbf {G} \in \mathbb {Z}^{n \times n'}_q$, where $n' = \lceil n\log q \rceil$, and for $\mathbf {A}'\in \mathbb {Z}^{n\times (m + n')}_q$, they call a short matrix $\mathbf {R} \in \mathbb {Z}^{m\times n'}$ a $\mathbf {G}$-trapdoor of $\mathbf {A}'$ if $\mathbf {A}'\cdot [\mathbf {R}^\top \,|\,\mathbf {I}_m]^\top = \mathbf {H}\mathbf {G}$ for some invertible $\mathbf {H} \in \mathbb {Z}^{n\times n}_q$. Micciancio and Peikert also showed that using a $\mathbf {G}$-trapdoor allows one to invert the $\textsf {LWE}$ function $(\mathbf {s},\mathbf {e}) \mapsto \mathbf {s}^\top \mathbf {A}' + \mathbf {e}^\top$ for any $\mathbf {s} \in \mathbb {Z}^n_q$ and any error $\mathbf {e} \in \mathbb {Z}^{m+n'}$ such that $\Vert \mathbf {e}\Vert _2 \le q/O(\sqrt{n\log q})$. More specifically, we have the following lemma:

Lemma 4

([45], Theorem 4.1 and Sect. 5). Let $n' = \lceil n \log q \rceil$ and $\delta = \textsf {negl}(n)$. Assume that $m \ge n\log q + 2\log \frac{n'}{2\delta }$. Then there exists a $\textsf {ppt}$ algorithm $\textsf {GenTrap}$ that takes as inputs matrices $\mathbf {A} \in \mathbb {Z}^{n \times m}_q, \mathbf {H} \in \mathbb {Z}^{n\times n}_q$, outputs a short matrix $\mathbf {R} \in \{-1, 0, 1\}^{m \times n'}$ and $\mathbf {A}' = [\mathbf {A}\,|\,-\mathbf {A}\cdot \mathbf {R} + \mathbf {H}\cdot \mathbf {G}] \in \mathbb {Z}^{n\times (m + n')}_q$ such that if $\mathbf {H}$ is invertible, then $\mathbf {R}$ is a $\mathbf {G}$-trapdoor of $\mathbf {A}'$ and we call $\mathbf {H}$ the invert tag of $\mathbf {A}'$.

In particular, inverting the function $g_{\mathbf {G}}(\mathbf {s}, \mathbf {e}) {:}{=}\mathbf {s}^\top \cdot \mathbf {G} + \mathbf {e}^\top$ can be done in quasi-linear time $O(n\cdot \log ^c n)$ for any $\mathbf {s} \in \mathbb {Z}^n_q$ and any $\mathbf {e} \in \mathcal {P}_{1/2}(q\cdot (\mathbf {B}^\text {-1})^\top )$, where $\mathbf {B}$ is a basis of the lattice $\varLambda ^\perp (\mathbf {G}) = \{\mathbf {z} \in \mathbb {Z}^{n'}\,:\, \mathbf {G}\cdot \mathbf {z} = 0 \text { (mod } q \text {)}\}$.

In a follow-up work, Alwen et al. [2] used $\textsf {GenTrap}$ to construct trapdoors for inverting Learning with Rounding $(\textsf {LWR})$ instances $\left\lfloor \mathbf {s}^\top \mathbf {A} \right\rfloor _p$. Their main observation is that one can convert $\left\lfloor \mathbf {s}^\top \mathbf {A} \right\rfloor _p$ to $\mathbf {s}^\top \mathbf {A} + \mathbf {e}^\top$ where $\Vert \mathbf {e}\Vert _2 \le \sqrt{m}q/p$, by first multiplying with q/p then taking the ceiling value. Afterwards, using a $\mathbf {G}$-trapdoor of $\mathbf {A}$, e.g. a sample from $\textsf {GenTrap}$, allows one to compute back $\mathbf {s}$. Formally, we have the following lemma:

Lemma 5

([2], Lemma 6.3). Let $n' = \lceil n \log q \rceil$ and $\delta = \textsf {negl}(n)$. Assume that $m \ge n\log q + 2\log \frac{n'}{2\delta }$ and $p \ge O(\sqrt{(m+n')n'})$. Then there exists a $\textsf {ppt}$ algorithm $\textsf {LWRInvert}$ that takes as inputs $(\mathbf {A}', \mathbf {R})$ with $\mathbf {R}$ being a $\mathbf {G}$-trapdoor of $\mathbf {A}'$, together with some $\mathbf {c} \in \mathbb {Z}^{m+n'}_p$ such that $\mathbf {c} = \left\lfloor \mathbf {s}^\top \mathbf {A}' \right\rfloor _p$ for some $\mathbf {s} \in \mathbb {Z}^n_q$, then outputs $\mathbf {s}$.

We will also need the following technical lemmas. Lemma 6 comes from a work by Gentry, Peikert, and Vaikuntanathan [30].

Lemma 6

([30], Lemma 5.3). Let $\ell$ and q be positive integers and q be prime. Let $n \ge 2\ell \log q$. Then for all but an at most $q^{-n}$ fraction of $\mathbf {D} \in \mathbb {Z}^{\ell \times n}_q$, we have $\lambda ^{\infty }_1(\varLambda (\mathbf {D})) \ge q/4$, where $\varLambda (\mathbf {D}) = \{\mathbf {s}^\top \mathbf {D}\,:\, \mathbf {s} \in \mathbb {Z}^{\ell }_q\}$ and $\lambda ^{\infty }_1(\varLambda (\mathbf {D}))$ is the minimum distance of $\varLambda (\mathbf {D})$ measured in the $\ell _{\infty }$-norm.

Lemma 7

([2], Lemma 2.7). Let p, q be positive integers and $p < q$. Let $R>0$ be an integer. Then, the probability that there exists $e\in [-R,R]$ such that $\left\lfloor y \right\rfloor _p \ne \left\lfloor y + e \right\rfloor _p$, where $y \hookleftarrow U(\mathbb {Z}_q)$, is at most 2pR/q.

The following lemma is well-known, e.g. a simple proof can be found in [44, Lemma 2.3].

Lemma 8

Let q be a prime a $D_{m,n,q}$ be a distribution over $\mathbb {Z}^{n\times m}_q$ such that $\varDelta (D_{m,n,q}, U(\mathbb {Z}^{n\times m}_q)) \le \epsilon$. Then, let $V_{n,q}$ be any distribution over $\mathbb {Z}^n_q$, we have $\varDelta (V^\top _{n,q}\cdot D_{m,n,q},\, U(\mathbb {Z}^{m}_q)) \le \epsilon + \alpha \cdot \left( 1 - \frac{1}{q^m}\right)$ where $\alpha {:}{=}\Pr [\mathbf {v} \hookleftarrow V_{n,q}\,:\, \mathbf {v} = \mathbf {0}]$.

2.3 Composite Residuosity

Our second construction of CALBO-TDFs relies on Paillier’s composite residuosity assumption.

Definition 4

([20, 47]). Let a composite $N=pq$, for primes p, q, and let an integer $\zeta \ge 1$. The Decision Composite Residuosity ($\zeta$-$\mathsf {DCR}$) problem is to distinguish between the distributions $D_0:=\{z = z_0^{N^\zeta } \bmod N^{\zeta +1} \mid z_0 \hookleftarrow U\left( \mathbb {Z}_N^*\right) \}$ and $D_1 :=\{ z \hookleftarrow U\left( \mathbb {Z}_{N^{\zeta +1}}^*\right) \}.$

For each $\zeta >0$, the $\zeta \text {-}\mathsf {DCR}$ assumption was shown to be equivalent to the original $1\text {-}\mathsf {DCR}$ assumption [20]. Damgård and Jurik [20] initially gave their security proof using a recursive argument (rather than a sequence of hybrid experiments) that loses a factor 2 at each step, thus incurring an apparent security loss $2^\zeta$. However, the semantic security of their scheme under the $1\text {-}\mathsf {DCR}$ assumption for any polynomial $\zeta$ is a well-known result. The proof of Lemma 9 is perhaps folklore but for completeness we will include it in the full version of this paper.

Lemma 9

(Adapted from [20]). Let $\zeta =\mathsf {poly}(\lambda )$. Then $\zeta \text {-}\mathsf {DCR}$ is equivalent to $1\text {-}\mathsf {DCR}$ with a security loss at most $\zeta$.

3 Cumulatively All-Lossy-But-One Trapdoor Functions

We now describe two constructions of CALBO-TDFs from standard assumptions. So far, the only known CALBO-TDFs construction was proposed by Chakraborty et al. [19] and relies on puncturable PRFs, cumulatively-lossy-trapdoor functions (C-LTDFs) and indistinguishability obfuscation (iO). This construction relies on iO to obfuscate a program, which first compares a given input tag with the hardcoded injective tag and outputs the hardcoded injective evaluation key if the comparison goes through. Otherwise, it generates a fresh lossy key. All auxiliary key generations in the program are realized using the algorithms from the underlying C-LTDF. The obfuscated program is described in the evaluation key for the CALBO-TDF. An evaluation on a pair of tag and input proceeds by first calling the obfuscated program on the given tag to get a C-LTDF key, then use the evaluation of the C-LTDF on the received key and the given input. The obfuscated program uses a puncturable PRF, which receives the given tag as input, to generate randomness needed for producing a fresh lossy key. Our constructions are much simpler and require neither CPRFs nor iO. They thus drastically improve the efficiency compared to [19].

We construct CALBO-TDFs from the $\textsf {LWE}$ and $\textsf {DCR}$ assumptions. Our $\textsf {LWE}$-based CALBO-TDFs only achieves the relaxed variant of cumulative lossiness while our $\textsf {DCR}$-based construction achieves the full notion. The fact that we have to relax the cumulative lossiness in the LWE case seems intrinsic due to the noise that appears in the $\textsf {LWE}$ samples. We remark that Chakraborty et al. faced a similar problem when constructing C-LTDFs from $\textsf {LWE}$ as well as when boostrapping C-LTDFs to CALBO-TDFs using iO in [19].

3.1 Relaxed CALBO-TDFs from $\textsf {LWE}$

In this section, we describe our construction of CALBO-TDFs from $\textsf {LWE}$. It is inspired from the PRF from [44], which can be seen as a CALBO-TDFs without inversion. We extend ideas from [44] to achieve inversion via trapdoors.

Let $\lambda$ be a security parameter and let $\ell = \ell (\lambda ), n = n(\lambda ), m = m(\lambda ), q = q(\lambda ), p = p(\lambda ), t = t(\lambda ), \beta = \beta (\lambda )$ be natural numbers and $\chi = \chi (\lambda ) = D_{\mathbb {Z}, \alpha q}$ be an $\textsf {LWE}$ error distribution. We denote $n' = \lceil n \log q\rceil$. The tag space is $\mathcal {T}_\lambda = \{0,1\}^{t}$. Our construction now goes as follows:

• $\mathbf {Sample}(1^\lambda , \textsf {tag}^*)$: Sample $(\mathbf {A},\,\mathbf {B}) \!\leftarrow \!\textsf {Lossy}(1^m, 1^n, 1^\ell , q, \chi )$, then set the evaluation key$\textsf {ek}{:}{=}\left( \mathbf {A} \in \mathbb {Z}^{n \times m}_q,\,\mathbf {B} \in \mathbb {Z}^{\ell \times m}_q,\, \{\mathbf {A}_{i,0}, \mathbf {A}_{i,1}\}^t_{i = 1} \right)$ where

  $$ \mathbf {A}_{i,b} = \mathbf {A} \cdot \mathbf {R}_{i,b} + \delta _{b,\textsf {tag}^*_i} \cdot \mathbf {G} \in \mathbb {Z}^{n \times n'}_q\quad \forall i \in [t],\,b \in \{0,1\}$$

  for $\mathbf {R}_{i,b} \leftarrow U(\{0,1\}^{m \times n'})$, $\textsf {tag}^*_i$ denotes the i-th bit of $\textsf {tag}^*$, and $\delta _{b,\textsf {tag}^*_i} = (b {\mathop {=}\limits ^{ {\tiny ?}}}\textsf {tag}^*_i)$. Afterwards, set the trapdoor key $\textsf {tk}{:}{=}\{ \mathbf {R}_{i,b} \}_{i\in [t],b\in \{0,1\}}$ and output $(\textsf {ek}, \textsf {tk})$.

• $\mathbf {Eval}(\textsf {ek}, \textsf {tag}, \mathbf {x} \in [0,\beta ]^n)$: Let $C_{\textsf {tag}}: \{0,1\}^t \rightarrow \{0,1\}$ be the circuit $C_{\textsf {tag}}(\textsf {tag}') = \prod ^t_{i=1} \delta _{\textsf {tag}_i,\textsf {tag}'_i}$ and $\delta _{\textsf {tag}_i,\textsf {tag}'_i} = 1$ if and only if $\textsf {tag}_i = \textsf {tag}'_i$. Parse the evaluation key $\textsf {ek}= \left( \mathbf {A},\,\mathbf {B}, \{\mathbf {A}_{i,0}, \mathbf {A}_{i,1}\}^t_{i = 1} \right)$ and perform the homomorphic evaluation

  $$\begin{aligned} \mathbf {A}(\textsf {tag})&{:}{=}\textsf {FHEval}\left( C_{\textsf {tag}}, \left( \mathbf {A}_{i,\textsf {tag}_i}\right) ^t_{i = 1}\right) = \mathbf {A} \cdot \mathbf {R}_{\textsf {tag}} + C_{\textsf {tag}}(\textsf {tag}^*) \cdot \mathbf {G} \nonumber \\&= {\left\{ \begin{array}{ll} &{}\mathbf {A} \cdot \mathbf {R}_{\textsf {tag}} + \mathbf {G}\text { if }\textsf {tag}= \textsf {tag}^*\\ &{}\mathbf {A} \cdot \mathbf {R}_{\textsf {tag}}\text { otherwise } \end{array}\right. }\in \mathbb {Z}^{n\times n'}_q \end{aligned}$$

  (3)

  where the procedure $\textsf {FHEval}$ is specified by:

  $$\begin{aligned} \textsf {FHEval}\left( C_{\textsf {tag}}, \left( \mathbf {A}_{i,\textsf {tag}_i}\right) ^t_{i = 1}\right) {:}{=}\mathbf {A}_{1,\textsf {tag}_1} \cdot \mathbf {G}^{\text {-1}} \left( \mathbf {A}_{2,\textsf {tag}_2} \cdot \mathbf {G}^\text {-1}\left( \cdots \mathbf {G}^\text {-1}(\mathbf {A}_{t, \textsf {tag}_t}) \cdots \right) \right) \end{aligned}$$

  and $\mathbf {R}_{\textsf {tag}} \in \mathbb {Z}^{m\times n'}$. Finally, compute and output $\left\lfloor \mathbf {x}^\top \cdot [\mathbf {A}\,|\,\mathbf {A}(\textsf {tag})] \right\rfloor _p .$

• $\mathbf {Invert}(\textsf {tk}, \textsf {tag}^*, \mathbf {y} \in \mathbb {Z}^{m + n'}_p)$: Parse the trapdoor key $\textsf {tk}= \{ \mathbf {R}_{i,b} \}_{i\in [t],b\in \{0,1\}}$ then compute $\textsf {FHEval}\left( C_{\textsf {tag}^*}, \left( \mathbf {A}_{i,\textsf {tag}^*_i}\right) ^t_{i = 1}\right) = \mathbf {A} \cdot \mathbf {R}_{\textsf {tag}^*} + \mathbf {G},$ and following Lemma 2, obtain $\mathsf {EvalPriv} \big (C_{\textsf {tag}^*},((\mathbf {R}_{i,\textsf {tag}^*_i},\textsf {tag}^*_i))_{i\in [t]} \big ) = \mathbf {R}_{\textsf {tag}^*}.$ Afterwards, compute $\mathbf {x} \!\leftarrow \!\textsf {LWRInvert}([\mathbf {A}\,|\,\mathbf {A} \cdot \mathbf {R}_{\textsf {tag}^*} + \mathbf {G}], -\mathbf {R}_{\textsf {tag}^*}, \mathbf {y})$ as per Lemma 5 and output $\mathbf {x}$.

The way we carry out the homomorphic computation $\textsf {FHEval}$ involved in equation (3) is not unique. Roughly speaking, at each step of the homomorphic evaluation of $C_\textsf {tag}$, we “decompose” the result from the previous step using $\mathbf {G}^\text {-1}$ (the decomposed entries become binary) before multiplying so as to obtain a ciphertext for the AND gate’s output. This gives the smallest possible increase in the error term of the resulting homomorphic ciphertext, following Lemma 2. Different approaches for computing $\textsf {FHEval}$ will lead to different error increases. Indeed, we homomorphically evaluate the circuit $C_\textsf {tag}$ in the most possible “sequential” way, which is inspired by [5], and always multiply ciphertexts whose noise terms are not too large. A less sequential computation will work, but at the cost of a larger modulus, which then becomes exponential not only in the security paramter but also in the depth of $C_\textsf {tag}$.

Parameter Selection. Let $\lambda$ be the security parameter. First of all, we set the bound $\beta = 1$ for the entries of inputs, which gives a domain $\{0,1\}^n$. We set the tag length $t = \log \lambda$, which means the circuits to be homomorphically evaluated have depths bounded by $t - 1 \le \log \lambda$. By Lemma 6, we must choose $\ell$ such that $n \ge 2\ell \log q$. In addition, for the trapdoor mechanism to work, Lemma 5 requires that $m \ge n\log q + 2\log \frac{n'}{2\delta }$ and $p \ge O(\sqrt{(m+n')n'})$, where $n' = \lceil n\log q\rceil$ and $\delta = \textsf {negl}(n)$.

We will need $m \ge n\log q + \omega (\log n)$ in order to apply Lemma 3. Moreover, for the $\textsf {LWE}_{q, m, n-1, \alpha }$ problem to be hard, it is necessary that $q \le 2^{n^\epsilon } < 2^n$ and $2\sqrt{n}/q \le \alpha \le n \cdot 2^{-n^\epsilon }$, for some $0< \epsilon < 1$. We refer to [17, Corollary 3.2] for more details on these bounds for q and $\alpha$. Similarly, we also need to ensure that the $\textsf {LWE}_{q,m,\ell , \alpha }$ problem is hard. Last but not least, we need $q/p > 2^\lambda$ for the rounding operation to anihilate the noise term, following Lemma 7. Concretely, let $0< \epsilon < 1$ be a constant and $d\ge 1$, we set up the parameters as follows:

$$\begin{aligned}&n = \varTheta (\lambda ^d);~~n' = n \log q = \varTheta \left( \lambda ^{d + d\epsilon }\right) ;&\beta = 1;~~t = \log \lambda ; ~~q = 2^{n^\epsilon } = \varTheta \left( 2^{\lambda ^{d\epsilon }}\right) ; \\&\alpha = n\cdot 2^{-n^{\epsilon }} = \varTheta \left( \lambda ^d\cdot 2^{-\lambda ^{d\epsilon }}\right) ;&m =2\lambda + \lceil n\log q \rceil = \varTheta \left( \lambda ^{d+d\epsilon }\right) ; \\&\ell = \frac{n}{2\log q} = \varTheta \left( \lambda ^{d - d\epsilon }\right) ;&p = \varTheta \left( \sqrt{(m+n')n'}\right) = \varTheta \left( \lambda ^{d+d\epsilon }\right) . \end{aligned}$$

Theorem 1

Let $\lambda \in \mathbb {N}$ be a security parameter. Under the $\textsf {LWE}_{q, m, \ell , \alpha }$ and $\textsf {LWE}_{q, m, n-1, \alpha }$ assumptions, the above construction $(\textsf {Sample}, \textsf {Eval}, \textsf {Invert})$ is a relaxed $(n, n - \ell \log q)$-cumulatively-all-lossy-but-one trapdoor function family with tag space $\mathcal {T}_t = \{0,1\}^t$.

Proof

We now prove each of the required properties.

Injectivity. The correctness of $\textsf {FHEval}$ and $\mathsf {EvalPriv}$ in $\textsf {Invert}$ follows Lemma 2. It is straightforward to see that $-\mathbf {R}_{\textsf {tag}^*}$ is a $\mathbf {G}$-trapdoor for the matrix $\mathbf {A}' {:}{=}[\mathbf {A}\,|\,\mathbf {A} \cdot \mathbf {R}_{\textsf {tag}^*} + \mathbf {G}]$. Hence, given as inputs $\mathbf {y} = \textsf {Eval}(\textsf {ek}, \textsf {tag}^*, \mathbf {x}) = \left\lfloor \mathbf {x}^\top \cdot \mathbf {A}' \right\rfloor _p$ and the pair $(\mathbf {A}', -\mathbf {R}_{\textsf {tag}^*})$, the algorithm $\textsf {LWRInvert}$ will be able to compute back $\mathbf {x}$ as per Lemma 5.

Indistinguishability. Let $\textsf {tag}^*_0, \textsf {tag}^*_1 \in \{0,1\}^t$ and $(\textsf {ek}_b, \textsf {tk}_b)\!\leftarrow \!\textsf {Sample}(1^\lambda , \textsf {tag}^*_b)$ for $b\in \{0,1\}$. We want to prove that $\textsf {ek}_0$ and $\textsf {ek}_1$ are indistinguishable. Let $b\in \{0,1\}$. The evaluation key $\textsf {ek}_b$ is parsed as

$$\begin{aligned} \textsf {ek}_b&= \left( \mathbf {A}^{(b)} \in \mathbb {Z}^{n \times m}_q,\,\mathbf {B}^{(b)} \in \mathbb {Z}^{\ell \times m}_q,\, \{\mathbf {A}^{(b)}_{i,0}, \mathbf {A}^{(b)}_{i,1}\}^t_{i = 1} \right) \end{aligned}$$

where $(\mathbf {A}^{(b)}, \mathbf {B}^{(b)}) \!\leftarrow \!\textsf {Lossy}(1^m, 1^n, 1^\ell , q, \chi )$ and $\mathbf {B}^{(b)} \sim U(\mathbb {Z}^{\ell \times m}_q)$, $\mathbf {A}^{(b)}_{i,b'}$ are encryptions of $\delta _{b', \textsf {tag}^*_{b,i}}\in \{0,1\}$ for $i\in [t]$ and $\textsf {tag}^*_{b,i}$ is the i-th bit of $\textsf {tag}^*_b$, respectively. Similarly to the proof of semantic security for the GSW encryption scheme [31], we first notice that $\mathbf {A}^{(b)}$ is indistinguishable from a uniformly random matrix $\tilde{\mathbf {A}}^{(b)}$ in $\mathbb {Z}^{n \times m}_q$ thanks to Lemma 3 and the parameter choice $m \ge n\log q + 2\lambda$. Hence, changing $\mathbf {A}^{(b)}$ to $\tilde{\mathbf {A}}^{(b)}$ is computationally indistinguishable under $\textsf {LWE}$.

We then apply Lemma 1 for the family of universal hash functions $\mathcal {H}= \{h_{\mathbf {A}}: \mathbb {Z}^n_q\rightarrow \mathbb {Z}^m_q\}$ where $h_\mathbf {A}(\mathbf {x}) {:}{=}\mathbf {x}^\top \cdot \mathbf {A}$ is indexed by $\mathbf {A} \in \mathbb {Z}^{n\times m}_q$ and q is prime. Therefore, it holds that $\Big (\tilde{\mathbf {A}}^{(b)}\mathbf {R}^{(b)}_{i,\textsf {tag}^*_{b,i}}\Big )_{i\in [t]}$ is statistically close to a t-tuple of independent uniformly random matrices. As a result, for all i, the pair $(\tilde{\mathbf {A}}^{(b)}_{i,0}, \tilde{\mathbf {A}}^{(b)}_{i,1})$, where $\tilde{\mathbf {A}}^{(b)}_{i,b'} {:}{=}\tilde{\mathbf {A}}^{(b)}\mathbf {R}^{(b)}_{i,\textsf {tag}^*_{b,i}} + \delta _{b',\textsf {tag}^*_{b,i}}\cdot \mathbf {G}\text { for } b'\in \{0,1\}$, is statistically close to a pair of uniformly random matrices. In the end, for $b \in \{0,1\}$, $\textsf {ek}_b$ is computationally indistinguishable from $\tilde{\textsf {ek}}_b$ whose components are sampled uniformly at random in the corresponding domain and the indistinguishability is concluded.

Relaxed Cumulative Lossiness. Let $\textsf {tag}^* \in \mathcal {T}_t$, $(\textsf {ek}, \textsf {tk}) \!\leftarrow \!\textsf {Sample}(1^\lambda , \textsf {tag}^*)$, and fix an input $\mathbf {x} \in [0,\beta ]^n = \{0,1\}^n$ by the parameter choice $\beta = 1$. For every $\textsf {tag}\in \mathcal {T}_t$ such that $\textsf {tag}\ne \textsf {tag}^*$, we need to describe two functions $\textsf {compress}_{\textsf {ek}}$ and $\textsf {expand}_{\textsf {ek}, \textsf {tag}}$ such that$\textsf {Eval}(\textsf {ek}, \textsf {tag}, \mathbf {x}) = \textsf {expand}_{\textsf {ek}, \textsf {tag}}(\textsf {compress}_{\textsf {ek}}(\mathbf {x}))$ except for a negligible probability over the choices of $\textsf {tag}\ne \textsf {tag}^*$.

The function $\textsf {compress}_{\textsf {ek}}(\mathbf {x} \in \{0,1\}^n)$ is described as follows:

• 1. Parse $\textsf {ek}$ as $\textsf {ek}{:}{=}\left( \mathbf {A},\,\mathbf {B},\, \{\mathbf {A}_{i,0}, \mathbf {A}_{i,1}\}^t_{i = 1} \right)$ then use $\mathbf {A} \in \mathbb {Z}^{n\times m}_q$ and $\mathbf {B} \in \mathbb {Z}^{\ell \times m}_q$ to recover (inefficiently) $\mathbf {D}\in \mathbb {Z}^{\ell \times n}_q$ and $\mathbf {E} \in \mathbb {Z}^{n \times m}$. This is essentially inverting an $\textsf {LWE}$ function $(\mathbf {D} ,\mathbf {E}) \rightarrow \mathbf {D}^\top \mathbf {B} + \mathbf {E}$ for the matrix $\mathbf {B}$.

• 2. Compute and output $\mathbf {D}\cdot \mathbf {x} \in \mathbb {Z}^{\ell }_q$.

Let $\mathbf {y} \in \mathbb {Z}^\ell _q$ and $\textsf {tag}\in \mathcal {T}_t$ such that $\textsf {tag}\ne \textsf {tag}^*$. The function $\textsf {expand}_{\textsf {ek}, \textsf {tag}}(\mathbf {y})$ is described as follows:

• 1. Parse the $\textsf {ek}$ as $\textsf {ek}{:}{=}\left( \mathbf {A},\,\mathbf {B},\, \{\mathbf {A}_{i,0}, \mathbf {A}_{i,1}\}^t_{i = 1} \right)$ then use $(\mathbf {A}, \mathbf {B})$ to (inefficiently) recover $\mathbf {D}\in \mathbb {Z}^{\ell \times n}_q$ and $\mathbf {E} \in \mathbb {Z}^{n \times m}_q$. Using $\mathbf {A}$ and $\{\mathbf {A}_{i,0}, \mathbf {A}_{i,1}\}^t_{i = 1}$, compute $\mathbf {A}(\textsf {tag})$ as in the $\textsf {Eval}$ algorithm, i.e.

  $$\begin{aligned} \mathbf {A}(\textsf {tag}) {:}{=}\textsf {FHEval}\left( C_{\textsf {tag}}, \left( \mathbf {A}_{i,\textsf {tag}_i}\right) ^t_{i = 1}\right)&= \mathbf {A} \cdot \mathbf {R}_{\textsf {tag}} + C_{\textsf {tag}}(\textsf {tag}^*) \cdot \mathbf {G} \\&{\mathop {=}\limits ^{(*)}} \mathbf {A} \cdot \mathbf {R}_{\textsf {tag}} \in \mathbb {Z}^{n \times n'}_q \end{aligned}$$

  where the $(*)$ equality comes from the fact that $\textsf {tag}\ne \textsf {tag}^*$. We will denote $\mathbf {A}' {:}{=}[\mathbf {A}\mid \mathbf {A}(\textsf {tag})] = [\mathbf {A}\,|\, \left( \mathbf {D}^\top \cdot \mathbf {B} + \mathbf {E} \right) \cdot \mathbf {R}_{\textsf {tag}}] \in \mathbb {Z}^{n \times (m+n')}_q .$

• 2. Compute (inefficiently) a matrix $\mathbf {F} \in \mathbb {Z}^{\ell \times n'}_q$ such that $\mathbf {F}$ is an $\textsf {LWE}$ secret for $(\mathbf {D}, \mathbf {A}(\textsf {tag}))$. Specifically, the matrix $\mathbf {F}$ statisfies that $\mathbf {A}(\textsf {tag}) = \mathbf {D}^\top \cdot \mathbf {F} + \mathbf {E}_\textsf {tag}$ where $\mathbf {E}_\textsf {tag}\in \mathbb {Z}^{n\times n'}$ has bounded entries. The bound will be analyzed below.

• 3. Compute (inefficiently) an arbitrary but small matrix $\mathbf {R}' \in \mathbb {Z}^{m \times n'}$ such that $\mathbf {B} \cdot \mathbf {R}' = \mathbf {F}$.

• 4. Compute and return $\left\lfloor [\mathbf {y}^\top \cdot \mathbf {B}\,|\, \mathbf {y}^\top \cdot \mathbf {F}] \right\rfloor _p \in \mathbb {Z}^{m + n'}_p$.

Given a fixed input $\mathbf {x} \in \{0,1\}^n$, for $\textsf {tag}\in \mathcal {T}_t$ and $\textsf {tag}\ne \textsf {tag}^*$, we consider

$$\begin{aligned} \textsf {expand}_{\textsf {ek}, \textsf {tag}}(\textsf {compress}_{\textsf {ek}}(\mathbf {x})) = \textsf {expand}_{\textsf {ek}, \textsf {tag}}(\mathbf {D} \cdot \mathbf {x}) = \left\lfloor [(\mathbf {D} \mathbf {x})^\top \cdot \mathbf {B}| (\mathbf {D} \mathbf {x})^\top \cdot \mathbf {B} \mathbf {R}'] \right\rfloor _p \end{aligned}$$

where $\mathbf {B}, \mathbf {D}, \mathbf {R}', \mathbf {F}$ are computed as specified in $\textsf {compress}_{\textsf {ek}}$ and $\textsf {expand}_{\textsf {ek}, \textsf {tag}}$.

To begin with, we analyze the bound of the entries in the error matrix $\mathbf {E}_\textsf {tag}$ so that the matrix $\mathbf {F}$ computed in step 2 of $\textsf {expand}_{\textsf {ek},\textsf {tag}}$ is uniquely determined. It suffices to bound the infinity norm of $\mathbf {E}\cdot \mathbf {R}_\textsf {tag}$. We evaluate homomorphically the ciphertexts $\mathbf {A}_{i, b}$ on a circuit $C_\textsf {tag}$ defined as a sequential AND-ing of t bits in $\textsf {tag}$ and has depth $t-1$. Moreover, the matrices $\mathbf {A}_{i, b}$ are obtained using binary $\mathbf {R}_i \in \{0,1\}^{m\times n'}$, for all $i \in [t]$ and $b \in \{0,1\}$. As a corollary of Lemma 2, we have $\Vert \mathbf {R}_{\textsf {tag}}\Vert _\infty \le n'(n' + 1)^t$. With $\mathbf {E} \in \mathbb {Z}^{n \times m}_q$, we also have $\Vert \mathbf {E}\Vert _\infty = \max _{i \in [n]}\left( \sum ^{m}_{j=1}|\mathbf {E}_{i,j}|\right) \le m\alpha q.$ This implies that $\Vert \mathbf {E}\cdot \mathbf {R}_\textsf {tag}\Vert _\infty \le \Vert \mathbf {E}\Vert _\infty \cdot \Vert \mathbf {R}_{\textsf {tag}}\Vert _\infty \le n'(n' + 1)^t\cdot m \cdot \alpha q.$ We choose the parameters for $n'(n' + 1)^t\cdot m \cdot \alpha q$ to be small enough, for example smaller than q/4 given a sufficiently large $\lambda$. Thus $\left( \mathbf {D}^\top \cdot \mathbf {B} + \mathbf {E} \right) \cdot \mathbf {R}_{\textsf {tag}}$ uniquely determines $\mathbf {B}\cdot \mathbf {R}_\textsf {tag}$ as a corollary of Lemma 6. Consequently, the (inefficient) step 2 of $\textsf {expand}_{\textsf {ek}, \textsf {tag}}$ will be able to find the unique $\mathbf {F} = \mathbf {B} \cdot \mathbf {R}_{\textsf {tag}}.$ Then, we have $\mathbf {B} \cdot \mathbf {R}' = \mathbf {B} \cdot \mathbf {R}_{\textsf {tag}}$ and $\left\lfloor [(\mathbf {D} \mathbf {x})^\top \cdot \mathbf {B}\,|\, (\mathbf {D} \mathbf {x})^\top \cdot \mathbf {B} \cdot \mathbf {R}'] \right\rfloor _p = \left\lfloor [(\mathbf {D} \mathbf {x})^\top \cdot \mathbf {B}\,|\, (\mathbf {D} \mathbf {x})^\top \cdot \mathbf {B} \cdot \mathbf {R}_{\textsf {tag}}] \right\rfloor _p.$ Let us define an event $\textsf {BAD}$ as

$$\begin{aligned}&\left\lfloor [(\mathbf {D} \mathbf {x})^\top \cdot \mathbf {B}\,|\, (\mathbf {D} \mathbf {x})^\top \cdot \mathbf {B} \cdot \mathbf {R}_{\textsf {tag}}] \right\rfloor _p \\&\qquad \ne \left\lfloor [(\mathbf {D} \mathbf {x})^\top \cdot \mathbf {B} + \mathbf {x}^\top \mathbf {E}\,|\, (\mathbf {D} \mathbf {x})^\top \cdot \mathbf {B} \cdot \mathbf {R}_{\textsf {tag}} + \mathbf {x}^\top \cdot \mathbf {E} \cdot \mathbf {R}_{\textsf {tag}}] \right\rfloor _p \end{aligned}$$

and we observe that the right-hand side is actually $\textsf {Eval}(\textsf {ek}, \textsf {tag}, \mathbf {x})$. A simple computation gives us $\Pr [\textsf {Eval}(\textsf {ek}, \textsf {tag}, \mathbf {x}) = \textsf {expand}_{\textsf {ek}, \textsf {tag}}(\textsf {compress}_{\textsf {ek}}(\mathbf {x}))] \ge 1 - \Pr [\textsf {BAD}]$ where the probabilities are taken over the choices of $\textsf {tag}\in \mathcal {T}_t$ such that $\textsf {tag}\ne \textsf {tag}^*$, for the fixed input $\mathbf {x} \in \{0,1\}^n$. The following lemma proves that $\Pr [\textsf {BAD}]$ is negligible under current parameter and completes the proof.

Lemma 10

We have the following bound:

$$\Pr [\textsf {BAD}]\le 2^{t+1}\cdot p\cdot m\alpha \cdot \left( 1 + n'(n' + 1)^t\right) .$$

A proof for Lemma 10 can be found in the full version of this paper.    $\square$

3.2 CALBO-TDFs from $\textsf {DCR}$

In this section we give a construction of CALBO-TDF achieving non-relaxed cumulative lossiness from the $\textsf {DCR}$ assumption. We start by recalling the Damgård-Jurik encryption scheme, whose decryption algorithm along with other useful properties are used in our CALBO-TDFs.

Damgå rd-Jurik Encryption. Damgård and Jurik introduced in [20] a generalization of Paillier’s cryptosystem based on the $\zeta \text {-}\textsf {DCR}$ assumption. Given a modulus $N = pq$ such that $\gcd (N, \varphi (N)) = 1$, where p and q are primes, Damgård and Jurik proved that the multiplicative group $\mathbb {Z}^*_{N^{\zeta +1}}$ is isomorphic to the direct product of $\mathbb {Z}_{N^\zeta }$ and $\mathbb {Z}^*_N$:

Theorem 2

([20], Theorem 1). For any N satisfying $\gcd (N, \varphi (N)) = 1$ and for $\zeta < \min (p, q)$, the map $\psi _\zeta : \mathbb {Z}_{N^\zeta } \times \mathbb {Z}^*_N \rightarrow \mathbb {Z}^*_{N^{\zeta +1}}$ given by $(m, r) \mapsto (1 + N)^m r^{N^\zeta } \text { (mod } N^{\zeta +1} \text {)}$ is invertible in polynomial time using $\mathrm {lcm}(p-1, q-1)$.

The Damgård-Jurik encryption exploits this isomorphic property: a public key is a pair $(N,\zeta )$ associated with secret key (p, q) and $\psi _\zeta$ is the encryption function (where r plays the role of randomness), that can be inverted (decryption) given (p, q). Semantic security is easily proven under the $\zeta \text {-}\textsf {DCR}$ assumption [20, Theorem 2]. We are now ready to describe our construction of CALBO-TDFs from the $\zeta \text {-}\textsf {DCR}$ assumption. We remark that the domain is currently index-dependent, i.e. inputs are taken in $\mathbb {Z}^*_{N^{\zeta +1}}$ where N and $\zeta$ are specified in the evaluation key. The domain can be made index-independent by using $\{0,1\}^n$ for some bitlength n in the same way Freeman et al. have done in [25], e.g. we can choose any $n \in \mathbb {N}$ such that $n < \min (\log p, \log q)$.

• $\mathbf {Sample}(1^\lambda ,\textsf {tag}^*)$: Given $\textsf {tag}^*\in \mathcal {T}_t=\{0,1\}^t$, generate an evaluation key $\mathsf {ek} := \left( N, ~\zeta , ~ \{ g_{i,0}, g_{i,1} ~\in \mathbb {Z}_{N^{\zeta +1}}^*~ \}_{i=1}^t \right) ,$ consisting of the following components:

  • A modulus $N=pq$ such that $p,q > 2^{l(\lambda )}$ and $\gcd (N, \varphi (N)) = 1$, where $l : \mathbb {N} \rightarrow \mathbb {N}$ is a polynomial dictating the bitlength of p and q as a function of $\lambda$, and an integer $\zeta >t$.

  • Elements $g_{i,0} ,g_{i,1} \in \mathbb {Z}_{N^{\zeta +1}}^*$ which are generated as

    $$ g_{i,b} = (1+N)^{\delta _{b,\textsf {tag}^*_i}} \cdot \alpha _{i,b}^{N^{\zeta }} \bmod N^{\zeta +1} \qquad \qquad \forall (i,b) \in [t] \times \{0,1\}, $$

    where $\alpha _{i,b} \hookleftarrow U( \mathbb {Z}_{N}^*)$ for each $i \in [t]$, $b \in \{0,1\}$, $\textsf {tag}^*_{i}$ denotes the i-th bit of $\textsf {tag}^*$, and $\delta _{b,\textsf {tag}^*_i} = (b {\mathop {=}\limits ^{ {\tiny ?}}}\textsf {tag}^*_i)$. We note that $g_{i,b}$ is a Damgård-Jurik ciphertext of $\delta _{b,\textsf {tag}^*_i}$.

  Output $\mathsf {ek}$ and $\mathsf {tk}=(p,q)$.

• $\mathbf {Eval}(\mathsf {ek},\textsf {tag},x)$: Given an input ${x} \in \mathbb {Z}_{N^{\zeta +1}}$ and $\textsf {tag}\in \mathcal {T}_t=\{0,1\}^t$, let $x_0=x$. Find $(y_0,z_0)\in \mathbb {Z}_{N^\zeta } \times \mathbb {Z}_N$ such that $x_0 = y_0\cdot N + z_0$. If $\gcd (z_0,N) > 1$, output 0. Otherwise, for $i=1$ to t, do the following:

  • 1. Parse $x_{i-1} \in \mathbb {Z}_{N^{\zeta +1}}$ as a pair of integers $(y_{i-1},z_{i-1}) \in \mathbb {Z}_{N^\zeta } \times \mathbb {Z}^*_N$ such that $x_{i-1} = y_{i-1} \cdot N + z_{i-1}$.

  • 2. Compute $x_i = g_{i,\textsf {tag}_i}^{y_{i-1}} \cdot z_{i-1}^{N^\zeta } \bmod N^{\zeta +1}$.

  In the end, output $z=x_t \in \mathbb {Z}_{N^{\zeta +1}}^*$.

• $\mathbf {Invert}(\mathsf {tk},\textsf {tag},z)$: Set $x_t = z$ and find $(y_t,z_t)\in \mathbb {Z}_{N^\zeta } \times \mathbb {Z}_N$ such that $x_t = y_t\cdot N + z_t$. If $\gcd (z_t,N) > 1$, output 0. Otherwise, for $i= t$ down to $i=1$, conduct the following steps:

  • 1. Using $\mathsf {tk}=(p,q)$, compute the unique pair $(y_{i-1},z_{i-1}) \in \mathbb {Z}_{N^\zeta } \times \mathbb {Z}_N^*$ such that $x_i = g_{i,\textsf {tag}_i}^{y_{i-1}} \cdot z_{i-1}^{N^\zeta } \bmod N^{\zeta +1}.$ This is done by first recovering $y_{i-1}=\textsf {Dec}((p,q),x_i) \in \mathbb {Z}_{N^\zeta }$ using the Damgård-Jurik decryption algorithm for obtaining $z_{i-1} = \big (x_i \cdot g_{i,\textsf {tag}_i}^{-y_{i-1}} \bmod N^{\zeta +1} \big )^{N^{-\zeta }} \bmod N .$ Note that $z_{i-1} \in \mathbb {Z}^*_N$ is well-defined thanks to the isomorphism $\psi ^\text {-1}_\zeta$ used in Damgård-Jurik decryption.

  • 2. Let $x_{i-1} = y_{i-1} \cdot N + z_{i-1}$. Output $x_0$ when $i=1$.

The check $\gcd (z_0,N) = 1$ in $\mathbf {Eval}$ implies that, as long as factoring is hard, it is infeasible to find non-invertible inputs, i.e. $x = y_0\cdot N + z_0\in \mathbb {Z}_{N^\zeta +1}$ such that $\gcd (z_0,N) > 1$ for $(y_0,z_0)\in \mathbb {Z}_{N^\zeta } \times \mathbb {Z}_N$. Moreover, the fraction of non-invertible inputs is bounded by $N^\zeta \cdot (p+q)/N^{\zeta +1} = (p+q)/{N}$, which is negligible. We now prove that the above construction is a CALBO-TDF assuming $\zeta \text {-}\textsf {DCR}$ holds.

Theorem 3

Let $\lambda \in \mathbb {N}$ is a security parameter. Let $\zeta = \zeta (\lambda ), l = l(\lambda ), t = t(\lambda )$ be functions in $\lambda$ such that $\zeta > t$. Assuming the $\zeta \text {-}\textsf {DCR}$ assumption, the triplet $(\textsf {Sample}, \textsf {Eval}, \textsf {Invert})$ is a $((\zeta +1)\log N,(\zeta +1)\log N - t\log N - 1)$-cumulatively-all-lossy-but-one trapdoor function family with tag space $\mathcal {T}_t = \{0,1\}^t$.

Proof

We prove injectivity, indistinguishability and cumulative lossiness properties as defined in Sect. 2.1. Let $\lambda \in \mathbb {N}$ be a security parameter and $\zeta = \zeta (\lambda ), l = l(\lambda ), t = t(\lambda )$ be polynomials in $\lambda$ such that $\zeta > t$. Let $\textsf {tag}^* \in \mathcal {T}_t$ be the injective tag and $(\textsf {ek}, \textsf {tk}) \!\leftarrow \!\textsf {Sample}(1^\lambda , \textsf {tag}^*)$.

We first justify why we only need to check $\gcd (z_0,N) = 1$ and can be sure that if it holds, $\gcd (z_i,N) = 1$ for all $i \ge 1$. Indeed, let $i \in [t]$. By construction $x_i = y_i\cdot N + z_i$ for $(y_i,z_i)\in \mathbb {Z}_{N^\zeta }\times \mathbb {Z}_N$. Suppose $z_0\in \mathbb {Z}^*_N$, we verify the claim by induction. Indeed $x_1 = \psi _\zeta (y_0,z_0)\in \mathbb {Z}^*_{N^{\zeta +1}}$. Hence $\gcd (z_1,N) = \gcd (z_1 + y_1\cdot N,N) = \gcd (x_1,N) = 1$. For the inductive step, suppose $z_{i-1}\in \mathbb {Z}^*_N$, then $x_i = \psi _\zeta (y_{i-1},z_{i-1})\in \mathbb {Z}^*_{N^{\zeta +1}}$. By the same argument, we have $\gcd (z_i,N) = \gcd (z_i + y_i\cdot N, N) = \gcd (x_i, N) = 1$.

Injectivity. Let $\textsf {tag}^*\in \{0,1\}^t$ be an injective tag. We consider two cases for invertibility of $\textsf {Eval}(\textsf {ek}, \textsf {tag}^*, x)$ given the trapdoor $\textsf {tk}$ of $\textsf {tag}^*$. If $x\in \mathbb {Z}_{N^{\zeta +1}} \setminus \mathbb {Z}^*_{N^{\zeta +1}}$, equivalently by Theorem 2 it holds that $x = y_0\cdot N + z_0$ and $\gcd (z_0,N)> 1$, then $\textsf {Eval}(\textsf {ek}, \textsf {tag}^*, x) = 0$ by construction and cannot be inverted using $\textsf {tk}$. The fraction of such inputs in $\mathbb {Z}_{N^{\zeta +1}}$ is ${N^\zeta \cdot (N - \varphi (N))}/{N^{\zeta +1}} = {(p+q-1)}/{N},$ which is negligible in $\lambda$.

Otherwise, suppose that $x\in \mathbb {Z}^*_{N^{\zeta +1}}$. By the correctness of Damgård-Jurik decryption algorithm and Theorem 2, for each $i=t$ down to 1, step 1 in $\textsf {Invert}$ correctly recovers $y_{i-1}\in \mathbb {Z}_{N^\zeta }$ and $z_{i-1}\in \mathbb {Z}^*_{N}$ such that $x_{i-1} = y_{i-1}\cdot N + z_{i-1}$, where $x_{i-1}$ is used at step $i-1$ in $\textsf {Eval}(\textsf {ek}, \textsf {tag}^*, x)$. Inductively, $x_0 = y_0\cdot N + z_0$ is recovered correctly. In summary, $\textsf {Invert}(\textsf {tk}, \textsf {tag}^*, \textsf {Eval}(\textsf {ek}, \textsf {tag}^*, x)) = x$ for an overwhelming fraction of the domain $\mathbb {Z}_{N^{\zeta +1}}$ and the injectivity is concluded.

Indistinguishability. Let $\textsf {tag}^*_0, \textsf {tag}^*_1 \in \{0,1\}^t$ and $(\textsf {ek}_b, \textsf {tk}_b)\!\leftarrow \!\textsf {Sample}(1^\lambda , \textsf {tag}^*_b)$ for $b\in \{0,1\}$. We want to prove that $\textsf {ek}_0$ and $\textsf {ek}_1$ are indistinguishable. Let $b\in \{0,1\}$. The evaluation key $\textsf {ek}_b$ is parsed as

$$\begin{aligned} \textsf {ek}_b&= \left( N, ~\zeta , ~ \{ g^{(b)}_{i,0}, g^{(b)}_{i,1} ~\in \mathbb {Z}_{N^{\zeta +1}}^*~ \}_{i=1}^t \right) \end{aligned}$$

where $g^{(b)}_{i,b'}$ is a Damgård-Jurik encryption of $\delta _{b', \textsf {tag}^*_{b,i}}$ for $i\in [t]$ and $b' \in \{0,1\}$, respectively and $\textsf {tag}^*_{b,i}$ is the i-th bit of $\textsf {tag}^*_b$. The indistinguishability readily follows the semantic security of the Damgård-Jurik encryption scheme under a standard hybrid argument.

Cumulative Lossiness. For $(\textsf {ek}, \textsf {tk})\!\leftarrow \!\textsf {Sample}(1^\lambda , \textsf {tag}^*)$ and $\textsf {tag}\in \{0,1\}^t$ such that $\textsf {tag}\ne \textsf {tag}^*$, we want to describe two (possibly inefficient) functions $\textsf {compress}_{\textsf {ek}}$ and $\textsf {expand}_{\textsf {ek}, \textsf {tag}}$ satisfying $\textsf {Eval}(\textsf {ek}, \textsf {tag}, x) = \textsf {expand}_{\textsf {ek}, \textsf {tag}}(\textsf {compress}_{\textsf {ek}}(x))$ for all $x \in \mathbb {Z}_{N^{\zeta +1}}$.

Given $x\in \mathbb {Z}_{N^{\zeta +1}}$, the function $\textsf {compress}_{\textsf {ek}}(x)$ is described as follows:

• 1. Parse the evaluation key as $\textsf {ek}_b = \left( N, ~\zeta , ~ \{ g_{i,0}, g_{i,1} ~\in \mathbb {Z}_{N^{\zeta +1}}^*~ \}_{i=1}^t \right)$ and (inefficiently) factor $N = pq$.

• 2. Initialize a list $\mathsf {List}$ to empty. Compute $(y,z)\in \mathbb {Z}_{N^\zeta } \times \mathbb {Z}_N$ such that $x = y\cdot N + z$. If $\gcd (z,N) > 1$ then add 0 to $\mathsf {List}$ and output $\mathsf {List}$.

• 3. Otherwise, having p, q, for all $(i, b) \in [t] \times \{0,1\}$, use the Damgård-Jurik decryption $\textsf {Dec}((p, q), g_{i,b}) = \delta _{b, \textsf {tag}^*_i}$ and in the end obtain $\textsf {tag}^* \in \{0,1\}^t$. Moreover, use the isomorphism $\psi ^{\text {-1}}_{\zeta }$ from Theorem 2 to also recover all the $\alpha _{i,b} \in \mathbb {Z}^*_N$ while knowing $g_{i,b} \in \mathbb {Z}^*_{N^{\zeta +1}}$ and $\delta _{b, \textsf {tag}^*_i} \in \mathbb {Z}_{N^\zeta }$.

• 4. For $i = 1$ to t, define

  $$\textsf {sibling}_i {:}{=}\textsf {tag}^*_{[1..(i-1)]}\,\Vert \,(1 - \textsf {tag}^*_i)$$

  where $\textsf {tag}^*_{[1..(i-1)]}$ denotes the first $i-1$ bits of $\textsf {tag}^*$.

• 5. For $j = 1$ to t, perform the following:

  • Let $x_0 = x$ and find $(y_0, z_0)$ such that $x_0 = y_0 \cdot N + z_0$.

  • For $k = 1$ to $j-1$, compute

    $$ x_k = g^{y_{k-1}}_{k, \textsf {sibling}_{j}[k]} \cdot z^{N^\zeta }_{k-1} \text { (mod } N^{\zeta +1} \text {)} $$

    where $\textsf {sibling}_{j}[k]$ is the k-th bit of $\textsf {sibling}_j$.

  • Let $b = \textsf {sibling}_{j}[j]$. Compute $(y_{j-1}, z_{j-1})$ such that $x_{j-1} = y_{j-1}\cdot N + z_{j-1}$ and add

    $$(\alpha _{j-1, b}^{y_{j-1}}\cdot z_{j-1})^{N^\zeta } \text { (mod } N^{\zeta +1} \text {)} \in \mathbb {Z}_N$$

    to $\mathsf {List}$.

• 6. Output $\mathsf {List} \in \mathbb {Z}^t_{N}$.

Given $\textsf {tag}\ne \textsf {tag}^*$ and a $\mathsf {List} \in \mathbb {Z}^t_N$, the function $\textsf {expand}_{\textsf {ek}, \textsf {tag}}(\mathsf {List})$ is given below:

• 1. Parse the evaluation key as $\textsf {ek}_b = \left( N, ~\zeta , ~ \{ g_{i,0}, g_{i,1} ~\in \mathbb {Z}_{N^{\zeta +1}}^*~ \}_{i=1}^t \right)$ and (inefficiently) factor $N = pq$.

• 2. If $\mathsf {List}$ contains only one element 0, output 0.

• 3. Otherwise, having p, q, for all $(i, b) \in [t] \times \{0,1\}$, use the Damgård-Jurik decryption $\textsf {Dec}((p, q), g_{i,b}) = \delta _{b, \textsf {tag}^*_i}$ and in the end obtain $\textsf {tag}^* \in \{0,1\}^t$.

• 4. Compute $i = \min _{j\in [t]}(\textsf {tag}_j \ne \textsf {tag}^*_j)$. It holds that $1 \le i \le t$ is well-defined because $\textsf {tag}\ne \textsf {tag}^*$.

• 5. Let $x_i = \mathsf {List}[i]$. For $k = i+1$ to t, conduct the following:

  • Compute $(y_{k-1}, z_{k-1})$ satisfying $x_{k-1} = y_{k-1} \cdot N + z_{k-1}$.

  • Compute

    $$ x_k = g^{y_{k-1}}_{k,\textsf {tag}_k}\cdot z^{N^\zeta }_{k-1} \text { (mod } N^{\zeta +1} \text {)}. $$

• 6. Output $x_t \in \mathbb {Z}^*_{N^{\zeta +1}}$.

Relating to cumulative lossiness, we evaluate $|\{\textsf {compress}_\textsf {ek}(x):x\in \mathbb {Z}_{N^{\zeta +1}}\}|$. By construction, for $x\in \mathbb {Z}^*_{N^{\zeta +1}}$, the output of $\textsf {compress}_\textsf {ek}(x)$ is a list of t elements in $\mathbb {Z}_N$. If $x\in \mathbb {Z}_{N^{\zeta +1}} \setminus \mathbb {Z}^*_{N^{\zeta +1}}$, $\textsf {compress}_\textsf {ek}(x)$ outputs a list of one single element, namely 0. We then have the bound

$$\begin{aligned} |\{\textsf {compress}_\textsf {ek}(x):x\in \mathbb {Z}_{N^{\zeta +1}}\}| = N^t + 1 \le 2\cdot N^t. \end{aligned}$$

We want to prove that $\textsf {Eval}(\textsf {ek}, \textsf {tag}, x) = \textsf {expand}_{\textsf {ek}, \textsf {tag}}(\textsf {compress}_{\textsf {ek}}(x))$ for all $x\in \mathbb {Z}_{N^{\zeta +1}}$ and $\textsf {tag}\ne \textsf {tag}^*$. If $x\in \mathbb {Z}_{N^{\zeta +1}} \setminus \mathbb {Z}^*_{N^{\zeta +1}}$, then $\textsf {Eval}(\textsf {ek}, \textsf {tag}, x) = 0$ by construction. Moreover, we have $x = y\cdot N + z$ for $(y,z) \in \mathbb {Z}_{N^\zeta } \times \mathbb {Z}_N$ such that $\gcd (z,N) > 1$. Thus, $\textsf {compress}_{\textsf {ek}}(x)$ outputs $\mathsf {List}$ containing only 0 and step 2 in $\textsf {expand}_{\textsf {ek}, \textsf {tag}}(\mathsf {List})$ recovers exactly 0. Otherwise, suppose $x\in \mathbb {Z}^*_{N^{\zeta +1}}$. Our main observation is that for $i = \min _{j\in [t]}(\textsf {tag}_j \ne \textsf {tag}^*_j)$, the value $x_i$ will uniquely determine $x_t$, by the fact that $\psi _{\zeta }$ is an isomorphism from Theorem 2. Moreover, because $\textsf {tag}_i \ne \textsf {tag}^*_i$ and $\textsf {tag}_k = \textsf {tag}^*_k$ for all $k < i$, we have

$$ x_i = (\alpha ^{y_{i-1}}_{i-1, b}\cdot z_{i-1})^{N^\zeta } \text { (mod } N^{\zeta +1} \text {)} $$

and the sequence $(x_0, \dots , x_{i-1} = y_{i-1}\cdot N + z_{i-1})$ stays the same as if the input tag is $\textsf {tag}^*$. By definition of $\textsf {sibling}_i$, it is easily verified that the loop 5 in $\textsf {compress}_\textsf {ek}$ constructs $\mathsf {List}$ such that $\mathsf {List}[i] = x_i$ and $i = \min _{j\in [t]}(\textsf {tag}_j \ne \textsf {tag}^*_j)$. Finally, the loop 5 in $\textsf {expand}_{\textsf {ek},\textsf {tag}}(\mathsf {List})$ performs exactly the same computation as $\textsf {Eval}(\textsf {ek}, \textsf {tag}, x)$ would do, starting from i. Hence, the equality $\textsf {Eval}(\textsf {ek}, \textsf {tag}, x) = \textsf {expand}_{\textsf {ek}, \textsf {tag}}(\textsf {compress}_{\textsf {ek}}(x))$ is justified.    $\square$

Remark 1

The domain is $\mathbb {Z}_{N^{\zeta +1}}$ and its size is $\log (N^{\zeta +1}) = (\zeta +1)\log N$. Moreover, by setting the tag length $t = O(\lambda )$ and the exponent $\zeta = \omega (\lambda )$ so that our CALBO-TDFs can be used for the applications to randomness extractors in [23, Corollary 5.12], the lossiness rate of the above construction becomes

$$ \frac{(\zeta +1)\log N - \log (2\cdot N^t)}{(\zeta +1)\log N} = 1 - \frac{t}{\zeta +1} - \frac{1}{(\zeta +1)\log N} = 1 - o(1) $$

and is indeed better than what the $\textsf {LWE}$-based CALBO-TDF achieves, which is $1 - \varTheta (1)$ by the parameter choices.