kyber v1

[ineiti]

This is the epic for v1 of our new kyber!

[bford]

What exactly is an "epic"? I can tell it's software engineering terminology of some kind but for some reason I'm unfamiliar with it. :)

[nikkolasg]

We use the Zenhub additional project management layer on top of Github. It has this notion of "Epic" issues, which is composed of a lot of sub issues and they can be tracked down etc etc.

[bford]

OK, and more useful: just from browsing the kyber v1 godoc (http://godoc.org/gopkg.in/dedis/kyber.v1) ...

• There are some XXX comments in the doc that we need to resolve one way or another (either fix now or defer to a future version)...

• We need to do a solid proofreading and cleanup pass on all the godoc documentation in any case

• Cipher is still in there; didn't we decide to leave that out of v1 at least? Does anything in v1 or onet still depend on it?

• BinaryEncoding is still there; we need to decide what to do with it. I'm currently inclined to move it to a separate package analogous to protobuf, maybe call it 'fixbuf' since it's a binary encoding intended specifically for fixed-length encodings. What all in kyber v1 still depends on this?

• Constructor is still there; didn't we decide to eliminate it or replace it with some other approach?

• I'm thinking that the Hiding interface hack perhaps should just be merged into the Point interface, since (a) it's increasingly generally useful and applicable to many types of curves, and (b) not all methods in the Point interface actually work with all possible curves anyway either.

• Also, if it's true - as has been suggested at least - that using an Elligator-type injective map is generally a faster/better way to pick random hash-points than the "sample and retry" method the library currently uses, then perhaps the Pick() and HideDecode() methods are redundant and should be merged somehow?

• The Group.PrimeOrder() method still needs to be either eliminated or renamed to something less confusing. (It sounds like it's asking whether the group is prime-order, but what it returns is actually whether the order of the Base() point is prime-order.) What all still depends on this? More generally, we need to systematize the API for obtaining basic properties of the group in question - e.g., its order, whether there's a cofactor, etc. Perhaps with several methods, perhaps with just one method that returns a GroupProperties struct of some kind, not sure.

• Can someone summarize or point me to the background discussion that led to Group.NewKey() getting added? This method seems out-of-place: keys are a higher-level concept related to public-key encryption or signing or other schemes; a Group is just a group that's useful to support discrete-log crypto schemes, but is not a scheme itself. Why should Group know about keys of any kind at all?

These are just the TODO items that came to me upon a quick browse of the top-level kyber package; I'm sure there are many other issues like this lurking in the sub-packages as well. We need to get issues like these at least a bit more under control before we even think of "releasing" v1.

[nikkolasg]

There are some XXX comments in the doc that we need to resolve one way or another (either fix now or defer to a future version)...

I've looked at most XXX in the code and solved the ones that I knew of. Many are in the cipher/ package which I never touched yet. I'm gonna look for those in the doc definitly.

Cipher is still in there; didn't we decide to leave that out of v1 at least? Does anything in v1 or onet still depend on it?

Yes we did, but in the end, @ineiti used it recently, and it's needed by the sign/anon package at least.

BinaryEncoding is still there; we need to decide what to do with it. I'm currently inclined to move it to a separate package analogous to protobuf, maybe call it 'fixbuf' since it's a binary encoding intended specifically for fixed-length encodings. What all in kyber v1 still depends on this?

Binary encoding is still needed by sign/anon and proof packages. Either we take an additional time to refactor those packages to extract the "encoding" functionality, or we move that to a future release.

Constructor is still there; didn't we decide to eliminate it or replace it with some other approach?

Constructor is needed by BinaryEncoding.

I'm thinking that the Hiding interface hack perhaps should just be merged into the Point interface, since (a) it's increasingly generally useful and applicable to many types of curves, and (b) not all methods in the Point interface actually work with all possible curves anyway either.

Your b) point is very accurate and reflects my general feeling that, on the contrary, we should perhaps aims to "reduce" the Point interface instead of extending it further. It takes time and efforts to implement a new point implementation and it feels wrong to "partially" fulfill an interface's definition by writing panic("not implemented") because there's no way to implement it, resulting in an incomplete implementation interface for potentially many curves. I like the design of the Hiding interface but except for Ed25519 and Ed448 with their Elligator mappings, I don't know any other curves that are providing this behavior, so I would prefer keep this interface separate. Would you provide us some pointers to such curves ?
On a higher level, I feel that we are putting too much on the Scalar and Point, at the point they become kind of a "throw away" interface for all features that we need (same story for the NewKey method). I would instead prefer to start thinking about a general, clear and modularized way to provides these features to a Scalar or a Point. Perhaps having the Group listing all available features for both types and one can then type to the right interface or stg. This needs some further thoughts obviously.

The Group.PrimeOrder() method still needs to be either eliminated or renamed to something less confusing. (It sounds like it's asking whether the group is prime-order, but what it returns is actually whether the order of the Base() point is prime-order.) What all still depends on this? More generally, we need to systematize the API for obtaining basic properties of the group in question - e.g., its order, whether there's a cofactor, etc. Perhaps with several methods, perhaps with just one method that returns a GroupProperties struct of some kind, not sure.

As mentionned just above, I'm also in favor of having a clearer way to get properties out of the group in question. We should maybe check how some other libraries are handling this but I have a slight tendency for your second approach, the GroupProperties approach. It does not overload the interface definition and allow easy extensibility & default values for quick implementation.

Can someone summarize or point me to the background discussion that led to Group.NewKey() getting added?

That was at the time when I was coding CoSi, and also with the early javascript libraries, we needed/wanted to be compatible with eddsa. Therefore, we needed to have a non-modulo'd scalar to do the bit-shifting for avoiding small sub-group attacks. Therefore, we also added the scalar.SetBytes method to "directly" embed bytes into a scalar, regardless of the value (if it's out of range or not).
Do you have any suggestions for this last point ?

I agree that key concepts could perhaps be managed at a higher level but at the time there was not enough "low level" methods to control the scalars at the bit level. Maybe one solution could simply to add that method as a edwards25519 top level package method ?

Thanks a lot for your thoughtful comments !

[nikkolasg]

Just some problems I encounter using the "nosuite interface" approach, so it's written down for testimony ;) :

• Be able to retrieve a "suite" from its name, give a code like this:

var suites = map[string]interface{}{}

func init() {
	ed25519 := edwards25519.NewAES128SHA256Ed25519(false)
	suites[ed25519.String()] = ed25519
}

In my opinion, this kind of code should be ommitted if possible, because here we rely on the knowledge of the programmer of the API of the specific package to know that it has a String method. This kind of code is usually done by going through interface, as simple as the Stringer interface.

• Lot of code in onet needs a "suite", mostly to be able to interface with the network package, so they expect network.Suite. With the current approach, all Services receive a interface{} and therefore must do a cast to use the onet methods, resulting in code like this:

 func newDKGService(c *Context, suite interface{}) (onet.Service, error) {
	s := &DkgService{
		ServiceProcessor: onet.NewServiceProcessor(c, suite.(network.Suite)),
	}
}

While it's not intself a big deal, it's again, one more tedious and repetitive piece of code that needs to be present everywhere, for again, what I consider a relatively low gain...

[nikkolasg]

Issues solved:

• Most XXX are deleted. Those who are kept are either too important to "fix as is" or I don't get them (usually in Cipher sub-packages)
• The fixed length encoding has been moved to external repo: https://github.com/dedis/fixbuf

Issues needing attention (consensus):

• PrimeOrder method: First, I would advise for a GroupProperty struct but given that we only have a few numbers of parameters to put (order of the group and cofactor ?), it's also OK for me to add those functions to the Group interface directly. What do you think ?
  Secondly, regarding the amgiguity you mentionned, I'm not sure about the best approach. Maybe a PrimeCurveOrder and PrimeGroupOrder ? In case of ed25519, the former returns false and the latter true.
• Hiding interface: I would advise against merging that with the Point interface because 1) it's already overloaded in my opinion and 2) not all curves supports this hiding interface right ? I only know of Elligator mappings.... Seems it's one of the properties we can ask for a Group, like "can you create hiding points?". It's the same story for bilinear mappings, "can you create a bilinear mapping?".
  Not going to the full GroupProperty approach, what about:

if group.SupportHiding() {
  hidden = myPoint.(Hiding)
  ...
}

• NewKey method: EDIT I recall now that NewKey was previously in Suite and so I naturally shifted it into Group since Suite does not exist anymore (sigh).
  if we really want it out of the Group interface, we thought with @ineiti of different solutions:
  • move the bit twiddling thing in the NewKeyPair method, where a manual switch to check if the Suite is ed25519 and in that case, apply the bit twiddling which would be implemented in the key package (where the KeyPair is defined).
  • move out the functionality of creating a "key" into a kyber.KeyFactory functionality. That way, NewKeyPair can check if the group given implements KeyFactory, if yes, then call group.NewKey otherwise simply create a regular Scalar. The actual bit twiddling would stay in the ed25519 package.
• Cipher: Apparently, you want the cipher package to be out of v1 ? That means we must get rid of the sign/anon package as well in v1 too. That is ok for me. BUT our pop service needs the sign/anon, and IIRC we wanted pop to be included in cothority.v2. In short, the problem is that we want to have a stable pop service which depends on the unstable sign/anon. We could try some casting magic between github.com/dedis/kyber and gopkg.in/dedis/kyber.v1 but I strongly advise against that as it's "one more trick" that only us, engineers, will understand. In my opinion, I see two solutions:
  • We keep cipher and sign/anon in v1, so we can keep the pop service in cothority.v2
  • We plan to not include the pop service in cothority.v2.

I'm more in favor of the former option...

[ineiti]

Opened separate issues for discussion, else we'll loose track of what's going on here.