In a criminal case, if the government wants to read the contents of your encrypted phone or laptop, can they compel you to enter or disclose your password? If so, when? The question sounds simple, but it doesn't have an answer. Instead, it has too many answers.
In the past few years, several state supreme courts in the United States have grappled with this question and reached wildly different rulings. The Massachusetts Supreme Judicial Court found that you can be compelled to enter your password to decrypt the hard drive contents [9, 10], whereas the Indiana Supreme Court reached the opposite conclusion [35]. The New Jersey Supreme Court ruled that you can even be forced to disclose your password [36], whereas the Pennsylvania Supreme Court ruled that passwords themselves cannot be compelled [8]. Conflicting decisions also exist among federal circuit courts [19,40] and district courts (e.g., [20,34,44,47]).
The confusion stems from disagreement about how to adapt the law of pre-digital act of production cases, where the government compels production of physical documents (see e.g., [13,43,46]). How should we overcome this physical-digital divide? Most prior work starts from the notion that encryption isn't fully understood within the law, and reasons about how encryption technology is analogous to-or fundamentally different from-physical acts of production. This article pursues a different path: we use the fact pattern of compelled decryption as a means to interrogate our understanding of the act of production doctrine generally.
The foregone conclusion doctrine. This work exclusively considers the law in the United States, where the government's ability to compel an action is substantially limited by the Fifth Amendment to the U.S. Constitution [39]. The Fifth Amendment prohibits the government from compelling an individual to provide selfincriminating testimony, such as oral or written statements that "disclose the contents of his own mind" [11].
Moreover, the government cannot compel an individual-who we call the respondent-to perform an action which, by its very performance, would reveal implicit testimony. But there's a catch: an action that communicates implicit testimony can be compelled if all the implicit testimony is already a "foregone conclusion. " If the government knows it, the implicit testimony would "add[] little or nothing to the sum total of the Government's information" about the respondent's mind [13], and the government would in no way be "relying on the truthtelling" of the respondent. This idea is called the foregone conclusion doctrine and stems from the 1976 Supreme Court case Fisher v. United States [13].
Complementing the law with computer science. This work pursues a formal (in the computer science sense) investigation of the foregone conclusion doctrine. Our target is a specification of the relevant law, written in the language of math and cryptography, that captures a meaningful and coherent version of the foregone conclusion doctrine. Our objective for doing so is to to gain a deeper understanding of the foregone conclusion doctrine in order to reason clearly and consistently about compelled decryption under varying present and future fact patterns.
We don't want to mechanize the law. Law is flexible and adapts to new situations, and attempts to encode society's rules into a rigid computer algorithm (aka, "code as law") typically don't end well [28,52]. Hence, our pursuit of a computer science specification is not meant to replace the law, but to illuminate it. Courts and legal scholars disagree wildly about compelled decryption. Some of that is due to imperfect analogies. Some is genuine disagreement as to what the law is. Some is simply bad law. In many cases, it is unclear how the various approaches relate to one another or apply to alternative scenarios.
Our goal is to present our approach in enough detail that one can apply it to unforeseen facts and get a concrete answer. Other scholars can identify both if and where they disagree with our interpretation. We make no claims that our work is "the correct interpretation" of the doctrine. We do claim that it is reasonable and coherent, that it exposes the nuance and ambiguity in the law, and that it serves as a base for others to improve in the future.
Demonstrating foregone conclusions through verification. Consider a government actor G and a respondent R. The overarching question is whether the government can compel the respondent to perform a certain action A, such as producing documents or decrypting a computer. In this work, we specify A as an algorithm that can request inputs from the respondent's mind, like the document's location or the computer's password. If this action involves explicit testimony, then it is strictly forbidden and the concept of foregone conclusion is irrelevant.
Otherwise, to compel this action, the government must generally show two things. 1 First, the government must establish that the respondent can perform the action A by submitting some convincing evidence E to the court. Second, in compelling the respondent to perform the action, the government must not "rely on the truthtelling" of the respondent R.
A key insight from Fisher is that the government does not rely on R's truthtelling if it has some way of verifying that R performed the required action. The government's task is typically called "authentication" in legal scholarship because when A is an act of production then it corresponds to authenticating in the evidentiary sense. We generalize the concept because authentication of evidence is a poor fit when A is an act of performance instead; see §2 for details.
Our goal is to make Fisher's verification idea precise. One approach might be to require that the government specifies a procedure V that checks whether the respondent R has performed the action exactly. But this approach is too restrictive. For example, suppose the action is "enter a password into this password prompt. " Must R stand or sit? Eyes open or closed? Can R make a typo if it succeeds on the second try? Of course the government doesn't care about any of this -it just wants the password to be entered. Another approach might be for the government to specify a set of all acceptable actions, but this set is infinite. The upshot is that the government's interest lies in the ends, not the means, and we should approach the foregone conclusion doctrine accordingly.
Our insight is to flip A and V around. Rather than asking how to verify a particular action A, in this work we make the verification procedure V the centerpiece of any foregone conclusion claim. For example, rather than compelling the respondent to "enter a password, " instead the government compels the respondent to "do something that gets past the login prompt screen and to the point that we can open the file explorer. " It is then up to the respondent to choose any action A that conforms to this verifier V.
Making the verifier V the centerpiece of our specification immediately resolves cruel trilemma of "relying on the truthtelling. " The respondent is free to perform any action it wants so long as V accepts; there is no longer a question of honesty or evasion. The only remaining question is how to evaluate whether the respondent's task is feasible in the first place. We impose the weakest requirement: the government must demonstrate that, based on the evidence, the respondent can perform some action A * that V accepts. We call A * the exemplar action, and we call V demonstrable if it has such an exemplar action. In summary, our shift in focus from A to V changes how we view compulsion: instead of "is action A a foregone conclusion?" we ask "is verifier V demonstrable?" 1 These two things are neither necessary nor sufficient conditions for compelling an action. For example, they are not sufficient if the act is providing oral or written testimony, and they are not necessary if the act is not incriminating.
Meaningfulness. The cost of this shift in focus is a lack of clarity about what the government will get. Presumably the government has a target action T in mind that it really wants the respondent to perform. There are many demonstrable V's for any given scenario; for example, the trivial V that accepts any action is always demonstrable, but it provides no guarantee that the government will receive the result of T or anything remotely resembling it. Another example of a demonstrable-but-meaningless verifier is to compel the respondent to flip a coin and verify that the result is one of "heads" or "tails" (rather than, say, "42").
But sometimes, it may be possible to gather enough evidence and specify V in enough detail that the respondent must perform an action that is more-or-less equivalent to T . We call this property entailment and we codify the claim of "more-or-less equivalent" using the cryptographic notion of extraction. That is, V entails T if the government can transform the result of any conforming action into the fruits of the action T it desired all along.
Our contributions. This work makes several contributions in the domains of law and computer science.
• As a matter of law, we adopt a view of implicit testimony as comprised of dual but equally important parts: ex ante ability and ex post conformity. We also present a new verificationcentric approach to compelling acts while constructively satisfying the foregone conclusion doctrine ( §2). • We define the concepts of demonstrability and entailment within a formal computer science framework ( §3-5). The framework is expressive enough to capture, for example, the government's uncertainty as to whether an encryption scheme is deniable or not. • Connecting the computer science to the law, we investigate whether several acts involving cryptography are compellable within our framework ( §6 and Appendix A). Generally speaking, we believe that §2 will be of most interest to readers with a background in law, and §3-5 will appeal to a computer science audience. That said, we highlight some of the takeaways about the compellability of cryptography, for both audiences.
• Decryption by entering a password is entailable in the (typical) case that the encryption scheme is committing. This is true even when using two-factor authentication. More generally, opening commitments is generally entailable. • Our framework reaches a novel middle ground conclusion if decryption is deniable -meaning that it will reveal different files when given a duress password. • In contrast to decryption and opening commitments, the acts of encrypting and creating commitments are not entailable. • Hash functions add a twist: compelling preimages is demonstrable and-under a cryptographic assumption-entailable.
Comparison to prior work. This article is inspired by several recent works that codify legal principles with computer science techniques [1,4,5,14,22,29,30], including Scheffler and Varia's related work on compelled decryption [32] that we contrast with in §7. Additionally, this work is influenced by a large body of legal scholarship on compelled decryption [6, 23-27, 31, 37, 38, 51], some of which suggest broad powers to compel decryption and some argue that the government can only compel files that they already know with "reasonable particularity. "
Our framework generally aligns with the broader interpretation, and it considers all acts of performance beyond just the produced files. In the next section, we delve deeper into case law, scholarship, and the value of a verification-centric approach as a matter of law.
The question of deniable encryption highlights the differences between the current work and prior work (see Section 6.2). Deniable encryption introduces a duress password which, when entered, allows a device to be decrypted to something other than its true contents. In Comm. v Gelfgatt, the court simply ordered the respondent to use the true password rather than the duress password. 2 Sacharoff sets aside this "niche case because deniable encryption remains rare" [31]. Kerr argues that duress passwords are "unlikely to raise significant Fifth Amendment issues" because, if used, "the government will not realize what the user has done. " 3 Cohen and Park argue that the government would be unable to compel decryption without some way of distinguishing the respondent's use of the true and duress passwords [6].
In contrast, our framework would allow the government to compel the respondent enter one of the true or duress passwords, but the respondent would be free to choose. If the government also had evidence as the contents of the encrypted drive-say, specific filenames as in In re Boucher [20]-the government could require that the apparently-decrypted device contain the known files by checking for those files in the verification procedure. In such cases, our framework yields a procedure more like Sacharoff's and Cohen-Park's than Kerr's. But like Kerr, meaningful acts are compellable even without any specific knowledge of the device's contents.
This section gives a too-brief overview of the law of the foregone conclusion doctrine and of our new approach to that doctrine. A full treatment is out of scope in this paper. 4 The Fifth Amendment to the US Constitution provides individuals a privilege against being "compelled in any criminal case to be a witness against himself. " 5 Courts and legal scholars disagree about how this privilege applies to so-called compelled decryption cases, wherein the government seeks to compel an individual to unlock or decrypt an encrypted phone, computer, or hard drive. At issue is how the foregone conclusion test applies to the act of decryption. 2 Comm. v Gelfgatt [9] at note 10 (the decryption "protocol" states in relevant part: "The defendant shall manually enter the password or key to each respective digital storage device in sequence. . . . The defendant is expressly ordered not to enter a false or 'fake' password or key"). 3 Kerr [24] at note 78. It is not clear to what extent these are statements of legal doctrine (e.g., no implicit testimony at issue; the testimony is always a foregone conclusion) or of practical reality (e.g., the deniable encryption will be invisible and therefore will not be at issue in the proceedings). In one sense, Kerr agrees with us: when ordered to "bypass [the] password prompt" a respondent is free to use a duress password. But he seems to suggest that this is merely a de facto freedom, and that use of a duress password could "violate the Decryption Order. " Under this reading, an order forbidding the use of the duress password (as in Gelfgatt, note 2 above) may be permissible even if the government "will not realize what the user has done." In contrast, this paper argues that the decryption order can only forbid the use of a duress password if the government is able to verify whether or not the true password was used. Otherwise, the act of decrypting with the true password would communicate testimony as to conformity that is not a foregone conclusion. 4 A draft of a companion law review article was presented at the Privacy Law Scholars Workshop in 2021 [7]. 5 U.S. Const. Amend. V.
The Fifth Amendment's privilege applies only to acts that are "testimonial." 6 An act is testimonial when it "explicitly or implicitly[] relate[s] a factual assertion or disclose[s] information. " 7 As such, a person may be compelled to furnish a blood sample 8 or to put on a shirt 9 no matter how incriminating. But a person may not be compelled to make incriminating oral or written statements.
Implicit testimony and the foregone conclusion doctrine. An act may have "testimonial aspects" even if it does not involve any oral or written testimony as such. Fisher v. U.S. lays out a version of this idea now called the act of production doctrine. In Fisher, the government issued a subpoena to compel the defendant to produce certain documents. "The act of producing the documents has communicative aspects of its own, wholly aside from the contents of the papers produced. Compliance with the subpoena tacitly concedes the existence of the papers demanded and their possession or control by the [respondent]. It also would indicate the [respondent]'s belief that the papers are those described in the subpoena. " The lesson is that testimony may be implicit in an act. Fisher's examples-existence, possession, and authenticity-are an application of this idea to the specific act of producing physical evidence.
Fisher also introduced the foregone conclusion doctrine which provides a way for the government to compel an act of production despite the implicit testimony. Kerr gives a typical account of the doctrine [24]:
[W]hen the testimonial aspect of a compelled act "adds little or nothing to the sum total of the Government's information," any implied testimony is a "foregone conclusion" and compelling it does not violate the Fifth Amendment. . . . The Court [in Fisher] held that the testimony implicit in handing over the tax documents was a foregone conclusion because the government was "in no way relying on the 'truthtelling' of the [respondent]" to prove it. In other words, "A valid privilege exists only when the compelled act is testimonial under the act of production doctrine but is not a foregone conclusion" [24]. Importantly, the foregone conclusion doctrine only considers testimony implicit in an act. It does not apply to 'pure' oral or written testimony -no matter how foregone, pure testimony cannot be compelled. 10 And the foregone conclusion doctrine is unconcerned with information that may result from the act, but is not implied by the act. Borrowing an example from Kerr, the testimony implicit in the act of opening a door to a treasure filled room does not include the treasure itself, only the "door-opening" testimony. The value of the treasure is not relevant to the Fifth Amendment privilege. 6 Fisher v. United States, 425 U.S. 391, 408 (1976) [13] 7 United States v Doe, 487 U.S. 201, 208 (1988) [12] 8 Schmerber v. California, 384 U.S. 757, 763-764 (1966) [33] 9 Holt v. United States, 218 U.S. 245 (1910) [15] 10 Fisher, 258 U.S. [13] ("It is doubtful that implicitly admitting the existence and possession of the papers rises to the level of testimony within the protection of the Fifth Amendment" at 411; additionally "it [the subpoena to produce documents] does not compel oral testimony, nor would it ordinarily compel the taxpayer to restate, repeat, or affirm the truth of the contents of the documents sought[, t]herefore the Fifth Amendment would not be violated" at 409. These statements contrast this foregone conclusion doctrine against explicit compelled admittance of the existence and possession of the papers by oral testimony. Thus the foregone conclusion doctrine may compel only implicit testimony and not explicit oral testimony, even if that information is already known to the government.) Ability and conformity. Applying the foregone conclusion doctrine first requires answering the question: what are the implicit testimonial aspects in the act of decryption (or some other act of performance) [6,19,24]? This may sound easy, but it is where many compelled decryption analyses diverge. For example, Kerr concludes that " 'I know the password' is the only assertion implicit in unlocking the device" [24]. Cohen and Park respond that "[d]eniable encryption complicates the very notion of 'the' password by introducing an alternate duress password" that appears to decrypt but hides certain files [6].
We adopt the view that there are two types of testimony implicit in acts of performance: ability and conformity. By honestly performing an act specified by the government, a respondent implicitly asserts "I can do it" and "I did do it. " Ability-I can do it-is the respondent's ex ante belief that she is able to perform the compelled act. Conformity-I did do it-is the respondent's ex post belief that she did indeed perform the compelled act as specified. This view has appeared in prior works, though the terms are new. For example, Kerr describes these as the "two kinds of beliefs" implicit in a compelled act. 11 The importance of ability to the foregone conclusion doctrine is well accepted, and the notion of ability has evolved beyond its act-of-production genesis. For physical production of some object, ability amounts to the existence of the object and the respondent's possession and control thereof, Fisher [13]. For entering a password, ability often amounts to the respondent's knowledge of the password [24]. For decryption and production of encrypted drives, ability communicates the respondent's "possession, control, and access to the encrypted portions of the drives; and of his capability to decrypt the files" [19].
By contrast, conformity's role is often minimized or overlooked. Fisher and all subsequent caselaw and scholarship focus on only one aspect of conformity: authenticity. In Kerr's analysis, only ability informs his analysis of compelled decryption. 12 An act of production in response to a subpoena implicitly communicates "that the articles produced are the ones demanded" [50]. But while authenticity -whether something is what it purports to be -is appropriate for acts of production, it is an ill fit for acts of performance where the respondent must do something instead of produce something. Compelled decryption-say, by typing a password into an encrypted computer-is typically best treated as an of performance, not production. 13 We consider conformity as a generalization of authenticity that is relevant to acts of performance as well as production, and our work gives conformity equal consideration for the first time.
A key difference between how Kerr and Cohen-Park treat compelled password entry is the importance they attach to conformity [6,24]. Both agree on ability: the act of entering a password communicates knowledge of the password. But they disagree about conformity in the context of deniable encryption. Kerr dismisses it, stating that "the government will not realize what the user has done." Cohen and Park recognize that deniable encryption implicates conformity exactly because the government cannot tell what the user has done.
The foregone conclusion exception. Once the implicit testimonial aspects of the act of decryption are identified, the foregone conclusion doctrine asks: Are those aspects foregone conclusions [6,19,24]? Ability is a foregone conclusion if the government can demonstrate that the respondent can perform the action ex ante. Conformity is a foregone conclusion if the government can demonstrate ex ante that it will be able to verify whether the respondent performed the action ex post.
Ability raises no new difficulties. The government must show that the respondent can perform the act. Depending on the act, this amounts to showing that the papers exist and and are in his control [13,46]; that he knows the password (e.g. [8-10, 34, 42, 48]); or that he is able to speak, write, or make a gesture [33]. In our formalism, the government meets its ability burden by (1) describing an exemplar action that is "conforming" (see below), and (2) presenting evidence that the respondent is able to perform the exemplar action.
Conformity is more challenging. Conformity is a foregone conclusion if the government can demonstrate that it will be able to verify whether or not the respondent performed the compelled act after the fact. Our framework requires the government to specify the procedure it will use to verify the act, and deems any act that successfully verifies as conforming.
Under this approach, the verification procedure is the centerpiece of a motion to compel. The question of conformity is resolved by construction: any action that verifies, verifies. To show that ability is a foregone conclusion, the government must demonstrate that there exists a conforming exemplar action that the respondent can perform. If so, we say the verification procedure is demonstrable.
Our approach to conformity addresses a shortcoming in the status quo's treatment of conformity in the guise of authenticity. In compelled decryption cases to date, courts have generally dealt with authenticity in one of four unsatisfactory ways. (In each, replacing "authenticity" with "conformity" would not fix the problem.) First, ignore the issue altogether: "the authenticity element is routinely cited but only applied loosely if at all." 14 Second, defer the question to trial, which we fear could allow the government to make improper use of fruit of a poisonous tree. Third, hold that decryption is self-authenticating-a technological assertion that deniable encryption, for example, disproves. Fourth, attempt to reason about the production of some thing-a password, plaintext, or ciphertext -rather than the performance of an act, a confusing and unworkable approach. 15Conformity should not be a mere afterthought. Even before Fisher, Wigmore's Treatise on Evidence [50] states that production of documents or chattels may only be compelled from a respondent "without the use against him of process relying on his truthtelling. " Where conformity is not a foregone conclusion, the government would be improperly "relying on his truthtelling." This reliance is clear in Comm. v. Gelgatt, where the court simply ordered the respondent "[n]ot to enter a false or 'fake' password" although it could not check compliance. 16 Such orders revive the cruel trilemma that is at the heart of the religious tribunals that gave rise to the right to silence: the respondent must choose among perjury, contempt of court, and self-incrimination.
A new procedure for motions to compel. Based on our framework, we suggest a new procedure for motions to compel decryption or other acts of performance. First, the government makes a motion to compel. It specifies a verification procedure and demonstrates that the respondent is able to perform some exemplar action that verifies. To do so, the government must clearly detail the steps of both the verification procedure and the exemplar action in a manner understandable by the judge and the respondent. The exemplar action must be one that the government would have been able to compel if all implicit testimony was forgone. In particular, the exemplar cannot require explicit oral or written testimony. The government must also introduce any evidence that it needs to demonstrate the respondent's ability to perform the exemplar.
Second, the respondent may challenge the motion to compel in a few different ways. She may challenge the accuracy of the government's evidence. She may also argue that she cannot perform the exemplar action. Or she may argue that the Fifth Amendment privilege precludes the exemplar action for reasons other than implicit testimony. (The respondent may not appeal to conformity, which is foregone by construction.)
The court must then decide whether to quash the motion or to grant it by issuing an order. The order would compel the respondent to perform an action of his choosing that passes the governmentspecified verification procedure. The order would contain within it a complete description of the procedure and the exemplar action.
In the new procedure based on our framework, it is important for the order to clearly specify the evidence, method of verification, and exemplar. Doing otherwise would undermine the Fifth Amendment privilege. The resulting uncertainty would present the respondent with a cruel choice: either risk contempt for failing the verification procedure or risk disclosing implicit testimony which is not foregone. Moreover, the idea that the government must provide the verification procedure before compelling an action is already present in, for example, U.S. v Bright.foot_3 As an added benefit, a welldefined verification procedure might be relevant in disputes over the introduction or authentication of evidence at trial time.
Under our framework, the respondent can perform any act that passes the government's verification procedure. Presumably the government has in mind some target action that it wants the respondent to perform (e.g., the exemplar). But if the government cannot tailor its verification procedure appropriately, then the compelled act may be meaningless. If however the verification is tailored so as to require something "just as good" as the target, we say that the verification procedure entails the target.
For example, consider the verification procedures the government could use to compel decryption of a device encrypted using deniable encryption. It could, of course, check that the device appears to be logged in. However, compelling this would clearly allow a decryption under both the true and duress passwords to pass the verification procedure. Using the duress password is allowed-the respondent would not be acting untruthfully. But if the government had specific knowledge of a file visible only using the true password, then checking for that file would prevent the duress password's use.
In this section, we describe the formal model of computation that we consider in this work. It is inspired by the computation and communication model within Canetti's universal composability (UC) framework [2] and it directly extends the computational model used within Scheffler and Varia's prior work on compelled actions and foregone conclusions [32,Appendix A].
Concretely, we model computation as a collection of stateful, event-driven interactive Turing machines (ITM). These Turing machines have two tapes called a method tape and an input tape. When a machine is invoked with a string Method on its method tape and an input input on its input tape, it executes the code of Method. Additionally, the machines have additional tapes that allow them to communicate with each other using authenticated, confidential channels, following the model of Canetti, Cohen, and Lindell [3].
In this work, we describe the methods of an interactive Turing machine using object-oriented pseudocode. Here is an example:
Example ITM 𝑀:
𝑀 ′ .Receive(𝑥 1 , 𝑥 2 , 𝑥 3 ) Our ITMs have variables and methods. By default, all variables are private and local and all methods are public. The example machine 𝑀 above has three local variables, where 𝑥 1 can be initialized arbitrarily, 𝑥 2 is initialized to some nonzero value, and 𝑥 3 is initialized to the value 5. 𝑀 also has public methods 𝑀.Set and 𝑀.Send. So, we can invoke machine 𝑀 by placing Set on its method tape and (𝑖, 𝑥 ′ ) on its input tape. (When an ITM has only one method and no variables, we omit naming the method.) The Send command sends a communication to another Turing machine 𝑀 ′ that it should invoke a method of its own called Receive. 18Looking ahead, in this work it will be useful to model situations in which the government knows that a device has a specific behavior in some situations, but may not know the entire code of the device. For this reason, we define a partial ordering ≼ on machines. Definition 3.1. Let 𝑀 1 and 𝑀 2 be interactive Turing machines, and let 𝑆 denote the set of all methods specified within 𝑀 1 . We say that 𝑀 1 is a partial specification of 𝑀 2 (equivalently, 𝑀 2 implements 𝑀 1 ), denoted 𝑀 1 ≼ 𝑀 2 , if:
• 𝑀 2 contains at least all of the methods specified in 𝑀 1 , i.e., the methods specified in 𝑀 2 form a superset of 𝑆, and
• For all executions of the machines that only invoke the methods within 𝑆, if 𝑀 1 halts with some output then 𝑀 2 halts with the same output. This semantic equivalence must hold even over multiple, sequential invocations of the stateful machines 𝑀 1 and 𝑀 2 .
In our example above, we can consider 𝑀 ≼ 𝑀 ′′ for any ITM 𝑀 ′′ that contains Set and Send commands with the same code as listed above. That said, 𝑀 ′′ might have additional commands, such as a Delete method that sets all variables to zero or a Write method that covertly overwrites a private variable. Note that ≼ is uncomputable in general.
In this work, machines provided by the government (i.e., V, A * , T , and P defined below) tend to be fully specified. On the other hand, machines controlled by others (i.e., R and N ) are typically only partially specified since the government may only have some incomplete evidence about how they operate.
We consider a government actor G, a respondent R, and the outside world (nature)
, . . . , where the index is called the location. Oftentimes we will specify a device 𝐷 as either a partial or full representation of an oracle at (for example) location ℓ in Nature, denoted as
respectively. Some of nature's ITMs simply store information and their only functionality is a read() method that returns that information. We call such locations read only. In these cases, we sometimes simplify the notation by writing 𝑥 ← N [1] instead of 𝑥 ← N [1].read(), for example. G and R don't interact with each other or with N directly. Instead, they each output ITMs that specify how they choose to act. The respondent outputs the action A it will take, and the government outputs a verifier V that represents how it will authenticate the action performed by the respondent. One can think of V and A as the actions G and R choose to perform under the circumstances. Separating V and A from G and R allows us to describe and reason about the interaction between government and respondent (and nature) while assuming very little about G and R.
We denote an execution ⟨V N , A N,R ⟩. 19 Here, V and A are ITMs that may interact freely with one another and with N . However, R may only interact with A, not with N nor A. The output of the execution is V's output: one of Accept or Reject along with a transcript 𝜏 of its view and execution. Definition 4.1 (V accepts A). We say V accepts A with respect to R, N if ⟨V N , A N,R ⟩ returns Accept with probability 1 over the coins of V, A, R, and machines in N . If N and R are clear from context we abbreviate this as V accepts A.
We envision the government as having some evidence that certain states of the world (N ) or the respondent's mind (R) are or are not 19 We borrow this notation from oracle machines to reinforce the ways the V, A, N, and R may and may not interact. More precisely though, V can invoke N and A can invoke N and R as (global) subroutines, in the UC language of Canetti [2]. true. We represent the evidence as a binary relation E : (R, N ) ↦ → {0, 1}. E (R, N ) = 1 means that the pair (R, N ) is consistent with the evidence. Even if E (R, N ) = 1, the "true" state of the world can be some other (R ′ , N ′ ). Conversely, E (R, N ) = 0 means that (R, N ) is inconsistent with the evidence. Namely, the evidence refutes that setting of R and N . (Note that E is generally uncomputable.) Definition 4.2 (E-consistency). Let E be a binary relation. We say that R, N are E-consistent if E (R, N ) = 1.
In our framework, E is exogenous and correct. We can imagine that the government has done the work to collect the evidence, introduced it in the court, and demonstrated its truth. As such, the "true" setting of R, N is E-consistent. (As a corollary, {(R, N ) : E (R, N ) = 1} ≠ ∅.) We do not consider incorrect evidence.
It will be useful to reason about cases when the government has greater or lesser evidence. We define a (weak) partial ordering over evidence which captures whether evidence E 2 is "at least as strong as" evidence E 1 . This can arise when the government goes and gathers more evidence, or when it introduces additional evidence that it already had. Definition 4.3 (Partial ordering of evidence). Let E 1 and E 2 be binary relations, and let C E 1 , C E 2 be the set of E 1 -and E 2 -consistent worlds respectively. That is, C E 𝑖 is the set of (R, N ) for which E 𝑖 (R, N ) outputs 1 (note that these sets may be uncomputable).
We say E 2 ⪰ E 1 , or E 2 has at least as much evidence as
As discussed in Section 3, most of the time we consider partial specifications of ITMs. In Section 6 we will sometimes find it useful to consider evidences where the machines are specified fully. We define the following useful shorthand to capture this scenario. Definition 4.4 (Fully specified E 𝐷 ). For evidence E and ITM 𝐷, we define E 𝐷 ⪰ E to be the evidence where every assertion of the form "𝐷 ⪯ 𝑀" is replaced with "𝐷 ∼ 𝑀. "
Our key mechanism to avoid "relying on the truthtelling" is for the government to specify a verifier V which will be used to verify the respondent's response. There must be some exemplar action A * which demonstrates that the respondent is able to make the verifier accept, however in the context of the court case the respondent is allowed to perform any action A that results in the verifier outputting Accept. Definition 4.5 (Demonstrability). A verifier V is demonstrable with respect to evidence E if there exists an "efficient" (see Remark 4.6) action A * such that for all (R, N ) that are E-consistent:
(1) Every method call by A * to R produces some output.
(2) V accepts A * with respect to R, N
The first requirement essentially requires that R is able to perform any actions in A * that directly involve the respondent's mind. Not only does this requirement ensure that E contains some evidence that R has the method called, the fact that the method must produce some output for all settings of R ensures that E must specify some behavior on the output of the method (or else the R for which the method outputs nothing will violate the statement).
Our envisioned courtroom procedure for a motion to compel would require G to provide V, A * , and E to the court and to R (see Section §2).
Remark 4.6. We deliberately leave the "efficiency" requirement of A * somewhat vague in Definition 4.5. We expect that the court will want to define "ability to perform A * " in a way that implies some kind of reasonable time and effort limit. For example, if A * instructed R to decrypt a ciphertext, this is theoretically doable even without the key -if the respondent spends time greater than the lifetime of the universe running a brute-force decryption algorithm. Instead, we expect a more typical setting is when G knows R is capable of decrypting the ciphertext quickly (say, by using the key). We leave incorporating computational requirements to future work.
The respondent may perform any action A that results in the verifier outputting Accept. We call such actions conforming: Definition 4.7 (Conformity). A conforms with V for a given N, R if V accepts A with respect to N, R. If any of these algorithms are randomized, then acceptance must hold with probability 1 over all random choices. We also say A is V-conforming. Lemma 4.8 shows that the more evidence the government reveals, the more it can compel. An action never becomes "less compellable" by revealing more evidence. Focusing narrowly on compulsion, it is in the government's best interests to reveal all evidence it possesses. We also remark that adding more evidence only restricts the respondent's possible response actions. Lemma 4.8 (Demonstrability, conforming are monotonic in E). Let V be demonstrable with respect to evidence E 1 , and let A * be V-conforming. For all E 2 ⪰ E 1 , V is demonstrable with respect to E 2 , and A * is V-conforming.
Proof. Let C E 𝑖 be the set of E 𝑖 -consistent (R, N ) for 𝑖 ∈ {1, 2}. By definition of demonstrability, ∀(R, N ) ∈ C E 1 , the execution
so the execution ⟨V N , A * N,R ⟩ returns 1. Thus, V is also demonstrable with respect to E 2 , with exemplar A * . □
In the last section, we described how, in order to avoid relying on the respondent's truthtelling, the government may provide a demonstrable verifier V, along with an exemplar action A * and evidence E, and compel the respondent to take some action A that is accepted by V. Ultimately though, the government likely has the goal of compelling the respondent to perform some specific target action T . In this section, we ask: is there some demonstrable V that forces R to perform the target action T , or something "just as good"?
To illustrate why this is a different property than demonstrability, consider that there are many demonstrable V's for any given scenario. If nothing else, the trivial V that always outputs Accept is demonstrable for any exemplar action and evidence. With this trivial V, even though the government might hope that the respondent would choose to perform the exemplar action A * , the respondent could take any action A whatsoever in order to satisfy V. But in some scenarios, it may be possible to specify V in enough detail that R has no choice but to perform an action that is more or less equivalent to T .
We call this property entailment, and we say that V entails T if G can recover the fruits of T after R performs any V-conforming action A (including but not limited to the exemplar action A * ). Namely, the government has some method P that "post-processes" the result of A to recover what would have resulted if R had run T itself. Definition 5.1 (Entailment). Consider an oracle TM T (target) that takes no input and outputs a string in {0, 1} * . V entails T with respect to evidence E if there exists an efficient oracle TM P such that for all E-consistent N , R and all V-conforming A:
where 𝜏 ← ⟨V N , A N,R ⟩ is the transcript of the execution between V N and A N,R , and N ′ is the state of nature after the interaction between V and A. We say T is entailable if there exists demonstrable V that entails T .
To complete this definition, it only remains to define what ≡ means. We begin with the easier case: if all Turing machines in the definition are deterministic, then ≡ denotes exact equality. That is: the Turing machines P and T must output the same string, even if they follow very different paths to get there. The harder case is when randomness is involved (formally, when the Turing machines have randomness tapes following the model of Canetti [2]). In this case we impose a high bar for entailment: for each setting of the randomness tapes of P, V, A, T , R, and all of the machines within N , it must be the case that the outputs of P and T are identical.
Remark 5.2. The requirement that P is "efficient" is necessary for entailment to be meaningful. For example, consider the case of compelled decryption. If the post-processor could run for an unbounded amount of time, then P could simply ignore the respondent's action and brute-force the decryption, allowing the government to entail the act of decryption even when the respondent did not have the key! For this reason, Definition 5.1 requires that the post-processor P be efficient. As in Remark 4.6, we leave the efficiency requirement underspecified and for future work.
Remark 5.3. We note that our definition of entailment only considers target actions T that produce some output. As such, it does not require that the state of nature N 𝐴,𝑃 that results after A and P is the same as the state of nature N 𝑇 that would have resulted if R performed T . But entailment is expressive enough to capture a somewhat weaker guarantee. Suppose there is a function 𝑞 N that reads from N whatever the government believes ex ante is relevant, and outputs the result. If V entails T 𝑞 ≜ 𝑞 • 𝑇 , then N 𝐴,𝑃 and N 𝑇 will be the same in the (ex ante) relevant part.
In this section, we show that it should not be possible to entail actions where the government does not even know what property they would need to check to verify the truth. We illustrate this concept by example and then show a general theorem.
Suppose the evidence states that R has some secret 𝑧 (for instance, a list of places she had been that week). And suppose R has a method 𝑥 () that can state one valid value for that statement (e.g. where she was last night). Can the government compel R to reveal where she was sometime this past week? Or, in our parlance, is the target action which returns R.𝑥 () entailable? (For the sake of this example, suppose the government was permitted to compel any act they could verify, even explicit verbal testimony.)
If the government has no evidence that the respondent was located anywhere in particular in the last week, then intuitively, there should be no way to entail the action of R.𝑥 (). 20 𝐿 𝑅.𝑧 = ∅, then there does not exist a demonstrable V which entails T lang with respect to E ′ .
Note that the hypothesis of Theorem 5.4 implies that the government has no ability to check membership in the language 𝐿 R.𝑧 . This is the formalization of the property stated above, that the government does not know "what it is looking for. "
We defer the proof of Thm. 5.4 to Appendix B.1. The proof does not rely on any computational limitations on the part of the government-only the information-theoretic uncertainty of the true value of R.𝑧.
In Appendix A.3 we will investigate actions that result in a distribution, such as compelled encryption or commitments. In those sections, it will be useful to make use of the following result, which states that it is impossible to entail actions that result in a distribution using the random coins of the action itself.
Theorem 5.5. Let E be some evidence, and let T rand be some target action. Suppose that T rand uses its own randomness in a non-trivial way: specifically, there exists E-consistent N, R with the property that at least one fixed setting of the random tapes of N, R have the property that |Support(T N,R rand )| ≥ 2. Then, there is no demonstrable V that entails T rand .
We defer the proof of Theorem 5.5 to Appendix B.2. 20 Observe that there are demonstrable Vs with "return R.𝑥 ()" as the exemplar. However, the respondent may respond by, for example, responding to the query with "Boston" even if she had never been there. This is not the result of R.𝑥 (), but the verifier must accept it anyway because the government has no way to rule out the possibility.
The ability for evidence to partially-specify functionalities in N poses a major difficulty for proving entailment in many cases.
The algorithms in Figure 1 illustrate the problem. Consider E read stating that 𝐷 read ≼ N [DLoc]: there is a device at location DLoc in nature that is consistent with 𝐷 read . 𝐷 read has a variable m and a method read() that returns m. It may seem that T read which simply outputs N [DLoc].read() should be entailable. After all, P could just call N [DLoc].read() itself. Whatever V entails T read could have an exemplar action that does nothing.
But in fact T read is not entailable! The problem is that the behavior of N [DLoc] is only partially specified. While it must be consistent with 𝐷 read , it may have other methods too. For example, N [DLoc] could instead contain device 𝐷 readWrite (Figure 1) which has another method write(𝑥) that sets m to 𝑥. Because E contains no information about m, if the A * that does nothing is V-conforming, then A 𝑥 that calls write(𝑥) is also V-conforming.
As such, many of our entailment claims will be proved with respect to the stronger evidence E 𝐷 wherein some function specifications are strengthened from partial to full specifications (see Definition 4.4). This showcases our framework's ability to reason about uncertainty about the world, as illustrated by the example of deniable encryption in Section 6.2.
In this section we consider how to construct demonstrable verifiers and analyze entailment for some important idealized foregone conclusion scenarios. We begin with the common example of compelling a respondent to enter a passcode that decrypts a device under the assumption that the encryption scheme is not deniable (Section 6.1). Then in Section 6.2 we show that removing the assumption of non-deniability eliminates the ability to entail the action of "honest" decryption, standing in contrast with most prior legal analysis. We then describe the entailability of cryptographic decommitment, which implies entailment of a wide variety of functionalities (Section 6.3). This finding stands in direct contrast with the approach of Scheffler and Varia [32] (see Appendix 7.2). We also examine additional examples, namely two-factor authentication, hash preimages, encryption, and commitmnets in Appendix A.
In the archetypal compelled decryption case, the government has lawfully seized an encrypted device and seeks order compelling the respondent to decrypt by entering her password. The government wants to specify an action for which all implicit testimony is foregone. For this act to be meaningful, it should allow the government to recover the decrypted plaintext. In our framework, the government seeks a demonstrable V pwd that entails the target task T pwd of decrypting and producing the plaintext (given in Figure 2). For an idealized non-deniable encryption, we will show that this is possible if the government knows that the respondent knows the password (as in Kerr [24]).
In this subsection, we will consider the algorithms and evidence given in Figure 2 (unless otherwise stated). In particular, we consider a simple password-protected device 𝐷 pwd that provides read access to a message if the correct password is entered, and hides all message contents otherwise. If the government has evidence E pwd that the respondent knows this password, then it can use a verifier V N pwd that checks if the device is unlocked and capable of displaying any message, along with an exemplar action A * N,R pwd in which the respondent types the known password into the prompt.
6.1.1 R knows the password. We begin with the case where G knows that R knows the password. The evidence E pwd states that G knows that a device implementing 𝐷 pwd is at location DLoc in nature. 𝐷 = 𝐷 pwd is some idealized encrypted device, with a hardcoded password 𝐷.pwd and message 𝐷.m ≠ ⊥. The evidence also states that R has some method R.pwd () that returns the password 𝐷.pwd (the starred line in Fig. 2). After that password is entered into 𝐷, the message 𝐷.m can be read using the method 𝐷.read().
Applying our framework, the government must specify a demonstrable verification procedure V pwd . The government's verifier V pwd reads m from the device, outputting Accept if m ≠ ⊥. Claim 6.1. V pwd is demonstrable with respect to E pwd .
pwd in Fig. 2. First, we must check that every method call by A * pwd to R produces some output. A * pwd only calls R.pwd (). By E, this method exists and outputs 𝐷.pwd. Second, we must check that V pwd accepts A * pwd with respect to R, N . Let 𝑀 be the device at N [DLoc]. E guarantees that 𝑀 implements 𝐷 pwd (i.e., 𝐷 pwd ≼ 𝑀). A * calls 𝑀.prompt with input R.pwd (). By E, R.pwd () = 𝑀.𝑝𝑤𝑑. Hence, when A * halts, 𝑀.decrypted = true. Now V pwd calls 𝑀.read(), which returns 𝑀.m. E states that m ≠ ⊥. Hence V pwd returns Accept. □ By construction, any V pwd -conforming action A will allow the government to recover the plaintext m, assuming the encrypted device is not deniable. We use entailment to make this precise. Consider T pwd in Figure 2, which enters R.pwd () into the device's password prompt, then reads and returns the message m. By the evidence, the result is the plaintext message.
We prove that V pwd entails T pwd under the stronger evidence E 𝐷 pwd that the device is fully specified by 𝐷-ruling out deniability. This restriction is necessary, and follows the general pattern described in Section 5.3. For one, the proof breaks down: the step marked (♣) does not hold for arbitrary E. Moreover, Section 6.2 shows that the government cannot entail T pwd when the device is deniable but otherwise consistent with 𝐷 pwd .
This example illustrates the expressiveness of our approach and the power of entailment. Claim 6.2 states that in this example 'decrypting by entering a password' entails 'decrypting then producing the plaintext'. But the act of decrypting-then-producing is not itself compellable! Specifically, it would require implicit testimony about conformity that is not a foregone conclusion under the evidence. (Additionally outside of our model, some would argue that producing the plaintext presents testimonial issues beyond Fisher.) Claim 6.2. V pwd entails T pwd with respect to E 𝐷 pwd .
Proof. We must provide an efficient oracle machine P pwd such that for all A that is V pwd -conforming:
pwd simply call and return 𝑀 ′ .read() as in Figure 2. To complete the proof, we show that both P pwd and T pwd always output 𝑀.m.
(RHS). By E pwd -consistency of R, we get 𝑥 = 𝑀.pwd on line 1 of T pwd . By E-consistency of 𝑀, we get m ′ = 𝑀.m on line 3 of T pwd .
Hence T N,R pwd always outputs 𝑀.m. (LHS). Because A is V pwd -conforming, we have ⟨V N pwd , A N,R ⟩ = Accept. By construction, the execution ⟨•, •⟩ first runs A and then runs V pwd . Because V pwd does not change the state of 𝑀 (i.e., does not call 𝑀.prompt), N ′ is equal to the state of nature after A N,R terminates. By construction of V pwd (and the conformity of A), 𝑀 ′ .read() ≠ ⊥ after A terminates. If 𝑀 ′ .read() ≠ ⊥, then 𝑀 ′ .read() = 𝑀.m (♣). Hence P N ′ pwd always outputs 𝑀.m. □ 6.1.2 R may not know the password. Next, we drop the starred assertion in E pwd in Figure 2. This tweaks the facts to remove the government G's assertion that R knows a password to 𝐷. Call the modified evidence E ★ . E ★ states that the respondent has some method R.pwd () that may do something. But not what it does, nor whether it has any relation to 𝐷. Under E ★ , it is entirely consistent that R simply does nothing. That is, for any (N, R) that is E ★ -conforming, (N, R ⊥ ) is also E ★ -conforming where R ⊥ immediately halts on all inputs.
where R ⊥ immediately halts on all inputs. Fix V demonstrable and A that is V-conforming, all with respect to E ★ . Because R ⊥ is E ★ -consistent, the action A ⊥ which emulates A with R ⊥ is also V-conforming with respect to E ★ .
For any post-processor P, the output of P after ⟨V N , A N,R ⊥ ⟩ is independent of R. On the other hand, T N,R pwd pwd always outputs 𝐷.𝑚 ≠ ⊥, while T N,R ⊥ pwd always outputs ⊥. Hence, there exists E ★consistent (N, R) such that P does not always output the result of T N,R pwd (e.g., R is an appropriately chosen distribution over R ⊥ and R pwd ). Hence, T pwd is not entailable with respect to E ★ . □ Evidence E pwd :
Device 𝐷 pwd :
Figure 2: Example algorithms for compelled decryption by entering a password as described in Section 6.1 and used in Section 6.2. The starred (★) assertion in E pwd refers to the respondent's knowledge of the decryption password. Removing that line captures the setting when the government has no evidence of the respondent's knowledge of the password.
We continue the example from Section 6.1 and Figure 2 wherein the government wishes to compel decryption by entering a password. Now we consider the case of deniable encryption. Deniable encryption introduces a duress password which, when entered, allows a device to be decrypted to something other than its "true" contents.
For illustrative purposes, we analyze a simple but unrealistically powerful form of deniable encryption 𝐷 deny , wherein the duress password can be used to overwrite the device's contents arbitrarily.
Device 𝐷 deny implements 𝐷 pwd : // Has the following variables and methods in addition to those provided by 𝐷 pwd in Fig. 2 Variables: duress Method deny(𝑥, 𝑦) if (𝑥 == duress) then set m ← 𝑦 set decrypted ← true
In Claim 6.2, we proved entailment only with respect to the strong evidence E 𝐷 pwd that states that the encryption is not deniable. This is not a fluke. Consider the idealized version of deniable encryption in 𝐷 deny . Because 𝐷 pwd ≼ 𝐷 deny , it is entirely consistent with E pwd . So the possibility that the actual encrypted device uses a form of deniable encryption affects entailment. Absent stronger evidence that the device is not deniable (i.e.: E 𝐷 pwd ⪰ E pwd ), T pwd is not entailable, and the message that will ultimately be read from 𝐷 is not meaningful.
While entailment fails, demonstrability does not. The same V pwd is demonstrable with the same exemplar action A * pwd . Using our framework, a respondent may ultimately be compelled to enter a password even if the government knows the encryption is deniablebut the respondent would be free to use the duress password. This is in contrast to prior legal approaches to this fact pattern, as discussed at the end of Section 1.
Next, we consider commitments-cryptographic objects related to, but distinct from encryption. In this section, we ask: when can the government compel the opening of a commitment? In our framework, the answer is: when the government has the commitment and knows that the respondent can open it. Note that this answer generalizes the claims about committing encryption from Section 6.1.
At a high level, commitments are like lockboxes, where each box has a bespoke lock and key. Once you put a secret message into the lockbox, nobody can read the secret (hiding), and nobody can change the secret (binding). Whoever has the key can open the box in front of others, thereby convincing them that box always contained that particular secret message. An important difference between commitments and encryption is this public-opening property. For instance, deniable encryption schemes are specifically non-committing: it can be decrypted in different ways. Commitments can only be opened a single way.
Moving from the physical analogy to the computational setting, commitments schemes provide an algorithm to commit to a secret 𝑥, producing the commitment 𝑐 and the decommitment 𝑑. Opening the commitment means revealing 𝑑 and 𝑥. Given 𝑐, 𝑑, and 𝑥, anybody can check that the opening was done correctly. Definition 6.4 (String commitment scheme). Let (Com, Check) be a string commitment scheme where (𝑐, 𝑑) ← Com(𝑥; 𝑟 ) yields a pair of strings (𝑐, 𝑑) called the commitment and decommitment to message 𝑥 respectively, and Check(𝑐 ′ , 𝑑 ′ , 𝑥 ′ ) returns either 1 or 0. For all 𝑟 , if (𝑐, 𝑑) ← Com(𝑥; 𝑟 ) then Check(𝑐, 𝑑, 𝑥) = 1.
Binding (informal): A commitment scheme is binding if it is difficult to find (𝑥, 𝑥 ′ , 𝑑, 𝑑 ′ , 𝑐) such that 𝑥 ≠ 𝑥, Check(𝑐, 𝑑, 𝑥) = 1, and Check(𝑐, 𝑑 ′ , 𝑥 ′ ) = 1. A commitment scheme is perfectly binding if there does not exist such a tuple (𝑥, 𝑥 ′ , 𝑑, 𝑑 ′ , 𝑐).
Hiding (informal): Suppose (𝑐, 𝑑) ← Com(𝑥; 𝑟 ). A commitment scheme is hiding if it is difficult to find 𝑥 given only 𝑐. A commitment scheme is perfectly hiding if the distribution of 𝑐 is identical for any 𝑥, 𝑥 ′ input into Com (over the choice of 𝑟 ).
Consider the Evidence E decom , Verifier V decom , Target Action T decom , and Exemplar Action A * decom given in Figure 3. E decom states that that the respondent is able to produce a valid opening to the commitment 𝑐 at location N [commLoc] Proof. If N, R are E decom -consistent, then A * decom will result in V accepting, because the Evidence states that Check(𝐶.read(), R.𝑑𝑒𝑐𝑜𝑚(), R.𝑠𝑒𝑐𝑟𝑒𝑡 ()) = 1. We know R has the ability to perform this action, because it involves only a read to R.𝑠𝑒𝑐𝑟𝑒𝑡 () and R.𝑑𝑒𝑐𝑜𝑚() which were specified in E decom . Thus, V decom is demonstrable with witness action A * decom . □
In fact, this holds even without binding. That is, dropping the starred (★) line in E decom in Figure 3 does not affect demonstrability.
If the government additionally has evidence that the commitment is perfectly binding, then V decom entails T decom which discloses R.secret(). 21 Let E bind ⪰ E decom represent this stronger evidence. (Both T decom and E bind are defined in Fig. 3. Claim 6.6. If Com is perfectly binding, then V decom entails T decom under E bind .
Proof. Recall that E decom reads 𝑐 from N [commLoc]. E decom asserts that for 𝑑 ← R.decom() and 𝑥 ← R.secret(), it must be true that Check(𝑐, 𝑑, 𝑥) = 1. Recall that V decom reads 𝑐 ′ ← N [E decom .commLoc], and since this oracle is read-only, we have that 𝑐 ′ = 𝑐. Since the commitment scheme is perfectly binding, there is no (𝑥, 𝑥 ′ , 𝑑, 𝑑 ′ , 𝑐) such that 𝑥 ≠ 𝑥 ′ , and both Check(𝑐, 𝑑, 𝑥) = 1 and Check(𝑐, 𝑑 ′ , 𝑥 ′ ) = 1. Thus, 𝑥 ′ = 𝑥 and 𝑑 ′ = 𝑑.
Letting N ′ be the state of Nature after running A, the postprocessor P R,N ′ decom which returns the 𝑥 ′ sent by A will always return R.𝑠𝑒𝑐𝑟𝑒𝑡 (), thus entailing T decom . □
A corollary of Claim 6.6 is that, under the same evidence, the government can entail arbitrary computation on the committed secret R.secret(). For any 𝑓 , T 𝑓 is entailable with respect to E decom :
T N,R 𝑓 := return 𝑓 (R.secret()) 21 If the commitment scheme is only computationally binding, then we expect entailment would still hold against a computationally-bounded respondent along the lines of Claim A.3. Remark 6.7. In this section, we showed that compelling the opening of a unknown but committed secret is demonstrable and entailable if the scheme is perfectly binding. In Appendix A.3, we show that there is no way to entail a commitment of an unknown secret. This is reassuring. If it were not true, then G could entail commitment-then-open of arbitrary unknown secrets. It is worth noting that there are many demonstrable Vs that have the exemplar action of committing to a secret value. However, the fact that none of those Vs entail the action of committing to a secret value means that those Vs would also be satisfied by other actions, possibly for example committing to the all-zeros string.
Here, we compare our verification-centric view to the body of legal scholarship on compelled decryption. On the one hand, scholars like Kiok [26] and Sacharoff [31] posit that the government can compel decryption only if they know the desired files with "reasonable particularity, " and Winkler [51] argues that the self-incrimination privilege provides an absolute defense against compelled decryption. On the other hand, Cohen and Park [6], Kerr [23][24][25], McGregor [27], and Terzian [37,38] deem compelled decryption to be a foregone conclusion in some contexts, either to re-balance government power due to the widespread use of encryption or because all the testimony implicit in the act of decryption (e.g., ownership, knowledge of password) is foregone.
Our framework largely agrees with the latter interpretation of the foregone conclusion, by considering all acts involved in the performance of decryption rather than simply the files produced. That said, our framework reaches a novel conclusion about the compellability of "deniable encryption" schemes, which include special duress password(s) that can reveal different files. Here, Kerr and Cohen-Park reach opposite conclusions. By separating demonstrability from entailment, our framework reaches a "middle ground" where decryption can be compelled, but the respondent can use any password unless the files are known with reasonable particularity.
The work that is most related to ours is the paper of Scheffler and Varia [32], which also contributes a cryptography-inspired candidate definition of the foregone conclusion doctrine. This work and [32] agree on landmark Supreme Court and circuit court decisions to date about the foregone conclusion doctrine [12, 13, 16-18, 45, 46, 49]. As a general rule of thumb that we expect to hold for many realistic fact patterns, an action that is a foregone conclusion under [32] is likely entailable in our current framework. A notable exception is the inability for our current framework to entail random sampling from a probability distribution (Theorem 5.5).
That being said, the two works differ in several legal and computer science aspects.
First, this work requires the government to specify how it will verify the respondent's act, thus ensuring that the government is not "relying on the truthtelling" [13, l. 411]. In contrast, [32] requires the government to specify how it could have performed the respondent's act using the cryptographic idea of simulation but without access to the "contents of [the respondent's] mind" [13, l. 421], thus ensuring that the respondent's production "adds little or nothing to the sum total of the Government's information" [13, l. 411].
Second, the two works take different approaches to conformity. Scheffler and Varia dealt with the implicit testimony from conformity using simulation. In contrast, this work defines away the problem of conformity by allowing the respondent to perform any conforming action.
Third, the modeling in this work allows modeling more scenarios than [32]. Scheffler and Varia focused on acts of production, and involved the simulation of what was produced. Our work, on the other hand, focuses on acts of either production or performance, and can analyze actions taken that have impact on the world even if no item is produced to the court as a result. To accomplish this technically, rather than modeling the world as a collection of passive strings such as a ciphertext stored on a smartphone's hard drive, we model dynamic, stateful, interactive processes such as the phone itself and all of the ways that one can interact with it.
The archetypal compelled decryption scenario asks: When can a respondent be compelled to enter a password into an encrypted device in the government's possession? Scheffler and Varia model a scenario where the respondent performs password-based decryption and produces the plaintext. But Cohen and Park argue that the "decryption" scenario is doctrinally distinct from the "production of plaintext" [6]. In contrast to [32], our current model allows us to consider either scenario directly.
In summary, we adopt a view of implicit testimony that treats ability and conformity as equally important, and we present a new verification-centric approach to compelling acts while constructively satisfying the foregone conclusion doctrine. On the technical side, we formally define the concepts of demonstrability and entailment and explore the compellability of acts of cryptography within our framework. Our goal in this project was CS-and-law: rigorous computer science that substantively engages with and contributes to legal thought. In this section, we take a step back and reflect on what seemed to work for us.
This paper is the culmination of a five-year research agenda that alternated between primarily legal and primarily technical contributions. First, AC in collaboration with Sunoo Park produced a law-first analysis grounded in their knowledge of cryptography; they showed how the application of the foregone conclusion doctrine can depend on the nuances of the underlying technology [6]. Next, SS and MV produced a technical-first analysis inspired by the law; they gave a more restricted simulation-based formal framework and analyzed how the compellability of different cryptosystems under it [32]. All three authors then worked to reconcile the differing accounts of those two works, resulting in a new legal analysis that introduced the idea that ability and conformity are testimony implicit in acts of performance [7]. The present paper represents our effort to turn these ideas into a formal framework; more than just a formalism, that effort spawned our verification-centric approach and the concepts of demonstrability and entailability.
In this project, neither side was subservient to the other. We did not start with a legal view or a set of technical outcomes to which we molded our framework.
Instead, our meta-level approach in this project was an iterative, alternating application of legal and technical thinking. At a high level, our goal was to fill in a gap in our understanding of the foregone conclusion doctrine: namely, it's requirement that the government may not "rely on the truthtelling" of the respondent. First, we would state a non-mathematical version of the requirement based on our understanding of the case law and fact patterns considered so far. Second, we attempted to formalize that statement in a technically precise and sound way, building from the framework of [32]. Third, we would test the result against many fact patterns, whether uncontroversial act-of-production cases, existing compelled decryption cases, the cryptographic primitives studied in this paper, or hypotheticals specifically designed to stress the framework. Fourth, we would ask whether the formalism uncovered a new aspect of the legal question that could help refine our thinking. After many many iterations, we converged on the ideas in this paper.
We do not know what legal questions are amenable to the sort of CS-and-law analysis we undertake in this paper. We highlight some properties that we believe make compelled decryption fruitful for a cross-disciplinary study, in the hopes that it may help others find other fertile grounds. First, law alone offers no obvious answers. Scholars are in disagreement and state supreme courts are split. And as Cohen and Park argue, forgone conclusion analyses can depend on technical details, and reasoning by analogy can only go so far. Second, there are clear connections to well-studied concepts in cryptography and computer science. Of course the very artifacts in question issue are technological and cryptographic. And at a conceptual level, cryptographic community has spent decades stress-testing notions of simulation and verification. The intuitive connection to ideas in Fisher's -adding to the government's knowledge, or relying on the respondent's truthtelling -are immediate to a cryptographer (though making the intuition precise is not easy). Third, the results of this project is of value to both communities, with the potential to affect future court cases and to spur new research directions in security and cryptography. Table 1: Is T = OTP(𝑘, R.𝑥) entailable (E) or not entailable (NE), for the given setting of E and generation of 𝑘?
Then when V 2fa calls 𝑀 𝐷 .read(), the device will return 𝑚 ≠ ⊥, and thus V 2fa accepts as desired. □ Claim A.2. V 2fa entails T 2fa with respect to the stronger evidence E 𝐷,𝑆 ⪰ E 2fa (i.e., that the specifications of 𝐷 and 𝑆 are full specifications).
Proof. Much like the proof given in Section 6.1, we will show that both running P 2fa on the transcript of ⟨V N 2fa , A R,N ⟩, and running the target action T 2fa , yield the same result of 𝐷.𝑚.
For the left hand side, observe that if V 2fa returns Accept, then 𝑚 ← N [E.deviceLoc].read() was not ⊥. E 𝐷,𝑆 states that N [E.deviceLoc] exactly implements 𝐷 (and similarly for 𝑆). Hence, the only way for read() to return anything other than ⊥ was for it to return 𝐷.𝑚, which cannot be altered using any of the methods provided. Thus, if V 2fa returns Accept, the post-processor P 2fa must also return 𝐷.𝑚.
Consider the right hand side. Because E 𝐷,𝑆 specifies that R.pwd() = 𝐷.pwd, this ensures that in the first line of T 2fa , 𝑥 = 𝐷.pwd (). Moreover, the second line of T 2fa calls exactly the given code of 𝐷.promptPwd(𝐷.pwd), which also calls exactly setCode(𝐷.code) no matter what the randomness tape of 𝐷 is. The third line of T 2fa sets 𝑐 to exactly 𝐷.code, and so the fourth line of T 2fa calls 𝐷.promptCode(𝐷.code). Thus, decrypted is set to true and when T 2fa calls read(), it must return 𝐷.m, as desired.
Thus, V 2fa entails T 2fa as desired. □
We imagine a scenario in which G wishes to compel R to provide a file and verify the file using its hash. This example is captured in Figure 4, where we envision ℎ to be a fixed hash function like SHA-256. By construction of the evidence, V hash is demonstrable. Entailment is more complicated.
Claim A.3. For all E hash -consistent N, R and for all V hash -conforming A, either (i) P N ′ (𝜏) = T R,N , or (ii) P N ′ (𝜏) and 𝑇 R,N = N [R.findFile()].read() are a hash collision for ℎ.
Proof. Let 𝑥 𝑡 = N [R.findFile()].read() be the output of T R,N . The evidence ensures that ℎ(𝑥 𝑡 ) = E.𝑦. Let 𝑥 𝑝 be the output of P N ′ (𝜏). By definition, 𝑥 𝑝 is the message sent by A to V. Because A is V-conforming, V (𝑥 𝑝 ) = Accept and hence ℎ(𝑥 𝑝 ) = E.𝑦. Hence ℎ(𝑥 𝑝 ) = ℎ(𝑥 𝑡 ). Either 𝑥 𝑝 = 𝑥 𝑡 or not, corresponding directly to the two cases in the claim. □
In words, this verifier almost entails T R,N , except that the government has not ruled out the possibility that R knows a hash collision at 𝑦. Note that we have only shown that this verifier almost but not quite entails the action -a different verifier might very well entail the target action.
Since, in the real world, we do not expect the respondent to be capable of producing a hash collision, we expect that R's only strategy will be to send the exact file G wanted to entail. By compelling a preimage of a hash (which G knows with certainty R is capable of doing), this forces the respondent to either respond with the file or a hash collision, putting the ball in their court. Although the government did not have evidence that pinned down every degree of freedom the respondent had, G did not need to make any additional assumptions to create the demonstrable V shown, nor did G need to implement a potentially-more-costly verifier to find a different way of compelling the file that directly entailed the action. This demonstrates why the focus of our system is on demonstrability rather than entailment.
Throughout this section, we will use the following evidences: E secret corresponds to the situation where G knows R has some secret, but has no knowledge of what it is and no way to verify it. E known corresponds to a situation where G is able to learn the secret independently of R (by checking N [xLoc]). Let OTP(𝑘 ′ , 𝑚) return the bitwise XOR of 𝑘 ′ and 𝑚 assuming they are the same length. Table 1 shows whether there is any way of entailing the target action T = OTP(𝑘 ′ , R.𝑥) depending on which key 𝑘 ′ is used and on the evidence. Of the scenarios considered, T is entailable only when the government specifies a fixed key 𝑘 ′ in T and is able to recover the plaintext R.𝑥 from nature.
Remark A.4. The action which deterministically chooses 𝑘 ′ and then returns OTP(𝑘 ′ , R.𝑥) is entailable under E known . The verifier V that deterministically sets the same 𝑘 and then sets 𝑚 ← N [xLoc].read() is demonstrable and must always have exact equality with the output of this action, and so entails the action.
Remark A.5. Note that if the one-time-pad was replaced with a randomized encryption scheme, by Theorem 5.5 compelling the action of honestly encrypting 𝑚 under the known 𝑘 (using randomness in T ) is not entailable by Theorem 5.5. However, this action is entailable if G additionally fixes the randomness used in the encryption scheme, because V may check the exact equality of the result. This latter result stands in contrast with Theorem 4.5.1 from Scheffler-Varia [32], which found that compelling encryption under a freshly sampled key was compellable (under a different definition as described in Section 7).
In re Search of a Residence in Aptos, California 95003, No.17-mj-70656-JSC-1, 2018 WL 1400401[21], at 10.
See also Cohen and Park[6] at VII.
Commonwealth v. Gelfgatt, 11 N.E.3d 605 (Mass. 2014) [9], (see footnote 10, emphasis removed)
United States v. Bright, 596 F. 3d 683, 693 (9th Cir. 2010) [41] (the government does not "need to prove that it had previously authenticated the same documents . . . it need[s] to show only that it could do so" (emphasis added)).
Though the UC model guides us, a complete UC specification is premature at this stage in this line of work and would make this paper inaccessible to its intended audience, most of whom are unfamiliar with the UC model. For the same reasons, we do not attempt a precise compilation from our pseudocode machines to ITMs.
Conference'17, July 2017, Washington, DC, USA