ACM Transactions on Computation Theory

We present a novel approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled, fully homomorphic encryption schemes (capable of evaluating arbitrary polynomial-size circuits of a-priori bounded depth), without Gentry’s bootstrapping procedure. Specifically, we offer a choice of FHE schemes based on the learning with error (LWE) or Ring LWE (RLWE) problems that have 2 λ security against known attacks. We construct the following. (1) A leveled FHE scheme that can evaluate depth-L arithmetic circuits (composed of fan-in 2 gates) using O(λ. L3) per-gate computation, quasilinear in the security parameter. Security is based on RLWE for an approximation factor exponential in L. This construction does not use the bootstrapping procedure. (2) A leveled FHE scheme that can evaluate depth-L arithmetic circuits (composed of fan-in 2 gates) using O(λ2) per-gate computation, which is independent of L. Security is based on RLWE for quasipolynomial factors. This construction uses bootstrapping as an optimization. We obtain similar results for LWE, but with worse performance. All previous (leveled) FHE schemes required a per-gate computation of Ω(λ3.5), and all of them relied on subexponential hardness assumptions. We introduce a number of further optimizations to our scheme based on the Ring LWE assumption. As an example, for circuits of large width (e.g., where a constant fraction of levels have width Ω(λ)), we can reduce the per-gate computation of the bootstrapped version to O(λ), independent of L, by batching the bootstrapping operation. At the core of our construction is a new approach for managing the noise in lattice-based ciphertexts, significantly extending the techniques of Brakerski and Vaikuntanathan [2011b].

Zvika Brakerski

Craig Gentry

Vinod Vaikuntanathan

ACM Trans. Comput. Theory

(Leveled) Fully Homomorphic Encryption without Bootstrapping

（分层）无需引导的全同态加密

We show that the space-bounded Statistical Zero Knowledge classes \({{{\sf SZK}_{\sf L}}} \) and \({{{\sf {NISZK}_{\sf {L}}}}} \) are surprisingly robust, in that the power of the verifier and simulator can be strengthened or weakened without affecting the resulting class. Coupled with other recent characterizations of these classes [5], this can be viewed as lending support to the conjecture that these classes may coincide with the non-space-bounded classes \({{{\sf SZK}}} \) and \({{{\sf {NISZK}_{\sf {L}}}}} \) , respectively.

Eric Allender

Jacob Gray

Saachi Mutreja

Harsha Tirumala

Pengxiang Wang

Robustness for Space-Bounded Statistical Zero Knowledge

空间有界统计零知识的鲁棒性

We show that the Consensus Division theorem implies lower bounds on the chromatic number of Kneser hypergraphs, offering a novel proof for a result of Alon, Frankl, and Lovász (Trans. Amer. Math. Soc., 1986) and for its generalization by Kříž (Trans. Amer. Math. Soc., 1992). Our approach is applied to study the computational complexity of the total search problem Kneser \(^p \) , which given a succinct representation of a coloring of a p -uniform Kneser hypergraph with fewer colors than its chromatic number, asks to find a monochromatic hyperedge. We prove that for every prime p , the Kneser \(^p \) problem with an extended access to the input coloring is efficiently reducible to a quite weak approximation of the Consensus Division problem with p shares. In particular, for p = 2, the problem is efficiently reducible to any non-trivial approximation of the Consensus Halving problem on normalized monotone functions. We further show that for every prime p , the Kneser \(^p \) problem lies in the complexity class \(\mathsf {PPA} {-}p \) . As an application, we establish limitations on the complexity of the Kneser \(^p \) problem, restricted to colorings with a bounded number of colors.

Ishay Haviv

The Chromatic Number of Kneser Hypergraphs via Consensus Division

通过共识分配确定Kneser超图的色数

Local search problems consist of a set of feasible solutions, an objective function, and a neighborhood relation which assigns to each feasible solution a set of neighbors. A solution S is called locally optimal if none of its neighbors has a better objective value than S . For PLS-complete local search problems, there is presumably no polynomial-time algorithm which finds a locally optimal solution, even though determining whether a solution is locally optimal and finding a better one if this is not the case can be done in polynomial time. We study local search for Weighted Independent Set and Weighted Dominating Set with the 3-swap neighborhood. The 3-swap neighborhood of a vertex set S in G is the collection of vertex sets which can be obtained from S by exchanging at most three vertices. On the negative side, the problem of finding a 3-swap-optimal independent set or dominating set is PLS-complete. Using the PLS-completeness for independent sets with the 3-swap-neighborhood we also show PLS-completeness for a large class of maximum-weight subgraph problems. On the positive side, we show that locally optimal independent sets or dominating sets can be found in polynomial time when allowing all 3-swaps except a) the swaps that remove two vertices from the current solution and add one vertex to the solution or b) the swaps that remove one vertex from the current solution and add two vertices to the solution. This result is shown via general algorithms for subset-weight optimization problems with a restricted k -swap neighborhood.

Christian Komusiewicz

Nils Morawietz

Finding 3-Swap-Optimal Independent Sets and Dominating Sets is Hard

寻找3-交换最优独立集和支配集是困难的

The communication class UPP cc is a communication analog of the Turing Machine complexity class PP . It is characterized by a matrix-analytic complexity measure called sign-rank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds. For a communication problem f , let f ∧ f denote the function that evaluates f on two disjoint inputs and outputs the AND of the results. We exhibit a communication problem f with UPP cc ( f ) = O (log n ), and UPP cc ( f ∧ f ) = Θ (log 2 n ). This is the first result showing that UPP communication complexity can increase by more than a constant factor under intersection. We view this as a first step toward showing that UPP cc , the class of problems with polylogarithmic-cost UPP communication protocols, is not closed under intersection. Our result shows that the function class consisting of intersections of two majorities on n bits has dimension complexity n Omega Ω(log n ) . This matches an upper bound of (Klivans, O’Donnell, and Servedio, FOCS 2002), who used it to give a quasipolynomial time algorithm for PAC learning intersections of polylogarithmically many majorities. Hence, fundamentally new techniques will be needed to learn this class of functions in polynomial time.

Mark Bun

Nikhil S. Mande

Justin Thaler

Sign-rank Can Increase under Intersection

符号秩在交集下可以增加

We show that any product-depth Δ algebraic circuit for the Iterated Matrix Multiplication polynomial IMM n , d (when d = O (log n /log log n )) must be of size at least \(n^{\Omega \left(d^{1/(\varphi ^2)^{\Delta }}\right)} \) where φ = 1.618… is the golden ratio. This improves the recent breakthrough result of Limaye, Srinivasan, and Tavenas (FOCS’21), who showed a super polynomial lower bound of the form \(n^{\Omega \left(d^{1/4^{\Delta }}\right)} \) for constant-depth circuits. One crucial idea of the (LST21) result was to use set-multilinear polynomials where each set in the variables’ underlying partition could be of different sizes. By picking the set sizes more carefully (depending on the depth we are working with), we first show that any product-depth Δ set-multilinear circuit for IMM n , d (when d = O (log n )) needs size at least \(n^{\Omega \left(d^{1/\varphi ^{\Delta }}\right)} \) . This improves the \(n^{\Omega \left(d^{1/2^{\Delta }}\right)} \) lower bound of (LST21). We then use their Hardness Escalation technique to lift this to general circuits. We also show that these techniques cannot improve our lower bound significantly. For the specific two set sizes used in (LST21), they showed that their lower bound cannot be improved. We show that for any d o (1) set sizes (out of maximum possible d ), the scope for improving our lower bound is minuscule. There exists a set-multilinear circuit that has product-depth Δ and size almost matching our lower bound such that the value of the measure used to prove the lower bound is maximum for this circuit. This results in a barrier to further improvement using the same measure.

C.S. Bhargav

Sagnik Dutta

Nitin Saxena

Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits

常深度代数电路的改进下界及证明障碍

We suggest a general framework to study dependency schemes for dependency quantified Boolean formulas (DQBF). As our main contribution, we exhibit a new infinite collection of implication-free DQBF dependency schemes that generalise the reflexive resolution path dependency scheme. We establish soundness of all these schemes, implying that they can be used in any DQBF proof system. We further explore the power of QBF and DQBF resolution systems parameterised by implication-free dependency schemes and show that the hierarchical structure naturally present among the dependency schemes translates isomorphically to a hierarchical structure of parameterised proof systems with respect to p-simulation. As a special case, we demonstrate that our new schemes are exponentially stronger than the reflexive resolution path dependency scheme when used in Q-resolution, thus resulting in the strongest QBF dependency schemes known to date.

短名	ACM Trans. Comput. Theory
Journal Impact	0.62
国际分区	COMPUTER SCIENCE, THEORY & METHODS(Q3)

ISSN	1942-3454, 1942-3462
h-index	20

涉及主题	数学计算机科学组合数学离散数学算法数学分析理论计算机科学程序设计语言物理哲学几何学纯数学上下界工程类图形统计认识论人工智能量子力学
出版信息	出版商: Association for Computing Machinery (ACM)，出版周期: ，期刊类型: journal，开源期刊: 否
基本数据	创刊年份: 2009，原创研究文献占比: 100.00%，自引率:0.00%， Gold OA占比: 2.13%

ACM Transactions on Computation Theory

期刊引文格式

有 1 位以上作者的期刊

有 2 位作者的期刊

有 3 位作者的期刊

有 5 位以上作者的期刊

书籍引用格式

学位论文引用格式

网页引用格式

专利引用格式

手工熬夜修改参考文献？研飞自动匹配期刊，一键轻松成稿，支持 Word/WPS

投稿经验分享

(Leveled) Fully Homomorphic Encryption without Bootstrapping

Robustness for Space-Bounded Statistical Zero Knowledge

The Chromatic Number of Kneser Hypergraphs via Consensus Division

Finding 3-Swap-Optimal Independent Sets and Dominating Sets is Hard

Sign-rank Can Increase under Intersection

Robustness for Space-Bounded Statistical Zero Knowledge

The Chromatic Number of Kneser Hypergraphs via Consensus Division

Finding 3-Swap-Optimal Independent Sets and Dominating Sets is Hard

Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits

Strong (D)QBF Dependency Schemes via Implication-free Resolution Paths