bug: Error multiplying a twistededwards point by scalar zero

[lucasmenendez]

Some of the hints used to perform an efficient ScalarMul operation over TwistedEdwards curve point does not check if the scalar used to the multiplication is zero, causing a division by zero.

Description

Here is a gist with a simple test and the current output: div_zero_test.go

The route of the error is the following:

1. gnark/std/algebra/native/twistededwards/curve.go

   Line 47 in 7887f6f

   func (c *curve) ScalarMul(p1 Point, scalar frontend.Variable) Point {

2. https://github.com/Consensys/gnark/blob/master/std/algebra/native/twistededwards/point.go#L130
3. https://github.com/Consensys/gnark/blob/master/std/algebra/native/twistededwards/point.go#L245

4. gnark/std/algebra/native/twistededwards/hints.go

   Line 69 in 7887f6f

   func halfGCD(mod *big.Int, inputs, outputs []*big.Int) error {

5. https://github.com/Consensys/gnark-crypto/blob/master/ecc/utils.go#L102

Expected Behavior

If the scalar used to the multiplication is zero, the result should be the Identity Point of the curve.

Possible Fix

Add something similar to this in

gnark/std/algebra/native/twistededwards/hints.go

Line 76 in 7887f6f

glvBasis := new(ecc.Lattice)

:

if inputs[0].Sign() == 0 {
    outputs[0].SetUint64(0) // s1
    outputs[1].SetUint64(0) // s2
    return nil
}

Steps to Reproduce

Check the gists with the test: div_zero_test.go

Context

We are trying to re-encrypt a frontend.Variable with elGamal, which involves to add a encrypted zero. The bug comes when we tried to encrypt a zero value.

Your Environment

• gnark version used (e.g. v0.8.1, HEAD@develop): HEAD@master
• gnark-crypto version used: v0.18.0
• go version (e.g. 1.20.6): v1.24.2

[ivokub]

cc @yelhousni

[yelhousni]

Indeed scalarMulFakeGLV is not defined for scalar input 0 (both for emulated and native packages). Although for the emulated case we state this in the comments but we fail to do so here.
https://github.com/consensys/gnark/tree/57a79c2edad54e746a4a12f41190cb05e5b1feec/std/algebra/emulated/sw_emulated/point.go#L1246

The best solution IMO is to document this here and export the more generic (less performant) scalarMulGeneric too. Given your gist, this works (within the twistededwards package):

var mPoint Point
mPoint.scalarMulGeneric(curve.API(), &G, c.Zero, curve.Params())

[lucasmenendez]

@yelhousni Why not just return the identity point of the curve? Is that incorrect?

[p4u]

I believe, the standard is that the point to infinity equals the identity point of the elliptic-curve group. So the scalar multiplication of a point by zero must return the identity point, as @lucasmenendez proposes.

I have searched some references, i.e. RFC 6090 states:

  An elliptic curve over a field Fp is defined by the curve equation

      y^2 = x^3 + a*x + b,

   where x, y, a, and b are elements of the field Fp [M1985], and the
   discriminant is nonzero (as described in Section 3.3.1).  A point on
   an elliptic curve is a pair (x,y) of values in Fp that satisfies the
   curve equation, or it is a special point (@,@) that represents the
   identity element (which is called the "point at infinity").  The
   order of an elliptic curve group is the number of distinct points.

[ivokub]

I think you have a point - previously for other curves we had to have two different cases where we could use incomplete or complete formulas, but twisted Edwards curve point addition and doubling formulas are always complete.

So scalar mul by zero (and other exceptional cases a la addition P+0, 0+P, 0+0, double(0)) should work as is. The only issue seems indeed to be the hint which doesn't work for the zero input. I'll see if it makes sense to fix it in gnark-crypto directly (to output 0,0 for 0 input) or in the hint here.

[ivokub]

See #1551 - hopefully we can merge it soon (CI + review)