Open questions BeleniosRF paper

[webmaster128]

When implementing BeleniosRF, the following questions arose

• [x] 1. Is there a typo in the definition of H (vk should be x)?
• [ ] 2. Can we prove that m_i is a bit (i.e. 0 or 1) by proving g^(m_i*(1-m_i)) == 0 (0 is the point at infinity)
• [ ] 3. What are the commitments on the scalars m_i in G1 needed for?
• [ ] 4. What is C_T (commitment on T = X1^r) needed for?
• [ ] 5. In order to verify pi_T, the value T = X1^r must be sent along with c1, c2, c3, right?
• [x] 6. What kind of curve is preferred? Supported options by amcl are "FP256BN" | "FP512BN" | "BN254" | "BN254CX" or "BLS383" | "BLS381" | "BLS461".
• [ ] 7. Is it okay that the commitments to m_i are not randomized?
• [ ] 8. Is it okay that the proofs that m_i is a bit are not randomized?
• [x] 9. Is there a ' missing in (Figure 2: Our SRC scheme; Random+)? C_2 can only commit elements, not scalars.

[pyrros]

• [ ] 1. Yes.

• [ ] 2,3. Doing multiplication on the exponents when we don't want to disclose them is hard. The usual way around it in this setting is to have the pairing do the multiplication for us (i.e. we prove something about e(g_1^{m_i},g_2^{1-m_i}) instead of g_1^{m_i*(1-m_i)}, which in turn implies we need to have m_i available in both groups.

• [ ] 4. It's there to make the security reduction in Theorem 1 work (See 3.3 esp. Remark 1). To provide a very brief insight, we need X_1^r to complete the proof. Note that even under an extractable GS CRS, we can't actually get back r from C'_2(r), but a G_2 element raised to r, so we can't build T that way. The workaround is to have it available in a commitment + demand a proof it's consistent with the rest of the ciphertext.

• [ ] 5. No, we don't need T to check the proof, it's enough to check it against C'_2(r).

• [ ] 7,8. Since they go to the message board, we want them to be rerandomized (see Fig.2).

• [ ] 9. Yes, Should be C'_2(r').

[webmaster128]

Thanks a lot for the feedback, @pyrros. I will be busy implementing the feedback/changes for some time and get back to you when something is unclear.

[dagacha]

• [ ] 6. The curve BN254 is a good choice as it gives you a reasonable trade-off between security and efficiency.

[webmaster128]

Regarding 2: I am looking at the possible proofs for pairing product equations in the GS paper (Page 4, Figure 1; orange means private, green means public):

When I want to prove e(g_1^{m_i}, g_2^{1-m_i}) = 1 and hide m_i/1-m_i, I need to set X_1 = g_1^{m_i} and Y_1 = g_2^{1-m_i}, right? In this case, don't I need commitments to X_1 and Y_1? This formular does not seem to support secret scalars. How do commitments to m_i help?

[webmaster128]

Regarding 5: I'm not sure if I understand this correctly, but right now I set

pi_T := proof that ( X_1^\overline{r} == \overline{w} )
      = proof that ( X_1^\overline{r} == value committed in C_T )
      = proof that ( X_1^\overline{r} == T )
      = proof that ( linear equation in G_1 with constant A = [X_1], secret y = [\overline{r}] and public righ-hand side T holds )

and in order to verify a multi-scalar equation in G_1, I need X_1, C'_2(r) and the public righthand-side T. This is the same approarch I do for pi_r and pi_V. Is the approach correct at all or am I running in the wrong direction?

[webmaster128]

Happy new year everyone! I'd really love to complete this BeleniosRF implementation. However, I'm stuck at the question how to prove that m_i is 0 or 1. I don't see how the commits to the scalar m_i in G1 and G2 helps me doing that. See also https://github.com/webmaster128/private-voting/issues/1#issuecomment-517712002

Could you help out with a little more guidance for that question @pyrros @dagacha?

[pyrros]

The idea is that m_i is a bit if and only if m_i *(m_i-1) is 0. This is something we can check for, once we have it committed to in both groups (the subtraction of 1 is easy to do).