Paper 2025/243

K-Linkable Ring Signatures and Applications in Generalized Voting

Xiangyu Liu, CISPA

Yanxin Pang, Georgia Institute of Technology

Lirong Xia, Rutgers, The State University of New Jersey

Vassilis Zikas, Georgia Institute of Technology

Abstract

Linkable ring signatures (LRS) allow a user to sign anonymously on behalf of a ring at most once: two signatures from the same signer are publicly identified, i.e., linked. Linkability makes LRS suitable for classical, plurality voting protocols---each voter casts at most one vote and the candidate with the most votes wins. Several voting and governance scenarios rely on (generalized) rules rather than plurality. For example, in ranked voting, voters submit a ranking of the candidates, and the outcome is a function of these rankings. Such generalized rules are common in social choice theory, and have recently found their way into blockchain governance, e.g., for prioritizing (voting on) proposed (candidate) projects. However, unlike plurality voting, using LRS for voters to sign their votes (rankings) does not guarantee vote privacy as one can observe the rankings of each individual voter. We introduce $k$-Linkable Ring Signatures ($k$-LRS), an extension of standard (1-)linkable signatures, which simultaneously achieves anonymity and privacy in generalized voting. A $k$-LRS scheme has the following properties: ($k$-)Anonymity: a user can sign anonymously (on behalf of the ring) up to $k$ times, so that no one can link his signatures. ($k$-)Linkability: If any signer signs more than $k$ times, all his signatures are publicly linked (individual $k$-linkability); and, any set of $c$ signers cannot generate more than $k \cdot c$ unlinked signatures (collective $k$-linkability). We provide two constructions of $k$-LRS: one is from the DDH, and the other is from SIS (hence post-quantum) achieving unconditional anonymity, which we believe is important for voting situations which keep state indefinitely., e.g., blockchain governance mechanisms. We, then, show how $k$-LRS can be applied to a broad range of voting rules, including score voting, multi-voting, and Borda. Our voting protocols are non-interactive---each voter just posts a message on a bulletin board---which highlights the potential of $k$-LRS in blockchain-governance scenarios. Finally, we initiate the study of computational hardness of linking, i.e., exposing violations of $k$-linkability. Our study shed light to trade-offs between privacy, statefulness, and linkability of $k$-LRS, and as a result to their usefulness (and limitations) for digital governance.

Note: remove some author comments

@misc{cryptoeprint:2025/243,
      author = {Wonseok Choi and Xiangyu Liu and Yanxin Pang and Lirong Xia and Vassilis Zikas},
      title = {K-Linkable Ring Signatures and Applications in Generalized Voting},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/243},
      year = {2025},
      url = {https://eprint.iacr.org/2025/243}
}