Paper 2023/1724

Accountability for Misbehavior in Threshold Decryption via Threshold Traitor Tracing

Abstract

A $t$-out-of-$n$ threshold decryption system assigns key shares to $n$ parties so that any $t$ of them can decrypt a well-formed ciphertext. Existing threshold decryption systems are not secure when these parties are rational actors: an adversary can offer to pay the parties for their key shares. The problem is that a quorum of $t$ parties, working together, can sell the adversary a decryption key that reveals nothing about the identity of the traitor parties. This provides a risk-free profit for the parties since there is no accountability for their misbehavior --- the information they sell to the adversary reveals nothing about their identity. This behavior can result in a complete break in many applications of threshold decryption, such as encrypted mempools, private voting, and sealed-bid auctions. In this work we show how to add accountability to threshold decryption systems to deter this type of risk-free misbehavior. Suppose a quorum of $$ or more parties construct a decoder algorithm $$ that takes as input a ciphertext and outputs the corresponding plaintext or $$. They sell $$ to the adversary. Our threshold decryption systems are equipped with a tracing algorithm that can trace $$ to members of the quorum that created it. The tracing algorithm is only given blackbox access to $$ and will identify some members of the misbehaving quorum. The parties can then be held accountable, which may discourage them from selling the decoder $$ in the first place. Our starting point is standard (non-threshold) traitor tracing, where $$ parties each holds a secret key. Every party can decrypt a well-formed ciphertext on its own. However, if a subset of parties $$ collude to create a pirate decoder $$ that can decrypt well-formed ciphertexts, then it is possible to trace $$ to at least one member of $$ using only blackbox access to the decoder $$. Traitor tracing received much attention over the years and multiple schemes have been developed. In this work we develop the theory of traitor tracing for threshold decryption, where now only a subset $$ of $$ or more parties can collude to create a pirate decoder $$. This problem has recently become quite important due to the real-world deployment of threshold decryption in encrypted mempools, as we explain in the paper. While there are several non-threshold traitor tracing schemes that we can leverage, adapting these constructions to the threshold decryption settings requires new cryptographic techniques. We present a number of constructions for traitor tracing for threshold decryption, and note that much work remains to explore the large design space.