Patent ID: 7970141

Claim:
A method for determining at least one traced private key used by a decoder to decrypt an encrypted message, the method comprising: defining an input ciphertext, the input ciphertext being associated with a tracing private key and having a sublinear size; calling the decoder on the input ciphertext; and associating the tracing private key with a set of traced private keys if the decoder is able to correctly decrypt the encrypted message in accordance with the input ciphertext, the set of traced private keys comprising at least one private key, wherein the sublinear size of the input ciphertext is a square root of a first number, the first number representing a number of users to whom the encrypted message is broadcast, wherein the tracing private key is structured such that, in order to decrypt the encrypted message, a first ciphertext component at a first position in an index of ciphertext components must be paired with a second ciphertext component at a second position in the index of ciphertext components, and wherein the first position in the index of ciphertext components and the second position in the index of ciphertext components are defined by a tuple associated with a user of the tracing private key.