Inverse Square Roots

As in the internet-draft, the decaf377 functions are defined in terms of the following function, which computes the square root of a ratio of field elements, with the special behavior that if the input is nonsquare, it returns the square root of a related field element, to allow reuse of the computation in the hash-to-group setting.

Define sqrt_ratio_zeta(N,D) as:

  • (True, ) if and are nonzero, and is square;
  • (True, ) if is zero;
  • (False, ) if is zero and is non-zero;
  • (False, ) if and are nonzero, and is nonsquare.

Since is nonsquare, if is nonsquare, is square. Note that unlike the similar function in the ristretto255/decaf448 internet-draft, this function does not make any claims about the sign of its output.

Define isqrt(x) as a function that internally invokes sqrt_ratio_zeta and computes the inverse square root of a field element :

  • (True, ) if is zero;
  • (True, ) if is nonzero, and is square;
  • (False, ) if is nonzero, and is nonsquare.

To compute sqrt_ratio_zeta we use a table-based method adapted from Sarkar 2020 and zcash-pasta, which is described in the remainder of this section.

Constants

We set (the 2-adicity of the field) and odd such that . For the BLS12-377 scalar field, and .

We define where is a non-square root of unity. We fix as 2841681278031794617739547238867782961338435681360110683443920362658525667816.

We then define a and such that . We also define a parameter where . For decaf377 we choose:

Precomputation

Lookup tables are needed which can be precomputed as they depend only on the 2-adicity and the choice of above.

lookup table:

We compute for and , indexed on and :

This table lets us lookup powers of .

lookup table:

We compute for , indexed on :

We use this table in the procedure that follows to find (they are the values) in order to compute .

Procedure

In the following procedure, let . We use the following relations from Sarkar 2020:

  • Equation 1: and for and
  • Lemma 3: for
  • Equation 2:

Step 1: Compute

We compute . This corresponds to line 2 of the findSqRoot Algorithm 1 in Sarkar 2020.

Substituting :

Applying Fermat’s Little Theorem (i.e. ):

Substituting and rearranging:

We compute using a quantity we define as:

We also define:

And substitute and into which gives us:

We now can use in the computation for and :

Step 2: Compute

Compute using and as calculated in the prior step. This corresponds to line 4 of the findSqRoot Algorithm 1 in Sarkar 2020.

Step 3: Compute

We next compute for . This corresponds to line 5 of the findSqRoot Algorithm 1 in Sarkar 2020. This gives us the following components:

Step 4: Compute and

Next, we loop over . This corresponds to lines 6-9 of the findSqRoot Algorithm 1 in Sarkar 2020.

For

Using Lemma 3:

Substituting the definition of from equation 1:

Rearranging and substituting in (initial condition):

Substituting in equation 2:

This is almost in a form where we can look up in our s lookup table to get and thus . If we define we get:

Which we can use with our s lookup table to get . Expressing in terms of , we get .

For

First we compute using equation 1:

Next, similar to the first iteration, we use lemma 3 and substitute in and to yield:

In this expression we can compute the quantities on the left hand side, and the right hand side is in the form we expect for the s lookup table, yielding us . Note that here too we define such that the s lookup table can be used. Expressing in terms of , we get .

For

The remaining iterations proceed similarly, yielding the following expressions:

Note for and the remaining iterations we do not require a trick (i.e. where ) to get in a form where it can be used with the s lookup table. However, we can reduce the size of the g lookup table, by using the same trick for our expressions:

where

At the end of this step, we have found and for .

Step 5: Return result

Next, we can use equation 1 to compute using and from the previous step:

This matches the expression from Lemma 4 in Sarkar 2020. We can also express as:

to reduce the number of lookups in the g table. Recall and .

Next, to compute , we lookup entries in the g lookup table. To do so, we can decompose into:

then is computed as:

Multiplying in from step 1, we compute:

This corresponds to line 10 of the findSqRoot Algorithm 1 in Sarkar 2020.

We can use the result of this computation to determine whether or not the square exists, recalling from Step 1 that :

  • If is square, then , and
  • If is non-square, then and .