On the download rate of homomorphic secret sharing

on YouTube ↗24m

" summary

Proves optimal linear HSS for low-degree polynomials with exact rate 1 - d t / k, gives a PIR instantiation with upload cost n^{1/d} and that download rate, and supplies three amplification routes: a black-box rate amplification turning small-server additive HSS into t-private k-server schemes with rate 1 - t/k, a variant achieving rate 1 - 1/Θ(√k) for many evaluations, and a non-linear Slepian-Wolf style compressor that beats 1/3 for 1-out-of-3; constructions use Shamir vs CNF secret shares, regenerating-code ideas and distributed source-coding techniques.

AI-written summary · about

" chapters (10)

1. 0:00Intro
2. 0:14Homomorphic Secret Sharing
3. 2:44Computation on secret shared data
4. 4:37Example
5. 6:02Can we do better for multiple products
6. 8:58Our results III
7. 15:23HSS for l-concatenation
8. 16:00t-private k-server CNF secret sharing
9. 17:03Universality of CNF secret sharing
10. 20:10HSS for degree d polynomials

" related talks

• 44mObfuscation IIIAayush Jain · Lattices: New Cryptographic Capabilities 2020
• 01h 00mSecure Computation 3Peter Scholl · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 35mA Unified Framework for Succinct Garbling from Homomorphic Secret SharingRachel Lin · Secure Computation 2025
• 01h 08mSecure Computation 1Peter Scholl · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 01mCommunication Complexity, Streaming and Computational AssumptionsMoni Naor · Minimal Complexity Assumptions for Cryptography 2023
• 59mDoubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWEDaniel Wichs · Minimal Complexity Assumptions for Cryptography 2023
• 01h 01mCircularity Based IO, Part 1Rafael Pass, Romain Gay · Simons Institute Workshop: New Developments in Obfuscation
• 40mCryptography in Distributed SystemsHamidreza Khoshakhlagh · RSAC 2021