Encoding/decoding to/from ristretto255

[isislovecruft]

While we have hash-to-group APIs, we do not have encode-to-group and decode-from-group APIs for ristretto255. Our hash-to-group API for ristretto255 makes use of the Elligator2 encoding, however, our ristretto255-elligator2 flavour is non-invertible, so reuse or incorporation of the hash-to-group API is impossible. And while there are not many cryptosystems in practice which use both the encode and decode functionality, there are a few notable exceptions like the obfs4 network traffic obfuscation protocol, used for Tor and several VPNs, and a recently introduced verifiable symmetric encryption scheme with applications to practical zero-knowledge proofs regarding plaintexts. The former safely uses the ed25519 group, while the latter does require a prime-order group like ristretto255.

@hdevalence mentioned that he made an example for encode-to-group here: https://github.com/hdevalence/ristretto255-data-encoding/blob/master/src/main.rs

• Is this something we would like to support directly in dalek?
• If so, is this something we'd like to add to the draft ristretto IETF standard in order to canonicalise it early on? (Thus hopefully avoiding the Elligator2 disaster where nearly all real-world usable implementations are slightly different..)
• Are there any other concerns or caveats which should be taken into account?

[ruescasd]

Just to say that I'm interested in the state of this, I have so far implemented it using @hdevalence's example (I had similar code before I came across his). My concern right now is whether this has implications for semantic security, briefly described here:

https://github.com/ruescasd/rmx-mg/issues/5

(This in the context of voting by the way, the project above is a verifiable re-encryption mixnet)

[isislovecruft]

If people other than me are doing this, I think we should consider just including @hdevalence's trivial encoding/decoding routine so that we don't end up with a bunch of incompatible adhoc implementations. People are obviously free to encode/decode differrently, but having a supported method seems nice for compatibility.

[eleanor-em]

Wanted to mention this: @hdevalence's implementation linked above is clearly not constant-time since how many trials are needed varies depending on the data. Is this likely to be relevant? Is it worth including anyway with a warning that it is not constant-time?

Thanks @isislovecruft for looking into this. The protocol I was working on during my Master's uses data encoding & decoding that's roughly the same as Henry's. (ETA: basically we needed to use a mix-net which requires the homomorphic property, but the encrypted data itself did not need to be homomorphically tallied.)

[ruescasd]

I'm using this so I prefer if it's included rather than having my own version of it (which I updated to @hdevalence's code). Fwiw, constant-time is not an issue for me @eleanor-em.