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 as a non-square in the field and 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.
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 as described above. 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 look up 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:
In these expressions, and are field elements. are unsigned -bit integers. At each , the algorithm first computes , then and (from the previous step’s and ), then finally and , in each case such that they satisfy the above expressions. Note that in the algorithm .
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. In the following expressions for , is always even, and so the high bit of each value is unchanged when adding .
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.
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.
In the non-square case, will be odd, and will be odd. We will have computed and multiply by a correction to get our desired output.
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 .