Re: [Belenios-discuss] Voter's side time efficiency [Was: Helios-C and the Majority Judgment]

[Pierrick Gaudry <pierrick.gaudry AT loria.fr>]

Hi Julien,

> # ECC vs. discrete log

First, some terminology. ECC is also based on discrete log. What we
compare here is ECC vs (multiplicative groups of) finite fields.

> I guess that using ECC would bring more time-efficiency on the voter's side.
> So I was wondering if you see drawbacks at using ECC instead of discrete 
> logarithms?
> Is it only an issue of trust in parameters of the elliptic curves
> or worktime to be spent on the implementation?

Lack of time to implement. Elliptic curves by themselves have no security
problem. But as in any crypto software, implementation of them can have
issues that lead to major problems.

> ## Apache Milagro Crypto Library (AMCL)
> 
> Apparently BeleniosRF+ has already explored that ECC path
> (though maybe not exactly the same, I don't know).

Indeed, in BeleniosRF, the need to have elliptic curve is not efficiency,
but to have the additional "pairing" feature. For this special elliptic
curves must be used.

> the source code of BeleniosRF+ does not seem to be publicly available
> (a password is needed to access its repository).

It was just a prototype. Nothing you could have used for a real product.

> So it looks like that aiming at a voter's side implementation
> in WebAssembly using AMCL and a specification using ECC
> would have a significative impact on time-efficiency on the voter's side.

This assumes that the browser is recent enough to support WebAssembly.
But then, in such a recent browser, I suspect that you don't have any
efficiency issue. Did you run some experiments in this direction to check
if you really have efficiency problems ?

> # ECC vs. mixnet
> 
> So, besides supporting Condorcet voting methods (which is not a feature I'm 
> pursuing),
> I understand that you're also implementing a mixnet out of a concern
> for time-efficency on the voter's side, right?

Well, not really. We'll see. Anyway, we wanted to support several voting
methods, and for that mixnets are needed.

> But is there another concern or a particular reason
> for which you're going the mixnet way rather than (of before) the ECC way?

We don't have any efficiency issue right now, so ECC is lower priority.

> And, does using a mixnet has significant drawbacks?

There are some theoretical drawbacks, and also the practical drawback
that the shufflings must be performed sequentially by the trustees.

> I mean, if an efficient support of the Majority Judgment
> can be achieved only by using ECC and AMCL for Web-only devices,
> would it still be important to implement a mixnet?

Indeed, if the current implementation is fast enough, or if you speed it
up using ECC and AMCL, then there is no need for mixnet in the case of
Majority Judgment.

Please ackonwledge that we won't give you support for adapting the
Belenios specicifaction to interfacing it with the AMCL API (or other) to
enjoy fast elliptic curve in webasm. This might be more difficult than
what you expect to make something clean and safe.

> Maybe the receipt-freeness?

No. There is no receipt-freeness in Belenios. And I don't recommend that
you go the BeleniosRF way. This is much more complicated and there is no
proper spec avaiblable that you could build upon.

> Finally, would you recommend a paper explaining
> Belenios's gen_shuffle_proof and check_shuffle_proof?
> Recently written in 
> https://gitlab.inria.fr/belenios/belenios/blob/explicit-homomorphism/src/lib/mixnet.ml
> Does Belenios implement the same Sako-Kilian mixnet that Helios uses?
> Is it compatible with he ECC way?

The Belenios mixnet follows the Chvote one. See
https://eprint.iacr.org/2017/325 and Section 5.5 for the description of
what is a mixnet, and Section 8 for pseudo-code that Belenios follows.