Fast Bounded-Independence Functions and Their Duals

• URL: http://arxiv.org/abs/2606.07009v1
• Date: Fri, 05 Jun 2026 07:53:04 GMT
• Title: Fast Bounded-Independence Functions and Their Duals
• Abstract summary: Motivated by cryptographic applications, we generalize and improve on previous results in this area.<n>We demonstrate the usefulness of the above results to cryptography.<n>This includes the first nontrivial protocols for perfectly secure multiparty computation.
• Score: 21.031497777539332
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We continue the study of {\em fast} functions, computable by linear-size circuits, that share useful properties of random functions. Motivated by cryptographic applications, we generalize and improve on previous results in this area, obtaining the following results: - For any constant $t$, we construct a fast $t$-wise independent hash function with algebraic degree $\log_2 t$ (over $\mathbb F_2$), simultaneously optimizing both asymptotic circuit size and degree. - We simplify and improve a recent construction (ITCS 2026) of a family of fast codes with fast duals, both meeting the Gilbert-Varshamov bound. Unlike the previous construction, our construction has negligible failure probability, can accommodate general fields and rates, supports a systematic encoding, and admits fast universal encoders. - We strengthen the above to support stronger random-like properties, such as optimal combinatorial list-decoding. This is achieved by constructing, for any constant $t$, a family of fast linear functions that map any $t$ linearly independent inputs to uniform and statistically independent outputs. Prior to our work, this was only known for $t=1$. We demonstrate the usefulness of the above results to cryptography. This includes the first nontrivial protocols for perfectly secure multiparty computation whose circuit complexity scales linearly with the number of parties, as well as protocols for computing encrypted matrix-vector products with optimal asymptotic circuit complexity.

Related papers

• Near-optimal synthesis of non-Gaussian phase gates via qubit-oscillator Rabi control [10.877976778339495]
  We develop an efficient qubit-oscillator Rabi synthesis scheme for phase gates.<n>We show that a degree-(R) phase gate can be approximated by an analytically constructed Rabi sequence with total time.
  arXiv  Detail & Related papers  (2026-09-08T17:53:18Z)
• Computational aspects of the Volterra Signature [0.0]
  We introduce efficient algorithms for the Volterra signature kernel.<n>All algorithms are implemented in the publicly available JAX-based package "tensordev"<n>We show that the number of factors in matrix-valued kernels of the form $K(t,s)=sum_p k_p(t-s)A_p$ do not increase the complexity in $J$ and $N$.
  arXiv  Detail & Related papers  (2026-05-18T13:46:47Z)
• Asymptotically Optimal Quantum Circuits for Comparators and Incrementers [2.488003578430483]
  We present quantum circuits for comparison and increment operations that achieve anally optimal gate count of $(n)$ and depth of $(log n)$ over the Clifford+Toffoli gate set.<n>We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count.
  arXiv  Detail & Related papers  (2026-03-13T11:41:14Z)
• Explicit Block Encodings of Discrete Laplacians with Mixed Boundary Conditions [45.88028371034407]
  Block encoding provides the standard method for accessing matrix data within quantum circuits.<n>We present a unified framework for efficiently block encoding finite-difference discretizations of the Laplacian.
  arXiv  Detail & Related papers  (2026-03-12T19:35:16Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Block Encoding Linear Combinations of Pauli Strings Using the Stabilizer Formalism [0.0]
  We introduce a novel method for constructing quantum circuits that block encode linear combinations of Pauli strings.<n>We present four concrete examples and use numerical simulations to compare our method's circuit complexity with that of the Linear Combination of Unitaries (LCU) approach.
  arXiv  Detail & Related papers  (2026-01-09T11:41:46Z)
• Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations [1.1694898979785655]
  We present optimized quantum circuits for multiplication and division operations.<n>Our ancilla-free GF multiplication circuit has the gate count complexity of $O(mlog3)$.<n>We demonstrate practical advantages for cryptographically relevant values of $m$, including reductions in both CNOT and Toffoli gate counts.
  arXiv  Detail & Related papers  (2025-11-25T18:43:08Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose $Zotimes n$ exponentials of arbitrary length into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions.<n>We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
  Despite being a key bottleneck in many machine learning tasks, the cost of solving large linear systems has proven challenging to quantify.<n>We consider a fine-grained notion of complexity for solving linear systems, which is motivated by applications where the data exhibits low-dimensional structure.<n>We give a algorithm based on the Sketch-and-Project paradigm, that solves the linear system $Ax = b$, that is, finds $barx$ such that $|Abarx - b| le epsilon |b|$, in time
  arXiv  Detail & Related papers  (2024-05-09T14:56:49Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.