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

IEEE Access

Efficient Threshold Function Secret Sharing With Information-Theoretic Security

Jinglong Luo, Liang Feng Zhang, Fuchun Lin, Changlu Lin

Published Jan 1, 2020• 7 citations
Publisher

Abstract

Function secret sharing (FSS) is a cryptographic primitive that is introduced by Boyle et al. (Eurocrypt 2015), motivated by application scenarios involving private access to large distributed data while minimising the overhead of communication, for example, private information retrieval. Informally, an n-party FSS scheme splits a function f into n functions f1,...,fnsuch that f = f1+...+ fnand every strict subset of the function shares hide f . Most of the known FSS constructions only have computational hiding, namely, the hiding property holds only against a computationally bounded adversary. We consider information-theoretic hiding in this work while allowing f to be recovered from t function shares and correspondingly, any (t - 1) function shares unconditionally hide f . Call it (t, n)-threshold function secret sharing ((t, n)-TFSS for short). Using information-theoretic tools and through a series of optimizations, we show that our (t, n)-TFSS have better performance than FSS in terms of communication complexity, a criterion that measures the efficiency of such protocols. Specifically, a (t, n)-TFSS scheme with communication complexity O(l) is designed in this paper and it is better than the existing FSS schemes with lowest communication complexity O(λl), where λ is the length of pseudo-random generator's seeds. In addition, the (t, n)-TFSS have an extra robustness property in the sense that even if up to (n - t) function shares are not available, the protocol still computes the function value at a given point correctly.

DOI
10.1109/access.2019.2963677

Related papers

Towards Efficient Information-Theoretic Function Secret Sharing

Wen Ming Li, Liang Feng Zhang

A (t, r)-function secret sharing ((t, r)-FSS) scheme allows a dealer to secret-share a functionf among r parties as r secret keys k1, ... , krsuch that for any input x the parties can compute r output shares that allow the reconstruction of f (x) but any ≤ t of the parties cannot learn any information aboutf. FSS schemes for point functions have been constructed under the name of distributed point functions (DPFs). The existing DPFs are computationally secure and based on the existence of PRGs or OWFs. As a result, the protocols where DPFs work as building blocks are computationally secure as well. In this paper, we study information-theoretically secure (t, r)-FSS (called (t, r)-itFSS) and propose a generic transformation from information-theoretic private information retrieval (PIR) schemes to itFSS schemes for point functions. We measure the efficiency of itFSS with its communication complexity, which can be defined as the total length of the secret keys and the output shares, maximized over the choices off and x. By instantiating the generic transformation, we obtain (t, r)-itFSS schemes for a variety of choices of (t, r), which have sublinear (in the functions' domain size) communication complexity. How to make sure that the parties' shares of f (x) do not reveal more information than what needed to computef(x) is an interesting problem. An itFSS with this property is called function-private. In this paper, we also define a parameter called the mutual rate of itFSS in order to measure the amount of information that will be leaked by the parties' output shares. We calculate the mutual rates for several specific itFSS schemes. We also define computational function privacy and propose a 2-party itFSS scheme with computational function privacy.

IEEE Access•Jan 1, 2020•3 citations

Broadcast Secret-Sharing, Bounds and Applications

Ivan Damgård, Kasper Green Larsen, Sophia Yakoubov

Consider a sender 𝒮 and a group of n recipients. 𝒮 holds a secret message 𝗆 of length l bits and the goal is to allow 𝒮 to create a secret sharing of 𝗆 with privacy threshold t among the recipients, by broadcasting a single message 𝖼 to the recipients. Our goal is to do this with information theoretic security in a model with a simple form of correlated randomness. Namely, for each subset 𝒜 of recipients of size q, 𝒮 may share a random key with all recipients in 𝒜. (The keys shared with different subsets 𝒜 must be independent.) We call this Broadcast Secret-Sharing (BSS) with parameters l, n, t and q. Our main question is: how large must 𝖼 be, as a function of the parameters? We show that (n-t)/q l is a lower bound, and we show an upper bound of ((n(t+1)/(q+t)) -t)l, matching the lower bound whenever t = 0, or when q = 1 or n-t. When q = n-t, the size of 𝖼 is exactly l which is clearly minimal. The protocol demonstrating the upper bound in this case requires 𝒮 to share a key with every subset of size n-t. We show that this overhead cannot be avoided when 𝖼 has minimal size. We also show that if access is additionally given to an idealized PRG, the lower bound on ciphertext size becomes (n-t)/q λ + l - negl(λ) (where λ is the length of the input to the PRG). The upper bound becomes ((n(t+1))/(q+t) -t)λ + l. BSS can be applied directly to secret-key threshold encryption. We can also consider a setting where the correlated randomness is generated using computationally secure and non-interactive key exchange, where we assume that each recipient has an (independently generated) public key for this purpose. In this model, any protocol for non-interactive secret sharing becomes an ad hoc threshold encryption (ATE) scheme, which is a threshold encryption scheme with no trusted setup beyond a PKI. Our upper bounds imply new ATE schemes, and our lower bound becomes a lower bound on the ciphertext size in any ATE scheme that uses a key exchange functionality and no other cryptographic primitives.

Leibniz international proceedings in informatics•Jan 1, 2021•1 citation

Intrusion-Resilient Secret Sharing

Stefan Dziembowski, Krzysztof Pietrzak

We introduce a new primitive called intrusion-resilient secret sharing (IRSS), whose security proof exploits the fact that there exist functions which can be efficiently computed interactively using low communication complexity in k, but not in k-1 rounds. IRSS is a means of sharing a secret message amongst a set of players which comes with a very strong security guarantee. The shares in an IRSS are made artificially large so that it is hard to retrieve them completely, and the reconstruction procedure is interactive requiring the players to exchange k short messages. The adversaries considered can attack the scheme in rounds, where in each round the adversary chooses some player to corrupt and some function, and retrieves the output of that function applied to the share of the corrupted player. This model captures for example computers connected to a network which can occasionally he infected by malicious software like viruses, which can compute any function on the infected machine, but cannot sent out a huge amount of data. Using methods from the bounded-retrieval model, we construct an IRSS scheme which is secure against any computationally unbounded adversary as long as the total amount of information retrieved by the adversary is somewhat less than the length of the shares, and the adversary makes at most k-1 corruption rounds (as described above, where k rounds are necessary for reconstruction). We extend our basic scheme in several ways in order to allow the shares sent by the dealer to be short (the players then blow them up locally) and to handle even stronger adversaries who can learn some of the shares completely. As mentioned, there is an obvious connection between IRSS schemes and the fact that there exist functions with an exponential gap in their communication complexity for k and k-1 rounds. Our scheme implies such a separation which is in several aspects stronger than the previously known ones.

Annual Symposium on Foundations of Computer Science•Oct 1, 2007•114 citations

Universal Communication Efficient Quantum Threshold Secret Sharing Schemes

Kaushik Senthoor, Pradeep Kiran Sarvepalli

Quantum secret sharing (QSS) is a cryptographic protocol in which a quantum secret is distributed among a number of parties where some subsets of the parties are able to recover the secret while some subsets are unable to recover the secret. In the standard ((k, n)) quantum threshold secret sharing scheme, any subset of k or more parties out of the total n parties can recover the secret while other subsets have no information about the secret. But recovery of the secret incurs a communication cost of at least k qudits for every qudit in the secret. Recently, a class of communication efficient QSS schemes were proposed which can improve this communication cost to $\frac{d}{{d - k + 1}}$ by contacting d ≥ k parties where d is fixed prior to the distribution of shares. In this paper, we propose a more general class of ((k, n)) quantum secret sharing schemes with low communication complexity. In these schemes the combiner can contact any d parties at the time of recovery where k ≤ d ≤ n. This is the first such class of universal communication efficient quantum threshold schemes.

arXiv:2002.09229•IEEE Information Theory Workshop (ITW)•Apr 11, 2021•6 citations

Intrusion-Resilient Secret Sharing

Stefan Dziembowski, Krzysztof Pietrzak

We introduce a new primitive called intrusion-resilient secret sharing (IRSS), whose security proof exploits the fact that there exist functions which can be efficiently computed interactively using low communication complexity in k, but not in k-1 rounds. IRSS is a means of sharing a secret message amongst a set of players which comes with a very strong security guarantee. The shares in an IRSS are made artificially large so that it is hard to retrieve them completely, and the reconstruction procedure is interactive requiring the players to exchange k short messages. The adversaries considered can attack the scheme in rounds, where in each round the adversary chooses some player to corrupt and some function, and retrieves the output of that function applied to the share of the corrupted player. This model captures for example computers connected to a network which can occasionally he infected by malicious software like viruses, which can compute any function on the infected machine, but cannot sent out a huge amount of data. Using methods from the bounded-retrieval model, we construct an IRSS scheme which is secure against any computationally unbounded adversary as long as the total amount of information retrieved by the adversary is somewhat less than the length of the shares, and the adversary makes at most k-1 corruption rounds (as described above, where k rounds are necessary for reconstruction). We extend our basic scheme in several ways in order to allow the shares sent by the dealer to be short (the players then blow them up locally) and to handle even stronger adversaries who can learn some of the shares completely. As mentioned, there is an obvious connection between IRSS schemes and the fact that there exist functions with an exponential gap in their communication complexity for k and k-1 rounds. Our scheme implies such a separation which is in several aspects stronger than the previously known ones.

Annual Symposium on Foundations of Computer Science•Oct 1, 2007•6 citations

Theory of Communication Efficient Quantum Secret Sharing

Kaushik Senthoor, Pradeep Kiran Sarvepalli

A$((k,n))$quantum threshold secret sharing (QTS) scheme is a quantum cryptographic protocol for sharing a quantum secret among$n$parties such that the secret can be recovered by any$k$or more parties while$k-1$or fewer parties have no information about the secret. Despite extensive research on these schemes, there has been very little study on optimizing the quantum communication cost during recovery. Recently, we initiated the study of communication efficient quantum threshold secret sharing (CE-QTS) schemes. These schemes reduce the communication complexity in QTS schemes by accessing$d>k$parties for recovery; here$d$is fixed ahead of encoding the secret. In contrast to the standard QTS schemes which require$k$qudits for recovering each qudit in the secret, these schemes have a lower communication cost of$\frac {d}{d-k+1}$. In this paper, we further develop the theory of communication efficient quantum threshold schemes. Here, we propose universal CE-QTS schemes which reduce the communication cost for all$d>k$simultaneously. We provide a framework based on ramp quantum secret sharing to construct CE-QTS and universal CE-QTS schemes. We give another construction for universal CE-QTS schemes based on Staircase codes. We derived a lower bound on communication complexity and show that our constructions are optimal. Finally, an information theoretic model is developed to analyse CE-QTS schemes and the lower bound on communication complexity is proved again using this model.

arXiv:2101.12419•IEEE Transactions on Information Theory•Jan 7, 2022•40 citations
Function secret sharing (FSS) is a cryptographic primitive that is introduced by Boyle et al. (Eurocrypt 2015), motivated by application scenarios involving private access to large distributed data while minimising the overhead of communication, for example, private information retrieval. Informally, an n-party FSS scheme splits a function f into n functions f1,...,fnsuch that f = f1+...+ fnand every strict subset of the function shares hide f . Most of the known FSS constructions only have computational hiding, namely, the hiding property holds only against a computationally bounded adversary. We consider information-theoretic hiding in this work while allowing f to be recovered from t function shares and correspondingly, any (t - 1) function shares unconditionally hide f . Call it (t, n)-threshold function secret sharing ((t, n)-TFSS for short). Using information-theoretic tools and through a series of optimizations, we show that our (t, n)-TFSS have better performance than FSS in terms of communication complexity, a criterion that measures the efficiency of such protocols. Specifically, a (t, n)-TFSS scheme with communication complexity O(l) is designed in this paper and it is better than the existing FSS schemes with lowest communication complexity O(λl), where λ is the length of pseudo-random generator's seeds. In addition, the (t, n)-TFSS have an extra robustness property in the sense that even if up to (n - t) function shares are not available, the protocol still computes the function value at a given point correctly.
A (t, r)-function secret sharing ((t, r)-FSS) scheme allows a dealer to secret-share a functionf among r parties as r secret keys k1, ... , krsuch that for any input x the parties can compute r output shares that allow the reconstruction of f (x) but any ≤ t of the parties cannot learn any information aboutf. FSS schemes for point functions have been constructed under the name of distributed point functions (DPFs). The existing DPFs are computationally secure and based on the existence of PRGs or OWFs. As a result, the protocols where DPFs work as building blocks are computationally secure as well. In this paper, we study information-theoretically secure (t, r)-FSS (called (t, r)-itFSS) and propose a generic transformation from information-theoretic private information retrieval (PIR) schemes to itFSS schemes for point functions. We measure the efficiency of itFSS with its communication complexity, which can be defined as the total length of the secret keys and the output shares, maximized over the choices off and x. By instantiating the generic transformation, we obtain (t, r)-itFSS schemes for a variety of choices of (t, r), which have sublinear (in the functions' domain size) communication complexity. How to make sure that the parties' shares of f (x) do not reveal more information than what needed to computef(x) is an interesting problem. An itFSS with this property is called function-private. In this paper, we also define a parameter called the mutual rate of itFSS in order to measure the amount of information that will be leaked by the parties' output shares. We calculate the mutual rates for several specific itFSS schemes. We also define computational function privacy and propose a 2-party itFSS scheme with computational function privacy.
Consider a sender 𝒮 and a group of n recipients. 𝒮 holds a secret message 𝗆 of length l bits and the goal is to allow 𝒮 to create a secret sharing of 𝗆 with privacy threshold t among the recipients, by broadcasting a single message 𝖼 to the recipients. Our goal is to do this with information theoretic security in a model with a simple form of correlated randomness. Namely, for each subset 𝒜 of recipients of size q, 𝒮 may share a random key with all recipients in 𝒜. (The keys shared with different subsets 𝒜 must be independent.) We call this Broadcast Secret-Sharing (BSS) with parameters l, n, t and q. Our main question is: how large must 𝖼 be, as a function of the parameters? We show that (n-t)/q l is a lower bound, and we show an upper bound of ((n(t+1)/(q+t)) -t)l, matching the lower bound whenever t = 0, or when q = 1 or n-t. When q = n-t, the size of 𝖼 is exactly l which is clearly minimal. The protocol demonstrating the upper bound in this case requires 𝒮 to share a key with every subset of size n-t. We show that this overhead cannot be avoided when 𝖼 has minimal size. We also show that if access is additionally given to an idealized PRG, the lower bound on ciphertext size becomes (n-t)/q λ + l - negl(λ) (where λ is the length of the input to the PRG). The upper bound becomes ((n(t+1))/(q+t) -t)λ + l. BSS can be applied directly to secret-key threshold encryption. We can also consider a setting where the correlated randomness is generated using computationally secure and non-interactive key exchange, where we assume that each recipient has an (independently generated) public key for this purpose. In this model, any protocol for non-interactive secret sharing becomes an ad hoc threshold encryption (ATE) scheme, which is a threshold encryption scheme with no trusted setup beyond a PKI. Our upper bounds imply new ATE schemes, and our lower bound becomes a lower bound on the ciphertext size in any ATE scheme that uses a key exchange functionality and no other cryptographic primitives.
We introduce a new primitive called intrusion-resilient secret sharing (IRSS), whose security proof exploits the fact that there exist functions which can be efficiently computed interactively using low communication complexity in k, but not in k-1 rounds. IRSS is a means of sharing a secret message amongst a set of players which comes with a very strong security guarantee. The shares in an IRSS are made artificially large so that it is hard to retrieve them completely, and the reconstruction procedure is interactive requiring the players to exchange k short messages. The adversaries considered can attack the scheme in rounds, where in each round the adversary chooses some player to corrupt and some function, and retrieves the output of that function applied to the share of the corrupted player. This model captures for example computers connected to a network which can occasionally he infected by malicious software like viruses, which can compute any function on the infected machine, but cannot sent out a huge amount of data. Using methods from the bounded-retrieval model, we construct an IRSS scheme which is secure against any computationally unbounded adversary as long as the total amount of information retrieved by the adversary is somewhat less than the length of the shares, and the adversary makes at most k-1 corruption rounds (as described above, where k rounds are necessary for reconstruction). We extend our basic scheme in several ways in order to allow the shares sent by the dealer to be short (the players then blow them up locally) and to handle even stronger adversaries who can learn some of the shares completely. As mentioned, there is an obvious connection between IRSS schemes and the fact that there exist functions with an exponential gap in their communication complexity for k and k-1 rounds. Our scheme implies such a separation which is in several aspects stronger than the previously known ones.
Quantum secret sharing (QSS) is a cryptographic protocol in which a quantum secret is distributed among a number of parties where some subsets of the parties are able to recover the secret while some subsets are unable to recover the secret. In the standard ((k, n)) quantum threshold secret sharing scheme, any subset of k or more parties out of the total n parties can recover the secret while other subsets have no information about the secret. But recovery of the secret incurs a communication cost of at least k qudits for every qudit in the secret. Recently, a class of communication efficient QSS schemes were proposed which can improve this communication cost to dd−k+1\frac{d}{{d - k + 1}}d−k+1d​ by contacting d ≥ k parties where d is fixed prior to the distribution of shares. In this paper, we propose a more general class of ((k, n)) quantum secret sharing schemes with low communication complexity. In these schemes the combiner can contact any d parties at the time of recovery where k ≤ d ≤ n. This is the first such class of universal communication efficient quantum threshold schemes.
We introduce a new primitive called intrusion-resilient secret sharing (IRSS), whose security proof exploits the fact that there exist functions which can be efficiently computed interactively using low communication complexity in k, but not in k-1 rounds. IRSS is a means of sharing a secret message amongst a set of players which comes with a very strong security guarantee. The shares in an IRSS are made artificially large so that it is hard to retrieve them completely, and the reconstruction procedure is interactive requiring the players to exchange k short messages. The adversaries considered can attack the scheme in rounds, where in each round the adversary chooses some player to corrupt and some function, and retrieves the output of that function applied to the share of the corrupted player. This model captures for example computers connected to a network which can occasionally he infected by malicious software like viruses, which can compute any function on the infected machine, but cannot sent out a huge amount of data. Using methods from the bounded-retrieval model, we construct an IRSS scheme which is secure against any computationally unbounded adversary as long as the total amount of information retrieved by the adversary is somewhat less than the length of the shares, and the adversary makes at most k-1 corruption rounds (as described above, where k rounds are necessary for reconstruction). We extend our basic scheme in several ways in order to allow the shares sent by the dealer to be short (the players then blow them up locally) and to handle even stronger adversaries who can learn some of the shares completely. As mentioned, there is an obvious connection between IRSS schemes and the fact that there exist functions with an exponential gap in their communication complexity for k and k-1 rounds. Our scheme implies such a separation which is in several aspects stronger than the previously known ones.
A((k,n))((k,n))((k,n))quantum threshold secret sharing (QTS) scheme is a quantum cryptographic protocol for sharing a quantum secret amongnnnparties such that the secret can be recovered by anykkkor more parties whilek−1k-1k−1or fewer parties have no information about the secret. Despite extensive research on these schemes, there has been very little study on optimizing the quantum communication cost during recovery. Recently, we initiated the study of communication efficient quantum threshold secret sharing (CE-QTS) schemes. These schemes reduce the communication complexity in QTS schemes by accessingd>kd>kd>kparties for recovery; heredddis fixed ahead of encoding the secret. In contrast to the standard QTS schemes which requirekkkqudits for recovering each qudit in the secret, these schemes have a lower communication cost ofdd−k+1\frac {d}{d-k+1}d−k+1d​. In this paper, we further develop the theory of communication efficient quantum threshold schemes. Here, we propose universal CE-QTS schemes which reduce the communication cost for alld>kd>kd>ksimultaneously. We provide a framework based on ramp quantum secret sharing to construct CE-QTS and universal CE-QTS schemes. We give another construction for universal CE-QTS schemes based on Staircase codes. We derived a lower bound on communication complexity and show that our constructions are optimal. Finally, an information theoretic model is developed to analyse CE-QTS schemes and the lower bound on communication complexity is proved again using this model.