Paper 2026/2793

Weights Come Almost for Free in Ramp Threshold Cryptography

Abstract

A weighted threshold access structure assigns a weight to each party and authorizes a subset of parties whenever their total weight exceeds a prescribed threshold. Most existing approaches to designing multiparty cryptographic protocols in the weighted threshold setting, however, either incur complexity that grows with the total weight assigned to the parties or remain far from concretely efficient. Toward \emph{concretely efficient} weighted threshold primitives, we take a different route and relax to the \emph{ramp} setting, in which two thresholds are prescribed: a subset whose total weight falls below an $\alpha$ fraction of the total is unauthorized, while a subset whose total weight exceeds a $\beta$ fraction is authorized. Exploiting the gap between these two thresholds, we obtain the following results. 1. Given any weighted ramp threshold access structure with privacy threshold $\alpha$ and reconstruction threshold $\beta$, where $0\!<\!\alpha\!<\!\beta\!<\!1$, we present a weight compression technique that reduces the total weight to $\approx n/(2(\beta-\alpha))$ while preserving the authorized and unauthorized sets. Combined with the standard player-virtualization paradigm, this yields concretely efficient weighted threshold cryptographic protocols with only a multiplicative overhead of $\approx 1/(2(\beta-\alpha))$ over their unweighted counterparts. Previously, the best known compression technique in this setting, due to Benhamouda et al.~[ITC'23], achieved total weight $\approx 5n/(\beta-\alpha)$. 2. Player virtualization has an inherent drawback: a party's share size and workload grow in proportion to its (compressed) weight, so the parties in which the most trust is placed also bear the largest computational and communication costs. Thus, although the \emph{overall} overhead is $O(1)$, the cost borne by a single party can still be $O(n)$ times that in the unweighted setting. Our second result removes this imbalance. Building on our compression technique, we construct a linear secret-sharing scheme in which every party receives a share of size $\widetilde{O}(1)$, independent of its weight, for a total share size of $\widetilde{O}(n)$, nearly matching the $O(n)$ complexity of standard unweighted threshold secret sharing.