Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Simplified PIR and CDS Protocols and Improved Linear Secret-Sharing Schemes

Bar Alon, Amos Beimel, Or Lasri

Published Dec 1, 2025• 4 citations
Publisher
DOI
10.1007/978-3-032-12293-3_12

Related papers

Linear Secret-Sharing Schemes for Forbidden Graph Access Structures

Amos Beimel, Oriol Farràs, Yuval Mintz +1 more

A secret-sharing scheme realizes the forbidden graph access structure determined by a graph$G=(V,E)$if the parties are the vertices of the graph and the subsets that can reconstruct the secret are the pairs of vertices in$E$(i.e., the edges) and the subsets of at least three vertices. Secret-sharing schemes for forbidden graph access structures defined by bipartite graphs are equivalent to conditional disclosure of secrets (CDS) protocols. We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes, which are schemes in which the secret can be reconstructed from the shares by a linear mapping. We provide efficient constructions and lower bounds on the share size of linear secret-sharing schemes for sparse and very dense graphs, closing the gap between upper and lower bounds. Given a sparse (resp. very dense) graph with$n$vertices and at most$n^{1+\beta }$edges (resp. at least$\binom {n}{2} - n^{1+\beta }$edges), for some$0 \leq \beta < 1$, we construct a linear secret-sharing scheme realizing its forbidden graph access structure with total share size$\tilde {O} (n^{1+\beta /2})$. Furthermore, we construct linear secret-sharing schemes realizing these access structures in which the size of each share is$\tilde {O} (n^{1/4+\beta /4})$. We also provide constructions achieving different trade-offs between the size of each share and the total share size. We prove that almost all forbidden graph access structures require linear secret-sharing schemes with total share size$\Omega (n^{3/2})$; this shows that the construction of Gay, Kerenidis, and Wee [CRYPTO 2015] is optimal. Furthermore, we show that for every$0 \leq \beta < 1$there exist a graph with at most$n^{1+\beta }$edges and a graph with at least$\binom {n}{2}-n^{1+\beta }$edges such that the total share size in any linear secret-sharing scheme realizing the associated forbidden graph access structures is$\Omega (n^{1+\beta /2})$. Finally, we show that for every$0 \leq \beta < 1$there exist a graph with at most$n^{1+\beta }$edges and a graph with at least$\binom {n}{2}-n^{1+\beta }$edges such that the size of the share of at least one party in any linear secret-sharing scheme realizing these forbidden graph access structures is$\Omega (n^{1/4+\beta /4})$. This shows that our constructions are optimal (up to poly-logarithmic factors).

IEEE Transactions on Information Theory•Dec 6, 2021•7 citations

Multi-linear Secret-Sharing Schemes

Amos Beimel, Aner Ben-Efraim, Carles Padró +1 more

Lecture notes in computer science•Jan 1, 2014•36 citations

Σ-private private information retrieval protocols

Zhang Zi

We pose the definition ofΣ-private private information retrieval(PIR)protocol,and then construct a Σ-private PIR protocol based on verifiable secret sharing(VSS)scheme on general access structure.We also construct an efficient robustΣ-private PIR protocol based on robust multiplication protocol and the database is also secure.The corresponding communication complexity is dependent on the size of the access structure and is efficient for minority of servers.

Journal of the Graduate School of the Chinese Academy of Sciences•Jan 1, 2011•0 citations

Improved Polynomial Secret-Sharing Schemes

Amos Beimel, Oriol Farràs, Or Lasri

Lecture notes in computer science•Jan 1, 2023•5 citations

Efficient Construction of Secure Multiparty Computation Realizing Practical Functionality

礼央 江利口

Secure multiparty computation (MPC) is a fundamental cryptographic primitive for a set of players to interactively compute a function without revealing their private inputs.MPC is of theoretical and practical importance due to its many interesting applications including voting, sealed-bid auctions and privacy-preserving machine learning.It has been an active research area in cryptography and many different approaches have been proposed to enhance security, functionality and efficiency in the literature.In particular, there are general constructions proving the existence of MPC for arbitrary functions under a set of desirable security notions.However, these general results do not give a satisfactory solution to constructing concrete protocols that are efficient enough to use in practice.It is therefore more effective to give concrete and efficient constructions of MPC protocols tailored to specific functionalities and security notions required in practical applications.In this thesis, we study different approaches to realize efficient MPC for functionalities of practical importance with enhanced security notions including non-threshold adversary structures and malicious security.We attain improvement in communication and round complexity by focusing on specific classes of functions or limited but still non-threshold adversary structures.The main contributions of this thesis consist of five parts, which concern the following specific MPC tasks: non-interactive MPC (NIMPC) for symmetric functions and linear classifiers, homomorphic secret sharing (HSS) for low-degree polynomials, verifiably multiplicative secret sharing (VMSS), private information retrieval (PIR), and distributed noise generation for differential privacy.Concretely, we first propose efficient constructions of NIMPC protocols tailored to symmetric functions and linear classifiers.Our protocols improve the best-known communication complexity of existing protocols.In addition, we reveal that a previously proposed method to enhance security of NIMPC does not satisfy specified security requirements and we also fix the problem.Secondly, we propose constructions of HSS schemes that tolerate multipartite and general adversary structures assuming homomorphic encryption.Our schemes support parallel evaluation of a single low-degree polynomial and hence achieve better communication complexity than if we simply execute the previous HSS schemes in parallel.Thirdly, we present VMSS schemes tolerating multipartite adversary structures.Our schemes have smaller communication complexity than those obtained from the previous constructions applicable to general adversary structures.In the fourth part, we study the optimal communication complexity of error-correcting PIR.We asymptotically characterize it as a function of the database size and as a corollary, obtain more communication-efficient error-correcting PIR schemes than the previous ones.Finally, we provide three kinds of MPC protocols for generating noise drawn from probability distributions providing differential privacy.We improve the round or communication complexity of the previous protocols for distributed noise generation.We also extend our protocols so that they provide differential privacy against malicious adversaries.

•Mar 23, 2023•0 citations

Secret-Sharing Schemes: A Survey

Amos Beimel

Lecture notes in computer science•Jan 1, 2011•708 citations
A secret-sharing scheme realizes the forbidden graph access structure determined by a graphG=(V,E)G=(V,E)G=(V,E)if the parties are the vertices of the graph and the subsets that can reconstruct the secret are the pairs of vertices inEEE(i.e., the edges) and the subsets of at least three vertices. Secret-sharing schemes for forbidden graph access structures defined by bipartite graphs are equivalent to conditional disclosure of secrets (CDS) protocols. We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes, which are schemes in which the secret can be reconstructed from the shares by a linear mapping. We provide efficient constructions and lower bounds on the share size of linear secret-sharing schemes for sparse and very dense graphs, closing the gap between upper and lower bounds. Given a sparse (resp. very dense) graph withnnnvertices and at mostn1+βn^{1+\beta }n1+βedges (resp. at least(n2)−n1+β\binom {n}{2} - n^{1+\beta }(2n​)−n1+βedges), for some0≤β<10 \leq \beta < 10≤β<1, we construct a linear secret-sharing scheme realizing its forbidden graph access structure with total share sizeO~(n1+β/2)\tilde {O} (n^{1+\beta /2})O~(n1+β/2). Furthermore, we construct linear secret-sharing schemes realizing these access structures in which the size of each share isO~(n1/4+β/4)\tilde {O} (n^{1/4+\beta /4})O~(n1/4+β/4). We also provide constructions achieving different trade-offs between the size of each share and the total share size. We prove that almost all forbidden graph access structures require linear secret-sharing schemes with total share sizeΩ(n3/2)\Omega (n^{3/2})Ω(n3/2); this shows that the construction of Gay, Kerenidis, and Wee [CRYPTO 2015] is optimal. Furthermore, we show that for every0≤β<10 \leq \beta < 10≤β<1there exist a graph with at mostn1+βn^{1+\beta }n1+βedges and a graph with at least(n2)−n1+β\binom {n}{2}-n^{1+\beta }(2n​)−n1+βedges such that the total share size in any linear secret-sharing scheme realizing the associated forbidden graph access structures isΩ(n1+β/2)\Omega (n^{1+\beta /2})Ω(n1+β/2). Finally, we show that for every0≤β<10 \leq \beta < 10≤β<1there exist a graph with at mostn1+βn^{1+\beta }n1+βedges and a graph with at least(n2)−n1+β\binom {n}{2}-n^{1+\beta }(2n​)−n1+βedges such that the size of the share of at least one party in any linear secret-sharing scheme realizing these forbidden graph access structures isΩ(n1/4+β/4)\Omega (n^{1/4+\beta /4})Ω(n1/4+β/4). This shows that our constructions are optimal (up to poly-logarithmic factors).
Secure multiparty computation (MPC) is a fundamental cryptographic primitive for a set of players to interactively compute a function without revealing their private inputs.MPC is of theoretical and practical importance due to its many interesting applications including voting, sealed-bid auctions and privacy-preserving machine learning.It has been an active research area in cryptography and many different approaches have been proposed to enhance security, functionality and efficiency in the literature.In particular, there are general constructions proving the existence of MPC for arbitrary functions under a set of desirable security notions.However, these general results do not give a satisfactory solution to constructing concrete protocols that are efficient enough to use in practice.It is therefore more effective to give concrete and efficient constructions of MPC protocols tailored to specific functionalities and security notions required in practical applications.In this thesis, we study different approaches to realize efficient MPC for functionalities of practical importance with enhanced security notions including non-threshold adversary structures and malicious security.We attain improvement in communication and round complexity by focusing on specific classes of functions or limited but still non-threshold adversary structures.The main contributions of this thesis consist of five parts, which concern the following specific MPC tasks: non-interactive MPC (NIMPC) for symmetric functions and linear classifiers, homomorphic secret sharing (HSS) for low-degree polynomials, verifiably multiplicative secret sharing (VMSS), private information retrieval (PIR), and distributed noise generation for differential privacy.Concretely, we first propose efficient constructions of NIMPC protocols tailored to symmetric functions and linear classifiers.Our protocols improve the best-known communication complexity of existing protocols.In addition, we reveal that a previously proposed method to enhance security of NIMPC does not satisfy specified security requirements and we also fix the problem.Secondly, we propose constructions of HSS schemes that tolerate multipartite and general adversary structures assuming homomorphic encryption.Our schemes support parallel evaluation of a single low-degree polynomial and hence achieve better communication complexity than if we simply execute the previous HSS schemes in parallel.Thirdly, we present VMSS schemes tolerating multipartite adversary structures.Our schemes have smaller communication complexity than those obtained from the previous constructions applicable to general adversary structures.In the fourth part, we study the optimal communication complexity of error-correcting PIR.We asymptotically characterize it as a function of the database size and as a corollary, obtain more communication-efficient error-correcting PIR schemes than the previous ones.Finally, we provide three kinds of MPC protocols for generating noise drawn from probability distributions providing differential privacy.We improve the round or communication complexity of the previous protocols for distributed noise generation.We also extend our protocols so that they provide differential privacy against malicious adversaries.