Yao's - Homework

We don't expect formal proofs; rather, just a high-level argument from intuition. Please submit your answers as a PDF to Gradescope.

Crypto Notions

  1. What does each of zk, S, N, and ARG mean in zk-SNARG? What does K mean in zk-SNARK? Give a potential application of zk-SNARG/ZKSNARK in practice. (Try to come up with one that was not covered in class!)
  2. In one sentence, what is secure two-party/multi-party computation? Give a potential application of secure 2PC/MPC in practice. (Try to come up with one that was not covered in class!)

Commitment Schemes

Consider a commitment scheme \((\mathsf{Commit}, \mathsf{Open})\) for a finite message space \(\mathcal{M}\) (for instance, \(\mathcal{M}=\{0,1\}\)). Recall the hiding and binding properties:

Hiding: The hiding property states that for any \(m_0, m_1 \in \mathcal{M}\), \(m_0 \neq m_1\), \(\mathsf{Commit}(m_0)\) is indistinguishable from \(\mathsf{Commit}(m_1)\). More specifically, perfect hiding states that \(\mathsf{Commit}(m_0)\) and \(\mathsf{Commit}(m_1)\) have the same distribution and are indistinguishable to any receiver. Computational hiding states that \(\mathsf{Commit}(m_0)\) is computationally indistinguishable from \(\mathsf{Commit}(m_1)\) to a PPT receiver.

Binding: The binding property states that it is hard for the sender to find \(m_0, m_1 \in \mathcal{M}\), \(m_0 \neq m_1\) and randomness \(r, s\) such that \(\mathsf{Commit}(m_0;r)=\mathsf{Commit}(m_1;s)\). More specifically, perfect binding states that for any \(m_0, m_1 \in \mathcal{M}\), \(m_0 \neq m_1\) and any randomness \(r, s\), \(\mathsf{Commit}(m_0;r)\neq \mathsf{Commit}(m_1;s)\). Computational binding states that it is computationally hard for a PPT sender to find \(m_0, m_1 \in \mathcal{M}\), \(m_0 \neq m_1\) and randomness \(r, s\) such that \(\mathsf{Commit}(m_0;r)=\mathsf{Commit}(m_1;s)\).

  1. Why can't a commitment scheme be both perfectly hiding and perfectly binding?
  2. Recall the Pedersen commitment scheme on a cyclic group \(\mathbb{G}\) of prime order \(q\) with generator \(g\). Let the receiver first sample a random group element \(h\in \mathbb{G}\). The message space is \(\mathcal{M} = \mathbb{Z}_q\). To commit to a message \(m \in \mathbb{Z}_q\), the sender randomly samples \(r \gets \mathbb{Z}_q\) and computes \(\mathsf{Commit}(m;r) = g^m \cdot h^r\). Why is this scheme perfectly hiding and computationally binding (under what computational assumption)?
  3. Recall the Merkle tree construction on a message space \(\mathcal{M} = \{0,1\}^{2^d}\). For any message \(m\in\{0,1\}^{2^d}\), we builds up a binary tree of depth \(d\) where the leaf nodes are the \(2^d\) bits of \(m\) and each non-leaf node is computed as \(H(\mathsf{lc} \| \mathsf{rc})\) where \(\mathsf{lc}\) and \(\mathsf{rc}\) are its left and right children. Finally, we use the root of the tree as the commitment. Why is this construction computationally binding (under what computational assumption)?
  4. Why is the above Merkle tree construction not hiding? How can we make it hiding?

Oblivious Transfer

Our OT protocol only supports 1-out-of-2 OT, which is sufficient for garbled circuits. However, 1-out-of-\(n\) OT (for \(n>2\)) may also be useful in certain applications. In 1-out-of-\(n\) OT, the sender has \(n\) messages \(m_0, m_1, \dots, m_{n-1} \in \{0,1\}^{\ell}\) and the receiver has an input \(c \in \{0,1,\dots, n\}\). From the OT protocol, we would like the receiver to learn only \(m_c\) and the sender to learn nothing.

  1. Extend the Diffie-Hellman-based OT protocol to a semi-honest 1-out-of-\(n\) OT for an arbitrary \(n\). You don't have to prove security for the protocol. Hint: 1-out-of-2 OT should be a special case of the extended protocol.
  2. Given a semi-honest 1-out-of-2 OT protocol (as a black box), construct a semi-honest 1-out-of-\(n\) OT for an arbitrary \(n\). You don't have to prove security for the protocol.

Malicious Garbler

As is, our 2PC protocol doesn't protect against malicious adversaries. For instance, the garbler doesn't have to garble the circuit that the two parties agreed on.

  1. Consider the private dating example where the two parties want to jointly compute a single AND gate on their private inputs. Describe an attack that allows the garbler to learn the evaluator's input bit (assuming the garbler is malicious and the evaluator is honest).
  2. Suppose we wish to boost security of this protocol by enforcing the garbler to generate each garbled gate honestly; for instance, an AND gate is actually an AND gate, and not an OR gate. This way, the evaluator can be sure that the function they're evaluating is the one they agreed on. What cryptographic primitive might be useful in this situation? A single-phrase response suffices.

(Bonus) KZG Commitments

In this problem, we will work towards constructing the KZG polynomial commitment scheme, or the Kate commitment scheme, one of the most popular and foundational polynomial commitment schemes in the world. This commitment scheme is used in practical zk-SNARGs/SNARKs because it allows constant time verification and constant sized proofs for polynomial evaluation. The drawbacks are that it relies on bilinear pairings and requires a trusted setup, which may be hard to achieve in real life without relying on MPC.

We start by partially presenting the scheme's setup. Consider a cyclic group \(\mathbb{G}\) of prime order \(Q\) with generator \(g\). A trusted party is going to run trusted setup by computing a random secret group element \(s \in \mathbb{G}\), then \(g^{s^i}\), for \(i = 0, 1, \ldots, n\). Critically, the trusted party will completely delete \(s\) - without doing this, the protocol is not secure. Finally, the trusted party will share the \(g^{s^i}\) as public parameters.

  1. How could we use MPC to conduct the trusted setup phase, so that no party knows the secret \(s\)? Assume we have two non-colluding semi-honest parties.

Next, we wish to commit to a polynomial \(p(x)\) of degree at most \(n\). The commitment to the polynomial \(p(x)\) is computed as \(g^{p(s)}\). Since we don't know \(s\), we'll have to use the public parameters to compute it.

  1. How can we compute the commitment \(g^{p(s)}\) using the public parameters?

  2. As an aside, it may be very useful to be able to homomorphically add commitments together. Show how we can homomorphically add up two commitments of \(p(x)\) and \(q(x)\) to retrieve a commitment of \(p(x) + q(x)\).

Now that we've committed to a polynomial, we want to be able to generate proofs that \(p(z) = y\) for some \(z\) and \(y\), without revealing \(p(x)\). Notice that proving this statement is equivalent to proving that there exists some polynomial \(q(x)\) such that \(p(x) - y = q(x)\cdot (x - z)\).

  1. Why are the above two statements equivalent?

Naturally, our proof that \(p(z) = y\) will be the commitment to the remainder polynomial \(q(x)\). To verify, we want to use the commitments to check that \(p(s) - y = q(s) \cdot (s-z)\), namely that the relationship above holds when evaluated at \(s\). We only have these elements in the exponents (namely, we have access to \(g^{p(s)}, g^{q(s)}, g^s\) and can easily compute \(g^y, g^z\)), and so we will verify them in the exponents. While we can compute \(g^{p(s) - y}\) quite easily, we can't compute \(g^{q(s) \cdot (s-z)}\). What should we do?

Thankfully, when we selected \(\mathbb{G}\), we chose \(\mathbb{G}\) to have special properties. In particular, for this group there exists an operation \(e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T\) where \(\mathbb{G}_T\) is another group of order \(Q\) with a generator \(g_T\). For any \(a, b \in \mathbb{Z}_q\), it holds that \(e(g^a, g^b) = g_T^{ab}\).

Such an operation is called a bilinear pairing and such a group \(\mathbb{G}\) is called a pairing-friendly group. (So far, pairings only work in elliptic curve groups, so we have that \(\mathbb{G}\) is an elliptic curve.)

  1. Given a pairing-friendly group \(\mathbb{G}\) with a bilinear pairing \(e\), how can we verify the above relationship?

We should inspect some of the security properties of this scheme. To do so, we'll introduce a neat fact about polynomials. Consider a polynomial \(p(x)\) of degree \(n\). We know from high school that \(p(x)\) has at most \(n\) roots; that is, \(p(x) = 0\) in at most \(n\) places. Moreover, we know that if another degree-\(n\) polynomial \(q(x)\) is equal to \(p(x)\), then \(p(x) - q(x)\) should be equal to 0 everywhere since their difference is the zero polynomial. However, if the polynomials are not equal, then the resulting polynomial is of degree at most \(n\), and thus has at most \(n\) roots. Given that \(n\) is much smaller than the field size \(Q\) the polynomials are defined in. Therefore, at a random point \(s\), it is extremely unlikely that \(p(s) - q(s) = 0\).

  1. Why is it hard for the prover to find another degree-\(n\) polynomial \(q(x)\) with the same commitment as \(p(x)\) while \(q(x) \neq p(x)\)?

Recall the trusted setup; we now explore why knowledge of \(s\) breaks security of this scheme.

  1. How could a malicious prover construct a degree-\(n\) polynomial \(q(x)\) with the same commitment as \(p(x)\) while \(q(x) \neq p(x)\), knowing \(s\)?

  2. How could a malicious prover fake a proof, knowing \(s\)? Extrapolate why without knowing \(s\) it is hard to create a fake proof.

The rabbit-hole goes deeper: Kate proofs can actually be combined to prove multiple evaluations of a polynomial all at once, or they can be used as a vector commitment like a Merkle tree. Other forms of commitments require no trusted setup, or are post-quantum secure, or both. We hope this interlude into commitments has been exciting!