Clarification on incomplete Twisted Edwards curves

[kevaundray]

Problem

It is not clear whether incomplete Twisted Edwards curves are allowed in arkworks or how to notify someone that they are using an incomplete twisted Edwards curve and their possible security implications.

Relevance

Currently Bandersnatch is an incomplete twisted Edwards curve.

The claim can be tested with the following code:

    assert!(d.sqrt().is_none());
    assert!(a.sqrt().is_none());
 
    assert!((d / a).sqrt().is_some());

Possible Solution

• A long term solution would depend on whether arkworks allows incomplete Edwards curves into the ecosystem.
• A short term solution; document Bandersnatch as being incomplete

[yelhousni]

It is indeed incomplete but "practically" complete with a reasonable assumption. The points at infinity are all of even order while we work on a field of odd prime order. So there are no exceptions as long as we check that the points are of odd order (we do a subgroup check anyway). See section.2 here.

[kevaundray]

Yep checking the point is in the odd prime order subgroup r would avoid these exceptional points. This check can be quite expensive however, another technique is to use a legendre check and take a quotient group;

• 1-aX^2 is a square for the points (x,y) and (x,y) + (0,-1)
• This means you can reject the other two points in the 2 torsion subgroup which are exactly the exceptional points or points which have been added to them.
• You then identify (x,y) and (-x,-y) to be equivalent forming a group of order r, similar to the Decaf technique

[weikengchen]

I checked the paper Section 6, page 11, https://eprint.iacr.org/2008/013.pdf, it said "if a is a square in k and d is a nonsquare in k."

Should the second condition assert!(a.sqrt().is_none()); be changed to assert!(!a.sqrt().is_none());? @kevaundray

[kevaundray]

I checked the paper Section 6, page 11, https://eprint.iacr.org/2008/013.pdf, it said "if a is a square in k and d is a nonsquare in k."

Should the second condition assert!(a.sqrt().is_none()); be changed to assert!(!a.sqrt().is_none());? @kevaundray

A little further it clarifies that we want d/a to be non-square.

• If a is a square, then d should be non square to make d/a non-sqaure.
• If a is non-square and d is non-square, then d/a is a square.

[weikengchen]

@yelhousni @simonmasson @zhenfeizhang @asanso

Do you think it would be possible to sample another Bandersnatch with d/a being a quadratic residue?

[asanso]

@weikengchen it would be tough to be so lucky again :) So the answer is probably not

[weikengchen]

following up on the previous response from @yelhousni

So, as long as we work on a prime-order subgroup, the issue is gone?