ENHANCED SYSTEMS AND METHODS FOR PIRATE DECODER IDENTIFICATION

Abstract

The disclosed technology relates to a method and system for detecting pirated decryption keys. The method involves the use of a computer tracer apparatus, comprising a translator algorithm and a query generator algorithm. The translator algorithm receives a decoder program and generates responses to queries based on a set of rules, including a state repair procedure. The query generator algorithm generates an initial and subsequent sets of queries based on inputs from the translator algorithm. The final output identifies potential traitor users. The system is executed on a quantum computer and includes modules configured for the same operations.

Claims

1. A method executing on a computer for a tracer for detecting if a decoder device is executing a pirated copy of a decryption key acquired from one or more traitor users, the method comprising: instantiating a translator algorithm, which in combination with a query generator algorithm, comprises a computer tracer apparatus; instantiating the query generator algorithm, the algorithm configured for: generating an initial set of queries, and generating subsequent sets of queries based on inputs from the translator algorithm; generating a final output based on responses it receives from the translator algorithm; by the translator algorithm: receiving a decoder program; receiving the initial set of queries q.sub.i from the query generator algorithm; generating responses to the the initial set of queries based on a set of rules comprising at least a state repair procedure; receiving subsequent queries q.sub.i from the query generator algorithm; generating subsequent responses to the subsequent queries; receiving the final output from the query generator; producing a final translator output based on the final output from the query generator; and storing the final translator output as the the identity of one or more traitor users.

2. The method of claim 1, wherein the translator, upon receiving a query from the query generator: either performs the state repair procedure or does not, depending on the queries received by that time; then responding to the query with 0 or 1 based on a computation involving the query and the decoder.

3. The method of claim 1, wherein the state repair procedure: receives as input a quantum decoder as a quantum system and two quantum measurements M.sub.1, M.sub.2 whose outputs are real numbers between 0 and 1, and a threshold; modifies the decoder in order to increase the value produced by M.sub.1; and then alternatively applying M.sub.1, M.sub.2, M.sub.1, M.sub.2, . . . , and terminating when an application of M.sub.1 produces an output above the threshold.

4. The method of claim 1, the translator further comprising a probability estimation procedure, wherein the estimation procedure is configured for: a. executing based on q.sub.i and using the decoder program, and b. producing an outcome that is p.sub.q.sub.i, which is a real number between 0 and 1, and at the translator, based on previous outputs of the probability estimation procedure, setting o.sub.q.sub.i to be 0 or 1.

5. The method of claim 1, wherein the query generator executes by: a. initializing integers a to be N and b to be 0, wherein N is determined based on system parameters; b. producing a query q.sub.i which is set to b; c. obtaining a response o; d. if o=1, set a=b and b=0, then go to step b; otherwise: if b=a1, then output a as the final output of the query generator; if ba1, produce the query q.sub.i which is set to a, set b to be the integer part of (a+b)/2, and go to step b.

6. The method of claim 1, wherein the system is a quantum system comprised of qbits, and wherein the algorithm for generating queries executes on a classical system.

7. A computerized system for a tracer for detecting if a decoder device is executing a pirated copy of a decryption key acquired from one or more traitor users, the system comprising a processor configured for: instantiating a translator algorithm, which in combination with a query generator algorithm, comprises a computer tracer apparatus; instantiating the query generator algorithm, the algorithm configured for: generating an initial set of queries, and generating subsequent sets of queries based on inputs from the translator algorithm; generating a final output based on responses it receives from the translator algorithm; by the translator algorithm: receiving a decoder program; receiving the initial set of queries q.sub.i from the query generator algorithm; generating responses to the the initial set of queries based on a set of rules comprising at least a state repair procedure; receiving subsequent queries q.sub.i from the query generator algorithm; generating subsequent responses to the subsequent queries; receiving the final output from the query generator; producing a final translator output based on the final output from the query generator; and storing the final translator output as the the identity of one or more traitor users.

8. The system of claim 7, wherein the translator, upon receiving a query from the query generator: either performs the state repair procedure or does not, depending on the queries received by that time; then responding to the query with 0 or 1 based on a computation involving the query and the decoder.

9. The system of claim 7, wherein the state repair procedure: receives as input a quantum decoder as a quantum system and two quantum measurements M.sub.1, M.sub.2 whose outputs are real numbers between 0 and 1, and a threshold; modifies the decoder in order to increase the value produced by M.sub.1; and then alternatively applying M.sub.1, M.sub.2, M.sub.1, M.sub.2, . . . , and terminating when an application of M.sub.1 produces an output above the threshold.

10. The system of claim 7, the translator further comprising a probability estimation procedure, wherein the estimation procedure is configured for: a. executing based on q.sub.i and using the decoder program, and b. producing an outcome that is p.sub.q.sub.i, which is a real number between 0 and 1, and at the translator, based on previous outputs of the probability estimation procedure, setting o.sub.q.sub.i to be 0 or 1.

11. The system of claim 7, wherein the query generator executes by: a. initializing integers a to be N and b to be 0, wherein N is determined based on system parameters; b. producing a query q.sub.i which is set to b; c. obtaining a response o; d. if o=1, set a=b and b=0, then go to step b; otherwise: if b=a1, then output a as the final output of the query generator; if ba1, produce the query q.sub.i which is set to a, set b to be the integer part of (a+b)/2, and go to step b.

12. The system of claim 7, wherein the system is a quantum system comprised of qbits, and wherein the algorithm for generating queries executes on a classical system.

13. A non-transitory processor-readable medium storing code representing instructions to be executed by a processor at a compute device, the code further comprising commands for: instantiating a translator algorithm, which in combination with a query generator algorithm, comprises a computer tracer apparatus; instantiating the query generator algorithm, the algorithm configured for: generating an initial set of queries, and generating subsequent sets of queries based on inputs from the translator algorithm; generating a final output based on responses it receives from the translator algorithm; by the translator algorithm: receiving a decoder program; receiving the initial set of queries q.sub.i from the query generator algorithm; generating responses to the the initial set of queries based on a set of rules comprising at least a state repair procedure; receiving subsequent queries q.sub.i from the query generator algorithm; generating subsequent responses to the subsequent queries; receiving the final output from the query generator; producing a final translator output based on the final output from the query generator; and storing the final translator output as the the identity of one or more traitor users.

14. The media of claim 13, wherein the translator, upon receiving a query from the query generator: either performs the state repair procedure or does not, depending on the queries received by that time; then responding to the query with 0 or 1 based on a computation involving the query and the decoder.

15. The media of claim 13, wherein the state repair procedure: receives as input a quantum decoder as a quantum system and two quantum measurements M.sub.1, M.sub.2 whose outputs are real numbers between 0 and 1, and a threshold; modifies the decoder in order to increase the value produced by M.sub.1; and then alternatively applying M.sub.1, M.sub.2, M.sub.1, M.sub.2, . . . , and terminating when an application of M.sub.1 produces an output above the threshold.

16. The media of claim 13, the translator further comprising a probability estimation procedure, wherein the estimation procedure is configured for: a. executing based on q.sub.i and using the decoder program, and b. producing an outcome that is p.sub.q.sub.i, which is a real number between 0 and 1, and at the translator, based on previous outputs of the probability estimation procedure, setting o.sub.q.sub.i to be 0 or 1.

17. The media of claim 13, wherein the query generator executes by: a. initializing integers a to be N and b to be 0, wherein N is determined based on system parameters; b. producing a query q.sub.i which is set to b; c. obtaining a response o; d. if o=1, set a=b and b=0, then go to step b; otherwise: if b=a1, then output a as the final output of the query generator; if ba1, produce the query q.sub.i which is set to a, set b to be the integer part of (a+b)/2, and go to step b.

18. The media of claim 13, wherein the system is a quantum system comprised of qbits, and wherein the algorithm for generating queries executes on a classical system.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0024] Non-limiting and non-exhaustive examples are described with reference to the following figures.

[0025] FIG. 1 illustrates a quantum computer tracer apparatus, according to aspects of the present disclosure.

[0026] FIG. 2 depicts a system architecture for a quantum computing environment, related to FIG. 1, according to aspects of the present disclosure.

[0027] FIG. 3 shows a block diagram of a quantum computer system, expanding on the system architecture in FIG. 2, according to aspects of the present disclosure.

[0028] FIG. 4 and FIG. 5 both represent classical computing components that may be used in combination with or in place of the quantum systems depicted in FIGS. 1-3, according to aspects of the present disclosure.

DETAILED DESCRIPTION

[0029] The following description sets forth exemplary aspects of the present disclosure. It should be recognized, however, that such description is not intended as a limitation on the scope of the present disclosure. Rather, the description also encompasses combinations and modifications to those exemplary aspects described herein.

1 Technical Overview

1.1 a General View of Classical Tracing Algorithms

Essentially all modern classical traitor tracing algorithms can be framed as follows. There is a collection ={D.sub.q of distributions of ciphertexts, and the adversary produces a decoder subject to the following guarantees: [0030] Large success probability on source. The distribution of honest ciphertexts is an element of , which we will denote as D.sub. for some distinguished that we call the source. Any useful decoder, by definition, has a large success probability on D.sub.. [0031] Small success probability on sinks. There is a collection of distributions {D.sub.q}.sub.q for q, which we may call sinks, for which any coalition of users has small success probability. [0032] Constant on adversary partition. Any coalition of malicious users corresponds to a partition on , such that the coalition, and therefore their decoder, cannot efficiently distinguish between distributions belonging to the same part of the partition. In other words, the decoder's decryption probability is roughly constant on each part of the partition.
The tracing algorithm therefore tests the decoder on various D.sub.q, learning (estimates of) the decoder's success probabilities on D.sub.q. The rough idea is that and q must have different success probabilities, so the tracer is guaranteed to see some jumps as it make its queries. These jumps must be across different parts of the partition, revealing some information about the structure of the partition. The hope is that this information can identify at least one malicious user.

[0033] Abstracting out the details of generating the various distributions and estimating their success probability, we arrive at a model we might call the Globally Consistent Hidden Partition model, where the tracer simply queries (potentially adaptively) on various q.sub.i and receives in response real numbers o.sub.i [0, 1]. We are guaranteed that any o.sub.i,o.sub.j which correspond to queries q.sub.i,q.sub.j lying in the same part of the partition will be close, that q.sub.i= will give large o.sub.i, and that q.sub.i will give small o.sub.i. The tracer then takes these o; and uses them to learn information about the partition.

Example: PLBE. To make things concrete, we now illustrate how this view captures private linear broadcast encryption (PLBE). Here, there are N users, with identities 1, . . . , N. For any q[0,N], one can encrypt to the set [q]={1, . . . , q}. Users in q will be able to decrypt, while users outside of q will not. An honest ciphertext is an encryption to all users, q=N. Moreover, any coalition of users will be unable to distinguish encryptions to [a] and [b], unless the coalition contains a user in the half-open interval (a,b]. In the view above, we would therefore have =[0,N], =N, and ={0}. For a coalition of users a.sub.1<a.sub.2< . . . <a.sub.t [N], the partition therefore consists of the intervals [0,a.sub.1], (a.sub.1,a.sub.2], (a.sub.2,a.sub.3], . . . , (a.sub.t,N].

[0034] To trace, we split into two cases. In the case where N is polynomial, one simply estimates the success probabilities o.sub.0, o.sub.1, . . . , o.sub.N on queries 0, 1, . . . , N. The usefulness of the decoder implies that o.sub.N>>0, while PLBE security implies that o.sub.00. Therefore, there must exist a q such that |o.sub.q1o.sub.q|>>0. But since o.sub.i must be constant on the intervals in , we know that q=a.sub.i for some i. Thus we have identified a member of the coalition.

[0035] If N is exponential, then we cannot simply do a linear scan. However, a variant of a binary search will work, as shown in Boyle, Chung, and Pass as well as Nishimaki et al. In the binary search, we recurse left if there is a large gap between the pivot and the left value, while we recurse right if there is a large gap between the pivot and the right value. Importantly, we must make sure to pivot both left and right if there is a large gap in both directions. Otherwise, there is a possibility that every time we recurse, the gap gets divided by 2, and after a polynomial number of steps the gap is negligible but we have yet to accuse a user. Fortunately, it is proved by those works that there will never be more branches in the binary search than there are users in the coalition, so the overall search still takes polynomial time.

1.2 Moving to Quantum: Prior Results

When we move to allowing a quantum decoder, we must be much more careful. There are several issues, first pointed out by Zhandry. First is definitional: the success probability of the decoder is not necessarily known (nor even knowable) until it is measured, and any measurement necessarily alters the quantum state. Care must be taken to appropriately define traitor tracing to handle cases where the decoder may be in superposition of both high success probability and low success probability. Zhandry shows how to handle these definitional issues.

[0036] The second issue has to do with rewinding, which happens at two levels. First, estimating success probability on a distribution classically involves running the decoder on various samples from the distribution. But this implicitly requires being able to return the decoder to its original state every time, to ensure independent trials from the same distribution. As mentioned above, quantumly rewinding is problematic. In particular, each trial may alter the state of the decoder. Zhandry demonstrates that the classical approach of repeated sampling cannot, in general, yield an estimate of the decoder's success probability. Fortunately, Zhandry shows how to develop a quantum-compatible success probability estimation routine based on a technique of Marriott and Watrous.

[0037] Note that Zhandry's procedure requires security to hold when the adversary gets an arbitrary polynomial number of tracing ciphertexts; this is not the case for traitor tracing from LWE. We inherit this limitation, and this is why we still cannot handle succinct traitor tracing from LWE.

[0038] A second level is that multiple success probabilities will have to be estimated, for various distributions of inputs. In the classical setting, it is assumed that each estimate of success probability is applied to the same initial decoder; in other words, the decoder is rewound to its initial state. (The usual terminology is that the decode is stateless.). Otherwise, how can we make sense of gaps between estimated success probabilities, if the success probabilities has since changed and the previous estimates are no longer valid.

[0039] Zhandry gives a first step toward overcoming this problem, by showing that a local consistency property holds: if two consecutive estimates of success probabilities are on computationally indistinguishable distributions, then the estimated success probabilities will be close. However, estimated probabilities that are not consecutive may not obey this property. This gives rise to a variant of the tracing model above, which we will call the Locally Consistent Hidden Partition Model, that is identical to the Globally Consistent model above, except that (1) o.sub.i,o.sub.j corresponding to q.sub.i,q.sub.j in the same part are guaranteed close only if |ij|1, and (2) q.sub.i= is guaranteed to yield a large r.sub.i only on the first query i=1. The good news is that the linear scan algorithm for PLBE with polynomial identity space fits within this model (provided the scan starts at N and goes to 0), allowing Zhandry to trace this particular case. On the other hand, the model seems inherently limited to PLBE: during any sequence of probability estimates, the estimate outcomes may be the sequence 1, 1, 1, . . . , 1, 0, 0, 0, . . . . Such a sequence would satisfy the local consistency requirements, as long as the jump from 1 to 0 happens the first time a distribution D.sub.q for q is tested. But for a polynomial-length sequence, only a log number of bits of information can be extracted, namely the location of the jump between 1 and 0. Thus this model is incapable of handling a variety of traitor tracing scenarios, such as [0040] Embedded identities, where the whole point is to embed more than a logarithmic amount of information. [0041] Combinatorial traitor tracing, which usually follows a non-linear path. For example, traitor tracing based on fingerprinting codes first extracts a very long codeword from the decoder, which is then further processed; in the locally consistent model it would be impossible to construct this codeword.
The work of Kitagawa and Nishimaki. Kitagawa and Nishimaki show how to watermark PRFs in a quantum decoder model. Most relevant to us, their algorithm surprisingly extracts more than a logarithmic amount of information. However, their techniques are likely limited to the case of no collusions, which is insufficient for our purposes.

1.3 Our Solution: The Back One Step (BOS) Model

A starting point for our results is the recent work of Chiesa, Ma, Spooner, and Zhandry. They provide a powerful new rewinding technique, where they show that in some sense it is possible to repair a quantum state after a measurement. They apply their technique to the setting of interactive proofs, where they repair the quantum state of the adversary in order to rewind the it many times. In this work, we show how to adapt the rewinding technique to our setting.

[0042] Before getting into the details of our approach, we highlight some conceptual differences between our settings: [0043] Chiesa et al. extract information from an adversary using the adversary's actual messages; the rewinds are used to obtain many such messages. The inputs for the different rewinds are typically all uniformly random and independent. In contrast, for traitor tracing, information is generally extracted by looking at success probabilities. The distributions tested will generally be far from uniform, in order to get differences in success probabilities. [0044] The decision tree in traitor tracing is rather deep. Consider for example the binary search algorithm for PLBE with large identities. In order to find a gap, we must explore a deep branch. We may not find anything, in which case we must return to the root and explore a different branch. In contrast, the rewinding in Chiesa et al. always returns the adversary to a state approximating the initial state of the adversary. In this sense, the decision tree is shallow, having only one level. [0045] The repair procedure can only repair a single feature of the adversary. This is inherent, since different quantities may correspond to incompatible observables, and in general quantum systems one cannot simultaneously know the values of incompatible observables. Chiesa et al. always repair just the original success probability of the adversary. This is enough for them, due to their shallow decision tree. Looking at our setting, however, always repairing to the initial setting will not work. For example, in the binary search case, if we just repair to the initial success probability, this allows us to return to the root of the binary search tree. But now the values at all points may have shifted around. So if we explore a branch and fail to find a gap, when we return to the root, the gap we are looking for may have moved into the branch we just abandoned. Even if we explore all branches, we may never end up actually finding the ever-moving gap.

[0046] In order to simplify the task of designing new tracing protocols to overcome these challenges, we propose an intermediate model which we call the Back One Step (BOS) model. The BOS model allows us to abstract away the complicated techniques of state repair in order to give a clean model of what the technique should be capable of. This model will then allow us to design novel tracing algorithms. Importantly, the task of designing algorithm in the model will be entirely classical, with all the quantum aspects hidden beneath the abstraction.

The Model. We now describe the BOS model: there is a collection of queries available. There is moreover a potentially stateful oracle which contains a secret partition of . The oracle accepts a sequence of queries q.sub.1, . . . , q.sub.t , and answers queries with a bit o.sub.i {0, 1}. Note that we descretized the o.sub.i, to make the model simpler. We impose the following constraints: [0047] Large value on source if first query. A distinguished query . If q.sub.1=, then o.sub.1=1. There are no guarantees on subsequent queries to , or if is not the very first query. [0048] Small values on sinks. There is a collection , such that if q.sub.i , then o.sub.i=0. This holds for all i. [0049] Local consistency. For any two consecutive queries q.sub.i, q.sub.i+1, if q.sub.i, q.sub.i+1 lie in the same part of the partition (and in particular, if q.sub.i=q.sub.i+1), then o.sub.i=o.sub.i+1. There is no such requirement for q.sub.i,q.sub.j with |ij|>1. [0050] Single step rewinding. Finally, if q.sub.i+2=q.sub.i, then o.sub.i+2=o.sub.i. Any other identical queries that may exist in the query sequence have no such restriction.
If we ignore the last requirement, note that we recover the model of Zhandry. The last requirement essentially says that we can make a query q.sub.i, make an arbitrary different query q.sub.i+1, and then rewind to the previous query q.sub.i for query i+2 and be guaranteed to recover the same output o.sub.i a second time.
Realizing the BOS Model. By adapting the rewinding technique of Chiesa et al., we show how to instantiate a BOS oracle from any pirate decoder or diO adversary. The rough idea is to run the BOS algorithm, using Zhandry's success probability estimation routine to answer every query. This already ensures large values on the source (if the first query), small values on the sinks, and local consistency, following the same analysis as Zhandry. In order to ensure single step rewinding, we then add one more feature: if any query q.sub.i+2 is equal to q.sub.i, instead of naively computing the success probability o.sub.q+2 using Zhandry, we instead use the quantum rewinding technique of Chiesa et al. to rewind to a state where query q.sub.i+2=q.sub.i yields success probability essentially equal to o.sub.q. Thus, we can answer the query with o.sub.q+2=o.sub.q, thereby guaranteeing single step rewinding.
Designing Algorithms for the BOS Model. The BOS oracle guarantees are much weaker than the Globally Consistent Hidden Partition Model, and as discussed above, many classical tracing algorithm crucially rely on these stronger consistency guarantees. Perhaps surprisingly, while local consistency alone does not appear enough for many tracing settings, the ability to rewind even a single step opens many doors. We design new algorithms for the BOS model for the various settings, crucially leveraging the ability to rewind a single step. Importantly, this design process is entirely classical, greatly simplifying the design task. We note that the algorithm for each result is different (aside from the iO/diO equivalence and basic embedded identity tracing scheme being the same).

[0051] We next briefly describe how the process works for tracing PLBE; for the other results see the main body of the paper.

The case of PLBE. As explained above, in the case of PLBE, we have =[0, N], =N, ={0}, and ={[0, a.sub.1], (a.sub.1, a.sub.2], (a.sub.2, a.sub.3], . . . , (a.sub.t, N]}. Our goal is to recover one of the a.sub.i.

[0052] We know if the first query is on =N, then the response is o.sub.N=1. Likewise, we know if we ever query on 0, the response is o.sub.0=0. In the classical case, we would identify an a.sub.i via a binary search. We first assign a pivot to be N/2, and query on N/2. If the query response is o.sub.N/2=1, we know that at least one a.sub.i lies in the interval [1, N/2], so we can recurse on the interval [0, N/2]. If the query response is O.sub.N/2=0, then we know at least one a.sub.i lies in the interval [N/2+1, N], and so we can recurse on the interval [N/2, N].

[0053] In the BOS model, we can try the same: after querying on N and receiving response 1, we query on N/2 and receive response o.sub.N/2. If o.sub.N/2=1, we know by the rules of the BOS model that there is an a.sub.i in the interval [1, N/2], and if o.sub.N/2=0, we know by the rules of the BOS model that there is an a.sub.i in the interval [N/2+1, N]. Moreover, in the case o.sub.N/2=1, we actually have the correct setup to recurse on =[0, N/2] by setting =N/2, ={0}, and to be the partition of induced by . Indeed by local consistency, since the last query was on N/2= and the response was 1, if the next query is on the response will be 1, guaranteeing a large response for the recursion. Small value on the sink, local consistency, and single step rewinding carry over as well.

[0054] On the other hand, let us see what happens if we try to recurse on [N/2, N] in the case o.sub.N/2=0. We would naturally set =[N/2, N], =N, ={N/2}. We note that local consistency and single step rewinding still carry over to this case. Moreover, since the penultimate query was on N=, single step rewinding guarantees that we get a large value on if it is the next query.

[0055] This leaves small values on sink. Initially, it is true that querying on the sink N/2 gives 0, as desired. But importantly this only holds initially, where the BOS model requires the sink to give 0 always. We can see where this leads to trouble by taking the recursion a couple steps model. The next step is to query on 3N/4, receiving o.sub.3N/4. Suppose o.sub.3N/4=1. Then we recuse left on the interval =[N/2, 3N/4] and query on 5N/8. Suppose again that o.sub.5N/8=1, so we recurse on the interval [N/2,5N/8]. At this point, we would want that ={N/2}. However, our last query on N/2 was three queries ago (with 3N/4 and 5N/2 between). Therefore, o.sub.N/2 may have changed, and there is no longer any guarantee of having small values on the sinks. Without a small value on the sinks, the recursion will fail.

[0056] One attempt to fix this problem is, after querying on 3N/4 and receiving o.sub.3N/4=1, we insert a query on N/2. By single step rewinding, we have, as desired, that the result is o.sub.N/2=1. However, this strategy fails when we move to the query on 5N/8. Suppose now that o.sub.5N/8=0, meaning we recurse right on the interval =[5N/8, 3N/4]. Unfortunately, by inserting the new query on N/2, the most recent query on 3N/4 was now three queries ago (being followed by N/2 and 5N/8). Therefore, we no longer have the guarantee that querying on the new source =3N/4 gives a 1, and in fact it could be that all future queries give a 0, which clearly does not allow for extracting any information.

[0057] We now explain our solution. If o.sub.N/2=1, we recurse on [0, N/2] as we would classically. In the case o.sub.N/2=0, we still query on 3N/4 to get o.sub.3N/4. Here, if o.sub.3N/4=1, we cannot recurse on the interval [N/2, 3N/4]. However, we can recurse on the interval =[0, 3N/4], since now ={0}=Q and so we guarantee small values on sinks throughout, not just on the next query.

[0058] What if o.sub.3N/4=0? In this case, we update the pivot to 7N/8 as if we were recursing to the right. Importantly, however, we always keep the bottom of the domain as 0 to ensure small values on the sink. So if o.sub.7N/8 gives 1, we recurse on the interval [0, 7N/8]. If o.sub.7N/8=0, we update the pivot to 15N/16, and so on.

[0059] With this new algorithm, we can prove that we do indeed preserve all the properties of the BOS model in each step of the recursion, and will eventually reach the case where the interval is [0, a] and the pivot is a1, and the last two queries were on a, a1 giving o.sub.a=1, o.sub.a1=0. We output a, as local consistency implies that a is one of the endpoints of the intervals in . Moreover, we can prove termination in a polynomial number of steps, namely O(t log.sup.2 N) where t is the number of a.sub.i

2 Quantum Background

We assume basic familiarity with quantum computation. We distinguish between classical probabilistic polynomial time (PPT) algorithms and quantum polynomial time (QPT) algorithms. Sometimes we will consider programs that consist of a quantum state. Formally, these will consist of a quantum circuit C, and and a quantum auxiliary input aux. To evaluate the program on input x, one evaluates C on |x.Math.aux. We will denote such programs by |P and the evaluation of such programs as |P(x).
Almost Projective Measurements. We state a property of general measurements due to zhandry that captures when a measurement is close to being projective, in the sense that sequential applications of the measurement yield similar outcomes.

[0060] A real-valued measurement M=(M.sub.p).sub.p is (, )-almost projective if applying M twice in a row to a register (initially containing any state produces measurement outcomes p, p where Pr[|pp|]1.

Quantum State Repair. We now recall quantum state repair from Chiesa, Ma, Spooner, and Zhandry.

[0061] [Chiesa et al., Lemma 4.10] Given a projective measurement P on register that has outcomes in set S of size N, an (, )-almost projective measurement M on , and T, sS, p[0,1], there exists a procedure Repair.sub.T,p,s.sup.M,P on such that: [0062] (State is repaired with respect to M) Consider applying the following operations to register initially containing state : [0063] 1. First apply M to obtain p[0, 1], [0064] 2. Then apply P to obtain outcome sS, [0065] 3. Then apply Repair.sub.T,p,s.sup.M,P, [0066] 4. And finally, apply M once more to obtain p[0,1].

[0067] Then Pr[|pp|>2]N+N/T+4. [0068] (Efficiency) The expected total number of calls that Repair makes to M and P is at most N+4{square root over ()}.

[0069] In other words, since M is almost projective, applying M twice in a row will give outcomes p, p that are close. However, if P is applied in between these two measurements, there are no more guarantees on the closeness of p, p. However, by applying Repair before the second application of M, we can once again ensure closeness of p, p.

Mixtures of Projective Measurements. The following is taken from Zhandry. We consider the following abstract setup. We have a collection ={.sub.i}.sub.i of binary outcome projective measurements .sub.i=(P.sub.i,Q.sub.i) over the same Hilbert space . Here, P.sub.i corresponds to output 0, and Q.sub.i corresponds to output 1. We will assume we can efficiently measure the .sub.i for superpositions of i, meaning we can efficiently perform the following projective measurement over .Math.:

[00001]$\begin{array}{cc}(\underset{i}{.Math.}.Math.i.Math..Math.i.Math..Math.P_i,\underset{i}{.Math.}.Math.i.Math..Math.i.Math..Math.Q_i)& \left(1\right)\end{array}$

[0070] Here, we call a collection of projective measurements, and call the control. For a distribution D over , let .sub.D be the POVM which samples a random iD, applies the measurement .sub.i, and outputs the resulting bit. We call .sub.D a mixture of projective measurements. The POVM is given by the matrices (P.sub.D,Q.sub.D) where

[00002]$P=\underset{i}{.Math.}Pr\left[iD\right]P_i\mathrm{and}Q=\underset{i}{.Math.}Pr\left[iD\right]Q_i$

[0071] Next, for a and interval [b,c], denote the distance between a and [b,c] as |a[b,c]|:=min.sub.x[b,c] |ax|. For a[b,c], the distance is 0 and for a.Math.[b,c], the distance is max(ac,ba). Let D.sub.0, D.sub.1 be two distributions over , with cumulative density functions .sub.0, .sub.1, respectively. Let . The Shift distance with parameter is defined as:

[00003]${}_{}\left(D_0,D_1\right):=\underset{x}{\sup }.Math.f_0\left(x\right)-\left[f_1\left(x-\right),f_1\left(x+\right)\right].Math.$

[0072] Let M= and N=(N.sub.j) be real-valued quantum measurements over the same quantum system . The shift distance between M, N, denoted .sub.(M, N) is defined as

[00004]${}_{}\left(M,N\right):=\underset{.Math..Math.}{\sup }{}_{}(M(.Math..Math.),N(.Math..Math.))$

[0073] Now, if .sub.D=(P.sub.D,Q.sub.D) is a mixture of projective measurements, we note that Q.sub.D=IP.sub.D, and therefore P.sub.D, Q.sub.D commute. In this case, .sub.D has a projective implementation, denoted ProjImp(.sub.D), which is defined as follows. Let S be the set of eigenvalues of P.sub.D, and R.sub.i for i the projectors onto the associated eigenspaces. Then ProjImp(.sub.D) is the projective measurement (P.sub.i).sub.iS. Note that S[0, 1]. Also note that applying .sub.D is equivalent to the following: first apply ProjImp(.sub.D) to obtain outcome p, then interpret p as a probability and output 1 probability p.

[0074] [Zhandry, Theorem 6.2] For any , , , D, there exists an algorithm operating on and making quantum queries to , D which additionally outputs a number in some set S[0, 1] such that: [0075] There is a function R=poly(1/, log(1/)) such that the expected number of calls makes to and D, the running time of , and |S| are all bounded by R. [0076] is (, )-almost projective. [0077] , ProjImp(.sub.D)).

[0078] [Zhandry, Theorem 6.5] Let be an efficiently constructible mixed state over , and D.sub.0, D.sub.1 efficiently sampleable, computationally indistinguishable distributions. For any inverse polynomial , there exists a negligible such that .sub.(ProjImp(.sub.D.sub.0)(), ProjImp(.sub.D.sub.0)()).

3 Cryptographic Notions

3.1 IPP Codes

A fingerprinting code is used to fingerprint data. Fingerprinting codes have long been used to build traitor tracing schemes. Note, however, that the fingerprinting codes explicitly cited in the literature are usually binary codes. Yet, the schemes provided can be generalized to non-binary codes, but require a different kind of code called an identifiable parent property (IPP) code. We will use this generalization in order to abstract more schemes from the literature, so we here define IPP codes rather than fingerprinting codes. Note that the two notions coincide for binary codes.

[0079] An IPP code is a pair (Gen.sup.IPP, Trace.sup.IPP) of PPT algorithms such that: [0080] Gen.sup.IPP(1.sup., 1.sup.N, 1.sup.c) takes as input a security parameter, a number of users N, and a collusion bound c. It outputs a tracing key tk, as well as N strings w.sub.1, . . . , w.sub.N . The w.sub.i are called codewords [0081] Trace.sup.IPP(tk, w*) takes as input the tracing key and a codeword w*. It outputs a set A[N].

[0082] For a set of codewords C, let F(C) be the feasible set of C, which is defined as follows. A codeword w*{?} is in F(C) if, for each position j[], either w.sub.j*=? or there exists a codeword wC such that w.sub.j*=w.sub.j. In other words, F(C) consists of all codewords in C, plus all codewords that can be obtained from C by potentially using a different codeword character in each position. Additionally, any entry can be set to ?. The condition of being in the feasible set of C is also called the marking condition.

[0083] Where IPP codes differ from fingerprinting codes is in this marking condition. For a fingerprinting code, in any position where {w.sub.j}.sub.wC is not a single character, w.sub.j* is allowed to be anything. This condition better reflects the use in fingerprinting. However, the marketing condition for IPP codes better reflects the use in traitor tracing.

[0084] An IPP code (Gen.sup.IPP, Trace.sup.IPP) is -robust if, for all (potentially unbounded) algorithms .sup.IPP, for all polynomially bounded N, c, and for all S[N], .sup.IPP wins the following experiment with probability at most 2.sup.: [0085] Run (tk, {w.sub.i}.sub.i[N])Gen.sup.IPP(1.sup., 1.sup.N, 1.sup.c) [0086] Run w*.sup.IPP({w.sub.i}.sub.iS) [0087] If the number of ? in in w* is more than , output lose and stop. [0088] Otherwise, run ATrace.sup.IPP(tk, w*) [0089] Output win if (1) w*F({w.sub.i}.sub.iS) (w* is feasible for the set of codewords given to .sup.IPP), and (2) either A= or A/S.
Instantiations. In the case of binary alphabets, -robust IPP codes are also fingerprinting codes. Optimal fingerprinting codes with constant have =(c.sup.2.sup.2). In the case of non-binary alphabets, less is known about IPP codes. However, the main traitor tracing scheme of Chor, Fiat, and Naor can be seen as employing IPP codes with =0 and various parameters choices for , , including =(c), ||=(c.sup.2).
3.2 Traitor Tracing with Quantum Decoders
We follow the definitions of traitor tracing given by Zhandry. The text is mostly taken from Zhandry, except we adjust the syntax to accommodate both ordinary and embedded-identity traitor tracing. A traitor tracing system for identity space is a tuple .sup.TT=(Gen.sup.TT, Derive.sup.TT, Enc.sup.TT, Dec.sup.TT, Trace.sup.TT) defined as follows: [0090] Gen.sup.TT(1.sup.) is a classical probabilistic polynomial time (PPT) algorithm that takes as input the security parameter, and samples a public key pk and master secret key msk. [0091] Derive.sup.TT(msk, id) is a classical PPT algorithm that takes as input the master secret key msk and an identity id, and outputs a user secret key sk.sub.id. [0092] Enc.sup.TT(pk, m) is a classical PPT algorithm that takes as input the public key pk and a message m, and outputs a ciphertext c. [0093] Dec.sup.TT(sk.sub.id, c) is a classical deterministic algorithm that takes as input a secret key sk.sub.id for user id and a ciphertext, and outputs a message m. [0094] Trace.sup.TT(pk, m.sub.0, m.sub.1, 1.sup.1/, |D) is a QPT algorithm that takes as input the public key pk, two messages m.sub.0, m.sub.1, and a parameter (whose reciprocal is an integer represented in unary), and a quantum state |D representing a pirate decoder. It ultimately outputs a subset of , which are the accused users. Here, m.sub.0, m.sub.1 are two messages whose ciphertexts |D supposedly distinguishes, and is a supposed lower bound on the distinguishing advantage.
We next define correctness and security. A traitor tracing system .sup.TT is correct if, for all messages m and identities id,

[00005]$\mathrm{Pr}\left[{\mathrm{Dec}}^{\mathrm{TT}}\left({\mathrm{sk}}_{\mathrm{id}},{\mathrm{Enc}}^{\mathrm{TT}}\left(\mathrm{pk},m\right)\right)=m:\begin{array}{c}\left(\mathrm{pk},\mathrm{msk}\right){\mathrm{Gen}}^{\mathrm{TT}}\left(1^{}\right)\\ {\mathrm{sk}}_{\mathrm{id}}{\mathrm{Derive}}^{\mathrm{TT}}\left(\mathrm{msk},\mathrm{id}\right)\end{array}\right]1-\mathrm{negl}\left(\right)$

[0095] We now discuss security, adapting the software decoder model version of the definition of Zhandry. For a decoder |D, two messages m.sub.0, m.sub.1, and public key pk, consider the operation on |D: [0096] Choose a random bit b{0, 1}. [0097] Run cEnc.sup.TT(pk, m.sub.b) to get a random encryption of m.sub.b. [0098] Run b|D(c). [0099] Output 1 if and only if b=b; otherwise output 0.

[0100] Let .sup.TT=(M.sub.0, M.sub.1) be the POVM given by this operation, which we call the associated POVM to the decoder. .sup.TT has a projective implementation ProjImp(.sup.TT)={M.sub.p}.sub.p, where each M.sub.p corresponds to the probability distribution on {0, 1} that is 1 with probability p.

Tracing Experiment. For an adversary .sup.TT, function (), and security parameter , we consider the following experiment on .sup.TT: [0101] Run (pk, msk)Gen.sup.TT(1.sup.), and send pk to .sup.TT. [0102] .sup.TT then makes an arbitrary number of classical queries on identities id; in response it receives sk.sub.id. Let S be the set of id queried by .sup.TT. [0103] Next, .sup.TT outputs (|D, m.sub.0, m.sub.1) for decoder |D and messages m.sub.0, m.sub.1. [0104] Apply the measurement ProjImp(.sup.TT) to |D, obtaining a probability p. Let Live.sub..sup.TT be the event that p+. [0105] Finally run ATrace.sup.TT(pk, m.sub.0, m.sub.1, 1.sup.1/, |D) to get a set of accused users. Let Fail.sub..sup.TT as the event that A/S (an accused user was not one of the queried users). We define the event Success.sub..sup.TT as the event that A (some user is accused).

[0106] A tracing system is quantum traceable if for all quantum polynomial time adversaries .sup.TT and for every inverse polynomial , there is a negligible negl such that Pr[Fail.sub..sup.TT]<negl() and Pr[Live.sub..sup.TTSuccess.sub..sup.TT]negl().

Variations. The usual setting of traitor tracing has I=[N] for a polynomial N. In this case, we often set N to be an explicit input to Gen.sup.TT, and the parameters of the scheme may depend on N. A bounded collusion traitor tracing scheme additionally has another parameter c given to Gen.sup.TT, and security only is required to hold if |S|c. Traitor tracing with embedded identities has for ={0, 1}.sup.n for integer n. Therefore, identities are now polynomial-length strings. Here, n may be an input to Gen.sup.TT and the parameters of the scheme may depend on n. Note that some versions of embedded identity traitor tracing will have ={0, 1}*, meaning there is no a priori bound on the length of identity strings. Finally, we consider schemes with private tracing, where Gen.sup.TT outputs a special tracing key tk, which is inputted into Trace.sup.TT, and security only holds if tk is kept secret.

3.3 Defining Differing Inputs Obfuscation.

We now define differing-inputs obfuscation (diO) in the quantum setting. To the best of our knowledge, diO has not been defined in the quantum setting, and it turns out that the task is somewhat subtle. Below, we adapt the definition of traitor tracing for quantum decoders to give a strong definition of quantum-secure diO.

[0107] Let m(), n(), s() be polynomials, and consider a quantum polynomial time algorithm Samp(1.sup.) which samples (1) a pair of circuits C.sub.0, C.sub.1 of size s(), input length n() and output length m(), and (2) a quantum side information aux. Consider a distinguishing adversary . Consider the following operation on aux: [0108] Choose a random bit b{0, 1}. [0109] Run diO(1.sup.,C.sub.b) to get an obfuscation of a random choice of C.sub.0, C.sub.1. [0110] Run b(, C.sub.0, C.sub.1, aux). [0111] Output 1 if and only if b=b; otherwise output 0.

[0112] Let .sup.diO=(M.sub.0, M.sub.1) be the POVM given by this operation, which we call the associated POVM to the sampler. .sup.diO has a projective implementation ProjImp(.sup.diO)={M.sub.p}.sub.p, where each M.sub.p corresponds to probability distribution on {0, 1} that is 1 with probability p.

[0113] Now consider an extractor which takes as input C.sub.0, C.sub.1, aux as well as a parameter whose reciprocal is inputted in unary (so 1.sup.1/), so that if runs in polynomial time, then it runs in time polynomial in whenever is an inverse polynomial in . We define the following experiment, parameterized by S, , as well as a function : [0114] Run (C.sub.0,C.sub.1,aux)S(1.sup.). Let be the register containing aux. [0115] Apply ProjImp(.sup.diO) to , resulting in probability p. [0116] If

[00006]$p>\frac{1}{2}+\left(\right),$

we say that event Live.sub..sup.diO happens. [0117] Next, run on , obtaining an input x or symbol [0118] If x but C.sub.0(x)=C.sub.1(x), we say event Fail.sub..sup.diO happens. [0119] If x and C.sub.0(x)C.sub.1(x), we say event Success.sub..sup.diO happens.

[0120] [Post-Quantum Differing-inputs Obfuscation] A post-quantum differing-inputs obfuscator (diO) is a PPT algorithm diO such that: [0121] diO(1.sup., C) is equivalent to C with overwhelming probability over the randomness of diO. [0122] For every QPT adversary and sampler S, there exists a QPT such that for every inverse polynomial function =(), there exists a negligible negl=negl() such that Pr[Fail.sub..sup.diO]<negl and Pr[Live.sup.diOSuccess.sub..sup.diO]<negl.

4 Hidden Partitions and the BOS Model

A partition of a set T is a collection of subsets ={S.sub.1, . . . , S.sub.n} such that T=.sub.iS.sub.i and the S.sub.i are disjoint. The sets S.sub.i are called parts of . Given partition ={S.sub.1, . . . , S.sub.n} of T and ={S.sub.1, . . . , S.sub.n,} of T, we can define the product partition of TT as ={S.sub.iS.sub.j}.sub.(i,j)[n][n]. We can similarly define the product of several partitions.
The basic setup. Fix a set , a distinguished element, and .Math. a distinguished subset. Also fix a relation R(, w) that takes as input partitions of and strings w{0, 1}* and outputs a bit.

4.1 The Quantum Hidden Partition Problem

Given , , , R as above, consider a QPT S(1.sup.), called a quantum hidden partition sampler (QHPS) that samples (|P, , , aux)S(1.sup.) such that: [0123] |P is a quantum state program taking inputs in some domain X and outputting a bit. [0124] is a partition of , and [0125] :.fwdarw.X{0, 1} is a PPT algorithm mapping to X{0, 1}.

[0126] Now consider two experiments involving a QHPS S and a quantum adversary . The first, called the sink indistinguishability experiment, works as follows: [0127] First run (|P, , )S(1.sup.), and give |P to . [0128] Throughout, may make classical queries to , sending q, and receiving independent samples (x, b)(q). Repeated queries on the same q will give independent samples. [0129] Eventually outputs a sink q*. In response, run (x*, b*)(q) and send x* to . [0130] Outputs a guess b for b*. The experiment outputs o=bb*;
We say wins the sink indistinguishability experiment if o=0 (equivalently, b=b*).

[0131] The second experiment, called the partition indisitnguishability experiment, works as follows: [0132] First run (|P, , )S(1.sup.), and give |P to . [0133] Throughout, may make classical queries to , sending q, and receiving independent samples (x, b)(q). [0134] Eventually outputs two queries q.sub.0*, q.sub.1*. If q.sub.0*, q.sub.1* are in the same part of , output a random bit o and abort. Otherwise, choose a random bit c and run (x, b)(q.sub.c*) and send (x*, b*) to . [0135] outputs a guess c for c. The experiment outputs o=cc; wins if o=0.
We say wins the partition indistinguishability experiment if o=0.

[0136] S is a valid QHPS if for any QPT adversaries, .sub.0, .sub.1, there exists negligible functions negl.sub.0, negl.sub.1 such that the probability .sub.0 wins the sink indistinguishability experiment is at most negl.sub.0(), and the probability .sub.1 wins the partition indistinguishability experiment is at most negl.sub.1().

[0137] Consider the POVM which runs (x, b)(), and run |P(x) to obtain a bit b. The POVM outputs 1 if b=b. This POVM has a projective implementation, which we denote ProjImp(()). Now, consider the following experiment with algorithm : [0138] First run (|P, , )S(1.sup.). [0139] Next apply ProjImp(()) to the register containing |P, obtaining probability p. [0140] Run on 1.sup.1/ and . can make queries to . Importantly, on query q, can obtain a superposition of samples from (q). The output is a string w or an abort symbol .

[0141] Let Live.sub..sup.BOS be the event that

[00007]$p\frac{1}{2}+.$

The event Live.sub..sup.BOS corresponds to |P being able to predict the bit b with advantage at least . Let Success.sub..sup.BOS be the event that outputs a w such that R(, w)=1, and let Fail.sub..sup.BOS be the event that outputs a w such that R(, w)=0.

[0142] , , , R is solvable if there exists a (|P, ) that runs in time polynomial in and 1/ and makes quantum queries to , such that for any valid QHPS S and inverse-polynomial there is a negligible negl such that Pr[Live.sub..sup.BOS Success.sub..sup.BOS]negl() and Pr[Fail.sub..sup.BOS]negl(). In other words, should almost always succeed if |P starts out live, and should almost never output a w that is not accepted by R (outputting instead if it cannot succeed).

4.2 The BOS Model

Now consider a stateful interactive potentially randomized algorithm O which takes as a secret input a partition H, and then receives a sequence of queries q.sub.1, q.sub.2, . . . and produces a corresponding sequence of outputs o.sub.1, o.sub.2, . . . {0,1}. We will denote an interactive algorithm interacting with O and outputting w as wO().

[0143] O is a BOS oracle if, for any partition and any poly-length sequence of queries q.sub.1, q.sub.2, . . . , O() satisfies each of the following guarantees: [0144] Accepts first distinguished query. If q.sub.1=, then o.sub.1=1. [0145] Rejects sinks. For any i, if q.sub.i, then o.sub.i=0. [0146] Local consistency. For any two consecutive queries q.sub.i, q.sub.i+1, if q.sub.i, q.sub.i+1P (that is, if q.sub.i,q.sub.i+1 are in the same part of the partition ), then o.sub.i=o.sub.i+1. [0147] Single step rewinding. For any i, if q.sub.i+2=q.sub.i, then o.sub.i+2=o.sub.i.

[0148] A PPT algorithm solves R (with the associated , , ) in the BOS model if, for any BOS oracle O and any partition of Q, then Pr[R(, w)=1:wAO()]=1.

4.3 From BOS to Solving Quantum Hidden Partitions

Here, we present the main technical tool of this paper:

[0149] For any R, , , R, , if there exists an algorithm which solves R in the BOS model in polynomial time, then R, , , is solvable. We now prove Theorem 4.3. We first assume without loss of generality that has the following properties: [0150] q.sub.1=, To see why this is without loss of generality, let solve R in the BOS model, and let be , except that if the first query is not , inserts a dummy query to as the first query, and then ignores the response. It is easy to see that the oracle seen by as a subroutine of is still a BOS algorithm, and so still solves R. [0151] If o.sub.i=0, then q.sub.i+1=q.sub.i1. A simple inductive argument then shows that any o.sub.i=0 is always preceded by an o.sub.i1=1. To see why this is without loss of generality, let solve R in the BOS model, and let be except that if o.sub.i=0 and q.sub.i+1q.sub.i1, then makes a final query on q.sub.i1, immediately stops making queries (including not querying on q.sub.i+1), and answers every subsequent query by with 0. The oracle seen by as a subroutine of is still a BOS algorithm, so still solves R. But the new will always query on q.sub.i+1=q.sub.i1 if o.sub.i=0.
We call an with the above properties normal form.

[0152] We describe the algorithm given a normal form : Let be any normal form algorithm in the BOS model. Consider a quantum program |P stored in register . First, define the following: [0153] Let r be an upper bound on the number of queries made by . [0154] Let =/r,=2.sup.,T=1/{square root over ()}. [0155] Let Pred={Pred.sub.x}.sub.x be the collection of projective measurements applied to corresponding to running |P on input x. [0156] Let EST(q) be the algorithm API.sub./4,.sup.Pred,.sup.(q), where API is the algorithm in Lemma 2. We will dilate EST(q) so that it is a projective measurement. This means that EST(q) acts on-register .sub.w, where .sub.q are the anilla registers used to purify, with a different register used for every query.
We now give the algorithm (|P, 1.sup.1/). Run , which makes queries q.sub.1, q.sub.2, . . . , q.sub.r. To answer each query q.sub.i, do the following: [0157] 1. Define p.sub.q.sub.0=+. [0158] 2. If q.sub.iq.sub.i2: [0159] (a) Create the register .sub.q.sub.i, replacing any existing register with that name. [0160] (b) Then run EST(q.sub.i), obtaining measurement outcome p.sub.q.sub.i, replacing any existing value for p.sub.q.sub.i. [0161] (c) If p.sub.q.sub.ip.sub.q.sub.i1, answer the query with o.sub.q.sub.i=0. [0162] (d) If p.sub.q.sub.i>p.sub.q.sub.i1, answer the query with o.sub.q.sub.i=1. [0163] (e) If i=1 and o.sub.q.sub.1=0 (that is, this is the first query and the query response is 0) then immediately abort and output . [0164] 3. Otherwise, if q.sub.i=q.sub.i2: [0165] (a) Run the algorithm

[00008]${\mathrm{Repair}}_{T,p_{q_{i-1}},p_{q_{i-2}}}^{\mathrm{EST}\left(q_{i-1}\right),\mathrm{EST}\left(q_{i-2}\right)}.$ [0166] (b) Update p.sub.q.sub.i to P.sub.q.sub.i2, and answer the query with o.sub.q.sub.i=o.sub.q.sub.i2.
When terminates and outputs w, outputs w.

[0167] We now prove that solves , , , R. We first need the following lemma:

[0168] Suppose does not abort in Step 2e. Then except with negligible probability, every query q.sub.i that responds with 1 will have p.sub.q.sub.i+i. We prove by induction on i. Since p.sub.q.sub.0=+, does not abort in Step 2e only if p.sub.q.sub.1>p.sub.q.sub.0=+1. Now we inductively assume the lemma holds for all queries before query i, and prove it holds for query i. We break into three cases: [0169] q.sub.i=q.sub.i2. In this case, o.sub.q.sub.i=o.sub.q.sub.i2, so if responds with 1, then must have responded two queries ago with 1 as well. By the inductive hypothesis, this means p.sub.q.sub.i2+(i2). But now we update p.sub.q.sub.i to p.sub.q.sub.i2+(i1)+i. [0170] q.sub.iq.sub.i1, and o.sub.q.sub.i1=1. In this case, by induction, we have p.sub.q.sub.i1+(i1). If o.sub.q.sub.i=1, then it must be that q.sub.iq.sub.i1+i. [0171] q.sub.iq.sub.i2 and o.sub.q.sub.i1=0. By the assumption that is valid, this is impossible.
This completes the proof of Lemma 4.3. We now prove the following lemma: If does not abort in Step 2e, then except with negligible probability the oracle presents to is a BOS oracle. We prove the properties of a BOS oracle. [0172] First distinguished query: Recall we assumed q.sub.1=. If does not abort in Step 2e, then responds to the query with 1. [0173] Sinks: Consider a query q.sub.i . We claim that EST(q.sub.i) gives measurement outcome p.sub.q.sub.i that is at most

[00009]$\frac{1}{2}+{}^{},$

except with negligible probability. First consider replacing EST(q.sub.i)=API.sub./4,.sup.Pred,.sup.(q.sup.i.sup.) (which produces p.sub.q.sub.i) with ProjImp((q.sub.i)), giving outcome p. By Lemma 2, since .sub./4(EST(q.sub.i), ProjImp((q.sub.i)), we have |pp.sub.q.sub.i|</4 except with negligible probability. [0174] Then we note that p must be at most +negl+/4, except with negligible probability. Indeed, if this were not the case, then the bit b produced by (q) could be predicted with non-negligible by probability. Thus we have that

[00010]$.Math.p_{q_i}-\frac{1}{2}.Math.{}^{}/2{}^{}/4.$ Now that

[00011]$p_{q_i}\frac{1}{2}+{}^{},$ we use Lemma 4.3. If o.sub.q.sub.i=1, then p.sub.q.sub.i+i+r>+1 since (r+1)<, we therefore have that o.sub.q.sub.i must be 0. [0175] Local consistency: Suppose q.sub.i, q.sub.i+1 lie in the same part of . We claim that the measurement outcomes p.sub.q.sub.i and p.sub.q.sub.i+1 satisfy p.sub.q.sub.i+1p.sub.q.sub.i. Indeed, consider replacing EST(q.sub.i+1)=API.sub./4,.sup.Pred,.sup.(q.sup.i.sup.) (which produces p.sub.q.sub.i+1) with each of the following: [0176] EST(q.sub.i)=API.sub./4,.sup.Pred,.sup.(q.sup.i.sup.), given outcome p. Since the last measurement on was also EST(q.sub.i), by being almost projective via Lemma 2, we have |pp.sub.q.sub.i|</4 except with negligible probability. [0177] ProjImp((q.sub.i+1)), giving p. Again by Lemma 2, since .sub./4(EST(q.sub.i), ProjImp((q.sub.i)), we have |pp|</4 except with negligible probability. [0178] ProjImp ((q.sub.i+1)), giving p. Since q.sub.i, q.sub.i+1 are in the same part of , the distributions (q.sub.i) and (q.sub.i+1) are computationally indistinguishable. Therefore, by Lemma 2, |pp|/4 except with negligible probability. [0179] EST(q.sub.i+1), giving p.sub.q.sub.i+1. As above, by Lemma 2, we have |p.sub.q.sub.i+1p|/4 except with negligible probability. Putting the above inequalities together shows that |p.sub.q.sub.i+1p.sub.q.sub.i| except with negligible probability. [0180] Single-step Rewinding: If q.sub.i=q.sub.i2, then Lemma 2 and the fact that EST(q.sub.i) is almost projective immediately gives us that |p.sub.q.sub.ip.sub.q.sub.i2|/2 except with probability N+N/T+4{square root over ()}=N+(N+4){square root over ()}, which is negligible.
One issue with the above proof is that in order to actually turn a bit predictor in the sink proof or a distinguisher in the local consistency proof into algorithms for the sink and partition indistinguishability games, the adversary needs to be able to run API, which in turn needs to get superpositions of samples from (q). While is allowed such queries, we do not allow adversaries for the sink and partition indistinguishability games such quantum access. However, following Zhandry, we can simulate such superpositions of samples with a polynomial number of samples, thus getting an algorithm for these games which only makes classical queries. This completes the proof of Lemma 4.3.

[0181] Now suppose Live.sup.BOS happens. In this case, by Lemma 2, .sub./4(EST(), ProjImp(())). This means, except with negligible probability , p.sub.=p.sub.q.sub.1 will be at least /4p.sub.q.sub.0. Thus, will not abort in Step 2e. Therefore, by Lemma 4.3, presents a BOS oracle to , meaning outputs a w such that R(, w)=1. Thus Live.sub..sup.BOSSuccess.sub..sup.BOS happens except with negligible probability.

[0182] We now turn to proving that Fail.sub..sup.BOS happens with negligible probability. For Fail.sub..sup.BOS to happen, we must have (1) that does not abort in Step 2e, and (2) that fails to output a w such that R(,w)=1. But by Lemma 4.3, if does not abort, then it presents a BOS oracle to except with negligible probability, meaning R(, w)=1. Thus Fail.sub..sup.BOS happens with negligible probability. This completes the proof of Theorem 4.3.

5 Post-Quantum Tracing with Embedded Identities
Here, we show how to build embedded identity traitor tracing from functional encryption, specifically a special case called private linear broadcast encryption (PLBE). PLBE with polynomial index space was first formalized by Boneh, Sahai, and Waters to build ordinary traitor tracing in the classical setting, and the result was upgraded to the quantum setting by Zhandry, though only in the setting of polynomial identity spaces. Using PLBE with exponential index space to build embedded identity traitor tracing was proposed by Nishimaki, Wichs, and Zhandry for the classical setting. Here, we upgrade their result to the quantum setting.

[0183] Let .sup.FE be a functional encryption scheme. We construct the traitor tracing scheme .sup.TT=(Gen.sup.TT, Derive.sup.TT, Enc.sup.TT, Dec.sup.TT, Trace.sup.TT), where we define Gen.sup.TT, Derive.sup.TT, Enc.sup.TT, Dec.sup.TT below:

[00012]${\mathrm{Gen}}^{\mathrm{TT}}\left(1^{},N\right)={\mathrm{Gen}}^{\mathrm{FE}}\left(1^{}\right){\mathrm{Derive}}^{\mathrm{TT}}\left(\mathrm{msk},\mathrm{id}\right)={\mathrm{Derive}}^{\mathrm{FE}}\left(\mathrm{msk},f_{\mathrm{id}}\right)\mathrm{where}{f}_{\mathrm{id}}\left(x,m\right)=\{\begin{array}{cc}m& \mathrm{if}x\mathrm{id}\\ & \mathrm{otherwise}\end{array}{\mathrm{Enc}}^{\mathrm{TT}}\left(\mathrm{pk},m\right)={\mathrm{Enc}}^{\mathrm{FE}}\left(\mathrm{pk},\left(N,m\right)\right){\mathrm{Dec}}^{\mathrm{TT}}\left({\mathrm{sk}}_{\mathrm{id}},c\right)={\mathrm{Dec}}^{\mathrm{FE}}\left({\mathrm{sk}}_{\mathrm{id}},c\right)$

5.1 The Hidden Partition

We use the hidden partition .sup.Bnd, .sup.Bnd, .sup.Bnd, R.sup.Bnd. We now explain how Construction 5 leads to an instance of the quantum hidden partition problem relative to this partition. We interpret an adversary .sup.TT interacting in the tracing experiment as a quantum hidden partition sampler S.sup.TT, where |P is the decoder |D outputted by .sup.TT, is the contiguous partition whose boundaries are the identities queried by .sup.TT. Finally , on input q, encrypts (q, m.sub.b) for a random choice of b to get ciphertext c, and outputs (c, b).

[0184] Assuming .sup.FE is an adaptively secure FE scheme, the QHPS S.sup.TT is valid for .sup.Bnd, .sup.Bnd, .sup.Bnd, R.sup.Bnd. The unique sink is 0, and note that encryptions of (0, m) computationally hide m, since the only secret keys are f.sub.id for id>0. Thus the probability the adversary can predict b (and therefore win the sink indistinguishability experiment) is at most +negl.

[0185] Next, observe that encryptions of (q, m) and (q, m) for q>q decrypt identically under any secret key except those for id in the interval [q, q1]. Thus, by FE security, the encryptions are indistinguishable unless the adversary has an id[q, q1], meaning no efficient adversary can distinguish query responses from the same part of . Therefore, the probability of winning the partition indistinguishability experiment is +negl.

[0186] Assuming .sup.FE is an adaptively secure FE scheme Construction 5 is quantum traceable. Let(|P, 1.sup.1/) be the algorithm guaranteed by Theorem 4.3 and the existence of .sup.Bnd. Then set Trace.sup.TT(pk, m.sub.0, m.sub.1, 1.sup.1/, |D) to be (|D, 1.sup.1/) where is the sampler above obtained from pk, m.sub.0, m.sub.1. Now consider the events Live.sub..sup.BOS, Success.sub..sup.BOS, Fail.sub..sup.BOS for the QHPS described above, and the events Live.sub..sup.TT, Success.sub..sup.TT, Fail.sub..sup.BOS for the tracing experiment with .sup.TT from Construction 5. We see that the events exactly coincide; in particular D() is identical to running Enc.sup.TT(pk, m.sub.b) for a random choice of b. Thus, by the guarantees of Theorem 4.3, .sup.TT in Construction 5 is secure.

6 Traitor Tracing from Collusion-Resistant IPP Codes
It was previously shown how to construct collusion-secure traitor tracing with constant-sized ciphertexts from binary fingerprinting codes. The scheme, described momentarily, naturally generalizes to larger alphabets (at the cost of larger ciphertexts). However, the code needed for the generalization is not a fingerprinting code, but a collusion resistant identifiable parent property (IPP) code, which has a different marking condition. It turns out that IPP codes and fingerprinting codes coincide for binary codes. But by generalizing to larger alphabets (and using IPP codes) we can abstract other existing combinatorial schemes in the literature such as Chor, Fiat, and Naor.

[0187] We now recall the scheme, which is parameterized by a parameter t.

[0188] Let (Gen.sup.PK, Enc.sup.PK, Dec.sup.PK) be a public key encryption scheme and (Gen.sup.IPP, Trace.sup.IPP) a -robust fingerprinting code. Define the following algorithms, which depend on a parameter that may be a function of , , : [0189] Gen.sup.TT(1.sup.,1.sup.N, 1.sup.c): Run (tk,w.sub.1, . . . , w.sub.N)Gen.sup.IPP(1.sup., 1.sup.N, 1.sup.c). For [] and , run (ek.sub.j,, dk.sub.j,)Gen.sup.PK(). Output [0190] pk=.sub.(the public key) [0191] tk=.sub., tk) (the tracing key) [0192] sk.sub.i=, w.sub.i) for [N] (the secret key for user ) [0193] where N is the total identity space, and c is the collision bound. [0194] Enc.sup.TT(pk, m): Choose a random subset T.Math.[] of size t. Let m.sub.j, T be a t-out-of-t secret sharing of m: m.sub.j are uniform conditioned on .sub.jTm.sub.j=m. For each jT, , compute c.sub.j,=Enc.sup.PK(ek.sub.j,, m.sub.j). Output c=(T, {c.sub.j,}.sub.jT,). [0195] Dec.sup.TT(sk.sub.i,c): For each jT, run m.sub.jDec.sup.PK(dk.sub.j,w.sub.i,j,w.sub.i,j). Then output m=.sub.jTm.sub.j.
Quantum Tracing Challenges. In the classical setting, tracing works by first extracting a codeword w* from the decoder D, and then traces w* using the fingerprinting code. The first step is accomplished roughly by replacing c.sub.i, with junk and seeing if D still decrypts. Based on this information, the tracer can determine if w.sub.i* should be one of the symbols in or ?. By doing this for each i[], the tracer extracts an entire codeword w*.

[0196] We can easily mimic the above strategy in the quantum setting to derive a measurement for each i which computes w.sub.i*. The problem is that the measurements for each i might be incompatible, which means that the tracing algorithm cannot apply these measurements simultaneously. If applied sequentially, it could be that after computing the first several positions, the decoder becomes dead. There is no guarantee that an entire codeword w* can be computed.

[0197] More abstractly, any tracing algorithm that works within the globally consistent hidden partition model is likely only able to extract logarithmically many bits, which is insufficient for obtaining a full codeword for the fingerprinting code.

6.1 The Hidden Partition

We will assume the alphabet is equal to [1, s]. Let Prod=[0, s] and .sup.Prod=. Let Q.sub..sup.Prod be the set of vectors w where the number of 0's is more than . We call a partition of valid if it is equal to a product partition .sub.1 . . . where each .sub.i is a contiguous partition of [0, s].

[0198] Given a valid partition, let (a.sub.i,j).sub.j for [] the boundaries of .sub.i. Let R.sub..sup.Prod(, w) be the following relation: [0199] Output 1 if is not valid. [0200] Output 1 if (1) is valid with boundaries (a.sub.i,j).sub.i,j, (2) for all [], w.sub.i=? or w.sub.i (a.sub.i,j).sub.j, and (3) the number of ? in w is at most . [0201] Output 0 in all other cases.

[0202] The first condition means that we trivially win for all non-valid , and can focus on the case of valid , where the goal is to find a string w that does not have too many ? and matches the boundaries of the product partition.

[0203] We now explain how the tracing experiment for Construction 6 leads to a QHPS relative to (.sup.Prod, .sup.Prod, .sub..sup.Prod, R.sub..sup.Prod). Given an adversary .sup.TT, we define the QHPS S.sup.Prod as follows: first run the tracing experiment with .sup.TT, until .sup.TT outputs (|D, m.sub.0*, m.sub.1*). Then set |P=|D. Let S be the set of id queried by .sup.TT, and let S be the corresponding set of codewords in the IPP code given to the users in S. Let be the valid partition generated by S.

[0204] Finally, let (q) be the algorithm which does the following: choose a random subset T.Math.[] of size t. Choose a random bit b, and let m=m.sub.b*. Then let m.sub.j, T be a t-out-of-t secret sharing of m: m.sub.j are uniform conditioned on .sub.jTm.sub.j=m. For each jT, , compute

[00013]$c_{j,}=\{\begin{array}{cc}{\mathrm{Enc}}^{\mathrm{PK}}\left({\mathrm{ek}}_{j,},m_j\right)& \mathrm{if}{q}_j\\ {\mathrm{Enc}}^{\mathrm{PK}}\left({\mathrm{ek}}_{j,},0\right)& \mathrm{otherwise}\end{array}$

Output c=(T, {c.sub.j,}.sub.jT,) and b. In other words, (q) outputs an encryption of a random choice of m.sub.b*, except that it replaces the ciphertext components c.sub.j, with junk (importantly, independent of b) if q.sub.j<.

[0205] The QHPS then outputs (|P, , ).

[0206] Assuming .sup.PK is semantically secure and either (1) t(1) or (2)

[00014]$\left(\begin{array}{c}\left(1-\right)\\ t\end{array}\right)/\left(\begin{array}{c}\\ t\end{array}\right)$

is negligible, then S.sup.Prod is valid for .sup.Prod, .sup.Prod, .sup.Prod, R.sup.Prod. Let q.sup.Prod. Then q has strictly more than zeros; call this set . If T0, then the share m.sub.j inside T is information-theoretically hidden given c. Since the m.sub.j form a t-out-of-t secret sharing, this means if T, then b is statistically hidden. Thus, to prove the sink indistinguishability problem is hard, we just need to show that T0 with overwhelming probability. A simple combinatorial argument shows that

[00015]$\mathrm{Pr}\left[T\right]=1-\mathrm{Pr}\left[T\right]=1-\frac{\left(\begin{array}{c}-.Math..Math.\\ t\end{array}\right)}{\left(\begin{array}{c}\\ t\end{array}\right)}1-\frac{\left(\begin{array}{c}\left(1-\right)-1\\ t\end{array}\right)}{\left(\begin{array}{c}\\ t\end{array}\right)}=1-\left(\frac{\left(1-\right)-t}{\left(1-\right)}\right)\left(\frac{\left(\begin{array}{c}\left(1-\right)\\ t\end{array}\right)}{\left(\begin{array}{c}\\ t\end{array}\right)}\right)$

[0207] If t>(1), then

[00016]$\left(\begin{array}{c}\left(1-\right)\\ t\end{array}\right)=0.$

If t=(1), then (1)t=0. In either case, Pr[T]=1. Alternatively, if

[00017]$\left(\begin{array}{c}\left(1-\right)\\ t\end{array}\right)/\left(\begin{array}{c}\\ t\end{array}\right)$

is negligible, then Pr[T]1negl. Thus, under the conditions of Lemma 6.1, the sink indisitnguishability problem is hard.

[0208] We now turn to the partition indisitnguishability experiment. Suppose q.sub.1, q.sub.2 are in the same part of , and consider the distributions (q.sub.1) and (q.sub.2). We will argue they are indistinguishable. Toward that end, consider some j[]. Since q.sub.1, q.sub.2 are in the same part of , then q.sub.1,j and q.sub.2,j are in the same part of .sub.j. If we assume w log that q.sub.1,jq.sub.2,j, then .sub.i has no boundary in (q.sub.1,j,q.sub.2,j]. Now consider a ciphertext component c.sub.j,. If q.sub.1,j, then the distributions of c.sub.j, under .sub.(q.sub.1) and (q.sub.2) are identical. Likewise if >q.sub.2,j. On the other hand, for (q.sub.1,j, q.sub.2,j), .sup.TT does not have the secret key dk.sub.j,. By the semantic security of .sup.PK, the adversary cannot distinguish c.sub.j, under (q.sub.i) and (q.sub.2).

[0209] By a hybrid over all j, no efficient adversary can distinguish (q.sub.1) from (q.sub.2), proving the hardness of the partition indistinguishability experiment.

6.2 The BOS Algorithm

[BOS Algorithm .sup.Prod] Initialize x[0, ], and set x=. Now query on x, which by definition gives 1. Then do the following for i=1, . . . , +1: [0210] 1. For a=s, . . . , 1: [0211] (a) Set x=x, except that x.sub.i is set to a1. [0212] (b) Query on x, receiving response o. [0213] (c) If o=0, query on x, break the loop in Step 1, and proceed to the next iteration of the main loop over i. [0214] (d) Otherwise, set x=x, and proceed to the next iteration of the loop over a in Step 1. [0215] 2. If the loop in Step 1 terminated with all responses o being 1, then set x.sub.i=0. Then proceed to the next iteration of the main loop over .
In the end, output w, which is x but with every 0 replaced by ?.

[0216] .sup.Prod solves (.sup.Prod, .sup.Prod, .sup.Prod, R.sub..sup.Prod) in the BOS model. We maintain the invariant that each time we exit an iteration of the main loop over i, the last query was on x and the response was 1. There are two cases: [0217] We exited the iteration from Step 1c. But in this step we query on x, so x is the most recent query at exit. Moreover, x was queried in the last iteration of the loop over a in Step 1, and the result must have been 1 in order to proceed to this iteration. Therefore, x was queried two queries ago and resulted in response 1. By single step rewinding, the latest query on x must also give 1. [0218] We existed the iteration from Step 2. But here the most recent query was on x, it resulted in query response 1, and in Step 1d we set x=x.

[0219] We also see that if we exit the loop of Step 1 via Step 1c, then the adjacent queries x and x resulted in different outcomes, meaning a is a boundary of .sub.i.

[0220] The result is that the final x is a string where all the non-zero terms are boundaries of the respective component partition, and x.Math..sup.Prod (since the query output was no 0), meaning the number of 0's in x is at most . Thus when we replace 0's with ?'s to get w, we have that R.sup.Prod(, w)=1. We finally note that the number of queries .sup.Prod makes is at most O(s), which is polynomial.

[0221] Assuming .sup.PK is a secure PKE scheme, Construction 6 is quantum traceable.

7 Tracing Embedded Identities with Short Ciphertexts
In Construction 5 from Section 5, the string x is n bits long, where n is the bit length of identities. It is also part of the message inputted to Enc.sup.FE of the underlying functional encryption scheme. Therefore, the ciphertext size must grow with the bit length of identities. As observed by Nishimaki, Wichs, and Zhandry, this is not inherent to traitor tracing. They instead propose a different structure where ciphertexts may be independent of the identity length. We now recall their construction:

[0222] Let .sup.FE be a functional encryption scheme. We construct the traitor tracing scheme .sup.TT=(Gen.sup.TT, Derive.sup.TT, Enc.sup.TT, Dec.sup.TT, Trace.sup.TT), where we define Gen.sup.TT, Derive.sup.TT, Enc.sup.TT, Dec.sup.TT below: [0223] Gen.sup.TT(1.sup.)=Gen.sup.FE(1.sup.) [0224] Derive.sup.TT(msk, id): choose a random [N] where N=2.sup.. Then return sk.sub.,id

[00018]${\mathrm{Derive}}^{\mathrm{FE}}\left(\mathrm{msk},f_{,\mathrm{id}}\right)\mathrm{where}{f}_{,\mathrm{id}}\left(i,x,m\right)=[\begin{array}{cc}m& \mathrm{if}x2*-{\mathrm{id}}_i\\ & \mathrm{otherwise}\end{array}.$

Note here that x[0,2N]=[0,2.sup.+1] and i[n], so the inputs to Enc.sup.TT are bounded by O() bits long, independent of n. Thus if .sup.FE has succinct ciphertexts, so will .sup.TT. [0225] Enc.sup.TT(pk, m)=Enc.sup.FE(pk, (1, N, m)) [0226] Dec.sup.TT(sk.sub.,id, c)=Dec.sup.FE(sk.sub.,id, c)
Tracing. The classical ideal behind the structure above is the following: first apply the tracing algorithm for Construction 5 setting i=1. The result is that the tracing algorithm outputs 2id.sub.1 from some secret key. Since id.sub.1 is a single bit, this reveals uniquely both and the first bit of the associated identity. Then, by varying i and testing on ciphertexts encrypting (i, 21, m), one can learn the rest of the bits of id. Essentially, we know if the first phase accused 2id.sub.1, there must be a gap in the success probabilities of the decoder on encryptions of (1,2id.sub.1, m) and (1,2id.sub.11, m). Call these two probabilities p.sub.0 and p.sub.1, respectively, which are far apart. Since the of various secret keys are unique whp, by the security of functional encryption, we know that the decryption probability for (i, 2id.sub.i, m) must be close to p.sub.0, and the decryption probability for (i, 2id.sub.i1, m) must be close to p.sub.1. Put another way, the decryption probability for (i, 21, m) will be close to p.sub.1id.sub.i, thus revealing id.sub.i.

[0227] Quantumly, we can employ the same strategy to recover , id.sub.1. However, recovering the rest of the bits of id will not work as in the classical case. This is because the probabilities p.sub.0, p.sub.1 may change as we further interrogate the decoder, so we cannot simply compare with the previous value. We therefore need to develop a new quantum algorithm for the problem.

7.1 The Hidden Partition

Let Q.sup.Short=[n][0,2N] where N=2.sup.. Let .sup.Short=(1,2N). Let .sup.Short={(i,0)}. Consider a sequence (.sup.(1), id.sup.(1)), . . . , (.sup.(t), id.sup.(t)) where id.sup.(j){0, 1}* and .sup.(j) [N] with .sup.(1)<.sup.(2)< . . . <.sup.(t). This gives rise to a partition ={S.sub.0, . . . , S.sub.t} of Q.sup.Short consisting of sets S.sub.j={(i,x):2.sup.(j)id.sub.i.sup.(j)x<2.sup.(j+1)id.sub.i.sup.(j+1)} for j=1, . . . , t1, S.sub.0={(i,x): x<2.sup.(1)id.sub.i.sup.(1)}, and S.sub.t={(i,x):2.sup.(t)id.sub.i.sup.(t)x}. We call of this form contiguous, and we call (.sup.(j), id.sup.(j)) the boundaries of . Let R.sup.Short(, w) be the following relation: [0228] Output 1 if is not valid [0229] Output 1 if is valid, and w is a boundary of . [0230] Output 0 if is valid but w is not a boundary of .

[0231] We now explain how Construction 7 leads to the quantum hidden partition problem relative to this partition. We interpret an adversary .sup.TT interacting in the tracing experiment as a quantum hidden partition sampler S.sup.TT, where |P is the decoder |D outputted by .sup.TT, is the contiguous partition whose boundaries are the identities queried by .sup.TT. Finally , on input (i, q), encrypts ((i, q), m.sub.b) for a random choice of b to get ciphertext c, and outputs (c, b).

[0232] Assuming .sup.FE is a secure FE scheme, the QHPS is valid for .sup.Short, .sup.Short, .sup.Short, R.sup.Short The sinks have the form (i, 0), and note that encryptions of ((i, 0), m) computationally hide m, since the only secret keys are f.sub.id for id>0. Thus the probability the adversary can predict b (and therefore win the sink indistinguishability experiment) is at most +negl.

[0233] Next, observe that encryptions of ((i, q), m) and ((i, q), m) decrypt identically if (i, q) and (i, q) are in the same part of H. Thus, by FE security, the encryptions are indistinguishable if they lie in the same part. Therefore, the probability of winning the partition indistinguishability experiment is +negl.

7.2 The BOS Algorithm

[BOS Algorithm .sup.Short] Initialize integers a, b[0, 2N] and i[n]. Set a=2N, b=0, and query on (1, a), which by definition gives response o=1. Then do the following for at most O(kn log.sup.2 N) steps, where k in an upper bound on the number of parts in : [0234] 1. Query on (1, b), obtaining response o. [0235] 2. If o=1, set (a, b)=(b,0) and go to Step 1. [0236] 3. Else (o=0): [0237] (a) If b(a1): Query on (1,a), set b=(a+b)/2 (a remains unchanged), and go to Step 1. [0238] (b) Else (b=a1): Query on (1, a), parse a as 2id.sub.1, and do the following for i=2, . . . , n: [0239] i. Query on (i, 21), receiving response o. [0240] ii. If o=0, query on (1, a), set id.sub.i=0, and proceed to the next i. [0241] iii. Else (o=1): [0242] A. Query on (i, 22), receiving response d. [0243] B. If o=0, set id.sub.i=1, query on (i, 21) and then (1, a) and proceed to the next i. [0244] C. Else (o=1), set (a, b)=(a1, 0), clear , id, exit the loop over i in Step 3b, and go to Step 1. [0245] If the loop over i in Step 3b completes (that is, if we never have o=1), output (, id).

[0246] .sup.Short solves (.sup.Short, .sup.Short, .sup.Short, R.sup.Short) in the BOS model. We will eventually find a, b=a1 where the previous query was on (1, a1) and gave 0, and the query before was on (1,a) and gave 1. This is Step 3b. By local consistency, a=2id.sub.1 for some (, id) that defined the partition. We then query on (1, a) again, which by single step rewinding gives 1.

[0247] It remains to show that id is obtained in its entirety. This is done by trying to ascertain if (i, 21) lies in the same part as (1, a) or (1, a1). This is done by querying on (i,21). If the result is 0 (Step 3(b)ii), we know by local consistency (and the fact that the last query was on (1, a) and gave 1) that (i, 21) cannot be in the same part as (1, a). So we set id.sub.i=0 and move on to the next bit of id. In order to guarantee that the last query response was 1, we query again on (1, a), which, by single-step rewinding will give 1.

[0248] If o=1, we do not immediately learn which part (i, 21) is in. So we also query on (i, 22) to get response o (Step 3(b)iiiA). If the response is now 0, we know that (i,21) and (i, 22) are in different parts, meaning (i, 21) is in the same part as (1, a). Thus we set id.sub.i=1 and move on to the next bit of id (Step 3(b)iiiB). But first we query again on (i, 21), which by single-step rewinding gives 1. Then we query on (1, a), which gives 1 by local consistency.

[0249] If on the other hand the response o is once again 1, then we learn nothing about id.sub.i. However, in this case, we have exactly the setup of a new hidden partition with N=1. In particular, we know there must be a (, id) with <. We therefore proceed back to Step 1 but with the new N=1. A simple inductive argument shows that we will eventually find such a (, id). This completes the proof.

[0250] Assuming FE, Construction 7 is quantum traceable. Let (|P, 1.sup.1/) be the algorithm guaranteed by Theorem 4.3 and the existence of .sup.Short. Then set Trace.sup.TT(pk, m.sub.0,m.sub.1, 1.sup.1/, |D) to be (|D, 1.sup.1/) where is the sampler obtained from pk, m.sub.0, m.sub.1 described in Section 7.1. Now consider the events Live.sub..sup.BOS, Success.sub..sup.BOS, Fail.sub..sup.BOS for the QHPS described in Section 7.1, and the events Live.sub..sup.TT, Success.sub..sup.TT, Fail.sub..sup.TT for the tracing experiment with .sup.TT from Construction 7; in particular D() is identical to running Enc.sup.TT(pk, m.sub.b) for a random choice of b. We see that the events exactly coincide. Thus, by the guarantees of Theorem 4.3, .sup.TT in Construction 7 is secure.

Example Systems and Apparatuses of the Present Disclosure

Referring to FIG. 1, a block diagram of a quantum computer tracer apparatus is depicted. The diagram illustrates the flow of information between a Quantum Decoder Program, a Translator Algorithm with an embedded State Repair Procedure, and a Query Generator Algorithm, culminating in the identification of a Traitor User Identity. The Quantum Decoder Program feeds into the Translator Algorithm, which interacts with the Query Generator Algorithm by receiving inputs and sending back queries. The State Repair Procedure is a component within the Translator Algorithm that contributes to the process leading to the determination of the Traitor User Identity.

[0251] In some aspects, the Translator Algorithm and the Query Generator Algorithm may be instantiated, forming a computer tracer apparatus. The Translator Algorithm may receive a decoder program and generate responses to queries based on a set of rules, which may include a state repair procedure. In some cases, the Translator Algorithm may produce a final output based on the final output from the Query Generator Algorithm and store this as the identity of one or more traitor users.

[0252] Upon receiving a query from the Query Generator Algorithm, the Translator Algorithm may perform the state repair procedure or may not, depending on the queries received by that time. The Translator Algorithm may then respond to the query with 0 or 1 based on a computation involving the query and the decoder.

[0253] The state repair procedure may receive as input a quantum decoder as a quantum system and two quantum measurements M1, M2 whose outputs are real numbers between 0 and 1, and a threshold. The state repair procedure may modify the decoder in order to increase the value produced by M1. The state repair procedure may then alternatively apply M1, M2, M1, M2, . . . , and terminate when an application of M1 produces an output above the threshold.

[0254] In some aspects, the translator algorithm may include a probability estimation procedure. This procedure may execute based on a query, denoted as qi, and using the decoder program. The outcome of this procedure, denoted as pqi, may be a real number between 0 and 1. Based on previous outputs of the probability estimation procedure, the translator algorithm may set an output, denoted as oqi, to be either 0 or 1.

[0255] In some cases, the query generator algorithm may execute by initializing two integers, denoted as a and b, to be a value N and 0, respectively, where N is determined based on system parameters. The query generator algorithm may then produce a query, denoted as qi, which is set to b. Upon obtaining a response, denoted as o, the query generator algorithm may adjust the integers a and b based on the response. If the response o equals 1, the query generator algorithm may set a to be b and b to be 0, and then proceed to generate a new query. Otherwise, if b equals a minus 1, the query generator algorithm may output a as the final output. If b does not equal a minus 1, the query generator algorithm may produce a new query qi, set b to be the integer part of the sum of a and b divided by 2, and then proceed to generate a new query. This process may continue until a final output is produced by the query generator algorithm.

[0256] To accomplish this, the parties may use any of the computer systems, including the communications networks, described herein.

[0257] FIG. 2 illustrates a block diagram of a system that may be specially configured within which embodiments of the present disclosure may operate. Specifically, FIG. 2 depicts an example system 100. The example system 100 includes a client device 104 and a quantum computing system 102. The client device 104 and quantum computing system 102 are communicable via a communications network 106. It should be appreciated that, in other embodiments, the system 100 includes one or more additional and/or alternative devices, which may operate independently and/or communicate with other devices of the system.

[0258] In some embodiments the client device 104 embodies one or more computing devices embodied in hardware, software, firmware, and/or any combination thereof. The client device 104 may be embodied by a user device configured to provide various functionality. In this regard, the client device 104 may embody a conventional computing environment that interacts with the quantum computing system 102. Non-limiting examples of a client device 104 include a specially configured mobile device, tablet, smartphone, personal computer, laptop, enterprise terminal, and/or the like. In some embodiments, the client device 104 is configured entirely by specially configured software application(s) installed to and/or otherwise executable via the client device 104 to provide various functionality for accessing and/or otherwise controlling the quantum computing system 102 as described herein. In various embodiments, the client device 104 is a conventional and/or classical computer.

[0259] In some embodiments, the client device 104 includes specially configured hardware, software, firmware, and/or a combination thereof, that enables access to and/or configuration of the quantum computing system 102. In some embodiments, the client device 104 provides access to functionality for generating and/or retrieving a quantum program for execution via a quantum computer of the quantum computing system 102. In this regard, the client device 104 may receive one or more user input(s) for constructing and/or that otherwise embody the quantum program to be executed. In this regard, a user of the client device 104 may interact with the client device 104 to construct a quantum circuit, store the quantum circuit, and submitting the quantum circuit for execution via a quantum computing system, such as the quantum computing system 102. In some embodiments, the client device 104 is embodied by a user-facing device of the quantum computing system 102, for example such that communications can occur without requiring the communications network 106.

[0260] Alternatively or additionally, in some embodiments, the client device 104 enables user input and/or output for accessing the quantum computing system 102 to execute a quantum program. In some embodiments, the client device 104 communicates with one or more computing devices of the quantum computing system 102, such as a controller, that generates and/or compiles instructions for executing via a quantum computer. For example, in some embodiments, the quantum computing system 102 includes a controller that receives the quantum program from the client device 104 and compiles it to produce control system instructions embodying hardware manipulation instructions for running the quantum program on a specific quantum computer. In some embodiments, the controller is embodied by one or more computing devices external from but communicable with the quantum computing system 102. For example, the controller may be embodied by a circuit compiler embodied in a dedicated computing system embodied in hardware, software, firmware, and/or a combination thereof internal or external to the quantum computing environment 102, dedicated hardware communicable with a quantum computer of the quantum computing system 102, software executing on a computing system communicable with the quantum computer of the quantum computing system 102, and/or the like,

[0261] The quantum computing system 102 may include one or more computing device(s) that enable compilation of a quantum program and/or use of a quantum computer for preforming a quantum program. In some embodiments, for example, the quantum computing system 102 includes a controller, a quantum computing environment, and various devices for physically manipulating the quantum computer. The quantum computing environment may include an ion trap architecture (e.g., linear, loop, and/or the like) for storing and manipulating qubits for gating. The controller may embody one or more computing device(s) embodied in hardware, software, firmware, and/or a combination thereof, that control the various devices that manipulate the quantum computer. Such control device(s) may include laser(s), cooling device(s), and/or the like. In some embodiments, the controller embodies a conventional computing system, for example specially configured via one or more specialized software application(s) to execute one or more process(es) that determine positions for the qubits at various time steps and/or instructions for repositioning the qubits to such position. For example, the controller may determine position assignments for each qubit at various time steps, and/or instructions embodying swap commands to cause the qubits to reach such positions at each of the appropriate time steps. In some embodiments, one or more device(s) of the quantum computing system 102 (e.g., a controller) receive data from the client device 104 that embodies the quantum program, instructions to be performed to manipulate the quantum computer, and/or the like.

[0262] FIG. 3 illustrates a block diagram of an example apparatus for global qubit placement assignment that may be specially configured in accordance with at least some example embodiment of the present disclosure. In some embodiments, the controller of the quantum computing system 102 is embodied by one or more computing systems, such as the apparatus 300 as depicted and described in FIG. 3. The apparatus 300 includes processor 302, memory 304, input/output circuitry 306, communications circuitry 308, and qubit positioning circuitry 310. The apparatus 300 may be configured, using one or more of the sets of circuitry 302, 304, 306, 308, and/or 310, to execute the operations described herein.

[0263] Although components are described with respect to functional limitations, it should be understood that the particular implementations necessarily include the user of particular computing hardware. It should also be understood that certain of the components described herein may include similar or common hardware. For example, two sets of circuitry may both leverage use of the same processor(s), network interface(s), storage medium(s), and/or the like, to perform their associated functions, such that duplicate hardware is not required for each set of circuitry. The user of the term circuitry as used herein with respect to components of the apparatuses described herein should therefore be understood to include particular hardware configured to perform the functions associated with the particular circuitry as described herein.

[0264] Particularly, the term circuitry should be understood broadly to include hardware and, in some embodiments, software for configuring the hardware. For example, in some embodiments, circuitry includes processing circuitry, storage media, network interfaces, input/output devices, and/or the like. Alternatively or additionally, in some embodiments, other elements of the apparatus 300 may provide or supplement the functionality of another particular set of circuitry. For example, the processor 302 in some embodiments provides processing functionality to any of the sets of circuitry, the memory 304 provides storage functionality to any of the sets of circuitry, the communications circuitry 308 provides network interface functionality to any of the sets of circuitry, and/or the like.

[0265] In some embodiments, the processor 302 (and/or co-processor or any other processing circuitry assisting or otherwise associated with the processor) may be in communication with the memory 304 via a bus for passing information among components of the apparatus 300. In some embodiments, for example, the memory 304 is non-transitory and may include, for example, one or more volatile and/or non-volatile memories. In other words, for example, the memory 304 in some embodiments includes or embodies an electronic storage device (e.g., a computer readable storage medium). In some embodiments, the memory 304 is configured to store information, data, content, applications, instructions, or the like, for enabling the apparatus 300 to carry out various functions in accordance with example embodiments of the present disclosure.

[0266] The processor 302 may be embodied in a number of different ways. For example, in some example embodiments, the processor 302 includes one or more processing devices configured to perform independently. Additionally or alternatively, in some embodiments, the processor 302 includes one or more processor(s) configured in tandem via a bus to enable independent execution of instructions, pipelining, and/or multithreading. The use of the terms processor and processing circuitry may be understood to include a single core processor, a multi-core processor, multiple processors internal to the apparatus 300, and/or one or more remote or cloud processor(s) external to the apparatus 300.

[0267] In an example embodiment, the processor 302 may be configured to execute instructions stored in the memory 304 or otherwise accessible to the processor. Alternatively or additionally, the processor 302 in some embodiments is configured to execute hard-coded functionality. As such, whether configured by hardware or software methods, or by a combination thereof, the processor 302 may represent an entity (e.g., physically embodied in circuitry) capable of performing operations according to an embodiment of the present disclosure while configured accordingly. Alternatively or additionally, as another example in some example embodiments, when the processor 302 is embodied as an executor of software instructions, the instructions may specifically configure the processor 302 to perform the algorithms embodied in the specific operations described herein when such instructions are executed.

[0268] As one particular example, the processor 302 may be configured to perform various operations associated with improved traitor tracing, for example as described with respect to operation of the quantum computing system 102 and/or as described further herein.

[0269] In some embodiments, the apparatus 300 includes input/output circuitry 306 that may, in turn, be in communication with processor 302 to provide output to the user and, in some embodiments, to receive an indication of a user input. The input/output circuitry 306 may comprise one or more user interface(s) and may include a display that may comprise the interface(s) rendered as a web user interface, an application user interface, a user device, a backend system, or the like. In some embodiments, the input/output circuitry 306 may also include a keyboard, a mouse, a joystick, a touch screen, touch areas, soft keys a microphone, a speaker, or other input/output mechanisms. The processor 302 and/or input/output circuitry 306 comprising the processor may be configured to control one or more functions of one or more user interface elements through computer program instructions (e.g., software and/or firmware) stored on a memory accessible to the processor (e.g., memory 304, and/or the like). In some embodiments, the input/output circuitry 306 includes or utilizes a user-facing application to provide input/output functionality to a client device and/or other display associated with a user.

[0270] The communications circuitry 308 may be any means such as a device or circuitry embodied in either hardware or a combination of hardware and software that is configured to receive and/or transmit data from/to a network and/or any other device, circuitry, or module in communication with the apparatus 300. In this regard, the communications circuitry 308 may include, for example, a network interface for enabling communications with a wired or wireless communication network. For example, the communications circuitry 308 may include one or more network interface card(s), antenna(s), bus(es), switch(es), router(s), modem(s), and supporting hardware, firmware, and/or software, or any other device suitable for enabling communications via one or more communication network(s). Additionally or alternatively, the communications circuitry 308 may include circuitry for interacting with the antenna(s) and/or other hardware or software to cause transmission of signals via the antenna(s) or to handle receipt of signals received via the antenna(s). In some embodiments, the communications circuitry 308 enables transmission to and/or receipt of data from a client device in communication with the apparatus 300.

[0271] It should be appreciated that, in some embodiments, qubit positioning circuitry 310 may include a separate processor, specially configured field programmable gate array (FPGA), or a specially programmed application specific integrated circuit (ASIC). Additionally or alternatively, in some embodiments, one or more of the sets of circuitries 302-310 are combinable. Alternatively or additionally, in some embodiments, one or more of the sets of circuitry perform some or all of the functionality described associated with another component. For example, in some embodiments, one or more of the sets of circuitry 302-310 are combined into a single module embodied in hardware, software, firmware, and/or a combination thereof. Similarly, in some embodiments, one or more of the sets of circuitry, for example qubit positioning circuitry 310 is combined such that the processor 302 performs one or more of the operations described above with respect to each of these modules.

[0272] Referring to FIG. 4, the figure illustrates classical computing components. These components may be part of a classical system, such as the client device 104 or the quantum computing system 102, as depicted in FIG. 2. The classical computing components may include various hardware and software elements that facilitate the operation of the classical system. These elements may include, but are not limited to, processors, memory units, input/output devices, and communication interfaces. In some cases, these classical computing components may execute algorithms, such as the query generator algorithm described earlier, and process data received from or sent to the quantum computing system 102. In other cases, the classical computing components may facilitate user interaction with the quantum computing system 102 or other devices or systems connected to the network cloud 106.

[0273] Referring now to FIG. 5, the figure illustrates additional classical computing components. These components may be part of a classical system, such as the client device 104 or the quantum computing system 102, as depicted in FIG. 2. The classical computing components may include various hardware and software elements that facilitate the operation of the classical system. These elements may include, but are not limited to, processors, memory units, input/output devices, and communication interfaces. In some cases, these classical computing components may execute algorithms, such as the query generator algorithm described earlier, and process data received from or sent to the quantum computing system 102. In other cases, the classical computing components may facilitate user interaction with the quantum computing system 102 or other devices or systems connected to the network cloud 106.

[0274] A number of implementations have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the disclosure. Accordingly, other implementations are within the scope of the following claims.

[0275] Although an example processing system has been described above, implementations of the subject matter and the functional operations described herein can be implemented in other types of digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them.

[0276] Embodiments of the subject matter and the operations described herein can be implemented in digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Embodiments of the subject matter described herein can be implemented as one or more computer programs, i.e., one or more modules of computer program instructions, encoded on computer storage medium for execution by, or to control the operation of, information/data processing apparatus. Alternatively, or in addition, the program instructions can be encoded on an artificially-generated propagated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal, which is generated to encode information/data for transmission to suitable receiver apparatus for execution by an information/data processing apparatus. A computer storage medium can be, or be included in, a computer-readable storage device, a computer-readable storage substrate, a random or serial access memory array or device, or a combination of one or more of them. Moreover, while a computer storage medium is not a propagated signal, a computer storage medium can be a source or destination of computer program instructions encoded in an artificially-generated propagated signal. The computer storage medium can also be, or be included in, one or more separate physical components or media (e.g., multiple CDs, disks, or other storage devices).

[0277] The operations described herein can be implemented as operations performed by an information/data processing apparatus on information/data stored on one or more computer-readable storage devices or received from other sources.

[0278] The term data processing apparatus encompasses all kinds of apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, a system on a chip, or multiple ones, or combinations, of the foregoing. The apparatus can include special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit). The apparatus can also include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a repository management system, an operating system, a cross-platform runtime environment, a virtual machine, or a combination of one or more of them. The apparatus and execution environment can realize various different computing model infrastructures, such as web services, distributed computing and grid computing infrastructures.

[0279] A computer program (also known as a program, software, software application, script, or code) can be written in any form of programming language, including compiled or interpreted languages, declarative or procedural languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, object, or other unit suitable for use in a computing environment. A computer program may, but need not, correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or information/data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, sub-programs, or portions of code). A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network.

[0280] The processes and logic flows described herein can be performed by one or more programmable processors executing one or more computer programs to perform actions by operating on input information/data and generating output. Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and information/data from a read-only memory or a random access memory or both. The essential elements of a computer are a processor for performing actions in accordance with instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive information/data from or transfer information/data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto-optical disks, or optical disks. However, a computer need not have such devices. Devices suitable for storing computer program instructions and information/data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto-optical disks; and CD-ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry.

[0281] To provide for interaction with a user, embodiments of the subject matter described herein can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information/data to the user and a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input. In addition, a computer can interact with a user by sending documents to and receiving documents from a device that is used by the user; for example, by sending web pages to a web browser on a user's client device in response to requests received from the web browser.

[0282] Embodiments of the subject matter described herein can be implemented in a computing system that includes a back-end component, e.g., as an information/data server, or that includes a middleware component, e.g., an application server, or that includes a front-end component, e.g., a client computer having a graphical user interface or a web browser through which a user can interact with an implementation of the subject matter described herein, or any combination of one or more such back-end, middleware, or front-end components. The components of the system can be interconnected by any form or medium of digital information/data communication, e.g., a communication network. Examples of communication networks include a local area network (LAN) and a wide area network (WAN), an inter-network (e.g., the Internet), and peer-to-peer networks (e.g., ad hoc peer-to-peer networks).

[0283] The computing system can include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other. In some embodiments, a server transmits information/data (e.g., an HTML page) to a client device (e.g., for purposes of displaying information/data to and receiving user input from a user interacting with the client device). Information/data generated at the client device (e.g., a result of the user interaction) can be received from the client device at the server.

[0284] While this specification contains many specific implementation details, these should not be construed as limitations on the scope of any disclosures or of what may be claimed, but rather as descriptions of features specific to particular embodiments of particular disclosures. Certain features that are described herein in the context of separate embodiments can also be implemented in combination in a single embodiment. Conversely, various features that are described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable subcombination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a subcombination or variation of a subcombination.

[0285] Similarly, while operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system components in the embodiments described above should not be understood as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.

[0286] Thus, particular embodiments of the subject matter have been described. Other embodiments are within the scope of the following claims. In some cases, the actions recited in the claims can be performed in a different order and still achieve desirable results. In addition, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In certain implementations, multitasking and parallel processing may be advantageous.