{"post":{"data":{"id":"27133","type":"post","attributes":{"title":"Appendix A and B","authors":null,"publisher":null,"id":27133,"created_at":"2021-02-25T00:07:57.527Z","updated_at":"2021-02-25T00:08:05.250Z","plugins":"{}","slug":"ozgozz-appendix-a-and-b","form_url":"/posts/ozgozz-appendix-a-and-b","body":"

A Security Arguments

This appendix formalizes and proves the soundness and metadata-hiding security properties described in Section 2. Soundness. We formalize soundness as follows.

Definition 1 (Soundness). We define the following soundness game SOUND[𝜆] played between an adversary A and a chal- lenger C who simulates the behavior of servers 𝐴 and 𝐵. Both A and C are given 𝜆 as input.

Setup. Challenger C creates an initially empty list 𝐼 of com- promised mailbox indices. Adversary A requests creation of a number of mailboxes 𝑁 of its choosing. There are two ways in which it may create a mailbox:
1. Adversary A performs the role of a user interacting with the servers to create a new mailbox. Challenger C adds this mailbox to 𝐼.
2. Adversary A instructs C to create a mailbox where C plays the role of both the user and the servers, saving the user’s state (and in particular, the mailbox keys) at the end of the registration process.
Queries and Corruptions. Adversary A sends requests to the servers, controlled by C. At any time, it may send C a mailbox index 𝑖, at which point C will send the saved state of the user who registered mailbox 𝑖 and add 𝑖 to list 𝐼.
Output. Challenger C performs a read on each registered mailbox. If |𝐼| < 𝑁 and any mailbox outside of the list 𝐼 contains nonzero contents, the adversary wins the game.

We say a messaging scheme is sound if no PPT adversary can win the soundness game above with greater than negligible probability in the security parameter 𝜆.

Claim. The Express scheme is sound.

Proof. The soundness proof follows closely from the sound- ness of our auditing protocol. For each write request sent to the Express servers, we consider two cases: where the write modifies one mailbox and where the write modifies more than one mailbox. If a write modifies more than one mailbox, then it will not be applied to the database of mailboxes, except with negligible probability in 𝜆, by the soundness property of the auditing protocol. This means that we must only consider writes that modify a single mailbox. The adversary does not know the virtual addresses of mailboxes outside of 𝐼, but it only wins the soundness game if it produces a DPF that writes to the address of a mailbox outside of 𝐼. This can only occur with probability 2−𝜆 (for 𝜆 = 128 in our instantiation of the protocol), which is also negligible. Thus an adversary can only win the soundness game with probability negligible in 𝜆.

Metadata-hiding. We can formalize the definition of metadata- hiding by requiring that there exists an efficient simulator algo- rithm Sim that, given the list l of honest clients who connect with the servers, produces an output which is computation- ally indistinguishable from the view of an adversary A who controls any number of users and one server while processing requests from the remaining honest users, subject to the re- striction that the recipients of the messages from honest users are never among those controlled by A. More specifically, l should include which client connects, time of connection, and size of message transmitted for each connection made to the compromised server. Given this information, the client can simulate the content of the messages sent by the honest client.

This definition satisfies our intuitive notion of metadata- hiding because it means that for each message, the server learns nothing about who the message is sent to, as everything it learns could be simulated before it even sees the request. This information would be contained in the content of the honest client’s messages, which are not given to the simulator. We sketch a proof of the metadata-hiding security argument below. The proof relies on the zero-knowledge property of the auditing protocol, the privacy of the DPFs used, and the security of the encryption used for access control.

Claim (Informal). There exists an algorithm Sim that, given the list l of honest client connections to the Express servers, simulates the view of an adversary A who controls one Express server and any number of clients, subject to the restriction that the recipients of the honest clients’ messages are never among those controlled by A.

Proof(sketch). Sim simulates write requests from honest users and the process of auditing them by invoking the simulator implied by the zero-knowledge property of the auditing protocol. Note that this in turn uses the simulator implied by the definition of DPF privacy to generate DPF shares. Moreover, whenever malicious users request to read the contents of mailboxes, the simulated honest server(s) returns encryptions of zero.

The proof that this simulator gives the adversary A a view indistinguishable from interaction with a real honest server and honest users is fairly straightforward. First, since the adversary knows the virtual addresses of honest users’ mailboxes, as well as one of the two keys needed to read the contents of those mailboxes (if it has compromised one of the servers), it can send read requests for the contents of honest mailboxes. However, since the adversary does not see the second key to any honest users’ mailboxes, we invoke the semantic security of the encryption scheme used to protect honest mailbox contents to show that the messages returned from read requests to an honest server are indistinguishable from encryptions of zero.

From here, just as in the case of soundness, the proof follows from the security of the auditing scheme. From the zero- knowledge property of the auditing scheme, we know that the view of either server in the auditing protocol can be simulated. But the view of each server in Express’s auditing protocol is the same as the view of that server in the overall protocol, since the server’s view only consists of its shares of the proof input (in the compressed form of a DPF share from which it derives the actual inputs) and the proof messages themselves.

B SNIPs and Analysis of Auditing Protocol

This appendix sketches the instantiation of the proofs used in our auditing protocol as well as the analysis of the auditing protocol. Full details and a security proof for this proof system can be found in the Prio paper [23]. We include the instantiation of the proof here for completeness, including some improvements described in the follow-up work of Boneh et al. [11].

The size of a SNIP proof is linear in the number of multipli- cation gates in the arithmetic circuit representing the statement to be proved. In our case, there are 2 multiplications. The client numbers the gates as 1 and 2. The idea of the proof is to create three polynomials 𝑓 , 𝑔, and h such that 𝑓 , 𝑔 represent the left and right inputs of each gate and h to the outputs of each gate. 𝑓 is the polynomial defined by the points (0,𝑟𝑓 ),(1,𝑐),(2,𝑚), and 𝑔isthepolynomialdefinedbythepoints(0,𝑟𝑔),(1,𝑐),(2,𝐶), where 𝑟 𝑓 and 𝑟𝑔 are random values chosen by the client. Ob- serve that the servers already hold shares of each point used to define 𝑓 and 𝑔 except the random values 𝑟 𝑓 and 𝑟𝑔, shares of which must be included in the SNIP proof.

Next, h is defined as the polynomial representing the expected outputs of each multiplication gate, or the product 𝑓 · 𝑔. Since eachof 𝑓 and𝑔willbeofdegree2,hwillbeofdegree4.The client can compute h from 𝑓 and 𝑔 and must send shares of the description of h to each server as part of the proof.

Since the servers now have shares of the inputs and outputs of each multiplication from 𝑓 , 𝑔, and h, they only need to check that 𝑓 · 𝑔 = h to be convinced that this relationship holds among their inputs. They do this by evaluating each polynomial at a random point 𝑡 and checking equality. To compute the product

𝑓 (𝑡) · 𝑔(𝑡), the servers simply evaluate their shares of each function and publish the result. This reveals nothing about 𝑓 or 𝑔 except their value at the point 𝑡.

The Prio paper [23] and the improvements of Boneh et al. [11] give full proofs of completeness, soundness, and zero- knowledge for this protocol. As a minor optimization, instead of sending one proof as described above, we send two separate SNIPs, one for each of the two multiplications. This results in a slightly larger proof size but simplifies the polynomial multiplications because the polynomials 𝑓 , 𝑔 become linear and h becomes quadratic. The security properties of the protocol are unchanged by this modification.

Analysis. Having described the relevant building blocks, we now sketch the analysis of our full auditing protocol. The security properties of our auditing scheme follow directly from those of the two protocols we combine to build it (which we do not re-prove here). Completeness follows directly from the completeness of the verifiable DPF protocol of Boyle et al. as well as the completeness of SNIPs.

Likewise, soundness follows directly from the soundness of these two building blocks, with soundness error equal to the sum of the soundness error of the DPF verification protocol and the SNIP. We prove the following claim.

Claim. If the servers begin the auditing protocol holding vectors𝑤 ∈F𝑛 and𝑤 ∈F𝑛 suchthat𝑤=𝑤 +𝑤 ∈F𝑛 is

a vector of Hamming-weight greater than one, then the audit will reject, except with error probability 𝜖 = 𝑂(1/|F|).

By taking F to be a field of size 2𝜆, for security parameter 𝜆, we can make the error probability 𝜖 negligibly small in 𝜆.

The claim is true because the auditing protocol will only accept a false proof if (1) the difference 𝑐2 − 𝑚𝐶 = 0 for a 𝑤 that has more than one non-zero entry, or (2) the soundness of the SNIP fails to enforce that only inputs satisfying this relationship will be accepted. But the probability of (1) is negligible in |F| by the security of the DPF verification protocol of Boyle et al. [15], and the probability of (2) is negligible in |F| by the soundness of SNIPs [11, 23]. By a union bound, the soundness error of the overall protocol is at most the sum of the soundness errors of the verifiable DPF protocol and the SNIPs.

To prove the zero-knowledge property, we must show that there exists a simulator algorithm Sim that can produce outputs whose distribution is computationally indistinguishable from the view of the servers in an execution of the Express auditing protocol where the sum 𝑤 𝐴 + 𝑤 𝐵 corresponds to a vector with a single non-zero entry. This algorithm will interact with a potentially malicious adversary A who plays the role of the server whose view is being simulated. This proves the security of the protocol because it shows that an adversary can learn anything it would learn from actually participating in the protocol by running Sim on its own.

The construction of Sim and subsequent proof of security follow almost directly from the original proof of security for SNIPs used in Prio [23]. To see why, observe that the view of each server in the auditing protocol consists of the server’s DPF share, the server’s share of the proof, and any messages sent between the servers during the proof. The only difference between this and the standard SNIP simulator is that the server’s inputs are compressed in the form of DPF shares instead of being stated explicitly as the vector 𝑤 𝐴 or 𝑤 𝐵 . In essence, the DPF can be thought of as an efficient way to encode the server’s inputs to the proof. To bridge this difference between our protocol and the original SNIP, we make one small change to the SNIP simulator. The original SNIP simulator samples the server’s input share at random. Our modified SNIP simulator will sample the server’s input shares using simulated DPF shares instead. Since the proof of zero-knowledge is otherwise identical, we defer to the prio paper for the full proof [23].

","cable_url":"wss://jellypbc.com/cable","upload_url":null,"tags":[],"title_comments":[],"body_comments":[],"contributors":"Cindy Wu","body_citations":[]},"relationships":{"uploads":{"data":[]},"citations":{"data":[]},"backlinks":{"data":[{"id":"26312","type":"backlink"},{"id":"26342","type":"backlink"}]},"figures":{"data":[]}}},"included":[{"id":"26312","type":"backlink","attributes":{"id":26312,"imprint_type":"","imprint_date":"","publisher":"","target":null,"post_id":27067,"generated_post_id":27133,"source_post_path":"/posts/dubvbh-express-lowering-the-cost-of-metadata-hiding-communication-with-cryptographic-privacy","title":"Express: Lowering the Cost of Metadata-hiding Communication with Cryptographic Privacy","authors":"Saba Eskandarian, Henry Corrigan-Gibbs, Matei Zaharia, Don Boneh"}},{"id":"26342","type":"backlink","attributes":{"id":26342,"imprint_type":"","imprint_date":"","publisher":"","target":null,"post_id":27135,"generated_post_id":27133,"source_post_path":"/posts/ufftmn-express-lowering-the-cost-of-metadata-hiding-communication-with-cryptographic-privacy","title":" Express: Lowering the Cost of Metadata-hiding Communication with Cryptographic Privacy ","authors":"Saba Eskandarian, Henry Corrigan-Gibbs, Matei Zaharia, Dan Boneh"}}]},"currentUser":{"data":{"attributes":{"name":"Anonymous","avatar_url":"/assets/avatar-bf489bd933e198667b26b776cbd7d0fc921ee585791fc68cca86a6187a8781f6.png"}}},"isProcessing":false,"editable":false}

Appendix A and B

Backlinks