[v1] Explore new Suite structure with interfaces of PBC

[nikkolasg]

In respect to @bford 's comment in this PR, we should try to define the interfaces of a possible PBC / BLS package using the new way of defining Suite to see if it makes sense / trying things out !

[nikkolasg]

Starting this work from the 1b1db52ccdcdb640574692a4049aa349bfa00362 commit in branch v1

[nikkolasg]

Working implementation in a171ce33991766e6f5c9b7dc09ce1621bb62e63d

[nikkolasg]

I made a first cut implementation of BLS signatures to try out if PBC was dwelling well into the new Suite decoupling approach. Here is the BLS implementation and the relevant PBC group.go file.

Short story: I am biased and I'm now more than ever not in favor of the suite decoupling approach...

Long story: BLS needs to hash a message onto a point in G1, that means it needs kyber.HashFactory (the old Hash() hash.Hash), and the kyber.CipherFactory (the old Cipher(key...)). So it gives something like this (I've factored out a bit in the latest version):

// bls.go
type Suite interface {
  G1() kyber.Group
  G2() kyber.Group
  GT() kyber.Group
  kyber.HashFactory
  kyber.CipherFactory
}

while what would be really ideal is:

type Suite interface {
  G1() kyber.Suite
  G2() kyber.Group
  GT() kyber.Group
}

Since only G1 needs to provide those methods. In the current approach I have to implement CipherFactory and HashFactory for the Pairing structure (code), which is just complete repetition of code again and again (it's not the first time I mention repetition of code explaining the caveats of this approach... ;) . Of course I could do something like

type G1Suite interface {
  kyber.Group
  kyber.HashFactory
  kyber.GroupFactory
}
type Suite interface {
  G1() G1Suite
  G2() kyber.Group
  GT() PairingPoint 
}

But personnaly I find it even more confusing, naming wise (a suite having a sub suite ? or a group inside a group ?) and implementation wise (why should I need to declare again a new interface, while before I needed to declare basically nothing !). It just increase the cognitive load for no benefits here.

So here it is. I would really like having your comments / objections / feedback on this, @bford @Daeinar @ineiti . Thank you.

[ineiti]

Can you add the PairingPoint-definition?

How is kyber.Suite defined?

Is it possible to have other Ciphers and Hashes?

[bford]

I second Linus's request to see what PairingPoint looks like.

I'm not sure that it makes sense to add separate G1, G2, and GT "constructor" methods to the Suite level, since the things they create all work together closely. For example, the G1, G2, and GT groups are all tied to the same types of scalars. I think it might make more sense for a Suite that needs pairing-based crypto just to contain one constructor that creates a "Pairing" object, which is analogous to Group but provides constructors for G1/G2/GT Points along with Scalars appropriate to that pairing. For example, the BLS package's Suite might be:

  type Suite {
    Pairing() kyber.Pairing
    kyber.HashFactory (perhaps this should really be called HashSuite?)
    kyber.CipherFactory (perhaps should be called CipherSuite?)
  }

...and in the kyber package:

  type Pairing {
    Scalar() Scalar
    PointG1() Point
    PointG2() Point
    PointGT() PairingPoint
    (Len methods etc...)
  }

  type PairingPoint {
    Point
    Pair(g1, g2 Point) -- perform pairing operation from g1,g2 into this target gt point
  }

Incidentally and somewhat orthogonally, I think it might make sense to clean up the Group interface a bit as well. At the very least, the PrimeOrder() method was always a bad hack used for only certain special-case needs, was confusingly named, and needs to be fixed with something better.

I'm also not sure where and under what need/rationale the NewKey() method appeared in Group?

[bford]

On further thought, it probably does make sense to have Group-compatible objects representing the individual G1, G2, GT groups, if for no other reason than so that they can be passed to the generic Group test infrastructure. However, in normal "workhorse" pairing-based crypto code I suspect that we'll be spending almost all our time just instantiating points in the relevant groups.

Thus, in the proposed Pairing interface above it might be worth having GroupG1, GroupG2, and GroupGT methods in addition to (not instead of) the direct PointG1, PointG2, PointGT constructors suggested above.

Also, perhaps the PairingPoint interface might be better named PointGT, since it's a Point interface extended with additional functionality that applies only to the GT group in a Pairing (since a GT point is always the destination of a pairing operation).

[ineiti]

I also don't understand why you do define the g1group and the other two as having a Pairing-struct, but as far as I see you only use the curve of that Pairing-struct. But as I cannot compile it due to missing libraries, I cannot play around with it.

For the 'constant' methods (Hash, Cipher, NewKey, PrimeOrder, Scalar, ScalarLen), is it not possible to define those once and then embed that structure? This would cut down the number of methods defined and would avoid the code-duplication you fear so much.

Probably the best bet would be to 'free your mind' and re-write those parts. It really seems overly complicated to me. I can also have a go at it, but for the moment I cannot get the tests to pass, so I won't know if I break it or make it better ;)

[nikkolasg]

The definitions are in the linked files and now here:

// Group interface extension to create pairing-capable points.
type PairingGroup interface {
    kyber.Group // Standard Group operations

    PairingPoint() PairingPoint // Create new pairing-capable Point
}

// Point interface extension for a point in a pairing target group (GT),
// which supports the Pairing operation.
type PairingPoint interface {
    kyber.Point // Standard Point operations

    // Compute the pairing of two points p1 and p2,
    // which must be in the associated groups G1 and G2 respectively.
    Pairing(p1, p2 kyber.Point) kyber.Point
}

// PairingSuite represents the basic functionalities needed to use pairing based
// cryptography.
type PairingSuite interface {
    G1() kyber.Group
    G2() kyber.Group
    GT() PairingGroup
}

[nikkolasg]

I also don't understand why you do define the g1group and the other two as having a Pairing-struct, but as far as I see you only use the curve of that Pairing-struct.

True, it's an aterfact from the first cut that can be removed. I changed that in the last commit.

For the 'constant' methods (Hash, Cipher, NewKey, PrimeOrder, Scalar, ScalarLen), is it not possible to define those once and then embed that structure?

Right thanks for the proposition. I've done that in the last commit too. It's ugly in terms of the Single Responsibility Principle but it's nevertheless quite efficient in this case ;)

Probably the best bet would be to 'free your mind' and re-write those parts. It really seems overly complicated to me.

I picked up on @bford 's older pbc wrapper implementation. This design actually makes sense, as all three groups are clearly separated (because of the underlying library) and there needs to be one "pairing" having a reference to all three groups. If you have any better ideas, they're welcome.

[jeffallen]

Pairing based crypto is now in Kyber.