Group properties involving Fr.Inverse

[jakubdabek]

I tried implementing an algorithm based on the following property: g^x == g^(x*1) == g^(x * (s * inv(s))) == (g^s)^(x * inv(s)), but I can't get it (or the simpler one: g == (g^s)^inv(s)) to work with code:

G := bls.NewG1()
g := G.One()
x, _ := bls.NewFr().Rand(rand.Reader)
X := G.New()
G.MulScalar(X, g, x)

s, _ := bls.NewFr().Rand(rand.Reader)
si, six, sixRed := bls.NewFr(), bls.NewFr(), bls.NewFr()
si.Inverse(s)
six.Mul(x, si)
sixRed.RedMul(x, si)

x2 := bls.NewFr()
x2.Mul(s, six)
fmt.Println(x.Equal(x2)) // false

x2Red := bls.NewFr()
x2Red.RedMul(s, sixRed)
fmt.Println(x.Equal(x2Red)) // true

g2 := G.New()
G.MulScalar(g2, g, s)
G.MulScalar(g2, g2, si)
fmt.Println(G.Equal(g, g2)) // false

X2 := G.New()
G.MulScalar(X2, g, s)
G.MulScalar(X2, X2, six)
fmt.Println(G.Equal(X, X2)) // false

X2Red := G.New()
G.MulScalar(X2Red, g, s)
G.MulScalar(X2Red, X2Red, sixRed)
fmt.Println(G.Equal(X, X2Red)) // false

I've seen that the test for Inverse uses Fr.RedMul, but I have no idea when to use it instead of Mul (some documentation would be great). Neither of them work with this example.

There is definitely some missing understanding of the library where reading source can only get me so far; what can be done to make this work?

[kilic]

@jakubdabek, I agree that Inverse function was confusing. It was performing Montgomery inversion. I have just introduced RedInverse function now that covers what Inverse function does before. And we also still have Inverse function too that implements the plain inversion.

Let me also leave a note about reduced functions. Reduced functions is for Montgomery form. We use Fr type for both Montgomery form and representation form. Developer should maintain which multiplication function has to be used depending of the form that is being used.

// R = 2**256 % q

// operations
a * b * R == RedMul(a * R, b * R)
a * a * R == RedSquare(a * R)
(a ^ -1) * R == RedInverse(a * R)

// conversion
a == FromMont(a * R)
a * R == ToMont(a)

[jakubdabek]

@kilic The group properties work now with the non-reduced version, thanks for the fix! So the group functions work only with non-reduced form Fr? I didn't see something like G1.RedMulScalar. The ones existing currently could have at least a mention that they work only with that form. Also I believe it would be easier to work with different forms if Fr.fromMont and Fr.toMont were public (and less confusing if they were different types).

[kilic]

Reduced multiplications are approx 2x faster than non reduced ones. Actually if you look at implementation non reduced operations are performed with reduced functions.

We present reduced multiplications because there are protocols that heavily uses scalar field arithmetic. However group multiplication is mostly rely on bit pattern of the scalar, so using a scalar in Montgomery space wouldn't bring us any benefit.

Also I believe it would be easier to work with different forms if Fr.fromMont and Fr.toMont were public (and less confusing if they were different types).

Agreed. They also might be named as ToRed and FromRed.

[kilic]

Agreed. They also might be named as ToRed and FromRed.

Added.