Cryptography with Weights: MPC, Encryption and Signatures

Paper: Cryptography with Weights: MPC, Encryption and Signatures. Sanjam Garg, Abhishek Jain, Pratyay Mukherjee, Rohit Sinha, Mingyuan Wang, and Yinuo Zhang. 2023

CRT-based (unweighted) sharing

Setup

  • Assume \(p_0, p_{1}, \ldots, p_n\) are \(n+1\) co-prime integers.
  • Let \(L\) be an integer.

Sharing

  • Pick a random secret \(s\in \mathbb{F}_{p_0}\).
  • Pick \(S = s + u\cdot p_{0}\) where \(u\) is uniform over \(1,2,\ldots,L\).
  • Share for party \(i\) is \(S\mod{p_i}\).

Reconstruction

  • Let \(A\) be the set of authorized users.
  • Define \(P_A = \prod\limits_{i\in A}p_i\).
  • Find \(0 \le S \le P_A-1\) and \(\forall i\in A, S=s_i\mod{p_i}\).
  • Concretely, compute \(((\lambda_1\cdot s_1 + \lambda_2\cdot s_2 + \ldots + \lambda_{n}s_n)\mod{P})\mod{p_{0}}\) where
    • \(P=p_{1}p_2\ldots p_n\).
    • \(\lambda_i\) is an integer satisfying \(\lambda_i\mod{p_i} = 1\) and \(\forall j\neq i, \lambda_i \mod{p_j} =0\).
  • For the secrecy to work, \(\max\limits_{\bar{A}}P_{\bar{A}} \ll L \leq \min\limits_A P_A/2^{\lambda}\). The constraint ensures that the distribution of the secret is uniformly random.

Weighted CRT-based sharing

  • Consider the ramp setting.
  • We know that \(\max\limits_{\bar{A}}P_{\bar{A}} \ll L \leq \min\limits_A P_A/2^{\lambda}\) for the unweighted setting.
  • Let \(p_i\) be integers of size \(c\cdot w_i\).
  • Then the constraint becomes \(\max\limits_{\bar{A}} 2^{\sum\limits_{i\in \bar{A}}c\cdot w_i} \ll L \leq \min\limits_A 2^{\sum\limits_{i\in A}c\cdot w_{i}}/2^{\lambda}\).
  • The constraint is therefore \(\sum\limits_{i\in \bar{A}} c\cdot w_i \ll \sum_{i\in A}c\cdot w_i - \lambda\).
  • Rewriting it \(c\cdot \sum\limits_{i\in \bar{A}} w_i \ll c\cdot \sum_{i\in A} w_i - \lambda\).
  • Let \(t\) be the privacy threshold in the ramp, and the \(T\) be the reconstruction threshold.
  • The constraint is now \(c\cdot t \ll c\cdot T - \lambda\) or \(\lambda \ll c\cdot (T-t)\).
  • If \(T-t = \theta(\lambda)\), then \(c=1\) suffices.
  • Therefore, the integers are of size \(w_i\) (improved from \(w_i\lambda\)).

Homomorphism in CRT-based sharing problems

  1. Non-linearity: reconstructing \(g^{s}\) is not straight-forward.
  2. Integer growing problem: Overflow, noise.
  3. Simulation challenges: distribution of [x]+[y] \(\neq\) distribution of [x+y].

WRSS

Weighted MPC

Weighted Threshold ECDSA

Questions

  • [X] Why is \((p_0+1)L \le P_A-1\)? Should it be \((L+1)p_0 \le P_A-1\)? This is a typo.
  • [X] Why does the right part of the constraint hold? i.e., \(P_A/2^{\lambda}\)?
  • [ ] Small weights leak the share. Figure 6, Step 1.

References

Sanjam Garg, Abhishek Jain, Pratyay Mukherjee, Rohit Sinha, Mingyuan Wang, and Yinuo Zhang. 2023. “Cryptography with Weights: MPC, Encryption and Signatures.” https://link.springer.com/10.1007/978-3-031-38557-5_10.