Paper 2022/1632

Cryptography with Weights: MPC, Encryption and Signatures

Sanjam Garg, NTT Research, University of California, Berkeley
Abhishek Jain, Johns Hopkins University
Pratyay Mukherjee, SupraOracles
Rohit Sinha, Meta
Mingyuan Wang, University of California, Berkeley
Yinuo Zhang, University of California, Berkeley

The security of several cryptosystems rests on the trust assumption that a certain fraction of the parties are honest. This trust assumption has enabled a diverse of cryptographic applications such as secure multiparty computation, threshold encryption, and threshold signatures. However, current and emerging practical use cases suggest that this paradigm of one-person-one-vote is outdated. In this work, we consider {\em weighted} cryptosystems where every party is assigned a certain weight and the trust assumption is that a certain fraction of the total weight is honest. This setting can be translated to the standard setting (where each party has a unit weight) via virtualization. However, this method is quite expensive, incurring a multiplicative overhead in the weight. We present new weighted cryptosystems with significantly better efficiency. Specifically, our proposed schemes incur only an {\em additive} overhead in weights. \begin{itemize} \item We first present a weighted ramp secret-sharing scheme where the size of the secret share is as short as $O(w)$ (where $w$ corresponds to the weight). In comparison, Shamir's secret sharing with virtualization requires secret shares of size $w\cdot\lambda$, where $\lambda=\log |\mathbb{F}|$ is the security parameter. \item Next, we use our weighted secret-sharing scheme to construct weighted versions of (semi-honest) secure multiparty computation (MPC), threshold encryption, and threshold signatures. All these schemes inherit the efficiency of our secret sharing scheme and incur only an additive overhead in the weights. \end{itemize} Our weighted secret-sharing scheme is based on the Chinese remainder theorem. Interestingly, this secret-sharing scheme is {\em non-linear} and only achieves statistical privacy. These distinct features introduce several technical hurdles in applications to MPC and threshold cryptosystems. We resolve these challenges by developing several new ideas.

Available format(s)
Publication info
weighted secret sharing mpc threshold decryption threshold signature
Contact author(s)
sanjamg @ berkeley edu
abhishek @ cs jhu edu
pratyay85 @ gmail com
sinharo @ gmail com
mingyuan @ berkeley edu
yinuo @ berkeley edu
2022-11-25: approved
2022-11-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sanjam Garg and Abhishek Jain and Pratyay Mukherjee and Rohit Sinha and Mingyuan Wang and Yinuo Zhang},
      title = {Cryptography with Weights: MPC, Encryption and Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1632},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.