Paper 2024/391

On Information-Theoretic Secure Multiparty Computation with Local Repairability

Daniel Escudero, J.P. Morgan AI Research and J.P. Morgan AlgoCRYPT CoE, New York, U.S.A.
Ivan Tjuawinata, Strategic Centre for Research on Privacy-Preserving Technologies and Systems, Nanyang Technological University, Singapore
Chaoping Xing, Shanghai Jiao Tong University, Shanghai, China

In this work we consider the task of designing information-theoretic MPC protocols for which the state of a given party can be recovered from a small amount of parties, a property we refer to as local repairability. This is useful when considering MPC over dynamic settings where parties leave and join a computation, a scenario that has gained notable attention in recent literature. Thanks to the results of (Cramer et al. EUROCRYPT'00), designing such protocols boils down to constructing a linear secret-sharing scheme (LSSS) with good locality, that is, each share is determined by only a small amount of other shares, that also satisfies the so-called multiplicativity property. Previous constructions that achieve locality (e.g. using locally recoverable codes---LRCs) do not enjoy multiplicativity, and LSSS that are multiplicative (e.g. Shamir's secret-sharing) do not satisfy locality. Our construction bridges this literature gap by showing the existence of an LSSS that achieves both properties simultaneously. Our results are obtained by making use of well known connection between error correcting codes and LSSS, in order to adapt the LRC construction by (Tamo & Barg, IEEE Transactions on Information Theory 2014) to turn it into a LSSS. With enough care, such coding-theoretic construction yields our desired locality property, but it falls short at satisfying multiplicativity. In order to address this, we perform an extensive analysis of the privacy properties of our scheme in order to identify parameter regimes where our construction satisfies multiplicativity. Finally, since our LSSS satisfies locality, every share is determined by a small amount of shares. However, in an MPC context it is not enough to let the (small set of) parties to send their shares to the repaired party, since this may leak more information than the regenerated share. To obtain our final result regarding MPC with local repairability, we construct a lightweight MPC protocol that performs such repairing process without any leakage. We provide both a passively secure construction (for the plain multiplicative regime) and an actively secure one (for strong multiplicativity).

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in PKC 2024
Secret SharingRepairability
Contact author(s)
daniel escudero @ protonmail com
ivan tjuawinata @ ntu edu sg
xingcp @ sjtu edu cn
2024-03-04: approved
2024-03-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Escudero and Ivan Tjuawinata and Chaoping Xing},
      title = {On Information-Theoretic Secure Multiparty Computation with Local Repairability},
      howpublished = {Cryptology ePrint Archive, Paper 2024/391},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.