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 SciencesJan 1, 20110 citations

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• 3 citations

Publisher

DOI: 10.1007/978-3-032-12293-3_12

Related papers

Multi-linear Secret-Sharing Schemes

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

Lecture notes in computer scienceJan 1, 201435 citations

Secure Multi-party Protocols Based on Secret-Sharing Techniques Considering Operational Requirements

Kittiphop Phalakarn

Nowadays, computation becomes more advanced, and may require more than one parties to participate.Some examples include e-voting system and privacy-preserving data analytics.One of the main concerns here is privacy.Inputs of these systems must be kept secret.To address this concern, we can construct the systems by using secure multi-party protocols, where several parties with their secret inputs perform joint computations in oblivious ways.Many aspects of the protocols can be further improved towards the usage in reallife applications, considering operational requirements and trade-offs.These operational requirements include efficiency, functionality, security, scalability, and verifiability.This thesis consists of three parts; each part focuses on specific improvements.In the first part, we focus on improving security and efficiency.We consider a homomorphic secret sharing scheme, where a secret input from each party is divided into several shares, each share is sent to different computing server, and the servers can perform some computation locally to get shares of the result.It is obvious that homomorphic secret sharing schemes can be used as secure multi-party protocols with small communication.We found that the existing homomorphic secret sharing scheme with public key of Lai et al. (Asiacrypt 2018) is 1-secure, which means if more than one computing servers try to collude, the security of the system will be compromised.They also proposed a t-secure scheme, but it requires solving NP-hard problem.To improve their security level, we use the idea from the secret sharing scheme of Ito et al.Our scheme also supports any number of computing servers without solving NP-hard problem.Using hyper-graph representation of non-access structures, we prove the maximum polynomial degree that our scheme can support.In addition, we prove correctness and security of the scheme, and propose some possible further improvements.In the second part, we focus on improving scalability and efficiency.Most of the secret sharing schemes, including homomorphic secret sharing, require the number of parties to be fixed in advance.This causes an inconvenience if we want to add more parties later in order to change the security setting or improve availability of the system.One existing variant of secret sharing, called evolving secret sharing, allows any number of parties to join the system at any time.However, it is inefficient to perform computation on this kind of secret sharing.To address this problem, we propose the definition of evolving homomorphic secret sharing, which combines evolving and homomorphic properties together.The scheme iii then supports unbounded number of parties, and allows local computation on shares.In addition to the definition, we propose two concrete schemes.The first scheme realizes evolving disjunctive hierarchical access structure supporting multiplication.The second scheme realizes evolving partially disjunctive hierarchical access structure supporting lowdegree polynomial computation.In the third part, we focus on improving functionality, verifiability, and efficiency.We consider the problem of oblivious deterministic finite automata (DFA) evaluation protocol.In this problem, one party holds a secret string, and the other party holds a secret pattern.The goal of this protocol is to output whether the string matches with the pattern of not without revealing both secret inputs.Most of the existing protocols use several communication rounds and require public key primitives, which can be inefficient.As our contribution, we propose an oblivious conditional disclosure of secrets (CDS) scheme for DFA.It is the first CDS scheme that has a functionality of DFA evaluation.We then use the proposed oblivious CDS scheme as a building block to construct an oblivious DFA evaluation protocol, using a multi-client verifiable computation framework.As a result, our protocol is constant-round, verifiable, and does not require any public key primitives.We also propose a standard CDS scheme for DFA as an independent interest.This thesis is expected to be a step of secure multi-party protocols and secret sharing schemes enhancements towards real-life applications.High level ideas for more improvements are also suggested as future prospects.Nowadays, computation becomes more advanced, and may require more than one parties to participate.Some examples include e-voting system and privacy-preserving data analytics.One of the main concerns here is privacy.Inputs of these systems must be kept secret.To address this concern, we can construct the systems by using secure multi-party protocols, where several parties with their secret inputs perform joint computations in oblivious ways.Many aspects of the protocols can be further improved towards the usage in reallife applications, considering operational requirements and trade-offs.These operational requirements include efficiency, functionality, security, scalability, and verifiability.This thesis consists of three parts; each part focuses on specific improvements.In the first part, we focus on improving security and efficiency.We consider a homomorphic secret sharing scheme, where a secret input from each party is divided into several shares, each share is sent to different computing server, and the servers can perform some computation locally to get shares of the result.It is obvious that homomorphic secret sharing schemes can be used as secure multi-party protocols with small communication.We found that the existing homomorphic secret sharing scheme with public key of Lai et al. (Asiacrypt 2018) is 1-secure, which means if more than one computing servers try to collude, the security of the system will be compromised.They also proposed a t-secure scheme, but it requires solving NP-hard problem.To improve their security level, we use the idea from the secret sharing scheme of Ito et al.Our scheme also supports any number of computing servers without solving NP-hard problem.Using hyper-graph representation of non-access structures, we prove the maximum polynomial degree that our scheme can support.In addition, we prove correctness and security of the scheme, and propose some possible further improvements.In the second part, we focus on improving scalability and efficiency.Most of the secret sharing schemes, including homomorphic secret sharing, require the number of parties to be fixed in advance.This causes an inconvenience if we want to add more parties later in order to change the security setting or improve availability of the system.One existing variant of secret sharing, called evolving secret sharing, allows any number of parties to join the system at any time.However, it is inefficient to perform computation on this kind of secret sharing.To address this problem, we propose the definition of evolving homomorphic secret sharing, which combines evolving and homomorphic properties together.The scheme iii then supports unbounded number of parties, and allows local computation on shares.In addition to the definition, we propose two concrete schemes.The first scheme realizes evolving disjunctive hierarchical access structure supporting multiplication.The second scheme realizes evolving partially disjunctive hierarchical access structure supporting lowdegree polynomial computation.In the third part, we focus on improving functionality, verifiability, and efficiency.We consider the problem of oblivious deterministic finite automata (DFA) evaluation protocol.In this problem, one party holds a secret string, and the other party holds a secret pattern.The goal of this protocol is to output whether the string matches with the pattern of not without revealing both secret inputs.Most of the existing protocols use several communication rounds and require public key primitives, which can be inefficient.As our contribution, we propose an oblivious conditional disclosure of secrets (CDS) scheme for DFA.It is the first CDS scheme that has a functionality of DFA evaluation.We then use the proposed oblivious CDS scheme as a building block to construct an oblivious DFA evaluation protocol, using a multi-client verifiable computation framework.As a result, our protocol is constant-round, verifiable, and does not require any public key primitives.We also propose a standard CDS scheme for DFA as an independent interest.This thesis is expected to be a step of secure multi-party protocols and secret sharing schemes enhancements towards real-life applications.High level ideas for more improvements are also suggested as future prospects.

Sep 22, 20220 citations

Linear multi-secret sharing schemes

Liangliang Xiao

Science in China Series F Information SciencesJan 1, 200511 citations

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).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 TheoryDec 6, 20216 citations

Improved Polynomial Secret-Sharing Schemes

Amos Beimel, Oriol Farràs, Or Lasri

Lecture notes in computer scienceJan 1, 20234 citations

Σ-private private information retrieval protocols

Zhang Zi

Journal of the Graduate School of the Chinese Academy of SciencesJan 1, 20110 citations

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).