Introduction
Public-key encryption (PKE) [32 , 74 ] is a fundamental primitive enabling secure communication via open and untrusted channels. Despite the immense success of public-key cryptography as a field, and despite intense interest and effort over nearly five decades, we know of surprisingly few sources of hardness that can be nontrivially utilized in building PKE1 .
Furthermore, almost all of these rely on structured hardness rooted in domains such as number theory, algebra, coding theory or lattices (see, for example [32 , 74 , 71 , 16 , 9 ] ). This is in stark contrast with private-key encryption and one-way functions, where any hard-on-average problem satisfying very mild structural requirements suffices (e.g. planted clique problem, random constraint satisfaction problems, and sparse PCA).
The overarching goal of this research is to devise new ways of nontrivially leveraging other sources of hardness to enable public-key encryption (and beyond). One such untapped source of hardness is the domain of statistical inference and average-case complexity. For decades, these areas have excelled at identifying and studying natural average-case problems in domains such as graph theory, combinatorics and machine learning from both algorithmic and hardness perspectives. There are also systematic means to give evidence of hardness in restricted algorithmic models such as sum-of-squares [76 , 66 , 70 , 62 ] , statistical-query model [56 ] , low-degree tests framework [BHK⁺19, Hop18] and many others. Unfortunately, despite an abundant supply of well-studied average-case problems, what we seem to lack are algorithmic reduction techniques that can nontrivially leverage these problems to create the kinds of “trapdoor” structures that are needed to create public-key encryption. Can we develop new techniques that would allow us to add to the short list of hardness conjectures that can be nontrivially used to build PKE?
In this work, we humbly add one more source of hardness to this list, namely n log α n n^{\log^{\alpha} n} n l o g α n hardness of the classic planted clique conjecture, for any α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) . We do by developing a new quasi-polynomial-time sparsification technique, that can “simulate” a random sparse graph from the point of view of achieving a desired level of expansion. We now elaborate.
Can the planted clique conjecture help us build PKE? Let us examine the classic planted-clique conjecture which roughly states that no efficient algorithm can determine, with constant advantage, whether a random graph contains a planted clique of an appropriate size. This conjecture is the oldest [7 , 52 Kuč95, 54 ] and arguably the most well-studied conjecture in average-case complexity. Moreover, its worst-case counterpart, the max clique problem, is a classic NP-complete problem. Despite decades of research on the planted clique conjecture [52 Kuč95, 35 , 53 , 5 ABI⁺23, MRS20, 45 AAK⁺07, 2 , 21 , 14 , 13 , 48 ] , constructing a PKE nontrivially utilizing this conjecture has remained elusive.
A seminal work that kick-started the search of PKE from such average-case complexity problems was that of Applebaum, Barak and Wigderson [5 ] which showed several PKE schemes from various statistical inference problems. Of particular relevance to this work is a construction recipe that shows how to design a PKE from any local CSP and a variant planted graph conjecture that, roughly speaking, posits the hardness of finding a small subgraph planted in a random sparse k k k -regular bipartite graph. Indeed, the work of [5 ] leaves finding a way to leverage the classic planted clique conjecture directly to build PKE as an open question.
We make significant progress towards this question. In particular, our main result builds a PKE scheme from two very well-studied [AKS98, Jer92, Kuč95, Kar76, ERSY22, JP00, ABW10, ABI⁺23, MRS20, [45 , 1 , 2 , 21 , 14 , 13 , 48 , 37 , 40 , 34 , 31 , 17 , 65 , 61 , 50 , 10 , 19 , 73 , 39 , 12 , 25 , 58 ] average-case complexity problems, namely: n log α n n^{\log^\alpha n} n l o g α n hardness of the standard planted clique conjecture on graphs with n n n vertices, for any constant α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , together with a mild conjecture on the hardness of the noisy k k k -LIN problem2 over expanding graphs. Our k k k -LIN conjecture when interpreted in the special case of equations over F 2 \mathbb{F}_2 F 2 also gives rise to one of the most studied hard distributions for MAX-k k k -SAT (e.g. [44 , 75 , 38 , 58 ] ).
Indeed, neither of these well-studied conjectures (with parameters that we use) were previously known to imply PKE. To the best of our knowledge, ours is the first work that constructs a PKE making critical use of the standard planted clique conjecture3 . At the heart of our work is a new algorithmic technique to leverage this conjecture to create “trapdoor-friendly” structures.
We now introduce our hardness conjectures, and go through a brief discussion of their history.
Conjecture 1: The Planted Clique Problem. Let G ( n , 1 2 ) \mathcal{G}(n,\frac{1}{2}) G ( n , 2 1 ) denote the standard Erdős–Rényi distribution4 over random graphs. Let G ( n , 1 2 , n δ ) \mathcal{G}(n,\frac{1}{2},n^\delta) G ( n , 2 1 , n δ ) denote the distribution that first samples a graph from G ( n , 1 2 ) \mathcal{G}(n,\frac{1}{2}) G ( n , 2 1 ) and then plants a clique on n δ n^\delta n δ randomly selected nodes.
Conjecture 1.1 (n log α n n^{\log^\alpha n} n l o g α n hardness5 of the Planted Clique Conjecture). There exist constants 0 < α < 1 0 < \alpha< 1 0 < α < 1 and δ ∈ ( 0 , 1 2 ) \delta\in(0,\frac{1}{2}) δ ∈ ( 0 , 2 1 ) such that, for all n O ( log α n ) n^{O(\log^\alpha n)} n O ( l o g α n ) -size algorithms A \mathcal{A} A ,
∣ Pr [ A ( G ) = 1 ∣ G ← $ G ( n , 1 2 ) ] − Pr [ A ( G ) = 1 ∣ G ← $ G ( n , 1 2 , n δ ) ] ∣ ≤ 1 3 . \left| \Pr\left[\mathcal{A}(G)=1 \mid G \xleftarrow{\$} \mathcal{G}\left(n,\frac{1}{2}\right)\right] - \Pr\left[\mathcal{A}(G)=1 \mid G \xleftarrow{\$} \mathcal{G}\left(n,\frac{1}{2},n^\delta\right)\right] \right| \leq\frac{1}{3}. Pr [ A ( G ) = 1 ∣ G $ G ( n , 2 1 ) ] − Pr [ A ( G ) = 1 ∣ G $ G ( n , 2 1 , n δ ) ] ≤ 3 1 .
Note that we only require the existence of some constants; for example, α = 10 − 3 \alpha= 10^{-3} α = 1 0 − 3 and δ = 10 − 3 \delta= 10^{-3} δ = 1 0 − 3 would suffice. Even stronger versions have been considered, for example the “strongish planted clique conjecture” of Manurangsi, Rubinstein, and Schramm [MRS20], which posits n o ( log n ) n^{o(\log n)} n o ( l o g n ) hardness for the same problem.
Planted clique has been rigorously studied in statistical inference and average-case complexity ever since its introduction [7 , 52 , 60 , 54 , 35 , 53 , 5 , 3 MRS20, 45 , 1 , 2 , 21 , 14 , 13 , 48 , 65 , 61 , 50 ] . Many different algorithms have been proposed (e.g. [7 , 37 , 40 , 34 , 31 ] ), but none of the currently known algorithms succeed in determining, with constant advantage, whether there exists a planted clique of size smaller than o ( n ) o(\sqrt{n}) o ( n ) in polynomial time. Furthermore, the problem has been very well analyzed in restricted algorithmic models, and is subject to strong lower bounds in these models, including sum-of-squares [17 ] and other frameworks [52 , 30 , 72 , 36 , 37 ] , providing rigorous evidence for hardness. The recent work of Hirahara and Shimizu also showed a search-to-decision reduction for planted clique [48 ] , so our conjecture is equivalent to assuming only the hardness of the search version of the problem.
Noisy k k k -LIN Problem over Expanders
We now describe the noisy k k k -LIN problem over expander graphs. This is a particular well-studied instantiation of local CSPs over expander graphs where the predicate is just the linear function. As in standard planted CSPs over expander graphs, the problem is defined with respect to a graph represented by a collection of sets ( S 1 , … , S m ) (S_1,\ldots,S_m) ( S 1 , … , S m ) . Here, n n n is the number of variables and m = m ( n ) m=m(n) m = m ( n ) is the number of clauses (each clause being a sparse linear equation over a subset of the variables), and each set S i S_i S i is of size exactly k = k ( n ) k=k(n) k = k ( n ) and supported over { 1 , … , n } \{1,\ldots,n\} { 1 , … , n } . The set system satisfies a property that is called ( γ , k , t ) (\gamma,k,t) ( γ , k , t ) -expansion, which requires that for any collection { S i } i ∈ I \{S_i\}_{i\in I} { S i } i ∈ I of size at most t t t , the union of S i S_i S i has at least γ ⋅ k ⋅ ∣ I ∣ \gamma\cdot k\cdot|I| γ ⋅ k ⋅ ∣ I ∣ many distinct variables, where γ \gamma γ is a constant bigger than 1 2 \frac{1}{2} 2 1 . See Definition 3.1 for formal details.
In the context of the noisy k k k -LIN problem, one is asked to distinguish between the joint distributions ( A , b = A s + e ) (\mathbf{A},\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}) ( A , b = As + e ) and ( A , b = r ) (\mathbf{A},\mathbf{b}=\mathbf{r}) ( A , b = r ) , where A \mathbf{A} A is a sparse matrix in F p m × n \mathbb{F}_p^{m\times n} F p m × n produced by taking an indicator matrix I ∈ { 0 , 1 } m × n \mathbf{I}\in\{0,1\}^{m\times n} I ∈ { 0 , 1 } m × n representing the sets { S 1 , … , S m } \{S_1,\ldots,S_m\} { S 1 , … , S m } and replacing each nonzero entry in I \mathbf{I} I with a random element of F p \mathbb{F}_p F p . Specifically, for all i i i , the i t h i^{\mathrm{th}} i th row of A \mathbf{A} A encodes the set S i S_i S i : we have that A i , j ≠ 0 A_{i,j}\ne0 A i , j = 0 if j ∈ S i j\in S_i j ∈ S i and 0 0 0 otherwise. The secret s ∈ F p n \mathbf{s}\in\mathbb{F}_p^n s ∈ F p n and r ∈ F p m \mathbf{r}\in\mathbb{F}_p^m r ∈ F p m are uniformly chosen random vectors of appropriate dimensions, and every entry of e \mathbf{e} e is sampled independently from a Bernoulli distribution with probability η \eta η . Backed by systematic lower bounds over many years [44 , 38 , 75 , 19 , 73 , 39 , 12 , 25 , 58 ] , we formalize the following widely believed conjecture:
Conjecture 1.3 (Noisy k k k -LIN Conjecture). There exists a constant γ ∈ ( 1 2 , 1 ) \gamma\in(\frac{1}{2},1) γ ∈ ( 2 1 , 1 ) such that the following holds. Let α , ς \alpha,\varsigma α , ς be any constants with α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) and ς > 0 \varsigma>0 ς > 0 . Then, for n n n large enough, prime p = n Ω ( 1 ) p=n^{\Omega(1)} p = n Ω ( 1 ) , k = Ω ( log ( n ) ) k=\Omega(\log(n)) k = Ω ( log ( n )) , we have the following: Let I ∈ { 0 , 1 } m × n \mathbf{I}\in\{0,1\}^{m\times n} I ∈ { 0 , 1 } m × n correspond to any ( γ , k , 2 ( log n ) α ) (\gamma,k,2^{(\log n)^\alpha}) ( γ , k , 2 ( l o g n ) α ) -expanding set system, and let A ∈ F p m × n \mathbf{A}\in\mathbb{F}_p^{m\times n} A ∈ F p m × n be sampled by replacing each nonzero entry in I \mathbf{I} I with a random element in F p \mathbb{F}_p F p . It holds that
( A , b = A s + e ) , (\mathbf{A},\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}), ( A , b = As + e ) , is computationally indistinguishable from
( A , b = r ) . (\mathbf{A},\mathbf{b}=\mathbf{r}). ( A , b = r ) . We only require indistinguishability with respect to a small constant distinguishing advantage, specifically 1 16 \frac{1}{16} 16 1 . Above, s ← F p n \mathbf{s}\leftarrow\mathbb{F}_p^n s ← F p n and r ← F p m \mathbf{r}\leftarrow\mathbb{F}_p^m r ← F p m are uniformly randomly chosen and e ∈ F p m \mathbf{e}\in\mathbb{F}_p^m e ∈ F p m sampled as:
e i = { Random element of F p , with probability η = ( log n ) − ς , 0 , otherwise. e_i=
\begin{cases}
\text{Random element of }\mathbb{F}_p,\text{ with probability }\eta=(\log n)^{-\varsigma},\\
0,\text{ otherwise.}
\end{cases} e i = { Random element of F p , with probability η = ( log n ) − ς , 0 , otherwise.
Remark 1.4. In fact, we can use the search version of the above conjecture, and the matrix A \mathbf{A} A for our PKE scheme will satisfy additional desirable properties6 . See § 4 for details.
Intuitively, the conjecture becomes more “secure” for larger values of k k k , and if the expansion threshold t t t and the error probability η \eta η are large. In particular, it is desirable that t t t is at least Ω ( log n ) \Omega(\log n) Ω ( log n ) , and in our case, it is actually much larger, namely t = 2 log α n t=2^{\log^\alpha n} t = 2 l o g α n . Keeping this value of t t t in mind, we can mentally classify the problem in two regimes when it comes to using noisy k k k -LIN for designing PKE, based on the noise probability η \eta η .
Noise probability η < O ( log n ) t \eta<\frac{O(\log n)}{t} η < t O ( l o g n ) : In this regime, Applebaum et. al. [5 ] showed how to design a PKE only leveraging the noisy k k k -LIN problem for any constant k ≥ 3 k\ge3 k ≥ 3 . Here, the noise probability increases as the number of clauses m m m gets closer to n k / 2 n^{k/2} n k /2 , but this causes the expansion parameter t t t to decrease as well, and in all cases, the noise probability is η < O ( log n ) t \eta<\frac{O(\log n)}{t} η < t O ( l o g n ) . Recall that noisy k k k -LIN is broken when given approximately m = n k / 2 m=n^{k/2} m = n k /2 clauses [10 , 19 , 39 ] , in which case no nontrivial expansion is possible. Any small non-expanding collection of sets, in some sense, can serve as a secret key for the scheme.
Indeed, the k k k -LIN problem in this regime can be efficiently attacked if given unbounded preprocessing on the graph7 . The ABW scheme from noisy k k k -LIN problem alone can be broken given a short advice on the matrix. This is also related to the so-called “Alekhnovich” barrier in cryptography for design of encryption schemes from (variants of) the Learning Parity with Noise problem [9 ] .
In the other regime when η > ω ( log n ) t \eta> \frac{\omega(\log n)}{t} η > t ω ( l o g n ) , which is our regime, we do not know of any PKE scheme from the noisy k k k -LIN conjecture alone. This regime differs greatly from the previous one: No attacks are known on noisy k k k -LIN in the second regime, even with unbounded preprocessing on the expander graph. This is also connected to the notion of efficient non-deterministic refutation for certain CSPs [38 ] which only applies to the first regime, and where there has been no progress in the second regime.
In our setting, we mandate expansion on all sets of size at most t = 2 ( log n ) α t = 2^{(\log n)^\alpha} t = 2 ( l o g n ) α , and the error rate is η = ( log n ) − O ( 1 ) = ( log t ) − O ( 1 ) ≫ ω ( log n ) t \eta= (\log n)^{-O(1)} = (\log t)^{-O(1)} \gg\frac{\omega(\log n)}{t} η = ( log n ) − O ( 1 ) = ( log t ) − O ( 1 ) ≫ t ω ( l o g n ) . At the same time, our construction satisfies the following property with regard to subsets of the clauses: For any set S S S of x x x variables, at most x 1 + ε ≪ x k / 2 x^{1+\varepsilon} \ll x^{k/2} x 1 + ε ≪ x k /2 clauses exist that use only variables contained in S S S , where ε \varepsilon ε is an arbitrarily small positive constant chosen at time of setup. In particular, this means that the total number of clauses is at most n 1 + ε ≪ n k / 2 n^{1+\varepsilon} \ll n^{k/2} n 1 + ε ≪ n k /2 .
In § 10 , we import some existing results that show unconditional lower bounds supporting Conjecture 1.3 in the following restricted models of computation: (1) local tests, (2) linear tests, (3) low degree polynomials, (4) sum of squares algorithms, and (5) A C 0 \mathrm{AC}^{0} AC 0 circuits.
Remark 1.5. An important remark is that there are contrived PAC learning based counterexamples to noisy k k k -LIN in settings where the entire expander graph can be computed by a circuit in a shallow complexity class such as A C 0 [ ⊕ ] \mathrm{AC}^{0}[\oplus] AC 0 [ ⊕ ] [68 ] . This is due the fact that the resulting k k k -LIN is approximable by a A C 0 [ ⊕ ] \mathrm{AC}^{0}[\oplus] AC 0 [ ⊕ ] circuit that can be PAC-learned. The work also showed existence of such expander graphs relying on Nisan-Wigderson pseudorandom generator applied to some polynomial sized seed [67 ] .
We note that in our case the expander for k k k -LIN is sampled from a natural distribution induced by a random G ( n , 1 2 ) G(n,\frac{1}{2}) G ( n , 2 1 ) , and furthermore multiple steps in our construction will introduce independent randomness for the neighbors of each edge in the expander graph. So the neighbor function simply has too much entropy to be computed by any nontrivial A C 0 [ ⊕ ] \mathrm{AC}^{0}[\oplus] AC 0 [ ⊕ ] circuit. In fact the current counterexamples [68 ] only apply to the setting where the number of samples is superpolynomial with respect to the length of the secret, which is far outside of our setting. Finally, in the setting where p > 2 p > 2 p > 2 , and the coefficients for the k k k -LIN constraints are chosen independently and randomly from F p ∗ \mathbb{F}_p^* F p ∗ (as in our construction), there are no known counterexamples even where the number of samples can be superpolynomial.
Our Main Result. We establish the following theorem:
Theorem 1.6 (Informal). If Conjecture 1.1 and Conjecture 1.3 both hold, then there exists a semantically secure public key encryption scheme.
Related Work
Relationship with [5 ] . Applebaum, Barak and Wigderson designed several PKE schemes from related assumptions. They have a construction from random noisy k k k -LIN for any k ≥ 3 k \ge3 k ≥ 3 that is in the regime η < O ( log n t ) \eta< O\left(\frac{\log n}{t}\right) η < O ( t l o g n ) . Most relevant to our work is their PKE scheme in the regime when η > ω ( log n ) t \eta> \frac{\omega(\log n)}{t} η > t ω ( l o g n ) , which is based on noisy k k k -LIN8 for any k k k and a hidden subgraph assumption over random sparse k k k regular bipartite graphs. Recently, this assumption was proven to be secure against low degree polynomial algorithms, thanks to the work of Bogdanov, Kothari and Rosen [18 ] , however we don’t know yet how to reduce the standard planted clique problem to their assumption. Applebaum, Barak, and Wigderson do prove an interesting theorem (see Theorem B.13 in the appendix of [5 ] ) that connects the planted clique problem to a variant of their bipartite graph assumption via a simple reduction. We now discuss two of the main reasons why Theorem B.13 in [5 ] leads to strictly (much) weaker conclusions than ours.
Firstly, the theorem only works with planted clique over significantly sparser graphs, specifically those with edge probability 2 − ℓ 2^{-\ell} 2 − ℓ where ℓ \ell ℓ is roughly of the order log ( 1 − ε ) n \log^{(1-\varepsilon)} n log ( 1 − ε ) n for some small constant ε > 0 \varepsilon> 0 ε > 0 . The standard planted clique problem, on the other hand, sets the edge probability to 1 2 \frac{1}{2} 2 1 , and is the most widely studied form of the problem algorithmically.
Also, their reduction for very low edge probability works only when considering a weakening of their bipartite subgraph assumption: namely where the associated graph satisfies a weaker property known as unique-neighbor expansion. While it turns out that unique neighbor expansion is enough to establish a few lower bounds for noisy k k k -LIN, it is much weaker than the notion of ( γ , k , t ) (\gamma,k,t) ( γ , k , t ) -expanding set-systems for γ > 1 2 \gamma> \frac{1}{2} γ > 2 1 , which is what our result uses.
Other Schemes. There are only a few other works that give PKE from graph-based assumptions. Bogdanov, Kothari and Rosen [18 ] give a variant of one scheme by Applebaum, Barak, and Wigderson [5 ] . In particular, they replace the planted dense subgraph assumption with another non-standard assumption about planted even covers, for which they show hardness against low degree polynomial algorithms.
Abram, Beimel, Ishai, Kushilevitz, and Narayanan explore using a more aggressive assumption to build PKE with logarithmic-size messages [3 ] . Hudoba proposed a scheme inspired by the problem of finding a planted clique in a modified random graph [49 ] , but this scheme was broken by a polynomial-time key recovery attack [28 ] .
Goldreich PRGs. Inspired by constraint satisfaction over expander graphs, in 2000 Goldreich proposed low-complexity local candidate one-way functions [42 ] that were later imagined as candidate low-complexity cryptographic pseudorandom generators [CM01, IKOS08]. The complexity theory and cryptography communities have jointly developed a rich body of literature on the cryptanalysis and theory of constant-locality Boolean PRGs [42 CM01, 64 , 27 , 20 , 5 , 4 , 11 , 69 , 8 , 58 , 26 , 6 ] . Ever since its introduction Goldreich’s PRGs have been conjectured [42 , 5 , 4 , 8 ] to be secure on arbitrary expander graphs. The cryptanalysis of such PRG candidates bears uncanny resemblance to the algorithmic study of the noisy k k k -LIN conjecture (in the regime p = 2 p=2 p = 2 ) over expander graphs due to similarity in structure of the two problems. A typical way to instantiate Goldreich PRG predicates is to consider a function that is a sparse linear function which is XORed with an appropriately chosen non-linear predicate to mimic the noise from the noisy k k k -XOR problem [8 ] . A 20 year study of Goldreich PRGs in cryptography once again solidifies our confidence in the noisy k k k -LIN conjecture.
Open Problems
Of course, the most natural open problem left open by our work is to build PKE assuming only some reasonable hardness of the planted clique conjecture. However, we believe that the most pressing open problems are:
Can we further populate the list of explicit average-case hardness conjectures that can be nontrivially used in building PKE?
Can we further populate the list of explicit hardness conjectures that suffice on their own to yield PKE (without needing any “helper” hardness conjectures)?
What level of sparse error is needed in the context of “noisy linear algebra”-type hardness conjectures, like k k k -LIN, to yield (plausibly sub-exponentially secure) PKE without any additional hardness conjectures?
More broadly, what are the minimal levels of mathematical structure that suffice to yield PKE?
Technical Overview
The technical core of our new PKE construction is the instantiation of an expanding set system from the planted clique conjecture. Concretely, the set system consists of a set of “variables” and a set of “clauses” over those variables. This set system is used to sample ciphertexts that are instances of k k k -LIN on expanders.
In this overview, we will focus on discussing how we start with a graph G G G that is either sampled from G ( n , 1 2 ) \mathcal{G}(n,\frac{1}{2}) G ( n , 2 1 ) or from G ( n , 1 2 , n δ ) \mathcal{G}(n,\frac{1}{2},n^\delta) G ( n , 2 1 , n δ ) , and then make a sequence of transformations to it that finally yields this desired set system.
Desiderata. We begin by stating the properties that we need in order to simultaneously achieve security and decryption correctness:
Goal 1. If we start with a graph G G G sampled from G ( n , 1 2 ) \mathcal{G}(n,\frac{1}{2}) G ( n , 2 1 ) , then we want the sets of variables and clauses to satisfy strong expansion properties. In particular, every collection I I I of up to t = 2 log α n t = 2^{\log^\alpha n} t = 2 l o g α n clauses must include at least γ ⋅ k ⋅ ∣ I ∣ \gamma\cdot k \cdot|I| γ ⋅ k ⋅ ∣ I ∣ variables, where γ ∈ ( 1 2 , 1 ) \gamma\in(\frac{1}{2},1) γ ∈ ( 2 1 , 1 ) is any fixed constant chosen at the time of construction.
Goal 2. If we start with a graph G G G sampled from G ( n , 1 2 , n δ ) \mathcal{G}(n,\frac{1}{2},n^\delta) G ( n , 2 1 , n δ ) , then there must exist a set of x = polylog ( n ) x = \operatorname{polylog}(n) x = polylog ( n ) clauses that include less than x x x variables.
Specifically, Goal 1 above is needed for security of our PKE scheme; Goal 2 allows us to have efficient decryption for our PKE scheme (see § 5 for details).
An initial naive approach. The most obvious idea is to use the incidence graph between edges and vertices to define our sets of variables and clauses. More specifically, we could use (i) the set of vertices to represent the variables, along with (ii) the set of edges to represent each clause, where each edge represents a clause depending on the variables for the edge’s endpoints. Indeed such a construction would only allow us to achieve an arity of k = 2 k = 2 k = 2 if applied to a standard graph9 , which doesn’t work for us10 .
A natural generalization of the above idea is to look at subgraphs of G G G with larger size. In particular, to obtain a set of clauses with arity k > 2 k > 2 k > 2 , we can start by assigning a variable to each ( k − 1 ) (k - 1) ( k − 1 ) -clique in G G G . Each clause would then correspond to a k k k -clique, with the variables being those for each ( k − 1 ) (k - 1) ( k − 1 ) -clique inside the k k k -clique.
If we think of constant k k k , then the number of variables and clauses is polynomial in n n n ; however, we do not achieve expansion as per Goal 1. Indeed, in G ( n , 1 2 ) \mathcal{G}(n,\frac{1}{2}) G ( n , 2 1 ) , we expect there to be cliques of size up to Θ ( log n ) \Theta(\log n) Θ ( log n ) , and for each clique of size x x x in our graph, we will have roughly ( x k ) \binom{x}{k} ( k x ) clauses on only ( x k − 1 ) \binom{x}{k-1} ( k − 1 x ) variables, which is (very) contracting. In fact, it turns out that if one picks a random set of x x x vertices, for any x ≤ n x \le n x ≤ n , we expect to find Θ ( ( x k ) ) \Theta\left(\binom{x}{k}\right) Θ ( ( k x ) ) clauses that contain Θ ( ( x k − 1 ) ) \Theta\left(\binom{x}{k-1}\right) Θ ( ( k − 1 x ) ) variables. The problem here is that the density of small regions in the resulting variable-clause bipartite graph when starting from G ( n , 1 2 ) \mathcal{G}(n,\frac{1}{2}) G ( n , 2 1 ) is not substantially different than the density of such regions when starting from G ( n , 1 2 , n δ ) \mathcal{G}(n,\frac{1}{2},n^\delta) G ( n , 2 1 , n δ ) . We therefore ask the following question:
Can we modify G G G in a useful way to amplify the difference in local density between the planted clique and the rest of the graph?
Sparsification. Intuitively, our aim is to amplify the density disparity between the portion of the graph inside and outside the planted clique, thereby enabling us to achieve Goals 1 and 2. We do so by means of a vertex -deletion based sparsification technique. We transform G G G into a larger and sparser graph H H H , and we will now identify variables with ( k − 1 ) (k-1) ( k − 1 ) -cliques in H H H , and clauses with k k k -cliques in H H H . We do so as follows:
Create a set of labels, each of which corresponds to an ℓ \ell ℓ -sized subset of vertices in G G G .
Include each label as a vertex of H H H with probability p = n − c ℓ p=n^{-c\ell} p = n − c ℓ for some small positive constant c < δ c<\delta c < δ .
Connect two nodes in H H H with an edge iff their respective labels correspond to two subsets whose union forms a clique (of size at most 2 ℓ 2\ell 2 ℓ ) in G G G .
This method is called the “randomized graph product” and has been used previously to study the hardness of various graph problems [24 MRS20, 48 ] . Perhaps the most interesting aspect of this randomized graph product is Step 2, where almost all of the labels are discarded. To gain intuition as to why this is helpful to us, let’s denote by H ^ \widehat{H} H the graph obtained via the product above, but without Step 2 – namely, we create a vertex in H ^ \widehat{H} H for every label created in Step 1. Now, observe that corresponding to the clique of size Θ ( log n ) \Theta(\log n) Θ ( log n ) in G G G , we can (efficiently) find a clique in H ^ \widehat{H} H of size roughly ( log n ℓ ) \binom{\log n}{\ell} ( ℓ l o g n ) . The fact that this “huge” clique in H ^ \widehat{H} H is of size ω ( log n ) \omega(\log n) ω ( log n ) turns out to be highly problematic for us: this is because the “huge” clique will induce a very high level of compression. Because of the deletion (Step 2), our sparsified graph H H H does not have such a large clique.
Going super-polynomial in n n n — the need for large graph H H H . We pause now to make a crucial observation. Note that if we pick ℓ = O ( 1 ) \ell=O(1) ℓ = O ( 1 ) , then the edge probability in H H H is still a constant. This implies that even after sparsification, for all x x x , there will exist many subgraphs with x x x vertices and Θ ( x 2 ) \Theta(x^2) Θ ( x 2 ) edges. In other words, small structures in H H H are still quite dense, and the difference in density as compared to the planted clique is only a constant factor.
To overcome this hurdle, it is imperative that we pick ℓ \ell ℓ to be superconstant. In particular, we choose ℓ = log α n \ell=\log^\alpha n ℓ = log α n , for any constant α ∈ ( 0 , 1 2 ) \alpha\in(0,\frac{1}{2}) α ∈ ( 0 , 2 1 ) . While this does yield an H H H whose size in slightly superpolynomial in the size of G G G , we now have a very useful property: H H H has an edge probability of ( 1 2 ) ( log n ) Θ ( 1 ) \left(\frac{1}{2}\right)^{(\log n)^{\Theta(1)}} ( 2 1 ) ( l o g n ) Θ ( 1 ) . In fact, it turns out that with these parameters, there exists a cutoff value t = 2 ( log n ) Θ ( 1 ) t=2^{(\log n)^{\Theta(1)}} t = 2 ( l o g n ) Θ ( 1 ) such that any subgraph of H H H with x ≤ t x\le t x ≤ t vertices will have at most only x ⋅ polylog ( n ) x\cdot\operatorname{polylog}(n) x ⋅ polylog ( n ) edges! At the same time, if G G G had a planted clique, then H H H still would contain a large planted clique, in which subgraphs of the same size will have Θ ( x 2 ) \Theta(x^2) Θ ( x 2 ) edges.
Since the size of H H H is superpolynomial in n n n , we need the planted clique conjecture to hold against adversaries running in time n O ( log α n ) n^{O(\log^\alpha n)} n O ( l o g α n ) as stated in Conjecture 1.1 .
Constructing the Incidence Graph. Our remaining goal is to create a mapping from H H H to variables and clauses. Drawing on the example from the start of this section, we could have a variable for each vertex and a clause for each edge. Obviously, as observed before, such a construction does not work because the arity is k = 2 k = 2 k = 2 , but it also fails for a more interesting reason: large star graphs11 always exist in H H H , and they correspond to sets of clauses with poor expansion properties. Since every edge in the star graph shares a vertex, this means that each clause corresponding to an edge of the star graph has only one unique variable, and the other variable is shared by all of the other clauses. So the best expansion factor we can hope for is γ ≤ 1 2 \gamma\le\frac{1}{2} γ ≤ 2 1 , no matter how aggressive our sparsification is. This violates Goal 1 where we need γ > 1 2 \gamma> \frac{1}{2} γ > 2 1 .
Looking at k k k -cliques. To get some intuition, let us extend the above idea and consider having one variable for each edge in H H H , and a clause for each triangle in H H H , where the three variables for each clause are given by the edges inside each triangle. We can again try to find a compressing subset by forcing all triangles to share as many edges as possible. Observe that, because any sufficiently small set of vertices has a near linear number of edges, we can only force all triangles to share a single edge. Nearly all of the other edges will be unique to their specific triangle. In this way, we get an upper bound on the expansion factor of γ ≤ 2 3 \gamma\le\frac{2}{3} γ ≤ 3 2 . Extending this to having one variable for each ( k − 1 ) (k-1) ( k − 1 ) -clique and a clause of arity k k k for each k k k -clique, the same worst-case construction gives an upper bound of γ ≤ k − 1 k \gamma\le\frac{k-1}{k} γ ≤ k k − 1 . In fact, this this naive upper bound is close to the lower bound in the following sense. We show that for any constant ε > 0 \varepsilon> 0 ε > 0 there is a constant integer k k k such that,
For any small enough set I I I of clauses, nearly all clauses in I I I have that a ( 1 − ε ) (1-\varepsilon) ( 1 − ε ) fraction of their variables appear in at most polylog( n ) (n) ( n ) many other clauses of I I I .
On the other hand, when G G G contains a planted clique, we get a tiny subset T T T of clauses where every variable is shared by a much higher number of clauses in T T T . Thus the planted clique gives a trapdoor “highly compressing” set of clauses, but when G G G doesn’t contain a planted clique, any small set of clauses can only be at worst mildly compressing. We refer readers to Lemma 6.7 for the formal claim and other details.
The above property takes us very close to our goal. However so far we cannot rule out the case that, for some small set of clauses I I I , the clauses together only touch ∣ I ∣ / polylog ( n ) |I|/\operatorname{polylog}(n) ∣ I ∣/ polylog ( n ) many variables.
Augmentation with Random Vectors. To ensure the stronger notion of expansion that we desire, we augment the clauses with random sparse vectors. In more detail, instead of each ( k − 1 ) (k-1) ( k − 1 ) -clique corresponding to just one variable, we will introduce a new constant parameter ζ \zeta ζ , and have each ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -clique correspond to log C ζ n \log_{\!C}^{\zeta} n log C ζ n many variables for some sufficiently large constant C C C . For every ζ \zeta ζ -clique, we will form a clause of arity k = Θ ( log ∣ H ∣ ) k = \Theta(\log|H|) k = Θ ( log ∣ H ∣ ) . To get the set of variables for each clause, we randomly subsample k / ζ k/\zeta k / ζ variables from the set of log C ζ n \log_{\!C}^{\zeta} n log C ζ n variables corresponding to each ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -size sub-clique of the clause’s ζ \zeta ζ -clique.
We show in Lemma 5.4 that a set of random sparse vectors has exemplary small-set-expansion properties. Recall that, without augmentation, any small set of clauses is only mildly compressing – nearly all of the clauses have a ( 1 − ε ) (1-\varepsilon) ( 1 − ε ) fraction of their variables appearing in at most polylog( n ) (n) ( n ) other clauses. In Lemma 5.5 , we layer these two observations to show that augmentation gives the necessary expansion when G G G is sampled from G ( n , 1 2 ) \mathcal{G}(n,\frac{1}{2}) G ( n , 2 1 ) .
At the same time, when G G G is sampled from G ( n , 1 2 , n δ ) \mathcal{G}(n,\frac{1}{2}, n^\delta) G ( n , 2 1 , n δ ) , our hidden “highly compressing” set of clauses is so dense that it remains dense even after this augmentation step, thereby enabling decryption (see proof of Lemma 5.3 ). Notational Guidance. What we called n n n here in this overview, we call n ˉ \bar{n} n ˉ in the technical sections. We will use n n n to refer to the total number of variables resulting from our final transformation as sketched above.
Preliminaries
Notations. A vector is said to be k k k -sparse if it has exactly k k k many non-zero entries. Similarly a matrix is called k k k -sparse if each of its rows forms a k k k -sparse vector. Let hw ( v ) \operatorname{hw}(\mathbf{v}) hw ( v ) be the Hamming weight of v \mathbf{v} v , so hw ( v ) = k \operatorname{hw}(\mathbf{v})=k hw ( v ) = k iff v \mathbf{v} v is a k k k -sparse vector. Let ⋁ v ∈ S v \bigvee_{\mathbf{v}\in S}\mathbf{v} ⋁ v ∈ S v denote the bitwise-OR of all vectors v ∈ S \mathbf{v}\in S v ∈ S . We use [ x ] [x] [ x ] to denote the set { 1 , … , x } \{1,\ldots,x\} { 1 , … , x } . We use N G ( v ) N_G(v) N G ( v ) to denote the open neighborhood of vertex v v v with respect to the graph G G G , i.e. all nodes (barring v v v ) in G G G that are connected to v v v with an edge. Throughout, the reader may assume that quantities are rounded to integer values as needed. All logarithms are taken base 2.
Definition 3.1 ((γ , k , t \gamma,k,t γ , k , t )-Expanding Set System). Let S S S be a collection of sets. We say that S S S is a ( γ , k , t ) (\gamma,k,t) ( γ , k , t ) -expanding set system iff:
∀ S ∈ S \forall S\in\mathcal{S} ∀ S ∈ S , ∣ S ∣ = k |S|=k ∣ S ∣ = k , and
∀ T ⊆ S \forall T\subseteq\mathcal{S} ∀ T ⊆ S such that ∣ T ∣ ≤ t |T|\leq t ∣ T ∣ ≤ t :
∣ ⋃ S ∈ T S ∣ ≥ γ ⋅ k ∣ T ∣ . \left|\bigcup_{S\in T}S\right|\geq\gamma\cdot k|T|. S ∈ T ⋃ S ≥ γ ⋅ k ∣ T ∣.
Definition 3.2 ((γ , k , t \gamma,k,t γ , k , t )-Expanding Matrix). We say that S ∈ { 0 , 1 } m × n \mathcal{S}\in\{0,1\}^{m\times n} S ∈ { 0 , 1 } m × n corresponds to a ( γ , k , t ) (\gamma,k,t) ( γ , k , t ) -expanding set system iff:
For all rows S i \mathbf{S}_i S i of S \mathcal{S} S , we have that hw ( S i ) = k \operatorname{hw}(\mathbf{S}_i)=k hw ( S i ) = k , and
∀ T ⊆ { 1 , … , m } \forall T\subseteq\{1,\ldots,m\} ∀ T ⊆ { 1 , … , m } such that ∣ T ∣ ≤ t |T|\leq t ∣ T ∣ ≤ t :
hw ( ⋁ i ∈ T S i ) ≥ γ ⋅ k ∣ T ∣ . \operatorname{hw}\left(\bigvee_{i\in T}\mathbf{S}_i\right)\geq\gamma\cdot k|T|. hw ( i ∈ T ⋁ S i ) ≥ γ ⋅ k ∣ T ∣.
Weak Public Key Encryption
Definition 3.3 (Adapted from Definition 4.1 in [5 ] ). An ( ψ ( n ) , ϕ ( n ) ) (\psi(n),\phi(n)) ( ψ ( n ) , ϕ ( n )) -secure public-key bit encryption scheme is a triple ( G e n , E n c , D e c ) (\mathsf{Gen},\mathsf{Enc},\mathsf{Dec}) ( Gen , Enc , Dec ) of probabilistic polynomial time algorithms such that
Algorithm Gen , on input 1 n 1^n 1 n , produces a pair ( p k , s k ) (pk,sk) ( p k , s k ) .
((1 − ψ 1-\psi 1 − ψ )-correctness) For a random bit b ← { 0 , 1 } b\leftarrow\{0,1\} b ← { 0 , 1 } ,
Pr [ D e c s k ( E n c p k ( b ) ) = b ] > 1 − ψ ( n ) , \Pr[\mathsf{Dec}_{sk}(\mathsf{Enc}_{pk}(b))=b]>1-\psi(n), Pr [ Dec s k ( Enc p k ( b )) = b ] > 1 − ψ ( n ) , where ( p k , s k ) ← $ G e n ( 1 n ) (pk,sk)\mathrel{\stackrel{\$}{\leftarrow}}\mathsf{Gen}(1^n) ( p k , s k ) ← $ Gen ( 1 n ) and the probability is over the randomness of Gen, Enc, Dec, and the choice of b b b .
(ϕ \phi ϕ -privacy) The distributions ( p k , E n c p k ( 0 ) ) (pk,\mathsf{Enc}_{pk}(0)) ( p k , Enc p k ( 0 )) and ( p k , E n c p k ( 1 ) ) (pk,\mathsf{Enc}_{pk}(1)) ( p k , Enc p k ( 1 )) are ϕ ( n ) \phi(n) ϕ ( n ) -indistinguishable, where ( p k , s k ) ← $ G e n ( 1 n ) (pk,sk)\mathrel{\stackrel{\$}{\leftarrow}}\mathsf{Gen}(1^n) ( p k , s k ) ← $ Gen ( 1 n ) .
If ψ ( n ) \psi(n) ψ ( n ) and ϕ ( n ) \phi(n) ϕ ( n ) satisfy ψ < ( 1 − ϕ ) / 2 \psi<(1-\sqrt{\phi})/2 ψ < ( 1 − ϕ ) /2 and ϕ \phi ϕ is a constant, we say that the scheme is a weak PKE.
Lemma 3.4 (See Theorem 6 in [47 ] ). Every weak PKE can be transformed into a semantically secure PKE that supports arbitrarily (polynomially) long messages.
Randomized Graph Product. Our version of the randomized graph product is a slight variation of the original definition introduced in [24 MRS20] . This will be a crucial tool for the construction of the PKE.
Definition 3.5 (Randomized Graph Product). Given a graph G = ( V G , E G ) G=(V_G,E_G) G = ( V G , E G ) , integer ℓ \ell ℓ , and probability p p p , we define the randomized graph product H : = ( V H , E H ) ← $ R P p ℓ ( G ) H := (V_H,E_H) \overset{\$}{\leftarrow} \mathrm{RP}_{p}^{\ell}(G) H := ( V H , E H ) ← $ RP p ℓ ( G ) as follows:
Let V ′ = ( v 1 , v 2 , … , v ( ∣ V G ∣ ℓ ) ) V' = (v_1,v_2,\ldots,v_{\binom{|V_G|}{\ell}}) V ′ = ( v 1 , v 2 , … , v ( ℓ ∣ V G ∣ ) ) denote an ordered sequence of labels. Every label v ∈ V ′ v \in V' v ∈ V ′ corresponds to a subset U v ⊂ V G U_v \subset V_G U v ⊂ V G of size ℓ \ell ℓ ordered in some fixed “canonical” sense.
Let V H V_H V H be the node set of H H H created in the following manner: for every v ∈ V ′ v \in V' v ∈ V ′ , add v v v to V H V_H V H independently with probability p p p .
For each u , v ∈ V H u,v \in V_H u , v ∈ V H with u ≠ v u \ne v u = v , let ( u , v ) ∈ E H (u,v) \in E_H ( u , v ) ∈ E H iff U u ∪ U v U_u \cup U_v U u ∪ U v induces a clique in G G G .
Our Hardness Conjectures
In this section we redefine the conjectures and all of their variants formally as we use them in the paper.
The Planted Clique Conjecture
Conjecture 4.1 (n log α n n^{\log^\alpha n} n l o g α n hardness of the Planted Clique Conjecture). There exist constants 0 < α < 1 0 < \alpha< 1 0 < α < 1 and δ ∈ ( 0 , 1 2 ) \delta\in(0,\frac{1}{2}) δ ∈ ( 0 , 2 1 ) such that, for all n O ( ( log n ) α ) n^{O((\log n)^\alpha)} n O (( l o g n ) α ) -size algorithms A \mathcal{A} A ,
∣ Pr [ A ( G ) = 1 ∣ G ← $ G ( n , 1 2 ) ] − Pr [ A ( G ) = 1 ∣ G ← $ G ( n , 1 2 , n δ ) ] ∣ ≤ 1 3 . \left|\Pr\left[\mathcal{A}(G)=1 \mid G \overset{\$}{\leftarrow} G\left(n,\frac{1}{2}\right)\right]-\Pr\left[\mathcal{A}(G)=1 \mid G \overset{\$}{\leftarrow} G\left(n,\frac{1}{2},n^\delta\right)\right]\right| \le\frac{1}{3}. Pr [ A ( G ) = 1 ∣ G ← $ G ( n , 2 1 ) ] − Pr [ A ( G ) = 1 ∣ G ← $ G ( n , 2 1 , n δ ) ] ≤ 3 1 .
Remark 4.2. Recall that, for conciseness, we simply refer to the above as “the planted clique conjecture.”
As discussed earlier, this conjecture is based on a long line of work in the average-case complexity community [7 , 52 Kuc95̌, 54 , 35 , 53 , 5 , 3 MRS20, 45 , 1 , 2 , 21 , 14 , 13 , 48 , 65 , 61 , 50 ] .
Noisy k k k -LIN Conjecture
We first restate the standard noisy k k k -LIN conjecture from the introduction. Recall that this conjecture is substantiated by a long series of works giving lower bounds on the k k k -LIN problem [44 , 38 , 75 , 19 , 73 , 39 , 12 , 25 , 58 ] .
Conjecture 4.3 (Noisy k k k -LIN Conjecture). There exists a constant γ ∈ ( 1 2 , 1 ) \gamma\in(\frac{1}{2},1) γ ∈ ( 2 1 , 1 ) such that the following holds. Let α , ς \alpha,\varsigma α , ς be any constants with α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) and ς > 0 \varsigma> 0 ς > 0 . Then, for n n n large enough, prime p = n Ω ( 1 ) p=n^{\Omega(1)} p = n Ω ( 1 ) , k = Ω ( log ( n ) ) k=\Omega(\log(n)) k = Ω ( log ( n )) , we have the following: For all ( γ , k , 2 ( log n ) α ) (\gamma,k,2^{(\log n)^\alpha}) ( γ , k , 2 ( l o g n ) α ) -expanding matrices S ‾ ∈ { 0 , 1 } m × n \overline{S} \in\{0,1\}^{m\times n} S ∈ { 0 , 1 } m × n and for all polynomial sized adversaries A \mathcal{A} A ,
∣ Pr A , s , e [ A ( A , b ) = 1 ∣ s ← $ F p n , b = A s + e ] − Pr A , b [ A ( A , b ) = 1 ∣ b ← $ F p m ] ∣ ≤ 1 4 . \left|\Pr_{A,s,e}\left[\mathcal{A}(A,b)=1 \mid s \overset{\$}{\leftarrow} \mathbb{F}_p^n,b=As+e\right]-\Pr_{A,b}\left[\mathcal{A}(A,b)=1 \mid b \overset{\$}{\leftarrow} \mathbb{F}_p^m\right]\right| \le\frac{1}{4}. A , s , e Pr [ A ( A , b ) = 1 ∣ s ← $ F p n , b = A s + e ] − A , b Pr [ A ( A , b ) = 1 ∣ b ← $ F p m ] ≤ 4 1 . In the above, A ∈ F p m × n A \in\mathbb{F}_p^{m\times n} A ∈ F p m × n is the matrix produce by replacing each nonzero entry in S ‾ \overline{S} S with a random element in F p ∗ \mathbb{F}_p^* F p ∗ , and e e e is sampled as:
e i = { Random element of F p ∗ , with probability η = ( log n ) − ς , 0 , otherwise. e_i =
\begin{cases}
\text{Random element of }\mathbb{F}_p^*, & \text{with probability }\eta=(\log n)^{-\varsigma},\\
0, & \text{otherwise.}
\end{cases} e i = { Random element of F p ∗ , 0 , with probability η = ( log n ) − ς , otherwise.
Below we define the analogous search version of the noisy k k k -XOR conjecture which we use to construct another PKE in § 11 .
Conjecture 4.4 (Search Noisy k k k -LIN Conjecture). There exists a constant γ ∈ ( 1 2 , 1 ) \gamma\in\left(\frac{1}{2},1\right) γ ∈ ( 2 1 , 1 ) such that the following holds. Let α , ς \alpha,\varsigma α , ς be any constants with α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) and ς > 0 \varsigma> 0 ς > 0 . Then, for n n n large enough, prime p = n Ω ( 1 ) p=n^{\Omega(1)} p = n Ω ( 1 ) , k = Ω ( log ( n ) ) k=\Omega(\log(n)) k = Ω ( log ( n )) , we have the following: For all ( γ , k , 2 ( log n ) α ) (\gamma,k,2^{(\log n)^\alpha}) ( γ , k , 2 ( l o g n ) α ) -expanding matrices A ˉ ∈ { 0 , 1 } m × n \bar{A}\in\{0,1\}^{m\times n} A ˉ ∈ { 0 , 1 } m × n and for all polynomial sized adversaries A \mathcal{A} A ,
Pr A , s , e [ A ( A ˉ , b ) = s ∣ s ← $ F p n , b = A s + e ] ≤ 1 4 . \Pr_{\mathcal{A},s,e}\left[\mathcal{A}(\bar{A},b)=s\mid s\mathrel{\overset{\$}{\leftarrow}}\mathbb{F}_p^n,\ b=As+e\right]\leq\frac{1}{4}. A , s , e Pr [ A ( A ˉ , b ) = s ∣ s ← $ F p n , b = A s + e ] ≤ 4 1 . In the above, A ∈ F p m × n A\in\mathbb{F}_p^{m\times n} A ∈ F p m × n is the matrix produce by replacing each nonzero entry in A ˉ \bar{A} A ˉ with a random element in F p ∗ \mathbb{F}_p^* F p ∗ , and e e e is sampled as:
e i = { Random element of F p ∗ , with probability η = ( log n ) − ς , 0 , otherwise. e_i=
\begin{cases}
\text{Random element of }\mathbb{F}_p^*, & \text{with probability }\eta=(\log n)^{-\varsigma},\\
0, & \text{otherwise.}
\end{cases} e i = { Random element of F p ∗ , 0 , with probability η = ( log n ) − ς , otherwise.
In other words, it should be hard to recover s s s given ( A , A s + e ) (A,As+e) ( A , A s + e ) . In § 11 we present a PKE construction from Conjecture 1.1 and Conjecture 4.4 . While a reduction from search to decision noisy k k k -LIN exists for random expander matrices A A A [12 , 25 ] , the reduction suffers from a polynomial loss in the sample complexity, i.e. the number of clauses. Thus our construction in § 11 relies on a potentially weaker12 assumption that the one in § 5 for the following two reasons: (1) the semantic security reduction to the search version does not suffer from a polynomial loss, and (2) it is unclear if the search-decision reduction mentioned above extends to arbitrary expander matrices A A A .
Non-Compression. In fact, the matrix A A A from both of our PKE schemes satisfies an additional property: The matrix S ∈ { 0 , 1 } m × n S\in\{0,1\}^{m\times n} S ∈ { 0 , 1 } m × n indicating the nonzero entries in A A A is a ( γ , Θ ( log n ) ) (\gamma,\Theta(\log n)) ( γ , Θ ( log n )) -non-compressing matrix, for any constant 0 < γ < 1 0<\gamma<1 0 < γ < 1 fixed at the beginning of key generation. We define this property below.
Definition 4.5 (( γ , k ) ( \gamma,k) ( γ , k ) -Non-Compressing Matrix). We say that S ∈ F 2 m × n S\in\mathbb{F}_2^{m\times n} S ∈ F 2 m × n is a ( γ , k ) (\gamma,k) ( γ , k ) -non-compressing matrix iff:
For all rows S i S_i S i of S S S , we have that hw ( S i ) = k \operatorname{hw}(S_i)=k hw ( S i ) = k , and
∀ T ⊆ { 1 , … , m } \forall T\subseteq\{1,\ldots,m\} ∀ T ⊆ { 1 , … , m } :
hw ( ⋁ i ∈ T S i ) ≥ ∣ T ∣ γ . \operatorname{hw}\left(\bigvee_{i\in T}S_i\right)\geq|T|^\gamma. hw ( i ∈ T ⋁ S i ) ≥ ∣ T ∣ γ .
In other words, for every arbitrarily large set of rows, the sum of hamming weights for those rows should not be much greater than the hamming weight when we bitwise-OR all of the rows together. This property is desirable in the context of Goldreich’s candidate one-way function [43 , 11 , 8 ] , which is highly related to noisy k k k -LIN. (In this context “non-compression” is known as “low stretch.”)
Public key encryption from Planted Clique and Noisy k k k -LIN
In this section, we give a PKE scheme from the decisional noisy k k k -LIN conjecture. For a description of how to use the search version, see § 11 .
Suggested Parameters. We suggest the following choices of parameters. The constants are solely optimized for exposition, and we believe they can be improved significantly while still maintaining the integrity of the scheme. Let α , δ ∈ ( 0 , 1 2 ) \alpha, \delta\in\left(0,\frac{1}{2}\right) α , δ ∈ ( 0 , 2 1 ) be constants such that Conjecture 1.1 holds, and let γ ∈ ( 1 2 , 1 ) \gamma\in\left(\frac{1}{2},1\right) γ ∈ ( 2 1 , 1 ) be a constant such that Conjecture 4.3 holds. (If Conjecture 1.1 holds for some α ≥ 1 2 \alpha\ge\frac{1}{2} α ≥ 2 1 , this automatically implies that the conjecture holds for all α ∈ ( 0 , 1 2 ) \alpha\in\left(0,\frac{1}{2}\right) α ∈ ( 0 , 2 1 ) .) Assuming the security parameter is λ \lambda λ , we will set the following parameters:
p p p is any prime.
Size of initial Erdos-Renyi random graph: n ˉ = 2 ( log λ ) 1 / ( 1 + α ) \bar{n}=2^{(\log\lambda)^{1/(1+\alpha)}} n ˉ = 2 ( l o g λ ) 1/ ( 1 + α ) .
Planted clique size: k ˉ = n ˉ δ \bar{k}=\bar{n}^{\delta} k ˉ = n ˉ δ .
Graph product parameter for RP: ℓ = ( log n ˉ ) α \ell=(\log\bar{n})^{\alpha} ℓ = ( log n ˉ ) α .
Node deletion probability for RP: q = n ˉ − ( δ ℓ ) / 2 q=\bar{n}^{-(\delta\ell)/2} q = n ˉ − ( δ ℓ ) /2 .
Clique size (constant integer) for constructing k k k -LIN matrix: ζ = ⌈ 1 1 − γ ⌉ + 1 \zeta=\left\lceil\frac{1}{1-\sqrt{\gamma}}\right\rceil+1 ζ = ⌈ 1 − γ 1 ⌉ + 1 .
Exponent (constant) for block size in k k k -LIN matrix: β = ζ ⋅ ( ζ ( 1 − α ) + 2 ) \beta=\zeta\cdot(\zeta(1-\alpha)+2) β = ζ ⋅ ( ζ ( 1 − α ) + 2 ) .
Exponent (constant) for Bernoulli noise for k k k -LIN samples: ρ = 2 + β ζ \rho=2+\beta\zeta ρ = 2 + β ζ .
Remark 5.1. The final three parameters are balanced so that, if our final k k k -LIN matrix A ∈ F 2 m × n A\in\mathbb{F}_2^{m\times n} A ∈ F 2 m × n is constructed from an Erdős–Rényi graph without a planted clique, we achieve arbitrarily high expansion on all sets of at most t = 2 ( log n ) α t=2^{(\log n)^{\alpha}} t = 2 ( l o g n ) α many rows, while maintaining an error rate of ( log t ) − O ( 1 ) (\log t)^{-O(1)} ( log t ) − O ( 1 ) . At the same time, we achieve arbitrarily high non-compression over the entire matrix.
Notations. Let H ← $ R P ℓ ( G ) H\stackrel{\$}{\leftarrow}\mathrm{RP}^{\ell}(G) H ← $ RP ℓ ( G ) . Then, by construction, every node v ∈ V H v\in V_H v ∈ V H corresponds to a set U v ⊂ V G U_v\subset V_G U v ⊂ V G of size ℓ \ell ℓ in some “canonical” order. Let c H , ζ c_{H,\zeta} c H , ζ denote the total number of ζ \zeta ζ -cliques in a graph H H H . Let A i A_i A i denote the i t h i^{\mathrm{th}} i th row of a matrix A A A . Allow ∥ \| ∥ to denote the concatenation of two vectors in the standard sense. We abuse notation and allow ( G , K G ) ← $ G ( n ˉ , 1 2 , k ˉ ) (G,K_G)\stackrel{\$}{\leftarrow}\mathcal{G}(\bar{n},\frac{1}{2},\bar{k}) ( G , K G ) ← $ G ( n ˉ , 2 1 , k ˉ ) to denote a graph G G G drawn from the planted Erdős–Rényi distribution along with the set of vertices K G K_G K G for the planted clique.
Encoding Process. First we describe a randomized encoding of any graph H H H with n n n nodes into a sparse matrix S ∈ { 0 , 1 } m × n S\in\{0,1\}^{m\times n} S ∈ { 0 , 1 } m × n , where m = c H , ζ m=c_{H,\zeta} m = c H , ζ and n = c H , ζ − 1 ⋅ log β m n=c_{H,\zeta-1}\cdot\log^{\beta}m n = c H , ζ − 1 ⋅ log β m . We use this algorithm in the key generation step of the PKE.
⋆ A ← Encode ( H , ζ , β ) \star\ A\leftarrow\operatorname{Encode}(H,\zeta,\beta) ⋆ A ← Encode ( H , ζ , β ) :
Let m = c H , ζ m=c_{H,\zeta} m = c H , ζ . Enumerate over all ζ \zeta ζ -cliques of H H H in a fixed canonical order and create labels ( R 1 , R 2 , … , R m ) (R_1,R_2,\ldots,R_m) ( R 1 , R 2 , … , R m ) .
Let n ′ = c H , ζ − 1 n'=c_{H,\zeta-1} n ′ = c H , ζ − 1 . Enumerate over all ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -cliques of H H H in a fixed canonical order and create labels ( C 1 , C 2 , … , C n ′ ) (C_1,C_2,\ldots,C_{n'}) ( C 1 , C 2 , … , C n ′ ) .
For all i ∈ [ m ] , j ∈ [ n ′ ] i\in[m],j\in[n'] i ∈ [ m ] , j ∈ [ n ′ ] do the following:
Set an indicator variable I i , j = 1 I_{i,j}=1 I i , j = 1 if the ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -clique labeled C j C_j C j is a subgraph of the ζ \zeta ζ -clique labeled R i R_i R i , and set I i , j = 0 I_{i,j}=0 I i , j = 0 otherwise.
For all i ∈ [ m ] , j ∈ [ n ′ ] i\in[m],j\in[n'] i ∈ [ m ] , j ∈ [ n ′ ] do the following:
Set b i , j ∈ { 0 , 1 } ( log m ) β \mathbf{b}_{i,j}\in\{0,1\}^{(\log m)^\beta} b i , j ∈ { 0 , 1 } ( l o g m ) β to be a random log m ζ \frac{\log m}{\zeta} ζ l o g m -sparse vector if I i , j = 1 I_{i,j}=1 I i , j = 1 , and set b i j = \mathbf{b}_{ij}= b ij = ♀♀♀♀♀♀
0 log β m 0^{\log^{\beta} m} 0 l o g β m otherwise. We refer to each b i , j b_{i,j} b i , j as a block .
For all i ∈ [ m ] i \in[m] i ∈ [ m ] , set S i : = ( b i , 1 ∥ b i , 2 ∥ ⋯ ∥ b i , n ′ ) S_i := (b_{i,1} \| b_{i,2} \| \cdots\| b_{i,n^{\prime}}) S i := ( b i , 1 ∥ b i , 2 ∥ ⋯ ∥ b i , n ′ ) .
Output S S S .
Key Generation.
⋆ ( p k , s k ) ← Gen ( 1 λ ) (\mathrm{pk},\mathrm{sk}) \leftarrow\operatorname{Gen}(1^{\lambda}) ( pk , sk ) ← Gen ( 1 λ ) :
( G , K G ) ← $ G ( n ˉ , 1 2 , k ˉ ) (G, K_G) \overset{\$}{\leftarrow} \mathcal{G}(\bar{n}, \frac{1}{2}, \bar{k}) ( G , K G ) ← $ G ( n ˉ , 2 1 , k ˉ ) .
H ← $ RP q ℓ ( G ) H \overset{\$}{\leftarrow} \operatorname{RP}_{q}^{\ell}(G) H ← $ RP q ℓ ( G ) .
Define K H = { v ∈ V H : U v ⊂ K G } K_H = \{v \in V_H : U_v \subset K_G\} K H = { v ∈ V H : U v ⊂ K G } .
A ˉ ← Encode ( H , ζ , β ) \bar{A} \leftarrow\operatorname{Encode}(H, \zeta, \beta) A ˉ ← Encode ( H , ζ , β ) . Let S S S have m m m rows and n n n columns. Let A ˉ ∈ F p m × n \bar{A} \in\mathbb{F}_p^{m \times n} A ˉ ∈ F p m × n be the matrix where we replace each nonzero entry in A ˉ \bar{A} A ˉ with a random element in F p ∗ \mathbb{F}_p^{*} F p ∗ .
p k : = A \mathrm{pk} := A pk := A .
s k : = ( H , K H ) \mathrm{sk} := (H, K_H) sk := ( H , K H ) .
Output ( p k , s k ) (\mathrm{pk}, \mathrm{sk}) ( pk , sk ) .
Encryption.
⋆ c t ← Enc ( 1 λ , p k , b ∈ { 0 , 1 } ) \mathrm{ct} \leftarrow\operatorname{Enc}(1^{\lambda}, \mathrm{pk}, b \in\{0,1\}) ct ← Enc ( 1 λ , pk , b ∈ { 0 , 1 }) :
Parse p k \mathrm{pk} pk as A A A . Let A A A have m m m rows and n n n columns.
Sample e e e as:
e i = { Random element of F p ∗ , with probability η = ( log n ) − ζ , 0 , otherwise. e_i =
\begin{cases}
\text{Random element of }\mathbb{F}_p^{*}, & \text{with probability }\eta= (\log n)^{-\zeta},\\
0, & \text{otherwise.}
\end{cases} e i = { Random element of F p ∗ , 0 , with probability η = ( log n ) − ζ , otherwise.
Sample s ← $ F p n s \overset{\$}{\leftarrow} \mathbb{F}_p^n s ← $ F p n .
If b = 0 b = 0 b = 0 , then c t ← A s + e \mathrm{ct} \leftarrow As + e ct ← A s + e .
If b = 1 b = 1 b = 1 , then c t ← $ F 2 m \mathrm{ct} \overset{\$}{\leftarrow} \mathbb{F}_2^m ct ← $ F 2 m .
Output c t \mathrm{ct} ct .
Decryption.
⋆ b ′ ← Dec ( 1 λ , p k , s k , c t ) b^{\prime} \leftarrow\operatorname{Dec}(1^{\lambda}, \mathrm{pk}, \mathrm{sk}, \mathrm{ct}) b ′ ← Dec ( 1 λ , pk , sk , ct ) :
Parse p k \mathrm{pk} pk as A A A . Let A A A have m m m rows and n n n columns.
Parse s k \mathrm{sk} sk as ( H , K H ) (H, K_H) ( H , K H ) .
Parse c t \mathrm{ct} ct as b b b .
Let η \eta η be any (superconstant) integer satisfying ( log n ) ρ − 1 ≤ ( ζ η ) ≤ 2 ( log n ) ρ − 1 (\log n)^{\rho-1} \le\binom{\zeta}{\eta} \le2(\log n)^{\rho-1} ( log n ) ρ − 1 ≤ ( η ζ ) ≤ 2 ( log n ) ρ − 1 .
Uniformly randomly select a subset T ⊂ K H T \subset K_H T ⊂ K H among all subsets of size η \eta η .
Recompute all canonical labels R i R_i R i and C j C_j C j . Recompute the indicator variables I i , j I_{i,j} I i , j .
Define X i ( ζ ) X_i^{(\zeta)} X i ( ζ ) as the subset of V H V_H V H corresponding to the ζ \zeta ζ -clique labeled as R i R_i R i . Define a set S S S of row labels of A \mathbf{A} A as
S = { i : X i ( ζ ) ⊂ T } S = \{i : X_i^{(\zeta)} \subset T\} S = { i : X i ( ζ ) ⊂ T }
Split every row of A \mathbf{A} A into blocks of length log β m \log^\beta m log β m , i.e., A i = ( b i , 1 ∥ ⋯ ∥ b i , c H , ζ − 1 ) \mathbf{A}_i = (b_{i,1} \mathbin\Vert\cdots\mathbin\Vert b_{i,c_{H,\zeta-1}}) A i = ( b i , 1 ∥ ⋯ ∥ b i , c H , ζ − 1 ) where every b i , j b_{i,j} b i , j has width log β m \log^\beta m log β m . Define a set of block labels S ′ ⊂ [ c H , ζ − 1 ] S' \subset[c_{H,\zeta-1}] S ′ ⊂ [ c H , ζ − 1 ] such that
S ′ = { j : ∃ i ∈ S such that I i , j = 1 } . S' = \{j : \exists i \in S \text{ such that } I_{i,j} = 1\}. S ′ = { j : ∃ i ∈ S such that I i , j = 1 } .
Let A ~ \widetilde{\mathbf{A}} A be the submatrix of A \mathbf{A} A with rows labeled by S S S and columns made by concatenating the blocks labeled by S ′ S' S ′ .
Solve the following system of linear equations using Gaussian elimination:
A ~ x ~ = b ∣ S , \widetilde{\mathbf{A}}\widetilde{x} = b|_S, A x = b ∣ S ,
where b ∣ S b|_S b ∣ S is the vector b b b restricted to indices in S S S .
If the above step returns a valid solution, then output b ′ = 0 b' = 0 b ′ = 0 . Otherwise output b ′ = 1 b' = 1 b ′ = 1 .
Correctness
First, we show that K H K_H K H is almost surely very large.
Lemma 5.2. For all constants α , δ ∈ ( 0 , 1 2 ) \alpha, \delta\in(0, \frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) , for all large enough λ \lambda λ , the following holds. Let n ˉ = 2 ( log λ ) 1 / ( 1 + α ) \bar{n} = 2^{(\log\lambda)^{1/(1+\alpha)}} n ˉ = 2 ( l o g λ ) 1/ ( 1 + α ) , k ˉ = n ˉ δ \bar{k} = \bar{n}^{\delta} k ˉ = n ˉ δ , ℓ = ( log n ˉ ) α \ell= (\log\bar{n})^\alpha ℓ = ( log n ˉ ) α , and q = n ˉ − ( δ ℓ ) / 2 q = \bar{n}^{-(\delta\ell)/2} q = n ˉ − ( δ ℓ ) /2 . Then the set K H K_H K H produced in algorithm Gen satisfies
∣ K H ∣ > ∣ V H ∣ δ / 2 |K_H| > |V_H|^{\delta/2} ∣ K H ∣ > ∣ V H ∣ δ /2 with all but o ( 1 ) o(1) o ( 1 ) probability over the randomness of R P k ˉ ℓ \mathrm{RP}^{\ell}_{\bar{k}} RP k ˉ ℓ .
Proof. The planted clique contains ( k ˉ ℓ ) \binom{\bar{k}}{\ell} ( ℓ k ˉ ) many ℓ \ell ℓ -tuples of vertices, and the entire graph G G G contains ( n ˉ ℓ ) \binom{\bar{n}}{\ell} ( ℓ n ˉ ) many ℓ \ell ℓ -tuples. Each ℓ \ell ℓ -tuple becomes a vertex in H H H independently with probability n ˉ − δ ℓ / 2 \bar{n}^{-\delta\ell/2} n ˉ − δ ℓ /2 , so a Chernoff argument shows that ∣ V H ∣ = n ˉ ( 1 − δ / 2 ± o ( 1 ) ) ℓ |V_H| = \bar{n}^{(1-\delta/2\pm o(1))\ell} ∣ V H ∣ = n ˉ ( 1 − δ /2 ± o ( 1 )) ℓ with all but o ( 1 ) o(1) o ( 1 ) probability. Since k ˉ = n ˉ δ \bar{k} = \bar{n}^{\delta} k ˉ = n ˉ δ , another Chernoff argument shows that the number of ℓ \ell ℓ -tuples inherited from the planted clique is n ˉ ( δ / 2 ± o ( 1 ) ) ℓ = ∣ V H ∣ δ / ( 2 − δ ) ± o ( 1 ) > ∣ V H ∣ δ / 2 \bar{n}^{(\delta/2\pm o(1))\ell} = |V_H|^{\delta/(2-\delta)\pm o(1)} > |V_H|^{\delta/2} n ˉ ( δ /2 ± o ( 1 )) ℓ = ∣ V H ∣ δ / ( 2 − δ ) ± o ( 1 ) > ∣ V H ∣ δ /2 with all but o ( 1 ) o(1) o ( 1 ) probability, with the last inequality holding for all large enough λ \lambda λ . □
We use the above to argue decryption correctness.
Lemma 5.3. For all constants α , δ ∈ ( 0 , 1 2 ) \alpha, \delta\in(0, \frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) , for all large enough λ \lambda λ , the following holds. Let n ˉ = 2 ( log λ ) 1 / ( 1 + α ) \bar{n} = 2^{(\log\lambda)^{1/(1+\alpha)}} n ˉ = 2 ( l o g λ ) 1/ ( 1 + α ) , k ˉ = n ˉ δ \bar{k} = \bar{n}^{\delta} k ˉ = n ˉ δ , ℓ = ( log n ˉ ) α \ell= (\log\bar{n})^\alpha ℓ = ( log n ˉ ) α , q = n ˉ − ( δ ℓ ) / 2 q = \bar{n}^{-(\delta\ell)/2} q = n ˉ − ( δ ℓ ) /2 , ζ > 1 \zeta> 1 ζ > 1 be a constant integer, β = Θ ( 1 ) \beta= \Theta(1) β = Θ ( 1 ) , and ρ = 2 + β ζ \rho= 2 + \beta\zeta ρ = 2 + β ζ . Then for all b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 }
Pr ( p k , s k ) ← G e n ( 1 n ˉ ) [ D e c ( s k , E n c ( p k , b ) ) = b ] ≥ 1 − o ( 1 ) , \Pr_{(\mathrm{pk},\mathrm{sk})\leftarrow\mathrm{Gen}(1^{\bar{n}})}
[\mathrm{Dec}(\mathrm{sk},\mathrm{Enc}(\mathrm{pk},b)) = b] \ge1-o(1), ( pk , sk ) ← Gen ( 1 n ˉ ) Pr [ Dec ( sk , Enc ( pk , b )) = b ] ≥ 1 − o ( 1 ) , where the probability is over the coins of Encode, Gen, Enc, and Dec.
Proof. Let A \mathbf{A} A have m m m rows and n n n columns. First observe that K H K_H K H is made of nodes that form a subgraph of K K K in G G G , and therefore K H K_H K H must form a clique. Moreover by Lemma 5.2 , the size of K H K_H K H is more than ∣ V H ∣ δ / 2 |V_H|^{\delta/2} ∣ V H ∣ δ /2 with all but o ( 1 ) o(1) o ( 1 ) probability. Since ρ \rho ρ is a constant, we can always find an integer η \eta η satisfying the requirement for decryption. By construction, ∣ T ∣ = η |T|=\eta ∣ T ∣ = η , and T T T induces a clique in H H H . Moreover, S S S contains precisely all of the row labels for ζ \zeta ζ -cliques that are subgraphs of T T T , and ∣ S ∣ = ( η ζ ) |S|=\binom{\eta}{\zeta} ∣ S ∣ = ( ζ η ) .
The encoding of H H H to A \mathbf{A} A is such that for any row A i \mathbf{A}_i A i , the j t h j^{\mathrm{th}} j th block b i , j \mathbf{b}_{i,j} b i , j is non-zero (i.e. I i , j = 1 I_{i,j}=1 I i , j = 1 ) iff the ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -clique labeled as C j C_j C j is a subgraph of the ζ \zeta ζ -clique labeled as R i R_i R i . As S S S contains all ζ \zeta ζ sized cliques that are a subgraph of T T T , and T T T is a clique, the set S S S corresponds to row labels of all possible ζ \zeta ζ -cliques that are subgraphs of T T T . This count is exactly ( η ζ ) \binom{\eta}{\zeta} ( ζ η ) . A similar argument shows that the size of S ′ S' S ′ is exactly ( η ζ − 1 ) \binom{\eta}{\zeta-1} ( ζ − 1 η ) . Thus, the total number of columns in A ~ \widetilde{\mathbf{A}} A is ( η ζ − 1 ) ⋅ log β m \binom{\eta}{\zeta-1}\cdot\log^\beta m ( ζ − 1 η ) ⋅ log β m , and the total number of rows is ( η ζ ) \binom{\eta}{\zeta} ( ζ η ) .
Note that for every choice of x ∈ F p ( η ζ − 1 ) ⋅ log β m \mathbf{x}\in\mathbb{F}_p^{\binom{\eta}{\zeta-1}\cdot\log^\beta m} x ∈ F p ( ζ − 1 η ) ⋅ l o g β m , we have that A ~ x \widetilde{\mathbf{A}}\mathbf{x} A x can map to at most one unique vector in F p ( η ζ ) \mathbb{F}_p^{\binom{\eta}{\zeta}} F p ( ζ η ) . Also, since ζ \zeta ζ is a constant and ( η ζ ) = Θ ( ( log n ) ρ − 1 ) \binom{\eta}{\zeta}=\Theta((\log n)^{\rho-1}) ( ζ η ) = Θ (( log n ) ρ − 1 ) , we have that η = Θ ( ( log n ) ( ρ − 1 ) / ζ ) \eta=\Theta((\log n)^{(\rho-1)/\zeta}) η = Θ (( log n ) ( ρ − 1 ) / ζ ) by the Stirling approximation. Thus if we encrypted a 1, i.e. b ∣ S \mathbf{b}|_S b ∣ S is a random vector in F p ∣ S ∣ \mathbb{F}_p^{|S|} F p ∣ S ∣ , then the probability that Gaussian elimination will return a solution is upper bounded as follows.
Pr [ return solution ] ≤ p ( η ζ − 1 ) ⋅ log β m p ( η ζ ) ≤ p ( η ζ − 1 ) ⋅ log β m p ( η ζ ) ≤ 2 ( η ζ − 1 ) ⋅ log β m − ( η ζ ) < 2 η ζ − 1 ⋅ log β m − Ω ( η ζ ) \begin{aligned}
\Pr[\text{return solution}] &\le\frac{p^{\binom{\eta}{\zeta-1}\cdot\log^\beta m}}{p^{\binom{\eta}{\zeta}}}\\
&\le\frac{p^{\binom{\eta}{\zeta-1}\cdot\log^\beta m}}{p^{\binom{\eta}{\zeta}}}\\
&\le2^{\binom{\eta}{\zeta-1}\cdot\log^\beta m-\binom{\eta}{\zeta}}\\
&<2^{\eta^{\zeta-1}\cdot\log^\beta m-\Omega(\eta^\zeta)}
\end{aligned} Pr [ return solution ] ≤ p ( ζ η ) p ( ζ − 1 η ) ⋅ l o g β m ≤ p ( ζ η ) p ( ζ − 1 η ) ⋅ l o g β m ≤ 2 ( ζ − 1 η ) ⋅ l o g β m − ( ζ η ) < 2 η ζ − 1 ⋅ l o g β m − Ω ( η ζ )
(Stirling approximation)
≤ 2 O ( ( log n ) ( ρ − 1 ) ⋅ ( ζ − 1 ) / ζ ⋅ log β m ) − Ω ( ( log n ) ρ − 1 ) < 2 O ( ( log n ) ( ρ − 1 ) ⋅ ( ζ − 1 ) / ζ ⋅ ( log n ) β ) − Ω ( ( log n ) ρ − 1 ) \begin{aligned}
&\le2^{O((\log n)^{(\rho-1)\cdot(\zeta-1)/\zeta}\cdot\log^\beta m)-\Omega((\log n)^{\rho-1})}\\
&<2^{O((\log n)^{(\rho-1)\cdot(\zeta-1)/\zeta}\cdot(\log n)^\beta)-\Omega((\log n)^{\rho-1})}
\end{aligned} ≤ 2 O (( l o g n ) ( ρ − 1 ) ⋅ ( ζ − 1 ) / ζ ⋅ l o g β m ) − Ω (( l o g n ) ρ − 1 ) < 2 O (( l o g n ) ( ρ − 1 ) ⋅ ( ζ − 1 ) / ζ ⋅ ( l o g n ) β ) − Ω (( l o g n ) ρ − 1 )
( m (m ( m and n n n are polynomially related w.h.p., and β \beta β is constant) ) )
≤ 2 O ( ( log n ) ( 1 + β ζ ) ⋅ ( ζ − 1 ) / ζ + β ) − Ω ( ( log n ) 1 + β ζ ) \begin{aligned}
&\le2^{O((\log n)^{(1+\beta\zeta)\cdot(\zeta-1)/\zeta+\beta})-\Omega((\log n)^{1+\beta\zeta})}
\end{aligned} ≤ 2 O (( l o g n ) ( 1 + β ζ ) ⋅ ( ζ − 1 ) / ζ + β ) − Ω (( l o g n ) 1 + β ζ )
( ρ = 2 + β ζ ) (\rho=2+\beta\zeta) ( ρ = 2 + β ζ )
≤ 2 O ( ( log n ) 1 + β ζ − 1 / ζ ) − Ω ( ( log n ) 1 + β ζ ) ≤ 2 − Ω ( ( log n ) 1 + β ζ ) . \begin{aligned}
&\le2^{O((\log n)^{1+\beta\zeta-1/\zeta})-\Omega((\log n)^{1+\beta\zeta})}\\
&\le2^{-\Omega((\log n)^{1+\beta\zeta})}.
\end{aligned} ≤ 2 O (( l o g n ) 1 + β ζ − 1/ ζ ) − Ω (( l o g n ) 1 + β ζ ) ≤ 2 − Ω (( l o g n ) 1 + β ζ ) .
( ζ (\zeta ( ζ is a constant) ) )
With (very) high probability, n n n is superconstant in λ \lambda λ . Therefore,
Pr [ ( p k , s k ) ← Gen ( 1 n ) ∧ Dec ( s k , Enc ( p k , 1 ) ) = 1 ] ≥ 1 − o ( 1 ) . \Pr[(\mathsf{pk},\mathsf{sk})\leftarrow\operatorname{Gen}(1^n)\wedge\operatorname{Dec}(\mathsf{sk},\operatorname{Enc}(\mathsf{pk},1))=1]\ge1-o(1). Pr [( pk , sk ) ← Gen ( 1 n ) ∧ Dec ( sk , Enc ( pk , 1 )) = 1 ] ≥ 1 − o ( 1 ) .
Let us look at the case that a 0 was encrypted. Here b = A s + e \mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e} b = As + e . Let S c o l S_{\mathrm{col}} S col be the set of columns for the blocks in S ′ S' S ′ . The linear system solved by Gaussian elimination becomes
A ~ x = A ~ ⋅ ( s ∣ S c o l ) + e ∣ S . \widetilde{\mathbf{A}}\mathbf{x}=\widetilde{\mathbf{A}}\cdot(\mathbf{s}|_{S_{\mathrm{col}}})+\mathbf{e}|_S. A x = A ⋅ ( s ∣ S col ) + e ∣ S .
Now, every entry of e \mathbf{e} e has is nonzero independently with probability at most ( log n ) − ρ (\log n)^{-\rho} ( log n ) − ρ . So the probability that e ∣ S = 0 \mathbf{e}|_S=0 e ∣ S = 0 is at most
( 1 − ( log n ) − ρ ) ∣ S ∣ = ( 1 − ( log n ) − ρ ) ( η ζ ) ≥ ( 1 − ( log n ) − ρ ) Θ ( ( log n ) ρ − 1 ) ≥ 1 − o ( 1 ) , (1-(\log n)^{-\rho})^{|S|}=(1-(\log n)^{-\rho})^{\binom{\eta}{\zeta}}\ge(1-(\log n)^{-\rho})^{\Theta((\log n)^{\rho-1})}\ge1-o(1), ( 1 − ( log n ) − ρ ) ∣ S ∣ = ( 1 − ( log n ) − ρ ) ( ζ η ) ≥ ( 1 − ( log n ) − ρ ) Θ (( l o g n ) ρ − 1 ) ≥ 1 − o ( 1 ) ,
again using that n n n is superconstant in λ \lambda λ with (very) high probability.
If this happens, then Gaussian elimination must return a valid solution. If there is at least one error, it is still possible that we get a valid solution, but this only increases the decryption correctness. Therefore
Pr [ ( p k , s k ) ← Gen ( 1 n ) ∧ Dec ( s k , Enc ( p k , 0 ) ) = 0 ) ] ≥ 1 − o ( 1 ) . \Pr[(\mathsf{pk},\mathsf{sk}) \leftarrow\operatorname{Gen}(1^n) \wedge\operatorname{Dec}(\mathsf{sk}, \operatorname{Enc}(\mathsf{pk},0)) = 0)] \ge1 - o(1). Pr [( pk , sk ) ← Gen ( 1 n ) ∧ Dec ( sk , Enc ( pk , 0 )) = 0 )] ≥ 1 − o ( 1 ) .
We conclude that for all b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } ,
Pr [ ( p k , s k ) ← Gen ( 1 n ) ∧ Dec ( s k , Enc ( p k , b ) ) = b ) ] ≥ 1 − o ( 1 ) . \Pr[(\mathsf{pk},\mathsf{sk}) \leftarrow\operatorname{Gen}(1^n) \wedge\operatorname{Dec}(\mathsf{sk}, \operatorname{Enc}(\mathsf{pk},b)) = b)] \ge1 - o(1). Pr [( pk , sk ) ← Gen ( 1 n ) ∧ Dec ( sk , Enc ( pk , b )) = b )] ≥ 1 − o ( 1 ) .
Security
The proof of security will follow from standard hybrid arguments by reducing to the hardness of planted clique (Conjecture 1.1 ) and noisy k k k -LIN (Conjecture 4.3 ). To use the latter, we first need to show that the indicator matrix S S S for A A A indeed satisfies the pre-conditions of Conjecture 4.3 . Namely, S S S should be an expanding matrix when S S S is constructed from a graph G G G without a planted clique. We will also show that S S S is a non-compressing matrix when constructed in this manner. We present the proofs below.
Proof of Expansion
Before showing the proof of expansion, we prove the following lemma regarding sparse vectors.
Lemma 5.4. Let c 1 , c 2 > 0 c_1, c_2 > 0 c 1 , c 2 > 0 be any constants. Let n ∈ N n \in\mathbb{N} n ∈ N and Δ = ( log n ) c 2 \Delta= (\log n)^{c_2} Δ = ( log n ) c 2 . Let T T T be a set of n O ( 1 ) n^{O(1)} n O ( 1 ) many uniformly sampled t t t -sparse vectors in F 2 ( log n ) c 1 \mathbb{F}_2^{(\log n)^{c_1}} F 2 ( l o g n ) c 1 , where t = Θ ( log n ) t = \Theta(\log n) t = Θ ( log n ) . Then, for all subsets S ⊂ T S \subset T S ⊂ T of size at most Δ \Delta Δ ,
hw ( ⋁ s ∈ S s ) > c 1 − c 2 − 2 c 1 ⋅ ∑ s ∈ S hw ( s ) \operatorname{hw}\left(\bigvee_{s \in S} s\right) > \frac{c_1-c_2-2}{c_1} \cdot\sum_{s \in S} \operatorname{hw}(s) hw ( s ∈ S ⋁ s ) > c 1 c 1 − c 2 − 2 ⋅ s ∈ S ∑ hw ( s ) with all but o ( 1 ) o(1) o ( 1 ) probability over the choice of the vectors.
Proof. Clearly the lemma holds if c 1 − c 2 − 2 ≤ 0 c_1-c_2-2 \le0 c 1 − c 2 − 2 ≤ 0 . So consider the case that c 1 − c 2 − 2 > 0 c_1-c_2-2 > 0 c 1 − c 2 − 2 > 0 .
We use linearity of expectation to calculate the number of sets of vectors S S S with ∣ S ∣ ≤ Δ |S| \le\Delta ∣ S ∣ ≤ Δ such that
hw ( ⋁ s ∈ S s ) ≤ c 1 − c 2 − 2 c 1 ⋅ ∑ s ∈ S hw ( s ) = c 1 − c 2 − 2 c 1 t ∣ S ∣ . \operatorname{hw}\left(\bigvee_{s \in S} s\right) \le\frac{c_1-c_2-2}{c_1} \cdot\sum_{s \in S} \operatorname{hw}(s) = \frac{c_1-c_2-2}{c_1}t|S|. hw ( s ∈ S ⋁ s ) ≤ c 1 c 1 − c 2 − 2 ⋅ s ∈ S ∑ hw ( s ) = c 1 c 1 − c 2 − 2 t ∣ S ∣.
Let x : = ∣ S ∣ x := |S| x := ∣ S ∣ and the number of sets of size x x x that contradict the lemma be N x N_x N x . We want all non-zero entries of each s ∈ S s \in S s ∈ S to be restricted to a subset of [ ( log n ) c 1 ] [(\log n)^{c_1}] [( log n ) c 1 ] that has size at most c 1 − c 2 − 2 c 1 t x \frac{c_1-c_2-2}{c_1}tx c 1 c 1 − c 2 − 2 t x .
Now, the total number of ways to choose a set of x x x many vectors is ( n O ( 1 ) x ) ≤ n O ( x ) \binom{n^{O(1)}}{x} \le n^{O(x)} ( x n O ( 1 ) ) ≤ n O ( x ) , and the total number of ways to select c 1 − c 2 − 2 c 1 t x \frac{c_1-c_2-2}{c_1}tx c 1 c 1 − c 2 − 2 t x many positions out of a total of ( log n ) c 1 (\log n)^{c_1} ( log n ) c 1 positions is
( ( log n ) c 1 c 1 − c 2 − 2 c 1 t x ) < ( ( log n ) c 1 ) c 1 − c 2 − 2 c 1 t x . \binom{(\log n)^{c_1}}{\frac{c_1-c_2-2}{c_1}tx} < \left((\log n)^{c_1}\right)^{\frac{c_1-c_2-2}{c_1}tx}. ( c 1 c 1 − c 2 − 2 t x ( log n ) c 1 ) < ( ( log n ) c 1 ) c 1 c 1 − c 2 − 2 t x .
The probability that all the non-zero entries for all vectors x ∈ S x \in S x ∈ S lie within a given set of c 1 − c 2 − 2 c 1 t x \frac{c_1-c_2-2}{c_1}t_x c 1 c 1 − c 2 − 2 t x many positions is
( ( c 1 − c 2 − 2 c 1 t x t ) ( ( log n ) c 1 t ) ) x < ( ( c 1 − c 2 − 2 c 1 t x t ) ( log n ) c 1 ) t x < ( t x ( log n ) c 1 ) t x < ( ( log n ) 3 / 2 ( log n ) c 1 ) t x = ( ( log n ) 3 / 2 + c 2 − c 1 ) t x . \left(\frac{\binom{\frac{c_1-c_2-2}{c_1}t_x}{t}}{\binom{(\log n)^{c_1}}{t}}\right)^x
<
\left(\frac{\binom{\frac{c_1-c_2-2}{c_1}t_x}{t}}{(\log n)^{c_1}}\right)^{t_x}
<
\left(\frac{t_x}{(\log n)^{c_1}}\right)^{t_x}
<
\left(\frac{(\log n)^{3/2}}{(\log n)^{c_1}}\right)^{t_x}
=
((\log n)^{3/2+c_2-c_1})^{t_x}. ( t ( l o g n ) c 1 ) ( t c 1 c 1 − c 2 − 2 t x ) x < ( log n ) c 1 ( t c 1 c 1 − c 2 − 2 t x ) t x < ( ( log n ) c 1 t x ) t x < ( ( log n ) c 1 ( log n ) 3/2 ) t x = (( log n ) 3/2 + c 2 − c 1 ) t x .
Putting all of this together, we have:
E [ N x ] ≤ n O ( x ) ⋅ ( ( log n ) c 1 ) c 1 − c 2 − 2 c 1 t x ⋅ ( ( log n ) 3 / 2 + c 2 − c 1 ) t x ≤ 2 O ( x log n ) ⋅ 2 ( c 1 − c 2 − 2 ) t x log log n ⋅ 2 ( 3 / 2 + c 2 − c 1 ) t x log log n ≤ 2 O ( x log n ) ⋅ 2 ( ( c 1 − c 2 − 2 ) + ( 3 / 2 + c 2 − c 1 ) ) t x log log n ≤ 2 O ( x log n ) ⋅ 2 − 1 2 t x log log n ≤ 2 O ( x log n ) ⋅ 2 − ω ( x log n ) ≤ 2 − ω ( x log n ) \begin{aligned}
\mathbb{E}[N_x] &\le n^{O(x)} \cdot((\log n)^{c_1})^{\frac{c_1-c_2-2}{c_1}t_x} \cdot((\log n)^{3/2+c_2-c_1})^{t_x}\\
&\le2^{O(x\log n)} \cdot2^{(c_1-c_2-2)t_x\log\log n} \cdot2^{(3/2+c_2-c_1)t_x\log\log n}\\
&\le2^{O(x\log n)} \cdot2^{((c_1-c_2-2)+(3/2+c_2-c_1))t_x\log\log n}\\
&\le2^{O(x\log n)} \cdot2^{-\frac{1}{2}t_x\log\log n}\\
&\le2^{O(x\log n)} \cdot2^{-\omega(x\log n)}\\
&\le2^{-\omega(x\log n)}
\end{aligned} E [ N x ] ≤ n O ( x ) ⋅ (( log n ) c 1 ) c 1 c 1 − c 2 − 2 t x ⋅ (( log n ) 3/2 + c 2 − c 1 ) t x ≤ 2 O ( x l o g n ) ⋅ 2 ( c 1 − c 2 − 2 ) t x l o g l o g n ⋅ 2 ( 3/2 + c 2 − c 1 ) t x l o g l o g n ≤ 2 O ( x l o g n ) ⋅ 2 (( c 1 − c 2 − 2 ) + ( 3/2 + c 2 − c 1 )) t x l o g l o g n ≤ 2 O ( x l o g n ) ⋅ 2 − 2 1 t x l o g l o g n ≤ 2 O ( x l o g n ) ⋅ 2 − ω ( x l o g n ) ≤ 2 − ω ( x l o g n )
Finally taking a union bound of all x ≤ Δ x \le\Delta x ≤ Δ and applying Markov’s inequality, we get that
Pr [ N : = ∑ x N x ≥ 1 ] ≤ 2 − ω ( log n ) . \Pr\left[N := \sum_x N_x \ge1\right] \le2^{-\omega(\log n)}. Pr [ N := x ∑ N x ≥ 1 ] ≤ 2 − ω ( l o g n ) .
Next, we state a useful lemma about ζ \zeta ζ -cliques and ( ζ − 1 ) (\zeta- 1) ( ζ − 1 ) -cliques, the proof of which is deferred to Section 6. To state the lemma, we begin by defining a notion of “high” and “low” degree that applies to cliques.
Definition 6.6 ((Δ , S \Delta, S Δ , S )-High Degree). A ( ζ − 1 ) (\zeta- 1) ( ζ − 1 ) -clique is said to be ( Δ , S ) (\Delta, S) ( Δ , S ) -high degree if it is contained in at least Δ \Delta Δ many distinct ζ \zeta ζ -cliques of S S S , where S S S is a set of ζ \zeta ζ -cliques.
Lemma 6.7. Let n ˉ ∈ N \bar{n} \in\mathbb{N} n ˉ ∈ N be any parameter, ζ > 1 \zeta> 1 ζ > 1 be any (not necessarily constant) integer, and α , δ ∈ ( 0 , 1 2 ) \alpha, \delta\in(0, \frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) be any constants. Set ℓ = ( log n ˉ ) α \ell= (\log\bar{n})^\alpha ℓ = ( log n ˉ ) α , q = n ˉ − ( δ ℓ ) / 2 q = \bar{n}^{-(\delta\ell)/2} q = n ˉ − ( δ ℓ ) /2 , and Δ = ( log n ˉ ) ζ ( 1 − α ) \Delta= (\log\bar{n})^{\zeta(1-\alpha)} Δ = ( log n ˉ ) ζ ( 1 − α ) . Sample G ← $ G ( n ˉ , 1 2 ) G \overset{\$}{\leftarrow} \mathcal{G}(\bar{n}, \frac{1}{2}) G ← $ G ( n ˉ , 2 1 ) , and sample H ← $ R P q ℓ ( G ) H \overset{\$}{\leftarrow} \mathrm{RP}^{\ell}_q(G) H ← $ RP q ℓ ( G ) . With all but o ( 1 ) o(1) o ( 1 ) probability over the random choice of G G G and randomness of R P q ℓ \mathrm{RP}^{\ell}_q RP q ℓ , the following occurs. For any set S S S of 2 o ( ( log n ˉ ) 2 α ) 2^{o((\log\bar{n})^{2\alpha})} 2 o (( l o g n ˉ ) 2 α ) many ζ \zeta ζ -cliques of H H H , define T ⊂ S T \subset S T ⊂ S as
T = { K ∈ S : K has as a subgraph more than one ( Δ , S ) -high degree ( ζ − 1 ) -clique } . T = \{K \in S : K\text{ has as a subgraph more than one }(\Delta,S)\text{-high degree }(\zeta- 1)\text{-clique}\}. T = { K ∈ S : K has as a subgraph more than one ( Δ , S ) -high degree ( ζ − 1 ) -clique } . Then ∣ T ∣ = o ( 1 ) ⋅ ∣ S ∣ |T| = o(1) \cdot|S| ∣ T ∣ = o ( 1 ) ⋅ ∣ S ∣ .
In other words, the above lemma says that for any set S S S consisting of ζ \zeta ζ -cliques, as long as the size of S S S is not too high, nearly all of the ζ \zeta ζ -cliques in S S S contain at most one high degree ( ζ − 1 ) (\zeta- 1) ( ζ − 1 ) -clique.
Using the above lemma, we can argue that A \mathbf{A} A is a good small-set-expander.
Lemma 5.5. For all constants α , δ ∈ ( 0 , 1 2 ) \alpha, \delta\in(0, \frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) and γ ∈ ( 1 2 , 1 ) \gamma\in(\frac{1}{2}, 1) γ ∈ ( 2 1 , 1 ) , for all large enough λ \lambda λ , the following holds. Set n ˉ = 2 ( log λ ) 1 / ( 1 + α ) \bar{n} = 2^{(\log\lambda)^{1/(1+\alpha)}} n ˉ = 2 ( l o g λ ) 1/ ( 1 + α ) , ℓ = ( log n ˉ ) α \ell= (\log\bar{n})^\alpha ℓ = ( log n ˉ ) α , q = n ˉ − ( δ ℓ ) / 2 q = \bar{n}^{-(\delta\ell)/2} q = n ˉ − ( δ ℓ ) /2 , ζ = ⌈ 1 1 − γ ⌉ + 1 \zeta= \left\lceil\frac{1}{1-\sqrt{\gamma}}\right\rceil+ 1 ζ = ⌈ 1 − γ 1 ⌉ + 1 , and β = ζ ⋅ ( ζ ( 1 − α ) + 2 ) \beta= \zeta\cdot(\zeta(1-\alpha)+2) β = ζ ⋅ ( ζ ( 1 − α ) + 2 ) . Let G ← $ G ( n ˉ , 1 2 ) G \overset{\$}{\leftarrow} \mathcal{G}(\bar{n}, \frac{1}{2}) G ← $ G ( n ˉ , 2 1 ) , H ← $ R P q ℓ ( G ) H \overset{\$}{\leftarrow} \mathrm{RP}^{\ell}_q(G) H ← $ RP q ℓ ( G ) , and A ← Encode ( H , ζ , β ) \mathbf{A} \leftarrow\operatorname{Encode}(H,\zeta,\beta) A ← Encode ( H , ζ , β ) . Then A ∈ F 2 λ × n \mathbf{A} \in\mathcal{F}^{2^{\lambda}\times n} A ∈ F 2 λ × n is a ( γ , Θ ( log n ) , 2 ( log n ) α ) (\gamma,\Theta(\log n),2^{(\log n)^\alpha}) ( γ , Θ ( log n ) , 2 ( l o g n ) α ) -expanding matrix with 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) probability over the random choice of G G G , the randomness of R P q ℓ \mathrm{RP}^{\ell}_q RP q ℓ , and the coins of Encode \operatorname{Encode} Encode .
Proof. First note that, by construction, each row of A A A is exactly k k k -sparse, where k = log m = Θ ( log n ) k=\log m=\Theta(\log n) k = log m = Θ ( log n ) . (m m m and n n n are polynomially related with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) over the random choice of G G G and the randomness of R P p ℓ \mathrm{RP}_{p}^{\ell} RP p ℓ .)
Recall that our small-set-expansion requirement is the following, where t = 2 ( log n ) α t=2^{(\log n)^{\alpha}} t = 2 ( l o g n ) α .
∀ S ⊆ { 1 , … , m } such that ∣ S ∣ ≤ t , we have that hw ( ⋁ i ∈ S S i ) ≥ γ ⋅ k ∣ S ∣ . \forall S\subseteq\{1,\ldots,m\}\text{ such that }|S|\le t,\text{ we have that }\operatorname{hw}\left(\bigvee_{i\in S}S_i\right)\ge\gamma\cdot k|S|. ∀ S ⊆ { 1 , … , m } such that ∣ S ∣ ≤ t , we have that hw ( i ∈ S ⋁ S i ) ≥ γ ⋅ k ∣ S ∣.
Consider any set of indices S S S with ∣ S ∣ ≤ t |S|\le t ∣ S ∣ ≤ t . Define B B B to be the set of all blocks b i , j \mathbf{b}_{i,j} b i , j such that i ∈ S i\in S i ∈ S and I i , j = 1 I_{i,j}=1 I i , j = 1 . We now lower bound hw ( ⋁ i ∈ S S i ) \operatorname{hw}\left(\bigvee_{i\in S}S_i\right) hw ( ⋁ i ∈ S S i ) by analyzing the blocks in B B B .
Fix Δ = ( log n ˉ ) ζ ( 1 − α ) \Delta=(\log\bar{n})^{\zeta(1-\alpha)} Δ = ( log n ˉ ) ζ ( 1 − α ) . Let K ( S ) = { ζ -clique of H with label R i : i ∈ S } K(S)=\{\zeta\text{-clique of }H\text{ with label }R_i:i\in S\} K ( S ) = { ζ -clique of H with label R i : i ∈ S } . Let S B a d ⊂ S S_{\mathrm{Bad}}\subset S S Bad ⊂ S be the set of all i ∈ S i\in S i ∈ S such that the ζ \zeta ζ -clique labeled R i R_i R i contains at least two ( Δ , K ( S ) ) (\Delta,K(S)) ( Δ , K ( S )) -high degree ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -cliques.
Observe that, since n = ∣ V H ∣ O ( 1 ) = n ˉ O ( ℓ ) n=|V_H|^{O(1)}=\bar{n}^{O(\ell)} n = ∣ V H ∣ O ( 1 ) = n ˉ O ( ℓ ) and α ∈ ( 0 , 1 2 ) \alpha\in\left(0,\frac{1}{2}\right) α ∈ ( 0 , 2 1 ) is a constant, we have that log α n = o ( log 2 α n ˉ ) \log^\alpha n=o(\log^{2\alpha}\bar{n}) log α n = o ( log 2 α n ˉ ) . So ∣ K ( S ) ∣ ≤ 2 o ( log 2 α n ˉ ) |K(S)|\le2^{o(\log^{2\alpha}\bar{n})} ∣ K ( S ) ∣ ≤ 2 o ( l o g 2 α n ˉ ) . Therefore by Lemma 6.7,
∣ S B a d ∣ ≤ o ( 1 ) ⋅ ∣ S ∣ . |S_{\mathrm{Bad}}|\le o(1)\cdot|S|. ∣ S Bad ∣ ≤ o ( 1 ) ⋅ ∣ S ∣.
Define B G o o d B_{\mathrm{Good}} B Good to be the set of all blocks b ∈ B \mathbf{b}\in B b ∈ B that are contained in a row S i S_i S i with i ∈ S ∖ S B a d i\in S\setminus S_{\mathrm{Bad}} i ∈ S ∖ S Bad . Since every row S i S_i S i contains exactly ζ \zeta ζ many blocks b i , j \mathbf{b}_{i,j} b i , j with I i , j = 1 I_{i,j}=1 I i , j = 1 :
∣ B G o o d ∣ ≥ ( 1 − o ( 1 ) ) ⋅ ∣ B ∣ . |B_{\mathrm{Good}}|\ge(1-o(1))\cdot|B|. ∣ B Good ∣ ≥ ( 1 − o ( 1 )) ⋅ ∣ B ∣.
Let B G o o d , L o w B_{\mathrm{Good,Low}} B Good , Low be the set of all blocks b i , j ∈ B G o o d \mathbf{b}_{i,j}\in B_{\mathrm{Good}} b i , j ∈ B Good such that C j C_j C j is the label of a ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -clique that is not ( Δ , K ( S ) ) (\Delta,K(S)) ( Δ , K ( S )) -high degree. Since each ζ \zeta ζ -clique with label R i R_i R i for some i ∈ S ∖ S B a d i\in S\setminus S_{\mathrm{Bad}} i ∈ S ∖ S Bad has that all but one of its ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -cliques are not ( Δ , K ( S ) ) (\Delta,K(S)) ( Δ , K ( S )) -high degree,
∣ B G o o d , L o w ∣ ≥ ζ − 1 ζ ⋅ ∣ B G o o d ∣ ≥ ζ − 1 ζ ⋅ ( 1 − o ( 1 ) ) ⋅ ∣ B ∣ . |B_{\mathrm{Good,Low}}|\ge\frac{\zeta-1}{\zeta}\cdot|B_{\mathrm{Good}}|\ge\frac{\zeta-1}{\zeta}\cdot(1-o(1))\cdot|B|. ∣ B Good , Low ∣ ≥ ζ ζ − 1 ⋅ ∣ B Good ∣ ≥ ζ ζ − 1 ⋅ ( 1 − o ( 1 )) ⋅ ∣ B ∣.
Since each block has exactly the same hamming weight, it must be the case that
∑ b ∈ B G o o d , L o w hw ( b ) = ∣ B G o o d , L o w ∣ ∣ B ∣ ⋅ ∑ b ∈ B hw ( b ) . \sum_{\mathbf{b}\in B_{\mathrm{Good,Low}}}\operatorname{hw}(\mathbf{b})=
\frac{|B_{\mathrm{Good,Low}}|}{|B|}\cdot\sum_{\mathbf{b}\in B}\operatorname{hw}(\mathbf{b}). b ∈ B Good , Low ∑ hw ( b ) = ∣ B ∣ ∣ B Good , Low ∣ ⋅ b ∈ B ∑ hw ( b ) .
Furthermore
∑ b ∈ B hw ( b ) = ∑ i ∈ S hw ( A i ) = k ∣ S ∣ \sum_{\mathbf{b}\in B}\operatorname{hw}(\mathbf{b})=\sum_{i\in S}\operatorname{hw}(A_i)=k|S| b ∈ B ∑ hw ( b ) = i ∈ S ∑ hw ( A i ) = k ∣ S ∣
since all of the nonzero entries in each row appear in a block b i , j \mathbf{b}_{i,j} b i , j with I i , j = 1 I_{i,j}=1 I i , j = 1 . Composing these results, we have
∑ b ∈ B G o o d , L o w hw ( b ) ≥ ζ − 1 ζ ⋅ ( 1 − o ( 1 ) ) ⋅ k ∣ S ∣ . \sum_{\mathbf{b}\in B_{\mathrm{Good,Low}}}\operatorname{hw}(\mathbf{b})\ge\frac{\zeta-1}{\zeta}\cdot(1-o(1))\cdot k|S|. b ∈ B Good , Low ∑ hw ( b ) ≥ ζ ζ − 1 ⋅ ( 1 − o ( 1 )) ⋅ k ∣ S ∣.
Let B G o o d , L o w , j B_{\mathrm{Good,Low},j} B Good , Low , j be the set of all b i , j ∈ B G o o d , L o w \mathbf{b}_{i,j}\in B_{\mathrm{Good,Low}} b i , j ∈ B Good , Low with a fixed j j j value. Recall that each block in B G o o d , L o w , j B_{\mathrm{Good,Low},j} B Good , Low , j is a ( log m ) (\log m) ( log m ) -sparse vector in F log β m \mathbb{F}_{\log^\beta m} F l o g β m . Furthermore, since m > n ˉ m>\bar{n} m > n ˉ w.h.p., B G o o d , L o w , j B_{\mathrm{Good,Low},j} B Good , Low , j contains at most Δ = ( log n ˉ ) ζ ( 1 − α ) < ( log m ) ζ ( 1 − α ) \Delta=(\log\bar{n})^{\zeta(1-\alpha)}<(\log m)^{\zeta(1-\alpha)} Δ = ( log n ˉ ) ζ ( 1 − α ) < ( log m ) ζ ( 1 − α ) many vectors selected out of a total of m O ( 1 ) m^{O(1)} m O ( 1 ) many vectors.
(The set of vectors is taken to be the set of all blocks b i , j b_{i,j} b i , j in S S S .) We now apply Lemma 5.4 with c 1 = β = ζ ⋅ ( ζ ( 1 − α ) + 2 ) c_1 = \beta= \zeta\cdot(\zeta(1-\alpha)+2) c 1 = β = ζ ⋅ ( ζ ( 1 − α ) + 2 ) and c 2 = ζ ( 1 − α ) c_2 = \zeta(1-\alpha) c 2 = ζ ( 1 − α ) . For each j j j , we have that
hw ( ⋁ b ∈ B G o o d , L o w , j b ) > ζ ⋅ ( ζ ( 1 − α ) + 2 ) − ζ ( 1 − α ) − 2 ζ ⋅ ( ζ ( 1 − α ) + 2 ) ⋅ ∑ b ∈ B G o o d , L o w , j hw ( b ) = ζ ⋅ ( ζ ( 1 − α ) + 2 ) − 1 ⋅ ( ζ ( 1 − α ) + 2 ) ζ ⋅ ( ζ ( 1 − α ) + 2 ) ⋅ ∑ b ∈ B G o o d , L o w , j hw ( b ) = ( ζ − 1 ) ⋅ ( ζ ( 1 − α ) + 2 ) ζ ⋅ ( ζ ( 1 − α ) + 2 ) ⋅ ∑ b ∈ B G o o d , L o w , j hw ( b ) = ζ − 1 ζ ⋅ ∑ b ∈ B G o o d , L o w , j hw ( b ) \begin{aligned}
\operatorname{hw}\left(\bigvee_{b\in B_{\mathrm{Good,Low},j}} b\right) > \frac{\zeta\cdot(\zeta(1-\alpha)+2)-\zeta(1-\alpha)-2}{\zeta\cdot(\zeta(1-\alpha)+2)}\cdot\sum_{b\in B_{\mathrm{Good,Low},j}}\operatorname{hw}(b) \\
&= \frac{\zeta\cdot(\zeta(1-\alpha)+2)-1\cdot(\zeta(1-\alpha)+2)}{\zeta\cdot(\zeta(1-\alpha)+2)}\cdot\sum_{b\in B_{\mathrm{Good,Low},j}}\operatorname{hw}(b) \\
&= \frac{(\zeta-1)\cdot(\zeta(1-\alpha)+2)}{\zeta\cdot(\zeta(1-\alpha)+2)}\cdot\sum_{b\in B_{\mathrm{Good,Low},j}}\operatorname{hw}(b) \\
&= \frac{\zeta-1}{\zeta}\cdot\sum_{b\in B_{\mathrm{Good,Low},j}}\operatorname{hw}(b)
\end{aligned} hw b ∈ B Good , Low , j ⋁ b > ζ ⋅ ( ζ ( 1 − α ) + 2 ) ζ ⋅ ( ζ ( 1 − α ) + 2 ) − ζ ( 1 − α ) − 2 ⋅ b ∈ B Good , Low , j ∑ hw ( b ) = ζ ⋅ ( ζ ( 1 − α ) + 2 ) ζ ⋅ ( ζ ( 1 − α ) + 2 ) − 1 ⋅ ( ζ ( 1 − α ) + 2 ) ⋅ b ∈ B Good , Low , j ∑ hw ( b ) = ζ ⋅ ( ζ ( 1 − α ) + 2 ) ( ζ − 1 ) ⋅ ( ζ ( 1 − α ) + 2 ) ⋅ b ∈ B Good , Low , j ∑ hw ( b ) = ζ ζ − 1 ⋅ b ∈ B Good , Low , j ∑ hw ( b )
To determine hw ( ⋁ i ∈ S S i ) \operatorname{hw}(\bigvee_{i\in S}S_i) hw ( ⋁ i ∈ S S i ) , we can sum the hamming weights for each section in the final vector. Considering only the blocks in B G o o d , L o w B_{\mathrm{Good,Low}} B Good , Low , we can write this as:
hw ( ⋁ i ∈ S S i ) ≥ ∑ j ( hw ( ⋁ b ∈ B G o o d , L o w , j b ) ) \operatorname{hw}\left(\bigvee_{i\in S}S_i\right)\geq\sum_j\left(\operatorname{hw}\left(\bigvee_{b\in B_{\mathrm{Good,Low},j}}b\right)\right) hw ( i ∈ S ⋁ S i ) ≥ j ∑ hw b ∈ B Good , Low , j ⋁ b
Now composing all of our results and using that ζ = ⌈ 1 1 − γ ⌉ + 1 \zeta=\left\lceil\frac{1}{1-\sqrt{\gamma}}\right\rceil+1 ζ = ⌈ 1 − γ 1 ⌉ + 1 :
∑ j ( hw ( ⋁ b ∈ B G o o d , L o w , j b ) ) > ∑ j ( ζ − 1 ζ ⋅ ∑ b ∈ B G o o d , L o w , j hw ( b ) ) = ζ − 1 ζ ⋅ ∑ b ∈ B G o o d , L o w hw ( b ) ≥ ζ − 1 ζ ⋅ ζ − 1 ζ ⋅ ( 1 − o ( 1 ) ) ⋅ k ∣ S ∣ = ( ⌈ 1 1 − γ ⌉ ⌈ 1 1 − γ ⌉ + 1 ) 2 ⋅ ( 1 − o ( 1 ) ) ⋅ k ∣ S ∣ > ( 1 1 − γ − 1 1 1 − γ ) 2 ⋅ k ∣ S ∣ = ( 1 − ( 1 − γ ) 1 ) 2 ⋅ k ∣ S ∣ = γ ⋅ k ∣ S ∣ . \begin{aligned}
\sum_j\left(\operatorname{hw}\left(\bigvee_{b\in B_{\mathrm{Good,Low},j}}b\right)\right)>\sum_j\left(\frac{\zeta-1}{\zeta}\cdot\sum_{b\in B_{\mathrm{Good,Low},j}}\operatorname{hw}(b)\right) \\
&=\frac{\zeta-1}{\zeta}\cdot\sum_{b\in B_{\mathrm{Good,Low}}}\operatorname{hw}(b) \\
&\geq\frac{\zeta-1}{\zeta}\cdot\frac{\zeta-1}{\zeta}\cdot(1-o(1))\cdot k|S| \\
&=\left(\frac{\left\lceil\frac{1}{1-\sqrt{\gamma}}\right\rceil}{\left\lceil\frac{1}{1-\sqrt{\gamma}}\right\rceil+1}\right)^2\cdot(1-o(1))\cdot k|S| \\
&>\left(\frac{\frac{1}{1-\sqrt{\gamma}}-1}{\frac{1}{1-\sqrt{\gamma}}}\right)^2\cdot k|S| \\
&=\left(\frac{1-(1-\sqrt{\gamma})}{1}\right)^2\cdot k|S| \\
&=\gamma\cdot k|S|.
\end{aligned} j ∑ hw b ∈ B Good , Low , j ⋁ b > j ∑ ζ ζ − 1 ⋅ b ∈ B Good , Low , j ∑ hw ( b ) = ζ ζ − 1 ⋅ b ∈ B Good , Low ∑ hw ( b ) ≥ ζ ζ − 1 ⋅ ζ ζ − 1 ⋅ ( 1 − o ( 1 )) ⋅ k ∣ S ∣ = ⌈ 1 − γ 1 ⌉ + 1 ⌈ 1 − γ 1 ⌉ 2 ⋅ ( 1 − o ( 1 )) ⋅ k ∣ S ∣ > ( 1 − γ 1 1 − γ 1 − 1 ) 2 ⋅ k ∣ S ∣ = ( 1 1 − ( 1 − γ ) ) 2 ⋅ k ∣ S ∣ = γ ⋅ k ∣ S ∣.
Thus, we achieve the desired lower bound with all but o ( 1 ) o(1) o ( 1 ) probability.
Proof of Non-Compression
As stated in § 4 , S S S will also be a ( γ , Θ ( log n ) ) (\gamma,\Theta(\log n)) ( γ , Θ ( log n )) -non-compressing matrix with high probability. We begin our proof by stating the Kruskal-Katona theorem [59 , 55 ] . At a high level, this relates the number unique sets of size ζ − 1 \zeta-1 ζ − 1 contained in a collection of sets, each of which has size ζ \zeta ζ , for arbitrary values of ζ \zeta ζ .
Lemma 5.6 (Simplified version of the Kruskal-Katona Theorem [59 , 55 ] ). Consider any set system T \mathcal{T} T where every T ∈ T T \in\mathcal{T} T ∈ T has cardinality ζ \zeta ζ , for any constant integer ζ > 1 \zeta> 1 ζ > 1 . Define
Q = { C : ∣ C ∣ = ( ζ − 1 ) ∧ ( ∃ T ∈ T such that C ⊂ T ) } . Q = \{C : |C| = (\zeta- 1) \wedge(\exists T \in\mathcal{T}\text{ such that } C \subset T)\}. Q = { C : ∣ C ∣ = ( ζ − 1 ) ∧ ( ∃ T ∈ T such that C ⊂ T )} . Then ∣ Q ∣ ≥ Ω ( ∣ T ∣ ( ζ − 1 ) / ζ ) |Q| \ge\Omega(|\mathcal{T}|^{(\zeta-1)/\zeta}) ∣ Q ∣ ≥ Ω ( ∣ T ∣ ( ζ − 1 ) / ζ ) .
Lemma 5.7. For all constants α , δ ∈ ( 0 , 1 2 ) \alpha,\delta\in(0,\frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) and γ ∈ ( 1 2 , 1 ) \gamma\in(\frac{1}{2},1) γ ∈ ( 2 1 , 1 ) and β > 0 \beta> 0 β > 0 , for all large enough λ \lambda λ , the following holds. Let n ˉ = 2 ( log λ ) 1 / ( 1 + α ) \bar{n} = 2^{(\log\lambda)^{1/(1+\alpha)}} n ˉ = 2 ( l o g λ ) 1/ ( 1 + α ) , k ˉ = n ˉ δ \bar{k} = \bar{n}^{\delta} k ˉ = n ˉ δ , ℓ = ( log n ˉ ) α \ell= (\log\bar{n})^{\alpha} ℓ = ( log n ˉ ) α , q = n ˉ − ( δ ℓ ) / 2 q = \bar{n}^{-(\delta\ell)/2} q = n ˉ − ( δ ℓ ) /2 , ζ = ⌈ 1 1 − γ ⌉ + 1 \zeta= \left\lceil\frac{1}{1-\sqrt{\gamma}}\right\rceil+ 1 ζ = ⌈ 1 − γ 1 ⌉ + 1 , and ρ = 2 + β ζ \rho= 2 + \beta\zeta ρ = 2 + β ζ .
Let G ← $ G ( n ˉ , 1 2 ) G \overset{\$}{\leftarrow} G(\bar{n}, \frac{1}{2}) G ← $ G ( n ˉ , 2 1 ) , H ← $ RP q ℓ ( G ) H \overset{\$}{\leftarrow} \operatorname{RP}_{q}^{\ell}(G) H ← $ RP q ℓ ( G ) , and S ← Encode ( H , ζ , β ) S \leftarrow\operatorname{Encode}(H,\zeta,\beta) S ← Encode ( H , ζ , β ) . Then S ∈ F 2 m × n S \in\mathbb{F}_{2}^{m \times n} S ∈ F 2 m × n is a ( γ , Θ ( log n ) ) (\gamma,\Theta(\log n)) ( γ , Θ ( log n )) -non-compressing matrix with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) over the randomness of Gen \operatorname{Gen} Gen .
Proof. As argued in Lemma 5.5 , each row of S S S is exactly k k k -sparse, where k = Θ ( log n ) k = \Theta(\log n) k = Θ ( log n ) with 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) probability.
Consider any set system K = { X i ( ζ ) : i ∈ P } \mathcal{K} = \{X_i^{(\zeta)} : i \in P\} K = { X i ( ζ ) : i ∈ P } , where P ⊆ { 1 , … , m } P \subseteq\{1,\ldots,m\} P ⊆ { 1 , … , m } and each X i ( ζ ) X_i^{(\zeta)} X i ( ζ ) is the set of vertices in H H H for the ζ \zeta ζ -clique of H H H with label R i R_i R i . Define
L = { L : ∣ L ∣ = ( ζ − 1 ) ∧ ( ∃ X ∈ K such that L ⊂ X ) } . \mathcal{L} = \{L : |L| = (\zeta- 1) \wedge(\exists X \in\mathcal{K}\text{ such that } L \subset X)\}. L = { L : ∣ L ∣ = ( ζ − 1 ) ∧ ( ∃ X ∈ K such that L ⊂ X )} .
In other words, L \mathcal{L} L is the set of all ( ζ − 1 ) (\zeta- 1) ( ζ − 1 ) -cliques contained in some ζ \zeta ζ -clique of K \mathcal{K} K . Since γ ∈ ( 1 2 , 1 ) \gamma\in(\frac{1}{2},1) γ ∈ ( 2 1 , 1 ) is a constant and ζ = ⌈ 1 1 − γ ⌉ + 1 \zeta= \left\lceil\frac{1}{1-\sqrt{\gamma}}\right\rceil+ 1 ζ = ⌈ 1 − γ 1 ⌉ + 1 , we have that ζ > 4 \zeta> 4 ζ > 4 . Therefore by Lemma 5.6 , we have that ∣ L ∣ ≥ Ω ( ∣ K ∣ ( ζ − 1 ) / ζ ) |\mathcal{L}| \ge\Omega(|\mathcal{K}|^{(\zeta-1)/\zeta}) ∣ L ∣ ≥ Ω ( ∣ K ∣ ( ζ − 1 ) / ζ ) . Expanding this expression, we get:
∣ L ∣ ≥ Ω ( ∣ K ∣ ⌈ 1 1 − γ ⌉ / ( ⌈ 1 1 − γ ⌉ + 1 ) ) > Ω ( ∣ K ∣ ( ⌈ 1 1 − γ ⌉ − 1 ) / ⌈ 1 1 − γ ⌉ ) = Ω ( ∣ K ∣ 1 − 1 / ⌈ 1 1 − γ ⌉ ) ≥ Ω ( ∣ K ∣ 1 − 1 / ( 1 − γ ) ) = Ω ( ∣ K ∣ γ ) . \begin{aligned}
|\mathcal{L}| &\ge\Omega\left(|\mathcal{K}|^{\left\lceil\frac{1}{1-\sqrt{\gamma}}\right\rceil/\left(\left\lceil\frac{1}{1-\sqrt{\gamma}}\right\rceil+1\right)}\right)\\
&>\Omega\left(|\mathcal{K}|^{\left(\left\lceil\frac{1}{1-\sqrt{\gamma}}\right\rceil-1\right)/\left\lceil\frac{1}{1-\sqrt{\gamma}}\right\rceil}\right)\\
&=\Omega\left(|\mathcal{K}|^{1-1/\left\lceil\frac{1}{1-\sqrt{\gamma}}\right\rceil}\right)\\
&\ge\Omega\left(|\mathcal{K}|^{1-1/(1-\sqrt{\gamma})}\right)\\
&=\Omega\left(|\mathcal{K}|^{\sqrt{\gamma}}\right).
\end{aligned} ∣ L ∣ ≥ Ω ( ∣ K ∣ ⌈ 1 − γ 1 ⌉ / ( ⌈ 1 − γ 1 ⌉ + 1 ) ) > Ω ( ∣ K ∣ ( ⌈ 1 − γ 1 ⌉ − 1 ) / ⌈ 1 − γ 1 ⌉ ) = Ω ( ∣ K ∣ 1 − 1/ ⌈ 1 − γ 1 ⌉ ) ≥ Ω ( ∣ K ∣ 1 − 1/ ( 1 − γ ) ) = Ω ( ∣ K ∣ γ ) .
Now consider the set of row vectors S \mathcal{S} S for S S S . Any subset T ⊂ S \mathcal{T} \subset\mathcal{S} T ⊂ S corresponds to exactly ∣ T ∣ |\mathcal{T}| ∣ T ∣ many distinct ζ \zeta ζ -cliques in H H H , and (by the above) at least Ω ( ∣ T ∣ γ ) \Omega(|\mathcal{T}|^{\sqrt{\gamma}}) Ω ( ∣ T ∣ γ ) many ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -cliques of H H H . By construction, each of these ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -cliques corresponds to at least one distinct “1” entry in the bitwise-OR of all vectors ⋁ v ∈ T v \bigvee_{\mathbf{v}\in\mathcal{T}}\mathbf{v} ⋁ v ∈ T v . Therefore we have
hw ( ⋁ v ∈ T v ) ≥ Ω ( ∣ T ∣ γ ) . \operatorname{hw}\left(\bigvee_{\mathbf{v}\in\mathcal{T}}\mathbf{v}\right)\ge\Omega(|\mathcal{T}|^{\sqrt{\gamma}}). hw ( v ∈ T ⋁ v ) ≥ Ω ( ∣ T ∣ γ ) .
Since each row vector is exactly k k k -sparse, we also have that any subset T ⊂ S \mathcal{T} \subset\mathcal{S} T ⊂ S with ∣ T ∣ ≤ k |\mathcal{T}| \le k ∣ T ∣ ≤ k satisfies
hw ( ⋁ v ∈ T v ) ≥ k ≥ ∣ T ∣ . \operatorname{hw}\left(\bigvee_{\mathbf{v}\in\mathcal{T}}\mathbf{v}\right)\ge k\ge|\mathcal{T}|. hw ( v ∈ T ⋁ v ) ≥ k ≥ ∣ T ∣.
Combining these two observations and noting that k k k is superconstant implies that
hw ( ⋁ v ∈ T v ) ≥ ∣ T ∣ γ . \operatorname{hw}\left(\bigvee_{\mathbf{v}\in\mathcal{T}}\mathbf{v}\right)\ge|\mathcal{T}|^{\gamma}. hw ( v ∈ T ⋁ v ) ≥ ∣ T ∣ γ .
holds for sufficiently large λ \lambda λ . ∎
Semantic Security
We first show that the scheme is a weak PKE.
Lemma 5.8 (Weak Security). Assume that Conjecture 1.1 holds for some constants α , δ ∈ ( 0 , 1 2 ) \alpha,\delta\in\left(0,\frac{1}{2}\right) α , δ ∈ ( 0 , 2 1 ) , and assume that Conjecture 4.3 holds for some constant γ ∈ ( 1 2 , 1 ) \gamma\in\left(\frac{1}{2},1\right) γ ∈ ( 2 1 , 1 ) . Then for all large enough λ \lambda λ , the following is true. Set n ˉ = 2 ( log λ ) 1 / ( 1 + α ) \bar{n}=2^{(\log\lambda)^{1/(1+\alpha)}} n ˉ = 2 ( l o g λ ) 1/ ( 1 + α ) , k ˉ = n ˉ α \bar{k}=\bar{n}^{\alpha} k ˉ = n ˉ α , ℓ = ( log n ˉ ) α \ell=(\log\bar{n})^{\alpha} ℓ = ( log n ˉ ) α , q = n ˉ − ( δ ℓ ) / 2 q=\bar{n}^{-(\delta\ell)/2} q = n ˉ − ( δ ℓ ) /2 , ζ = ⌈ 1 1 − γ ⌉ + 1 \zeta=\left\lceil\frac{1}{1-\sqrt{\gamma}}\right\rceil+1 ζ = ⌈ 1 − γ 1 ⌉ + 1 , β = ζ ⋅ ( ζ ( 1 − α ) + 2 ) \beta=\zeta\cdot(\zeta(1-\alpha)+2) β = ζ ⋅ ( ζ ( 1 − α ) + 2 ) , and ρ = 2 + β ζ \rho=2+\beta\zeta ρ = 2 + β ζ . For all poly ( λ ) \operatorname{poly}(\lambda) poly ( λ ) -size algorithms A A A ,
∣ Pr [ ( p k , s k ) ← Gen ( 1 λ ) ; A ( p k , Enc ( p k , 0 ) ) = 1 ] − Pr [ ( p k , s k ) ← Gen ( 1 λ ) ; A ( p k , Enc ( p k , 1 ) ) = 1 ] ∣ ≤ 12 13 . \left|\Pr\left[(\mathit{pk},\mathit{sk})\gets\operatorname{Gen}(1^\lambda);A(\mathit{pk},\operatorname{Enc}(\mathit{pk},0))=1\right]-\Pr\left[(\mathit{pk},\mathit{sk})\gets\operatorname{Gen}(1^\lambda);A(\mathit{pk},\operatorname{Enc}(\mathit{pk},1))=1\right]\right|\leq\frac{12}{13}. Pr [ ( pk , sk ) ← Gen ( 1 λ ) ; A ( pk , Enc ( pk , 0 )) = 1 ] − Pr [ ( pk , sk ) ← Gen ( 1 λ ) ; A ( pk , Enc ( pk , 1 )) = 1 ] ≤ 13 12 . where the probability is taken over the coins of Encode \operatorname{Encode} Encode , Gen \operatorname{Gen} Gen , and Enc \operatorname{Enc} Enc .
Proof. We will use standard hybrid arguments.
Hybrid H 0 ( 1 λ ) \mathcal{H}_0(1^\lambda) H 0 ( 1 λ ) :
G ← $ G ( n ˉ , 1 2 , k ˉ ) G\mathrel{\overset{\$}{\leftarrow}}\mathcal{G}\left(\bar{n},\frac{1}{2},\bar{k}\right) G ← $ G ( n ˉ , 2 1 , k ˉ ) .
H ← $ RP p ℓ ( G ) H\mathrel{\overset{\$}{\leftarrow}}\operatorname{RP}_{p}^{\ell}(G) H ← $ RP p ℓ ( G ) .
S ← Encode ( H , ζ , β ) \mathbf{S}\leftarrow\operatorname{Encode}(H,\zeta,\beta) S ← Encode ( H , ζ , β ) . Let S \mathbf{S} S have m m m rows and n n n columns.
Let A ∈ F p m × n \mathbf{A}\in\mathbb{F}_{p}^{m\times n} A ∈ F p m × n be the matrix where we replace each nonzero entry in S \mathbf{S} S with a random element in F p ∗ \mathbb{F}_{p}^{*} F p ∗ .
p k : = A \mathit{pk}:=\mathbf{A} pk := A .
c t ← Enc ( p k , 0 ) ct\leftarrow\operatorname{Enc}(\mathit{pk},0) c t ← Enc ( pk , 0 ) where
c t ← A s + e . ct\leftarrow\mathbf{A}s+e. c t ← A s + e .
Here s ← $ F p n s\mathrel{\overset{\$}{\leftarrow}}\mathbb{F}_{p}^{n} s ← $ F p n and we sample e e e as:
e i = { Random element of F p ∗ , with probability η = ( log n ) − ζ , 0 , otherwise. e_i=
\begin{cases}
\text{Random element of }\mathbb{F}_{p}^{*}, & \text{with probability }\eta=(\log n)^{-\zeta},\\
0, & \text{otherwise.}
\end{cases} e i = { Random element of F p ∗ , 0 , with probability η = ( log n ) − ζ , otherwise.
Output ( p k , c t ) (\mathit{pk},ct) ( pk , c t ) .
Hybrid H 0 , $ ( 1 λ ) \mathcal{H}_{0,\$}(1^\lambda) H 0 , $ ( 1 λ ) :
G ← $ G ( n ˉ , 1 2 ) G\mathrel{\overset{\$}{\leftarrow}}\mathcal{G}\left(\bar{n},\frac{1}{2}\right) G ← $ G ( n ˉ , 2 1 ) .
H ← $ RP p ℓ ( G ) H\mathrel{\overset{\$}{\leftarrow}}\operatorname{RP}_{p}^{\ell}(G) H ← $ RP p ℓ ( G ) .
S ← Encode ( H , ζ , β ) \mathbf{S}\leftarrow\operatorname{Encode}(H,\zeta,\beta) S ← Encode ( H , ζ , β ) . Let S \mathbf{S} S have m m m rows and n n n columns.
Let A ∈ F p m × n \mathbf{A}\in\mathbb{F}_{p}^{m\times n} A ∈ F p m × n be the matrix where we replace each nonzero entry in S \mathbf{S} S with a random element in F p ∗ \mathbb{F}_{p}^{*} F p ∗ .
p k : = A \mathsf{pk} := A pk := A .
c t ← Enc ( p k , 0 ) \mathsf{ct} \leftarrow\operatorname{Enc}(\mathsf{pk},0) ct ← Enc ( pk , 0 ) where
c t ← A s + e . \mathsf{ct} \leftarrow As + e. ct ← A s + e .
Here s ← $ F p n s \xleftarrow{\$} \mathbb{F}_p^n s $ F p n and we sample e e e as:
e i = { Random element of F p ∗ , with probability η = ( log n ) − ρ , 0 , otherwise. e_i =
\begin{cases}
\text{Random element of }\mathbb{F}_p^*, & \text{with probability }\eta= (\log n)^{-\rho},\\
0, & \text{otherwise.}
\end{cases} e i = { Random element of F p ∗ , 0 , with probability η = ( log n ) − ρ , otherwise.
Output ( p k , c t ) (\mathsf{pk},\mathsf{ct}) ( pk , ct ) .
Hybrid H 1 , $ ( 1 λ ) \mathcal{H}_{1,\$}(1^\lambda) H 1 , $ ( 1 λ ) :
G ← $ G ( n ˉ , 1 2 ) G \xleftarrow{\$} \mathcal{G}(\bar{n},\frac{1}{2}) G $ G ( n ˉ , 2 1 ) .
H ← $ RP p ℓ ( G ) H \xleftarrow{\$} \operatorname{RP}^{\ell}_p(G) H $ RP p ℓ ( G ) .
S ← Encode ( H , ζ , β ) S \leftarrow\operatorname{Encode}(H,\zeta,\beta) S ← Encode ( H , ζ , β ) . Let S S S have m m m rows and n n n columns.
Let A ∈ F p m × n A \in\mathbb{F}_p^{m \times n} A ∈ F p m × n be the matrix where we replace each nonzero entry in S S S with a random element in F p ∗ \mathbb{F}_p^* F p ∗ .
p k : = A \mathsf{pk} := A pk := A .
c t ← Enc ( p k , 1 ) \mathsf{ct} \leftarrow\operatorname{Enc}(\mathsf{pk},1) ct ← Enc ( pk , 1 ) where
c t ← b \mathsf{ct} \leftarrow b ct ← b
where b ← $ F p m b \xleftarrow{\$} \mathbb{F}_p^m b $ F p m .
Output ( p k , c t ) (\mathsf{pk},\mathsf{ct}) ( pk , ct ) .
Hybrid H 1 ( 1 λ ) \mathcal{H}_{1}(1^\lambda) H 1 ( 1 λ ) :
G ← $ G ( n ˉ , 1 2 , k ˉ ) G \xleftarrow{\$} \mathcal{G}(\bar{n},\frac{1}{2},\bar{k}) G $ G ( n ˉ , 2 1 , k ˉ ) .
H ← $ RP p ℓ ( G ) H \xleftarrow{\$} \operatorname{RP}^{\ell}_p(G) H $ RP p ℓ ( G ) .
S ← Encode ( H , ζ , β ) S \leftarrow\operatorname{Encode}(H,\zeta,\beta) S ← Encode ( H , ζ , β ) . Let S S S have m m m rows and n n n columns.
Let A ∈ F p m × n A \in\mathbb{F}_p^{m \times n} A ∈ F p m × n be the matrix where we replace each nonzero entry in S S S with a random element in F p ∗ \mathbb{F}_p^* F p ∗ .
p k : = A \mathsf{pk} := A pk := A .
c t ← Enc ( p k , 1 ) \mathsf{ct} \leftarrow\operatorname{Enc}(\mathsf{pk},1) ct ← Enc ( pk , 1 ) where
c t ← b \mathsf{ct} \leftarrow b ct ← b
where b ← $ F p m b \xleftarrow{\$} \mathbb{F}_p^m b $ F p m .
Output (pk, ct).
Before analyzing the hybrids, note that λ = n ˉ Θ ( ℓ ) \lambda= \bar{n}^{\Theta(\ell)} λ = n ˉ Θ ( ℓ ) and λ = n Θ ( 1 ) \lambda= n^{\Theta(1)} λ = n Θ ( 1 ) with very high probability.
Claim 5.9 (H 0 ≈ 1 3 H 0 , $ \mathcal{H}_0 \approx_{\frac{1}{3}} \mathcal{H}_{0,\$} H 0 ≈ 3 1 H 0 , $ ). Assume that Conjecture 1.1 holds for some constants α , δ ∈ ( 0 , 1 2 ) \alpha, \delta\in(0, \frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) . For all sufficiently large λ \lambda λ , and for all constant γ ∈ ( 1 2 , 1 ) \gamma\in(\frac{1}{2},1) γ ∈ ( 2 1 , 1 ) , the following is true. Set the parameters as in the lemma statement. For all poly ( λ ) \operatorname{poly}(\lambda) poly ( λ ) -size algorithms A \mathcal{A} A ,
∣ Pr [ A ( 1 λ , H 0 ( 1 λ ) ) = 1 ] − Pr [ A ( 1 λ , H 0 , $ ( 1 λ ) ) = 1 ] ∣ ≤ 1 3 . \left|\Pr\left[\mathcal{A}(1^\lambda,\mathcal{H}_0(1^\lambda))=1\right]-\Pr\left[\mathcal{A}(1^\lambda,\mathcal{H}_{0,\$}(1^\lambda))=1\right]\right|\leq\frac{1}{3}. Pr [ A ( 1 λ , H 0 ( 1 λ )) = 1 ] − Pr [ A ( 1 λ , H 0 , $ ( 1 λ )) = 1 ] ≤ 3 1 . Proof. The only difference between H 0 \mathcal{H}_0 H 0 and H 0 , $ \mathcal{H}_{0,\$} H 0 , $ is the presence or absence of a planted clique. Therefore, a poly ( λ ) \operatorname{poly}(\lambda) poly ( λ ) -size algorithm A \mathcal{A} A for differentiating between the two hybrids implies a poly ( λ ) \operatorname{poly}(\lambda) poly ( λ ) -size algorithm B \mathcal{B} B for the planted clique problem.
Specifically, B \mathcal{B} B uses its input graph G ∗ G^* G ∗ in place of graph G G G from Step 1, then follows steps 2 through 7 (which are the same in both hybrids and can be completed in poly ( λ ) \operatorname{poly}(\lambda) poly ( λ ) time), and finally gives the result as input to A \mathcal{A} A . The output from A \mathcal{A} A is used as the output for B \mathcal{B} B . Clearly by our choice of parameters, the distinguishing advantage of B \mathcal{B} B is identical to that of A \mathcal{A} A .
Claim 5.10 (H 0 , $ ≈ 1 4 + o ( 1 ) H 1 , $ \mathcal{H}_{0,\$} \approx_{\frac{1}{4}+o(1)} \mathcal{H}_{1,\$} H 0 , $ ≈ 4 1 + o ( 1 ) H 1 , $ ). Assume that Conjecture 4.3 holds for some constant γ ∈ ( 1 2 , 1 ) \gamma\in(\frac{1}{2},1) γ ∈ ( 2 1 , 1 ) . For all sufficiently large λ \lambda λ , and for all constants α , δ ∈ ( 0 , 1 2 ) \alpha,\delta\in(0,\frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) , the following is true. Set the parameters as in the lemma statement. For all poly ( λ ) \operatorname{poly}(\lambda) poly ( λ ) -size algorithms A \mathcal{A} A ,
∣ Pr [ A ( 1 λ , H 0 , $ ( 1 λ ) ) = 1 ] − Pr [ A ( 1 λ , H 1 , $ ( 1 λ ) ) = 1 ] ∣ ≤ 1 4 + o ( 1 ) . \left|\Pr\left[\mathcal{A}(1^\lambda,\mathcal{H}_{0,\$}(1^\lambda))=1\right]-\Pr\left[\mathcal{A}(1^\lambda,\mathcal{H}_{1,\$}(1^\lambda))=1\right]\right|\leq\frac{1}{4}+o(1). Pr [ A ( 1 λ , H 0 , $ ( 1 λ )) = 1 ] − Pr [ A ( 1 λ , H 1 , $ ( 1 λ )) = 1 ] ≤ 4 1 + o ( 1 ) . Proof. We have already proved that when we start with a graph G ← $ G ( n ˉ , 1 2 ) G\mathrel{\overset{\$}{\leftarrow}}\mathcal{G}(\bar{n},\frac{1}{2}) G ← $ G ( n ˉ , 2 1 ) , then the matrix A \mathbf{A} A generated as per our encoding procedure above satisfies the preconditions of Conjecture 4.3 , namely Lemma 5.5 , with 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) probability. Assuming this event occurs, it is easy to see that any adversary that can distinguish between Hybrids H 0 , $ \mathcal{H}_{0,\$} H 0 , $ and H 1 , $ \mathcal{H}_{1,\$} H 1 , $ with advantage greater than 1 4 \frac{1}{4} 4 1 can be transformed into one that can distinguish between ( A , A s + e ) (\mathbf{A},\mathbf{A}\mathbf{s}+\mathbf{e}) ( A , As + e ) and ( A , s ) (\mathbf{A},\mathbf{s}) ( A , s ) with advantage better than 1 4 \frac{1}{4} 4 1 . This will contradict Conjecture 4.3 .
Claim 5.11 (H 1 , $ ≈ 1 3 H 1 \mathcal{H}_{1,\$} \approx_{\frac{1}{3}} \mathcal{H}_1 H 1 , $ ≈ 3 1 H 1 ). Assume that Conjecture 1.1 holds for some constants α , δ ∈ ( 0 , 1 2 ) \alpha,\delta\in(0,\frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) . For all sufficiently large λ \lambda λ , and for all constant γ ∈ ( 1 2 , 1 ) \gamma\in(\frac{1}{2},1) γ ∈ ( 2 1 , 1 ) , the following is true. Set the parameters as in the lemma statement. For all poly ( λ ) \operatorname{poly}(\lambda) poly ( λ ) -size algorithms A \mathcal{A} A ,
∣ Pr [ A ( 1 λ , H 1 , $ ( 1 λ ) ) = 1 ] − Pr [ A ( 1 λ , H 1 ( 1 λ ) ) = 1 ] ∣ ≤ 1 3 . \left|\Pr\left[\mathcal{A}(1^\lambda,\mathcal{H}_{1,\$}(1^\lambda))=1\right]-\Pr\left[\mathcal{A}(1^\lambda,\mathcal{H}_{1}(1^\lambda))=1\right]\right|\leq\frac{1}{3}. Pr [ A ( 1 λ , H 1 , $ ( 1 λ )) = 1 ] − Pr [ A ( 1 λ , H 1 ( 1 λ )) = 1 ] ≤ 3 1 . Proof. This follows identically from the proof of Claim 5.9 .
Combining the above three claims, and accounting for the fact that λ = n ˉ Θ ( ℓ ) \lambda= \bar{n}^{\Theta(\ell)} λ = n ˉ Θ ( ℓ ) and λ = n Θ ( 1 ) \lambda= n^{\Theta(1)} λ = n Θ ( 1 ) with very high probability, we get
∣ Pr [ ( p k , s k ) ← Gen ( 1 λ ) ; A ( p k , Enc ( p k , 0 ) ) = 1 ] − Pr [ ( p k , s k ) ← Gen ( 1 λ ) ; A ( p k , Enc ( p k , 1 ) ) = 1 ] ∣ ≤ 11 12 + o ( 1 ) < 12 13 . \left|\Pr\left[(\mathsf{pk},\mathsf{sk})\leftarrow\operatorname{Gen}(1^\lambda);\mathcal{A}(\mathsf{pk},\operatorname{Enc}(\mathsf{pk},0))=1\right]-\Pr\left[(\mathsf{pk},\mathsf{sk})\leftarrow\operatorname{Gen}(1^\lambda);\mathcal{A}(\mathsf{pk},\operatorname{Enc}(\mathsf{pk},1))=1\right]\right|\leq\frac{11}{12}+o(1)<\frac{12}{13}. Pr [ ( pk , sk ) ← Gen ( 1 λ ) ; A ( pk , Enc ( pk , 0 )) = 1 ] − Pr [ ( pk , sk ) ← Gen ( 1 λ ) ; A ( pk , Enc ( pk , 1 )) = 1 ] ≤ 12 11 + o ( 1 ) < 13 12 .
We are now ready to prove our main theorem.
Theorem 5.12. Assuming Conjecture 1.1 and Conjecture 4.3 both hold, there exists a semantically secure public key encryption scheme.
Proof. Clearly o ( 1 ) < 1 − 12 / 13 2 o(1) < \frac{1-\sqrt{12/13}}{2} o ( 1 ) < 2 1 − 12/13 . Thus, by Lemma 5.8 , the encryption scheme constructed above is an ( o ( 1 ) , 12 13 ) (o(1), \frac{12}{13}) ( o ( 1 ) , 13 12 ) weak PKE. The theorem then follows from Lemma 3.4.
Useful Properties of Random Graphs
In this section, we will prove certain properties of random graphs that will eventually be helpful towards proving Lemma 6.7.
Throughout, we will consider G : = ( V G , E G ) ← $ G ( n , 1 2 ) G := (V_G, E_G) \overset{\$}{\leftarrow} \mathcal{G}(n, \frac{1}{2}) G := ( V G , E G ) ← $ G ( n , 2 1 ) and H : = ( V H , E H ) ← $ RP q ℓ ( G ) H := (V_H, E_H) \overset{\$}{\leftarrow} \operatorname{RP}^{\ell}_{q}(G) H := ( V H , E H ) ← $ RP q ℓ ( G ) . Let n ˉ : = ∣ V G ∣ \bar{n} := |V_G| n ˉ := ∣ V G ∣ , q : = n ˉ − ( δ ℓ ) / 2 q := \bar{n}^{-(\delta\ell)/2} q := n ˉ − ( δ ℓ ) /2 , and ℓ : = ( log n ˉ ) α \ell:= (\log\bar{n})^{\alpha} ℓ := ( log n ˉ ) α , for any positive constants α , δ ∈ ( 0 , 1 2 ) \alpha, \delta\in(0, \frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) . Recall that we can interpret every node v ∈ V H v \in V_H v ∈ V H as corresponding to a set U v U_v U v of ℓ \ell ℓ many nodes in G G G , and interpret any edge e ∈ E H e \in E_H e ∈ E H connecting nodes ( v , w ) ∈ V H (v,w) \in V_H ( v , w ) ∈ V H as corresponding to a set of edges W e = K ( U v ∪ U w ) W_e = K(U_v \cup U_w) W e = K ( U v ∪ U w ) . Here K ( X ) K(X) K ( X ) denotes the clique induces by vertices in the set X X X .
Definition 6.1 (Vertex and Edge Mappings). For a subset of vertices S ⊆ V H S \subseteq V_H S ⊆ V H , define
G V ( S ) : = ⋃ v ∈ S U v , G^V(S) := \bigcup_{v \in S} U_v, G V ( S ) := v ∈ S ⋃ U v , where U i U_i U i is as defined above, and for a subset of edges T ⊆ E H T \subseteq E_H T ⊆ E H , define
G E ( T ) : = ⋃ e ∈ T W e , G^E(T) := \bigcup_{e \in T} W_e, G E ( T ) := e ∈ T ⋃ W e , where W e W_e W e is as defined above.
In other words G V ( S ) G^V(S) G V ( S ) is the union of vertices in G G G for each ℓ \ell ℓ -subset corresponding to a vertex of S S S and G E ( T ) G^E(T) G E ( T ) is the union of edges in G G G for each clique in G G G corresponding to an edge of T T T .
Lemma 6.2. For all constants α , δ ∈ ( 0 , 1 2 ) \alpha, \delta\in(0, \frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) , there exists a constant c = c ( δ ) c = c(\delta) c = c ( δ ) such that the following is true. Let n ˉ \bar{n} n ˉ be any parameter. Set ℓ = ( log n ˉ ) α \ell= (\log\bar{n})^{\alpha} ℓ = ( log n ˉ ) α and q = n ˉ − ( δ ℓ ) / 2 q = \bar{n}^{-(\delta\ell)/2} q = n ˉ − ( δ ℓ ) /2 . Let G G G be any graph with n ˉ \bar{n} n ˉ many vertices, and sample H ← $ RP q ℓ ( G ) H \overset{\$}{\leftarrow} \operatorname{RP}^{\ell}_{q}(G) H ← $ RP q ℓ ( G ) . With all but o ( 1 ) o(1) o ( 1 ) probability over the randomness of RP q ℓ \operatorname{RP}^{\ell}_{q} RP q ℓ we have that, for all S ⊂ V H S \subset V_H S ⊂ V H with ∣ S ∣ ≤ n ˉ o ( 1 ) |S| \le\bar{n}^{o(1)} ∣ S ∣ ≤ n ˉ o ( 1 ) , ∣ G V ( S ) ∣ > c ℓ ∣ S ∣ |G^V(S)| > c\ell|S| ∣ G V ( S ) ∣ > c ℓ ∣ S ∣ .
Proof. Suppose for contradiction that there exists some S ⊂ V H S \subset V_H S ⊂ V H with ∣ S ∣ = n ˉ o ( 1 ) |S| = \bar{n}^{o(1)} ∣ S ∣ = n ˉ o ( 1 ) and such that ∣ G V ( S ) ∣ ≤ c ℓ ∣ S ∣ |G^V(S)| \le c\ell|S| ∣ G V ( S ) ∣ ≤ c ℓ ∣ S ∣ . This implies that there exists an x = n ˉ o ( 1 ) x = \bar{n}^{o(1)} x = n ˉ o ( 1 ) and some subset S ′ ⊂ V G S' \subset V_G S ′ ⊂ V G of size y ≤ c ℓ x y \le c\ell x y ≤ c ℓ x with the property that at least x x x many vertices v v v in V H V_H V H have U v ⊂ S ′ U_v \subset S' U v ⊂ S ′ . If this event occurs for some y < c ℓ x y < c\ell x y < c ℓ x , this automatically implies that the event also occurs for all larger values of y y y , so throughout the proof we will assume y = c ℓ x y = c\ell x y = c ℓ x .
Let N x N_x N x denote the expected number of such subsets S ′ S' S ′ for a fixed choice of x x x , and N = ∑ x ≤ n ˉ o ( 1 ) N x N = \sum_{x \le\bar{n}^{o(1)}} N_x N = ∑ x ≤ n ˉ o ( 1 ) N x .
Observe that there are ( n ˉ y ) \binom{\bar{n}}{y} ( y n ˉ ) many ways to choose a set S ′ S' S ′ of y y y many nodes in G G G . Furthermore, ( y ℓ ) \binom{y}{\ell} ( ℓ y ) is the total number of ℓ \ell ℓ -sized subsets of a given S ′ S' S ′ , so there are ( ( y ℓ ) x ) \binom{\binom{y}{\ell}}{x} ( x ( ℓ y ) ) many ways to choose x x x many ℓ \ell ℓ -sized subsets. The probability that all x x x of these were actually sampled by RP q ℓ \operatorname{RP}^{\ell}_{q} RP q ℓ (in other words, the probability that they all exist as vertices of H H H ) is q x q^x q x . Take c = δ / 5 c=\delta/5 c = δ /5 . We show by linearity of expectation that
E [ N x ] ≤ ( n ˉ y ) ⋅ ( y ℓ ) ⋅ q x < n ˉ y ⋅ y x ℓ ⋅ p q \begin{aligned}
\mathbb{E}[N_x]\leq\binom{\bar{n}}{y}\cdot\binom{y}{\ell}\cdot q^x \\
&<\bar{n}^{y}\cdot y^{x\ell}\cdot p^q
\end{aligned} E [ N x ] ≤ ( y n ˉ ) ⋅ ( ℓ y ) ⋅ q x < n ˉ y ⋅ y x ℓ ⋅ p q
≤ 2 y log ( n ˉ ) + x ℓ log ( y ) − 1 2 x ℓ δ log ( n ˉ ) \leq2^{y\log(\bar{n})+x\ell\log(y)-\frac{1}{2}x\ell\delta\log(\bar{n})} ≤ 2 y l o g ( n ˉ ) + x ℓ l o g ( y ) − 2 1 x ℓ δ l o g ( n ˉ )
≤ 2 y log ( n ˉ ) + x ℓ ⋅ ( log ( y ) − 1 2 δ log ( n ˉ ) ) \leq2^{y\log(\bar{n})+x\ell\cdot(\log(y)-\frac{1}{2}\delta\log(\bar{n}))} ≤ 2 y l o g ( n ˉ ) + x ℓ ⋅ ( l o g ( y ) − 2 1 δ l o g ( n ˉ ))
≤ 2 y log ( n ˉ ) + x ℓ ⋅ ( log x + log ℓ + log c − 1 2 δ log ( n ˉ ) ) ( y = c x ℓ ) \leq2^{y\log(\bar{n})+x\ell\cdot(\log x+\log\ell+\log c-\frac{1}{2}\delta\log(\bar{n}))}\qquad(y=cx\ell) ≤ 2 y l o g ( n ˉ ) + x ℓ ⋅ ( l o g x + l o g ℓ + l o g c − 2 1 δ l o g ( n ˉ )) ( y = c x ℓ )
≤ 2 y log ( n ˉ ) + x ℓ ⋅ ( o ( 1 ) − 1 2 δ ) log ( n ˉ ) ( ℓ ≤ n ˉ o ( 1 ) , x ≤ n ˉ o ( 1 ) ) \leq2^{y\log(\bar{n})+x\ell\cdot(o(1)-\frac{1}{2}\delta)\log(\bar{n})}\qquad(\ell\leq\bar{n}^{o(1)},\ x\leq\bar{n}^{o(1)}) ≤ 2 y l o g ( n ˉ ) + x ℓ ⋅ ( o ( 1 ) − 2 1 δ ) l o g ( n ˉ ) ( ℓ ≤ n ˉ o ( 1 ) , x ≤ n ˉ o ( 1 ) )
≤ 2 − x ℓ ⋅ δ 4 log ( n ˉ ) = 2 − x ⋅ ω ( log n ˉ ) ( y = c x ℓ , and c < δ / 4 ) \leq2^{-x\ell\cdot\frac{\delta}{4}\log(\bar{n})}=2^{-x\cdot\omega(\log\bar{n})}\qquad(y=cx\ell,\text{ and }c<\delta/4) ≤ 2 − x ℓ ⋅ 4 δ l o g ( n ˉ ) = 2 − x ⋅ ω ( l o g n ˉ ) ( y = c x ℓ , and c < δ /4 )
Taking a union bound over all possible values of x x x gives
E [ N ] = ∑ x ≤ n o ( 1 ) E [ N x ] = ∑ x ≤ n o ( 1 ) 2 − x ω ( log n ˉ ) ≤ 2 − ω ( log n ˉ ) . \mathbb{E}[N]=\sum_{x\leq n^{o(1)}}\mathbb{E}[N_x]=\sum_{x\leq n^{o(1)}}2^{-x\omega(\log\bar{n})}\leq2^{-\omega(\log\bar{n})}. E [ N ] = x ≤ n o ( 1 ) ∑ E [ N x ] = x ≤ n o ( 1 ) ∑ 2 − x ω ( l o g n ˉ ) ≤ 2 − ω ( l o g n ˉ ) .
Finally using Markov’s inequality,
Pr [ N ≥ 1 ] ≤ E [ N ] , \Pr[N\geq1]\leq\mathbb{E}[N], Pr [ N ≥ 1 ] ≤ E [ N ] ,
and therefore N = 0 N=0 N = 0 with all but o ( 1 ) o(1) o ( 1 ) probability.
Lemma 6.3. For all constants α , δ ∈ ( 0 , 1 2 ) \alpha,\delta\in(0,\frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) , there exists a constant c ∗ = c ∗ ( δ ) c^*=c^*(\delta) c ∗ = c ∗ ( δ ) such that the following is true. Let n ˉ \bar n n ˉ be any parameter. Set ℓ = ( log n ˉ ) α \ell=(\log\bar n)^\alpha ℓ = ( log n ˉ ) α and q = n ˉ − ( δ ℓ ) / 2 q=\bar n^{-(\delta\ell)/2} q = n ˉ − ( δ ℓ ) /2 . Sample G ← G ( n , 1 2 ) G\gets G(n,\frac{1}{2}) G ← G ( n , 2 1 ) and H ← RP q ℓ ( G ) H\gets\operatorname{RP}_{q}^{\ell}(G) H ← RP q ℓ ( G ) . With all but o ( 1 ) o(1) o ( 1 ) probability over the random choice of G G G and the randomness of RP q ℓ \operatorname{RP}_{q}^{\ell} RP q ℓ we have that, for all subgraphs S = ( V S , E S ) S=(V_S,E_S) S = ( V S , E S ) of H H H with ∣ V S ∣ = 2 o ( ( log n ˉ ) 2 α ) |V_S|=2^{o((\log\bar n)^{2\alpha})} ∣ V S ∣ = 2 o (( l o g n ˉ ) 2 α ) , ∣ E S ∣ < c ∗ ( ∣ V S ∣ ( log n ˉ ) 1 − α ) |E_S|<c^*(|V_S|(\log\bar n)^{1-\alpha}) ∣ E S ∣ < c ∗ ( ∣ V S ∣ ( log n ˉ ) 1 − α ) .
Proof. Assume that the event in Lemma 6.2 occurs. Now suppose for the sake of contradiction that there exists a subgraph S S S of H H H with ∣ V S ∣ = 2 o ( ( log n ˉ ) 2 α ) |V_S|=2^{o((\log\bar n)^{2\alpha})} ∣ V S ∣ = 2 o (( l o g n ˉ ) 2 α ) and ∣ E S ∣ ≥ c ∗ ∣ V S ∣ ( log n ˉ ) 1 − α |E_S|\geq c^*|V_S|(\log\bar n)^{1-\alpha} ∣ E S ∣ ≥ c ∗ ∣ V S ∣ ( log n ˉ ) 1 − α .
We can actually argue the contradiction for just ∣ E S ∣ = c ∗ ∣ V S ∣ ( log n ˉ ) 1 − α |E_S|=c^*|V_S|(\log\bar n)^{1-\alpha} ∣ E S ∣ = c ∗ ∣ V S ∣ ( log n ˉ ) 1 − α . This is because, if there exists a subgraph S S S with ∣ E S ∣ > c ∗ ∣ V S ∣ ( log n ˉ ) 1 − α |E_S|>c^*|V_S|(\log\bar n)^{1-\alpha} ∣ E S ∣ > c ∗ ∣ V S ∣ ( log n ˉ ) 1 − α , we can arbitrarily delete edges of S S S to get a subgraph S ′ S' S ′ with ∣ E S ′ ∣ = c ∗ ∣ V S ′ ∣ ( log n ˉ ) 1 − α |E_{S'}|=c^*|V_{S'}|(\log\bar n)^{1-\alpha} ∣ E S ′ ∣ = c ∗ ∣ V S ′ ∣ ( log n ˉ ) 1 − α and ∣ V S ′ ∣ = ∣ V S ∣ |V_{S'}|=|V_S| ∣ V S ′ ∣ = ∣ V S ∣ .
Let x : = ∣ V S ∣ x:=|V_S| x := ∣ V S ∣ and y x : = ∣ E S ∣ yx:=|E_S| y x := ∣ E S ∣ (which implies that y = c ∗ ( log n ˉ ) 1 − α y=c^*(\log\bar n)^{1-\alpha} y = c ∗ ( log n ˉ ) 1 − α ). Let N S ( v S ) N_S(v_S) N S ( v S ) denote the open neighborhood of v S ∈ V S v_S\in V_S v S ∈ V S within the subgraph S S S . Without loss of generality, we may assume that the minimum degree of each vertex in S S S is ⌊ y ⌋ = ⌊ c ∗ ( log n ˉ ) 1 − α ⌋ \lfloor y\rfloor=\lfloor c^*(\log\bar n)^{1-\alpha}\rfloor ⌊ y ⌋ = ⌊ c ∗ ( log n ˉ ) 1 − α ⌋ . If not, since y y y is independent of ∣ S ∣ |S| ∣ S ∣ , we can repeatedly delete each vertex of degree less than ⌊ y ⌋ \lfloor y\rfloor ⌊ y ⌋ to get a smaller subgraph S ′ S' S ′ with minimum degree ⌊ y ⌋ \lfloor y\rfloor ⌊ y ⌋ and x ′ < x x'<x x ′ < x many vertices. For ease of exposition, we will actually just assume a minimum degree of y 2 \frac{y}{2} 2 y , since y 2 ≤ ⌊ y ⌋ \frac{y}{2}\leq\lfloor y\rfloor 2 y ≤ ⌊ y ⌋ for any y ≥ 1 y\geq1 y ≥ 1 .
By Lemma 6.2, there exists some constant c = f ( δ ) c=f(\delta) c = f ( δ ) such that
∣ G V ( N S ( v S ) ) ∣ > c ℓ ∣ N S ( v S ) ∣ ≥ c ℓ y 2 |G^V(N_S(v_S))|>c\ell|N_S(v_S)|\geq c\ell\frac{y}{2} ∣ G V ( N S ( v S )) ∣ > c ℓ ∣ N S ( v S ) ∣ ≥ c ℓ 2 y
for all $v_S\in V_S.
Define a mapping ϕ : G V ( V S ) → V S \phi: G^{V}(V_{S}) \to V_{S} ϕ : G V ( V S ) → V S such that, for all v G ∈ G V ( V S ) v_{G} \in G^{V}(V_{S}) v G ∈ G V ( V S ) , we have that ϕ ( v G ) = v S \phi(v_{G}) = v_{S} ϕ ( v G ) = v S for some v S ∈ V S v_{S} \in V_{S} v S ∈ V S such that v G ∈ U v S v_{G} \in U_{v_{S}} v G ∈ U v S . There may be multiple choices of v S v_{S} v S for each v G v_{G} v G ; just choose from these arbitrarily. By the definition of G V ( ⋅ ) G^{V}(\cdot) G V ( ⋅ ) , such a mapping always exists.
Let E ϕ ( v G ) ⊂ G E ( E S ) E_{\phi}(v_{G}) \subset G^{E}(E_{S}) E ϕ ( v G ) ⊂ G E ( E S ) be the set of edges between a vertex v G ∈ G V ( V S ) v_{G} \in G^{V}(V_{S}) v G ∈ G V ( V S ) and the vertices in G V ( N S ( ϕ ( v G ) ) ) G^{V}(N_{S}(\phi(v_{G}))) G V ( N S ( ϕ ( v G ))) . Note that v G v_{G} v G must have an edge to every vertex in G V ( N S ( ϕ ( v G ) ) ) ∖ v G G^{V}(N_{S}(\phi(v_{G}))) \setminus v_{G} G V ( N S ( ϕ ( v G ))) ∖ v G by the definition of the randomized graph product. So ( ∣ G V ( N S ( ϕ ( v G ) ) ) ∣ − 1 ) (|G^{V}(N_{S}(\phi(v_{G})))| - 1) ( ∣ G V ( N S ( ϕ ( v G ))) ∣ − 1 ) is a lower bound on the degree of v G ∈ G V ( V S ) v_{G} \in G^{V}(V_{S}) v G ∈ G V ( V S ) with respect to the edges in G E ( E S ) G^{E}(E_{S}) G E ( E S ) .
We already showed that ∣ G V ( N S ( ϕ ( v G ) ) ) ∣ > c ℓ y 2 |G^{V}(N_{S}(\phi(v_{G})))| > c\ell\frac{y}{2} ∣ G V ( N S ( ϕ ( v G ))) ∣ > c ℓ 2 y for all possible ϕ ( v G ) \phi(v_{G}) ϕ ( v G ) , and therefore this statement holds for all v G v_{G} v G . Thus c ℓ y 2 − 1 c\ell\frac{y}{2} - 1 c ℓ 2 y − 1 is a strict lower bound for the degree of each v G v_{G} v G with respect to G E ( E S ) G^{E}(E_{S}) G E ( E S ) . (In other words the min degree is at least c ℓ y 2 c\ell\frac{y}{2} c ℓ 2 y .)
Applying Lemma 6.2 again, and using that having constant α ∈ ( 0 , 1 2 ) \alpha\in(0,\frac{1}{2}) α ∈ ( 0 , 2 1 ) implies that ∣ V S ∣ = 2 o ( ( log n ˉ ) 2 α ) = n ˉ o ( 1 ) |V_{S}| = 2^{o((\log\bar{n})^{2\alpha})} = \bar{n}^{o(1)} ∣ V S ∣ = 2 o (( l o g n ˉ ) 2 α ) = n ˉ o ( 1 ) , we know that ∣ G V ( V S ) ∣ > c ℓ ∣ V S ∣ |G^{V}(V_{S})| > c\ell|V_{S}| ∣ G V ( V S ) ∣ > c ℓ ∣ V S ∣ .
Let z : = ∣ G E ( E S ) ∣ z := |G^{E}(E_{S})| z := ∣ G E ( E S ) ∣ . Putting all of this together, and observing that the total number of edges in any graph Z = ( V Z , E Z ) Z = (V_{Z}, E_{Z}) Z = ( V Z , E Z ) is at least 1 2 ⋅ ∣ V Z ∣ ⋅ MinDegree ( Z ) \frac{1}{2} \cdot|V_{Z}| \cdot\operatorname{MinDegree}(Z) 2 1 ⋅ ∣ V Z ∣ ⋅ MinDegree ( Z ) , we have
∣ G E ( E S ) ∣ ≥ 1 2 ⋅ ∣ G V ( V S ) ∣ ⋅ c ℓ y 2 > 1 4 ⋅ c 2 ℓ 2 ⋅ y ∣ V S ∣ = 1 4 ⋅ c 2 ℓ 2 ⋅ y x . |G^{E}(E_{S})| \ge\frac{1}{2} \cdot|G^{V}(V_{S})| \cdot c\ell\frac{y}{2} > \frac{1}{4} \cdot c^{2}\ell^{2} \cdot y|V_{S}| = \frac{1}{4} \cdot c^{2}\ell^{2} \cdot yx. ∣ G E ( E S ) ∣ ≥ 2 1 ⋅ ∣ G V ( V S ) ∣ ⋅ c ℓ 2 y > 4 1 ⋅ c 2 ℓ 2 ⋅ y ∣ V S ∣ = 4 1 ⋅ c 2 ℓ 2 ⋅ y x .
We now apply linearity of expectation to show that the number of subgraphs S S S of H H H with ∣ V S ∣ = 2 o ( ( log n ˉ ) 2 α ) |V_{S}| = 2^{o((\log\bar{n})^{2\alpha})} ∣ V S ∣ = 2 o (( l o g n ˉ ) 2 α ) and ∣ E S ∣ = c ∗ ∣ V S ∣ ( log n ˉ ) 1 − α |E_{S}| = c^{*}|V_{S}|(\log\bar{n})^{1-\alpha} ∣ E S ∣ = c ∗ ∣ V S ∣ ( log n ˉ ) 1 − α is vanishing by analyzing the edge probabilities in G G G . Let N x N_{x} N x be the expected number of subgraphs in H H H with x x x nodes and y x yx y x edges. Setting c ∗ = 15 c 2 c^{*} = \frac{15}{c^{2}} c ∗ = c 2 15 and using that the edge probability in G G G is 1 2 \frac{1}{2} 2 1 , we have
E [ N x ] = ( ∣ V H ∣ x ) ⋅ ( ( x 2 ) x y ) ⋅ 2 − z < n ˉ x ℓ ⋅ x 2 x y ⋅ 2 − z < 2 x ℓ log n ˉ + 2 x y log x − 1 4 c 2 ℓ 2 y x = 2 x ( ℓ log n ˉ + 2 y log x − 1 4 c 2 ℓ 2 y ) < 2 x ( ℓ log n ˉ − 1 5 c 2 ℓ 2 y ) = 2 x ( ℓ log n ˉ − 1 5 c 2 ℓ c ∗ log n ˉ ) = 2 − x ( ℓ log n ˉ − 3 ℓ log n ˉ ) ≤ 2 − 2 x ℓ log n ˉ \begin{aligned}
\mathbb{E}[N_{x}] &= \binom{|V_{H}|}{x} \cdot\binom{\binom{x}{2}}{xy} \cdot2^{-z}\\
&< \bar{n}^{x\ell} \cdot x^{2xy} \cdot2^{-z}\\
&< 2^{x\ell\log\bar{n}+2xy\log x-\frac{1}{4}c^{2}\ell^{2}yx}\\
&=2^{x(\ell\log\bar{n}+2y\log x-\frac{1}{4}c^{2}\ell^{2}y)}\\
&<2^{x(\ell\log\bar{n}-\frac{1}{5}c^{2}\ell^{2}y)}\\
&=2^{x(\ell\log\bar{n}-\frac{1}{5}c^{2}\ell c^{*}\log\bar{n})}\\
&=2^{-x(\ell\log\bar{n}-3\ell\log\bar{n})}\\
&\le2^{-2x\ell\log\bar{n}}
\end{aligned} E [ N x ] = ( x ∣ V H ∣ ) ⋅ ( x y ( 2 x ) ) ⋅ 2 − z < n ˉ x ℓ ⋅ x 2 x y ⋅ 2 − z < 2 x ℓ l o g n ˉ + 2 x y l o g x − 4 1 c 2 ℓ 2 y x = 2 x ( ℓ l o g n ˉ + 2 y l o g x − 4 1 c 2 ℓ 2 y ) < 2 x ( ℓ l o g n ˉ − 5 1 c 2 ℓ 2 y ) = 2 x ( ℓ l o g n ˉ − 5 1 c 2 ℓ c ∗ l o g n ˉ ) = 2 − x ( ℓ l o g n ˉ − 3 ℓ l o g n ˉ ) ≤ 2 − 2 x ℓ l o g n ˉ
where ∣ V H ∣ < n ˉ ℓ |V_{H}| < \bar{n}^{\ell} ∣ V H ∣ < n ˉ ℓ , ∣ E G ( E S ) ∣ > 1 4 c 2 ℓ 2 y x |E^{G}(E_{S})| > \frac{1}{4}c^{2}\ell^{2}yx ∣ E G ( E S ) ∣ > 4 1 c 2 ℓ 2 y x , log x = o ( ℓ 2 ) \log x = o(\ell^{2}) log x = o ( ℓ 2 ) , ℓ = ( log ( n ˉ ) ) α \ell= (\log(\bar{n}))^{\alpha} ℓ = ( log ( n ˉ ) ) α and y = c ∗ ( ( log n ˉ ) 1 − α ) y = c^{*}((\log\bar{n})^{1-\alpha}) y = c ∗ (( log n ˉ ) 1 − α ) . Finally this gives us
E [ N ] = ∑ x ≤ 2 o ( ( log n ˉ ) 2 α ) E [ N x ] < ∑ x ≤ 2 o ( ( log n ˉ ) 2 α ) 2 − 2 x ℓ log n ˉ < o ( 1 ) \mathbb{E}[N] = \sum_{x \le2^{o((\log\bar{n})^{2\alpha})}} \mathbb{E}[N_x]
< \sum_{x \le2^{o((\log\bar{n})^{2\alpha})}} 2^{-2x\ell\log\bar{n}}
< o(1) E [ N ] = x ≤ 2 o (( l o g n ˉ ) 2 α ) ∑ E [ N x ] < x ≤ 2 o (( l o g n ˉ ) 2 α ) ∑ 2 − 2 x ℓ l o g n ˉ < o ( 1 )
Using Markov’s inequality,
Pr [ N ≥ 1 ] ≤ E [ N ] , \Pr[N \ge1] \le\mathbb{E}[N], Pr [ N ≥ 1 ] ≤ E [ N ] ,
and therefore N = 0 N = 0 N = 0 with all but o ( 1 ) o(1) o ( 1 ) probability (assuming the event in Lemma 6.2 occurred, which also happens with all but o ( 1 ) o(1) o ( 1 ) probability).
Lemma 6.4. For all constants α , δ ∈ ( 0 , 1 2 ) \alpha, \delta\in(0, \frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) , there exists a constant c ~ = c ~ ( δ ) \tilde{c} = \tilde{c}(\delta) c ~ = c ~ ( δ ) such that the following is true. Let n ˉ \bar{n} n ˉ be any parameter and ζ > 1 \zeta> 1 ζ > 1 be any (not necessarily constant) integer. Set ℓ = ( log n ˉ ) α \ell= (\log\bar{n})^\alpha ℓ = ( log n ˉ ) α and q = n ˉ − ( δ ℓ ) / 2 q = \bar{n}^{-(\delta\ell)/2} q = n ˉ − ( δ ℓ ) /2 . Sample G ← $ G ( n ˉ , 1 2 ) G \xleftarrow{\$} G(\bar{n}, \frac{1}{2}) G $ G ( n ˉ , 2 1 ) , and sample H ← $ RP q ℓ ( G ) H \xleftarrow{\$} \operatorname{RP}_q^\ell(G) H $ RP q ℓ ( G ) . With all but o ( 1 ) o(1) o ( 1 ) probability over the random choice of G G G and the randomness of RP q ℓ \operatorname{RP}_q^\ell RP q ℓ we have that, for all sets S S S of 2 o ( ( log n ˉ ) 2 α ) 2^{o((\log\bar{n})^{2\alpha})} 2 o (( l o g n ˉ ) 2 α ) many ζ \zeta ζ -cliques in H H H , there exists a set S ′ S' S ′ of ( ζ − 1 ) (\zeta- 1) ( ζ − 1 ) -cliques such that ∣ S ′ ∣ ≥ c ~ ζ ( log n ˉ ) 1 − α ∣ S ∣ |S'| \ge\frac{\tilde{c}\zeta}{(\log\bar{n})^{1-\alpha}} |S| ∣ S ′ ∣ ≥ ( l o g n ˉ ) 1 − α c ~ ζ ∣ S ∣ and
∀ C ∈ S ′ , ∃ K ∈ S such that C ⊂ K \forall C \in S', \exists K \in S \text{ such that } C \subset K ∀ C ∈ S ′ , ∃ K ∈ S such that C ⊂ K
Proof. We give a proof by induction. Throughout the proof, we will take S ′ S' S ′ to be the set of all distinct ( ζ − 1 ) (\zeta- 1) ( ζ − 1 ) -cliques contained in some ζ \zeta ζ -clique of S S S .
For the base case of ζ = 2 \zeta= 2 ζ = 2 , the lemma corresponds to lower bounding the ratio of vertices to edges, and so the claim holds by Lemma 6.3 . For the inductive case, we will count the number of ( ζ − 1 ) (\zeta- 1) ( ζ − 1 ) -cliques and ζ \zeta ζ -cliques that each vertex participates in, and then use this to bound the overall ratio between ∣ S ′ ∣ |S'| ∣ S ′ ∣ and ∣ S ∣ |S| ∣ S ∣ . All of the inductive cases are deterministic, so they follow immediately if the event in Lemma 6.3 occurs.
Consider some set S S S satisfying the condition in the lemma, and let V S V_S V S be the union of vertices for all cliques in S S S . We now examine an arbitrary vertex v ∈ V S v \in V_S v ∈ V S . Each distinct ζ \zeta ζ -clique K ∈ S K \in S K ∈ S with v ∈ K v \in K v ∈ K contains a unique ( ζ − 1 ) (\zeta- 1) ( ζ − 1 ) -clique, namely C : = K ∖ { v } C := K \setminus\{v\} C := K ∖ { v } . Denote the set of all such ( ζ − 1 ) (\zeta- 1) ( ζ − 1 ) -cliques to be S v ′ S'_v S v ′ . Note that ∣ S v ′ ∣ ≤ ∣ S ∣ |S'_v| \le|S| ∣ S v ′ ∣ ≤ ∣ S ∣ , since each K ∈ S K \in S K ∈ S contributes at most one ( ζ − 1 ) (\zeta- 1) ( ζ − 1 ) -clique to S v ′ S'_v S v ′ . This implies that that the inductive hypothesis also bounds the ratio of ( ζ − 1 ) (\zeta- 1) ( ζ − 1 ) -cliques to ( ζ − 2 ) (\zeta- 2) ( ζ − 2 ) -cliques in S v ′ S'_v S v ′ .
Observe that v v v participates in exactly ∣ S v ′ ∣ |S'_v| ∣ S v ′ ∣ many ζ \zeta ζ -cliques. But also, v v v participates in exactly as many ( ζ − 1 ) (\zeta- 1) ( ζ − 1 ) -cliques as there are ( ζ − 2 ) (\zeta- 2) ( ζ − 2 ) -cliques fully contained in some ( ζ − 1 ) (\zeta- 1) ( ζ − 1 ) -clique C ∈ S v ′ C \in S'_v C ∈ S v ′ . Denote this set of ( ζ − 2 ) (\zeta- 2) ( ζ − 2 ) -cliques to be S v ′ ′ S''_v S v ′′ . Using the inductive hypothesis, ∣ S v ′ ′ ∣ ≥ c ~ ⋅ ( ζ − 1 ) ⋅ ∣ S v ′ ∣ / ( log n ˉ ) 1 − α |S''_v| \ge\tilde{c} \cdot(\zeta- 1) \cdot|S'_v|/(\log\bar{n})^{1-\alpha} ∣ S v ′′ ∣ ≥ c ~ ⋅ ( ζ − 1 ) ⋅ ∣ S v ′ ∣/ ( log n ˉ ) 1 − α .
Now consider the sum over all counts for ζ \zeta ζ -cliques. We have that
∑ v ∈ V S ∣ S v ′ ∣ = ζ ⋅ ∣ S ∣ \sum_{v \in V_S} |S'_v| = \zeta\cdot|S| v ∈ V S ∑ ∣ S v ′ ∣ = ζ ⋅ ∣ S ∣
since each ζ \zeta ζ -clique is counted exactly ζ \zeta ζ many times. By the same argument,
∑ v ∈ V S ∣ S v ′ ′ ∣ = ( ζ − 1 ) ⋅ ∣ S ′ ∣ . \sum_{v \in V_S} |S''_v| = (\zeta- 1) \cdot|S'|. v ∈ V S ∑ ∣ S v ′′ ∣ = ( ζ − 1 ) ⋅ ∣ S ′ ∣.
Composing these results yields the lemma:
∣ S ′ ∣ = 1 ζ − 1 ∑ v ∈ V S ∣ S v ′ ∣ ≥ 1 ζ − 1 ∑ v ∈ V S ( c ~ ⋅ ( ζ − 1 ) ⋅ ∣ S v ′ ∣ / ( log n ˉ ) 1 − α ) = c ~ ( log n ˉ ) 1 − α ∑ v ∈ V S ∣ S v ′ ∣ = c ~ ζ ( log n ˉ ) 1 − α ∣ S ∣ \begin{aligned}
|S'| &= \frac{1}{\zeta-1}\sum_{v\in V_S}|S'_v| \\
&\ge\frac{1}{\zeta-1}\sum_{v\in V_S}\left(\tilde{c}\cdot(\zeta-1)\cdot|S'_v|/(\log\bar{n})^{1-\alpha}\right) \\
&= \frac{\tilde{c}}{(\log\bar{n})^{1-\alpha}}\sum_{v\in V_S}|S'_v| \\
&= \frac{\tilde{c}\zeta}{(\log\bar{n})^{1-\alpha}}|S|
\end{aligned} ∣ S ′ ∣ = ζ − 1 1 v ∈ V S ∑ ∣ S v ′ ∣ ≥ ζ − 1 1 v ∈ V S ∑ ( c ~ ⋅ ( ζ − 1 ) ⋅ ∣ S v ′ ∣/ ( log n ˉ ) 1 − α ) = ( log n ˉ ) 1 − α c ~ v ∈ V S ∑ ∣ S v ′ ∣ = ( log n ˉ ) 1 − α c ~ ζ ∣ S ∣
Corollary 6.5. Let n ˉ ∈ N \bar{n} \in\mathbb{N} n ˉ ∈ N be any parameter, ζ > 1 \zeta> 1 ζ > 1 be any (not necessarily constant) integer, and α , δ ∈ ( 0 , 1 2 ) \alpha,\delta\in(0,\frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) be any constants. Set ℓ = ( log n ˉ ) α \ell= (\log\bar{n})^\alpha ℓ = ( log n ˉ ) α and q = n ˉ − ( δ ℓ ) / 2 q = \bar{n}^{-(\delta\ell)/2} q = n ˉ − ( δ ℓ ) /2 . Sample G ← $ G ( n ˉ , 1 2 ) G \xleftarrow{\$} G(\bar{n},\frac{1}{2}) G $ G ( n ˉ , 2 1 ) , and sample H ← $ RP q ℓ ( G ) H \xleftarrow{\$} \operatorname{RP}^{\ell}_{q}(G) H $ RP q ℓ ( G ) . With all but o ( 1 ) o(1) o ( 1 ) probability over the random choice of G G G and the randomness of RP q ℓ \operatorname{RP}^{\ell}_{q} RP q ℓ , the following occurs. Any subgraph H ′ = ( V H ′ , E H ′ ) H'=(V_{H'},E_{H'}) H ′ = ( V H ′ , E H ′ ) of H H H with ∣ V H ′ ∣ = 2 o ( ( log n ˉ ) 2 α ) |V_{H'}|=2^{o((\log\bar{n})^{2\alpha})} ∣ V H ′ ∣ = 2 o (( l o g n ˉ ) 2 α ) contains at most O ( ∣ V H ′ ∣ ζ ( log n ˉ ) ( ζ − 1 ) ( 1 − α ) ) O\left(\frac{|V_{H'}|}{\zeta}(\log\bar{n})^{(\zeta-1)(1-\alpha)}\right) O ( ζ ∣ V H ′ ∣ ( log n ˉ ) ( ζ − 1 ) ( 1 − α ) ) many ζ \zeta ζ -cliques.
Proof. The proof follows by iteratively applying Lemma 6.4 .
Definition 6.6 ((Δ , S \Delta,S Δ , S )-High Degree). A ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -clique is said to be ( Δ , S ) (\Delta,S) ( Δ , S ) -high degree if it is contained in at least Δ \Delta Δ many distinct ζ \zeta ζ -cliques of S S S , where S S S is a set of ζ \zeta ζ -cliques.
Lemma 6.7. Let n ˉ ∈ N \bar{n} \in\mathbb{N} n ˉ ∈ N be any parameter, ζ > 1 \zeta> 1 ζ > 1 be any (not necessarily constant) integer, and α , δ ∈ ( 0 , 1 2 ) \alpha,\delta\in(0,\frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) be any constants. Set ℓ = ( log n ˉ ) α \ell=(\log\bar{n})^\alpha ℓ = ( log n ˉ ) α , q = n ˉ − ( δ ℓ ) / 2 q=\bar{n}^{-(\delta\ell)/2} q = n ˉ − ( δ ℓ ) /2 , and Δ = ( log n ˉ ) ζ ( 1 − α ) \Delta=(\log\bar{n})^{\zeta(1-\alpha)} Δ = ( log n ˉ ) ζ ( 1 − α ) . Sample G ← $ G ( n ˉ , 1 2 ) G \xleftarrow{\$} G(\bar{n},\frac{1}{2}) G $ G ( n ˉ , 2 1 ) , and sample H ← $ RP q ℓ ( G ) H \xleftarrow{\$} \operatorname{RP}^{\ell}_{q}(G) H $ RP q ℓ ( G ) . With all but o ( 1 ) o(1) o ( 1 ) probability over the random choice of G G G and randomness of RP q ℓ \operatorname{RP}^{\ell}_{q} RP q ℓ , the following occurs. For any set S S S of 2 o ( ( log n ˉ ) 2 α ) 2^{o((\log\bar{n})^{2\alpha})} 2 o (( l o g n ˉ ) 2 α ) many ζ \zeta ζ -cliques of H H H , define T ⊂ S T\subset S T ⊂ S as
T = { K ∈ S : K has as a subgraph more than one ( Δ , S ) -high degree ( ζ − 1 ) -clique } . T=\{K\in S:K\text{ has as a subgraph more than one }(\Delta,S)\text{-high degree }(\zeta-1)\text{-clique}\}. T = { K ∈ S : K has as a subgraph more than one ( Δ , S ) -high degree ( ζ − 1 ) -clique } . Then ∣ T ∣ = o ( 1 ) ⋅ ∣ S ∣ |T|=o(1)\cdot|S| ∣ T ∣ = o ( 1 ) ⋅ ∣ S ∣ .
Proof. Consider any set S S S satisfying the condition in the lemma. By the pigeonhole principle, and the fact that each ζ \zeta ζ -clique contains exactly ζ \zeta ζ many ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -cliques, at most ζ ∣ S ∣ / Δ \zeta|S|/\Delta ζ ∣ S ∣/Δ many ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -cliques will be ( Δ , S ) (\Delta,S) ( Δ , S ) -high degree. Denote this set of ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -cliques to be S H i g h ′ S'_{\mathrm{High}} S High ′ . We now bound the number of ζ \zeta ζ -cliques K ∈ S K\in S K ∈ S that contain at least two ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -cliques in S H i g h ′ S'_{\mathrm{High}} S High ′ .
Let V H i g h ⊂ V H V_{\mathrm{High}}\subset V_H V High ⊂ V H be the set of all vertices v v v such that there exists C ∈ S H i g h ′ C\in S'_{\mathrm{High}} C ∈ S High ′ with v ∈ C v\in C v ∈ C . Applying a naive upper bound, we have that ∣ V H i g h ∣ ≤ ( ζ − 1 ) ∣ S H i g h ′ ∣ |V_{\mathrm{High}}|\leq(\zeta-1)|S'_{\mathrm{High}}| ∣ V High ∣ ≤ ( ζ − 1 ) ∣ S High ′ ∣ , which is realized when all of the ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -cliques in S H i g h ′ S'_{\mathrm{High}} S High ′ are vertex-disjoint. Applying Corollary 6.5 , we see that at most
O ( ∣ V H i g h ∣ ζ ⋅ ( log n ˉ ) ( ζ − 1 ) ( 1 − α ) ) = O ( ( ∣ S ∣ / Δ ) ⋅ ( log n ˉ ) ( ζ − 1 ) ( 1 − α ) ) = O ( ∣ S ∣ / ( log n ˉ ) 1 − α ) O\left(\frac{|V_{\mathrm{High}}|}{\zeta}\cdot(\log\bar{n})^{(\zeta-1)(1-\alpha)}\right)
=O\left((|S|/\Delta)\cdot(\log\bar{n})^{(\zeta-1)(1-\alpha)}\right)
=O\left(|S|/(\log\bar{n})^{1-\alpha}\right) O ( ζ ∣ V High ∣ ⋅ ( log n ˉ ) ( ζ − 1 ) ( 1 − α ) ) = O ( ( ∣ S ∣/Δ ) ⋅ ( log n ˉ ) ( ζ − 1 ) ( 1 − α ) ) = O ( ∣ S ∣/ ( log n ˉ ) 1 − α ) many ζ \zeta ζ -cliques can possibly span V H i g h V_{\mathrm{High}} V High (even ignoring whether they are in S S S ). The remaining ζ \zeta ζ -cliques in S S S must have at least one vertex outside of V H i g h V_{\mathrm{High}} V High . But if at least one vertex of a ζ \zeta ζ -clique K ∈ S K\in S K ∈ S is outside, then all but one of the ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -cliques C ⊂ K C\subset K C ⊂ K will also have a vertex outside of V H i g h V_{\mathrm{High}} V High . Since V H i g h V_{\mathrm{High}} V High completely
covers all high degree ( ζ − 1 ) (\zeta- 1) ( ζ − 1 ) -cliques, this implies that only one ( ζ − 1 ) (\zeta- 1) ( ζ − 1 ) -cliques in K K K could be high degree.
Therefore the total number of all ζ \zeta ζ -cliques in S S S that have more than one ( Δ , S ) (\Delta, S) ( Δ , S ) -high degree ( ζ − 1 ) (\zeta- 1) ( ζ − 1 ) -clique is O ( ∣ S ∣ / ( log n ˉ ) 1 − α ) = o ( 1 ) ⋅ ∣ S ∣ O(|S|/(\log\bar{n})^{1-\alpha}) = o(1)\cdot|S| O ( ∣ S ∣/ ( log n ˉ ) 1 − α ) = o ( 1 ) ⋅ ∣ S ∣ .
Evidence for the Noisy k k k -LIN Conjecture
Here we discuss some lower bounds about the special case of k k k -XOR, i.e., k k k -LIN over F 2 \mathbb{F}_2 F 2 . We refer readers to a recent work by Kocurek and Manohar [57 ] for lower bounds for k k k -Lin over larger fields.
Computational Indistinguishability (Adapted from [5 ] ). We say that a distribution D \mathcal{D} D over { 0 , 1 } m \{0,1\}^m { 0 , 1 } m ε \varepsilon ε -fools a class F \mathcal{F} F of boolean functions over { 0 , 1 } m \{0,1\}^m { 0 , 1 } m if for every f ∈ F f \in\mathcal{F} f ∈ F we have:
∣ Pr [ f ( D ) = 1 ] − Pr [ f ( U m ) = 1 ] ∣ ≤ ε . \left|\Pr[f(\mathcal{D})=1]-\Pr[f(U_m)=1]\right|\leq\varepsilon. ∣ Pr [ f ( D ) = 1 ] − Pr [ f ( U m ) = 1 ] ∣ ≤ ε .
Here U m U_m U m is the uniform distribution over F 2 m \mathbb{F}_2^m F 2 m . Let D A , ( log n ) − ρ \mathcal{D}_{A,(\log n)^{-\rho}} D A , ( l o g n ) − ρ be the distribution induced by a noisy k k k -XOR sample, where A ∈ F 2 m × n A \in\mathbb{F}_2^{m\times n} A ∈ F 2 m × n . We import the following theorem about the unconditional hardness of the noisy k k k -XOR conjecture from the work of Applebaum, Barak and Wigderson.
Lemma 7.1 (Theorem 9.1 in the full version of [5 ] ). Let A ∈ F 2 m × n A \in\mathbb{F}_2^{m\times n} A ∈ F 2 m × n be any ( 0.51 , k , t ) (0.51,k,t) ( 0.51 , k , t ) -expanding matrix. Then D A , ( log n ) − ρ \mathcal{D}_{A,(\log n)^{-\rho}} D A , ( l o g n ) − ρ satisfies the following:
0 0 0 -fools t t t -wise tests. (D A , ( log n ) − ρ \mathcal{D}_{A,(\log n)^{-\rho}} D A , ( l o g n ) − ρ is t t t -wise independent.)
δ = 1 2 ⋅ ( 1 − 2 ( log n ) − ρ ) t \delta= \frac{1}{2}\cdot(1-2(\log n)^{-\rho})^t δ = 2 1 ⋅ ( 1 − 2 ( log n ) − ρ ) t -fools linear tests. (D A , ( log n ) − ρ \mathcal{D}_{A,(\log n)^{-\rho}} D A , ( l o g n ) − ρ is δ \delta δ -biased.)
8 ⋅ ( 1 − 2 ( log n ) − ρ ) t / 2 d − 1 8\cdot(1-2(\log n)^{-\rho})^{t/2^{d-1}} 8 ⋅ ( 1 − 2 ( log n ) − ρ ) t / 2 d − 1 -fools degree d d d polynomials over F 2 \mathbb{F}_2 F 2 .
In this paper, we use the noisy k k k -XOR conjecture with ρ = O ( 1 ) \rho=O(1) ρ = O ( 1 ) , k = Ω ( log n ) k=\Omega(\log n) k = Ω ( log n ) , and t = 2 log α n t=2^{\log^\alpha n} t = 2 l o g α n . Moreover, we achieve an expansion of, say, 0.99 0.99 0.99 , which is significantly higher than the 0.51 0.51 0.51 threshold in the above theorem. Plugging these in, we can state the following corollary:
Corollary 7.2. Let A ∈ F 2 m × n A \in\mathbb{F}_2^{m\times n} A ∈ F 2 m × n be a d d d -sparse matrix that is a ( 0.51 , log n , 2 log α n ) (0.51,\log n,2^{\log^\alpha n}) ( 0.51 , log n , 2 l o g α n ) -expander for some constant α < 1 2 \alpha< \frac{1}{2} α < 2 1 . Then D A , ( log n ) − ρ \mathcal{D}_{A,(\log n)^{-\rho}} D A , ( l o g n ) − ρ satisfies the following:
0 0 0 -fools any 2 log α n 2^{\log^\alpha n} 2 l o g α n -wise test.
2 − Ω ( 2 log α n ) 2^{-\Omega(2^{\log^\alpha n})} 2 − Ω ( 2 l o g α n ) -fools linear tests.
2 − Ω ( 2 log α n ) 2^{-\Omega(2^{\log^\alpha n})} 2 − Ω ( 2 l o g α n ) -fools degree d d d polynomials over F 2 \mathbb{F}_2 F 2 , for any d ≤ 0.99 log α n d \leq0.99\log^\alpha n d ≤ 0.99 log α n .
Sum of Squares Lower Bounds. Grigoriev [44 ] showed that a random instance of 3-XOR over n n n variables with O ( n ) O(n) O ( n ) clauses cannot be refuted by the degree o ( n ) o(n) o ( n ) sum of squares algorithm. This result was later rediscovered by Schoenebeck [75 ] , who also observed that it can be used to get lower bounds for random instances of k k k -XOR and k k k -SAT. In fact, these lower bounds work for any k k k -XOR instance that is sufficiently expanding. Barak and Steurer [23 ] describe how to derive Grigoriev’s result in this generalized sense, with their main lemma being the following.
Lemma 7.3 (Paraphrased from Lemma 9 in [23 ] ). There exists some constant c ˉ \bar{c} c ˉ such that the following is true. Let ϕ \phi ϕ be any max 3-XOR instance whose clauses constitute a ( 0.51 , 3 , t ) (0.51,3,t) ( 0.51 , 3 , t ) -expanding set system. Then the degree c ˉ t \bar{c}t c ˉ t sum of squares algorithm fails to refute ϕ \phi ϕ .
In other words, even if only a 0.51 fraction of the clauses can be satisfied by any assignment of the variables, the degree c ˉ t \bar{c}t c ˉ t sum of squares algorithm fails to show that we cannot satisfy all of the clauses simultaneously.
Barak and Steurer’s proof proceeds independently of the XOR arity, so it directly translates to k k k -XOR for any (possibly superconstant) k k k . We can thus state the following corollary.
Corollary 7.4. There exists some constant c ˉ \bar{c} c ˉ such that the following is true. Let ϕ \phi ϕ be any max k k k -XOR instance whose clauses constitute a ( 0.51 , k , t ) (0.51,k,t) ( 0.51 , k , t ) -expanding set system. Then the degree c ˉ t \bar{c}t c ˉ t sum of squares algorithm fails to refute ϕ \phi ϕ .
While the above corollary only concerns refutation, not the problem of distinguishing between ( A , A s + e ) (A, A s+e) ( A , A s + e ) and ( A , $ ) (A, \$) ( A , $ ) , it is natural to believe that it gives strong evidence for the security of the noisy k k k -XOR conjecture.
AC0 {}^{0} 0 Circuit Lower Bounds. We can also apply a result of Braverman regarding AC0 {}^{0} 0 circuits [22 ] . We import the following theorem.
Lemma 7.5 (From [22 ] ). There exists some function r ( m , ε , d ) = ( log ( m / ε ) ) O ( d 2 ) r(m,\varepsilon,d)=(\log(m/\varepsilon))^{O(d^{2})} r ( m , ε , d ) = ( log ( m / ε ) ) O ( d 2 ) such that the following holds. For all d = O ( 1 ) d=O(1) d = O ( 1 ) and m = Ω ( 1 ) m=\Omega(1) m = Ω ( 1 ) , for all AC0 {}^{0} 0 circuits X X X of depth d d d and size m m m , and for all r ( m , d , ε ) r(m,d,\varepsilon) r ( m , d , ε ) -wise independent distributions D D D over Boolean vectors, we have that X X X is ε \varepsilon ε -fooled by D D D .
Rearranging values, we get the following corollary.
Corollary 7.6. Any circuit of depth d = O ( 1 ) d=O(1) d = O ( 1 ) and size n O ( 1 ) n^{O(1)} n O ( 1 ) is 2 − 2 Ω ( log α n ) 2^{-2^{\Omega(\log^{\alpha} n)}} 2 − 2 Ω ( l o g α n ) -fooled by D A , ( log n ) − ρ D_{A,(\log n)^{-\rho}} D A , ( l o g n ) − ρ .
Using the Search Version of Noisy k k k -LIN
PKE Scheme
This construction is very similar to the previous one. The only major change is in the decryption procedure.
Notations. Recall that we can interpret every node v ∈ V H v \in V_H v ∈ V H as corresponding to a set U v U_v U v of ℓ \ell ℓ many nodes in G G G , and interpret any edge e ∈ E H e \in E_H e ∈ E H connecting nodes ( v , w ) ∈ V H (v,w) \in V_H ( v , w ) ∈ V H as corresponding to a set of edges W e = K ( U v ∪ U w ) W_e=K(U_v\cup U_w) W e = K ( U v ∪ U w ) . Here K ( X ) K(X) K ( X ) denotes the clique induces by vertices in the set X X X .
As before, for a subset of vertices S ⊆ V H S\subseteq V_H S ⊆ V H , define
G V ( S ) : = ⋃ v ∈ S U v , G^V(S):=\bigcup_{v\in S} U_v, G V ( S ) := v ∈ S ⋃ U v ,
where U i U_i U i is as defined above, and for a subset of edges T ⊆ E H T\subseteq E_H T ⊆ E H , define
G E ( T ) : = ⋃ e ∈ T W e , G^E(T):=\bigcup_{e\in T} W_e, G E ( T ) := e ∈ T ⋃ W e ,
where W e W_e W e is as defined above.
In other words G V ( S ) G^V(S) G V ( S ) is the union of vertices in G G G for each ℓ \ell ℓ -subset corresponding to a vertex of S S S and G E ( T ) G^E(T) G E ( T ) is the union of edges in G G G for each clique in G G G corresponding to an edge of T T T .
Suggested Parameters. We use the same parameters as for the first PKE scheme. Let α , δ ∈ ( 0 , 1 2 ) \alpha,\delta\in(0,\frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) be constants such that Conjecture 1.1 holds, and let γ ∈ ( 1 2 , 1 ) \gamma\in(\frac{1}{2},1) γ ∈ ( 2 1 , 1 ) be a constant such that Conjecture 4.4 holds. (As noted before, if Conjecture 1.1 holds for some α ≥ 1 2 \alpha\ge\frac{1}{2} α ≥ 2 1 , this automatically implies that the conjecture holds for all α ∈ ( 0 , 1 2 ) \alpha\in(0,\frac{1}{2}) α ∈ ( 0 , 2 1 ) .) Assuming the security parameter is λ \lambda λ ,
Size of initial Erdos-Renyi random graph: n ˉ = 2 ( log λ ) 1 / ( 1 + α ) \bar{n}=2^{(\log\lambda)^{1/(1+\alpha)}} n ˉ = 2 ( l o g λ ) 1/ ( 1 + α ) .
Planted clique size: k ˉ = n ˉ δ \bar{k}=\bar{n}^{\delta} k ˉ = n ˉ δ .
Graph product parameter for RP: ℓ = ( log n ˉ ) α \ell=(\log\bar{n})^{\alpha} ℓ = ( log n ˉ ) α .
Node deletion probability for RP: q = n ˉ − ( δ ℓ ) / 2 q=\bar{n}^{-(\delta\ell)/2} q = n ˉ − ( δ ℓ ) /2 .
Clique size (constant integer) for constructing k k k -LIN matrix: ζ = ⌈ 1 1 − γ ⌉ + 1 \zeta=\left\lceil\frac{1}{1-\sqrt{\gamma}}\right\rceil+1 ζ = ⌈ 1 − γ 1 ⌉ + 1 .
Exponent (constant) for block size in k k k -LIN matrix: β = ζ ⋅ ( ζ ( 1 − α ) + 2 ) \beta=\zeta\cdot(\zeta(1-\alpha)+2) β = ζ ⋅ ( ζ ( 1 − α ) + 2 ) .
Exponent (constant) for Bernoulli noise for k k k -LIN samples: ρ = 2 + β ζ \rho=2+\beta\zeta ρ = 2 + β ζ .
Key Generation and Encoding Scheme. The algorithms Gen ( 1 λ ) \operatorname{Gen}(1^\lambda) Gen ( 1 λ ) and Encode ( H , ζ , β ) \operatorname{Encode}(H,\zeta,\beta) Encode ( H , ζ , β ) are identical to those for the first PKE scheme.
Encryption.
⋆ c t ← Enc ( 1 λ , p k , b ∈ { 0 , 1 } ) \mathsf{ct}\leftarrow\operatorname{Enc}(1^\lambda,\mathsf{pk},b\in\{0,1\}) ct ← Enc ( 1 λ , pk , b ∈ { 0 , 1 }) :
Parse p k \mathsf{pk} pk as A \mathbf{A} A . Let A \mathbf{A} A have m m m rows and n n n columns.
Sample e \mathbf{e} e as:
e i = { Random element of F p ∗ , with probability η = ( log n ) − ρ , 0 , otherwise. e_i=
\begin{cases}
\text{Random element of }\mathbb{F}_p^*, & \text{with probability }\eta=(\log n)^{-\rho},\\
0, & \text{otherwise.}
\end{cases} e i = { Random element of F p ∗ , 0 , with probability η = ( log n ) − ρ , otherwise.
Sample s ← $ F p n \mathbf{s}\xleftarrow{\$}\mathbb{F}_p^n s $ F p n , and then sample y ← $ F 2 n ⌈ log p ⌉ \mathbf{y}\xleftarrow{\$}\mathbb{F}_2^{n\lceil\log p\rceil} y $ F 2 n ⌈ l o g p ⌉ conditioned on s ~ ⋅ y = b \tilde{\mathbf{s}}\cdot\mathbf{y}=b s ~ ⋅ y = b , where s ~ \tilde{\mathbf{s}} s ~ is any canonical bit representation of s \mathbf{s} s .
Output c t ← ( y , b = A s + e ) \mathsf{ct}\leftarrow(\mathbf{y},b=\mathbf{A}\mathbf{s}+\mathbf{e}) ct ← ( y , b = As + e ) .
Decryption. Decryption in this case is significantly more involved than it was for the scheme based on decisional k k k -LIN. This is because to enable decryption, one needs to recover the entire secret s \mathbf{s} s with 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) probability. This is a strictly stronger requirement than before.
⋆ b ′ ← Dec ( 1 λ , p k , s k , c t ) b'\leftarrow\operatorname{Dec}(1^\lambda,\mathsf{pk},\mathsf{sk},\mathsf{ct}) b ′ ← Dec ( 1 λ , pk , sk , ct ) :
Parse p k \mathsf{pk} pk as A \mathbf{A} A . Let A \mathbf{A} A have m m m rows and n n n columns.
Parse s k \mathsf{sk} sk as ( H , K H ) (H,K_H) ( H , K H ) .
Parse c t \mathsf{ct} ct as ( y , b ) (\mathbf{y},\mathbf{b}) ( y , b ) .
Let η \eta η be any (superconstant) integer satisfying ( log n ) ρ − 1 ≤ ( η ζ ) ≤ 2 ( log n ) ρ − 1 (\log n)^{\rho-1}\le\binom{\eta}{\zeta}\le2(\log n)^{\rho-1} ( log n ) ρ − 1 ≤ ( ζ η ) ≤ 2 ( log n ) ρ − 1 .
Recompute all canonical labels C j C_j C j .
We will solve for a vector s ′ ∈ F p n \mathbf{s}'\in\mathbb{F}_p^n s ′ ∈ F p n as follows: Interpret the s ′ \mathbf{s}' s ′ as the concatenation of $c_{H,\zeta-1}
many blocks, each of size exactly log β m \log^{\beta} m log β m . In other words, ( s ′ ) T = ( b 1 ∥ ⋯ ∥ b n / log β m ) (\mathbf{s}')^{T} = (\mathbf{b}_1 \Vert\cdots\Vert\mathbf{b}_{n/\log^{\beta} m}) ( s ′ ) T = ( b 1 ∥ ⋯ ∥ b n / l o g β m ) , where ( s ′ ) T (\mathbf{s}')^{T} ( s ′ ) T is the transpose of s ′ \mathbf{s}' s ′ . For each j ∈ [ n / log β m ] j \in[n/\log^{\beta} m] j ∈ [ n / log β m ] , we solve for b j \mathbf{b}_j b j in the following manner.
(a) Let X j ( ζ − 1 ) X_j^{(\zeta-1)} X j ( ζ − 1 ) be the set of vertices in H H H for the ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -clique labeled as C j C_j C j .
(b) Let K ( j ) = ( ⋂ v ∈ X j ( ζ − 1 ) N H ( v ) ) ∩ K H K^{(j)} = \left(\bigcap_{v \in X_j^{(\zeta-1)}} N_H(v)\right) \cap K_H K ( j ) = ( ⋂ v ∈ X j ( ζ − 1 ) N H ( v ) ) ∩ K H .
(c) Let z : = ⌊ ∣ K ( j ) ∣ η − ( ζ − 1 ) ⌋ z := \left\lfloor\frac{|K^{(j)}|}{\eta-(\zeta-1)} \right\rfloor z := ⌊ η − ( ζ − 1 ) ∣ K ( j ) ∣ ⌋ . Randomly partition K ( j ) K^{(j)} K ( j ) into subsets K 1 ( j ) , … , K z ( j ) K_1^{(j)}, \ldots, K_z^{(j)} K 1 ( j ) , … , K z ( j ) of size exactly η − ( ζ − 1 ) \eta-(\zeta-1) η − ( ζ − 1 ) and at most one subset K L e f t o v e r ( j ) K_{\mathrm{Leftover}}^{(j)} K Leftover ( j ) of size less than η − ( ζ − 1 ) \eta-(\zeta-1) η − ( ζ − 1 ) .
(d) For all a ∈ [ z ] a \in[z] a ∈ [ z ] , let T a = K a ( j ) ∪ X j ( ζ − 1 ) T_a = K_a^{(j)} \cup X_j^{(\zeta-1)} T a = K a ( j ) ∪ X j ( ζ − 1 ) .
(e) For all a ∈ [ z ] a \in[z] a ∈ [ z ] , let x a ← Solve ( H , T a , A , b ) \mathbf{x}_a \leftarrow\operatorname{Solve}(H,T_a,\mathbf{A},\mathbf{b}) x a ← Solve ( H , T a , A , b ) .
(f) Set b j \mathbf{b}_j b j to be the majority vote of the corresponding blocks in the x a \mathbf{x}_a x a ’s. If there is no majority vector for b j \mathbf{b}_j b j , set b j \mathbf{b}_j b j to an arbitrary vector.
Output b ′ ← y ⋅ s ~ ′ \mathbf{b}' \leftarrow\mathbf{y} \cdot\tilde{\mathbf{s}}' b ′ ← y ⋅ s ~ ′ , where s ~ ′ \tilde{\mathbf{s}}' s ~ ′ is expressed in the same canonical bit representation as in the algorithm Enc.
Below is the algorithm to solve each system of linear equations.
⋆ x ← Solve ( H , T , A , b ) \mathbf{x} \leftarrow\operatorname{Solve}(H,T,\mathbf{A},\mathbf{b}) x ← Solve ( H , T , A , b ) :
Let A \mathbf{A} A have m m m rows and n n n columns.
Recompute all canonical labels R i R_i R i and C j C_j C j . Recompute all indicator variables I i , j I_{i,j} I i , j .
For all A i \mathbf{A}_i A i , define X i ( ζ ) X_i^{(\zeta)} X i ( ζ ) as the subset of m a t h b f V H mathbf{V}_H ma t hb f V H corresponding to the ζ \zeta ζ clique labelled as R i R_i R i . Define a set S S S of row labels of A \mathbf{A} A as
S = { i : X i ( ζ ) ⊂ T } S = \left\{i : X_i^{(\zeta)} \subset T\right\} S = { i : X i ( ζ ) ⊂ T }
Split every row of A \mathbf{A} A into blocks of length log β m \log^{\beta} m log β m , i.e., A i = ( b i , 1 ∥ ⋯ ∥ b i , c H , ζ − 1 ) \mathbf{A}_i = (\mathbf{b}_{i,1} \Vert\cdots\Vert\mathbf{b}_{i,c_{H,\zeta-1}}) A i = ( b i , 1 ∥ ⋯ ∥ b i , c H , ζ − 1 ) where every b i , j \mathbf{b}_{i,j} b i , j has width log β m \log^{\beta} m log β m . Define a set of block labels S ′ ⊂ [ c H , ζ − 1 ] S' \subset[c_{H,\zeta-1}] S ′ ⊂ [ c H , ζ − 1 ] such that
S ′ = { j : ∃ i ∈ S such that I i , j = 1 } . S' = \left\{j : \exists i \in S \text{ such that } I_{i,j}=1\right\}. S ′ = { j : ∃ i ∈ S such that I i , j = 1 } .
Let A ~ \widetilde{\mathbf{A}} A be the submatrix of A \mathbf{A} A with rows labeled by S S S and columns made by concatenating the blocks labeled by S ′ S' S ′ .
Solve the following system of linear equations using Gaussian elimination:
A ~ x = b ∣ S , \widetilde{\mathbf{A}}\mathbf{x} = \mathbf{b}|_S, A x = b ∣ S ,
where b ∣ S \mathbf{b}|_S b ∣ S is the vector b \mathbf{b} b restricted to indices in S S S .
If the above step returns a valid solution, then output x \mathbf{x} x . Otherwise output 0.
Correctness
We first show that for all j j j , K ( j ) K^{(j)} K ( j ) is very large. In particular, this applies even if the j j j th block of s ′ \mathbf{s}' s ′ corresponds to a ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -clique that is entirely outside of K H K_H K H .
Lemma 8.1. For all constants α , δ ∈ ( 0 , 1 2 ) \alpha, \delta\in(0,\frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) and β > 0 \beta> 0 β > 0 , for all constant integers ζ > 1 \zeta> 1 ζ > 1 , for all large enough λ \lambda λ , the following is true. Set n ˉ = 2 ( log λ ) 1 / ( 1 + α ) \bar{n} = 2^{(\log\lambda)^{1/(1+\alpha)}} n ˉ = 2 ( l o g λ ) 1/ ( 1 + α ) , k ˉ = n ˉ δ \bar{k} = \bar{n}^{\delta} k ˉ = n ˉ δ , ℓ = ( log n ˉ ) α \ell= (\log\bar{n})^{\alpha} ℓ = ( log n ˉ ) α , q = n ˉ − ( δ ℓ ) / 2 q = \bar{n}^{-(\delta\ell)/2} q = n ˉ − ( δ ℓ ) /2 , and ρ = 2 + β ζ \rho= 2 + \beta\zeta ρ = 2 + β ζ . With 1 − 2 − n ˉ Ω ( 1 ) 1-2^{-\bar{n}^{\Omega(1)}} 1 − 2 − n ˉ Ω ( 1 ) probability over the random choice of G G G and the randomness of R P q ℓ \mathrm{RP}^{\ell}_{q} RP q ℓ , we have that ∣ K ( j ) ∣ > n ˉ δ ℓ / 3 |K^{(j)}| > \bar{n}^{\delta\ell/3} ∣ K ( j ) ∣ > n ˉ δ ℓ /3 for all j j j .
Proof. Recall that K ( j ) = ( ⋂ v ∈ X j ( ζ − 1 ) N H ( v ) ) ∩ K H K^{(j)} = \left(\bigcap_{v\in X^{(\zeta-1)}_j}N_H(v)\right)\cap K_H K ( j ) = ( ⋂ v ∈ X j ( ζ − 1 ) N H ( v ) ) ∩ K H , where X j ( ζ − 1 ) X^{(\zeta-1)}_j X j ( ζ − 1 ) is the set of vertices for the ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -clique in H H H labeled C j C_j C j . We will analyze each K ( j ) K^{(j)} K ( j ) in terms of the original graph G G G .
Let the set of vertices for the planted clique in G G G be K G K_G K G . The vertices of X j ( ζ − 1 ) X^{(\zeta-1)}_j X j ( ζ − 1 ) correspond to a set of at most ℓ ⋅ ( ζ − 1 ) \ell\cdot(\zeta-1) ℓ ⋅ ( ζ − 1 ) many vertices in G G G , namely Y = G V ( X j ( ζ − 1 ) ) Y=G^V(X^{(\zeta-1)}_j) Y = G V ( X j ( ζ − 1 ) ) .
By definition of the randomized graph product, we have that G V ( K ( j ) ) ⊆ K G ( j ) G^V(K^{(j)})\subseteq K_G^{(j)} G V ( K ( j ) ) ⊆ K G ( j ) , where K G ( j ) = ( ⋂ u ∈ Y N G ( u ) ) ∩ K G K_G^{(j)}=\left(\bigcap_{u\in Y}N_G(u)\right)\cap K_G K G ( j ) = ( ⋂ u ∈ Y N G ( u ) ) ∩ K G . Furthermore, during R P q ℓ \mathrm{RP}^{\ell}_{q} RP q ℓ , every ℓ \ell ℓ -sized subset of K G ( j ) K_G^{(j)} K G ( j ) becomes a vertex of K ( j ) K^{(j)} K ( j ) with probability q q q .
Our first goal is to give a lower bound on ∣ K G ( j ) ∣ |K_G^{(j)}| ∣ K G ( j ) ∣ that holds for all j j j with very high probability. To do this, we find it more convenient to consider a random set of vertices as the set Y Y Y , and then take a union bound over all possible sets of size up to ℓ ⋅ ( ζ − 1 ) \ell\cdot(\zeta-1) ℓ ⋅ ( ζ − 1 ) .
Fix a random set Y ⊆ V G Y\subseteq V_G Y ⊆ V G , conditioned on ∣ Y ∣ ≤ ℓ ⋅ ( ζ − 1 ) |Y|\leq\ell\cdot(\zeta-1) ∣ Y ∣ ≤ ℓ ⋅ ( ζ − 1 ) , and let K G Y = ( ⋂ u ∈ Y N G ( u ) ) ∩ K G K_G^Y=\left(\bigcap_{u\in Y}N_G(u)\right)\cap K_G K G Y = ( ⋂ u ∈ Y N G ( u ) ) ∩ K G . We have that ∣ K G ∣ = k ˉ = n ˉ δ |K_G|=\bar{k}=\bar{n}^{\delta} ∣ K G ∣ = k ˉ = n ˉ δ by construction, and each vertex of K G K_G K G is in the neighborhood of all vertices in Y Y Y with probability at least 2 − ∣ Y ∣ 2^{-|Y|} 2 − ∣ Y ∣ , over the random choice of G G G and the randomness of Y Y Y . (The true probability is slightly greater since some vertices of Y Y Y may happen to fall inside of the planted clique.) Furthermore, this event occurs independently for each vertex of K G K_G K G . We can thus lower bound the probability that ∣ K G Y ∣ ≥ n ˉ 0.9 δ |K_G^Y|\geq\bar{n}^{0.9\delta} ∣ K G Y ∣ ≥ n ˉ 0.9 δ using a Chernoff bound. Since E [ ∣ K G Y ∣ ] ≥ n ˉ δ 2 − ∣ Y ∣ > 2 n ˉ 0.9 δ \mathbb{E}[|K_G^Y|]\geq\bar{n}^{\delta}2^{-|Y|}>2\bar{n}^{0.9\delta} E [ ∣ K G Y ∣ ] ≥ n ˉ δ 2 − ∣ Y ∣ > 2 n ˉ 0.9 δ when n ˉ \bar{n} n ˉ is sufficiently large and α ∈ ( 0 , 1 2 ) \alpha\in(0,\frac{1}{2}) α ∈ ( 0 , 2 1 ) , we get
Pr [ ∣ K G Y ∣ ≥ n ˉ 0.9 δ ] = 1 − Pr [ ∣ K G Y ∣ < n ˉ 0.9 δ ] \Pr\left[|K_G^Y|\geq\bar{n}^{0.9\delta}\right]=1-\Pr\left[|K_G^Y|<\bar{n}^{0.9\delta}\right] Pr [ ∣ K G Y ∣ ≥ n ˉ 0.9 δ ] = 1 − Pr [ ∣ K G Y ∣ < n ˉ 0.9 δ ]
≥ 1 − Pr [ ∣ K G Y ∣ < 1 2 E [ ∣ K G Y ∣ ] ] \geq1-\Pr\left[|K_G^Y|<\frac{1}{2}\mathbb{E}[|K_G^Y|]\right] ≥ 1 − Pr [ ∣ K G Y ∣ < 2 1 E [ ∣ K G Y ∣ ] ]
≥ 1 − 2 − n ˉ Ω ( 1 ) . \geq1-2^{-\bar{n}^{\Omega(1)}}. ≥ 1 − 2 − n ˉ Ω ( 1 ) .
This lower bound also holds with 1 − 2 − n ˉ Ω ( 1 ) 1-2^{-\bar{n}^{\Omega(1)}} 1 − 2 − n ˉ Ω ( 1 ) probability after taking a union bound over all subsets Y ⊂ V G Y\subset V_G Y ⊂ V G such that ∣ Y ∣ ≤ ℓ ⋅ ( ζ − 1 ) |Y|\leq\ell\cdot(\zeta-1) ∣ Y ∣ ≤ ℓ ⋅ ( ζ − 1 ) , since there are less than n ˉ ℓ ⋅ ( ζ − 1 ) \bar{n}^{\ell\cdot(\zeta-1)} n ˉ ℓ ⋅ ( ζ − 1 ) such subsets. So with probability 1 − 2 − n ˉ Ω ( 1 ) 1-2^{-\bar{n}^{\Omega(1)}} 1 − 2 − n ˉ Ω ( 1 ) , we have that ∣ K G ( j ) ∣ ≥ n ˉ 0.9 |K_G^{(j)}|\geq\bar{n}^{0.9} ∣ K G ( j ) ∣ ≥ n ˉ 0.9 holds for all j j j .
Fix a random choice of j j j . We now lower bound the number of ℓ \ell ℓ -sized subsets of K G ( j ) K_G^{(j)} K G ( j ) that were sampled by R P q ℓ ( G ) \mathrm{RP}^{\ell}_{q}(G) RP q ℓ ( G ) . The number of such subsets is ∣ K ( j ) ∣ |K^{(j)}| ∣ K ( j ) ∣ . We apply a Chernoff bound again, and use that
E [ ∣ K ( j ) ∣ | ∣ K G ( j ) ∣ = n ˉ 0.9 δ ] > 2 n ˉ δ ℓ / 3 . \mathbb{E}\left[|K^{(j)}| \,\middle|\, |K_G^{(j)}|=\bar{n}^{0.9\delta}\right] > 2\bar{n}^{\delta\ell/3}. E [ ∣ K ( j ) ∣ ∣ K G ( j ) ∣ = n ˉ 0.9 δ ] > 2 n ˉ δ ℓ /3 .
Pr [ ∣ K ( j ) ∣ ≥ n ˉ δ ℓ / 3 ] ≥ Pr [ ∣ K ( j ) ∣ ≥ n ˉ δ ℓ / 3 | ∣ K G ( j ) ∣ ≥ n ˉ 0.9 δ ] ⋅ ( 1 − 2 − n ˉ Ω ( 1 ) ) ≥ ( 1 − Pr [ ∣ K ( j ) ∣ < 1 2 E [ ∣ K ( j ) ∣ | ∣ K G ( j ) ∣ ≥ n ˉ 0.9 δ ] ] ) ⋅ ( 1 − 2 − n ˉ Ω ( 1 ) ) > ( 1 − Pr [ ∣ K ( j ) ∣ < 1 2 E [ ∣ K ( j ) ∣ | ∣ K G ( j ) ∣ = n ˉ 0.9 δ ] ] ) ⋅ ( 1 − 2 − n ˉ Ω ( 1 ) ) ≥ 1 − 2 − n ˉ Ω ( 1 ) . \begin{aligned}
\Pr\left[|K^{(j)}|\ge\bar{n}^{\delta\ell/3}\right]
&\ge\Pr\left[|K^{(j)}|\ge\bar{n}^{\delta\ell/3}\,\middle|\,|K_G^{(j)}|\ge\bar{n}^{0.9\delta}\right]\cdot\left(1-2^{-\bar{n}^{\Omega(1)}}\right)\\
&\ge\left(1-\Pr\left[|K^{(j)}|<\frac{1}{2}\mathbb{E}\left[|K^{(j)}|\,\middle|\,|K_G^{(j)}|\ge\bar{n}^{0.9\delta}\right]\right]\right)\cdot\left(1-2^{-\bar{n}^{\Omega(1)}}\right)\\
&> \left(1-\Pr\left[|K^{(j)}|<\frac{1}{2}\mathbb{E}\left[|K^{(j)}|\,\middle|\,|K_G^{(j)}|=\bar{n}^{0.9\delta}\right]\right]\right)\cdot\left(1-2^{-\bar{n}^{\Omega(1)}}\right)\\
&\ge1-2^{-\bar{n}^{\Omega(1)}}.
\end{aligned} Pr [ ∣ K ( j ) ∣ ≥ n ˉ δ ℓ /3 ] ≥ Pr [ ∣ K ( j ) ∣ ≥ n ˉ δ ℓ /3 ∣ K G ( j ) ∣ ≥ n ˉ 0.9 δ ] ⋅ ( 1 − 2 − n ˉ Ω ( 1 ) ) ≥ ( 1 − Pr [ ∣ K ( j ) ∣ < 2 1 E [ ∣ K ( j ) ∣ ∣ K G ( j ) ∣ ≥ n ˉ 0.9 δ ] ] ) ⋅ ( 1 − 2 − n ˉ Ω ( 1 ) ) > ( 1 − Pr [ ∣ K ( j ) ∣ < 2 1 E [ ∣ K ( j ) ∣ ∣ K G ( j ) ∣ = n ˉ 0.9 δ ] ] ) ⋅ ( 1 − 2 − n ˉ Ω ( 1 ) ) ≥ 1 − 2 − n ˉ Ω ( 1 ) .
Applying a union bound over all choices of j j j yields the lemma.
We now show that decryption succeeds with very high probability.
Lemma 8.2. For all constants α , δ ∈ ( 0 , 1 2 ) \alpha,\delta\in(0,\frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) and β > 0 \beta>0 β > 0 , for all constant integers ζ > 1 \zeta>1 ζ > 1 , for all large enough λ \lambda λ , the following is true. Set n ˉ = 2 ( log λ ) 1 / ( 1 + α ) \bar{n}=2(\log\lambda)^{1/(1+\alpha)} n ˉ = 2 ( log λ ) 1/ ( 1 + α ) , k ˉ = n ˉ δ \bar{k}=\bar{n}^{\delta} k ˉ = n ˉ δ , ℓ = ( log n ˉ ) α \ell=(\log\bar{n})^{\alpha} ℓ = ( log n ˉ ) α , q = n ˉ − ( δ ℓ ) / 2 q=\bar{n}^{-(\delta\ell)/2} q = n ˉ − ( δ ℓ ) /2 , and ρ = 2 + β ζ \rho=2+\beta\zeta ρ = 2 + β ζ . Then for all b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } ,
Pr ( p k , s k ) ← Gen ( 1 n ˉ ) [ Dec ( s k , Enc ( p k , b ) ) = b ] ≥ 1 − o ( 1 ) , \Pr_{(\mathrm{pk},\mathrm{sk})\gets\operatorname{Gen}(1^{\bar{n}})}
\left[\operatorname{Dec}(\mathrm{sk},\operatorname{Enc}(\mathrm{pk},b))=b\right]\ge1-o(1), ( pk , sk ) ← Gen ( 1 n ˉ ) Pr [ Dec ( sk , Enc ( pk , b )) = b ] ≥ 1 − o ( 1 ) , where the probability is over the coins of Encode, Gen, Enc, and Dec.
Proof. Assume that the event in Lemma 8.1 occurs. Consider a single block b j b_j b j of s ′ s' s ′ . By Lemma 8.1 , when solving for b j b_j b j , we take the majority vote of the solutions to at least n ˉ δ ℓ / 3 − o ( 1 ) \bar{n}^{\delta\ell/3-o(1)} n ˉ δ ℓ /3 − o ( 1 ) many systems of linear equations. Denote this set of systems to be E \mathcal{E} E .
Each system E a ∈ E E_a\in\mathcal{E} E a ∈ E is derived from a set K a ( j ) ∪ X j ( ζ − 1 ) K_a^{(j)}\cup X_j^{(\zeta-1)} K a ( j ) ∪ X j ( ζ − 1 ) of vertices in H H H . Specifically, the equations are defined by the ζ \zeta ζ -cliques in K a ( j ) ∪ X j ( ζ − 1 ) K_a^{(j)}\cup X_j^{(\zeta-1)} K a ( j ) ∪ X j ( ζ − 1 ) . Because every K a ( j ) K_a^{(j)} K a ( j ) is vertex-disjoint, we have that every ζ \zeta ζ -clique in K a ( j ) ∪ X j ( ζ − 1 ) K_a^{(j)}\cup X_j^{(\zeta-1)} K a ( j ) ∪ X j ( ζ − 1 ) is distinct from every ζ \zeta ζ -clique in K a ′ ( j ) ∪ X j ( ζ − 1 ) K_{a'}^{(j)}\cup X_j^{(\zeta-1)} K a ′ ( j ) ∪ X j ( ζ − 1 ) , for all a ≠ a ′ a\ne a' a = a ′ . So for every E a , E a ′ ∈ E E_a,E_{a'}\in\mathcal{E} E a , E a ′ ∈ E with a ≠ a ′ a\ne a' a = a ′ , every equation in E a E_a E a is distinct from every equation in E a ′ E_{a'} E a ′ . (In fact, all of the ( ζ − 1 ) (\zeta-1) ( ζ − 1 ) -cliques are also distinct, except for the one labeled C j C_j C j , which is common across all E a ∈ E E_a\in\mathcal{E} E a ∈ E .)
Using that K ( j ) K^{(j)} K ( j ) was partitioned randomly, we know that each E a ∈ E E_a\in\mathcal{E} E a ∈ E will give the correct value for all variables in its system with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , via the same proof technique as in Lemma 5.3 . In fact, the probability is only over the randomness of the error vector restricted the that specific set of equations. This means that every E a E_a E a gives the correct value for b j b_j b j independently with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) . By a Chernoff bound, the probability that more than half of the systems give the correct value is more than 1 − 2 − n ˉ Ω ( 1 ) 1-2^{-\bar{n}^{\Omega(1)}} 1 − 2 − n ˉ Ω ( 1 ) . If this occurs, then the majority vote must give the correct value of b j b_j b j regardless of the values given by the remaining systems.
The lemma follows by taking a union bound over all blocks of s ′ s' s ′ , multiplying by the probability that the even in Lemma 8.1 occurs, and noting that recovering s ′ = s s'=s s ′ = s implies b ′ = b b'=b b ′ = b .
Security
Security follows from nearly the same hybrid argument as in § 5 , but with an additional appeal to the Goldreich-Levin Theorem [41 ] .
Lemma 8.3 (Weak Security). Assume that Conjecture 1.1 holds for some constants α , δ ∈ ( 0 , 1 2 ) \alpha,\delta\in(0,\frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) , and assume that Conjecture 4.4 holds for some constant γ ∈ ( 1 2 , 1 ) \gamma\in(\frac{1}{2},1) γ ∈ ( 2 1 , 1 ) . Then for all large enough λ \lambda λ , the following
is true. Set n ˉ = 2 ( log λ ) 1 / ( 1 + α ) \bar{n}=2^{(\log\lambda)^{1/(1+\alpha)}} n ˉ = 2 ( l o g λ ) 1/ ( 1 + α ) , k ˉ = n ˉ δ \bar{k}=\bar{n}^{\delta} k ˉ = n ˉ δ , ℓ = ( log n ˉ ) α \ell=(\log\bar{n})^{\alpha} ℓ = ( log n ˉ ) α , q = n ˉ − ( δ ℓ ) / 2 q=\bar{n}^{-(\delta\ell)/2} q = n ˉ − ( δ ℓ ) /2 , ζ = ⌈ 1 1 − γ ⌉ + 1 \zeta=\left\lceil\frac{1}{1-\sqrt{\gamma}}\right\rceil+1 ζ = ⌈ 1 − γ 1 ⌉ + 1 , β = ζ ⋅ ( ζ ( 1 − α ) + 2 ) \beta=\zeta\cdot(\zeta(1-\alpha)+2) β = ζ ⋅ ( ζ ( 1 − α ) + 2 ) , and ρ = 2 + β ζ \rho=2+\beta\zeta ρ = 2 + β ζ . For all poly ( λ ) \operatorname{poly}(\lambda) poly ( λ ) size algorithms A \mathcal{A} A ,
∣ Pr [ ( p k , s k ) ← Gen ( 1 λ ) ; A ( p k , Enc ( p k , 0 ) ) = 1 ] − Pr [ ( p k , s k ) ← Gen ( 1 λ ) ; A ( p k , Enc ( p k , 1 ) ) = 1 ] ∣ ≤ 0.99 \left|\Pr\left[(\mathrm{pk},\mathrm{sk})\gets\operatorname{Gen}(1^\lambda);\mathcal{A}(\mathrm{pk},\operatorname{Enc}(\mathrm{pk},0))=1\right]-\Pr\left[(\mathrm{pk},\mathrm{sk})\gets\operatorname{Gen}(1^\lambda);\mathcal{A}(\mathrm{pk},\operatorname{Enc}(\mathrm{pk},1))=1\right]\right|\le0.99 Pr [ ( pk , sk ) ← Gen ( 1 λ ) ; A ( pk , Enc ( pk , 0 )) = 1 ] − Pr [ ( pk , sk ) ← Gen ( 1 λ ) ; A ( pk , Enc ( pk , 1 )) = 1 ] ≤ 0.99
where the probability is taken over the coins of Encode, Gen, Enc, and A \mathcal{A} A .
Proof. We will use standard hybrid arguments.
Hybrid H 0 ( 1 λ ) \mathcal{H}_0(1^\lambda) H 0 ( 1 λ ) :
G ← $ G ( n ˉ , 1 2 , k ˉ ) G\mathrel{\overset{\$}{\leftarrow}}\mathcal{G}(\bar{n},\frac{1}{2},\bar{k}) G ← $ G ( n ˉ , 2 1 , k ˉ ) .
H ← $ RP p ℓ ( G ) H\mathrel{\overset{\$}{\leftarrow}}\operatorname{RP}_{p}^{\ell}(G) H ← $ RP p ℓ ( G ) .
S ← Encode ( H , ζ , β ) S\leftarrow\operatorname{Encode}(H,\zeta,\beta) S ← Encode ( H , ζ , β ) . Let A A A have m m m rows and n n n columns.
Let A ∈ F p m × n A\in\mathbb{F}_{p}^{m\times n} A ∈ F p m × n be the matrix where we replace each nonzero entry in S S S with a random element in F p ∗ \mathbb{F}_{p}^{*} F p ∗ .
p k : = A \mathrm{pk}:=A pk := A .
c t ← Enc ( p k , 0 ) \mathrm{ct}\leftarrow\operatorname{Enc}(\mathrm{pk},0) ct ← Enc ( pk , 0 ) where
c t ← ( y , A s + e ) \mathrm{ct}\leftarrow(y,A s+e) ct ← ( y , A s + e )
Here s ← $ F p n s\mathrel{\overset{\$}{\leftarrow}}\mathbb{F}_{p}^{n} s ← $ F p n , and then we sample y ← $ F 2 n ⌈ log p ⌉ y\mathrel{\overset{\$}{\leftarrow}}\mathbb{F}_{2}^{n\lceil\log p\rceil} y ← $ F 2 n ⌈ l o g p ⌉ conditioned on s ~ ⋅ y = 0 \tilde{s}\cdot y=0 s ~ ⋅ y = 0 . We sample e e e as:
e i = { Random element of F p ∗ , with probability η = ( log n ) − ρ , 0 , otherwise. e_i=
\begin{cases}
\text{Random element of }\mathbb{F}_{p}^{*}, & \text{with probability }\eta=(\log n)^{-\rho},\\
0, & \text{otherwise.}
\end{cases} e i = { Random element of F p ∗ , 0 , with probability η = ( log n ) − ρ , otherwise.
Output ( p k , c t ) (\mathrm{pk},\mathrm{ct}) ( pk , ct ) .
Hybrid H 0 , $ ( 1 λ ) \mathcal{H}_{0,\$}(1^\lambda) H 0 , $ ( 1 λ ) :
G ← $ G ( n ˉ , 1 2 ) G\mathrel{\overset{\$}{\leftarrow}}\mathcal{G}(\bar{n},\frac{1}{2}) G ← $ G ( n ˉ , 2 1 ) .
H ← $ RP p ℓ ( G ) H\mathrel{\overset{\$}{\leftarrow}}\operatorname{RP}_{p}^{\ell}(G) H ← $ RP p ℓ ( G ) .
S ← Encode ( H , ζ , β ) S\leftarrow\operatorname{Encode}(H,\zeta,\beta) S ← Encode ( H , ζ , β ) . Let A A A have m m m rows and n n n columns.
Let A ∈ F p m × n A\in\mathbb{F}_{p}^{m\times n} A ∈ F p m × n be the matrix where we replace each nonzero entry in S S S with a random element in F p ∗ \mathbb{F}_{p}^{*} F p ∗ .
p k : = A \mathrm{pk}:=A pk := A .
c t ← Enc ( p k , 0 ) \mathrm{ct}\leftarrow\operatorname{Enc}(\mathrm{pk},0) ct ← Enc ( pk , 0 ) where
c t ← ( y , A s + e ) (1) \mathrm{ct}\leftarrow(y,A s+e) \tag*{(1)} ct ← ( y , A s + e ) (1)
Here s ← $ F p n \mathbf{s} \stackrel{\$}{\leftarrow} \mathbb{F}_p^n s ← $ F p n , and then we sample y ← $ F 2 n ⌈ log p ⌉ \mathbf{y} \stackrel{\$}{\leftarrow} \mathbb{F}_2^{n\lceil\log p\rceil} y ← $ F 2 n ⌈ l o g p ⌉ conditioned on s ~ ⋅ y = 0 \tilde{\mathbf{s}}\cdot\mathbf{y}=0 s ~ ⋅ y = 0 . We sample e \mathbf{e} e as:
e i = { Random element of F p ∗ , with probability η = ( log n ) − p . 0 , otherwise. e_i =
\begin{cases}
\text{Random element of }\mathbb{F}_p^*, & \text{with probability }\eta=(\log n)^{-p}.\\
0, & \text{otherwise.}
\end{cases} e i = { Random element of F p ∗ , 0 , with probability η = ( log n ) − p . otherwise.
Output ( p k , c t ) (\mathrm{pk},\mathrm{ct}) ( pk , ct ) .
Hybrid H 1 , $ ( 1 λ ) \mathcal{H}_{1,\$}(1^\lambda) H 1 , $ ( 1 λ ) :
G ← $ G ( n ˉ , 1 2 ) G \stackrel{\$}{\leftarrow} \mathcal{G}(\bar{n},\frac{1}{2}) G ← $ G ( n ˉ , 2 1 ) .
H ← $ R P p ℓ ( G ) H \stackrel{\$}{\leftarrow} \mathrm{RP}_p^\ell(G) H ← $ RP p ℓ ( G ) .
S ← Encode ( H , ζ , β ) S \leftarrow\operatorname{Encode}(H,\zeta,\beta) S ← Encode ( H , ζ , β ) . Let A \mathbf{A} A have m m m rows and n n n columns.
Let A ∈ F p m × n \mathbf{A}\in\mathbb{F}_p^{m\times n} A ∈ F p m × n be the matrix where we replace each nonzero entry in S S S with a random element in F p ∗ \mathbb{F}_p^* F p ∗ .
p k : = A \mathrm{pk}:=\mathbf{A} pk := A .
c t ← Enc ( p k , 0 ) \mathrm{ct}\leftarrow\operatorname{Enc}(\mathrm{pk},0) ct ← Enc ( pk , 0 ) where
c t ← ( y , A s + e ) \mathrm{ct}\leftarrow(\mathbf{y},\mathbf{A}\mathbf{s}+\mathbf{e}) ct ← ( y , As + e )
Here s ← $ F p n \mathbf{s} \stackrel{\$}{\leftarrow} \mathbb{F}_p^n s ← $ F p n , and then we sample y ← $ F 2 n ⌈ log p ⌉ \mathbf{y} \stackrel{\$}{\leftarrow} \mathbb{F}_2^{n\lceil\log p\rceil} y ← $ F 2 n ⌈ l o g p ⌉ conditioned on s ~ ⋅ y = 1 \tilde{\mathbf{s}}\cdot\mathbf{y}=1 s ~ ⋅ y = 1 . We sample e \mathbf{e} e as:
e i = { Random element of F p ∗ , with probability η = ( log n ) − p . 0 , otherwise. e_i =
\begin{cases}
\text{Random element of }\mathbb{F}_p^*, & \text{with probability }\eta=(\log n)^{-p}.\\
0, & \text{otherwise.}
\end{cases} e i = { Random element of F p ∗ , 0 , with probability η = ( log n ) − p . otherwise.
Output ( p k , c t ) (\mathrm{pk},\mathrm{ct}) ( pk , ct ) .
Hybrid H 1 ( 1 λ ) \mathcal{H}_1(1^\lambda) H 1 ( 1 λ ) :
G ← $ G ( n ˉ , 1 2 , k ˉ ) G \stackrel{\$}{\leftarrow} \mathcal{G}(\bar{n},\frac{1}{2},\bar{k}) G ← $ G ( n ˉ , 2 1 , k ˉ ) .
H ← $ R P p ℓ ( G ) H \stackrel{\$}{\leftarrow} \mathrm{RP}_p^\ell(G) H ← $ RP p ℓ ( G ) .
S ← Encode ( H , ζ , β ) S \leftarrow\operatorname{Encode}(H,\zeta,\beta) S ← Encode ( H , ζ , β ) . Let A \mathbf{A} A have m m m rows and n n n columns.
Let A ∈ F p m × n \mathbf{A}\in\mathbb{F}_p^{m\times n} A ∈ F p m × n be the matrix where we replace each nonzero entry in S S S with a random element in F p ∗ \mathbb{F}_p^* F p ∗ .
p k : = A \mathrm{pk}:=\mathbf{A} pk := A .
c t ← Enc ( p k , 0 ) \mathrm{ct}\leftarrow\operatorname{Enc}(\mathrm{pk},0) ct ← Enc ( pk , 0 ) where
c t ← ( y , A s + e ) \mathrm{ct}\leftarrow(\mathbf{y},\mathbf{A}\mathbf{s}+\mathbf{e}) ct ← ( y , As + e )
Here s ← $ F p n \mathbf{s} \xleftarrow{\$} \mathbb{F}_p^n s $ F p n , and then we sample y ← $ F 2 n ⌈ log p ⌉ \mathbf{y} \xleftarrow{\$} \mathbb{F}_2^{n\lceil\log p\rceil} y $ F 2 n ⌈ l o g p ⌉ conditioned on s ~ ⋅ y = 1 \tilde{\mathbf{s}}\cdot\mathbf{y}=1 s ~ ⋅ y = 1 . We sample e \mathbf{e} e as:
e i = { Random element of F p ∗ , with probability η = ( log n ) − p , 0 , otherwise. e_i =
\begin{cases}
\text{Random element of }\mathbb{F}_p^*, & \text{with probability }\eta=(\log n)^{-p},\\
0, & \text{otherwise.}
\end{cases} e i = { Random element of F p ∗ , 0 , with probability η = ( log n ) − p , otherwise.
Output ( p k , c t ) (\mathrm{pk},\mathrm{ct}) ( pk , ct ) .
As before, before analyzing the hybrids, note that λ = n ˉ Θ ( ℓ ) \lambda=\bar{n}^{\Theta(\ell)} λ = n ˉ Θ ( ℓ ) and λ = n Θ ( 1 ) \lambda=n^{\Theta(1)} λ = n Θ ( 1 ) with very high probability.
We first argue that H 0 ≈ 1 3 H 0 , $ \mathcal{H}_0\approx_{\frac{1}{3}}\mathcal{H}_{0,\$} H 0 ≈ 3 1 H 0 , $ and H 1 , $ ≈ 1 3 H 1 \mathcal{H}_{1,\$}\approx_{\frac{1}{3}}\mathcal{H}_1 H 1 , $ ≈ 3 1 H 1 , which follows from the planted clique conjecture.
Claim 8.4 (H 0 ≈ 1 3 H 0 , $ \mathcal{H}_0\approx_{\frac{1}{3}}\mathcal{H}_{0,\$} H 0 ≈ 3 1 H 0 , $ ). Assume that Conjecture 1.1 holds for some constants α , δ ∈ ( 0 , 1 2 ) \alpha,\delta\in(0,\frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) . For all sufficiently large λ \lambda λ , and for all constant γ ∈ ( 1 2 , 1 ) \gamma\in(\frac{1}{2},1) γ ∈ ( 2 1 , 1 ) , the following is true. Set the parameters as in the lemma statement. For all poly ( λ ) \operatorname{poly}(\lambda) poly ( λ ) -size algorithms A \mathcal{A} A ,
∣ Pr [ A ( 1 λ , H 0 ( 1 λ ) ) = 1 ] − Pr [ A ( 1 λ , H 0 , $ ( 1 λ ) ) = 1 ] ∣ ≤ 1 3 . \left|\Pr\left[\mathcal{A}(1^\lambda,\mathcal{H}_0(1^\lambda))=1\right]-\Pr\left[\mathcal{A}(1^\lambda,\mathcal{H}_{0,\$}(1^\lambda))=1\right]\right|\leq\frac{1}{3}. Pr [ A ( 1 λ , H 0 ( 1 λ )) = 1 ] − Pr [ A ( 1 λ , H 0 , $ ( 1 λ )) = 1 ] ≤ 3 1 . Proof. Identical to the proof of Claim 5.9.
Claim 8.5 (H 1 , $ ≈ 1 3 H 1 \mathcal{H}_{1,\$}\approx_{\frac{1}{3}}\mathcal{H}_1 H 1 , $ ≈ 3 1 H 1 ). Assume that Conjecture 1.1 holds for some constants α , δ ∈ ( 0 , 1 2 ) \alpha,\delta\in(0,\frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) . For all sufficiently large λ \lambda λ , and for all constant γ ∈ ( 1 2 , 1 ) \gamma\in(\frac{1}{2},1) γ ∈ ( 2 1 , 1 ) , the following is true. Set the parameters as in the lemma statement. For all poly ( λ ) \operatorname{poly}(\lambda) poly ( λ ) -size algorithms A \mathcal{A} A ,
∣ Pr [ A ( 1 λ , H 1 , $ ( 1 λ ) ) = 1 ] − Pr [ A ( 1 λ , H 1 ( 1 λ ) ) = 1 ] ∣ ≤ 1 3 . \left|\Pr\left[\mathcal{A}(1^\lambda,\mathcal{H}_{1,\$}(1^\lambda))=1\right]-\Pr\left[\mathcal{A}(1^\lambda,\mathcal{H}_1(1^\lambda))=1\right]\right|\leq\frac{1}{3}. Pr [ A ( 1 λ , H 1 , $ ( 1 λ )) = 1 ] − Pr [ A ( 1 λ , H 1 ( 1 λ )) = 1 ] ≤ 3 1 . Proof. Identical to the proof of Claim 5.11.
We now argue that H 0 , $ ≈ 0.30 H 1 , $ \mathcal{H}_{0,\$}\approx_{0.30}\mathcal{H}_{1,\$} H 0 , $ ≈ 0.30 H 1 , $ via an appeal to the Goldreich-Levin Theorem [41 ] . We first state a version of this theorem below:
Claim 8.6 (Adapted from Theorem 3 in [15 ] ). Suppose we have an unknown vector s ∈ F 2 n \mathbf{s}\in\mathbb{F}_2^n s ∈ F 2 n , but we know the value of f ( s ) f(\mathbf{s}) f ( s ) for some function f f f . Suppose further that we have a poly ( n ) \operatorname{poly}(n) poly ( n ) -size algorithm Q Q Q satisfying
Pr y ← $ F 2 n [ Q ( y , f ( s ) ) = y ⋅ s ] ≥ 0.51 , \Pr_{\mathbf{y}\xleftarrow{\$}\mathbb{F}_2^n}[Q(\mathbf{y},f(\mathbf{s}))=\mathbf{y}\cdot\mathbf{s}]\geq0.51, y $ F 2 n Pr [ Q ( y , f ( s )) = y ⋅ s ] ≥ 0.51 , and a poly ( n ) \operatorname{poly}(n) poly ( n ) -size algorithm Y Y Y satisfying
Y ( s ′ , f ( s ) ) = 1 if and only if s ′ = s . Y(\mathbf{s}',f(\mathbf{s}))=1\text{ if and only if }\mathbf{s}'=\mathbf{s}. Y ( s ′ , f ( s )) = 1 if and only if s ′ = s . Then there exists a poly ( n ) \operatorname{poly}(n) poly ( n ) -size algorithm Z Z Z such that
Pr [ Z ( f ( s ) ) = s ] = 1 − o ( 1 ) . \Pr[Z(f(\mathbf{s}))=\mathbf{s}]=1-o(1). Pr [ Z ( f ( s )) = s ] = 1 − o ( 1 ) .
Claim 8.7 (H 0 , $ ≈ 0.30 H 1 , $ \mathcal{H}_{0,\$}\approx_{0.30}\mathcal{H}_{1,\$} H 0 , $ ≈ 0.30 H 1 , $ ). Assume that Conjecture 4.4 holds for some constant γ ∈ ( 1 2 , 1 ) \gamma\in(\frac{1}{2},1) γ ∈ ( 2 1 , 1 ) . For all sufficiently large λ \lambda λ , and for all constants α , δ ∈ ( 0 , 1 2 ) \alpha,\delta\in(0,\frac{1}{2}) α , δ ∈ ( 0 , 2 1 ) , the following is true. Set the parameters as in the lemma statement. For all poly ( λ ) \operatorname{poly}(\lambda) poly ( λ ) -size algorithms A \mathcal{A} A ,
∣ Pr [ A ( 1 λ , H 0 , $ ( 1 λ ) ) = 1 ] − Pr [ A ( 1 λ , H 1 , $ ( 1 λ ) ) = 1 ] ∣ ≤ 0.30. \left|\Pr\left[\mathcal{A}(1^\lambda,\mathcal{H}_{0,\$}(1^\lambda))=1\right]-\Pr\left[\mathcal{A}(1^\lambda,\mathcal{H}_{1,\$}(1^\lambda))=1\right]\right|\leq0.30. Pr [ A ( 1 λ , H 0 , $ ( 1 λ )) = 1 ] − Pr [ A ( 1 λ , H 1 , $ ( 1 λ )) = 1 ] ≤ 0.30.
Proof. Towards a proof by contradiction, suppose there exists a poly ( λ ) \operatorname{poly}(\lambda) poly ( λ ) -size algorithm A \mathcal{A} A to differentiate between H 0 , $ \mathcal{H}_{0,\$} H 0 , $ and H 1 , $ \mathcal{H}_{1,\$} H 1 , $ with advantage more than 0.30. By randomly sampling λ \lambda λ many choices of ( A , s , e ) (\mathcal{A},s,e) ( A , s , e ) as generated in hybrids H 0 , $ \mathcal{H}_{0,\$} H 0 , $ and H 1 , $ \mathcal{H}_{1,\$} H 1 , $ , and then executing A \mathcal{A} A on these, we can approximate
p 0 ≈ Pr [ A ( 1 λ , H 0 , $ ( 1 λ ) ) = 1 ] and p_0 \approx\Pr\left[\mathcal{A}(1^\lambda,\mathcal{H}_{0,\$}(1^\lambda))=1\right]\text{ and} p 0 ≈ Pr [ A ( 1 λ , H 0 , $ ( 1 λ )) = 1 ] and
p 1 ≈ Pr [ A ( 1 λ , H 1 , $ ( 1 λ ) ) = 1 ] p_1 \approx\Pr\left[\mathcal{A}(1^\lambda,\mathcal{H}_{1,\$}(1^\lambda))=1\right] p 1 ≈ Pr [ A ( 1 λ , H 1 , $ ( 1 λ )) = 1 ]
to within an error of ± o ( 1 ) \pm o(1) ± o ( 1 ) , with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) .
Suppose the above procedure indicates that p 1 > p 0 p_1>p_0 p 1 > p 0 . Then we define an algorithm B \mathcal{B} B which (i) takes as input a tuple ( y , A , A s + e ) (y,\mathcal{A},As+e) ( y , A , A s + e ) , (ii) gives the tuple as input to algorithm A \mathcal{A} A , and (iii) outputs 1 if A \mathcal{A} A outputs 1, and outputs 0 otherwise. If instead the procedure indicates that p 1 < p 0 p_1<p_0 p 1 < p 0 , we define B \mathcal{B} B identically, except it outputs 1 if A \mathcal{A} A does not output 1, and it outputs 0 otherwise. Assuming the estimates for p 0 p_0 p 0 and p 1 p_1 p 1 are accurate to within ± o ( 1 ) \pm o(1) ± o ( 1 ) , we have that
Pr ( y , A , s , e ) is sampled as in H 1 , $ [ B ( y , A , A s + e ) = 1 ] − Pr ( y , A , s , e ) is sampled as in H 0 , $ [ B ( y , A , A s + e ) = 1 ] > 0.30. (2) \Pr_{(y,\mathcal{A},s,e)\text{ is sampled as in }\mathcal{H}_{1,\$}}\left[\mathcal{B}(y,\mathcal{A},As+e)=1\right]-
\Pr_{(y,\mathcal{A},s,e)\text{ is sampled as in }\mathcal{H}_{0,\$}}\left[\mathcal{B}(y,\mathcal{A},As+e)=1\right]>0.30. \tag*{(2)} ( y , A , s , e ) is sampled as in H 1 , $ Pr [ B ( y , A , A s + e ) = 1 ] − ( y , A , s , e ) is sampled as in H 0 , $ Pr [ B ( y , A , A s + e ) = 1 ] > 0.30. (2)
This ensures that, with high probability, B \mathcal{B} B is more likely to return 1 when the dot product y ⋅ s ~ y\cdot\tilde{s} y ⋅ s ~ does indeed equal 1 (the original algorithm A \mathcal{A} A may have the reverse property).
We now perform a probabilistic analysis of B \mathcal{B} B . Define
f ( A , s , e ) = Pr y ← $ F p n conditioned on s ~ ⋅ y = 1 [ B ( y , A , A s + e ) = 1 ] − Pr y ← $ F p n conditioned on s ~ ⋅ y = 0 [ B ( y , A , A s + e ) = 1 ] . f(\mathcal{A},s,e)=
\Pr_{\substack{y\overset{\$}{\leftarrow}\mathbb{F}_p^n\\\text{conditioned on }\tilde{s}\cdot y=1}}
\left[\mathcal{B}(y,\mathcal{A},As+e)=1\right]-
\Pr_{\substack{y\overset{\$}{\leftarrow}\mathbb{F}_p^n\\\text{conditioned on }\tilde{s}\cdot y=0}}
\left[\mathcal{B}(y,\mathcal{A},As+e)=1\right]. f ( A , s , e ) = y ← $ F p n conditioned on s ~ ⋅ y = 1 Pr [ B ( y , A , A s + e ) = 1 ] − y ← $ F p n conditioned on s ~ ⋅ y = 0 Pr [ B ( y , A , A s + e ) = 1 ] .
Note that f ( A , s , e ) ∈ [ − 1 , 1 ] f(\mathcal{A},s,e)\in[-1,1] f ( A , s , e ) ∈ [ − 1 , 1 ] for all ( A , s , e ) (\mathcal{A},s,e) ( A , s , e ) . The sampling procedure for ( A , s , e ) (\mathcal{A},s,e) ( A , s , e ) is the same in both hybrids, so we can rewrite (1) as
∑ ( A , s , e ) Pr [ ( A , s , e ) is sampled in H 1 , $ ] ⋅ f ( A , s , e ) > 0.30. (3) \sum_{(\mathcal{A},s,e)}\Pr\left[(\mathcal{A},s,e)\text{ is sampled in }\mathcal{H}_{1,\$}\right]\cdot f(\mathcal{A},s,e)>0.30. \tag*{(3)} ( A , s , e ) ∑ Pr [ ( A , s , e ) is sampled in H 1 , $ ] ⋅ f ( A , s , e ) > 0.30. (3)
Let T \mathcal{T} T be the set of all possible ( A , s , e ) (\mathcal{A},s,e) ( A , s , e ) , and let T ≥ ε ⊆ T \mathcal{T}_{\geq\varepsilon}\subseteq\mathcal{T} T ≥ ε ⊆ T be the set of all ( A , s , e ) (\mathcal{A},s,e) ( A , s , e ) such that f ( A , s , e ) ≥ ε f(\mathcal{A},s,e)\geq\varepsilon f ( A , s , e ) ≥ ε . For all ( A , s , e ) ∈ T ∖ T ≥ ε (\mathcal{A},s,e)\in\mathcal{T}\setminus\mathcal{T}_{\geq\varepsilon} ( A , s , e ) ∈ T ∖ T ≥ ε , we have the trivial upper bound that f ( A , s , e ) < ε f(\mathcal{A},s,e)<\varepsilon f ( A , s , e ) < ε . For all ( A , s , e ) ∈ T ≥ ε (\mathcal{A},s,e)\in\mathcal{T}_{\geq\varepsilon} ( A , s , e ) ∈ T ≥ ε , we have the trivial upper bound that f ( A , s , e ) ≤ 1 f(\mathcal{A},s,e)\leq1 f ( A , s , e ) ≤ 1 . This combined with (2) implies that
∑ ( A , s , e ) ∈ T ≥ ε Pr [ ( A , s , e ) is sampled in H 1 , $ ] + ε ⋅ ∑ ( A , s , e ) ∈ T ∖ T ≥ ε Pr [ ( A , s , e ) is sampled in H 1 , $ ] > 0.30 , \sum_{(\mathcal{A},s,e)\in\mathcal{T}_{\geq\varepsilon}}\Pr\left[(\mathcal{A},s,e)\text{ is sampled in }\mathcal{H}_{1,\$}\right]
+\varepsilon\cdot
\sum_{(\mathcal{A},s,e)\in\mathcal{T}\setminus\mathcal{T}_{\geq\varepsilon}}\Pr\left[(\mathcal{A},s,e)\text{ is sampled in }\mathcal{H}_{1,\$}\right]>0.30, ( A , s , e ) ∈ T ≥ ε ∑ Pr [ ( A , s , e ) is sampled in H 1 , $ ] + ε ⋅ ( A , s , e ) ∈ T ∖ T ≥ ε ∑ Pr [ ( A , s , e ) is sampled in H 1 , $ ] > 0.30 ,
and hence,
∑ ( A , s , e ) ∈ T ≥ ε Pr [ ( A , s , e ) is sampled in H 1 , $ ] > 0.30 − ε . \sum_{(\mathcal{A},s,e)\in\mathcal{T}_{\geq\varepsilon}}\Pr\left[(\mathcal{A},s,e)\text{ is sampled in }\mathcal{H}_{1,\$}\right]>0.30-\varepsilon. ( A , s , e ) ∈ T ≥ ε ∑ Pr [ ( A , s , e ) is sampled in H 1 , $ ] > 0.30 − ε .
Expressed equivalently, we have
Pr ( A , s , e ) is sampled as in H 1 , $ [ ( A , s , e ) ∈ T ≥ ε ] > 0.30 − ε . \Pr_{(\mathcal{A},s,e)\text{ is sampled as in }\mathcal{H}_{1,\$}}\left[(\mathcal{A},s,e)\in\mathcal{T}_{\geq\varepsilon}\right]>0.30-\varepsilon. ( A , s , e ) is sampled as in H 1 , $ Pr [ ( A , s , e ) ∈ T ≥ ε ] > 0.30 − ε .
This is useful because, for all ( A , s , e ) ∈ T ≥ ε (A,s,e) \in T_{\geq\varepsilon} ( A , s , e ) ∈ T ≥ ε , by the definition of T ≥ ε T_{\geq\varepsilon} T ≥ ε , we have the lower bound that
Pr y ← $ F p n c o n d i t i o n e d o n s ~ ⋅ y = 1 [ B ( y , A , A s + e ) = 1 ] − Pr y ← $ F p n c o n d i t i o n e d o n s ~ ⋅ y = 0 [ B ( y , A , A s + e ) = 1 ] ≥ ε . (4) \Pr_{y \xleftarrow{\$} \mathbb{F}_{p}^{n}\ \mathrm{conditioned\ on}\ \tilde{s}\cdot y=1}[\mathcal{B}(y,A,As+e)=1]-
\Pr_{y \xleftarrow{\$} \mathbb{F}_{p}^{n}\ \mathrm{conditioned\ on}\ \tilde{s}\cdot y=0}[\mathcal{B}(y,A,As+e)=1]\geq\varepsilon. \tag*{(4)} y $ F p n conditioned on s ~ ⋅ y = 1 Pr [ B ( y , A , A s + e ) = 1 ] − y $ F p n conditioned on s ~ ⋅ y = 0 Pr [ B ( y , A , A s + e ) = 1 ] ≥ ε . (4)
This analysis actually shows that we can interpret B \mathcal{B} B as a predictor for the dot product y ⋅ s y\cdot s y ⋅ s . (This will serve as algorithm Q \mathcal{Q} Q when we apply the Goldreich-Levin Theorem.) To see this, first let
p a v g = 1 2 ( Pr y ← $ F p n c o n d i t i o n e d o n s ~ ⋅ y = 1 [ B ( y , A , A s + e ) = 1 ] + Pr y ← $ F p n c o n d i t i o n e d o n s ~ ⋅ y = 0 [ B ( y , A , A s + e ) = 1 ] ) . (5) p_{\mathrm{avg}}=\frac{1}{2}\left(\Pr_{y \xleftarrow{\$} \mathbb{F}_{p}^{n}\ \mathrm{conditioned\ on}\ \tilde{s}\cdot y=1}[\mathcal{B}(y,A,As+e)=1]+\Pr_{y \xleftarrow{\$} \mathbb{F}_{p}^{n}\ \mathrm{conditioned\ on}\ \tilde{s}\cdot y=0}[\mathcal{B}(y,A,As+e)=1]\right). \tag*{(5)} p avg = 2 1 ( y $ F p n conditioned on s ~ ⋅ y = 1 Pr [ B ( y , A , A s + e ) = 1 ] + y $ F p n conditioned on s ~ ⋅ y = 0 Pr [ B ( y , A , A s + e ) = 1 ] ) . (5)
Now we analyze the behavior of B \mathcal{B} B on ( y , A , A s + e ) (y,A,As+e) ( y , A , A s + e ) , where y y y is a random vector y ← $ F 2 n y \xleftarrow{\$} \mathbb{F}_{2}^{n} y $ F 2 n and we assume ( A , s , e ) ∈ T ≥ ε (A,s,e) \in T_{\geq\varepsilon} ( A , s , e ) ∈ T ≥ ε . With probability 1 2 \frac{1}{2} 2 1 over the choice of y y y , we have that y ⋅ s = 1 y\cdot s=1 y ⋅ s = 1 , and in this case
Pr [ B ( y , A , A s + e ) = 1 = y ⋅ s ~ ] ≥ p a v g + ε 2 . \Pr[\mathcal{B}(y,A,As+e)=1=y\cdot\tilde{s}]\geq p_{\mathrm{avg}}+\frac{\varepsilon}{2}. Pr [ B ( y , A , A s + e ) = 1 = y ⋅ s ~ ] ≥ p avg + 2 ε .
With the remaining probability 1 2 \frac{1}{2} 2 1 over the choice of y y y , we have y ⋅ s ~ = 0 y\cdot\tilde{s}=0 y ⋅ s ~ = 0 , and in this case
Pr [ B ( y , A , A s + e ) = 1 ] ≤ p a v g − ε 2 . \Pr[\mathcal{B}(y,A,As+e)=1]\leq p_{\mathrm{avg}}-\frac{\varepsilon}{2}. Pr [ B ( y , A , A s + e ) = 1 ] ≤ p avg − 2 ε .
which implies
Pr [ B ( y , A , A s + e ) = 0 = y ⋅ s ] ≥ 1 − p a v g + ε 2 . \Pr[\mathcal{B}(y,A,As+e)=0=y\cdot s]\geq1-p_{\mathrm{avg}}+\frac{\varepsilon}{2}. Pr [ B ( y , A , A s + e ) = 0 = y ⋅ s ] ≥ 1 − p avg + 2 ε .
Accumulating these probabilities, we have the following when y ← $ F 2 n y \xleftarrow{\$} \mathbb{F}_{2}^{n} y $ F 2 n and ( A , s , e ) ∈ T ≥ ε (A,s,e) \in T_{\geq\varepsilon} ( A , s , e ) ∈ T ≥ ε :
Pr [ B ( y , A , A s + e ) = y ⋅ s ] ≥ 1 2 ⋅ ( p a v g + ε 2 ) + 1 2 ⋅ ( 1 − p a v g + ε 2 ) = 1 2 + ε 2 . \Pr[\mathcal{B}(y,A,As+e)=y\cdot s]\geq\frac{1}{2}\cdot\left(p_{\mathrm{avg}}+\frac{\varepsilon}{2}\right)+\frac{1}{2}\cdot\left(1-p_{\mathrm{avg}}+\frac{\varepsilon}{2}\right)=\frac{1}{2}+\frac{\varepsilon}{2}. Pr [ B ( y , A , A s + e ) = y ⋅ s ] ≥ 2 1 ⋅ ( p avg + 2 ε ) + 2 1 ⋅ ( 1 − p avg + 2 ε ) = 2 1 + 2 ε .
If we take ε = 0.04 \varepsilon=0.04 ε = 0.04 , then the predictor has accuracy 0.52 > 0.51 0.52>0.51 0.52 > 0.51 .
We can also define a poly ( λ ) \operatorname{poly}(\lambda) poly ( λ ) -size algorithm D ( s ′ , A , A s + e ) \mathcal{D}(s',A,As+e) D ( s ′ , A , A s + e ) such that, with 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) probability over the choice of ( A , s , e ) (A,s,e) ( A , s , e ) as produced in H 0 , $ \mathcal{H}_{0,\$} H 0 , $ and H 1 , $ \mathcal{H}_{1,\$} H 1 , $ , we have that D ( s ′ , A , A s + e ) = 1 \mathcal{D}(s',A,As+e)=1 D ( s ′ , A , A s + e ) = 1 if and only if s ′ = s s'=s s ′ = s . (Note that we can freely convert between the bit representation s ~ ′ \tilde{s}' s ~ ′ and the original vector s ′ s' s ′ .) This will serve as algorithm Y \mathcal{Y} Y when we apply the Goldreich-Levin Theorem. The algorithm will simply compute b ′ = A s ′ b'=As' b ′ = A s ′ , determine the Hamming distance between b ′ b' b ′ and b = A s + e b=As+e b = A s + e , and then return either 0 or 1 based on the magnitude of the Hamming distance. With 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) probability over the choice of ( A , s , e ) (A,s,e) ( A , s , e ) as produced in H 0 , $ \mathcal{H}_{0,\$} H 0 , $ and H 1 , $ \mathcal{H}_{1,\$} H 1 , $ , if we set s ′ = s s'=s s ′ = s , the Hamming distance will be significantly smaller than for all other choices of s ′ s' s ′ . (This property is folklore. Roughly speaking, it follows because, when ζ \zeta ζ is a constant, every column of A A A will have polynomial Hamming weight with very high probability.) We can determine an appropriate Hamming distance cutoff in polynomial time.
Now we apply Claim 8.6 to get a poly ( λ ) \operatorname{poly}(\lambda) poly ( λ ) -size algorithm X \mathcal{X} X that recovers s s s from f ( s ) f(s) f ( s ) , where f ( s ) = ( A , A s + e ) f(s)=(A,As+e) f ( s ) = ( A , A s + e ) . The algorithm follows by simply applying the claim with Q : = B \mathcal{Q}:=\mathcal{B} Q := B , Y : = D \mathcal{Y}:=\mathcal{D} Y := D , and X : = Z \mathcal{X}:=\mathcal{Z} X := Z .
Assuming that ( A , s , e ) ∈ T ≥ 0.04 (A,s,e) \in T_{\geq0.04} ( A , s , e ) ∈ T ≥ 0.04 , that we can construct the algorithm D \mathcal{D} D , and that our estimates for p 0 , p 1 p_0,p_1 p 0 , p 1 are accurate to within ± o ( 1 ) \pm o(1) ± o ( 1 ) , the algorithm X \mathcal{X} X will recover the vector s s s with 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) probability. Applying the probability bounds we derived above, we see that X \mathcal{X} X recovers s s s from ( A , A s + e ) (A,As+e) ( A , A s + e ) with probability 0.26 − o ( 1 ) 0.26 - o(1) 0.26 − o ( 1 ) when ( A , s , e ) (\mathbf{A},\mathbf{s},\mathbf{e}) ( A , s , e ) is sampled as in H 0 , $ \mathcal{H}_{0,\$} H 0 , $ and H 1 , $ \mathcal{H}_{1,\$} H 1 , $ .
As in the proof of Claim 5.10 , the matrix A \mathbf{A} A will satisfy the preconditions of Conjecture 4.4 with 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) probability. Furthermore, the sampling procedure for s \mathbf{s} s and e \mathbf{e} e is the same in the statement of Conjecture 4.4 as in the hybrids H 0 , $ \mathcal{H}_{0,\$} H 0 , $ and H 1 , $ \mathcal{H}_{1,\$} H 1 , $ . Combining this with the above analysis of algorithm X \mathcal{X} X , we see that X \mathcal{X} X is an algorithm for the search problem in Conjecture 4.4 that succeeds with probability at least 0.26 − o ( 1 ) > 1 4 0.26-o(1)>\frac{1}{4} 0.26 − o ( 1 ) > 4 1 , which is a contradiction.
Combining Claims 8.4 , 8.5 , and 8.7 , and accounting for the fact that λ = n ~ Θ ( ℓ ) \lambda=\widetilde{n}^{\Theta(\ell)} λ = n Θ ( ℓ ) and λ = n Θ ( 1 ) \lambda=n^{\Theta(1)} λ = n Θ ( 1 ) with very high probability, we get
∣ Pr [ ( p k , s k ) ← Gen ( 1 λ ) ; A ( p k , Enc ( p k , 0 ) ) = 1 ] − Pr [ ( p k , s k ) ← Gen ( 1 λ ) ; A ( p k , Enc ( p k , 1 ) ) = 1 ] ∣ ≤ 29 30 + o ( 1 ) < 0.99. \left|\Pr\left[(\mathsf{pk},\mathsf{sk})\leftarrow\operatorname{Gen}(1^\lambda);\mathcal{A}(\mathsf{pk},\operatorname{Enc}(\mathsf{pk},0))=1\right]-\Pr\left[(\mathsf{pk},\mathsf{sk})\leftarrow\operatorname{Gen}(1^\lambda);\mathcal{A}(\mathsf{pk},\operatorname{Enc}(\mathsf{pk},1))=1\right]\right|\leq\frac{29}{30}+o(1)<0.99. Pr [ ( pk , sk ) ← Gen ( 1 λ ) ; A ( pk , Enc ( pk , 0 )) = 1 ] − Pr [ ( pk , sk ) ← Gen ( 1 λ ) ; A ( pk , Enc ( pk , 1 )) = 1 ] ≤ 30 29 + o ( 1 ) < 0.99.
Proof. Identical to the proof of Theorem 5.12 .
References