#  Lossy Cryptography from Code-Based Assumptions
Dense-Sparse LPN: A New Subexponentially Hard LPN Variant in SZK

Quang Dao Carnegie Mellon University. Email<EMAIL_ADDRESS>Aayush Jain
Carnegie Mellon University. Email<EMAIL_ADDRESS>
###### Abstract

Over the past few decades, we have seen a proliferation of advanced
cryptographic primitives with lossy or homomorphic properties built from
various assumptions such as Quadratic Residuosity, Decisional Diffie-Hellman,
and Learning with Errors. These primitives imply hard problems in the
complexity class $\mathcal{SZK}$ (statistical zero-knowledge); as a
consequence, they can only be based on assumptions that are broken in
$\mathcal{BPP}^{\mathcal{SZK}}$. This poses a barrier for building advanced
primitives from code-based assumptions, as the only known such assumption is
Learning Parity with Noise (LPN) with an extremely low noise rate
$\frac{\log^{2}n}{n}$, which is broken in quasi-polynomial time.

In this work, we propose a new code-based assumption: Dense-Sparse LPN, that
falls in the complexity class $\mathcal{BPP}^{\mathcal{SZK}}$ and is
conjectured to be secure against subexponential time adversaries. Our
assumption is a variant of LPN that is inspired by McEliece’s cryptosystem and
random $k\mbox{-}$XOR in average-case complexity. Roughly, the assumption
states that

$(\mathbf{T}\,\mathbf{M},\mathbf{s}\,\mathbf{T}\,\mathbf{M}+\mathbf{e})\quad\text{is
indistinguishable from}\quad(\mathbf{T}\,\mathbf{M},\mathbf{u}),$

for a random (dense) matrix $\mathbf{T}$, random sparse matrix $\mathbf{M}$,
and sparse noise vector $\mathbf{e}$ drawn from the Bernoulli distribution
with inverse polynomial noise probability.

We leverage our assumption to build lossy trapdoor functions (Peikert-Waters
STOC 08). This gives the first post-quantum alternative to the lattice-based
construction in the original paper. Lossy trapdoor functions, being a
fundamental cryptographic tool, are known to enable a broad spectrum of both
lossy and non-lossy cryptographic primitives; our construction thus implies
these primitives in a generic manner. In particular, we achieve collision-
resistant hash functions with plausible subexponential security, improving
over a prior construction from LPN with noise rate $\frac{\log^{2}n}{n}$ that
is only quasi-polynomially secure.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results
    2. 1.2 Related Works
  2. 2 Overview of Techniques
    1. 2.1 Collision-Resistant Hash Functions from Dense-Sparse LPN
    2. 2.2 Lossy Trapdoor Functions
    3. 2.3 Discussion on Our Assumption
    4. 2.4 Open Questions
  3. 3 Preliminaries
    1. 3.1 Coding Theory
  4. 4 Our Code-Based Assumption: Dense-Sparse LPN
  5. 5 Collision-Resistant Hash Functions
  6. 6 Lossy Trapdoor Functions
    1. 6.1 Definition
    2. 6.2 Construction
  7. 7 Cryptanalysis on Dense-Sparse LPN
    1. 7.1 Security of Sparse LPN
    2. 7.2 Dual-Distance of Dense-Sparse LPN
      1. 7.2.1 Searching for $\mathbf{T}$
      2. 7.2.2 On Subexponential Time Attacks

##  1 Introduction

Introduced in 2005, the Learning with Errors (LWE) assumption [Reg05] has
emerged as a basis for designing post-quantum cryptography. LWE and its
structured variants such as Ring-LWE [LPR10] or NTRU [HPS98] are central to
constructing a host of advanced cryptographic primitives including fully
homomorphic encryption for classical [Gen09, BV11, GSW13] and quantum
computations [Mah18a, Bra18], attribute-based and other advanced encryption
schemes [GVW13, GVW15], non-interactive zero-knowledge [PS19], succinct
arguments [CJJ22], and many other advances in classical [GKW17, WZ17, GKW18,
LMW23] and quantum cryptography [BCM+18, Mah18b].

While LWE has proven to be surprisingly expressive in giving rise to advanced
primitives, other post-quantum assumptions such as Learning Parity with Noise
[BFKL94], Isogenies [Cou06, RS06, CLM+18], and Multivariate Quadratics
[Har82], currently stand nowhere close in implying such advanced primitives,
making LWE the single point of failure for designing advanced post-quantum
cryptography. This state of affairs is highly unsatisfactory, since we would
like to have some diversity in the assumptions implying a given primitive to
hedge against unexpected cryptanalytic breakthroughs. Indeed, recent works
[CD23a, MMP+23, Rob23] have rendered the once-believed post-quantum assumption
of SIDH classically broken in polynomial time.

This work aims to address a possible stagnation in terms of techniques and
assumptions implying advanced post-quantum cryptography. This lack of
versatility in assumptions for the most part can be attributed to the _lack of
techniques_ in utilizing other post-quantum assumptions. The focus of this
work lies in code-based cryptographic assumptions such as the Learning Parity
with Noise (LPN) assumption [BFKL94] and its variants.

Learning Parity with Noise posits that random linear equations (with a planted
secret solution) that is perturbed by sparse noise appears pseudorandom.
Namely:

$\displaystyle(\mathbf{A},\mathbf{s}\cdot\mathbf{A}+\mathbf{e})\approx_{c}(\mathbf{A},\mathbf{b}),$

where the coefficient matrix $\mathbf{A}$ is chosen at random from
$\mathbb{F}^{n\times m}_{2}$, the secret
$\mathbf{s}\leftarrow\mathbb{F}^{1\times n}_{2}$, $\mathbf{b}$ is chosen to be
random vector in $\mathbb{F}^{1\times m}_{2}$ and the error vector
$\mathbf{e}\in\mathbb{F}^{1\times m}_{2}$ is chosen so that each coordinate is
i.i.d. sampled from the Bernoulli distribution with probability $\epsilon$.
The problem is believed to be _subexponentially secure_ , meaning that
subexponential $\exp(n^{O(1)})$-time adversaries have negligible
distinguishing advantage when $\epsilon=O\left(\frac{1}{n^{\delta}}\right)$
for any constant $\delta\in(0,1)$.111A stronger version of subexponential
security, which we do not consider in this work, also requires that the
distinguishing advantage is an inverse subexponential $\exp(-n^{O(1)})$.

LPN is conceptually similar to LWE, in the sense that both posit
pseudorandomness of planted random linear equations perturbed with noise.
However, while for LWE the noise has low magnitude, for LPN it is sparse. One
would expect that due to this similarity, LPN should imply a comparable
variety of advanced primitives—yet this could not be any further from reality.
On the one hand, recent works have leveraged the sparse noise structure to
build specialized primitives such as homomorphic secret sharing [DIJL23], or
use LPN (over large fields) in combination with Bilinear Maps [MVO91] and
Goldreich’s PRG [Gol11] to build indistinguishability obfuscation [JLS21,
JLS22].

On the other hand, despite almost three decades of research and in drastic
contrast to LWE, we currently know only a handful of ways to leverage the LPN
assumption. This is evident in the fact that aside from CPA/CCA secure public-
key encryption schemes [Ale03, DMN12, KMP14, YZ16] and UC-secure two-round
oblivious transfer [DGH+20], subexponentially secure variants of LPN alone are
currently not known to imply any other primitives in Cryptomania [Imp95].
Things seem to improve when one works with the quasi-polynomial time broken
variant of the LPN assumption with very small noise probability
$O(\frac{\log^{2}n}{n})$, but even assuming this variant, very few primitives
are known. These include collision-resistant and collapsing hash functions
[BLVW19, YZW+19, Zha22], identity-based encryption [BLSV18], and
statistically-sender-private oblivious transfer [BF22].

This brings us to our goal:

Goal. _Devise new coding-theoretic techniques and assumptions for building
advanced cryptography._

To facilitate progress on the main goal above, we focus more on identifying
properties of the assumption that could enable progress on the question,
rather than focusing on specific primitives themselves. What makes assumptions
such as LWE, Diffie-Hellman, Bilinear Maps, or Quadratic Reciprocity, special
is that they can be used to design primitives with “lossy” or “homomorphic”
properties, such as lossy trapdoor functions [PW08] and linearly homomorphic
encryption. Furthermore, the homomorphic/lossy properties of the assumption
make them easier to work with to design other advanced Cryptomania primitives,
such as attribute-based encryption or succinct arguments.

A key property that captures such assumptions is that they can be broken using
an $\mathcal{SZK}$ oracle, where $\mathcal{SZK}$ is the complexity class of
languages that have statistically-hiding zero-knowledge proofs. This
“$\mathcal{SZK}$-broken” complexity class, known as
$\mathcal{BPP}^{\mathcal{SZK}}$, consists of languages that can be decided
efficiently using a _statistical difference_ ($\mathsf{SD}$) oracle [SV97].
The $\mathsf{SD}$ oracle takes as input two polynomial sized distribution
samplers $({\cal D}_{0},{\cal D}_{1})$ (represented as randomized circuits),
with the promise that either the statistical distance between the
distributions is less than $\frac{1}{3}$ or it is more than $\frac{2}{3}$. The
oracle then identifies which is the case.

This $\mathcal{SZK}$ regime indeed captures all of the assumptions mentioned
above. For LPN, it is known [BLVW19] that the quasi-polynomial time broken
variant with noise probability $O(\frac{\log^{2}n}{n})$ can be broken with an
$\mathcal{SZK}$ oracle, whereas subexponential time secure variants with
inverse polynomial noise probability $\frac{1}{n^{\delta}}$ for
$\delta\in(0,1)$ are currently not known to be in $\mathcal{SZK}$. This helps
to explain why so little is known from LPN with inverse polynomial noise rate.

Therefore, to make progress in code-based cryptography, the first step would
be to answer the following question:

Question. _Is there a subexponentially-secure coding theoretic assumption with
inverse polynomial noise probability that is in $\mathcal{SZK}$?_

###  1.1 Our Results

We introduce a novel, well-motivated variant of LPN that we believe is secure
against subexponential time algorithms. Unlike LPN where the matrix is chosen
randomly, in our case it is a structured matrix. We work with a sufficiently
small but inverse polynomial probability $\frac{1}{n^{\delta}}$ for a constant
$\delta\in(0.5,1)$, a regime for which our assumption can be conjectured to be
hard against subexponential $\exp(\widetilde{O}(n^{1-\delta}))$-time
adversaries.222However, an adversary’s success probability in breaking our
assumption is at least inverse quasi-polynomial; see Section 2.3 for more
discussion. Since our assumption implies primitives that can be broken by
$\mathcal{BPP}^{\mathcal{SZK}}$,333It’s a folklore result that lossy trapdoor
functions, which we construct, lie in $\mathcal{BPP}^{\mathcal{SZK}}$; a
formal proof can be found in [FR23, Appendix B]. our assumption indeed lies in
$\mathcal{BPP}^{\mathcal{SZK}}$, making it the first plausible subexponential-
time secure coding-theoretic assumption known to be in
$\mathcal{BPP}^{\mathcal{SZK}}$.

##### New Assumption: Dense-Sparse LPN.

Our assumption borrows structural properties of two well-studied assumptions:
the standard Learning Parity with Noise [BFKL94] and the sparse Learning
Parity with Noise problem [Ale03]. Introduced in 2003 by Alekhnovich, Sparse
LPN is exactly like standard LPN except that each column is chosen randomly
among $k$-sparse vectors, where $k\geq 3$ is a constant. Sparse LPN is closely
related to well-studied problems in the domain of constraint satisfaction and
local pseudorandom generators [Gol00, CM01, Fei02, MST03, FKO06, CEMT09, BQ09,
ABW10, ABR12, BQ12, App12, App13, OW14, AL16, KMOW17, CDM+18, AK19], and when
the number of samples satisfies $m=n^{\frac{k}{2}(1-\rho)}$ for any constant
$0<\rho<1$,444When $m=\Omega(n^{k/2})$, due to the birthday bound two
equations will repeat with constant probability, implying a trivial cheating
strategy. it is believed to be subexponentially secure (provided the noise
probability is a large enough inverse polynomial). Sparse LPN has also been
shown to give rise to public-key encryption by Applebaum, Barak and Wigderson
[ABW10], but not more advanced Cryptomania primitives.

Our assumption combines features from both LPN and Sparse LPN, and posits that
LPN holds for the following _Dense-Sparse_ matrix distribution. We first
sample a $k$-sparse matrix $\mathbf{M}\in\mathbb{F}^{n\times m}_{2}$ according
to the distribution of coefficient matrix for the Sparse LPN assumption. We
then sample a random (dense) matrix
$\mathbf{T}\leftarrow\mathbb{F}^{n^{\prime}\times n}_{2}$, where
$n^{\prime}=\alpha n$ for some constant $\alpha\in(0,1)$ (for simplicity, we
set $\alpha=1/2$ in our paper). Finally, we give out
$\mathbf{A}=\mathbf{T}\cdot\mathbf{M}\in\mathbb{F}^{n/2\times m}_{2}$, and
assume that random codewords of $\mathbf{A}$, perturbed by a Bernoulli noise
vector $\mathbf{e}$ of inverse-polynomial noise rate, look pseudorandom. More
formally, our assumption is stated as follows.

######  Assumption 1.1 (Dense-Sparse LPN, informal).

Let $k\geq 3$ be a constant, and consider parameters $n\in\mathbb{N}$,
$m=m(n)<n^{k/2}$, and $\epsilon=\epsilon(n)<1$. Let ${\cal M}_{\mathsf{sp}}$
be an efficiently sampleable “good” distribution over all $k$-sparse matrices
in $\mathbb{F}_{2}^{n\times m}$. We say that the _$(n,m,k,{\cal
M}_{\mathsf{sp}},\epsilon)$ -Dense-Sparse LPN_ assumption holds if the
following two distributions are computationally indistinguishable:

$\displaystyle\\{(\mathbf{T}\,\mathbf{M},\mathbf{s}\,\mathbf{T}\,\mathbf{M}+\mathbf{e})\\}_{n\in\mathbb{N}}\approx_{c}\\{(\mathbf{T}\,\mathbf{M},\mathbf{u})\\}_{n\in\mathbb{N}},$

where $\mathbf{T}\leftarrow\mathbb{F}_{2}^{n/2\times n}$,
$\mathbf{M}\leftarrow{\cal M}_{\mathsf{sp}}$,
$\mathbf{s}\leftarrow\mathbb{F}_{2}^{1\times n/2}$,
$\mathbf{e}\leftarrow\mathsf{Ber}(\epsilon)^{1\times m}$, and
$\mathbf{u}\leftarrow\mathbb{F}_{2}^{m}$.

Looking ahead, our constructions will require us to assume Dense-Sparse LPN
for an inverse polynomial noise rate $\epsilon=O(n^{-\delta})$ for some
constant $\delta$ close to $1$, and the number of samples
$m=\Omega(n^{1+\rho(\delta)})$ for a constant $\rho$ that depends on $\delta$.
This parameter regime is plausibly secure against subexponential-time
adversaries (see Section 7 for details).

An important technical point in Assumption 1.1 is that of a “good”
distribution of $k$-sparse matrices. This is due to the following reason: for
$\mathbf{M}\in\mathbb{F}_{2}^{n\times m}$ chosen uniformly at random from the
set of all $k$-sparse matrices, there is an _inverse polynomial_ probability
of $O(m^{2}/n^{k})$ that $\mathbf{M}$ has a vector $\mathbf{x}$ in its kernel
of constant Hamming weight (so that $\mathbf{M}\,\mathbf{x}=\mathbf{0}$). When
this “bad” event happens, one cannot hope for distinguishing security to hold.
Thus, since we want our distinguishing advantage to be negligible, we must
sample $\mathbf{M}$ from another “good” distribution where this “bad” event
happens with negligible probability; in particular, we will use the recent
distribution constructed by Applebaum and Kachlon [AK19]. We will expand on
this in Section 2.3.

##### Connections to McEliece.

Our assumption can be viewed as applying the design principles of the classic
McEliece [McE78] and Niederreiter [Nie86] cryptosystems, which is to hide the
sparse matrix $\mathbf{M}$ whose exposure would lead to an efficient attack in
our parameter regime. In this sense, we follow a rich body of works on
McEliece instantiated with different families of codes [Sid94, LJ12, BL05,
BLP10, BLP11, JM96, MTSB12, SK14, HSEA14]. Nevertheless, there are two
important distinctions between our assumption and prior McEliece variants. The
first is that our variants are _not_ algebraically structured, unlike the
original McEliece cryptosystem itself (which uses binary Goppa codes), or many
other algebraic variants [Sid94, JM96, BL05] or LDPC codes [BC07, BBC08] that
have subsequently been broken [SS92, BC07, MS07, OTD10, Wie10, LT13, COT14,
BCD+16].555In this sense, our assumption is related to the more combinatorial
McEliece variant with _medium-density parity check (MDPC)_ codes [MTSB12],
which still remains secure to this day. Secondly, we diverge from McEliece by
making the masking matrix $\bm{T}$ _compressing_ of dimension $\alpha n\times
n$ for any $\alpha<1$, which is necessary for ensuring security in our
setting. We expand more on this connection in Section 2.1.

##### Cryptographic Applications.

We leverage Dense-Sparse LPN with inverse polynomial noise rate to build the
following two primitives: a _collision-resistant hash function_ (in a simple
and direct manner), and a _lossy trapdoor function_.

Lossy Trapdoor Functions (LTDFs), introduced by Peikert and Waters in 2008
[PW08], is a fundamental cryptographic tool that has found countless
applications to building other cryptographic applications. LTDFs consist of a
function family $F_{\mathsf{fk}}(\cdot)$ indexed by a public function key
$\mathsf{fk}$, where the algorithm $\mathsf{Gen}$ that samples $\mathsf{fk}$
could sample keys in two modes. When the mode is injective, then the function
$F_{\mathsf{fk}}(\cdot)$ is injective and can even be inverted uniquely using
a trapdoor $\mathsf{td}$ generated by $\mathsf{Gen}$ at the same time of
sampling $\mathsf{fk}$. In lossy mode, the range of the function
$F_{\mathsf{fk}}(\cdot)$ is significantly smaller than the number of inputs.
Equivalently, this also means that the conditional entropy in
$x\in\\{0,1\\}^{\ell}$, given $y=F_{\mathsf{fk}}(x)$ for a random $x$ is
large. In our setting we design such LTDFs for which the conditional entropy
is at least $\Omega(\ell)$ where $\ell$ is the bit length of $x$. Finally, the
two modes are required to be computationally indistinguishable, meaning that
it is computationally hard to distinguish a random lossy key from a random
injective key.

######  Theorem 1.1 (informal).

Assuming Dense-Sparse LPN with inverse polynomial noise probability, there
exists a construction of LTDF where the lossy mode loses any constant fraction
$\Omega(\ell)$ of the input length $\ell$.

We give an example of how our parameters in Theorem 1.1 can be concretely
instantiated. In order for the lossy trapdoor function to lose (say) half of
its entropy in lossy mode, we may set the sparsity parameter $k=6$, the number
of samples $m=n^{2}$, and the error probability to be
$\epsilon=O\left(n^{-10/11}\right)$. See Theorem 6.1 for the precise parameter
regime required for LTDFs.

Lossy Trapdoor Functions are known from a number of quantum-broken assumptions
such as Decisional Diffie-Hellman, Bilinear Maps, Quadratic Residuosity, Phi-
Hiding, and Decisional Composite Residuosity (DCR). However, prior to our
work, no post-quantum assumption barring LWE was known to imply lossy trapdoor
functions, including LPN with noise probability $O(\frac{\log^{2}n}{n})$ that
is broken in quasi-polynomial time.

Since Lossy Trapdoor Functions are known to imply a number of lossy
primitives, as a result we can generically realize those primitives from
Dense-Sparse LPN. This list of primitives and applications include: collision-
resistant hash functions and CCA secure encryption [PW08], dual-mode
commitments and statistically-sender-private oblivious transfer [HLOV11],
deterministic encryption [BFO08], trapdoor functions with many hardcore bits,
analyzing OAEP [KOS10], hedged public-key encryption with bad randomness
[BBN+09], selective opening security [BHY09], pseudo-entropy functions
[BHK11], point-function obfuscation [Zha16], computational extractors [DVW20,
GKK20], incompressible encodings [MW20], and many more.

###  1.2 Related Works

##### LPN Variants and their Applications.

Recent works on _pseudorandom correlation generators (PCGs)_ [BCGI18, BCG+19,
BCG+20b] and _pseudorandom correlation functions (PCFs)_ [BCG+20a] have
proposed many novel variants of LPN with different matrix distributions
[BCG+20a, CRR21, BCG+22, CD23b, RRT23, BCCD23]. While these works are similar
to ours in that they introduce new LPN variants, we introduce our variant
(Dense-Sparse LPN) for a _different_ purpose: building more advanced lossy
primitives in Cryptomania. In contrast, it is not known whether PCGs or PCFs
imply public-key encryption or other Cryptomania primitives.

##### Group Actions and SZK Primitives.

Besides lattices, certain assumptions on (suitable) group actions [BY91,
Cou06] also imply primitives in $\mathcal{SZK}$, and are plausibly post-
quantum secure against subexponential time adversaries. In more details, the
authors of [ADMP20] showed that group actions satisfying a _weak
pseudorandomness_ property, such as those based on isogenies like CSIDH
[CLM+18] or CSI-FiSh [BKV19], suffices for building a variety of
$\mathcal{SZK}$ primitives such as hash proof system [CS02], dual-mode PKE
[PVW08], malicious SSP-OT [NP01, HK12], and more. However, their techniques do
not seem to extend to building lossy trapdoor functions.

##### Future Directions.

A fascinating question left open in our work is whether we can construct
similar Cryptomania primitives, though not known to generically follow from
lossy trapdoor functions, from our Dense-Sparse LPN assumption. These
primitives, which are known to be achievable from LPN with quasi-polynomial
security, include laconic oblivious transfer [CDG+17, BLSV18], identity-based
encryption [BLSV18], and (maliciously-secure) statistically-sender-private
oblivious transfer [BF22]. In Section 2.4, we sketch how our current
assumption encounters roadblocks toward building these primitives.

##  2 Overview of Techniques

We now discuss the intuition for how the structural properties of Dense-Sparse
LPN puts it in $\mathcal{SZK}$ and enables applications such as lossy trapdoor
functions. We then discuss key points in the cryptanalysis of our assumption
and end with some open questions.

###  2.1 Collision-Resistant Hash Functions from Dense-Sparse LPN

##### Collision-Resistance from LPN.

In a nutshell, our progress on building lossy trapdoor functions from Dense-
Sparse LPN is a result of achieving _input compression_ under a _larger_ ,
inverse polynomial noise rate. In both lattice-based and code-based
cryptography, we consider the following hash function family:

$\displaystyle
h_{\mathbf{A}}(\mathbf{x})=\mathbf{A}\cdot\mathbf{x},\qquad\text{ indexed by
}\mathbf{A}\leftarrow{\cal R}^{n\times m}\text{ over some finite ring }{\cal
R},$

and the input $\mathbf{x}$ comes from a “low-norm” distribution. In the case
of LWE, we have $\mathbf{A}\leftarrow\mathbb{Z}_{q}^{n\times m}$ for some
modulus $q=q(n)$, and $\mathbf{x}\in\\{0,1\\}^{m}$. A simple calculation then
shows that the number of inputs, which is $\lvert\\{0,1\\}^{m}\rvert=2^{m}$,
is greater than the number of outputs, which is
$\lvert\mathbb{Z}_{q}^{n}\rvert=2^{n\log q}$, when $m>n\log q$. This is
achievable even for exponential modulus $q=2^{O(n)}$, for which we only need
to set $m>O(n^{2})=\operatorname{\mathsf{poly}}(n)$.

In contrast, in the case of LPN, we have
$\mathbf{A}\leftarrow\mathbb{F}_{2}^{n\times m}$ and
$\mathbf{x}\leftarrow{\cal B}(m,t)$, the Hamming ball of weight $t$ in
$\mathbb{F}_{2}^{m}$. To achieve compression, we then need to ensure that

$\displaystyle\text{number of inputs for
}h_{\mathbf{A}}=\binom{m}{t}\quad\gg\quad 2^{n}=\text{number of outputs for
}h_{\mathbf{A}}.$ (1)

For $m=\operatorname{\mathsf{poly}}(n)$, using the binomial approximations
$\left(\frac{m}{t}\right)^{t}\leq\binom{m}{t}\leq\left(\frac{em}{t}\right)^{t}$,
this is only possible when $t=\Omega(n/\log n)$. To see why this is
problematic, we now sketch the proof (which can be found in [BLVW19]) that
$h_{\mathbf{A}}$ is collision-resistant, by a reduction to LPN with error
probability $\epsilon=\epsilon(n)$. A collision
$(\mathbf{x}_{0},\mathbf{x}_{1})$ for $h_{\mathbf{A}}$ gives us
$\mathbf{A}\cdot(\mathbf{x}_{0}-\mathbf{x}_{1})=0$, which implies that we have
found a vector $\mathbf{x}=\mathbf{x}_{0}-\mathbf{x}_{1}$ in the kernel of
$\mathbf{A}$ that is at most $2t$-sparse. Such a vector can be used to detect
bias in LPN samples $(\mathbf{A},\mathbf{b}=\mathbf{s}\mathbf{A}+\mathbf{e})$,
since $\mathbf{b}\cdot\mathbf{x}=\mathbf{e}\cdot\mathbf{x}$ is distributed
according to the Bernoulli distribution with error probability

$\displaystyle\epsilon^{\prime}\leq\frac{1-(1-\epsilon)^{2t}}{2},\quad\text{
and thus with bias }\quad 1-2\epsilon^{\prime}=(1-\epsilon)^{2t}\geq
2^{-\Omega(\epsilon t)},$

by the Piling-Up Lemma. For this bias to be noticeable, compared to a uniform
random bit $\mathbf{b}\cdot\mathbf{x}$ when
$\mathbf{b}\leftarrow\mathbb{F}_{2}^{m}$ is sampled randomly, we would need
$\epsilon=O(\log n/t)=O(\log^{2}n/n)$. With this error probability, LPN is
broken in quasi-polynomial time $O(n^{\log n})$. More importantly, we cannot
afford a lower error probability so that $\epsilon t=O(1)$, as LPN is fully
broken with $\epsilon=O(\log n/n)$.666For $\epsilon=O(\log n/n)$, we can
choose $n$ random coordinates of $\mathbf{b}=\mathbf{s}\mathbf{A}+\mathbf{e}$,
which is error-free with noticeable probability, and then solve for
$\mathbf{s}$.

##### Achieving Higher Noise Rate with Sparse LPN.

Can we hope to achieve collision-resistance with larger error probability? Our
key idea is that by changing the distribution of the matrix $\mathbf{A}$, we
are able to _reduce_ the size of the output space, making compression possible
at lower sparsity $t$ (and hence collision-resistance at higher noise rate
$\epsilon$). Indeed, if the matrix $\mathbf{A}$ is _sparse_ with each column
having exactly $k$ ones, where $k$ is a constant or slightly super-constant,
then the output space only consists of vectors
$\mathbf{y}=\mathbf{A}\mathbf{x}\in\mathbb{F}_{2}^{n}$ that are at most
$kt$-sparse. Thus, we achieve compression when

$\displaystyle\text{number of inputs for }h_{\mathbf{A}}={m\choose
t}\quad\gg\quad\sum_{s=0}^{kt}{n\choose s}=\text{number of outputs for
}h_{\mathbf{A}}.$

Using binomial approximations and some straightforward calculations, the above
is satisfied when

$\displaystyle\left(\frac{m}{t}\right)^{t}\gg
kt\cdot\left(\frac{en}{kt}\right)^{kt}\quad\implies\quad
t^{k-1}\gg\Omega\left(\frac{n^{k}}{m}\right).$

Thus, as soon as $t^{k-1}\gg\frac{n^{k}}{m}$, we will have $\mathbf{y}$ lose
information on a random $t$-sparse $\mathbf{x}$. Let us try to understand how
large $t$ needs to be. In the most conservative regime when $m=n^{1+\rho}$ for
a small constant $\rho>0$, $t^{k-1}$ must be bigger than $n^{k-1-\rho}$,
implying $t>n^{1-\frac{\rho}{k-1}}$ which approaches $n$ as $\rho$ approaches
$0$. In the most aggressive setting when $m$ is close to $n^{\frac{k}{2}}$,
$t^{k-1}$ must be bigger than $n^{\frac{k}{2}}$. This yields
$t\approx\sqrt{n}$ if $k$ is a large enough constant.

More generally, if we wish to achieve a compression factor $D>1$, meaning that
the output length is a factor of $D$ smaller than the input length, then we
would need

$\displaystyle\left(\frac{m}{t}\right)^{t}>\left(kt\cdot\left(\frac{en}{kt}\right)^{kt}\right)^{D}\quad\implies\quad
t^{D\cdot k-1}=\Omega\left(\frac{n^{D\cdot k}}{m}\right).$ (2)

We will refer to Equation 2 as the _compression_ equation. Similar to the
above estimate, we can have $t=n^{\delta}$ be polynomially smaller than $n$
for a polynomial number of samples $m=n^{1+\rho_{k,D}(\delta)}$, where
$\rho_{k,D}(\delta)$ is a constant related to $\delta$. This implies that
collision-resistance can be achieved at an inverse polynomial error
probability $\epsilon=O(1/t)=O(1/n^{\delta})$. We call this the _compression
regime_ of Sparse LPN.

##### Sparse LPN in its Compression Regime is Broken.

Unfortunately, while Sparse LPN in the compression regime would imply
collision-resistant hash functions, it is not secure. We give a new but simple
attack, that in the compression regime with any factor $D>1$, one can easily
find $O(t)$ sparse vectors $\mathbf{v}\in\mathbb{F}_{2}^{m}$ so that
$\mathbf{A}\mathbf{v}=\mathbf{0}$. Thus, unlike (dense) LPN, Sparse LPN can be
broken in polynomial time even at sufficiently small but inverse-polynomial
noise probability $\epsilon=O(n^{-\delta})$, and with (related) polynomial
number of samples $m=n^{1+\rho_{k,D}(\delta)}$.

$|{\cal S}|=L$$\geq L+1$$\mathbf{0}$$\mathbf{0}$$\cdots$$\cdots$ Figure 1:
Attack against Sparse LPN with sparsity $k$, number of samples
$m=\Omega(n\cdot(n/t)^{k-1})$, and noise rate $\epsilon=O(\log n/t)$. We focus
on a set of rows ${\cal S}$ of size $L=O(t)$, and find all columns that is
non-zero only within rows contained in $T$. If we find at least $L+1$ such
columns, then we can find a linear dependence between these columns and come
up with a $\leq L$-sparse vector $\mathbf{x}$ such that
$\mathbf{A}\mathbf{x}=\mathbf{0}$, which can be used to detect noticeable bias
in the Sparse LPN samples.

The attack can be described as follows. For simplicity, assume that each
column of $\mathbf{A}$ is randomly and independently chosen from the set of
all $k$-sparse columns. We want to find a set ${\cal S}\subset[n]$ of size $L$
so that there are $L+1$ columns $\\{\mathbf{a}_{1},\ldots,\mathbf{a}_{L+1}\\}$
that are supported entirely in ${\cal S}$. Namely, these columns take the
value $0$ for indices in $[n]\setminus{\cal S}$. Once we have found these
columns, we can easily find some non-zero combinations combining
$\\{\mathbf{a}_{1},\ldots,\mathbf{a}_{L+1}\\}$ that sum to $0$ since they must
be linearly dependent.

For what $L$ can we expect this to happen? We compute the probability that for
an arbitrary set $S$ of size $L$ there exist $L+1$ column vectors supported
entirely in $S$. Since the probability that a single vector is supported in
$S$ is ${L\choose k}/{n\choose k}$, the expected number of such equations
becomes roughly $m\cdot{L\choose k}/{n\choose k}$. Thus, for $m$ samples, we
need to set $L$ so that

$\displaystyle m\cdot\frac{{L\choose k}}{{n\choose k}}\approx
m\cdot\left(\frac{L}{n}\right)^{k}\gg L,\qquad\text{ which is satisfied when
}L^{k-1}\approx\frac{n^{k}}{m}.$ (3)

Therefore, $L$ is up to a constant multiple of $t$ satisfying the compression
equation $t^{k-1}=\Omega(\frac{n^{k}}{m})$.

##### McEliece-style Wrapper to the Rescue.

Note that the above attack crucially relies on being able to identify the
support, or locality pattern, of the column vectors. Thus, if we can mask
these locality patterns, such as by applying a random linear transformation to
the columns, then we can prevent our attack.

This idea of masking a matrix, whose exposure would lead to an efficient
attack, goes back to the McEliece cryptosystem [McE78], and is the motivation
behind Dense-Sparse LPN. Recall that in McEliece and its variants, the public
key consists of a “randomized” code generating matrix
$\mathbf{A}=\mathbf{S}\mathbf{G}\mathbf{P}$, hiding a “nice” representation
$\mathbf{G}\in\mathbb{F}_{2}^{n\times m}$ (such as a binary Goppa code) that
enables efficient decoding. Here the masking matrices consist of a random
_square_ matrix $\mathbf{S}\in\mathbb{F}_{2}^{n\times n}$ multiplied on the
left and a permutation matrix $\mathbf{P}\in\mathbb{F}_{2}^{m\times m}$
multiplied on the right. The ciphertexts are then LPN samples with respect to
this structured matrix.

Our Dense-Sparse LPN assumption makes several modifications to the McEliece
template to suit our specific needs. Instead of an algebraically structured
matrix $\mathbf{G}$, we work with $k$-sparse matrices $\mathbf{M}$ which do
not have any algebraic structure. We also omit the permutation matrix
$\mathbf{P}$ as the sparse matrix distribution can be made invariant under
column permutations. Finally, we multiply with a random _compressing_ matrix
$\mathbf{T}\in\mathbb{F}_{2}^{\frac{n}{2}\times n}$ to get
$\mathbf{A}=\mathbf{T}\mathbf{M}$. This change serves two purposes: it ensures
security, as a square matrix $\mathbf{S}\in\mathbb{F}_{2}^{n\times n}$ does
not adequately mask $\mathbf{M}$ (see Section 7 for the attack), and it aligns
with our goal of using $\mathbf{M}$ for its lossy properties rather than for
decoding.

We discuss further aspects of Dense-Sparse LPN in Section 2.3; for the moment,
we shall go back to constructing collision-resistant hashes from our
assumption.

##### Back to Collision-Resistance.

We now re-examine our hash function
$h_{\mathbf{A}}=\mathbf{A}\mathbf{x}=\mathbf{T}\mathbf{M}\mathbf{x}$, which
takes $t$-sparse inputs $\mathbf{x}\in\mathbb{F}^{m}_{2}$ and maps them to
$\mathbb{F}^{\frac{n}{2}}_{2}$. When $n,m,t$ is chosen in the compression
regime to satisfy Equation 2 for any factor $D>1$, the mapping
$h_{\mathbf{M}}$ sending
$\mathbf{x}\mapsto\mathbf{x}^{\prime}=\mathbf{M}\mathbf{x}$ admits collisions.
Since $\mathbf{x}^{\prime}\in\mathbb{F}_{2}^{n}$ is at most $kt$-sparse, which
is lower than the threshold $O(n/\log n)$ for $\mathbf{T}$ to get collisions,
it follows that, with overwhelming probability, all collisions of
$h_{\mathbf{A}}$ come from collisions of $h_{\mathbf{M}}$.

Unfortunately, $h_{\mathbf{A}}$ is no longer compressing. Since the output of
$h_{\mathbf{A}}$ is no longer sparse, we can only bound the output size by its
length $\frac{n}{2}$, which is more than the input length of
$\log_{2}{m\choose t}=O(t\log n)$ as $t$ is polynomially smaller than $n$. To
get around this issue, we multiply the function $h_{\mathbf{A}}$ with another
compressing matrix $\mathbf{U}\in\mathbb{F}^{\ell\times\frac{n}{2}}_{2}$ for a
suitable $\ell$. Equivalently, we now consider the hash family

$\displaystyle
h_{\mathbf{A}^{\prime}}(\mathbf{x})=\mathbf{A}^{\prime}\cdot\mathbf{x}\in\mathbb{F}_{2}^{\ell},\qquad\text{where
}\quad\mathbf{A}^{\prime}=\mathbf{U}\cdot\mathbf{A}=(\mathbf{U}\cdot\mathbf{T})\cdot\mathbf{M}\in\mathbb{F}_{2}^{\ell\times
m}.$

Note that $\mathbf{V}=\mathbf{U}\cdot\mathbf{T}\in\mathbb{F}_{2}^{\ell\times
n}$ is identically distributed to a random matrix of the same dimensions. We
will set $\ell$ so that two conditions are satisfied:

  * •

To ensure $h_{\mathbf{A}^{\prime}}$ is compressing, we need
$2^{\ell}\ll{m\choose t}$.

  * •

To ensure $h_{\mathbf{A}^{\prime}}$ is collision-resistant, we want the linear
transformation $\mathbf{y}\mapsto\mathbf{V}\mathbf{y}$ to map different
vectors $\mathbf{y}=\mathbf{M}\mathbf{x}$ that are at most $kt$-sparse to
different elements of $\mathbb{F}_{2}^{\ell}$. This is satisfied with
overwhelming probability if $2^{\ell}\gg{n\choose kt}^{2}\approx\lvert{\cal
B}_{\leq}(n,kt)\rvert^{2}$ by a birthday bound, where ${\cal B}_{\leq}(n,kt)$
denotes the Hamming ball of radius $kt$.

We can meet both conditions by setting the compression factor $D>2$, so that
${m\choose t}\gg{n\choose k\cdot t}^{2}$. We give a formal argument in Section
5, where collision-resistance can be reduced to Dense-Sparse LPN with an
inverse polynomial error probability $\epsilon=O(n^{-\delta})$. Finally, we
note that while our later construction of lossy trapdoor functions generically
implies collision-resistant hash functions [PW08], the hash construction we
just sketched is more direct and conceptually simpler.

###  2.2 Lossy Trapdoor Functions

We now describe the main ideas behind our lossy trapdoor function
construction, which on a high level builds upon the lattice-based template of
[PW08]. The core of our contribution lies in identifying that, for the same
compression regime of Dense-Sparse LPN as sketched above, we can ensure both
lossiness and invertibility depending on the mode being instantiated.

Our function key is of the following form. Given a matrix
$\mathbf{A}=\mathbf{T}\mathbf{M}\in\mathbb{F}_{2}^{\frac{n}{2}\times m}$ drawn
from the Dense-Sparse LPN matrix distribution, we generate samples
$(\mathbf{b}_{i}=\mathbf{s}_{i}\mathbf{A}+\mathbf{e}_{i})_{i=1}^{\ell}$ for a
parameter $\ell=\ell(n)$ to be chosen later. Equivalently, we may concatenate
these samples to get a matrix
$\mathbf{B}=\mathbf{S}\mathbf{A}+\mathbf{E}\in\mathbb{F}_{2}^{\ell\times m}$.
This matrix $\mathbf{B}$ will be given out as-is for the lossy mode, and for
the injective mode, will be used to hide a _(robust) compressed sensing_
instance $\mathbf{C}\in\mathbb{F}_{2}^{\ell\times m}$ which allows for
efficient inversion. To summarize, the function key is as follows:

$\displaystyle\mathsf{fk}=\begin{cases}(\mathbf{A},\mathbf{B}=\mathbf{S}\mathbf{A}+\mathbf{E})&\text{
if }\mathsf{mode}=\mathsf{loss},\\\
(\mathbf{A},\mathbf{B}=\mathbf{S}\mathbf{A}+\mathbf{E}+\mathbf{C})&\text{ if
}\mathsf{mode}=\mathsf{inj},\text{ with }\mathsf{td}=\mathbf{S}.\end{cases}$

From the Dense-Sparse LPN assumption, it is clear that the two modes are
computationally indistinguishable. Now, the input to the function will be
$t$-sparse vectors $\mathbf{x}\in\mathbb{F}_{2}^{m}$, and function evaluation
returns

$\displaystyle\mathbf{y}=(\mathbf{y}_{1},\mathbf{y}_{2}),\qquad\text{ where
}\mathbf{y}_{1}=\mathbf{A}\mathbf{x}\in\mathbb{F}_{2}^{\frac{n}{2}},\text{ and
}\mathbf{y}_{2}=\mathbf{B}\mathbf{x}\in\mathbb{F}_{2}^{\ell}.$

To invert in injective mode (with trapdoor $\mathbf{S}$), we compute
$\mathbf{y}^{\prime}=\mathbf{y}_{2}-\mathbf{S}\mathbf{y}_{1}=\mathbf{C}\mathbf{x}+\mathbf{E}\mathbf{x}$,
then use the decoding guarantee of the compressed sensing matrix $\mathbf{C}$
to recover $\mathbf{x}$ in the presence of noise $\mathbf{E}\mathbf{x}$.

We now analyze the two modes to figure out the parameters that would ensure
both lossiness and efficient inversion holds with $1-\mathsf{negl}(n)$
probability over the choice of the function key.

##### Lossy Mode.

We want to choose parameters so that both
$\mathbf{y}_{1}=\mathbf{A}\mathbf{x}$ and
$\mathbf{y}_{2}=(\mathbf{S}\mathbf{A}+\mathbf{E})\mathbf{x}$ loses information
about $\mathbf{x}$. We will reason separately about these two components as
follows:

  * •

Using the decomposition $\mathbf{A}=\mathbf{T}\mathbf{M}$ for a random (dense)
$\mathbf{T}$ and sparse $\mathbf{M}$, it suffices to have
$\mathbf{x}^{\prime}=\mathbf{M}\mathbf{x}$ lose information about
$\mathbf{x}$. This is satisfied in the compression regime for Sparse LPN where
Equation 2 requires $t=\Omega\left(n\cdot(n/m)^{\frac{1}{Dk-1}}\right)$ for a
compression factor $D>1$.

  * •

For a fixed value $\mathbf{y}_{1}$, we can see that
$\mathbf{y}_{2}=\mathbf{S}\mathbf{y}_{1}+\mathbf{E}\mathbf{x}$ lies in a
Hamming ball of radius $\lVert\mathbf{E}\mathbf{x}\rVert_{0}$ around
$\mathbf{S}\mathbf{y}_{1}$. If we work with error probability $\epsilon$, then
$\mathbf{E}\leftarrow\mathsf{Ber}(\epsilon)^{\ell\times m}$ and
$\lVert\mathbf{x}\rVert_{0}=t$ implies that
$\mathbf{E}\mathbf{x}\sim\mathsf{Ber}(\epsilon^{\prime})^{\ell}$, where
$\epsilon^{\prime}=\frac{1-(1-2\epsilon)^{t}}{2}\leq\epsilon t$. We want the
size of this ball, which is roughly ${\ell\choose\epsilon t\ell}$, to be at
most a $(D^{\prime})^{th}$-root of the number of inputs which is ${m\choose
t}$.

Putting things together, we have that

$\displaystyle\lvert\\{(\mathbf{A}\mathbf{x},\mathbf{B}\mathbf{x})\mid\lVert\mathbf{x}\rVert_{0}=t\\}\rvert<{m\choose
t}^{1/D}\cdot{m\choose t}^{1/D^{\prime}}={m\choose t}^{1/D+1/D^{\prime}}.$ (4)

Therefore, we can ensure that the output length is an arbitrarily small
constant of the input length by setting $D,D^{\prime}$ to be large enough,
with error probability $\epsilon=O(1/t)$ and $\ell=\Theta(\log{m\choose
t})=\Theta(t\log n)$.

##### Injective Mode.

Do the parameters required for lossy mode also enable efficient inversion? To
answer this, we need to design a matrix
$\mathbf{C}\in\mathbb{F}_{2}^{\ell\times m}$ equipped with an efficient
decoding algorithm that can recover a $t$-sparse vector $\mathbf{x}$ from
$\mathbf{y}^{\prime}=\mathbf{C}\mathbf{x}+\mathbf{e}\in\mathbb{F}_{2}^{\ell}$,
where $\mathbf{e}=\mathbf{E}\mathbf{x}$ is a noise term that is constant-
fraction sparse with overwhelming probability.

If our task were to recover a (dense) vector $\mathbf{x}$, then we can simply
pick $\mathbf{C}$ to be (the transpose of) an error-correcting code. Then
$\mathbf{C}\mathbf{x}$ is (the transpose of) a codeword, which is then
perturbed in a constant number of entries to form $\bm{y}^{\prime}$. Using an
efficient decoding algorithm for $\mathbf{C}$ that can correct a constant
fraction of errors, we can recover $\mathbf{x}$ from $\mathbf{y}^{\prime}$.

However, in our case we have to recover a $t$-sparse vector
$\mathbf{x}\in\mathbb{F}_{2}^{m}$. Our idea is to restrict the inversion
process to only a _special_ subset of such $t$-sparse vectors, namely the ones
that arise as the result of _sparsifying_ dense vectors
$\mathbf{z}\in\mathbb{F}_{2}^{t\log(\frac{m}{t})}$. The sparsification process
is as follows:

$\displaystyle\mathbf{z}=[\underbrace{\mathbf{z}_{1}}_{\log(\frac{m}{t})}\|\dots\|\underbrace{\mathbf{z}_{t}}_{\log(\frac{m}{t})}]\quad\implies\quad\mathsf{spfy}(\mathbf{z})=[\underbrace{(0,\dots,1,\dots,0)}_{\mathbf{z}_{1}\text{-th
position}}\|\dots\|\underbrace{(0,\dots,1,\dots,0)}_{\mathbf{z}_{t}\text{-th
position}}]\in\mathbb{F}_{2}^{m},$

where we interpret $\mathbf{z}_{i}\in\mathbb{F}_{2}^{\log(\frac{m}{t})}$ as a
number in $\\{0,\dots,\frac{m}{t}-1\\}$ for all $i\in[t]$. This gives a
bijection between binary vectors of length $t\log(\frac{m}{t})$, with
_regular_ $t$-sparse vectors of length $m$. We may also recover $\mathbf{z}$
from $\mathsf{spfy}(\mathbf{z})$ by multiplying with a _gadget matrix_
$\mathbf{G}\in\mathbb{F}_{2}^{t\log(\frac{m}{t})\times m}$ (whose formula can
be found in Definition 3.2). In other words, we have
$\mathbf{G}\cdot\mathsf{spfy}(\mathbf{z})=\mathbf{z}$ for all
$\mathbf{z}\in\mathbb{F}_{2}^{t\log(\frac{m}{t})}$. Note that these procedures
have appeared in prior works [BLVW19, YZW+19], and can be seen as a code-based
analogue of binary decomposition and the gadget matrix in lattice-based
cryptography [MP12].

Given these tools, we can instantiate the injective mode as follows. We first
slightly change the input space of our function to be regular $t$-sparse
vectors $\mathbf{x}\in\mathbb{F}_{2}^{m}$, which are in bijection with
$\mathbf{z}=\mathbf{G}\mathbf{x}\in\mathbb{F}_{2}^{t\log(\frac{m}{t})}$. We
now set

$\displaystyle\mathbf{C}=\mathbf{C}^{\prime}\cdot\mathbf{G},$

where $\mathbf{C}^{\prime}\in\mathbb{F}_{2}^{\ell\times t\log(\frac{m}{t})}$
is the transpose of an error-correcting code with constant rate and distance
[Jus72]. Therefore, using the decoding of $\mathbf{C}^{\prime}$ we may
efficiently recover $\mathbf{z}$, and hence
$\mathbf{x}=\mathsf{spfy}(\mathbf{z})$, from
$\mathbf{y}^{\prime}=\mathbf{C}\mathbf{x}+\mathbf{e}=\mathbf{C}^{\prime}\mathbf{G}\mathbf{x}+\mathbf{e}=\mathbf{C}^{\prime}\mathbf{z}+\mathbf{e}$.

##### All-but-one LTDFs.

Our LTDF construction also generalize straightforwardly to realizing its _all-
but-one (ABO)_ variant. In an ABO-LTDF, we have an exponential of branches
${\cal B}=\mathbb{F}_{2}^{L}$ where one distinguished branch $b^{*}$ is lossy,
and all other branches are injective. Additionally, given the function key
$\mathsf{fk}$ it is difficult to find out which branch is distinguished. While
there is a generic transformation from LTDFs to its all-but-one version
[PW08], it presents a tradeoff between the number of branches supported and
the degradation of the lossiness parameter.

We avoid this tradeoff by leveraging algebraic properties in our setting. In
particular, we achieve ABO-LTDFs with number of branches $2^{L}$, where
$L=t\log(\frac{m}{t})$, through a simple twist on our construction above. At a
high level, we associate the branches
$b\in\mathbb{F}_{2}^{t\log(\frac{m}{t})}$ with a matrix family
$\mathbf{H}_{b}\in\mathbb{F}_{2}^{L\times L}$ such that
$\mathbf{H}_{b}-\mathbf{H}_{b^{\prime}}$ is invertible for all $b\neq
b^{\prime}$. Such a _full-rank difference (FRD)_ family of matrices has
appeared in prior works [ABB10, KMP14], and we refer to Section 6 for the
details of our ABO construction.

##### Why Low-Noise LPN does not Suffice.

As a final remark, let us argue why LPN with noise probability
$\epsilon=O(\log^{2}n/n)$ does not imply lossy trapdoor functions from our
template above. The reason is that since $\epsilon t=O(\log n)$, the vector
$\mathbf{E}\mathbf{x}$, with
$\mathbf{E}\leftarrow\mathsf{Ber}(\epsilon)^{\ell\times m}$ and
$\lVert\mathbf{x}\rVert_{0}=t$, is Bernoulli distributed with error
$\epsilon^{\prime}=\frac{1}{2}-\frac{1}{\operatorname{\mathsf{poly}}(n)}$.
This requires setting $\ell=n^{1+\Omega(1)}$ for successful inversion in
injective mode.777Error-correcting codes of relative distance
$\frac{1}{2}-\frac{1}{\operatorname{\mathsf{poly}}(n)}$ must have rate at most
$1/\operatorname{\mathsf{poly}}(n)$, so we have $\ell=n^{1+\Omega(1)}$.
However, such a large $\ell$ prevents any hope of achieving lossiness, as the
Hamming ball around each $\mathbf{y}_{1}$ is simply too large:

$\displaystyle{\ell\choose\epsilon^{\prime}\ell}=2^{n^{1+\Omega(1)}}\gg
2^{O(n)}={m\choose t}.$ (5)

###  2.3 Discussion on Our Assumption

We now discuss several aspects of our Dense-Sparse LPN assumption. Since our
assumption combines aspects of both standard LPN and Sparse LPN, it also
inherits some subtle considerations that arise in the context of choosing
“good” matrices for Sparse LPN.

##### Sampling “Good” Matrices for Sparse LPN.

In the Sparse LPN assumption, the matrix $\mathbf{M}$ is chosen in
$\mathbb{F}^{n\times m}_{2}$, where $m\ll n^{\frac{k}{2}}$, such that every
column is $k$-sparse where $k$ is some constant. For this parameter setting,
there is an inverse polynomial probability of $\mathbf{M}$ having a constant-
sparse vector $\mathbf{x}$ in its kernel, so that
$\mathbf{M}\mathbf{x}=\mathbf{0}$.888For instance, $\mathbf{M}$ has two
identical columns with probability $O(\frac{m^{2}}{n^{k}})$. When this “bad”
event happens, an adversary can find $\mathbf{x}$ in polynomial time and
distinguish Sparse LPN samples from random.

However, this “bad” event is only over the choice of matrix $\mathbf{M}$.
Outside of this bad event, it is known that if
$m=\widetilde{O}(n^{1+(\frac{k}{2}-1)(1-\rho)})$ for some $\rho>0$, then with
overwhelming probability, the minimum Hamming weight for a vector $\mathbf{x}$
that satisfies $\mathbf{M}\mathbf{x}=\mathbf{0}$ is at least $O(n^{\rho})$
(see Lemma 7.1 for details). Therefore, if we consider Sparse LPN with a large
enough noise probability $\epsilon=O(n^{-\rho})$, giving an adversary
subexponential time do not seem to increase its advantage beyond the
probability of sampling a “bad” matrix.

We note that this issue is present in all prior cryptographic constructions
relying on Sparse LPN. Applebaum, Barak and Wigderson [ABW10] resolved this
issue by weakening the indistinguishability advantage to be only $o(1)$; this
suffices for their application of building public-key encryption, as they
could rely on security amplification [HR05]. However, our goal is to build
lossy primitives, which do not amplify well [PRS12], so we must rely on a
sampling $\mathbf{M}$ from a distribution that avoids sampling a “bad” matrix
with overwhelming probability. We will use the following efficiently
sampleable distribution from [AK19] which has this property.

######  Theorem 2.1 (informal).

For every even $k\geq 6$, every $1<c<k/4$, and every $0<\gamma<k-4c$, there
exists an efficiently sampleable distribution of $k$-sparse matrices
$\mathbf{M}\in\mathbb{F}_{2}^{n\times n^{c}}$ such that with overwhelming
probability, every nonzero vector $\mathbf{x}$ in the kernel of $\mathbf{M}$
has Hamming weight at least $O(n^{\delta})$, where
$\delta=\frac{k-4c-\gamma}{k-\gamma-4}$.

While this distribution does not sample matrix from all possible parameter
regime of Sparse LPN (for instance, we have $m=n^{c}<n^{k/4}$), it suffices to
instantiate the compression regime in Equation 2 with any compression factor
$D>1$, where the noise probability remains inverse polynomial and we have
plausible security against subexponential time attacks. Therefore, we can use
this distribution to instantiate the sparse matrix $\mathbf{M}$ in our Dense-
Sparse LPN assumption.

##### Almost-Subexponential Regime.

Alternatively, we can work with a $k$ that is mildly super-constant, such as
$k=\log\log n$. In this setting, $m=n^{c}$ can be an arbitrary polynomial in
$n$, and the “bad” matrix probability is now negligible, namely
$n^{-O(\log\log n)}$. This allows us to sidestep the need for special
distributions, and just sample $\mathbf{M}$ uniformly at random from the set
of $k$-sparse matrices. Equation 2 now implies that we can achieve compression
factor $D>1$ when

$\displaystyle
t=O\left(\left(\frac{n^{Dk}}{m}\right)^{\frac{1}{Dk-1}}\right)=n^{1-O\left(\frac{1}{\log\log
n}\right)}.$ (6)

Thus, in our construction of LTDFs, we can rely on Dense-Sparse LPN with error
probability $\epsilon=O(1/t)=n^{-O\left(\frac{1}{\log\log n}\right)}$ which is
_inverse almost-polynomial_. Note that this noise probability is still larger
than the $O(\frac{\log^{2}n}{n})$ noise rate of (standard) LPN. Therefore, our
Dense-Sparse LPN assumption with this error rate is plausibly secure against
_almost-subexponential_ $2^{n^{O\left(\frac{1}{\log\log n}\right)}}$-time
attacks, unlike the quasi-polynomial security of (standard) LPN in its
compression regime.

##### A Stronger Variant of Our Assumption.

Finally, we can consider making a stronger assumption that together with
(standard) LPN implies Dense-Sparse LPN. In this variant, we now assume that
the matrix $\mathbf{A}=\mathbf{T}\mathbf{M}$ from the Dense-Sparse matrix
distribution is actually _pseudorandom_.

######  Assumption 2.1 (Dense-Sparse Indistinguishability).

For $\mathbf{T}\leftarrow\mathbb{F}_{2}^{\frac{n}{2}\times n}$,
$\mathbf{M}\leftarrow\mathbb{F}_{2}^{n\times m}$ drawn from a good
distribution of $k$-sparse matrices, and
$\mathbf{U}\leftarrow\mathbb{F}_{2}^{\frac{n}{2}\times m}$, we have
$\mathbf{T}\mathbf{M}\approx_{c}\mathbf{U}$.

By a simple hybrid argument, Assumption 2.1 together with (standard) LPN
indeed implies Dense-Sparse LPN with noise rate as small as
$O(\frac{\log^{2}n}{n})$. We do not see any better attack against this
assumption than against Dense-Sparse LPN, and refer to Section 7 for initial
cryptanalysis regarding this assumption.

###  2.4 Open Questions

At a high level, our Dense-Sparse LPN assumption is designed specifically so
that we can harness the lossiness property of the $k$-sparse matrix
$\mathbf{M}$, and do so without losing security by applying a random
compressing matrix $\mathbf{T}$ before giving out
$\mathbf{A}=\mathbf{T}\mathbf{M}$. In our construction of collision-resistant
hash functions (CRHFs), we even managed to convert this lossiness into actual
compression of the output. However, it seems difficult to achieve compression
directly without giving up on other properties of the assumption.

Let us explain this difficulty by attempting to construct a (single-server)
private information retrieval (PIR) scheme [CGKS95, KO97].999It is not known
whether lossy trapdoor functions imply PIR, nor is there a black-box
separation between two primitives. In PIR, we have a server holding a database
$\mathbf{D}\in\mathbb{F}_{2}^{n}$, and a client who wishes to learn the $i$-th
entry $\mathbf{D}_{i}$ of $\mathbf{D}$ without revealing the index $i$. A
client will send a query $\mathbf{q}$ to the server, who then responds with a
response $\mathbf{r}$. A non-trivial PIR scheme requires _compactness_ ,
namely that the response length is less than the database length.

We now consider the following candidate PIR scheme from Dense-Sparse LPN,
which borrows from our construction of LTDFs and the template in [KO97].
Assume for simplicity that the database $\mathbf{D}\in\mathbb{F}_{2}^{m}$ is
$t$-sparse (the general case can be reduced to this setting by
sparsification). To make a query on index $i\in[m]$, the client will send an
encryption

$\displaystyle\mathbf{q}=(\mathbf{A},\mathbf{b}=\mathbf{s}\mathbf{A}+\mathbf{e}+\mathbf{u}_{i}),\quad\text{
where
}\quad\mathbf{A}=\mathbf{T}\mathbf{M}\in\mathbb{F}_{2}^{\frac{n}{2}\times
m}\quad\text{ and
}\quad\mathbf{u}_{i}=\underbrace{(0,\dots,1,\dots,0)}_{i\text{-th position}}.$

The server will respond with the ciphertext applied to $\mathbf{D}$, i.e. with
$\mathbf{r}=(\mathbf{r}_{1},\mathbf{r}_{2})=(\mathbf{A}\mathbf{D},\mathbf{b}\mathbf{D})\in\mathbb{F}_{2}^{\frac{n}{2}+1}$.
The client then recovers
$\mathbf{D}_{i}=\langle\mathbf{D},\mathbf{u}_{i}\rangle$ by computing
$\mathbf{r}_{2}-\mathbf{s}\mathbf{r}_{1}=\mathbf{D}\mathbf{u}_{i}+\mathbf{D}\mathbf{e}$.
By sampling $\mathbf{e}$ from a Bernoulli distribution of probability
$\epsilon=O(1/t)$, we can guarantee that the scheme has constant correctness,
which can be amplified to negligible by $\omega(\log n)$ repetitions of
$\mathbf{b}$. Client’s query privacy also follows directly from Dense-Sparse
LPN with noise rate $\epsilon$.

The problem with the scheme above is that it is not compact. Indeed, the
response is of length $\frac{n}{2}+1$ which is greater than the database
length $\log{m\choose t}\approx t\log(m/t)$. Here, we are in a similar
situation to our CRHF construction, but we _cannot_ use the same trick to
achieve compactness here. The reason is that, if we were to multiply
$\mathbf{r}_{1}=\mathbf{A}\mathbf{D}$ by a further compressing matrix
$\mathbf{U}\in\mathbb{F}_{2}^{\ell\times\frac{n}{2}}$, then the client would
receive $\mathbf{U}\mathbf{A}\mathbf{D}$. From there, the client must
“decompress” $\mathbf{A}\mathbf{D}$ from $\mathbf{U}$, but this appears
computationally infeasible since $\mathbf{U}$ does not come with a trapdoor
for efficient inversion!

We note that the same difficulty above also prevents us from using Dense-
Sparse LPN to build laconic oblivious transfer and identity-based encryption
[BLSV18]. Therefore, we leave as open question the task of overcoming these
limitations, either by finding a way to efficiently compress and decompress
$\mathbf{A}\mathbf{x}$ for a random $t$-sparse $\mathbf{x}$, or by proposing a
different LPN variant that avoids this issue entirely.

##  3 Preliminaries

##### Notation.

Let $\mathbb{N}=\\{1,2,\dots\\}$ be the natural numbers, and define
$[a,b]:=\\{a,a+1,\dots,b\\}$, $[n]:=[1,n]$. Our logarithms are in base $2$.
For a finite set $S$, we write $x\overset{}{\leftarrow}S$ to denote uniformly
sampling $x$ from $S$. We denote the security parameter by $\lambda$; our
parameters depend on $\lambda$, e.g. $n=n(\lambda)$, and we often drop the
explicit dependence.

We abbreviate PPT for probabilistic polynomial-time. Our adversaries are non-
uniform PPT, or equivalently, polynomial-sized, ensembles ${\cal A}=\\{{\cal
A}_{\lambda}\\}_{\lambda\in\mathbb{N}}$. We write $\mathsf{negl}(\lambda)$ to
denote a negligible function in $\lambda$. Two ensembles of distributions
$\\{{\cal D}_{\lambda}\\}_{\lambda\in\mathbb{N}}$ and $\\{{\cal
D}^{\prime}_{\lambda}\\}_{\lambda\in\mathbb{N}}$ are computationally
indistinguishable if for any non-uniform PPT adversary ${\cal A}$ there exists
a negligible function $\mathsf{negl}$ such that ${\cal A}$ can distinguish
between the two distributions with probability at most
$\mathsf{negl}(\lambda)$.

For $q\in\mathbb{N}$ that is a prime power, we write $\mathbb{F}_{q}$ to
denote the finite field with $q$ elements, and $\mathbb{F}_{q}^{\times}$ to
denote its non-zero elements. We write vectors and matrices in boldcase, e.g.
$\mathbf{v}\in\mathbb{F}_{q}^{m}$ and $\mathbf{A}\in\mathbb{F}_{q}^{n\times
m}$. Given $\mathbf{v}\in\mathbb{F}_{q}^{m}$, we define the Hamming weight
$\mathsf{wt}(\mathbf{v})$, also denoted $\lVert\mathbf{v}\rVert_{0}$, to be
the number of non-zero entries of $\mathbf{v}$.

##### Bernoulli Distribution.

We denote the Bernoulli distribution over a finite field $\mathbb{F}_{q}$ with
noise rate $\epsilon\in(0,1)$ by $\mathsf{Ber}(\mathbb{F}_{q},\epsilon)$; this
distribution gives $0$ with probability $1-\epsilon$, and a random non-zero
element of $\mathbb{F}_{q}$ with probability $\epsilon$. We write
$e\sim\mathsf{Ber}(\mathbb{F}_{q},\epsilon)$ to denote that $e$ comes from the
corresponding Bernoulli distribution. When $q=2$, we omit $\mathbb{F}_{q}$ and
simply write $\mathsf{Ber}(\epsilon)$.

######  Definition 3.1 (Bias).

Let $\mathbb{F}$ be a finite field. Given a distribution $\mathcal{D}$ over
$\mathbb{F}^{m}$ and a vector $\mathbf{u}\in\mathbb{F}^{m}$, we define the
_bias_ of $\mathcal{D}$ with respect to $\mathbf{u}$ to be

$\displaystyle\mathsf{bias}_{\mathbf{u}}(\mathcal{D}):=\left|\operatorname*{\mathbb{E}}_{\mathbf{x}\sim{\cal
D}}\left[\langle\mathbf{u},\mathbf{x}\rangle\right]-\frac{1}{\lvert\mathbb{F}\rvert}\right|.$

The _bias_ of $\mathcal{D}$ is defined as
$\mathsf{bias}(\mathcal{D})=\max_{\mathbf{u}\neq\mathbf{0}}\mathsf{bias}_{\mathbf{u}}(\mathcal{D})$.

######  Lemma 3.1 (Bias of the Bernoulli distribution).

For any finite field $\mathbb{F}_{q}$, noise rate $\epsilon\in(0,1)$, and
$d\in\mathbb{N}$, consider the noise distribution
$\mathcal{D}_{m,n}=(\mathsf{Ber}(\mathbb{F}_{q},\epsilon))^{m}$. Then
$\epsilon_{d}=\left(1-\frac{q}{q-1}\epsilon\right)^{d}$.

As a special case when $q=2$, we have the piling-up lemma.

######  Lemma 3.2 (Piling-Up Lemma).

For any $\epsilon\in(0,1)$, we have that

$\Pr\left[\sum_{i=1}^{\ell}e_{i}=1\;\middle|\;e_{1},\dots,e_{\ell}\leftarrow\mathsf{Ber}(\epsilon)\right]=\frac{1-(1-2\epsilon)^{\ell}}{2}<\min\left(\epsilon\ell,\frac{1}{2}-2^{-4\epsilon\ell-1}\right).$

##### Tail Bounds.

We also state some standard tail bounds for binary variables.

######  Lemma 3.3 (Chernoff/Hoeffding bound).

Let $X_{1},\dots,X_{n}\in\\{0,1\\}$ be i.i.d random variables with mean at
most $\epsilon$. Then for every $\kappa>1$,

$\Pr[X_{1}+\dots+X_{n}>(1+\kappa)\epsilon n]\leq e^{-2\kappa^{2}\epsilon n}.$

##### Binomial Approximation.

We will use the following basic approximations of the binomial coefficient,
which can be found in e.g. [CLRS22]. Namely, for any $1\leq k\leq n/2$, we
have

$\left(\frac{n}{k}\right)^{k}\leq{n\choose
k}\leq\left(\frac{en}{k}\right)^{k}.$ (7)

##### Hamming Balls.

Given $n,w\in\mathbb{N}$ with $w\leq n$, we define the following sets:

  * •

${\cal
B}_{\leq}(n,w)=\\{\mathbf{x}\in\\{0,1\\}^{n}\mid\mathsf{wt}(\mathbf{x})\leq
w\\}$,

  * •

${\cal B}(n,w)=\\{\mathbf{x}\in\\{0,1\\}^{n}\mid\mathsf{wt}(\mathbf{x})=w\\}$,

  * •

${\cal
B}_{\mathsf{reg}}(n,w)=\\{\mathbf{x}=\mathbf{x}_{1}\|\dots\|\mathbf{x}_{w}\in\\{0,1\\}^{n}\mid\mathbf{x}_{i}\in\\{0,1\\}^{n/w}\,\land\,\mathsf{wt}(\mathbf{x}_{i})=1\;\forall\,i\in[w]\\}$,
for any $w$ dividing $n$.

Their sizes are as follows.

######  Lemma 3.4.

For any $w<n/3$, we have the following:

  * •

$\lvert{\cal B}_{\leq}(n,w)\rvert=\sum_{t=0}^{w}{n\choose t}\in\left({n\choose
w},2{n\choose w}\right)$.

  * •

$\lvert{\cal B}(n,w)\rvert={n\choose
w}\in\left(2^{w\log(n/w)},2^{w\log(en/w)}\right)$.

  * •

$\lvert{\cal
B}_{\mathsf{reg}}(n,w)\rvert=\left(\frac{n}{w}\right)^{w}=2^{w\log(n/w)}$.

Thus, we have that $\lvert{\cal B}_{\mathsf{reg}}(n,w)\rvert<\lvert{\cal
B}(n,w)\rvert<\lvert{\cal B}_{\leq}(n,w)\rvert<2^{w\log e+1}\cdot\lvert{\cal
B}_{\mathsf{reg}}(n,w)\rvert$.

###### Proof.

The only non-trivial claim is that $\sum_{t=0}^{w}{n\choose t}<2{n\choose w}$.
This follows from the fact that ${n\choose t-1}=\frac{t}{n-t+1}{n\choose
t}<\frac{1}{2}{n\choose t}$ for all $t<n/3$, and hence
$\sum_{t=0}^{w}{n\choose
t}<\left(1+\frac{1}{2}+\left(\frac{1}{2}\right)^{2}+\dots\right){n\choose
w}=2{n\choose w}$. ∎

##### Sparsification and the Gadget Matrix.

We describe an LPN analogue to the LWE gadget matrix [MP12], based on the idea
of sparsification.

Given any $s\in\mathbb{N}$, we denote by
$\mathsf{bin}_{s}:[0,2^{s}-1]\to\\{0,1\\}^{s}$ the binary decomposition
function, and $\mathsf{bin}_{s}^{-1}:\\{0,1\\}^{s}\to[0,2^{s}-1]$ its inverse.
Given any $\mathbf{v}\in\\{0,1\\}^{s}$, we define $\mathsf{ind}(\mathbf{v})$
to be the vector of length $2^{s}$ (indexed from $0$) consisting of all zeros,
except for the $\mathsf{bin}_{s}^{-1}(\mathbf{v})$-th entry being $1$.

######  Definition 3.2.

Let $n,w\in\mathbb{N}$ with $w\leq n$, and define $\widetilde{w}=w\log(n/w)$.
Given $\mathbf{x}\in\\{0,1\\}^{\widetilde{w}}$ divided into $w$ blocks of size
$s=\log(n/w)$, so that $\mathbf{x}=\mathbf{x}_{1}\|\dots\|\mathbf{x}_{w}$, we
define its _$(n,w)$ -sparsification_ $\mathsf{spfy}_{n,w}(\mathbf{x})$ to be

$\mathsf{spfy}_{n,w}(\mathbf{x}):=\mathsf{ind}(\mathbf{x}_{1})\|\dots\|\mathsf{ind}(\mathbf{x}_{w})\in\\{0,1\\}^{n}.$

We also define the _$(n,w)$ -gadget matrix_ $\mathbf{G}_{n,w}$ to be

$\mathbf{G}_{n,w}:=\mathbf{g}_{s}\otimes\mathbf{I}_{w}\in\\{0,1\\}^{w\times
n},\quad\text{where
}\mathbf{g}_{s}:=\left[\mathsf{bin}_{s}(0)\|\mathsf{bin}_{s}(1)\|\dots\|\mathsf{bin}_{s}(2^{s}-1)\right],$

and $\mathbf{I}_{w}$ is the identity matrix of dimension $w$. For convenience,
we also refer to $\mathsf{spfy}_{n,w}$ as $\mathbf{G}_{n,w}^{-1}$, and omit
the subscripts $n,w$ when they are clear from context.

We can easily check that

$\displaystyle\mathbf{G}_{n,w}\cdot\mathbf{G}_{n,w}^{-1}(\mathbf{x})=\mathbf{G}_{n,w}\cdot\mathsf{spfy}_{n,w}(\mathbf{x})=\mathbf{x}.$
(8)

Note that for the dimensions of $\mathbf{G}_{n,w}$ to satisfy
$n=\operatorname{\mathsf{poly}}(w)$, we need $s\leq c\log w$ for some constant
$c$. We also get the following identity for any
$\mathbf{x},\mathbf{y}\in\\{0,1\\}^{\widetilde{w}}$:

$\displaystyle\langle\mathbf{x},\mathbf{y}\rangle=\left\langle\mathbf{x},\mathbf{G}_{n,w}\cdot\mathsf{spfy}_{n,w}(\mathbf{y})\right\rangle=\left\langle\mathbf{G}_{n,w}^{\mathsf{T}}\cdot\mathbf{x},\mathsf{spfy}_{n,w}(\mathbf{y})\right\rangle.$
(9)

###  3.1 Coding Theory

######  Definition 3.3 (Dual Distance).

Let $\mathbb{F}_{q}$ be a finite field and $n<m\in\mathbb{N}$. The _dual
distance_ of a matrix $\mathbf{A}\in\mathbb{F}_{q}^{n\times m}$, denoted
$\mathsf{dd}(\mathbf{A})$, is defined to be minimum sparsity of a vector
$\mathbf{x}\in\mathbb{F}_{q}^{m}$ in the kernel of $\mathbf{A}$. In other
words, we define
$\mathsf{dd}(\mathbf{A})=\min\\{\mathsf{wt}(\mathbf{x})\mid\mathbf{A}\mathbf{x}=\mathbf{0}\\}$.

######  Definition 3.4 ($q$-ary Entropy).

For any $x\in(0,1)$, we define the $q$-ary entropy function to be
$H_{q}(x)=x\log_{q}(q-1)-x\log_{q}x-(1-x)\log_{q}(1-x)$. We denote binary
entropy by $H(x)$.

The following standard results can be found in coding theory textbooks, e.g.
[GRS12].

######  Lemma 3.5 (Entropy Approximation).

For any $\delta\in(0,1)$, we have that
$\delta\log(1/\delta)<H(\delta)<\delta\log(4/\delta)$.

######  Lemma 3.6 (Gilbert-Varshamov Bound).

Let $\mathbb{F}_{q}$ be a finite field. For every $\delta\in(0,1-1/q)$ and
every $\epsilon\in(0,1-H_{q}(\delta))$, letting
$k=\lfloor(1-H_{q}(\delta)-\epsilon)\cdot n\rfloor$, a random matrix
$\mathbf{G}\leftarrow\mathbb{F}_{q}^{k\times n}$ generates a $q$-ary linear
code of distance at least $\delta n$ with probability at least $1-q^{-\epsilon
n}$.

Equivalently, for $\ell=\lceil(H_{q}(\delta)+\epsilon)\cdot n\rceil$, a random
matrix $\mathbf{H}\leftarrow\mathbb{F}_{q}^{\ell\times n}$ is a parity-check
matrix for a $q$-ary linear code of distance at least $\delta n$ with
probability at least $1-q^{-\epsilon n}$.

######  Lemma 3.7 (Asymptotically Good Codes).

For some constants $\delta,\rho>0$, there exists an explicit construction of a
family of binary codes $\\{\mathbf{C}_{n}\\}_{n\in\mathbb{N}}$ with block
length $N(n)$ (bounded by some fixed polynomial in $n$), rate $\rho$, and
supporting efficient error correction for up to $\delta n$ errors.

##  4 Our Code-Based Assumption: Dense-Sparse LPN

In this section, we define our main assumption, Dense-Sparse LPN. To do so, we
will first define a general LPN assumption with an arbitrary distribution of
coefficient matrix.

######  Definition 4.1 (Decisional $({\cal M},\epsilon)$-LPN).

Let $n\in\mathbb{N}$ be the dimension, $m=m(n)$ be the number of samples,
$\epsilon=\epsilon(n)\in(0,1)$ be the noise rate, and $q=q(n)$ be a prime
power. Given an efficiently sampleable distribution ${\cal M}={\cal
M}(n,m,\mathbb{F}_{q})$ over matrices in $\mathbb{F}_{q}^{n\times m}$, we say
that the _$({\cal M},\epsilon)$ -LPN assumption_ is $(T(n),\delta(n))$-hard if
for all adversary ${\cal A}$ running in time at most $T$, the following holds:

$\displaystyle\mathbf{Adv}^{\mathsf{LPN}}_{n,m,q,{\cal M},\epsilon}({\cal
A}):=\left|\begin{aligned} &\Pr\left[{\cal
A}(\mathbf{A},\mathbf{s}\mathbf{A}+\mathbf{e})=1\;\middle|\;\mathbf{A}\leftarrow{\cal
M},\mathbf{s}\leftarrow\mathbb{F}_{q}^{1\times
n},\mathbf{e}\leftarrow\mathsf{Ber}(\mathbb{F}_{q},\epsilon)^{1\times
m}\right]\\\ -\;&\Pr\left[{\cal
A}(\mathbf{A},\mathbf{u})=1\;\middle|\;\mathbf{A}\leftarrow{\cal
M},\mathbf{u}\leftarrow\mathbb{F}_{q}^{1\times
m}\right]\end{aligned}\right|\leq\delta.$

We say that $({\cal M},\epsilon)\text{-}\mathsf{LPN}$ is _polynomially hard_
if for every polynomial $p(n)$, there exists a negligible function
$\mathsf{negl}(n)$ such that it is $(p(n),\mathsf{negl}(n))$-hard. Similarly,
$({\cal M},\epsilon)\text{-}\mathsf{LPN}$ is _subexponentially hard_ if there
exists a constant $0<c<1$ and a negligible function $\mathsf{negl}(n)$ such
that it is $(2^{n^{c}},\mathsf{negl}(n))$-hard.

######  Definition 4.2 (Decisional $({\cal M},\epsilon)$-Dual LPN).

Consider $n,m,q,{\cal M},\epsilon$ as in Definition 4.1. We say that the
_$({\cal M},\epsilon)$ -dual LPN assumption_ is $(T(n),\delta(n))$-hard if for
all adversary ${\cal A}$ running in time at most $T$, the following holds:

$\displaystyle\mathbf{Adv}^{\mathsf{dual}\text{-}\mathsf{LPN}}_{n,m,q,{\cal
M},\epsilon}({\cal A}):=\left|\begin{aligned} &\Pr\left[{\cal
A}(\mathbf{H},\mathbf{H}\mathbf{e})=1\;\middle|\;\mathbf{H}\leftarrow{\cal
M},\mathbf{e}\leftarrow\mathsf{Ber}(\mathbb{F}_{q},\epsilon)^{1\times
m}\right]\\\ -\;&\Pr\left[{\cal
A}(\mathbf{H},\mathbf{u})=1\;\middle|\;\mathbf{H}\leftarrow{\cal
M},\mathbf{u}\leftarrow\mathbb{F}_{q}^{1\times
m}\right]\end{aligned}\right|\leq\delta.$

We may define polynomial or subexponential hardness of $({\cal
M},\epsilon)\text{-}\mathsf{dual}\text{-}\mathsf{LPN}$ similar to Definition
4.1.

######  Remark 4.1.

For the rest of the paper, we will work over the binary field (so that $q=2$).
We note that our assumptions and constructions can be straightforwardly
generalized to work with any constant $q=O(1)$.

When ${\cal M}$ is the uniform distribution over $\mathbb{F}_{2}^{n\times m}$,
we recover the (standard) LPN assumption [BFKL94] (with Dual-LPN equivalent to
LPN). We now define variants of LPN with different matrix distributions ${\cal
M}$.

######  Definition 4.3 (Sparse LPN).

Let $k\in\mathbb{N}$ be a constant, and consider parameters $n\in\mathbb{N}$,
$m=m(n)<n^{k/2}$, and $\epsilon=\epsilon(n)<1$. Denote by
$\mathsf{SpMat}(n,m,k)$ the set of matrices
$\mathbf{A}\in\mathbb{F}_{2}^{n\times m}$ such that each column of
$\mathbf{A}$ has exactly $k$ non-zero entries.

We define the _$(n,m,k,\epsilon)$ -sparse LPN ($\mathsf{sLPN}$) assumption_ to
be the following: there exists an efficiently sampleable distribution ${\cal
M}_{\mathsf{sp}}$ over $\mathsf{SpMat}(n,m,k)$ such that the _$({\cal
M}_{\mathsf{sp}},\epsilon)\text{-}\mathsf{LPN}$_ assumption holds.

Note that the above assumption does not specify the exact distribution ${\cal
M}_{\mathsf{sp}}$ of sparse matrices. This is because the “canonical”
distribution ${\cal M}_{\mathsf{unif}}$ of sampling $k$-sparse columns
independently and uniformly at random do _not_ suffice for the above
assumption. The reason is that there is a noticeable probability, of roughly
$O(m^{2}/n^{k})$, for sampling a “bad” matrix $\mathbf{A}\leftarrow{\cal
M}_{\mathsf{unif}}$ with small dual distance, which would break the assumption
by giving the adversary a noticeable distinguishing advantage.

Motivated by this discussion, we lay out a necessary criteria for the sparse
matrix distribution ${\cal M}_{\mathsf{sp}}$ to satisfy the Sparse LPN
assumption.

######  Definition 4.4 (Sparse matrices with $\omega(1)$-dual distance).

For every $n\in\mathbb{N}$, $k=k(n)$, $m=m(n)<n^{k/2}$ and $d=\omega(1)$,
define
$\mathsf{SpMat}(n,m,k,d)=\\{\mathbf{A}\in\mathsf{SpMat}(n,m,k)\mid\mathsf{dd}(\mathbf{A})\geq
d\\}$ to be the subset of $\mathsf{SpMat}(n,m,k)$ consisting of matrices with
super-constant dual distance of at least $d$.

We say that an efficiently sampleable distribution ${\cal M}_{\mathsf{sp}}$
over $\mathsf{SpMat}(n,m,k)$ is _$(d,\delta)$ -good_ if

$\Pr[\mathbf{A}\not\in\mathsf{SpMat}(n,m,k,d)\mid\mathbf{A}\leftarrow{\cal
M}_{\mathsf{sp}}]\leq\delta.$

We say that ${\cal M}_{\mathsf{sp}}$ is _good_ if it is $(d,\delta)$-good for
some $d=\omega(1)$ and $\delta=\mathsf{negl}(n)$.

We may make the _conjecture_ that any such good distribution ${\cal
M}_{\mathsf{sp}}$ would give rise to a secure $\mathsf{sLPN}$ assumption. A
more conservative assumption would be to assume $\mathsf{sLPN}$ assumption
holds for _specific_ good distributions that have been constructed in the
literature. In our work, we will use the following distribution by Applebaum
and Kachlon [AK19].

######  Theorem 4.1 (Theorem 7.18 [AK19], adapted).

For every even $k\geq 6$, every $1<c<k/4$ with $\gamma=k-4c$, there exists an
efficiently computable, $\left(O(n^{\delta}),n^{-O\left(\frac{\log\log\log
n}{\log\log\log\log n}\right)}\right)$-good distribution over
$\mathsf{SpMat}(n,m,k)$, where $m=n^{c}$ and
$\delta=\frac{k-4c-\gamma}{k-\gamma-4}$. We call this the _AK19 distribution_.

Note that the AK19 distribution does not give us all possible parameter range
for $k$-sparse matrices. In particular, the number of samples $m$ is limited
to be at most $n^{k/4}$. However, the parameter regime that the AK19
distribution supports overlap with the compression regime of Lemma 4.1 for any
constant compression factor $D>1$. Therefore, we can indeed use this
distribution to instantiate our schemes and assumptions.

######  Definition 4.5 (Dense-Sparse LPN).

Let $k\in\mathbb{N}$, $\alpha\in(0,1)$ be constants, and consider parameters
$n\in\mathbb{N}$, $m=m(n)<n^{k/2}$, and $\epsilon=\epsilon(n)<1$. Let ${\cal
M}_{\mathsf{sp}}$ be a good distribution over $\mathsf{SpMat}(n,m,k)$. We
define the _$(n,m,k,{\cal M}_{\mathsf{sp}},\epsilon)$ -Dense-Sparse LPN
($\mathsf{DS}\text{-}\mathsf{LPN}$)_ assumption to be the $({\cal
M},\epsilon)$-LPN assumption, where ${\cal M}$ is the following distribution:

$\displaystyle{\cal
M}=\\{\mathbf{T}\cdot\mathbf{M}\mid\mathbf{T}\leftarrow\mathbb{F}_{2}^{\alpha
n\times n},\mathbf{M}\leftarrow{\cal M}_{\mathsf{sp}}\\}.$

In other words, we say that Dense-Sparse LPN is $(T(n),\delta(n))$-hard if the
following holds for every adversary ${\cal A}$ running in time at most $T$:

$\displaystyle\mathbf{Adv}^{\mathsf{DS}\text{-}\mathsf{LPN}}_{n,m,k,{\cal
M}_{\mathsf{sp}},\epsilon}({\cal A}):=\left|\Pr\left[{\cal
A}(\mathbf{A},\mathbf{s}\mathbf{A}+\mathbf{e})=1\right]-\Pr\left[{\cal
A}(\mathbf{A},\mathbf{u})=1\right]\right|\leq\delta,$

where $\mathbf{T}\leftarrow\mathbb{F}_{2}^{\alpha n\times n}$,
$\mathbf{M}\leftarrow{\cal M}_{\mathsf{sp}}$,
$\mathbf{A}=\mathbf{T}\cdot\mathbf{M}$,
$\mathbf{s}\leftarrow\mathbb{F}_{2}^{1\times\alpha n}$,
$\mathbf{e}\leftarrow\mathsf{Ber}(\epsilon)^{1\times m}$, and
$\mathbf{u}\leftarrow\mathbb{F}_{2}^{m}$.

To simplify notation, we will take $\alpha=1/2$ for all of our constructions,
though the assumption plausibly holds for any constant $\alpha\in(0,1)$. We
provide detailed cryptanalysis of Dense-Sparse LPN in Section 7.

######  Remark 4.2 (Dense-Sparse Dual-LPN).

It is plausible that the dual version of Dense-Sparse LPN also holds, namely
that

$\displaystyle\\{(\mathbf{T}\mathbf{M},\mathbf{T}\mathbf{M}\mathbf{e})\\}\approx_{c}\\{(\mathbf{T}\mathbf{M},\mathbf{u})\\}\quad\text{
for }\quad\text{$\mathbf{T}\leftarrow\mathbb{F}_{2}^{\alpha n\times n}$,
$\mathbf{M}\leftarrow{\cal M}_{\mathsf{sp}}$,
$\mathbf{e}\leftarrow\mathsf{Ber}(\epsilon)^{m\times 1}$, and
$\mathbf{u}\leftarrow\mathbb{F}_{2}^{\alpha n\times 1}$}.$

This is because $\mathbf{M}\mathbf{e}$ is roughly $O(kt)$-sparse, so that
plausibly
$(\mathbf{T},\mathbf{T}\mathbf{M}\mathbf{e})\approx_{c}(\mathbf{T},\mathbf{u})$
by dual-LPN for the random matrix $\mathbf{T}\in\mathbb{F}_{2}^{\alpha n\times
n}$.

Note that this is not yet a rigorous argument since the sparse vector
$\mathbf{M}\mathbf{e}$ is very far from being Bernoulli distributed. Since we
do not use Dense-Sparse dual-LPN in our constructions, we leave a more
rigorous cryptanalysis and further applications of this assumption to future
work.

##### Compression Regime.

We give here the parameter regime that allows for the function

$f_{\mathbf{M}}:{\cal B}_{\mathsf{reg}}(m,t)\to{\cal
B}_{\leq}(n,kt)\quad\text{ defined by }\quad
f_{\mathbf{M}}(\mathbf{x})=\mathbf{M}\cdot\mathbf{x},\quad\text{ for any
}\quad\mathbf{M}\in\mathsf{SpMat}(n,m,k),$

to be compressing (by some constant factor $D$ in the exponent).

######  Lemma 4.1.

Given constant $k\in\mathbb{N},k\geq 3$ and compression factor $D>1$, define
$\delta_{(\ref{lem:compress})}(k,D):=1-\frac{k/2-1}{Dk-1}$. For any
$\delta\in(\delta_{(\ref{lem:compress})}(k,D),1)$, any $n\in\mathbb{N}$ large
enough, and any $m<n^{k/2}$, letting $t=n^{\delta}$, we have the following:

$\displaystyle\lvert{\cal
B}_{\mathsf{reg}}(m,t)\rvert=2^{t\log(m/t)}>\left(2^{kt\log(en/kt)+1}\right)^{D}>\lvert{\cal
B}_{\leq}(n,kt)\rvert^{D}$ (10)

whenever $m>m_{(\ref{lem:compress})}(n,k,D,\delta):=n^{1+(Dk-1)(1-\delta)}$.

###### Proof.

Note that the last inequality in Equation 10 follows from Lemma 3.4. Thus it
suffices to show the central inequality. Taking the logarithms of both sides,
we need to show that

$\displaystyle t(\log m-\log t)>D\left(kt\log(en/kt)+1\right).$

Dividing by $t$ and isolating out $\log(m)$, we get

$\displaystyle\log m>D/t+\log(t)+Dk\log(en/kt),$

which is equivalent to

$\displaystyle m>2^{D/t}\cdot
t\cdot\left(\frac{en}{kt}\right)^{Dk}=2^{D/t}\cdot\left(\frac{e}{k}\right)^{Dk}\cdot\frac{n^{Dk}}{t^{Dk-1}}.$

Plugging in $t=n^{\delta}$ gives us

$\displaystyle m>2^{D/n^{\delta}}\cdot\left(\frac{e}{k}\right)^{Dk}\cdot
n^{1+(Dk-1)(1-\delta)}.$

Since $\lim_{n\to\infty}2^{D/n^{\delta}}=1$ and $e/k\leq e/3<1$, for $n$ large
enough we have

$2^{D/n^{\delta}}\cdot\left(\frac{e}{k}\right)^{Dk}<\left(\frac{e}{k}\right)^{-Dk}\cdot\left(\frac{e}{k}\right)^{Dk}=1.$

Therefore, Equation 10 is satisfied when $m>n^{1+(Dk-1)(1-\delta)}$. Finally,
since we need to impose the condition that $m<n^{k/2}$, it follows that
$\delta$ is at most $1-\frac{k/2-1}{Dk-1}=\delta_{(\ref{lem:compress})}(k,D)$.
∎

##  5 Collision-Resistant Hash Functions

In this section, we give a simple construction of collision-resistant hash
functions (CRHFs) from our Dense-Sparse LPN assumption. While lossy trapdoor
functions (LTDFs), which we construct in Section 6, are known to imply CRHFs
[PW08], the resulting construction is more complex than the one presented here
(and require a slightly smaller noise rate $\epsilon=O(1/n^{\delta})$ instead
of $\epsilon=O(\log n/n^{\delta})$).

Compared to prior LPN-based hashes [BLVW19, YZW+19], which rely on either
inverse quasi-polynomial noise rate $\epsilon=O(\log^{2}n/n)$ or sub-
exponential hardness, our construction only requires polynomial hardness and
sub-exponential noise rate $\epsilon=\widetilde{O}(n^{-\delta})$ for
$\mathsf{DS}\text{-}\mathsf{LPN}$, where $\delta$ is a constant that can be
arbitrarily close to $3/4$ (as $k\to\infty$).

######  Definition 5.1.

A _collision-resistant hash function (CRHF)_ family, with input length
$m(\lambda)$ and output length $n(\lambda)$, is a tuple of PPT algorithms
${\cal H}=(\mathsf{Gen},\mathsf{Hash})$ with the following properties:

  * •

Syntax:

    * –

$\mathsf{Gen}(1^{\lambda})\to\mathsf{k}$. On input the security parameter
$1^{\lambda}$, output a hash key $\mathsf{k}$.

    * –

$\mathsf{Hash}(\mathsf{k},\mathbf{x})$. On input the hash key $\mathsf{k}$ and
an input $\mathbf{x}\in\\{0,1\\}^{m(\lambda)}$, deterministically output
$\mathsf{h}\in\\{0,1\\}^{n(\lambda)}$.

  * •

Compression: We have $m(\lambda)>n(\lambda)+2\lambda$ for all
$\lambda\in\mathbb{N}$.

  * •

Collision-Resistance: For all polynomial-size adversary ${\cal A}$, the
following probability is negligible:

$\displaystyle\mathbf{Adv}^{\mathsf{CRHF}}({\cal
A}):=\Pr\left[\begin{gathered}\mathbf{x}_{1}\neq\mathbf{x}_{2}\quad\land\\\
\mathsf{Hash}(\mathsf{k},\mathbf{x}_{1})=\mathsf{Hash}(\mathsf{k},\mathbf{x}_{2})\end{gathered}\;\middle|\;\begin{aligned}
&\mathsf{k}\leftarrow\mathsf{Gen}(1^{\lambda})\\\
&(\mathbf{x}_{1},\mathbf{x}_{2})\leftarrow{\cal
A}(\mathsf{k})\end{aligned}\right]\leq\mathsf{negl}(\lambda).$

Parameters. • Pick any constant $k\in\mathbb{N},k\geq 3$, any constant $D>2$,
and any $\delta\in(\delta_{(\ref{lem:compress})}(k,D),1)$. Let
$\rho=1/2-1/D>0$. • Let $m>m_{(\ref{lem:compress})}(n,k,D,\delta)$,
$t=n^{\delta}$, and $\epsilon=O(\log n/t)$. Denote $\widetilde{t}=t\log(m/t)$.
Choose $n=(2\lambda/\rho)^{1/\delta}$ so that $\rho\widetilde{t}>\rho
n^{\delta}>2\lambda$. Let ${\cal M}_{\mathsf{sp}}$ be a good distribution over
$\mathsf{SpMat}(n,m,k)$. Construction. •
$\mathsf{Gen}(1^{\lambda})\to\mathsf{k}$. Sample
$\mathbf{H}\leftarrow\mathbb{F}_{2}^{(1-\rho)\widetilde{t}\times n}$, and
$\mathbf{M}\leftarrow{\cal M}_{\mathsf{sp}}$. Return
$\mathsf{k}=\mathbf{A}^{\prime}=\mathbf{H}\cdot\mathbf{M}$. •
$\mathsf{Hash}(\mathsf{k},\mathbf{x})\to\mathsf{h}$. On input
$\mathbf{x}\in\mathbb{F}_{2}^{\widetilde{t}}$, return
$\mathsf{h}=\mathbf{A}^{\prime}\cdot\mathsf{spfy}_{m,t}(\mathbf{x})\in\mathbb{F}_{2}^{(1-\rho)\widetilde{t}}$.
Figure 2: CRHF construction

######  Theorem 5.1.

Assuming the $(n,m,k,{\cal
M}_{\mathsf{sp}},\epsilon)$-$\mathsf{DS}\text{-}\mathsf{LPN}$ assumption
holds, where $n,m,k,{\cal M}_{\mathsf{sp}},\epsilon$ are defined as in Figure
2. Then Figure 2 gives a construction of a CRHF family.

###### Proof.

It is clear that we have compression, as the gap between input and output size
is $\widetilde{t}-(1-\rho)\widetilde{t}=\rho\widetilde{t}>2\lambda$ by our
parameter choice. It remains to show collision-resistance, which we show by
going through the following hybrids.

  * •

$\mathsf{Hyb}_{0}$: this is the CHRF game, where an adversary ${\cal A}$
receives $\mathbf{A}^{\prime}=\mathbf{H}\cdot\mathbf{M}$ and outputs
$\mathbf{x}_{1},\mathbf{x}_{2}\in\mathbb{F}_{2}^{t\log(m/t)}$. ${\cal A}$
wins, or equivalently $\mathsf{Hyb}_{0}$ returns $1$, if
$\mathbf{x}_{1}\neq\mathbf{x}_{2}$ and
$\mathbf{A}^{\prime}\cdot\mathsf{spfy}_{m,t}(\mathbf{x}_{1})=\mathbf{A}^{\prime}\cdot\mathsf{spfy}_{m,t}(\mathbf{x}_{2})$;
equivalently, when $\mathbf{A}^{\prime}\cdot\mathbf{x}^{\prime}=\mathbf{0}$
where
$\mathbf{x}^{\prime}=\mathsf{spfy}_{m,t}(\mathbf{x}_{1})-\mathsf{spfy}_{m,t}(\mathbf{x}_{2})$.

  * •

$\mathsf{Hyb}_{1}$: this is identical to $\mathsf{Hyb}_{0}$, except the
adversary ${\cal A}$ only wins if
$\mathbf{M}\cdot\mathbf{x}^{\prime}=\mathbf{0}$ (and also
$\mathbf{x}_{1}\neq\mathbf{x}_{2}$). Thus, $\mathsf{Hyb}_{2}$ differs from
$\mathsf{Hyb}_{1}$ only when
$\mathbf{M}\cdot\mathbf{x}^{\prime}\neq\mathbf{0}$ but
$\mathbf{H}\cdot(\mathbf{M}\cdot\mathbf{x}^{\prime})=\mathbf{0}$. Since
$\mathbf{y}=\mathbf{M}\cdot\mathbf{x}^{\prime}\in\mathbb{F}_{2}^{n}$ is at
most $2kt$-sparse, this amounts to bounding the probability that a random
parity-check matrix $\mathbf{H}\in\mathbb{F}_{2}^{(1-\rho)\widetilde{t}\times
n}$ has distance less than $2kt$.

We will show that this probability is negligible by examining our parameter
choices. By Lemma 3.5, we have that

$\displaystyle H\left(\frac{2kt}{n}\right)\cdot n$
$\displaystyle<2kt\log\left(\frac{2n}{kt}\right).$

Since we choose $t=n^{\delta}$ and $m>m_{(\ref{lem:compress})}(n,k,D,\delta)$,
we know from Lemma 4.1 that the following holds:

$\displaystyle\qquad\quad\widetilde{t}=t\log\left(\frac{m}{t}\right)>D\left(kt\log\left(\frac{en}{kt}\right)+1\right)>Dkt\log\left(\frac{2n}{kt}\right)$
$\displaystyle\implies\frac{2}{D}\,\widetilde{t}>2kt\log\left(\frac{2n}{kt}\right)>H\left(\frac{2kt}{n}\right)\,n$
$\displaystyle\implies(1-\rho)\widetilde{t}=\left(\frac{2}{D}+\rho\right)\widetilde{t}>H\left(\frac{2kt}{n}\right)n+2\lambda.$

Therefore, by Gilbert-Varshamov (Lemma 3.6),
$\mathbf{H}\in\mathbb{F}_{2}^{(1-\rho)\widetilde{t}\times n}$ has distance
less than $2kt$ with probability at most
$2^{-2\lambda}=\mathsf{negl}(\lambda)$.

  * •

$\mathsf{Hyb}_{2}$: this is identical to $\mathsf{Hyb}_{1}$, but instead of
sampling $\mathbf{H}\leftarrow\mathbb{F}_{2}^{2t\log(m/t)\times n}$, we sample
$\mathbf{H}=\mathbf{H}^{\prime}\cdot\mathbf{T}$ where
$\mathbf{H}^{\prime}\leftarrow\mathbb{F}_{2}^{2t\log(m/t)\times n/2}$ and
$\mathbf{T}\leftarrow\mathbb{F}_{2}^{n/2\times n}$. Since
$\widetilde{t}<n/2<n$, by basic linear algebra, it follows that $\mathbf{H}$
is identically distributed as in $\mathsf{Hyb}_{1}$.

We now show that $\Pr[\mathsf{Hyb}_{2}\text{ returns
}1]\leq\mathsf{negl}(\lambda)$ assuming $\mathsf{DS}\text{-}\mathsf{LPN}$
holds. We do this by constructing an adversary ${\cal B}$ against
$\mathsf{DS}\text{-}\mathsf{LPN}$ from an adversary ${\cal A}$ against
$\mathsf{Hyb}_{2}$. ${\cal B}$ receives $(\mathbf{A},\mathbf{b})$ where
$\mathbf{A}=\mathbf{T}\cdot\mathbf{M}$ for
$\mathbf{T}\leftarrow\mathbb{F}_{2}^{n/2\times n}$, $\mathbf{M}\leftarrow{\cal
M}_{\mathsf{sp}}$, and $\mathbf{b}\in\mathbb{F}_{2}^{1\times m}$ is either
uniformly random or is equal to $\mathbf{s}\mathbf{A}+\mathbf{e}$ for a random
$\mathbf{s}\leftarrow\mathbb{F}_{2}^{1\times n/2}$ and
$\mathbf{e}\leftarrow\mathsf{Ber}(\epsilon)^{1\times m}$. ${\cal B}$ now
samples
$\mathbf{H}^{\prime}\leftarrow\mathbb{F}_{2}^{(1-\rho)\widetilde{t}\times
n/2}$, computes $\mathbf{A}^{\prime}=\mathbf{H}^{\prime}\cdot\mathbf{A}$, then
runs ${\cal A}$ on $\mathbf{A}^{\prime}$ to get
$(\mathbf{x}_{1},\mathbf{x}_{2})$ from ${\cal A}$ and return
$\mathsf{ans}:=\mathbf{b}\cdot(\mathsf{spfy}_{m,t}(\mathbf{x}_{1})-\mathsf{spfy}_{m,t}(\mathbf{x}_{2}))$.
Here $\mathsf{ans}=1$ indicates that ${\cal B}$ received random
$\mathbf{b}\leftarrow\mathbb{F}_{2}^{1\times m}$.

We will analyze ${\cal B}$’s success probability. If $\mathbf{b}$ is uniformly
random, then $\mathsf{ans}$ is also uniformly random whenever ${\cal A}$ wins
(so that $\mathbf{x}_{1}\neq\mathbf{x}_{2}$); thus, in this case we have

$\Pr[\mathsf{ans}=1\mid\mathbf{b}\leftarrow\mathbb{F}_{2}^{m}]=\frac{1}{2}\cdot\Pr[\mathsf{Hyb}_{2}\text{
returns }1].$

If $\mathbf{b}=\mathbf{s}\mathbf{A}+\mathbf{e}$, then
$\mathsf{ans}=(\mathbf{s}\mathbf{A}+\mathbf{e})\cdot\mathbf{x}^{\prime}=\mathbf{e}\cdot\mathbf{x}^{\prime}$
whenever ${\cal A}$ wins in $\mathsf{Hyb}_{2}$. Since $\mathbf{x}^{\prime}$ is
at most $2t$-sparse, by Lemma 3.2 we have

$\displaystyle\Pr[\mathsf{ans}=1\mid\mathbf{b}=\mathbf{s}\mathbf{A}+\mathbf{e}]$
$\displaystyle\leq\Pr[\mathbf{e}\cdot\mathbf{x}^{\prime}=1]\cdot\Pr[\mathsf{Hyb}_{2}\text{
returns }1]$
$\displaystyle\leq\left(\frac{1-(1-2\epsilon)^{2t}}{2}\right)\cdot\Pr[\mathsf{Hyb}_{2}\text{
returns }1]$ $\displaystyle\leq\left(\frac{1}{2}-2^{-8\epsilon
t-1}\right)\cdot\Pr[\mathsf{Hyb}_{2}\text{ returns }1]$
$\displaystyle=\left(\frac{1}{2}-\frac{1}{\operatorname{\mathsf{poly}}(\lambda)}\right)\cdot\Pr[\mathsf{Hyb}_{2}\text{
returns }1].$

The last inequality is due to our choice of parameter $\epsilon=O(\log n/t)$,
which implies $2^{-8\epsilon
t-1}=1/\operatorname{\mathsf{poly}}(n)=1/\operatorname{\mathsf{poly}}(\lambda)$.
Putting everything together, we have

$\displaystyle\mathbf{Adv}^{\mathsf{DS}\text{-}\mathsf{LPN}}({\cal B})$
$\displaystyle=\lvert\Pr[\mathsf{ans}=1\mid\mathbf{b}=\mathbf{s}\mathbf{A}+\mathbf{e}]-\Pr[\mathsf{ans}=1\mid\mathbf{b}\leftarrow\mathbb{F}_{2}^{m}]\rvert$
$\displaystyle\geq\frac{1}{\operatorname{\mathsf{poly}}(\lambda)}\cdot\Pr[\mathsf{Hyb}_{2}\text{
returns }1].$

Therefore, if $\mathsf{DS}\text{-}\mathsf{LPN}$ holds (for our parameters),
then

$\Pr[\mathsf{Hyb}_{2}\text{ returns
}1]\leq\operatorname{\mathsf{poly}}(\lambda)\cdot\mathbf{Adv}^{\mathsf{DS}\text{-}\mathsf{LPN}}({\cal
B})\leq\mathsf{negl}(\lambda).$

∎

##  6 Lossy Trapdoor Functions

###  6.1 Definition

We define all-injective-but-one lossy trapdoor functions, which include lossy
trapdoor functions as a special case of having two branches.

######  Definition 6.1.

An _all-(injective)-but-one lossy trapdoor function_
$\mathsf{ABO}\text{-}\mathsf{LTDF}$ with input size $n=n(\lambda)$, output
size $m=m(\lambda)$, residual leakage $r=r(\lambda)$, and number of branches
$B(\lambda)$, consists of a PPT algorithm $\mathsf{Gen}$ and a tuple of
deterministic functions $(F,F^{-1})$ with the following syntax:

  * •

$\mathsf{Gen}(1^{\lambda},b^{*})\to(\mathsf{fk},\mathsf{td})$. Given the
security parameter $1^{\lambda}$ and a distinguished lossy branch
$b^{*}\in[B(\lambda)]$, return a function key $\mathsf{fk}$ and a trapdoor
$\mathsf{td}$.

  * •

$F(\mathsf{fk},b,x)\to y$. Given the function key $\mathsf{fk}$, a branch
$b\in[B]$, and an input $x\in\mathbb{F}_{2}^{n}$, return an output
$y\in\mathbb{F}_{2}^{m}$.

  * •

$F^{-1}(\mathsf{td},b,y)\to x$. Given the trapdoor $\mathsf{td}$, a branch
$b\in[B]$, and an output $y\in\mathbb{F}_{2}^{m}$, return a preimage
$x\in\mathbb{F}_{2}^{n}$.

and the following requirements:

  * •

Branch Indistinguishability. For any two different branches $b^{*}_{0}\neq
b^{*}_{1}\in[B]$, the following two distributions are indistinguishable

$\displaystyle\left\\{\mathsf{fk}\;\middle|\;(\mathsf{fk},\mathsf{td})\leftarrow\mathsf{Gen}(1^{\lambda},b^{*}_{0})\right\\}_{\lambda\in\mathbb{N}}\approx_{c}\left\\{\mathsf{fk}\;\middle|\;(\mathsf{fk},\mathsf{td})\leftarrow\mathsf{Gen}(1^{\lambda},b^{*}_{1})\right\\}_{\lambda\in\mathbb{N}}.$

  * •

Correct Inversion for Injective Branch. For any $\lambda\in\mathbb{N}$ and
$b\neq b^{*}\in[B]$, we have

$\displaystyle\Pr\left[F^{-1}(\mathsf{td},b,F(\mathsf{fk},b,x))=x\;\forall
x\in\mathbb{F}_{2}^{n}\;\middle|\;(\mathsf{fk},\mathsf{td})\leftarrow\mathsf{Gen}(1^{\lambda},b^{*})\right]\geq
1-\mathsf{negl}(\lambda).$

  * •

Lossyness for Lossy Branch. For any $\lambda\in\mathbb{N}$, we have

$\displaystyle\Pr\left[\left\lvert\\{F(\mathsf{fk},b^{*},x)\mid
x\in\mathbb{F}_{2}^{n}\\}\right\rvert\leq
2^{r}\;\middle|\;(\mathsf{fk},\mathsf{td})\leftarrow\mathsf{Gen}(1^{\lambda},b^{*})\right]\geq
1-\mathsf{negl}(\lambda).$

We define the _lossiness factor_ to be $\Gamma=n/r$, meaning that in lossy
mode, the output size is reduced by a factor of $\Gamma$ compared to the input
size.

A _lossy trapdoor function_ $\mathsf{LTDF}$ is an
$\mathsf{ABO}\text{-}\mathsf{LTDF}$ with only two branches, i.e.
$B(\lambda)=2$ for all $\lambda\in\mathbb{N}$.

##### Other extension of LTDFs.

Over the years, several variants of LTDFs have been proposed with a goal
toward increased functionality and more diverse applications. These include
all-but-$N$ LTDFs [HLOV11] (which can be built in a black-box way from LTDFs),
all-but-many [Hof12], and cumulative-all-lossy-but-one [CPW20] lossy trapdoor
functions. However, post-quantum constructions of the latter two variants
[BL17, LSSS17, LNP22] rely on lattice techniques such as preimage sampling
[GPV08, MP12] and GSW-style homomorphic evaluation [GSW13]. Since we do not
know analogues of these techniques for code-based cryptography, we leave as
future work the task of constructing these more advanced variants of LTDFs
from code-based assumptions.

###  6.2 Construction

Parameters. Let $k\in\mathbb{N},k\geq 3$ be a constant, $\Gamma>1$ be any
desired lossiness factor. • Let $D>\Gamma$ be the compression factor, and
consider any $\delta\in(\delta_{(\ref{lem:compress})}(k,D),1)$. • Let
$n=\operatorname{\mathsf{poly}}(\lambda)$,
$m=m_{(\ref{lem:compress})}(n,k,D,\delta)$, $t=n^{\delta}$, and consider a
good distribution ${\cal M}_{\mathsf{sp}}$ over $\mathsf{SpMat}(n,m,k)$. • Let
${\cal C}=\\{\mathbf{C}_{\kappa}\\}_{\kappa\in\mathbb{N}}$ be an explicit
family of asymptotically-good linear codes, where each $\mathbf{C}_{\kappa}$
has block length $L(\kappa)$, constant rate $\rho_{{\cal C}}$, and admits an
efficient algorithm $\mathsf{Decode}$ that can correct up to $\delta_{{\cal
C}}L$ errors (which exists by Lemma 3.7). • Let $D^{\prime}=\frac{\Gamma
D}{\Gamma-D}$ so that $\frac{1}{D}+\frac{1}{D^{\prime}}=\frac{1}{\Gamma}$, and
$\gamma=\min\left(\delta_{{\cal
C}},H^{-1}\left(\frac{\rho}{D^{\prime}}\right)\right)$. Let $\alpha>0$ be a
constant such that $\frac{\alpha^{2}}{\alpha+1}>\frac{\rho_{{\cal
C}}}{\gamma}$. • Let $\ell=\frac{1}{\rho_{{\cal C}}}\cdot t\log(\frac{m}{t})$
be the block length,101010Without loss of generality, we may assume
$\ell=L(\kappa)$ for some $\kappa\in\mathbb{N}$. Otherwise, letting
$L(\kappa)$ be the nearest block size larger than $\ell$, we may scale $n$
(and thus $\ell$) by an appropriate polynomial amount so that
$\ell=L(\kappa)$. and $\epsilon=\frac{\gamma}{(\alpha+1)t}$ be the noise rate.
We will abbreviate
$\mathbf{C}=\mathbf{C}_{\ell}\in\mathbb{F}_{2}^{t\log(m/t)\times\ell}$.
Construction. •
$\mathsf{Gen}(1^{\lambda},\tau^{*})\to(\mathsf{fk},\mathsf{td})$. Given lossy
branch $\tau^{*}\in\mathbb{F}_{2^{t\log(m/t)}}$, sample
$\mathbf{M}\leftarrow{\cal M}_{\mathsf{sp}}$,
$\mathbf{T}\leftarrow\mathbb{F}_{2}^{n/2\times n}$,
$\mathbf{S}\leftarrow\mathbb{F}_{2}^{\ell\times n/2}$, and
$\mathbf{E}\leftarrow\mathsf{Ber}(\mathbb{F}_{2},\epsilon)^{\ell\times m}$.
Let $\mathbf{A}=\mathbf{T}\cdot\mathbf{M}\in\mathbb{F}_{2}^{n/2\times m}$, and
$\mathbf{B}=\mathbf{S}\cdot\mathbf{A}+\mathbf{E}+\mathbf{C}^{\mathsf{T}}\cdot\mathbf{H}_{\tau^{*}}\cdot\mathbf{G}_{m,t}^{\mathsf{T}}\in\mathbb{F}_{2}^{\ell\times
m}$. Return $\mathsf{fk}=(\mathbf{A},\mathbf{B})$ and
$\mathsf{td}=(\mathbf{S},\tau^{*})$. •
$F(\mathsf{fk},\tau,\mathbf{x})\to\mathbf{y}$. Given
$\tau\in\mathbb{F}_{2^{t\log(m/t)}}$ and
$\mathbf{x}\in\mathbb{F}_{2}^{t\log(m/t)}$, compute
$\widetilde{\mathbf{x}}=\mathsf{spfy}_{m,t}(\mathbf{x})$ and
$\mathbf{B}_{\tau}=\mathbf{B}-\mathbf{C}^{\mathsf{T}}\cdot\mathbf{H}_{\tau}\cdot\mathbf{G}_{m,t}^{\mathsf{T}}$.
Return
$\mathbf{y}=(\mathbf{A}\cdot\widetilde{\mathbf{x}},\mathbf{B}_{\tau}\cdot\widetilde{\mathbf{x}})\in\mathbb{F}_{2}^{n/2+\ell}$.
• $F^{-1}(\mathsf{td},\tau,\mathbf{y})\to\mathbf{x}$. Parse
$\mathbf{y}=(\mathbf{y}_{1}\in\mathbb{F}_{2}^{n/2},\mathbf{y}_{2}\in\mathbb{F}_{2}^{\ell})$
and compute
$\mathbf{y}^{\prime}=\mathbf{y}_{2}-\mathbf{S}\cdot\mathbf{y}_{1}$. Return
$\mathbf{x}\leftarrow\left(\mathbf{H}_{\tau^{*}-\tau}\right)^{-1}\cdot\mathsf{Decode}(\mathbf{y}^{\prime})$.
Figure 3: ABO-LTDF construction

We give our construction of $\mathsf{ABO}\text{-}\mathsf{LTDF}$ in Figure 3.
In the construction, we use the following family of matrices
$\\{\mathbf{H}_{\tau}\\}_{\tau\in\mathbb{F}_{2^{n}}}$ for any
$n\in\mathbb{N}$, where $\mathbf{H}_{\tau}\in\mathbb{F}_{2}^{n\times n}$ is
the matrix corresponding to multiplication by $\tau$ in the field
$\mathbb{F}_{2^{n}}$ (which is isomorphic as vector spaces to
$\mathbb{F}_{2}^{n}$). It follows that
$\mathbf{H}_{\tau}-\mathbf{H}_{\tau^{\prime}}=\mathbf{H}_{\tau-\tau^{\prime}}$
is invertible for all $\tau\neq\tau^{\prime}$. Such a family has been used in
previous works [ABB10, KMP14].

To analyze the security of our construction, we begin with the following
result which bounds the noise growth.

######  Lemma 6.1.

Consider the parameters $n,m,t,B,\epsilon,\ell$ as in Figure 3. Let
$\mathbf{E}\leftarrow\mathsf{Ber}(\mathbb{F}_{2},\epsilon)^{\ell\times m}$.
Then except with $\mathsf{negl}(\lambda)$ probability over the choice of
$\mathbf{E}$, the vector
$\mathbf{E}\cdot\mathsf{spfy}_{m,t}(\mathbf{x})\in\mathbb{F}_{2}^{\ell}$ is at
most $\gamma\ell$-sparse for all $\mathbf{x}\in\mathbb{F}_{2}^{t\log(m/t)}$.

###### Proof.

By union bound, it suffices to show that for any fixed
$\mathbf{x}\in\mathbb{F}_{2}^{t\log(m/t)}$, letting
$\widetilde{\mathbf{x}}=\mathsf{spfy}_{m,t}(\mathbf{x})$, we have:

$\Pr\left[\mathsf{wt}(\mathbf{E}\cdot\widetilde{\mathbf{x}})>\gamma\ell\;\middle|\;\mathbf{E}\leftarrow\mathsf{Ber}(\mathbb{F}_{2},\epsilon)^{\ell\times
m}\right]\leq 2^{-t\log(m/t)}\cdot\mathsf{negl}(\lambda).$

Let $\mathbf{e}=\mathbf{E}\cdot\widetilde{\mathbf{x}}$. We can see that for
each $j\in[\ell]$, the entry
$(\mathbf{E}\cdot\widetilde{\mathbf{x}})_{j}=\langle\mathbf{E}_{j},\widetilde{\mathbf{x}}\rangle$,
where $\mathbf{E}_{j}$ is the $j^{th}$ row of $\mathbf{E}$, is drawn from the
Bernoulli distribution with noise

$\displaystyle\epsilon^{\prime}=\frac{1-(1-2\epsilon)^{t}}{2}<\epsilon
t=\frac{\gamma}{\alpha+1},\qquad\text{by
\lx@cref{creftypecap~refnum}{lem:bias-bernoulli} and the choice of
$\epsilon$}.$

We now apply Chernoff bound (Lemma 3.3) to get

$\displaystyle\Pr\left[\mathsf{wt}(\mathbf{E}\cdot\widetilde{\mathbf{x}})>\gamma\ell\;\middle|\;\mathbf{E}\leftarrow\mathsf{Ber}(\mathbb{F}_{2},\epsilon)^{\ell\times
m}\right]$ $\displaystyle\leq
e^{-2\alpha^{2}\frac{\gamma}{\alpha+1}\ell}=e^{-2\frac{\alpha^{2}}{\alpha+1}\frac{\gamma}{\rho_{{\cal
C}}}t\log(m/t)}<2^{-2t\log(m/t)}.$

In the above, the last inequality follows from our choice of $\alpha$.
Therefore, $\mathbf{E}\cdot\widetilde{\mathbf{x}}$ has Hamming weight at most
$\gamma\ell$ for all $\mathbf{x}\in\mathbb{F}_{2}^{t\log(m/t)}$ with
probability at least

$1-2^{t\log(m/t)}\cdot
2^{-2t\log(m/t)}=1-2^{-t\log(m/t)}=1-\mathsf{negl}(\lambda).$

∎

######  Theorem 6.1.

Assuming the $(n,m,k,{\cal M}_{\mathsf{sp}},\epsilon)$-Dense-Sparse LPN
assumption, where $n,m,k,{\cal M}_{\mathsf{sp}},\epsilon$ are chosen as in
Figure 3, the construction in Figure 3 is an
$\mathsf{ABO}\text{-}\mathsf{LTDF}$ with input length $t\log(m/t)$, branches
indexed by $\mathbb{F}_{2}^{t\log(m/t)}$, and lossiness factor $\Gamma>1$.

###### Proof.

We argue each property separately as follows.

_Mode indistinguishability._ This is clear from the Dense-Sparse LPN
assumption, since in both cases, $\mathsf{fk}=(\mathbf{A},\mathbf{B})$ is
indistinguishable from $(\mathbf{A},\mathbf{U})$ for a random
$\mathbf{U}\leftarrow\mathbb{F}_{2}^{\ell\times m}$.

_Trapdoor inversion._ If
$\mathsf{Gen}(1^{\lambda},\mathsf{inj})\to(\mathsf{fk}=(\mathbf{A},\mathbf{B}),\mathsf{td}=(\mathbf{S},\tau^{*}))$
and $F(\mathsf{fk},\tau,\mathbf{x})=(\mathbf{y}_{1},\mathbf{y}_{2})$ for some
$\mathbf{x}\in\mathbb{F}_{2}^{t\log(m/t)}$, letting
$\widetilde{\mathbf{x}}=\mathsf{spfy}_{m,t}(\mathbf{x})$, we have that

$\displaystyle\mathbf{y}_{1}=\mathbf{A}\cdot\widetilde{\mathbf{x}},\quad\mathbf{y}_{2}$
$\displaystyle=(\mathbf{B}-\mathbf{C}^{\mathsf{T}}\cdot\mathbf{H}_{\tau}^{\mathsf{T}}\cdot\mathbf{G}_{m,t}^{\mathsf{T}})\cdot\widetilde{\mathbf{x}}$
$\displaystyle=\mathbf{S}\cdot\mathbf{y}_{1}+\mathbf{E}\cdot\widetilde{\mathbf{x}}+\mathbf{C}^{\mathsf{T}}\cdot\mathbf{H}_{\tau^{*}-\tau}\cdot\mathbf{x}.$

The last equality follows from Equation 8, namely that
$\mathbf{G}_{m,t}^{\mathsf{T}}\cdot\mathsf{spfy}_{m,t}(\mathbf{x})=\mathbf{x}$.
Hence for all $\tau\neq\tau^{*}$, with all but $\mathsf{negl}(\lambda)$
probability, we have:

$\displaystyle F^{-1}(\mathsf{td},(\mathbf{y}_{1},\mathbf{y}_{2}))$
$\displaystyle=\left(\mathbf{H}_{\tau^{*}-\tau}\right)^{-1}\cdot\mathsf{Decode}\left(\mathbf{y}_{2}-\mathbf{S}\cdot\mathbf{y}_{1}\right)$
$\displaystyle=\left(\mathbf{H}_{\tau^{*}-\tau}\right)^{-1}\cdot\mathsf{Decode}\left(\mathbf{C}^{\mathsf{T}}\cdot\mathbf{H}_{\tau^{*}-\tau}\cdot\mathbf{x}+\mathbf{E}\cdot\mathsf{spfy}_{m,t}(\mathbf{x})\right)$
$\displaystyle=\left(\mathbf{H}_{\tau^{*}-\tau}\right)^{-1}\cdot\left(\mathbf{H}_{\tau^{*}-\tau}\cdot\mathbf{x}\right)\qquad\text{(holds
with $1-\mathsf{negl}(\lambda)$ probability)}$ $\displaystyle=\mathbf{x}.$

Indeed, the third equality holds with probability $1-\mathsf{negl}(\lambda)$
because of the following. First, the fact that $\mathsf{Decode}$ can
efficiently decode from any $\gamma\ell$ errors, i.e.
$\mathsf{Decode}(\mathbf{C}^{\mathsf{T}}\cdot\mathbf{x}+\mathbf{e})=\mathbf{x}$
for any $\mathbf{e}\in{\cal B}_{\leq}(\ell,\gamma\ell)$. Second, from Lemma
6.1 and the choice of $\gamma$, we know that
$\mathsf{wt}(\mathbf{E}\cdot\mathsf{spfy}_{m,t}(\mathbf{x}))\leq\gamma\ell\leq\delta_{{\cal
C}}\ell$ for any $\mathbf{x}\in\mathbb{F}_{2}^{t\log(m/t)}$, which holds with
all but $\mathsf{negl}(\lambda)$ probability.

_Lossyness._ For the lossy branch $\tau=\tau^{*}$, we will count the number of
attainable values
$\mathbf{y}=(\mathbf{y}_{1},\mathbf{y}_{2})\in\mathbb{F}_{2}^{n/2+\ell}$ in
the range of $F$. Denote ${\cal X}=\mathbb{F}_{2}^{t\log(m/t)}$ to be the
domain, and ${\cal
Y}=\\{(\mathbf{y}_{1},\mathbf{y}_{2})\\}\subset\mathbb{F}_{2}^{n/2+\ell}$ to
be the range.

The first part
$\mathbf{y}_{1}:=\mathbf{A}\cdot\widetilde{\mathbf{x}}=\mathbf{T}\cdot(\mathbf{M}\cdot\widetilde{\mathbf{x}})$,
is determined by the value $\mathbf{M}\cdot\widetilde{\mathbf{x}}\in{\cal
B}(n,\leq kt)$, hence has cardinality at most $\lvert{\cal
B}_{\leq}(n,kt)\rvert$. By our choice of parameters for $n,m,t$ so that Lemma
4.1 is satisfied with compression factor $D$, it follows that the set ${\cal
Y}_{1}$ of possible values of $\mathbf{y}_{1}$ satisfies $\lvert{\cal
Y}_{1}\rvert<\lvert{\cal X}\rvert^{1/D}=2^{t\log(m/t)/D}$.

Next, for a fixed $\mathbf{y}_{1}$, using Lemma 6.1, we have that

$\mathbf{y}_{2}=\mathbf{B}_{\tau}\cdot\widetilde{\mathbf{x}}=\mathbf{S}\cdot\mathbf{y}_{1}+\mathbf{E}\cdot\widetilde{\mathbf{x}}$

is in a Hamming ball of radius $\gamma\ell$ around $\mathbf{y}_{1}$ except
with $\mathsf{negl}(\lambda)$ probability. Thus we have that

$\displaystyle\lvert{\cal Y}\rvert$ $\displaystyle\leq\lvert{\cal
Y}_{1}\rvert\cdot\lvert{\cal B}_{\leq}(\ell,\gamma\ell)\rvert$
$\displaystyle\leq 2^{t\log(m/t)/D}\cdot 2^{H(\gamma)\ell}$
$\displaystyle\leq\left(2^{t\log(m/t)}\right)^{1/D+1/D^{\prime}}$
$\displaystyle=\lvert{\cal X}\rvert^{1/\Gamma},$

and thus the lossiness parameter is at least $\Gamma$. Here the second
inequality is due to upper bounds on $\lvert{\cal Y}_{1}\rvert$ and
$\lvert{\cal B}_{\leq}(\ell,\gamma\ell)\rvert$, the third inequality is due to
our choice of $\gamma\leq H^{-1}(\rho/D^{\prime})$, which implies that
$H(\gamma)\ell=\frac{H(\gamma)}{\rho}\cdot
t\log(m/t)\leq\frac{1}{D^{\prime}}\cdot t\log(m/t)$, and the final equality is
because $\frac{1}{D}+\frac{1}{D^{\prime}}=\frac{1}{\Gamma}$. ∎

##  7 Cryptanalysis on Dense-Sparse LPN

Recent works, in the context of generating correlated pseudorandomness for MPC
applications [BCGI18, BCG+19, BCG+20a], have proposed various novel variants
of LPN with different matrix distributions [BCG+20a, CRR21, BCG+22, CD23b,
RRT23, BCCD23]. These recent progress also came with a _systematization_ of
known attacks on LPN-style assumption. Namely, prior works observed that most
attacks (Information-Set Decoding [Pra62], BKW [BKW00], Gaussian Elimination
[EKM17], Statistical Decoding [Jab01], etc.) on LPN-style assumptions can be
captured by a unified framework for the security of LPN variants, namely the
_linear test framework_ , which we will also use to analyze the security of
our assumption. The linear test framework has also been used to extensively
cryptanalyze Goldreich’s PRGs [Gol00, CM01, MST03, CEMT09, BQ09, ABW10, ABR12,
BQ12, App12, App13, OW14, AL16, KMOW17, CDM+18, AK19], which is a related
assumption to Sparse LPN.

In a linear test, an adversary takes as input a matrix
$\mathbf{A}\in\mathbb{Z}^{n\times m}_{2}$ and outputs a vector
$\mathbf{v}\in\mathbb{Z}^{m\times 1}_{2}$ such that
$(\mathbf{s}\mathbf{A}+\mathbf{e})\,\mathbf{v}$ is a biased random variable
with an inverse polynomial bias towards $0$. Assuming $\mathbf{e}$ is chosen
from Bernoulli distribution with probability $\epsilon$, a successful attacker
must output $\mathbf{v}$ with hamming weight $O(\frac{\log n}{\epsilon})$, or
else the bias is negligible.

######  Definition 7.1 (Security against Linear Test, adapted from [CRR21]).

Let $n\in\mathbb{N}$ be the dimension, $m=m(n)$ be the number of samples, and
$q=q(n)$ be a prime power. Given an efficiently sampleable distribution ${\cal
M}={\cal M}(n,m,\mathbb{F}_{q})$ over matrices in $\mathbb{F}_{q}^{n\times m}$
and noise probability $\epsilon=\epsilon(n)\in(0,1)$, we say that the $({\cal
M},\epsilon)\text{-}\mathsf{LPN}$ assumption is _$(T(n),\beta(n),\delta(n))$
-computationally secure against linear tests_ if for any adversary
${\mathcal{A}}$ running in time at most $T(n)$, it holds that

$\Pr\left[\mathsf{bias}_{\mathbf{v}}({\cal
D}_{\mathbf{A}})\geq\beta\quad\middle|\quad\begin{aligned}
&\mathbf{A}\leftarrow{\cal M}\\\
&\mathbf{v}\leftarrow{\mathcal{A}}(\mathbf{A})\end{aligned}\right]\leq\delta,$

where ${\cal
D}_{\mathbf{A}}=\left\\{\mathbf{s}\mathbf{A}+\mathbf{e}\mid\mathbf{s}\overset{}{\leftarrow}\mathbb{F}_{q}^{1\times
n},\mathbf{e}\leftarrow\mathsf{Ber}(\mathbb{F}_{q},\epsilon)^{1\times
m}\right\\}$. (Recall that bias is defined in Definition 3.1.)

In other words, the Linear Test Hypothesis for the $({\cal M},\epsilon)$-LPN
assumption states that $({\cal M},\epsilon)$-LPN is secure if it is
computationally difficult to find $O(\frac{\log n}{\epsilon})$-sparse vectors
in the kernel of $\mathbf{A}\leftarrow{\cal M}$. All known counter-examples to
this hypothesis are for distributions ${\cal M}$ of algebraically structured
matrices (see [BCG+20b] for a detailed discussion). In contrast, our Dense-
Sparse matrix distribution $\mathbf{A}=\mathbf{T}\mathbf{M}$ has no apparent
algebraic structure, and thus it is reasonable to conjecture that Dense-Sparse
LPN is secure assuming it is secure against linear tests. Furthermore, if
finding $O(\frac{\log n}{\epsilon})$-sparse vectors in the kernel is difficult
for subexponential time adversaries, then the corresponding LPN assumption is
also subexponentially secure.

Assuming the Linear Test Hypothesis, we now examine the hardness of finding
sparse vectors in the kernel of $\mathbf{A}=\mathbf{T}\mathbf{M}$. Such
vectors of sparsity $n^{\delta}$ for any $\delta\in(0,1)$ actually come from
the kernel of $\mathbf{M}$, with all but negligible probability. This is
because $\mathbf{T}$ is a random binary matrix of dimension $\frac{n}{2}\times
n$, and so typically only has vectors in the kernel that are at least
$\Omega(n/\log n)$-sparse (see [CRR21] for a detailed calculation). Therefore,
we will focus our attention on the size of short vectors in the kernel of the
$k$-sparse matrix $\mathbf{M}$, and also on the overall security of Sparse
LPN.

###  7.1 Security of Sparse LPN

Sparse LPN is a relatively well-understood assumption in the domain of
refutations for random constraint satisfaction. When one samples a random
matrix for the sparse LPN assumption $\mathbf{M}$ with sparsity parameter $k$,
dimension $n$ and sample complexity $n^{1+(\frac{k}{2}-1)(1-\delta)}$, it can
be proven that the dual distance of $\mathbf{M}$, chosen randomly from
$\mathsf{SpMat}(n,m,k,\mathbb{F})$ (the set of $k$-sparse matrices in
$\mathbb{F}^{n\times m}$), is $t=\Theta(n^{\delta})$ with all but inverse
polynomial probability.

######  Lemma 7.1 (Folklore, see [DIJL23]).

For any finite field $\mathbb{F}$, given any $k=k(n)\geq 3$, any $0<\delta<1$,
and $m=O\left(n^{1+(\frac{k}{2}-1)(1-\delta)}\right)$, there exists a constant
$c>0$ such that the following holds for large enough $n$:

$\displaystyle\Pr\left[\mathsf{dd}(\mathbf{M})\leq c\cdot
n^{\delta}\;\middle|\;\mathbf{M}\leftarrow\mathsf{SpMat}(n,m,k,\mathbb{F})\right]=\Theta\left(\left(\frac{k}{n^{\delta}}\right)^{k-2}\right).$

Note that the dual distance of $t=O(n^{\delta})$ is also known in the stronger
case of _worst-case_ $k$-sparse $\mathbf{M}$, whenever
$m=\widetilde{O}\left(n^{1+(\frac{k}{2}-1)(1-\delta)}\right)$ [GKM22, HKM23].

One could then consider Sparse LPN in two regimes. In the first regime, the
error probability is $\epsilon=\omega(\frac{\log n}{t})$. In this regime,
conditioned on the event that there simply _does not exist_ vectors of
sparsity $O(\frac{\log n}{\epsilon})$ in the kernel of $\mathbf{M}$, security
against linear tests holds. Sparse LPN with this regime of error (even
constant error probability) has found prior applications [IKOS08, ADI+17,
AK23, BCG+23, DIJL23].

Nevertheless, there are also applications of Sparse LPN where sparse vectors
(in the kernel of $\mathbf{M}$) do exist, but seem computationally hard to
find. One such example is the public-key encryption scheme of Applebaum, Barak
and Wigderson [ABW10] uses an inverse polynomial error probability
$\epsilon=O(\frac{\log n}{t})$. In this case, certainly there exist lots of
$t$-sparse vectors in the kernel of $\mathbf{M}$. To this date, we do not know
any procedure that can efficiently find (even in subexponential time
$2^{t^{\rho}}$ for any $0<\rho<1$) such $t$-sparse vectors in the kernel of
$\mathbf{M}$. Therefore, the linear test framework correctly predicts the
(subexponential) security of this assumption.

Our applications could have been based on Sparse LPN in its compression
regime. This holds at a significantly lower error probability
$\epsilon_{\mathsf{cps}}=o(\frac{1}{t_{\mathsf{cps}}})$ where
$t_{\mathsf{cps}}\sim\left(\frac{n^{k}}{m}\right)^{\frac{1}{k-1}}$, which is
polynomially larger than the dual distance
$t\sim\left(\frac{n^{k/2}}{m}\right)^{\frac{1}{k/2-1}}$. We in fact show that
it is _easy_ to find $t_{\mathsf{cps}}$-sparse solutions to
$\mathbf{M}\,\mathbf{x}$ for randomly chosen $\mathbf{M}$.

##### Sparse LPN is Broken in its Compression Regime.

Following our exposition in Section 2, we give a simple attack on Sparse LPN
in the parameter regime needed for achieving compression (and hence lossy
trapdoor functions).

######  Theorem 7.1.

Consider Sparse LPN with sparsity $k$, dimension $n$ and sample complexity $m$
in the regime in Lemma 4.1, with error rate $\epsilon=O(1/t)$. Assuming the
matrix is chosen by sampling distinct $k$-sparse random columns, this variant
of Sparse LPN can be broken in polynomial time.

The attack, given samples $(\mathbf{M},\mathbf{b})$ with $\mathbf{b}$ either
from the Sparse LPN distribution, or the random distribution:

  1. 1.

Pick a random subset $S\subset[n]$ of size $t$. Initialize $T=\emptyset$.

  2. 2.

For each column $j\in[m]$ of $\mathbf{M}$, if all $k$ of the non-zero entries
lie inside $S$, add $j$ to $T$.

  3. 3.

If $\lvert T\rvert>t$, find a linear dependency (expressed as a vector
$\mathbf{x}$) between the columns in $T$.

  4. 4.

Compute $d=\langle\mathbf{b},\mathbf{x}\rangle$. If $d=0$, return “Sparse
LPN”, else return “random”.

######  Lemma 7.2.

This attack succeeds with high probability $1-o(1)$ whenever $m>c\cdot
m_{(\ref{lem:compress})}(k,D)$ for a sufficiently large constant $c$ and any
compression factor $D>1$.

###### Proof.

For any fixed choice of $S\subset[n]$, we can compute the expectation of the
number of columns found in step 2 as follows.

$\displaystyle\operatorname*{\mathbb{E}}[\lvert
T\rvert]=m\cdot\Pr[\mathsf{Supp}(\mathbf{a})\subset
S\mid\mathbf{a}\leftarrow\mathsf{SpMat}(n,1,k)]=m\cdot\frac{{t\choose
k}}{{n\choose k}}\approx m\cdot\left(\frac{t}{n}\right)^{k}>t.$

The last inequality is due to the choice $m>m_{(\ref{lem:compress})}(k,1)$.

∎

###  7.2 Dual-Distance of Dense-Sparse LPN

We now examine the dual-distance of the matrices arising in our Dense-Sparse
LPN assumption, and the computational hardness of finding sparse vectors
$\bm{x}$ that are in the kernel of those matrices. Since our matrices are of
the form $\mathbf{T}\mathbf{M}$ where $\mathbf{T}\in\mathbb{Z}^{n\times
m}_{2}$ is randomly chosen matrix with high probability the dual distance is
around $t=O(n^{\delta})$ where $m=n^{1+(\frac{k}{2}-1)(1-\delta)}$ where as
the error probability $\epsilon<\frac{1}{t_{\mathsf{cps}}}$, where
$t_{\mathsf{cps}}\sim\left(\frac{n^{k}}{m}\right)^{\frac{1}{k-1}}$ is the
threshold for compression.

##### Sparse Vector in the Kernel of $\mathbf{T}\mathbf{M}$.

As described above, if we can efficiently find $t=O(n^{\delta})$ sparse
vectors $\bm{x}\in\mathbb{Z}^{m\times 1}_{2}$ in the kernel of
$\mathbf{T}\mathbf{M}$, that is enough to break our assumption with any error
probability $O(\frac{\log n}{t})$. In our specific setting, we work with an
error probability of about $\frac{1}{t_{\mathsf{cps}}}$ where
$t_{\mathsf{cps}}\sim\left(\frac{n^{k}}{m}\right)^{\frac{1}{k-1}}\approx\frac{n}{m^{1/k}}$
(for large enough constant $k$). Setting $m=n^{1+(k/2-1)(1-\delta)}$, this
turns out to be roughly $t_{\mathsf{cps}}\approx
n^{\frac{1}{2}+\delta-\frac{1}{k}}$. On the other hand, much sparser vectors
($t=O(n^{\delta})$ sparse) in the kernel exist. Thus, if one can find kernel
vectors of this sparsity, it could break our assumption. However, for
arbitrary dense matrices we don’t know a better way to find such
$n^{\delta}$-sparse vectors than naive search, which is known to be
subexponentially hard even given $\mathbf{M}$ in the clear (this very
assumption was made by [ABW10]).

It is also true that one could also break our assumption by finding vectors in
the kernel with much higher sparsity $t_{\mathsf{cps}}\approx
n^{\frac{1}{2}+\delta-\frac{1}{k}}$. In fact, we showed how to do find such
vectors in Theorem 7.1, but our attack crucially relies on seeing the
_sparsity pattern_ of the matrix $\mathbf{M}$. This pattern is no longer
apparent when we only give out $\mathbf{A}=\mathbf{T}\mathbf{M}$ with
$\mathbf{T}$ being a random (dense) matrix, so the attack in Theorem 7.1 no
longer applies.

##### Pseudorandomness of $\mathbf{T}\mathbf{M}$.

We in fact postulate that the matrices $\mathbf{T}\mathbf{M}$ are
computationally hard to distinguish from random matrices (which have dual
distance of $O(\frac{n}{\log n})$ with overwhelming probability). A first
observation is that since any $O(t)$ columns of $\mathbf{M}$ are linearly
independent (as its dual distance is $\Omega(t)$) with overwhelming
probability (assuming $\mathbf{M}$ is chosen from a good distribution), any
$O(t)$ columns of $\mathbf{T}\mathbf{M}$ are distributed according to a random
distribution over $\mathbb{Z}^{\frac{n}{2}\times 1}_{2}$. This ensures that
matrix is from a $O(t)$-wise independent distribution.

####  7.2.1 Searching for $\mathbf{T}$

Next, we examine the possibility of learning $\mathbf{T}$ from the matrix
$\mathbf{T}\mathbf{M}$ and then finding $t_{\mathsf{cps}}$ sparse vectors in
the kernel of $\mathbf{M}$. We provide an attack that works with $\mathbf{T}$
is an invertible matrix in $\mathbb{Z}^{n\times n}_{2}$. This attack does not
apply when the matrix lives inside $\mathbb{Z}^{\beta n\times n}_{2}$ for any
constant $\beta\in(0,1)$, which justifies our choice of parameters for Dense-
Sparse LPN.

##### When $\mathbf{T}\leftarrow\mathbb{F}_{2}^{n\times n}$ is a square
matrix.

We can generalize our previous attack to rule out the case where $\mathbf{T}$
is a random square matrix (and not just the identity). The idea is that this
$\mathbf{T}$ may be “unmasked” by searching for its inverse $\mathbf{Z}$. In
other words, given the Dense-Sparse matrix
$\mathbf{A}=\mathbf{T}\cdot\mathbf{M}$, we want to find
$\mathbf{Z}\in\mathbb{F}_{2}^{n\times n}$ such that
$\mathbf{Z}\cdot\mathbf{A}=\mathbf{M}$ is a sparse matrix. Let a candidate row
for $\mathbf{Z}$ be $\mathbf{z}$. Observe that $\mathbf{z}\mathbf{A}$ must be
a sparse vector that corresponds to the row of $\mathbf{M}$. Since each column
of $\mathbf{M}$ has some constant number $k$ of elements, with high
probability (roughly $1-O(\frac{k}{n})$) each coordinate of
$\mathbf{z}\mathbf{A}$ must be $0$. Then, we can essentially apply the same
attack that breaks LPN assumption with error probability $O(\frac{1}{n})$ to
learn $\mathbf{z}$.

The attack is as follows. Let the columns of $\mathbf{A}$ be
$\mathbf{a}_{1},\ldots,\mathbf{a}_{m}$. We randomly sample $n$ equations at
random, say denoted by $I$,$\\{\mathbf{a}_{i}\\}_{i\in I}$. There is
probability $(1-\frac{k}{n})^{n}=\Omega(1)$ chance that there exist $\bm{z}$
that satisfy $\langle\bm{z},\bm{a}_{i}\rangle=0$. We can then find all such
vectors $\bm{z}$ that will form the rows of $\bm{Z}$. This can be used derive
$\mathbf{M}$ up to a permutation of rows, which is sufficient for carrying out
the attack on Sparse LPN.

##### When $\mathbf{T}\leftarrow\mathbb{F}_{2}^{\beta n\times n}$ is a
compressing matrix for $\beta<1$.

A natural way to extend the above attack would be to find an inverse
$\mathbf{Z}$ for a square sub-matrix of $\mathbf{T}$. For example, we can hope
to find $\mathbf{Z}\in\mathbb{Z}^{\beta n\times\beta n}_{2}$ that is the
inverse of the submatrix formed by the first $\beta\cdot n$ sub-columns of
$\mathbf{T}$, so that $\mathbf{Z}\mathbf{T}\mathbf{M}=[\mathbf{I}_{\beta
n}\|\mathbf{T}^{\prime}]\cdot\mathbf{M}$. Note that
$\mathbf{T}^{\prime}\in\mathbb{F}_{2}^{\beta n\times(1-\beta)n}$ is randomly
distributed.

Now, if one examines $[\mathbf{I}_{\beta
n}\|\mathbf{T}^{\prime}]\cdot\mathbf{M}$ the following holds. For any $i$-th
column $\mathbf{m}_{i}$ of $\mathbf{M}$, if $\mathbf{m}_{i}$ is supported over
the first $\beta\cdot n$ variables, then the same $i$-th column in
$[\mathbf{I}_{\beta n}\|\mathbf{T}^{\prime}]\cdot\mathbf{M}$ is precisely
$\mathbf{m}_{i}$, and hence remains $k$-sparse. Otherwise, if $\mathbf{m}_{i}$
has a non-zero entry in the rest of the positions, then the randomness of
$\mathbf{T}^{\prime}$ would make the resulting column in
$\mathbf{Z}\mathbf{T}\mathbf{M}$ random as well.

Let’s calculate when the first event happens, so that we have hope of
unmasking a column of $\mathbf{M}$. Since there is a constant chance that when
choosing a column of $\mathbf{M}$, that column is supported inside the first
$\beta\cdot n$ set of variables, the product $[\mathbf{I}_{\beta
n}\|\mathbf{T}^{\prime}]\cdot\mathbf{M}$ will be so that each row has a
constant fraction of non-zero element. As a consequence, to solve for
$\mathbf{Z}$ we might have to rely on an LPN solver that works with constant
probability noise which might be hard to do. In general, this attack should
take (near-)exponential time as long $\mathbf{T}$ is randomly chosen from
$\mathbb{Z}^{\beta n\times n}_{2}$ for any $\beta>0$.

####  7.2.2 On Subexponential Time Attacks

We have discussed two main attacks for finding sparse vectors in the kernel of
the Dense-Sparse matrix $\mathbf{T}\mathbf{M}$, which by the linear test
framework (Definition 7.1) is the best attack against Dense-Sparse LPN. In the
fist attack, we attempt to directly find $O(n^{\delta})$ sparse vectors in the
kernel of $\mathbf{T}\mathbf{M}$, treating it as an arbitrary dense matrix. In
the second attack, we attempt to peel off $\mathbf{T}$, and then use our
attack in Theorem 7.1 to find sparse vectors in the kernel of $\mathbf{M}$. As
argued above, the best known algorithms for the first takes
$2^{\widetilde{O}(n^{\delta})}$ time and the second to the best of our current
knowledge should take almost exponential time assuming $\beta$ is some
constant. Therefore, we may justify our conjecture that Dense-Sparse LPN is
hard against subexponential time adversaries.

## References

  * [ABB10] Shweta Agrawal, Dan Boneh, and Xavier Boyen.  Efficient lattice (H)IBE in the standard model.  In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 553–572. Springer, Heidelberg, May / June 2010.
  * [ABR12] Benny Applebaum, Andrej Bogdanov, and Alon Rosen.  A dichotomy for local small-bias generators.  In Ronald Cramer, editor, TCC 2012, volume 7194 of LNCS, pages 600–617. Springer, Heidelberg, March 2012.
  * [ABW10] Benny Applebaum, Boaz Barak, and Avi Wigderson.  Public-key cryptography from different assumptions.  In Leonard J. Schulman, editor, 42nd ACM STOC, pages 171–180. ACM Press, June 2010.
  * [ADI+17] Benny Applebaum, Ivan Damgård, Yuval Ishai, Michael Nielsen, and Lior Zichron.  Secure arithmetic computation with constant computational overhead.  In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part I, volume 10401 of LNCS, pages 223–254. Springer, Heidelberg, August 2017.
  * [ADMP20] Navid Alamati, Luca De Feo, Hart Montgomery, and Sikhar Patranabis.  Cryptographic group actions and applications.  In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part II, volume 12492 of LNCS, pages 411–439. Springer, Heidelberg, December 2020.
  * [AK19] Benny Applebaum and Eliran Kachlon.  Sampling graphs without forbidden subgraphs and unbalanced expanders with negligible error.  In David Zuckerman, editor, 60th FOCS, pages 171–179. IEEE Computer Society Press, November 2019.
  * [AK23] Benny Applebaum and Niv Konstantini.  Actively secure arithmetic computation and VOLE with constant computational overhead.  In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part II, volume 14005 of LNCS, pages 190–219. Springer, Heidelberg, April 2023.
  * [AL16] Benny Applebaum and Shachar Lovett.  Algebraic attacks against random local functions and their countermeasures.  In Daniel Wichs and Yishay Mansour, editors, 48th ACM STOC, pages 1087–1100. ACM Press, June 2016.
  * [Ale03] Michael Alekhnovich.  More on average case vs approximation complexity.  In 44th FOCS, pages 298–307. IEEE Computer Society Press, October 2003.
  * [App12] Benny Applebaum.  Pseudorandom generators with long stretch and low locality from random local one-way functions.  In Howard J. Karloff and Toniann Pitassi, editors, 44th ACM STOC, pages 805–816. ACM Press, May 2012.
  * [App13] Benny Applebaum.  Pseudorandom generators with long stretch and low locality from random local one-way functions.  SIAM J. Comput., 42(5):2008–2037, 2013.
  * [BBC08] Marco Baldi, Marco Bodrato, and Franco Chiaraluce.  A new analysis of the McEliece cryptosystem based on QC-LDPC codes.  In Rafail Ostrovsky, Roberto De Prisco, and Ivan Visconti, editors, SCN 08, volume 5229 of LNCS, pages 246–262. Springer, Heidelberg, September 2008.
  * [BBN+09] Mihir Bellare, Zvika Brakerski, Moni Naor, Thomas Ristenpart, Gil Segev, Hovav Shacham, and Scott Yilek.  Hedged public-key encryption: How to protect against bad randomness.  In Mitsuru Matsui, editor, ASIACRYPT 2009, volume 5912 of LNCS, pages 232–249. Springer, Heidelberg, December 2009.
  * [BC07] Marco Baldi and Franco Chiaraluce.  Cryptanalysis of a new instance of mceliece cryptosystem based on QC-LDPC codes.  In IEEE International Symposium on Information Theory, ISIT 2007, Nice, France, June 24-29, 2007, pages 2591–2595. IEEE, 2007.
  * [BCCD23] Maxime Bombar, Geoffroy Couteau, Alain Couvreur, and Clément Ducros.  Correlated pseudorandomness from the hardness of quasi-abelian decoding.  In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part IV, volume 14084 of LNCS, pages 567–601. Springer, Heidelberg, August 2023.
  * [BCD+16] Magali Bardet, Julia Chaulet, Vlad Dragoi, Ayoub Otmani, and Jean-Pierre Tillich.  Cryptanalysis of the McEliece public key cryptosystem based on polar codes.  In Tsuyoshi Takagi, editor, Post-Quantum Cryptography - 7th International Workshop, PQCrypto 2016, pages 118–143. Springer, Heidelberg, 2016\.
  * [BCG+19] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl.  Efficient pseudorandom correlation generators: Silent OT extension and more.  In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part III, volume 11694 of LNCS, pages 489–518. Springer, Heidelberg, August 2019.
  * [BCG+20a] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl.  Correlated pseudorandom functions from variable-density LPN.  In 61st FOCS, pages 1069–1080. IEEE Computer Society Press, November 2020.
  * [BCG+20b] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl.  Efficient pseudorandom correlation generators from ring-LPN.  In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part II, volume 12171 of LNCS, pages 387–416. Springer, Heidelberg, August 2020.
  * [BCG+22] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Nicolas Resch, and Peter Scholl.  Correlated pseudorandomness from expand-accumulate codes.  In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part II, volume 13508 of LNCS, pages 603–633. Springer, Heidelberg, August 2022.
  * [BCG+23] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Nicolas Resch, and Peter Scholl.  Oblivious transfer with constant computational overhead.  In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part I, volume 14004 of LNCS, pages 271–302. Springer, Heidelberg, April 2023.
  * [BCGI18] Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai.  Compressing vector OLE.  In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, ACM CCS 2018, pages 896–912. ACM Press, October 2018.
  * [BCM+18] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh V. Vazirani, and Thomas Vidick.  A cryptographic test of quantumness and certifiable randomness from a single quantum device.  In Mikkel Thorup, editor, 59th FOCS, pages 320–331. IEEE Computer Society Press, October 2018.
  * [BF22] Nir Bitansky and Sapir Freizeit.  Statistically sender-private OT from LPN and derandomization.  In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part III, volume 13509 of LNCS, pages 625–653. Springer, Heidelberg, August 2022.
  * [BFKL94] Avrim Blum, Merrick L. Furst, Michael J. Kearns, and Richard J. Lipton.  Cryptographic primitives based on hard learning problems.  In Douglas R. Stinson, editor, CRYPTO’93, volume 773 of LNCS, pages 278–291. Springer, Heidelberg, August 1994.
  * [BFO08] Alexandra Boldyreva, Serge Fehr, and Adam O’Neill.  On notions of security for deterministic encryption, and efficient constructions without random oracles.  In David Wagner, editor, CRYPTO 2008, volume 5157 of LNCS, pages 335–359. Springer, Heidelberg, August 2008.
  * [BHK11] Mark Braverman, Avinatan Hassidim, and Yael Tauman Kalai.  Leaky pseudo-entropy functions.  In Bernard Chazelle, editor, Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, pages 353–366. Tsinghua University Press, 2011.
  * [BHY09] Mihir Bellare, Dennis Hofheinz, and Scott Yilek.  Possibility and impossibility results for encryption and commitment secure under selective opening.  In Antoine Joux, editor, EUROCRYPT 2009, volume 5479 of LNCS, pages 1–35. Springer, Heidelberg, April 2009.
  * [BKV19] Ward Beullens, Thorsten Kleinjung, and Frederik Vercauteren.  CSI-FiSh: Efficient isogeny based signatures through class group computations.  In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part I, volume 11921 of LNCS, pages 227–247. Springer, Heidelberg, December 2019.
  * [BKW00] Avrim Blum, Adam Kalai, and Hal Wasserman.  Noise-tolerant learning, the parity problem, and the statistical query model.  In 32nd ACM STOC, pages 435–440. ACM Press, May 2000.
  * [BL05] Thierry P. Berger and Pierre Loidreau.  How to mask the structure of codes for a cryptographic use.  Des. Codes Cryptogr., 35(1):63–79, 2005.
  * [BL17] Xavier Boyen and Qinyi Li.  All-but-many lossy trapdoor functions from lattices and applications.  In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part III, volume 10403 of LNCS, pages 298–331. Springer, Heidelberg, August 2017.
  * [BLP10] Daniel J Bernstein, Tanja Lange, and Christiane Peters.  Wild mceliece.  In International Workshop on Selected Areas in Cryptography, pages 143–158. Springer, 2010.
  * [BLP11] Daniel J. Bernstein, Tanja Lange, and Christiane Peters.  Wild McEliece incognito.  In Bo-Yin Yang, editor, Post-Quantum Cryptography - 4th International Workshop, PQCrypto 2011, pages 244–254. Springer, Heidelberg, November / December 2011.
  * [BLSV18] Zvika Brakerski, Alex Lombardi, Gil Segev, and Vinod Vaikuntanathan.  Anonymous IBE, leakage resilience and circular security from new assumptions.  In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part I, volume 10820 of LNCS, pages 535–564. Springer, Heidelberg, April / May 2018.
  * [BLVW19] Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, and Daniel Wichs.  Worst-case hardness for LPN and cryptographic hashing via code smoothing.  In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part III, volume 11478 of LNCS, pages 619–635. Springer, Heidelberg, May 2019.
  * [BQ09] Andrej Bogdanov and Youming Qiao.  On the security of goldreich’s one-way function.  In Irit Dinur, Klaus Jansen, Joseph Naor, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009\. Proceedings, volume 5687 of Lecture Notes in Computer Science, pages 392–405. Springer, 2009.
  * [BQ12] Andrej Bogdanov and Youming Qiao.  On the security of goldreich’s one-way function.  Comput. Complex., 21(1):83–127, 2012.
  * [Bra18] Zvika Brakerski.  Quantum FHE (almost) as secure as classical.  In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 67–95. Springer, Heidelberg, August 2018.
  * [BV11] Zvika Brakerski and Vinod Vaikuntanathan.  Efficient fully homomorphic encryption from (standard) LWE.  In Rafail Ostrovsky, editor, 52nd FOCS, pages 97–106. IEEE Computer Society Press, October 2011.
  * [BY91] Gilles Brassard and Moti Yung.  One-way group actions.  In Alfred J. Menezes and Scott A. Vanstone, editors, CRYPTO’90, volume 537 of LNCS, pages 94–107. Springer, Heidelberg, August 1991.
  * [CD23a] Wouter Castryck and Thomas Decru.  An efficient key recovery attack on SIDH.  In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part V, volume 14008 of LNCS, pages 423–447. Springer, Heidelberg, April 2023.
  * [CD23b] Geoffroy Couteau and Clément Ducros.  Pseudorandom correlation functions from variable-density LPN, revisited.  In Alexandra Boldyreva and Vladimir Kolesnikov, editors, PKC 2023, Part II, volume 13941 of LNCS, pages 221–250. Springer, Heidelberg, May 2023.
  * [CDG+17] Chongwon Cho, Nico Döttling, Sanjam Garg, Divya Gupta, Peihan Miao, and Antigoni Polychroniadou.  Laconic oblivious transfer and its applications.  In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part II, volume 10402 of LNCS, pages 33–65. Springer, Heidelberg, August 2017.
  * [CDM+18] Geoffroy Couteau, Aurélien Dupin, Pierrick Méaux, Mélissa Rossi, and Yann Rotella.  On the concrete security of Goldreich’s pseudorandom generator.  In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part II, volume 11273 of LNCS, pages 96–124. Springer, Heidelberg, December 2018.
  * [CEMT09] James Cook, Omid Etesami, Rachel Miller, and Luca Trevisan.  Goldreich’s one-way function candidate and myopic backtracking algorithms.  In Omer Reingold, editor, TCC 2009, volume 5444 of LNCS, pages 521–538. Springer, Heidelberg, March 2009.
  * [CGKS95] Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan.  Private information retrieval.  In 36th FOCS, pages 41–50. IEEE Computer Society Press, October 1995.
  * [CJJ22] Arka Rai Choudhuri, Abhishek Jain, and Zhengzhong Jin.  SNARGs for $\mathcal{P}$ from LWE.  In 62nd FOCS, pages 68–79. IEEE Computer Society Press, February 2022.
  * [CLM+18] Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes.  CSIDH: An efficient post-quantum commutative group action.  In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part III, volume 11274 of LNCS, pages 395–427. Springer, Heidelberg, December 2018.
  * [CLRS22] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.  Introduction to algorithms.  MIT press, 2022.