Zero-Knowledge Proofs
Succinct Homomorphic Secret Sharing (HSS) Explained
October 25, 2026
13 mins read
Succinct homomorphic secret sharing makes shares smaller than the inputs they hide. See how the 2024 paper builds it and what it enables for VOLE and MPC.
Succinct homomorphic secret sharing is a way for two parties to compute on private data split between them, where the pieces each party holds are smaller than the data they hide. In homomorphic secret sharing (HSS), each party holds a share of the data and computes on that share locally, so neither sees the data itself; "homomorphic" means the computation on shares gives shares of the real result. In the succinct version, the shares for part of the inputs grow sublinearly (slower than the number of inputs), not linearly. Damiano Abram, Lawrence Roy and Peter Scholl of Aarhus University introduced it in "Succinct Homomorphic Secret Sharing" (EUROCRYPT 2024; the extended version is Cryptology ePrint Archive 2024/814). This article walks through what the paper builds and what it enables.
I. General View
Background and Motivation
Homomorphic Secret Sharing (HSS) represents a powerful cryptographic technique that allows multiple parties to collaboratively compute functions over their private inputs without revealing the inputs themselves. The essence of HSS is similar to homomorphic encryption, but instead of a single server performing computations on encrypted data, multiple parties each hold a share of the data and perform computations on these shares. This distributed approach offers enhanced privacy and security.
The motivation for succinct HSS stems from the need to optimize communication and storage. Traditional HSS schemes often involve share sizes that grow linearly with the input size, which can be a significant burden in large-scale applications. By introducing succinct HSS, where the share size is sublinear in the number of inputs, we aim to reduce this overhead and make HSS more practical for real-world scenarios.
Related Work
The concept of HSS was first introduced by Boyle, Gilboa, and Ishai in 2016, who demonstrated how to construct two-party HSS for branching programs based on the decisional Diffie-Hellman (DDH) assumption. This initial work opened the door to a new realm of secure multi-party computation, bypassing the need for fully homomorphic encryption (FHE) and achieving significant communication efficiency. For background on FHE itself, see our beginner's guide to fully homomorphic encryption.
Since then, several advancements have been made in the field. For example, new constructions based on different mathematical assumptions have been proposed, including Paillier encryption and the Damgård-Jurik cryptosystem, which offer alternative approaches to HSS with improved correctness and efficiency. Additionally, HSS techniques have been applied to various cryptographic primitives, such as trapdoor hash functions, correlated pseudorandomness, and more.
In this work, they make several key contributions to the field of succinct HSS:
-
Succinct HSS for Branching Programs: We construct succinct, two-party HSS for branching programs using various cryptographic assumptions, including decisional composite residuosity, a DDH-like assumption in class groups, and learning with errors with a superpolynomial modulus-to-noise ratio.
-
Bilinear HSS and Succinct VOLE: We develop a form of HSS for bilinear functions, enabling succinct vector oblivious linear evaluation (VOLE). This construction allows two parties to share a vector and a scalar and compute the product with sublinear communication.
-
Applications of Succinct HSS: We demonstrate several applications of our succinct HSS constructions, including batch multi-party distributed point functions (DPFs) and sublinear multi-party computation (MPC). These applications showcase the practicality and efficiency gains of our approach.
If you want to see why Zero-Knowledge Proofs are useful, we covered that topic here: When are Zero-Knowledge Proofs Useful?
II. Preliminaries and Construction
Homomorphic Secret Sharing (HSS)
Homomorphic Secret Sharing (HSS) is a technique that allows multiple parties to share and compute on secret data without revealing the data itself. The computation is performed on the shares, and the result is also shared among the parties. This concept can be seen as a distributed form of homomorphic encryption. In traditional homomorphic encryption, a single entity holds the encrypted data and performs computations on it. In HSS, however, the data is split into shares, and each party holds a share, enabling collaborative computation while maintaining privacy.
Mathematical Assumptions
Our constructions of succinct HSS rely on several key cryptographic assumptions:
-
Decisional Composite Residuosity (DCR): This assumption is related to the difficulty of distinguishing between certain residues modulo a composite number. It underpins many cryptographic schemes, including Paillier encryption.
-
Quadratic Residuosity (QR): This assumption concerns the difficulty of determining whether a number is a quadratic residue modulo a composite number. It is used in various cryptographic protocols.
-
DDH-like Assumption in Class Groups: This assumption is similar to the decisional Diffie-Hellman (DDH) assumption but applied in the context of class groups, which are algebraic structures used in cryptography.
-
Learning with Errors (LWE): This assumption involves the hardness of solving linear equations with noise. It is a cornerstone of modern cryptography and is used in many homomorphic encryption and HSS schemes. We use a variant with a superpolynomial modulus-to-noise ratio for our constructions.
Succinct HSS for Branching Programs
We construct succinct, two-party HSS for branching programs, a type of computational model that can represent a wide range of functions. In our succinct HSS scheme, a subset of the inputs can be shared with a share size that is sublinear in the number of inputs. This is a significant improvement over traditional HSS schemes, where the share size is typically linear in the input size.
Branching programs are particularly useful because they can represent any log-space computation, which includes many practical computations. Our construction leverages the mathematical assumptions mentioned above to achieve succinctness and efficiency.
Bilinear HSS and Succinct VOLE
Our work extends to the construction of bilinear HSS, which allows two parties to compute bilinear maps with sublinear communication. In this setting, one party holds a vector, and the other party holds a matrix. The goal is to obtain shares of the product of the matrix and the vector using only a single round of interaction.
This construction leads to the development of succinct vector oblivious linear evaluation (VOLE). In succinct VOLE, two parties can share a vector and a scalar and compute the product with communication complexity that is sublinear in the size of the vector. This primitive is crucial for various cryptographic protocols, such as zero-knowledge proofs and private set intersection.
Our succinct HSS constructions for bilinear functions and VOLE are based on the same mathematical assumptions as our branching program construction. We show that these constructions can be instantiated with different cryptographic assumptions, providing flexibility and robustness in various settings.
The preliminaries and construction of succinct HSS lay the foundation for understanding the efficiency gains and practical applications of our schemes. By leveraging well-established mathematical assumptions and extending HSS to new computational models, we provide a robust framework for secure and efficient multi-party computation.
III. Applications of Succinct HSS
Succinct Vector Oblivious Linear Evaluation (VOLE)
One of the primary applications of our succinct HSS construction is in achieving succinct Vector Oblivious Linear Evaluation (VOLE). In this setting, two parties, Alice and Bob, can efficiently share and compute on vectors and scalars. Specifically, Alice holds a vector, while Bob holds a scalar. The goal is for Alice and Bob to obtain secret shares of the vector multiplied by the scalar, with the total communication being sublinear in the size of the vectors.
Our construction achieves this by allowing the parties to share the vectors and scalars in such a way that the communication complexity remains sublinear. This is a significant improvement over traditional methods, which often require linear communication complexity. This succinct VOLE can be used in various cryptographic protocols, including designated-verifier zero-knowledge proofs and private set intersection.
Batch, Multi-Party Distributed Point Functions (DPFs)
Another crucial application of succinct HSS is in the construction of batch, multi-party Distributed Point Functions (DPFs).
In a distributed setting, the goal is to distribute shares of a point function to multiple parties such that they can locally compute shares of the function's output for any input.
Using our succinct HSS constructions, we can efficiently distribute shares of multiple point functions among a large number of parties. Our protocol allows the communication complexity to be sublinear in the number of distributed point functions, making it highly efficient. This application is particularly useful for generating pseudorandom correlations and other cryptographic primitives that require distributed point functions.
Sublinear MPC for Any Number of Parties
Our succinct HSS constructions also enable the development of sublinear Multi-Party Computation (MPC) protocols. For the basics of MPC, see our introduction to multi-party computation and our post on MPC with information-theoretic techniques. Traditional MPC protocols often suffer from high communication complexity, which can be a significant bottleneck, especially when the number of parties or the size of the computation increases.
We present two new constructions for MPC with sublinear communication complexity:
-
General Layered Boolean Circuits: For arbitrary layered Boolean circuits of size s, our protocol achieves a total communication complexity of O(N·s / log log s), where N is the number of parties.
-
Sufficiently Wide Layered Boolean Circuits: For sufficiently wide layered Boolean circuits, our protocol achieves a total communication complexity of O(N·s / log s). This further reduces the communication overhead and makes our protocol highly efficient for large-scale computations.
These sublinear MPC protocols are achieved by leveraging our succinct HSS constructions and optimizing the communication patterns among the parties. The result is a highly efficient and scalable MPC protocol that can be used in a wide range of applications, from secure voting systems to privacy-preserving data analysis.
IV. Practical Considerations and Efficiency
When implementing and evaluating succinct Homomorphic Secret Sharing (HSS) schemes, several practical considerations come into play. Ensuring that the theoretical benefits translate into real-world performance improvements requires careful attention to implementation details, efficiency, and comparison with existing methods. In this section, we delve into these aspects to provide a comprehensive view of the practical viability of our succinct HSS constructions.
Implementation Details
Implementing succinct HSS schemes involves several critical steps, each requiring careful design and optimization to ensure efficiency and security. The key components include:
-
Key Generation: The process of generating keys must be efficient and secure. This typically involves generating cryptographic keys based on the chosen mathematical assumptions (e.g., DCR, QR, LWE). Efficient key generation algorithms are essential to minimize the setup time and ensure that the scheme can be deployed in practice.
-
Share Generation: Once the keys are generated, the input data must be split into shares. For succinct HSS, this step is crucial as it determines the overall communication complexity. The shares must be generated in a way that ensures they are smaller than the original input data while maintaining the necessary security properties.
-
Homomorphic Evaluation: The core of HSS lies in the ability to perform computations on the shares without revealing the underlying data. Implementing efficient homomorphic evaluation algorithms is essential to ensure that the computations can be performed quickly and securely.
-
Share Combination: After the homomorphic evaluation, the resulting shares must be combined to obtain the final result. This step should be efficient and should not compromise the security of the scheme.
Performance Evaluation
The paper's results are theoretical: it gives constructions and asymptotic communication bounds, and it does not report an implementation, benchmarks or runtime measurements. Concrete performance remains to be measured by future implementation work.
Comparison with Previous Works
To provide a comprehensive view of the efficiency gains achieved by our succinct HSS constructions, we compared our schemes with existing HSS methods. The comparison focused on several key aspects:
-
Share Size: Traditional HSS schemes typically have share sizes that grow linearly with the input size. In contrast, our succinct HSS constructions achieve sublinear share sizes, resulting in significant reductions in communication overhead. This makes our schemes more suitable for large-scale applications where communication costs are a critical factor.
-
Communication Complexity: Our succinct HSS schemes consistently outperform traditional methods in terms of communication complexity. By achieving sublinear communication complexity, our schemes reduce the amount of data exchanged between the parties, making them more practical for real-world deployment.
Security Considerations
The paper presents its results in the semi-honest security model: the parties follow the protocol, and security means they learn nothing beyond their output. It notes that malicious security could be reached with communication-preserving compilers based on succinct zero-knowledge arguments, but it does not develop them. The schemes rest on the cryptographic assumptions listed above.
V. Future Work
Exploring future avenues for research and development in succinct Homomorphic Secret Sharing (HSS) opens up exciting possibilities to enhance efficiency, security, and applicability across various domains. In this section, we outline potential directions for advancing the field and addressing current limitations.
Summary of Contributions
Before delving into future prospects, it's essential to summarize the key contributions of our work in succinct HSS. We have introduced novel schemes that achieve sublinear communication complexity and reduced share sizes compared to traditional HSS methods. Our constructions leverage cryptographic assumptions like DCR, QR, and LWE to enable efficient distributed computations while maintaining strong security guarantees.
Implications
The implications of our succinct HSS constructions extend beyond theoretical advancements to practical applications in cryptography and distributed computing. By reducing communication overhead and computation time, our schemes pave the way for scalable and secure solutions in multi-party computation, privacy-preserving protocols, and decentralized systems.
Open Problems and Research Directions
Moving forward, several open problems and research directions merit exploration:
-
Improving Efficiency: Despite significant reductions in communication complexity, there is scope to further optimize the efficiency of our succinct HSS schemes. Future research could focus on refining algorithms for key generation, share generation, and homomorphic evaluation to achieve even faster computation times and lower resource utilization.
-
Enhancing Security Assumptions: While our schemes are based on established cryptographic assumptions, such as DCR and LWE, exploring new or enhanced security assumptions could strengthen the resilience of succinct HSS against emerging threats. Investigating post-quantum secure primitives or adapting existing assumptions to different computational models could enhance the robustness of our constructions.
-
Scaling to Complex Computations: Extending succinct HSS to support complex computations beyond linear and branching programs presents a significant challenge. Future work could explore techniques to generalize our constructions for non-linear functions, arbitrary circuits, or applications requiring richer computational capabilities.
-
Practical Deployments: Real-world deployment of succinct HSS schemes requires considerations beyond theoretical advancements. Addressing practical challenges such as interoperability with existing cryptographic frameworks, integration into distributed systems, and compliance with regulatory requirements will be crucial for widespread adoption.
-
Exploring New Applications: Investigating novel applications of succinct HSS in emerging domains such as blockchain technology, machine learning over encrypted data, and secure data analytics could uncover new use cases and drive innovation in cryptographic protocols.
Conclusion
The development of succinct Homomorphic Secret Sharing represents a significant step towards efficient and secure distributed computation. By addressing current challenges and exploring future research directions, we aim to advance the state-of-the-art in cryptographic protocols and empower practical applications in privacy-preserving computing. Our work lays the foundation for continued exploration and innovation in the field, with the potential to shape the future of secure data handling and collaborative computing environments.
HSS keeps data private while parties compute on it. A Zero-Knowledge Proof works on a related goal: it lets someone check that a statement about data is true without seeing the data (see our plain explanation of Zero-Knowledge Proofs). Orochi Network builds zkDatabase, a verifiable database powered by Zero-Knowledge Proofs, built to ensure both data integrity and privacy. It generates a Zero-Knowledge Proof for every operation, proving each data change was done correctly.
Explore zkDatabase to see how it keeps off-chain data private and checkable.
Related toZero-Knowledge Proofs
