Paper 2022/096

On Regenerating Codes and Proactive Secret Sharing: Relationships and Implications

Karim Eldefrawy, Nicholas Genise, Rutuja Kshirsagar, and Moti Yung


We look at two basic coding theoretic and cryptographic mechanisms developed separately and investigate relationships between them and their implications. The first mechanism is Proactive Secret Sharing (PSS), which allows randomization and repair of shares using information from other shares. PSS enables constructing secure multi-party computation protocols that can withstand mobile dynamic attacks. This self-recovery and the redundancy of uncorrupted shares allows a system to overcome recurring faults throughout its lifetime, eventually finishing the computation (or continuing forever to maintain stored data). The second mechanismis Regenerating Codes (RC) which were extensively studied and adopted in distributed storage systems. RC are error correcting (or erasure handling) codes capable of recovering a block of a distributively held codeword from other servers' blocks. This self-healing nature enables more robustness of a code distributed over different machines. Given that the two mechanisms have a built-in self-healing (leading to stabilizing) and that both can be based on Reed Solomon Codes, it is natural to formally investigate deeper relationships between them. We prove that a PSS scheme can be converted into an RC scheme, and that under some conditions RC can be utilized to instantiate a PSS scheme. This allows us, in turn, to leverage recent results enabling more efficient polynomial interpolation (due to Guruswami and Wooters) to improve the efficiency of a PSS scheme. We also show that if parameters are not carefully calibrated, such interpolation techniques (allowing partial word leakage) may be used to attack a PSS scheme over time. Secondly, the above relationships give rise to extended (de)coding notions. Our first example is mapping the generalized capabilities of adversaries (called generalized adversary structures) from the PSS realm into the RC one. Based on this we define a new variant of RC we call Generalized-decoding Regenerating Code (GRC) where not all network servers have a uniform sub-codeword (motivated by non-uniform probability of attacking different servers case). We finally highlight several interesting research directions due to our results, e.g., designing new improved GRC, and more adaptive RC re-coding techniques.

Available format(s)
Publication info
Published elsewhere. MINOR revision.SSS 2021
Proactive Secret SharingRegenerating Codes
Contact author(s)
karim eldefrawy @ sri com
ngenise @ dualitytech com
rutujak @ vt edu
motiyung @ google com
2022-01-31: received
Short URL
Creative Commons Attribution


      author = {Karim Eldefrawy and Nicholas Genise and Rutuja Kshirsagar and Moti Yung},
      title = {On Regenerating Codes and Proactive Secret Sharing: Relationships and Implications},
      howpublished = {Cryptology ePrint Archive, Paper 2022/096},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.