Scalable auditability of monitoring process using public ledgers
11323489 · 2022-05-03
Assignee
Inventors
- Gaurav Panwar (Las Cruces, NM, US)
- Roopa Vishwanathan (Las Cruces, NM, US)
- Satyajayant Misra (Las Cruces, NM, US)
Cpc classification
H04L63/0428
ELECTRICITY
H04L63/306
ELECTRICITY
International classification
H04L9/32
ELECTRICITY
Abstract
Secure auditability of monitoring processing using public ledgers that are particularly useful for monitoring surveillance orders, whereby an overseeing enforcer (“E”) checks if law enforcement agencies and companies are respectively over-requesting or over-sharing user data beyond what is permitted by the surveillance order, in a privacy-preserving way, such that E does not know the real identities of the users being surveilled, nor does E get to read the users' unencrypted data. Embodiments of the present invention also have inbuilt checks and balances to require unsealing of surveillance orders at the appropriate times, thus enabling accounting of the surveillance operation to verify that lawful procedures were followed, protecting users from government overreach, and helping law enforcement agencies and companies demonstrate that they followed the rule of law.
Claims
1. A method for ensuring compliance and public accountability between parties of a confidential transaction implemented by a hardware processor and memory comprising: entering an encrypted confidential order into a public ledger wherein said entering is based on a judge's signature and said confidential order comprises a surveillance order; receiving from a requesting party a request for data of a first party; reviewing by an enforcer the request for data and if the request for data is within a scope of the encrypted confidential order, the enforcer forwarding the request for data to a second party; receiving from the second party encrypted data of the first party in response to the request for data; and reviewing by the enforcer the encrypted data, without decrypting the encrypted data, and forwarding the encrypted data to the requesting party if the encrypted data does not exceed the scope of the confidential order and/or a scope of the request for data.
2. The method of claim 1 wherein the second party providing encrypted data of the first party includes encrypting data of the first party and storing the encrypted data on non-transitory computer readable media by the second party.
3. The method of claim 1 wherein issuing a request for data comprises issuing a request for data that comprises emails.
4. The method of claim 3 wherein the emails are grouped and encrypted into batches of emails.
5. The method of claim 1 wherein the enforcer enters information into the public ledger when the requesting party requests data beyond the scope of the confidential order.
6. The method of claim 1 wherein the enforcer enters information into the public ledger when the providing party provides data beyond the scope of the confidential order or beyond the scope of the request for data.
7. The method of claim 1 further comprising the second party providing the requesting party with a key for decrypting the encrypted data.
8. The method of claim 1 wherein the confidential order comprises a search order in accordance with a national security letter.
9. The method of claim 8 wherein the search order is posted to the public ledger by the requesting party.
10. The method of claim 1 wherein the search order comprises a request for confidential information.
11. The method of claim 1 wherein issuing a request for data comprises issuing a request for data that comprises one or more IP addresses.
12. The method of claim 1 wherein issuing a request for data comprises issuing a request for data that comprises searchable encryptions.
Description
BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS
(1) The accompanying drawings, which are incorporated into and form a part of the specification, illustrate one or more embodiments of the present invention and, together with the description, serve to explain the principles of the invention. The drawings are only for the purpose of illustrating one or more embodiments of the invention and are not to be construed as limiting the invention. In the drawings:
(2)
(3)
(4)
(5)
(6)
(7)
(8)
DETAILED DESCRIPTION OF THE INVENTION
(9) Embodiments of the present invention address the challenges described in the Background section above. Some of the unique aspects of embodiments of the present invention include i) a generic and scalable framework for accountability of monitoring processes; ii) a capability to audit the compliance of the entities over the lifetime of the surveillance order from the outset, using cryptographic techniques such as ZKPs, and Pedersen commitments. An entity, referred to herein as an “Enforcer”, preferably serves as the conduit for interactions between law enforcement/intelligence gathering agencies and companies, and verifies their interactions to guarantee compliance. Embodiments of the present invention qualitatively prove that auditability of the surveillance process when the court order is active is possible if an entity such as an Enforcer serves as the conduit for information and the process does not leak information about the surveillance to the public—only provides audit insights. iii) A case study of SAMPL in the context of the US legal system. iv) Security analysis of the framework of SAMPL. v) Validation of the framework using a near-real world implementation to assess scalability. As used throughout this application, the term “public ledger” is intended to include a blockchain as well as any public messaging system that preserves anonymity and provides provenance.
(10) In an embodiment of the present invention, there are preferably six parties the individual being surveilled “I”, company “C” that I has an account (e.g., e-mail) with, law enforcement and/or intelligence gathering agency “L” requesting the surveillance, Judge “J” who can potentially issue the surveillance order on I, and an Enforcer “E”, who enforces accountability of L and C's operations, by ensuring that L does not request more information about I than what is authorized by J, and C does not over-share information about I, more than what is authorized by J. Finally, embodiments of the present invention have a set of interested users, “U”, which can be made up of civil-rights and/or non-profit organizations (e.g., American Civil Liberties Union (ACLU)) whose mission is to protect and preserve individuals' privacy as defined by laws. We assume that all communication between J, L, C, E, I, and U takes place via secure and authenticated channels. They use each other's public and verification keys, respectively to encrypt and authenticate all communication between them.
(11) In one non-limiting example of a user-company interaction with an embodiment of the present invention, a user preferably signs up with the company, creates signing keys for a real identity (“RI”), an anonymous identity (“AI”) and an initial pseudonymous identity (“PI”). The RI and AI of user preferably remain static while a new PI can be generated on demand or in a periodic manner. The RI can be used to sign AI, thus, with the signature, it can be proved that AI belongs to user identified by RI. Each PI is preferably signed with the user's AI, this proves PI belongs to a user with AI without revealing user's RI to verifier. The user data is preferably batched and hashes of individual pieces of data are preferably used to form Merkle trees. The roots of Merkle trees are signed by user's current PI.
(12) A few of the many benefits provided by embodiments of the present invention include:
(13) 1) The public can routinely check the ledger for activity of parties involved in ongoing and past surveillances;
(14) 2) On expiration of a specific surveillance order a judge can be approached to provide the keys and verify that the surveillance carried out was not unlawful; and
(15) 3) Certain govt organizations, for example the Office of Inspector General, can verify surveillance orders even before the expiration of a surveillance order to keep all involved parties in check.
(16) Embodiments of the present invention can include every combination of features that are disclosed herein independently from each other.
(17) In one exemplary embodiment as illustrated in
(18) Part 1: Contains sensitive and revealing information, for example the reason for the surveillance, RI of users, etc., which is preferably encrypted with keys only available to J, L and C.
(19) Part 2: Contains sensitive but non-revealing information, for example the surveillance period, AI of users, etc., which is preferably encrypted with keys only available to J, L, C and E.
(20) Part 3: Contains publicly available information, for example, the expiry date of the surveillance order, etc., which is preferably unencrypted.
(21) L then preferably requests information from C through E (see
(22) TABLE-US-00001 TABLE 1 Variable Definition λ Security parameter J, L, C, E, I, U, I Judge, Law enforcement agency, Company, Enforcers Set, Individual, Set of Users, Set of Individuals σ Signature T T's total data records RI = (VK.sub.RI, SK.sub.RI) Real identity of individual I AI = (VK.sub.AI, SK.sub.AI) Anonymized identity of individual I PI = (VK.sub.PI.sub.
(23) A table of notations is given in Table 1. Note that I⊂I, where I is a set of individuals who have an account with C.
(24) Identities of an individual: In one embodiment, an individual I preferably has three identities associated with him or her:
(25) 1) A real identity, RI which may correspond to I's e-mail address that is being surveilled. RI is preferably established between I and C when I signs up for service with C. RI is preferably represented by a verification/signing key-pair: RI=(VK.sub.RI, SK.sub.RI). The company C stores VK.sub.RI and VK.sub.RI is known only to J, L, and C. In particular, RI is preferably not known to E. RI is preferably stored safely by I, does not get compromised, and acts as the root-of-trust for all other keys involving I.
(26) 2) An anonymized identity, AI, which corresponds to a nickname associated with RI. When a user signs up for service with a company, they are preferably asked to create the anonymized identity AI which is linked by C to their real identity RI. The user can preferably create only one anonymous identity with a service provider (e.g., one nickname per e-mail address). AI can optionally be represented by a keypair: AI=(VK.sub.AI, SK.sub.AI). Anonymized identities are preferably used to avoid having the enforcer know RI. The company C stores VK.sub.AI, which is known and revealed to E, J, L, and C during the surveillance period.
(27) 3) A pseudonymous identity, PI.sub.i; i∈[1 . . . m], represented by PI.sub.i=(VK.sub.PI.sub.
(28) An individual storing data on company servers: Although SAMPL enables the auditing of a broad range of data and application types, user emails are used for illustration herein. Later in the application, we generalize this requirement. When an individual I signs up for service with a company C, it interactively creates a symmetric key K.sub.CI to be shared between C and I. I uses K.sub.CI to encrypt sensitive information, but keeps the date and time as plaintext and signs the whole message. K.sub.CI can be updated periodically. C and I agree on two parameters, bSize and bNum, which denote batch size and batch number.
(29) The batch size represents the intervals at which the user's messages are batched. The batch number indicates the batch a given message originates from. Let I's total data records, e.g., emails be denoted by T. Then bNum=T bSize, bSize can be a static or dynamic parameter. In the static case, I sets up bSize at the time of service initiation with C, and doesn't change it; in the dynamic case, bSize can be changed by I as needed. SAMPL supports both these implementation choices
(30) I preferably creates and encrypts each email with K.sub.CI before sending it to C. At the end of each batch, C creates a Merkle tree with the hashes of all messages in the batch at the leaves. C sends the root hash of the Merkle tree to I. I verifies the root hash calculation, signs it if it is accepted, and sends it to C. All signatures preferably contain a timestamp which has sign date and time. C then discards the Merkle tree and archives just the signed root hash, because C can create the Merkle tree on demand from the stored ciphertexts as needed.
(31) Role of Enforcer, E: Each communication between L and C involves them independently passing the message to E for verification. Once E verifies that the message is not over-requesting or over-sharing data with respect to an approved court order, the message is passed on to the intended recipient (C or L). When surveillance data from C is approved by E and received by L, C sends the shared key, K.sub.CI directly to L, who can then decrypt the information and carry out the investigation. Although the enforcer can be any desired individual or group thereof, in one embodiment, the enforcer can preferably be a government watchdog or organization that oversees adherence to laws and rights by private companies and law enforcement agencies. Federal agencies have their own oversight entities, e.g., FBI is audited by the Department of Justice's Office of the Inspector General (“OIG”). Other federal agencies also have their corresponding auditing entities. These entities currently do auditing when needed, and hence the auditing always happens after the event. In one embodiment, the OIG can play a proactive role in auditing such process, and enforce accountability from the beginning, rather than play a reactive role and issue review and audit reports after-the-fact, as it currently does.
(32) Blockchain and its operations: The blockchain, BC, is preferably used as an official record for verification of actions performed, it can be used as an off-the-shelf enabling technology. When forwarding a request, each entity preferably posts a signed hash of the request and/or response to the blockchain—a transaction—all messages posted on the BC are signed. The BC also serves as a platform to announce new cases to public watch dogs and the general public without divulging investigation details. The miners ensure that only valid entities involved in an investigation can post transactions to the BC. SAMPL can be implemented using a permissioned blockchain with read-only access given to public. For efficiency and fast convergence, proof-of-stake can optionally be used as the distributed consensus mechanism. The infrastructure required for the BC can be maintained and managed by the judicial system to engender greater trust.
(33) In one embodiment, the following general assumptions can be made as to the various parties:
(34) 1) Judge J: The judge J is assumed to be honest, but forgetful, i.e., J might forget to unseal records at the right time. J is trusted to correctly generate a surveillance order (“SO”) and place it on the BC. Whenever SO's seal expires, members of U can choose to contact J to make public the contents of SO. U can then verify details of case, including contacting I as needed.
(35) 2) Law enforcement agency L: L is assumed to be malicious, in that L will try to over-request data beyond what is authorized by the SO issued by J. Once the SO is posted by Jon the blockchain, L will contact E with a surveillance request (SR). SR will be checked and ratified by E based on the SO and prevalent policies.
(36) 3) Company C: C is assumed to be malicious, in that C can over-share data beyond what is sought by the SR, and authorized by J's SO. If C fails to respond to an SR with a surveillance request response (“SRR”), then there are policy measures that can be exercised by J to enforce compliance.
(37) 4) Enforcer E: E verifies each SR generated by L and also verifies each SRR generated by C, respectively. E is assumed to be honest. The enforcer only knows I's anonymized identity, AI and pseudonymous identity, PI. In particular, E is not privy to I's real identity RI. E also preferably does not have access to the plaintext version of I's records stored with C (e.g., emails). When a certain threshold of failures on the part of L, C is reached (which can optionally be an implementation specific system parameter), E can choose to contact J and post a message to BC exposing identity of the faulty party. The enforcer preferably does not store information linking AI and PI after evaluating an SRR.
(38) 5) No collusion assumption: in one embodiment, L and C are assumed not to directly communicate with each other—instead, they preferably go through E for information exchanges. If L and C break this protocol and interact directly, auditable data structures can optionally be used to verify the operations of C. However, out of band, unbridled data exchange is difficult to prevent when both parties are complicit. Nevertheless, for accountability, it is in L's and C's interest to act according to due process, and go through E, and not collude.
(39) Embodiments of the present invention preferably provide the following privacy and security properties:
(40) 1) Accountability for L and C: Embodiments of the present invention preferably ensure that a malicious L and/or C cannot over-request, or over-share data, respectively, beyond that authorized by the SO, as long as they do not bypass the entire system, and collude via side-channels. This applies to both: over-requesting/over-sharing of the surveilled user's data, or data belonging to users not listed in the SO (not under surveillance).
(41) 2) Forgetful J: Embodiments of the present invention preferably enables an independent set of users, U (which can include for example, non-profit organizations including but not limited to the ACLU) who keep track of court order unsealing dates, to contact the courts to unseal non-sensitive information, contact the individuals who were being surveilled, and help them with further courses of action.
(42) 3) Security against malicious I and C: Embodiments of the present invention preferably ensure that a malicious/cannot make C fail E's queries by creating fake ZKP for their real, anonymous and pseudonymous identities. Also, a malicious C cannot create fake data for I and frame I.
(43) The following is a computational assumption for an embodiment of the present invention:
(44) Definition: The DDH problem is hard relative to G for all PPT algorithms A, there is a negligible function negl such that
|Pr[A(G,q,∂,∂.sup.X,∂.sup.Y,∂.sup.Z)=1]−Pr[A(G,q,∂,∂.sup.X,∂.sup.Y,∂.sup.XY)=1]|≤negl(λ)
where in each case the probabilities are taken over the experiment in which G(1.sup.λ) outputs (G, q, ∂), and then uniform x, y, z∈Zq are chosen.
(45) DESCRIPTION OF SAMPL: As a pre-requisite to using SAMPL for surveillance, I and C interact to setup keys, associated ZKPs, and other operations as outlined below. Surveillance on user I's data is preferably carried out with interactions between J, L, C, and E as also described below. In one embodiment, SAMPL has 7 protocols and 4 algorithms. A convention is preferably adopted that communication protocols are run between two or more entities, and algorithms are computations done by a single entity. It is assumed that all communication between entities takes place over secure and authenticated channels.
(46) Protocols 1 and 2 preferably bootstrap the communication between C and I, and the corresponding data exchange. These protocols are preferably required so that in case of surveillance request by L for I's data, E can verify the user data without gaining any knowledge about the identity of I.
(47) TABLE-US-00002 Protocol 1: Setup run between C and I. Input :Public parameters: Group , q = |
|, g, h ϵ
. Output:I establishes RI, AI, PI.sub.i, bSize and K.sub.CI with C. Parties :C and I. 1 User I sets up (VK.sub.AI, SK.sub.AI) and (VK.sub.PI.sub.
.sup.+.
(48) Protocol 1: This is preferably run by an individual I the first time he or she sets up an email account with company C. In Line 1, I does two 3-round ZKPs with C to prove that: 1) VK.sub.AI was produced by someone who has knowledge of SK.sub.RI, and 2) VK.sub.PI.sub.
(49) Next, I and C setup a shared key K.sub.CI using which I's emails stored on C's servers are encrypted. I and C also agree upon a batch-size bSize, which denotes the message-intervals at which I's emails will be batched, e.g., after every 100 emails. C preferably batches all of I's emails at bSize intervals and creates a Merkle hash tree for the batch with the hashes of the emails at the leaves; I preferably verifies and signs the root of the tree.
(50) TABLE-US-00003 Protocol 2: Exchange of data between C and I for a given batch. Input : Public parameters: bSize, bNum ϵ [1..maxbNum]. Output:C stores I's emails along with verification hashes. Parties:C and I. 1 Let .sub.bNum represent the set of all e-mail messages in bNum. 2 for each M.sub.x ϵ
.sub.bNum, x ϵ [1..bSize] do 3 | I encrypts M.sub.x:
.sub.x ← K.sub.CI(M.sub.x), sends
.sub.x to C. 4 | C stores
.sub.x. end 5 /* At the end of batch bNum of bSize messages: */ Let
.sub.bNum represent the set of all ciphertexts in bNum. 6 begin 7 | C generates hashes, H.sub.x = H(
.sub.x), for all the
.sub.x received | from I. 8 | C forms a Merkle tree M.sub.bNum, with the H.sub.xs at the leaves, | and R.sub.bNum as root of the Merkle tree. 9 | C sends M.sub.bNum and R.sub.bNum to I. 10 | I verifies that the root hash (R.sub.bNum) of M.sub.bNum is correctly | computed: | 10.1 If verification fails, I notifies C to retry. | 10.2 Else, I signs R.sub.bNum: σ.sub.RbNum ← Sign.sub.SK.sub.
.sub.x's for | batch bNum. end
(51) Protocol 2: Protocol 2 depicts I's emails being stored on C's servers. Before I and C preferably execute this algorithm, they would have already run Protocol 1 to setup the symmetric key K.sub.CI. I creates an email message M.sub.x and encrypts it with K.sub.CI, generating C.sub.x, before forwarding it to C (Lines 2,3,4). This already happens in OpenSSL, where the connections (and data transmitted) between two communicating entities are encrypted using pairwise symmetric session keys.
(52) At the end of the current batch bNum, let C.sub.bNum represent the set of all ciphertexts in bNum. C calculates hashes for all C.sub.x∈C.sub.bNum and uses them as leaves to create a Merkle hash tree M.sub.bNum (Lines 7,8). C sends M.sub.bNum and the root hash (R.sub.bNum) of the Merkle tree to I (Line 9). I preferably verifies that R.sub.bNum calculation is correct for the current batch. I signs the verified R.sub.bNum and sends σ.sub.R.sub.
(53) The communication model under SAMPL can be divided into four phases, which are illustrated depict in
(54) Phase 1 is illustrated in steps 1-7 of
(55) Phase 2 is illustrated in steps 8-11 of
(56) Phase 3 is illustrated in steps 12-15 of
(57) Phase 4 is illustrated in step 15 of
(58) TABLE-US-00004 Protocol 3: J issuing SO and posting SO on BC. Input :VK.sub.AI,VK.sub.PI of user I, , g, h ϵ
, q = |
| Output :J issues SO, sets up keys K.sub.JLC,K.sub.EJLC and transmits them to relevant parties. Parties :E,J,L, and C. 1 L issues a request to J:SR = (VK.sub.RI∥evidence). 2 J validates L's request. If “accept” ← Jdecide(SR), J generates IO = (VK.sub.RI∥evidence) and gives to L. 3 L gives IO to C; C validates the IO. If “accept” ← Cdecide(IO), C sends to J and L, (VK.sub.AI∥σ.sub.AI∥π.sub.AI), given to C by I in Protocol 1. 4 J validates C's response, checks if “true” ← Verify(VK.sub.RI,σ.sub.AI,π.sub.AI), and if “true” ← ZPKVerify(VK.sub.RI∥VK.sub.AI∥π.sub.AI∥zkpVerf), and does the following: 4.1 Pick K.sub.JLC ← {0, 1}.sup.λ, send to L and C. Pick K.sub.EJLC ← {0, 1}.sup.λ,. send to E,L,C.J also picks r.sub.2,r.sub.3 ← Z.sub.q, g,h ϵ
, and generates Pedersen commitments: Com.sub.1 = (g.sup.
metadata∥σ.sub.metadata∥C.sub.P1∥C.sub.P2∥C.sub.P3
,where CP1 = E.sub.JLC(P1) CP2 = E.sub.EJLC(P2) CP3 = E.sub.EJLC(σ.sub.JP2∥σ.sub.LP2∥σ.sub.CP2)
(59) Protocol 3: Protocol 3 presents the interaction between J, L, C, and E, which culminates in J issuing a surveillance order SO, and setting up surveillance-related keys. In Line 1, L approaches J with evidence of suspicious behavior on the part of I which forms the surveillance request (SR). Here, evidence represents the documented evidence supporting the SR. J has its own internal decision procedure, J decide. It decides whether to accept or turn down the request (Line 2). If J decides to reject the request, L will have to return with an updated request SR=(VK.sub.RI∥evidence'), if L wants VK.sub.AI to persist with the request.
(60) If the request SR is accepted, J preferably generates an intermediate order IO, and gives it to L who forwards it to C. If C decides to comply (according to C.sub.decide), it retrieves VK.sub.AI corresponding to VK.sub.RI, sends to L, along with π.sub.AI, and σ.sub.AI obtained in Protocol 1. L forwards this info to J (Line 3). If C decided to not comply with IO (e.g., request violates statutory company policy), C would address the reasons to L prompting potential intervention from J, which is a judicial matter and out of scope of SAMPL.
(61) On receiving info from C, J preferably independently verifies the ZKP associated with VK.sub.AI and the signature on it (Line 4). If the verification fails, J preferably notifies C and L, and exits. If the verification passes, J generates two symmetric keys: K.sub.JLC meant to be shared between J, L, and C, and K.sub.EJLC meant to be shared between E, J, L, and C. J preferably then issues a surveillance order SO which is preferably formatted as illustrated in
(62) These signatures are preferably then verified by J, encrypted with K.sub.EJ LC and added to SO as part of Part 3 (“P3”). The signatures are preferably included in the encrypted text to preserve the identity of L and C from public until the SO is opened to public. Signatures on C.sub.P1 and C.sub.P2 are verified by E to hold J, L, and C accountable. The different kinds of SOs are discussed in later in the application.
(63) TABLE-US-00005 Algorithm 4: L creating and posting SR on BC, and sending to E for verification. Input :SO created on BC. Output: Surveillance request SR created and sent to E. 1 begin 2 | L creates a surveillance request: | SR = (SO∥t = [t.sub.s,t.sub.e]∥VK.sub.AI∥C). 3 | L generates and posts H(SR) to BC. 4 | L sends SR to E, who handles it as described in Algorithm 5. 5 end
(64) Algorithm 4 illustrates an example of the surveillance request, (“SR”) that can be created by L after J posts SO to the blockchain, (“BC”). L preferably creates an SR by creating a tuple with the start/end dates for the requested surveillance time interval, I=[t.sub.s, t.sub.e] (see Line 2). L includes the AI of the intended surveillance target, VK.sub.AI. A reference to the original SO and the identity of C (whom the SR is intended for), is also preferably included in the SR, which can be in the form of a tuple. L then preferably posts the hash of the SR on the BC and forwards SR to E for verification (see Lines 3 and 4 of algorithm 4).
(65) In SAMPL, the Enforcer uses the start/end times listed in the SO, and the pseudonymous identities of the email senders listed in the SO to check for over-requesting by L and over-sharing by C. This can be extended to the Enforcer checking pseudonyms of recipients too, filtering by subject of e-mails, etc., which gives finer auditing granularity. This preferably will not affect the base system design, but can require more computations and verifications on the part of I, C, and E.
(66) TABLE-US-00006 Algorithm 5: E verifying SR received from L. Input :SR received from L Output: Accept or reject SR. /* Verify SR does not violate SO published on BC by J. */ 1 E retrieves K.sub.EJLC sent by J in Protocol 3, does P2 ← D.sub.EJLC(C.sub.P2), posted on BC, and accepts SR as valid if: 2 begin 3 | The VK.sub.AI of P2 and SR match. 4 | The time interval, t = [t.sub.s,t.sub.e] contained in SR is within the | timeline specified in P2. 5 end 6 If E accepts SR, a confirmation is posted on BC. Since all BC transactions are signed, we denote the corresponding transaction signature as σ.sub.SR.sup.E and SR is forwarded to C. 7 If E rejects SR, it notifies agency L and judge J, and SR is not sent to C. It also stores evidence of the reason for rejection, which will be provided to J,L upon request
(67) In algorithm 5, E preferably receives the SR from L and processes the SR. The verification preferably includes checking that the time interval I from SR is a sub-interval of the timeline contained in P2 of SO. After E verifies SR, it preferably signs the hash, H(SR), and posts the signature σ.sub.SR.sup.E on BC. Then SR is forwarded to the C that is preferably listed as the intended receiver in SR. If SR fails to verify with E, no message is posted on the BC, and SR is not forwarded to C. If fine-grained accountability is desired, the failure message can optionally be posted to BC, identifying the reason and scope of the failure.
(68) TABLE-US-00007 Algorithm 6: C creating SRR, posting H(SRR) on BC, and sending SRR to E for verification. Input :SR received from E. Output:SRR created and forwarded to E. /* When C receives a validated SR from E, it does the following: */ 1 begin | /* SO verification */ 2 | C decrypts .sub.P3 of SO contained in SR, verifies signatures | σ.sub.JP2, σ.sub.LP2, C then decrypts P2 of SO, verifies σ.sub.JP1, σ.sub.LP1, | It then checks if (t,VK.sub.AI) contained in SR corresponds to | what it had signed in σ.sub.CP2. 3 end /* C create an SRR in response to the SR as follows */ 4 begin 5 | C retrieves and verifies signature σ.sub.SR.sup.E posted on BC. 6 | Let
.sub.bNum represent the set of all ciphertexts in bNum. 7 | for each
.sub.x ϵ
.sub.bNum; x ϵ [1..bSize] for VK.sub.AI do 8 | | if
.sub.x was created during time-period t = [t.sub.s,t.sub.e] from | | SR then 9 | | | Add
.sub.x∥siblingHashes(
.sub.x)∥bNum∥σ.sub.R.sub.
SR∥L∥
.sub.x∥siblingHashes(
.sub.x)∥ | bNum∥σ.sub.R.sub.
13 | C generates and posts H(SRR) on BC. 14 end /* C sends SRR to E. */ 15 C sends SRR to E, who processes it as described in Algorithm 7.
(69) TABLE-US-00008 Algorithm 7: E verifying SRR received from C. Input :SRR received from C. Output:Accept or reject SRR. 1 E retrieves SR from SRR, and verifies signature σ.sub.SR.sup.E posted on BC. 2 for each .sub.x ϵ SRR;x ϵ [1..bSize] do 3 | E confirms that
.sub.x is dated within time period t from the | SR. 4 | E computes H(
.sub.x). runs | R.sub.bNum ← rootCompute(
.sub.x∥siblingHashes(
.sub.x)∥bNum), | and checks “true”
Verify(VK.sub.PI.sub.
(70) Algorithm 6 and algorithm 7 cover interaction between E and C, as illustrated in
(71) In algorithm 6, when C receives a verified SR from E, C preferably verifies that I and VK.sub.AI listed in SR are the ones actually signed by C in P2 of SO (See line 2 of algorithm 6). C preferably then creates an SRR in response to SR. C checks each message stored corresponding to VK.sub.AI listed in the SR. If some message (“M.sub.x”) in batch (“b.sub.Num”) matches the surveillance time (“I”) in SR, then the encrypted message (“C.sub.x”), the sibling hashes for H(C.sub.x) in the Merkle tree for b.sub.Num, and σ.sub.bNum are preferably added to the SRR by C (See line 9 of algorithm 6). C preferably also includes the ZKP for the VK.sub.PI.sub.
(72) For ease of exposition, SRR creation for one batch (b.sub.Num) is presented. However, if there exist multiple batches, b.sub.Num.sub.
(73) In algorithm 7, E preferably receives the SRR from C, and parses its contents. E verifies the signature (σ.sub.SR.sup.E) on the corresponding SR (See line 1 of algorithm 7). For each C.sub.x that appears in SRR, E checks that the message is dated within the time period I=[t.sub.s, t.sub.e] from SR (See line 3). Then, the root hash for C.sub.x, R.sub.bNum, is preferably computed using the sibling hashes for C.sub.x provided in SRR, and the signature σ.sub.R.sub.
(74) TABLE-US-00009 Protocol 8: L on receiving validated SRR from E. Input :Verified SRR received by L from E. Output: Surveillance carried out by L. Parties :L and C. 1 L receives SRR, and posts a signed hash of SRR to BC as acknowledgment of SRR received. 2 L gets K.sub.CI from C to decrypt I's emails ( .sub.x's contained in SRR), and carry out surveillance.
(75) In Protocol 8, once L receives a validated SRR from E, it preferably posts a signature on the hash of SRR to BC as acknowledgment. L then preferably asks C to hand over K.sub.CI to be able to decrypt I's encrypted emails in SRR and conduct surveillance.
(76) Protocol 9 is preferably not a part of the regular workflow of SAMPL and is optionally executed by members of U on an as needed basis. It can optionally be implemented using smart contracts. In Protocol 9, any member(s) of a set of watchdog organizations, u∈U (e.g., ACLU), who monitor the BC, can contact J whenever an SO expires and retrieve K.sub.JLC, K.sub.EJLC. Entity u preferably decrypts the SO (P1 and P2), verifies signatures (P3), and can contact I who was surveilled. I and u can then investigate and verify the validity of reason for surveillance, if due diligence was applied, and lawful procedures were followed during surveillance.
(77) TABLE-US-00010 Protocol 9: Protocol run by members of U. Input :SO posted on BC. Output :u checks adherence to protocol by parties involved in surveillance in relation to SO and follows up with J. Parties :u ϵ and J. /* Whenever there is a message posted on BC by E: */ 1 u ϵ
checks the signatures of the hashes posted. /* Whenever an SO expires according to t ϵ [t.sub.s,t.sub.e] posted on BC: */ 2 u contacts J and retrieves K.sub.JLC,K.sub.EJLC. u decrypts P1, P2 and verifies P3 of the SO.
(78) The U.S. constitution provides several authorization paths for law enforcement agencies to obtain permission to conduct surveillance, some with judicial oversight, some without. The Electronic Communications Privacy act (“ECPA”) was created by the U.S. Congress in 1986 to elucidate the boundaries of government surveillance on citizens, and clearly define the ways and means by which government surveillance can be conducted. The ECPA can be used by federal law enforcement agencies to obtain information about users' emails in transit, emails at rest, phone calls, location data, and more. The ECPA provides law enforcement agencies two methods of accessing users' information: via a warrant, or via a subpoena. A subpoena is a court order demanding that someone or something be provided to assist in a case. For issuing a warrant, the law enforcement agency must show the issuing judge probable cause that a crime has been or will be committed. Most warrants are unsealed when charges are filed against someone, and the defendant has the right to see the evidence collected against them before the trial.
(79) Per ECPA statute 18 U.S.C. § 2616 and statute 18 U.S.C. § 2703, emails in transit, emails in storage on a home computer, and unopened emails in remote storage stored for up to 180 days need a warrant for law enforcement access. Opened emails in remote storage, and unopened emails stored for greater than 180 days only need a subpoena for law enforcement access.
(80) Embodiments of the present invention can be deployed in a straightforward manner in both cases, as previously described, where the SO written to the blockchain by J can be either a subpoena or a warrant. The SR and the furnished data are preferably all routed through Enforcer, E, who writes the data transfer success/failure to the blockchain BC for auditing as previously described.
(81) The USA Patriot act § 505 empowered the Federal Bureau of Investigation (“FBI”) to issue a National Security Letter compelling companies to disclose information about their customers for a national security-related investigation. A national security letter (“NSL”) is typically issued to a company by a local FBI field office and does not require judicial oversight. It can be used to obtain meta-information about phone/email records, times, length of service, network addresses, and how a customer paid for service; although the FBI cannot obtain actual content of phone/email records. An NSL can also be used by the FBI to obtain financial details, such as credit reports, and bank account details from banks, credit unions and insurance companies. Any recipient of an NSL is prohibited by law or “gagged” from disclosing their receipt of the NSL, which makes oversight difficult. Additionally, the U.S. government can seek judicial enforcement of an NSL in non-compliance situations, under ECPA statute 18 U.S.C. § 2709.
(82) Because an NSL does not require a judge, there is no J to post the SO to BC. But L and C can still use SAMPL and hence E for auditability. In this case, L can create an SO for the NSL, post it on BC, and then create an SR, before sending it to E. E can then pass it on to C, after checking that the SO and the SR do not request content of emails, which is a legal restriction on NSLs. Note that E cannot check if a SO is for a genuine national security issue, because U.S. law expressly gives discretionary powers to the FBI while deciding to issue NSLs. But what E can help check is if the SO and SR adhere to legal guidelines—that is, the agency is only seeking meta-information. On receipt of the SR from E, C will preferably construct and return an SRR to E, who will then verify it and send it to L.
(83) The pseudonymous identity scheme of embodiments of the present invention prevent E from learning the actual identities of the users whose details were requested. As discussed before, E preferably writes the pass/fail result of the SR and SRR to the BC.
(84) Foreign Intelligence Surveillance Act (“FISA”) was enacted in 1978 and amended in 2008 by the U.S. Congress for the purposes of surveillance related to foreign powers and persons. Under FISA, a person who is believed to be a foreign power, or spying on behalf of a foreign power, can be put under surveillance, even if they haven't engaged in any criminal activity. Over the years, the ambit of FISA has gradually expanded to include electronic surveillance, “roving wiretap” surveillance, pen-registers, and trap-and-trace devices, per 50 U.S.C. Ch. 36. Additionally, FISA permits warrantless surveillance up until certain time periods, beyond which the agency conducting the surveillance needs to obtain a warrant from a special court called the FISA court. Although the court maintains records of its proceedings, the FISA court's records are not available to the public.
(85) Embodiments of the present invention can be applied to the FISA ecosystem, which encompasses the court, and surveilling agencies which work with it—including but not limited to the NSA. The FISA ecosystem operates with little to no auditability (other than annual aggregate statistics published by the court). Using embodiments of the present invention, the FISA court judges will issue and post an encrypted SO on the BC. The E can verify that the surveillance is not conducted in wholesale or an overarching manner by agencies, and only data that is pertinent to an ongoing investigation is revealed by companies. In particular, embodiments of the present invention allow independent non-profit organizations to verify if due process has been followed during FISA-authorized surveillance, even if the actual court orders are never made public, without compromising national security.
(86) In the U.S. legal system, a government agency, which can include for example FBI or NSA is, in most cases, required to present a warrant to a company for conducting surveillance on its customers, and conduct the surveillance within the confines of the warrant. Unfortunately, in practice, there are agency overreaches; including for example:
(87) 1) In 2018, the NSA's office of inspector general (“OIG”) in its first semi-annual unclassified report to the U.S. Congress described the investigations and activities of the NSA. Among other findings, the OIG report found “several deficiencies that have the potential to impact the protection of U.S. persons privacy rights,” in relation to FISA investigations conducted by the NSA.
(88) 2) A report by the department of justice (DoJ) OIG found that the FBI issued NSLs “contrary to statutory limitations,” issued “improper requests under the statute referenced in the NSL”, “obtained information beyond the time period referenced in the NSL,” and various other illegal uses of NSLs. A partially redacted 300-page report by the DoJ OIG also found that the FBI acquired phone call information regarding “hot numbers” without legal process, made inaccurate statements to the FISA court, and improperly used FBI administrative subpoenas. The OIG report also found that the FBI used “exigent letters” and other informal requests for phone records that do not comply with legal requirements or FBI policies governing the acquisition of those records. The same report also found the FBI has a practice of conducting “sneak peeks” for telephone toll records in providers' databases without due process, a practice that violates the ECPA statute 18 U.S.C. § 2702(a)(3).
(89) All said, embodiments of the present invention can help systematize a seemingly unpredictable process that can help law enforcement agencies and companies ensure that they follow the letter of the law with respect to issuing and responding to surveillance requests respectively.
(90) Embodiments of the present invention can also be used in the well-known universal composability (“UC”) framework. The UC paradigm elegantly captures the conditions under which a given distributed protocol is secure, by comparing it to an ideal realization of the protocol. To this end, the UC framework defines two “worlds”: the real-world, where the protocol, π to be proved secure runs in the presence of a real-world adversary, A. The other is the ideal-world, where the entire protocol, ϕ is executed by an ideal, trusted functionality, in the presence of a simulator, S, which models the ideal-world adversary. All users only talk to an ideal functionality via secure and authenticated channels, the ideal functionality takes input from users, performs some computations in a possibly interactive manner, and returns the output of the protocol. The goal then is to prove that no distinguishing algorithm, commonly referred to as the “environment”, Z, can successfully distinguish between the execution (“EXEC”) of the two worlds.
(91) Ideal functionality, F.sub.Surveil, which encompasses all these functionalities and algorithms, and consists of four independent ideal functionalities, F.sub.Surveil=(F.sub.zk.sup.SAMPL, F.sub.init, F.sub.create, F.sub.BC). Furthermore, F.sub.Surveil is assumed to maintain an internal state that is accessible at any time to F.sub.zk.sup.SAMPL, F.sub.init, F.sub.create, F.sub.BC.
(92) Theorem 1: Let F.sub.Surveil be an ideal functionality for SAMPL. Let A be a probabilistic polynomial-time (“PPT”) adversary for SAMPL, and let S be an ideal-world PPT simulator for F.sub.Surveil. SAMPL UC—realizes F.sub.Surveil for any PPT distinguishing environment Z.
(93) SAMPL can apply to other types of surveillance criteria by modifying the way that user records are stored by C. In case of email, the sender and receiver names and their IP addresses can be salted and hashed separately and stored along with other details, which can include for example date and time as well as metadata. This information can be listed in the SO and subsequently verified by E without learning the actual values. This enables search based on sender/receiver names and/or IP addresses. Searchable encryption can be implemented to search based on specific keywords in the data records. Although this increases the types of surveillance auditable, it leaks more information to E.
(94) SAMPL can also be extended to allow a user to delete historical records. The user preferably updates the data record to a generic “deleted message,” the Merkle root for the given historical batch is recalculated with the new message, and the user signs the updated Merkle root with the current SK.sub.PI. Every time VK.sub.PI gets updated by the user, C preferably verifies the ZKP and also verifies the signatures on the Merkle root so that I cannot inject fake data and/or signatures to frame an honest C. For practicality, the management of users' VK.sub.PIs can be handled by software, which can include for example keystores, plugins, etc.
(95) There can be instances where a single user is part of multiple surveillance requests. In that case, each SO has VK.sub.AI, and E can link it to the corresponding VK.sub.PI using the ZKP provided by C. Embodiments of the present invention optionally do not provide unlinkability of the independent surveillances to a user's VK.sub.PI.
(96) SR can also include requests for system logs showing activity of a certain user identified by VK.sub.AI. If the logs contain VK.sub.RI, to preserve privacy, C can optionally replace it with VK.sub.AI. If the logs contain VK.sub.PI, then C preferably furnishes the ZKP associated with VK.sub.PI. Unlike data such as emails, users preferably do not see the logs, hence do not sign them.
(97) There are several design choices in that are implementation-specific and thus can be altered to provide desirable results for different applications a few such aspects include:
(98) 1) Set of Enforcers: The assumption on E can be relaxed from being assumed to be honest to being honest but curious. To provide unlinkability of users' PIs over multiple surveillances for a given time period, nonoverlapping striping of data across the set of Es, when sending SR or SRR can optionally be used. Note that the sets of enforcers chosen by L and C need not be the same. This increases the efficiency of verification of the system, as data for verification is not duplicated between different Es. As long as the number of SOs for a given AI does not exceed the number of enforcers in the system, the unlinkability assumption will hold (due to the non-overlapping striping).
(99) 2) Internal decision procedures of J, L, and C: Certain actions are largely dependent on the specific jurisdiction, and are governed by the laws of the country where J, L, and C operate. What exactly J, L, and C do when any of their internal decision procedures return a “reject” in the course of operation can be adjusted to fit a particular application. For example, a policy can be implemented to determine what happens when C decides to reject the IO when the IO violates statutory company policy in some way. Or to determine the course of action for L to follow if J decides to reject its surveillance request.
(100) 3) Handling Multiple Users: Although this application attempts to maintain brevity and ease of reading by describing embodiments of the present invention with respect to a single user being surveilled by L, embodiments of the present invention can easily be extended to multiple users (I 1 . . . α) by modifying the SO to include a list of users' identities. This would result in VK.sub.RI.sup.1, . . . , VK.sub.RI.sup.α, VK.sub.AI.sup.1, . . . , VK.sub.AI.sup.α, and VK.sub.PI.sup.1, . . . , VK.sub.PI.sup.α. When multiple identities are surveilled, J preferably salts each users identity by adding a random string to each identity (VK.sub.RI.sup.1, . . . , VK.sub.RI.sup.α) and hash it before putting it in P1 of SO. This randomization, added to each identity, will help protect the identities of each of the surveilled users from each other whenever the SO expires and is released to the individuals being surveilled. The random salts for all the VK.sub.RI's are preferably shared with L and C.
(101) 4) Hard reject/soft reject: Whenever an SR or SRR is rejected by E, perhaps due to clerical errors, administrative errors, or otherwise honest mistakes on the part of C or L, E preferably just responds with a reject message and takes no further action. This is referred to as a “soft reject”. E can assess how many times a certain party's request/response has been rejected. Once this number of rejections reaches a threshold, which can be a system parameter, E can optionally inform the party whose request/response was rejected, and the judge J, and can store a local copy of the reason for the rejection (to provide to J upon request), and writes a “fail” message to the BC—a hard reject. Note that for fine-grained information on errors and/or malicious behaviors, E can choose to post a soft reject on BC.
(102) 5) Auditable data structures: Auditable data structures implemented on C's servers can also be used by E to verify that C is non-malicious and complying with court orders. This implementation would preferably include careful system design with read/write counters on the data stores with E having access to the counters.
(103) TABLE-US-00011 TABLE 3 Surveillance Period (Days) 5 10 50 Number of 5 10 15 30 5 10 15 30 5 10 15 30 Users ZKP 0.039 0.0795 0.1207 0.2003 0.0750 0.1528 0.229 0.459 0.369 0.740 1.109 2.219 Verification for PI.sub.i (s) Merkle Root 0.140 0.259 .382 0.619 0.246 0.475 0.705 1.390 1.1178 2.224 3.32 6.64 Generation (s) Merkle Sign 0.015 0.0304 0.046 0.0767 0.0286 0.0583 0.057 0.1757 0.141 0.282 0.423 0.846 Verification (s)
(104) 6) Forward Security: If one of I's previously used SK.sub.PI gets compromised and C gets access to it, C can fake I's historical data by modifying the Merkle trees for past batches and signing them with the compromised key. To guard against this, each time I chooses a new PI, a new Merkle tree is preferably created between I and C whose leaves are the signed root hashes of the past batches. The root of this new hierarchical Merkle tree is preferably signed with the new PI. This operation can be repeated for each new PI to make it harder for a malicious C to frame I, because C would need to compromise multiple SK.sub.PIs belonging to I.
(105) TABLE-US-00012 Protocol 10: Setup of (RI, AI) keypairs. Inputs :Public parameters: Group , q = |
|, g, h ϵ
. ZKP Claim: VK.sub.AI was generated by someone with knowledge of SK.sub.AI,SK.sub.RI. Witness: SK.sub.AI,SK.sub.RI. Output :Signed ZKP: Sign.sub.SK.sub.
(X.sup.s .Math. y.sub.1) mod q, and if | Y.sup.z
(Z.sup.s .Math. y.sub.2) mod q. If checks verify, C accepts the | response as valid, asks I to send signed transcript of | proof, π.sub.AI. 9 | I sends | σ.sub.AI = Sign.sub.SK.sub.
(106) Zero-Knowledge Proofs Between I and C: Protocol 10 is preferably initiated by I when she needs to establish her real identity RI (corresponding to an email address and represented by keypair (VK.sub.RI, SK.sub.RI) and tie it to an anonymized identity AI (corresponding to a nickname for the email address and represented by keypair VK.sub.AI, SK.sub.AI). I can choose to create a new AI if she needs to change the current AI in case SK.sub.AI gets compromised. Protocol 10 preferably enables I to establish her (VK.sub.RI, SK.sub.RI), (VK.sub.AI, SK.sub.AI) keypairs, and prove in zero-knowledge to C that VK.sub.AI could have been generated only by someone who had knowledge of SK.sub.AI, and that the two key-pairs are related to each other by a DDH tuple. To this end, I and C preferably do a Chaum-Pedersen-style interactive ZKP for I to prove her anonymized identity, AI to C. The proof π.sub.AI can be made non-interactive by applying the Fiat-Shamir transform. If C chooses to accept the proof as valid, it asks I to send a signed copy of the transcript of the proof, σ.sub.AI. C preferably stores π.sub.AI and σ.sub.AI.
(107) TABLE-US-00013 Protocol 11:Setup of (PI.sub.i) keypair. Inputs :Public parameters: Group , |
| = q, g, h ϵ
, VK.sub.AI,SK.sub.AI. Claim : VK.sub.PI.sub.
(Y.sup.s.sub.
(Q.sup.s1 .Math. y′.sub.2) mod q. If checks verify, C accepts the | | response as valid, asks I to send signed transcript of | | proof, π.sub.PI.sub.
(108) Protocol 11 is preferably initiated by I when she needs to establish her pseudonymous identity (“PI”) keypair VK.sub.PI, SK.sub.PI, where i∈[1 . . . m]. I could have multiple PIs tied into a single AI, but preferably only one can be active at a given point in time. I creates a new PI.sub.i+1 if SK.sub.PI.sub.
(109) Protocol 11 is preferably used for I to establish her (VK.sub.PI.sub.
(110) Note that the ZKP and the signature on the ZKP can be replaced by a single signature zero-knowledge proof of knowledge.
(111) UC Functionalities and Analysis: The notion of UC security is preferably captured by the pair of definitions below:
(112) Definition (UC-emulation)—Let π and ϕ be probabilistic polynomial-time (“PPT”) protocols. π UC-emulates ϕ if for any PPT adversary A there exists a PPT adversary S such that for any balanced PPT environment Z we have EXEC.sub.ϕ,S,Z≈EXEC.sub.π,A,Z
(113) Definition (UC-realization)—Let F be an ideal functionality and let π be a protocol. π UC-realizes F if π UC-emulates the ideal protocol for F.
(114) The functionalities of F.sub.Surveil are preferably described as: F.sub.zk.sup.SAMPL, F.sub.init, F.sub.create, FBC. F.sub.Surveil is assumed to maintain a table τ, with information about the individuals being surveilled, and the surveillance orders. A single row of the table would look like: (VK.sub.RI, SO, soid) where soid denotes the id number of the SO which is associated with VK.sub.RI. ⊥ is used to denote unresponsive parties, malformed replies to the ideal functionalities, and ideal functionalities returning fail messages to parties.
(115) Ideal functionality for zero-knowledge proofs F.sub.zk.sup.SAMPL is preferably defined based on the ideal zero knowledge functionality, F.sub.zk. In embodiments of the present invention, F.sub.zk.sup.SAMPL is preferably restricted only to discrete-log relations, and also involves the ideal functionality writing the claim to the shared table τ. F.sub.zk.sup.SAMPL is given as:
(116) TABLE-US-00014 Functionality F.sub.zk.sup.SAMPL F.sub.zk.sup.SAMPL proceeds as follows, running with prover, verifier C, an adversary S. Let G be a prime-order cyclic group, ∂ ϵ G, |G| = q, and a ϵ Z.sub.q (1) Upon receiving (VK.sub.RI, sid, a) from I, if ∂.sup.a = VK.sub.RI, send (VK.sub.RI, sid) to C and S, else exit. Write (VK.sub.RI) to table τ and exit.
and the F.sub.zk functionality is given as:
(117) TABLE-US-00015 Functionality F.sub.zk F.sub.zk proceeds as follows, running with a prover P , verifier V, and an adversary S, and parametrized with a relation R: (1) Upon receiving (zk - prover, sid. x, w) from P, if R(x, w) = 1, send (zk - proof, sid, x) to V and S and exit. Otherwise exit.
F.sub.zk.sup.SAMPL is parametrized by a prime-order cyclic group G, |G|=q, g∈G, a∈Z.sub.q, and a session id, sid. The prover, I preferably sends a claim to be proven, VK.sub.RI to F.sub.zk, and a witness a. F.sub.zk checks if ∂.sup.a=VK.sub.RI, i.e., if the claim is correct and forwards VK.sub.RI to the verifier C and the ideal-world adversary S, and writes VK.sub.RI into table τ.
(118) F.sub.zk is preferably parametrized by a relation R, and a session id, sid. The prover, P preferably sends a claim to be proven, x to F.sub.zk, and a witness w. F.sub.zk preferably checks if R(x, w)=1, i.e., if the claim is correct and forwards x to the verifier V and the ideal-world adversary S.
(119) The F.sub.init preferably uses the following ideal functionality for issuance of SO:
(120) TABLE-US-00016 Functionality .sub.init (1) L sends
.sub.init a tuple requesting for an IO, (create - |O, evidence, VK.sub.RI), which
.sub.init forwards to J. J replies with either (accept, VK.sub.RI) or ⊥. If J responds with ⊥,
.sub.init returns ⊥ to L and exits. (2) If J accepts the IO request,
.sub.init creates an intermediate order IO = (VK.sub.RI, evidence) and sends it to C. C can either send(accept) or ⊥ to
.sub.init. If C sends (accept),
.sub.init checks if VK.sub.RI is present in table τ. If yes,
.sub.init proceeds to the next step. If either C sends ⊥, or VK.sub.RI is not present in τ,
.sub.init sends ⊥ to J, L, C and exits. (3)
.sub.init picks a symmetric key, K ← {0, 1}.sup.λ, and gener- ates data ← {0, 1}.sup.λ, creates a surveillance order tuple, SO = (metadata, (
= E.sub.K(VK.sub.RI, data)), and picks an soid ϵ
.sup.+.
.sub.init writes (SO, soid) to τ in the VK.sub.RI row.
.sub.init sends (K,
) to J, L, C.
.sub.init calls
.sub.BC and writes SO to the blockchain. (4) At the time of unsealing of SO,
.sub.init sends I a tuple SO = (metadata,VK.sub.RI, data) and exits.
and preferably interacts with J, L, and C and preferably initiates the process for creating a SO, and posts the SO to the BC. L initiates contact with F.sub.init by sending a (create—IO, evidence, VK.sub.RI) request tuple to F.sub.init. F.sub.init forwards the request to J, who can accept or decline it. If J accepts, F.sub.init preferably creates an intermediate order IO=(VK.sub.RI, evidence) and forwards the IO to C. C can either accept or decline the IO. If either J or C declines the IO request, F.sub.init preferably aborts the execution and exits. If C accepts, F.sub.init preferably checks if VK.sub.RI was deposited in the shared table τ by F.sub.zk.sup.SAMPL.
(121) If yes, it means VK.sub.RI was verified by F.sub.zk.sup.SAMPL. F.sub.init then generates a key K←{0, 1}.sup.λ, preferably generates a string regarding the surveillance order, data←{0, 1}.sup.λ, which includes evidence provided by L, crimes committed by VK.sub.RI, reason for sealing, etc. It also preferably generates metadata, which can include the date the SO will be unsealed. F.sub.init, writes (SO, soid) to the table τ, in the VK.sub.RI row. F.sub.init then creates the SO tuple: (metadata, C=EK (VK.sub.RI, data)) sends (K, C) to J, L, C, calls F.sub.BC and posts the SO on the BC. Finally, when the SO needs to be unsealed, F.sub.init proactively contacts I, whom VK.sub.RI belongs to, and gives her the decrypted contents of the SO.
(122) F.sub.create is given as:
(123) TABLE-US-00017 Functionality F.sub.create (1) L sends a tuple (create - SR, VK.sub.RI) to F.sub.create. F.sub.create looks up the SO corresponding to VK.sub.RI in τ. If none exists, F.sub.create sends ⊥ to L and exits. Else. F.sub.create gen- erates an SR = (SO, VK.sub.RI) and forwards it to L and C. (2) C replies to F.sub.create with a tuple (VK.sub.RI, records ← {0, 1}.sup.λ, where records ← {0, 1}.sup.λ denote VK.sub.RI's emails, and verification metadata. If C replies with ⊥. F.sub.create will call F.sub.BC and write (SO, C) to the BC and exit. (3) In response to C's tuple, F.sub.create verifies records, and creates an SRR = (SO, records) tuple, and forwards to L and C. (4) F.sub.create calls F.sub.BC, posts H(SR) and H(SRR) to the BC and exits.
(124) F.sub.create creates a request SR and response SRR. L preferably first contacts F.sub.create for creating an SR by sending VK.sub.RI, upon which F.sub.create looks up table τ for an SO corresponding to VK.sub.RI. If none has been entered by F.sub.init, that means L is not authorized to surveil VK.sub.RI, and F.sub.create returns ⊥ to L. Else, F.sub.create proceeds with generating SR and forwards SR to L and C. At this point, C is expected to respond to SR with VK.sub.RI's emails, batch information, and Merkle tree information required to verify the emails are from the correct batches.
(125) All this information is preferably represented by a string, records. If C ignores the request, F.sub.create will preferably write C's identity to BC, along with the associated SO (this means C is behaving maliciously). If C responds with the records, F.sub.create will preferably first verify that the records belong to the surveillance time-period as given in the metadata part of the SO. If verification succeeds, F.sub.create will create the SRR, which will be sent to L and C. Finally, F.sub.create preferably posts the hash of SR, SRR to BC respectively.
(126) The blockchain functionality, F.sub.BC, is given as:
(127) TABLE-US-00018 Functionality F.sub.BC (1) F.sub.BC receives three kinds of write messages: Finit writes SO, F.sub.create writes (SO, C) and F.sub.create writes (H (SR), H (SRR)). F.sub.BC writes the tuples to the blockchain and sends a copy of the newest block B to all parties, J,L,C,I by sending a tuple (update, B). (2) Each party either replies with (agree, B) or ⊥. In the former case, the party updates the local copy of the blockchain, and is synced with the global blockchain. However if the reply was ⊥, the party now has an outdated copy of the blockchain. (3) In the event that an outdated. party wants to get synced with the blockchain it sends a message (read) to F.sub.BC, F.sub.BC replies with (update, B′). where B′ is the copy of the entireblockchain.
(128) F.sub.BC receives messages from F.sub.init and F.sub.create. F.sub.BC writes tuples to the blockchain, and sends a copy of the new block, B, to parties J, L, C, I. This is preferably done by sending (update, B). The party can either accept the update, or decline (unresponsive, disconnected, or non-cooperating parties). When a dormant party wishes to update itself, it can request a copy of the full blockchain by sending a read message to F.sub.BC.
(129) Correctness: The privacy properties that embodiments of the present invention aim to provide are accountability for L and C, protection against a forgetful J who might forget to unseal orders, and protection against a malicious I and C. Accountability is provided by the fact that F.sub.create generates the SR and SRR, thus ensuring that no data is over-requested by L, or over-shared by C, both in terms of redundant data belonging to the same user, or other users' data. F.sub.init creates the SO and guarantees that the SO will get unsealed by F.sub.init before it exits, thus providing protection against forgetful J. Because F.sub.zk.sup.SAMPL checks the witness and generates the ZKP for each VK.sub.RI, it ensures that a user cannot create a fake ZKP for VK.sub.RI, that passes verification, yet the corresponding SK.sub.RI cannot be used for decrypting the user's email records. Protection against a malicious C which tries to include fake data in an SRR is provided by F.sub.create, which verifies C's returned user information before creating an SRR.
(130) Some configuration choices that are preferably made for an embodiment of the present invention include:
(131) 1) In F.sub.init, J, C can preferably return to F.sub.init in Step 1 and Step 2 respectively. This is to model the fact that in the real-world, J has the right to refuse a surveillance request by L, and C has the right to refuse or appeal an intermediate order by J.
(132) 2) F.sub.init preferably creates an SO, and F.sub.create preferably generates the SR and SRR for SO, but only after being contacted by L (Step 1 of F.sub.create). This is because in the real-world, L might get an SO authorized by J, but may choose not to follow it up with any action, i.e., eventually not conduct any surveillance, e.g., because L needs to invest its limited resources in higher-priority matters, budget cuts after SO was issued, etc.
(133) 3) F.sub.create preferably writes C's identity to the BC if C doesn't respond with I's email records in Step 2 of F.sub.create. For example, it may be assumed that I is an (email) customer of C, and C will have email records associated with I for the surveillance period. These emails are preferably stored only with C. If C deliberately chooses not to respond to, or refuses an SR, after having accepted the IO that the SR is a follow up on (F.sub.init, Step 2), then that can only be construed as malicious behavior on the part of C. Hence F.sub.create will expose malicious C's identity on the public BC.
(134) Proof of Theorem 1: An embodiment of the present invention can describe a simulator S such that for any real-world A running with SAMPL, Z cannot distinguish A from an ideal-world S running with F.sub.Surveil. S runs A internally, simulates all inputs A is expecting, and gives A's outputs to F.sub.Surveil, who will complete the simulation in the ideal-world. S reflects the choices of A in the ideal-world, and reflects the protocol outcomes and aborts of the ideal-world in the real-world. If A cheats, S aborts.
(135) That is, any attempt by A to cheat in the real-world will result in the protocol aborting in both, the ideal and real worlds. Hence it follows that at no PPT Z can distinguish between EXEC.sub.SAMPL, A, Z and EXEC.sub.F.sub.
(136) First, S needs to create keypairs (VK.sub.RI, SK.sub.RI), (VK.sub.AI, SK.sub.AI), (VK.sub.PI.sub.
(137) S will also preferably generates the zero-knowledge proofs associated with VK.sub.AI and VK.sub.PI.sub.
(138) S then preferably sets up shared key K.sub.CI of Protocol 1, and passes it to A, if A has corrupted either C and/or I. S creates a key K←{0, 1}.sup.λ by calling F.sub.init, and passes it to A. Finally, S generates a random batch-size bSize and gives to A. This completes the simulation of the setup phase.
(139) Next, S needs to pass on inputs to A during the SO creation phase, and simulate the corresponding actions in the ideal-world (actions of Protocol 3). If A has corrupted L, A will generate the SR=(VK.sub.RI, evidence), else, S generates the SR=(VK.sub.RI, evidence) and gives the SR to A (recollect from the adversary model that J is forgetful, but not malicious). In other words, A cannot corrupt J.
(140) Once J (impersonated by S) has received the SR from A, J will validate it, and decide whether to accept it or not. Once J decides, it will give its output to A. A will then pass on the IO to C, through corrupted L. C will decide whether to accept the IO or not. If A has corrupted C, then this communication is handled locally by A, and need not be simulated. If C is honest, its action will be simulated by S.
(141) C responds to the IO, and generates an SRR=(VK.sub.AI∥π.sub.AI∥σ.sub.AI), and sends SRR to J, L. In the ideal world, S calls F.sub.init, which creates an IO and sends to J, L, C. If A cheats, i.e., includes a wrong π.sub.AI, σ.sub.AI inside the SRR, then S will send a corresponding malformed message to F.sub.init, which will then abort (Step 2 of Functionality of F.sub.init), and S aborts the execution of A. S then generates the SO as an honest J would, and gives the final SO to A. If either of C or L are corrupted by A, or if a subset of E are corrupted by A, S will send the K.sub.JLC and/or K.sub.EJLC to A. The SO generation by S is straightforward (simulate S.sub.sig for signatures, F.sub.sig in the ideal-world, etc.). If at any step, the signatures in the SO sent by A do not verify, S preferably aborts. In the ideal-world, S calls F.sub.init who will in turn call F.sub.BC and posts the SO to the blockchain.
(142) The next step for S is to simulate the storage of I's emails on C (see Protocol 2). There are three cases to consider:
(143) 1) Case 0: If both I and C are corrupted by A, this is handled locally by A, and does not need to be simulated.
(144) 2) Case 1: If C is corrupted, but I is not, S creates I's outputs, i.e., for each M.sub.x∈M.sub.bNum, x∈[1 . . . bSize], S generates a C.sub.x. A, playing the role of corrupted C will create a Merkle hash tree with the H(C.sub.x) at the leaves, which will be checked by S, will verify the root-hash and will abort if there is any mismatch. Else, S will sign the root-hashes by simulating S.sub.sig. In the ideal world, S will get random strings signed by calling F.sub.sig.
(145) 3) Case 2: If I is corrupted, but C is not, A does I's leaf encryptions, creates C.sub.x's, etc., and gives to S. S generates the corresponding root-hashes for the Merkle trees, and sends the root-hashes to A for signing. A is expected to sign the root-hashes. If A refuses to sign the root-hashes, S will abort.
(146) Now, S preferably simulates the creation and verification of the SR (see algorithm 4, and algorithm 5). For this, S will retrieve the SO, I, etc., and construct a tuple SR=(SO∥I∥VK.sub.RI∥C) and forward it to a subset of E. If L is corrupted, A will construct the SR tuple. If A's SR tuple is malformed, S preferably aborts. In the ideal world, S calls F.sub.create, who generates the SR. At this point S.Math.E needs to validate SR. Per the adversary model, A can corrupt a minority of members in S. Here there are two cases to consider:
(147) 1) Case 0: None of S are corrupted: S verifies SR (if SR was generated by A in the previous step), and checks it against the SO S had created. S simulates S.sub.sig and creates the signature σ.sub.SR.sup.S, and gives it to A. In the ideal world, S calls F.sub.sig and creates the signature.
(148) 2) Case 1: A (minority) subset of S are corrupted by A. For the minority, A will check the SR. If A rejects the SR, or refuses to produce a signature σ.sub.SR.sup.S, for any reason, S preferably aborts, and sends a malformed request to F.sub.create, which will abort the simulation in the ideal world. Communication among members of corrupted minority of S is controlled by A and need not be simulated. If A behaves properly, i.e., validates the SR and produces signature σ.sub.SR.sup.S, S will simulate the honest majority, and the ideal world similar to Case 0.
(149) S preferably simulates C, producing an SRR, and a subset of E, verifying the SRR. S first retrieves the SO it created. Here again, there are two broad cases:
(150) 1) Case 0: If C is uncorrupted, S retrieves the C.sub.x∈C.sub.bn; x∈[1 . . . bSize], adds the C.sub.x's, sibling hashes, etc. to the SRR tuple, the ZKP tuple it created before, calls S.sub.sig, signs the SRR tuple, and gives the H(SRR), along with the signed SRR to A. A then passes it on to S.Math.E, who will accept or reject it. If all members of S are honest, S will validate the signed SRR, thus concluding. In the ideal world, S will call F.sub.create, F.sub.zk.sup.SAMPL, and F.sub.sig to create and sign the SRR, respectively.
(151) 2) Case 1: If C is corrupted, A will create the SRR; the SO is given to A. Firstly, A can return a verification fail on the SO created by S. If this happens, S will abort the simulation.
(152) If A chooses to proceed with the simulation, A will create the Merkle hash trees with the H C.sub.x at the leaves, sibling hashes, etc. A will give the ZKPs, πAI, πPI.sub.j and signatures on the ZKPs, σ.sub.AI, σ.sub.PI.sub.
(153) If a minority of S.Math.E are corrupted, A can return a fail on the ZKP verification, upon which S aborts. If A rejects the SRR, or refuses to produce a signature σ.sub.SRR.sup.S, S preferably aborts. In the ideal world, S will corrupt C such that C does not respond to F.sub.create 's request for an SRR, upon which F.sub.create will write C's identity to the blockchain by calling F.sub.BC, and will then abort. If A validates the SRR and produces signature σ.sub.SRR.sup.S, S will simulate the honest majority. In the ideal world S will call F.sub.sig. Lastly, S will give K.sub.CI to A, if A had not already corrupted C and/or I, and obtained K.sub.CI earlier. This concludes the proof.
(154) Embodiments of the present invention can also be applied to other general data sharing interactions, aside from those specifically discussed in this application. For example, embodiments of the present invention can be used in the interactions of companies that share and sell user data. Currently, without the present invention, there is no way they can validate to the stakeholders the information that they shared to another interested party. Embodiments of the present invention enable such validation. In one embodiment, the enforcer can include a data broker or an independent person or company.
(155) Embodiments of the present invention also allow identification of the parties who have access to the data and the parties to whom a request for deletion and/or modification of the data needs to go, for example under general data protection regulations and/or guidelines. Embodiments of the present invention enable a gatekeeper, conduit, and/or broker to all share interactions to remain anonymous but can provide a witness when needed.
(156) Industrial Applicability:
(157) The invention is further illustrated by the following non-limiting examples.
Example 1
(158) The performance of SAMPL was evaluated for scalability, and to bench mark the operations performed by different entities within SAMPL with varying system parameters and surveillance requirements.
(159) Experimental Setup: Four desktop class machines with INTEL®Core™ i7-6700K CPUs and 8 GB RAM each were used to run an implementation of SAMPL according to an embodiment of the present invention. Each of the machines ran a single entity in SAMPL: J, E, L, and C, communicating over C Sockets. The entities were coded using the C programming language and compiled with gcc version 7.3.0 (Ubuntu 7.3.0-27 ubuntu1 18.04). Random user data, for 500 users, was pre-generated and stored in an SQL database (email was used as the representative application) at C. User data was created for 120 days.
(160) In this experiment, RI for a given user was tied to their real name and each user had an AI tied to their name in the database, where the AI was a key pair that was tied to the user's PI.sub.i; i∈[1 . . . m] using ZKPs. The simulation was performed with only a single PI.sub.i for each user's data, during the surveillance period. The cryptographic operations of signing and verifying user data, and ZKP related operations were prototyped using the Charm Cryptographic framework. AES-256 in GCM mode was used for the symmetric key encryption involving K.sub.CI, K.sub.JLC, and K.sub.EJLC. For emulating the blockchain in SAMPL, Ethereum was used. Each entity ran its own Ethereum node and communicated with the local blockchain network.
(161) Metrics and Parameters: Separate simulations were run for 5, 10, 15, and 30 users in the SO posted by J. The surveillance periods simulated were 5, 10, 20, and 50 days. These aforementioned values (number of users, days) were chosen to demonstrate scalability in the event of concurrency. SAMPL was evaluated using the following metrics:
(162) 1) ZKP generation and verification time per user: The Prime192v1 Elliptic Curve was used as the prime order group G for ZKP as described in Protocol 11.
(163) 2) Merkle root generation and signing per user: Simulations were run for batch-sizes with 16, 32, 64, 128, and 256, leaves in the tree with message sizes set to 1 KB, 75 KB, 1 MB, and 2 MB.
(164) 3) Enforcer Verification Time: Measured for 5, 10, 15, and 30 users, batch sizes of 32 and 64 messages, and surveillance period of 5, 10, 20, and 50 days. The message size was set to 75 KB.
(165) Verification of SR by E as depicted in
(166) Results: Table 2 reflects the ZKP verification and generation times per user averaged over 100 runs. The generation time was calculated for the setup in Protocol 1 (only establishment of P1: ref. Protocol 11) The average ZKP generation time was 1.02 ms with a standard deviation of 0.236 ms. This time is expended when an I signs up for a new account with C or whenever I establishes a new PI with C. The verification time is calculated for an E verifying the user data inside SRR (calculated once per SRR). The verification time was found to be 1.066 ms with a standard deviation of 0.096 ms.
(167)
(168) Comparison of
(169)
(170) To give a fine-grained analysis of components of SRR verification at E, a breakdown of the computation time is given in Table 3. For each step, it does follow that the amount of time taken is linear, as the number of users and/or surveillance period is increased, hence showing the scalability that is offered by embodiments of the present invention.
(171) TABLE-US-00019 TABLE 2 Operation Mean Standard Deviation ZKP Generation 1.02 ms 0.236 ms ZKP Verification 1.066 ms 0.096 ms
(172) Note that the total time for operations performed on a given SRR depicted in Table 3 are lower than the computation time illustrated in
(173) The preceding example can be repeated with similar success by substituting the generically or specifically described operating conditions of embodiments of the present invention for those used in the preceding examples.
(174) Optionally, embodiments of the present invention can include a general or specific purpose computer or distributed system programmed with computer software implementing steps described above, which computer software may be in any appropriate computer language, including but not limited to C++, FORTRAN, BASIC, Java, Python, Linux, assembly language, microcode, distributed programming languages, etc. The apparatus may also include a plurality of such computers/distributed systems (e.g., connected over the Internet and/or one or more intranets) in a variety of hardware implementations. For example, data processing can be performed by an appropriately programmed microprocessor, computing cloud, Application Specific Integrated Circuit (ASIC), Field Programmable Gate Array (FPGA), or the like, in conjunction with appropriate memory, network, and bus elements. One or more processors and/or microcontrollers can operate via instructions of the computer code and the software is preferably stored on one or more tangible non-transitive memory-storage devices.
(175) Note that in the specification and claims, “about” or “approximately” means within twenty percent (20%) of the numerical amount cited. All computer software disclosed herein may be embodied on any non-transitory computer-readable medium (including combinations of mediums), including without limitation CD-ROMs, DVD-ROMs, hard drives (local or network storage device), USB keys, other removable drives, ROM, and firmware.
(176) Embodiments of the present invention can include every combination of features that are disclosed herein independently from each other. Although the invention has been described in detail with particular reference to the disclosed embodiments, other embodiments can achieve the same results. Variations and modifications of the present invention will be obvious to those skilled in the art and it is intended to cover in the appended claims all such modifications and equivalents. The entire disclosures of all references, applications, patents, and publications cited above are hereby incorporated by reference. Unless specifically stated as being “essential” above, none of the various components or the interrelationship thereof are essential to the operation of the invention. Rather, desirable results can be achieved by substituting various components and/or reconfiguring their relationships with one another.