Crypto Seminar

April 5, 2024 4:30pm — 5:30pm

Location:
In Person and Virtual - ET - Gates Hillman 7501 and Zoom

Speaker:
ADITI PARTAP, Ph.D. Student, Computer Science Department, Stanford University
https://aditi741997.github.io/

Accountability for Misbehavior in Threshold Decryption via Threshold Traitor Tracing

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 propose a solution to this problem. Suppose a quorum of~t or more parties construct a decoder algorithm~D(⋅) that takes as input a ciphertext and outputs the corresponding plaintext or ⊥. 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 (non-threshold) traitor tracing, where n parties each holds a secret key. Every party can decrypt a well-formed ciphertext on its own. However, if a subset of parties {𝒥} ⊆ [n] collude to create a pirate decoder D(⋅) that can decrypt well-formed ciphertexts, then it is possible to trace D to at least one member of {𝒥} 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 {𝒥} ⊆ [n] of~t or more parties can collude to create a pirate decoder D(⋅). 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.

Event Website:
https://sites.google.com/view/crypto-seminar/home