International Association for Cryptologic Research

International Association
for Cryptologic Research


Rohit Sinha


Cryptography with Weights: MPC, Encryption and Signatures
The security of many powerful cryptographic systems such as secure multiparty computation, threshold encryption, and threshold signatures rests on trust assumptions about the parties. The de-facto model treats all parties equally and requires that a certain fraction of the parties are honest. While this paradigm of one-person-one-vote has been very successful over the years, current and emerging practical use cases suggest that it 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: our proposed schemes incur only an {\em additive} overhead in weights. \begin{itemize} \item We first present a weighted ramp secret-sharing scheme (WRSS) where the size of a secret share is $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 |\bbF|$ is the security parameter. \item Next, we use our WRSS to construct weighted versions of (semi-honest) secure multiparty computation (MPC), threshold encryption, and threshold signatures. All these schemes inherit the efficiency of our WRSS and incur only an additive overhead in weights. \end{itemize} Our WRSS is based on the Chinese remainder theorem-based secret-sharing scheme. 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.