CryptoDB
Accountability in Threshold Decryption via Threshold Traitor Tracing
Authors: 


Download: 

Presentation:  Slides 
Conference:  CRYPTO 2024 
Abstract:  A $t$outof$n$ threshold decryption system assigns key shares to $n$ parties so that any $t$ of them can decrypt a wellformed 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 riskfree 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 sealedbid auctions. In this work we propose a solution to this problem. Suppose a quorum of~$t$ or more parties construct a decoder algorithm~$D(\cdot)$ that takes as input a ciphertext and outputs the corresponding plaintext or $\bot$. They sell~$D$ to the adversary. Our threshold decryption systems are equipped with a tracing algorithm that can trace~$D$ to members of the quorum that created it. The tracing algorithm is only given blackbox access to~$D$ and will identify some members of the misbehaving quorum. The parties can then be held accountable, which may discourage them from selling the decoder~$D$ in the first place. Our starting point is standard (nonthreshold) traitor tracing, where $n$ parties each holds a secret key. Every party can decrypt a wellformed ciphertext on its own. However, if a subset of parties ${\cal J} \subseteq [n]$ collude to create a pirate decoder $D(\cdot)$ that can decrypt wellformed ciphertexts, then it is possible to trace $D$ to at least one member of ${\cal J}$ using only blackbox access to the decoder~$D$. In this work we develop the theory of traitor tracing for threshold decryption, where now only a subset ${\cal J} \subseteq [n]$ of~$t$ or more parties can collude to create a pirate decoder $D(\cdot)$. This problem has recently become quite important due to the realworld deployment of threshold decryption in encrypted mempools, as we explain in the paper. While there are several nonthreshold traitor tracing schemes that we can leverage, adapting these constructions to the threshold decryption settings requires new cryptographic techniques. A $t$outof$n$ threshold decryption system assigns key shares to $n$ parties so that any $t$ of them can decrypt a wellformed ciphertext. Existing threshold decryption systems are {\em 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 riskfree 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 sealedbid auctions. In this work we propose a solution to this problem. Suppose a quorum of~$t$ or more parties construct a decoder algorithm~$D(\cdot)$ that takes as input a ciphertext and outputs the corresponding plaintext or $\bot$. They sell~$D$ to the adversary. Our threshold decryption systems are equipped with a tracing algorithm that can trace~$D$ to members of the quorum that created it. The tracing algorithm is only given blackbox access to~$D$ and will identify some members of the misbehaving quorum. The parties can then be held accountable, which may discourage them from selling the decoder~$D$ in the first place. Our starting point is standard (nonthreshold) traitor tracing, where $n$ parties each holds a secret key. Every party can decrypt a wellformed ciphertext on its own. However, if a subset of parties ${\cal J} \subseteq [n]$ collude to create a pirate decoder $D(\cdot)$ that can decrypt wellformed ciphertexts, then it is possible to trace $D$ to at least one member of ${\cal J}$ using only blackbox access to the decoder~$D$. In this work we develop the theory of traitor tracing for threshold decryption, where now only a subset ${\cal J} \subseteq [n]$ of~$t$ or more parties can collude to create a pirate decoder $D(\cdot)$. This problem has recently become quite important due to the realworld deployment of threshold decryption in encrypted mempools, as we explain in the paper. While there are several nonthreshold 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. 
BibTeX
@inproceedings{crypto202434214, title={Accountability in Threshold Decryption via Threshold Traitor Tracing}, publisher={SpringerVerlag}, doi={10.1007/9783031683947_11}, author={Dan Boneh and Aditi Partap and Lior Rotem}, year=2024 }