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

arXiv:1402.1368 · Designs Codes and Cryptography

On-line secret sharing

László Csirmaz, Gábor Tardos

Published Jul 8, 2011• 18 citations
arXivHTMLPDF
DOI
10.1007/s10623-011-9540-y

Related papers

Unclonable Secret Sharing

Prabhanjan Ananth, Vipul Goyal, Jiahui Liu +1 more

arXiv:2406.11008•Lecture notes in computer science•Dec 8, 2024•5 citations

Locally Reconstructable Non-Malleable Secret Sharing

Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Sruthi Sekar +1 more

Non-malleable secret sharing (NMSS) schemes, introduced by Goyal and Kumar (STOC 2018), ensure that a secret m can be distributed into shares m₁,⋯,m_n (for some n), such that any t (a parameter ≤ n) shares can be reconstructed to recover the secret m, any t-1 shares doesn't leak information about m and even if the shares that are used for reconstruction are tampered, it is guaranteed that the reconstruction of these tampered shares will either result in the original m or something independent of m. Since their introduction, non-malleable secret sharing schemes sparked a very impressive line of research. In this work, we introduce a feature of local reconstructability in NMSS, which allows reconstruction of any portion of a secret by reading just a few locations of the shares. This is a useful feature, especially when the secret is long or when the shares are stored in a distributed manner on a communication network. In this work, we give a compiler that takes in any non-malleable secret sharing scheme and compiles it into a locally reconstructable non-malleable secret sharing scheme. To secret share a message consisting of k blocks of length ρ each, our scheme would only require reading ρ + log k bits (in addition to a few more bits, whose quantity is independent of ρ and k) from each party’s share (of a reconstruction set) to locally reconstruct a single block of the message. We show an application of our locally reconstructable non-malleable secret sharing scheme to a computational non-malleable secure message transmission scheme in the pre-processing model, with an improved communication complexity, when transmitting multiple messages.

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

Anonymous secret sharing schemes

Carlo Blundo, Doug R. Stinson

Discrete Applied Mathematics•Jun 1, 1997•37 citations

Packed Linear Secret Sharing-Based Simultaneous Multiplication and Comparison

Shohei MITA, Kazuki Yoneyama

Performing L pairs of multiplication with known (k, n)-linear secret sharing-based n party multiplication protocols using an (offline) preprocessing by the Beaver multiplication triple requires 2Lk elements of on-line communications where k is the threshold. This paper proposes a simultaneous multiplication protocol for L pairs based on (k, L, n)-packed linear secret sharing. By embedding L secret information into each share using (k, L, n)-packed linear secret sharing, though partial information of secret information is leaked from k - l + 1 shares for 1 ≤ l ≤ L, the proposed protocol can perform L multiplications with 2k elements of online communications. As applications of the proposed simultaneous multiplication protocol, we also introduce a simultaneous comparison protocol and an improvement of the communication cost of Araki et al.'s n party group-wise maximum/minimum value aggregation protocol. For example, when computing the maximum/minimum value of eight 64-bit data, our proposed aggregation protocol can reduce 59.6% of the communication cost.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jun 4, 2026•0 citations

PERFECT SECRET SHARING SCHEMES

K.G. Parvatov

PRIKLADNAYa DISKRETNAYa MATEMATIKA•Dec 1, 2008•4 citations

Improved Bound on the Local Leakage-resilience of Shamir’s Secret Sharing

Hemanta K. Maji, Hai H. Nguyen, Anat Paskin-Cherniavsky +1 more

Side-channel attacks have repeatedly falsified the assumption that cryptosystems are black boxes. Leakage-resilient cryptography studies the robustness of cryptographic constructions when an unforeseen revelation of information occurs. In this context, recently, Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO–2018) motivated the study of the local leakage resilience of secret-sharing schemes against an adversary who obtains independent leakage from each secret share.Motivated by applications in secure computation, Benhamouda et al. (CRYPTO–2018) initiated the study of the local leakage resilience of Shamir’s secret-sharing scheme, an essential primitive for nearly all threshold cryptography. The objective is to achieve local leakage resilience with as small a fractional reconstruction threshold as possible. Previously, Benhamouda et al. showed that the reconstruction threshold k being at least 0.907 times the number of parties n is sufficient for Shamir’s secretsharing scheme to be resilient against arbitrary single-bit local leakage from each secret share. After that, Maji et al. (CRYPTO–2021) and Benhamouda et al. (Journal of Cryptology–2021) independently lowered this threshold to k/n ⩾ 0.8675 and k/n ⩾0.85, respectively.This paper contributes to this line of research and proves that k/n ⩾ 0.78 is sufficient. Next, motivated by applications in GMW-style leakage-resilient secure computation, our work extends this bound to a more general adversary who corrupts some parties (obtaining their entire secret shares) and obtains leakage from the remaining honest parties’ secret shares.Our technical analysis proceeds by Fourier analysis and accurately estimates an exponential sum arising in this analysis.

IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•24 citations
Non-malleable secret sharing (NMSS) schemes, introduced by Goyal and Kumar (STOC 2018), ensure that a secret m can be distributed into shares m₁,⋯,m_n (for some n), such that any t (a parameter ≤ n) shares can be reconstructed to recover the secret m, any t-1 shares doesn't leak information about m and even if the shares that are used for reconstruction are tampered, it is guaranteed that the reconstruction of these tampered shares will either result in the original m or something independent of m. Since their introduction, non-malleable secret sharing schemes sparked a very impressive line of research. In this work, we introduce a feature of local reconstructability in NMSS, which allows reconstruction of any portion of a secret by reading just a few locations of the shares. This is a useful feature, especially when the secret is long or when the shares are stored in a distributed manner on a communication network. In this work, we give a compiler that takes in any non-malleable secret sharing scheme and compiles it into a locally reconstructable non-malleable secret sharing scheme. To secret share a message consisting of k blocks of length ρ each, our scheme would only require reading ρ + log k bits (in addition to a few more bits, whose quantity is independent of ρ and k) from each party’s share (of a reconstruction set) to locally reconstruct a single block of the message. We show an application of our locally reconstructable non-malleable secret sharing scheme to a computational non-malleable secure message transmission scheme in the pre-processing model, with an improved communication complexity, when transmitting multiple messages.
Performing L pairs of multiplication with known (k, n)-linear secret sharing-based n party multiplication protocols using an (offline) preprocessing by the Beaver multiplication triple requires 2Lk elements of on-line communications where k is the threshold. This paper proposes a simultaneous multiplication protocol for L pairs based on (k, L, n)-packed linear secret sharing. By embedding L secret information into each share using (k, L, n)-packed linear secret sharing, though partial information of secret information is leaked from k - l + 1 shares for 1 ≤ l ≤ L, the proposed protocol can perform L multiplications with 2k elements of online communications. As applications of the proposed simultaneous multiplication protocol, we also introduce a simultaneous comparison protocol and an improvement of the communication cost of Araki et al.'s n party group-wise maximum/minimum value aggregation protocol. For example, when computing the maximum/minimum value of eight 64-bit data, our proposed aggregation protocol can reduce 59.6% of the communication cost.
Side-channel attacks have repeatedly falsified the assumption that cryptosystems are black boxes. Leakage-resilient cryptography studies the robustness of cryptographic constructions when an unforeseen revelation of information occurs. In this context, recently, Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO–2018) motivated the study of the local leakage resilience of secret-sharing schemes against an adversary who obtains independent leakage from each secret share.Motivated by applications in secure computation, Benhamouda et al. (CRYPTO–2018) initiated the study of the local leakage resilience of Shamir’s secret-sharing scheme, an essential primitive for nearly all threshold cryptography. The objective is to achieve local leakage resilience with as small a fractional reconstruction threshold as possible. Previously, Benhamouda et al. showed that the reconstruction threshold k being at least 0.907 times the number of parties n is sufficient for Shamir’s secretsharing scheme to be resilient against arbitrary single-bit local leakage from each secret share. After that, Maji et al. (CRYPTO–2021) and Benhamouda et al. (Journal of Cryptology–2021) independently lowered this threshold to k/n ⩾ 0.8675 and k/n ⩾0.85, respectively.This paper contributes to this line of research and proves that k/n ⩾ 0.78 is sufficient. Next, motivated by applications in GMW-style leakage-resilient secure computation, our work extends this bound to a more general adversary who corrupts some parties (obtaining their entire secret shares) and obtains leakage from the remaining honest parties’ secret shares.Our technical analysis proceeds by Fourier analysis and accurately estimates an exponential sum arising in this analysis.