Fast Bounded-Independence Functions and Their Duals

Computer Science > Cryptography and Security [Submitted on 5 Jun 2026] Fast Bounded-Independence Functions and Their Duals Martijn Brehm, Yuval Ishai, Nicolas Resch 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. Comments: Full version of paper to appear in ITC 2026. 34 pages Subjects: Cryptography and Security (cs.CR); Information Theory (cs.IT) Cite as: arXiv:2606.07009 [cs.CR]   (or arXiv:2606.07009v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2606.07009 Focus to learn more Submission history From: Nicolas Resch [view email] [v1] Fri, 5 Jun 2026 07:53:04 UTC (39 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-06 Change to browse by: cs cs.IT math math.IT References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)