| 1 |
/* |
| 2 |
This file is for implementing the Gao-Mateer FFT, see |
| 3 |
http://www.math.clemson.edu/~sgao/papers/GM10.pdf |
| 4 |
|
| 5 |
For the implementation strategy, see |
| 6 |
https://eprint.iacr.org/2017/793.pdf |
| 7 |
*/ |
| 8 |
// 20240805 djb: more use of cryptoint |
| 9 |
// 20221230 djb: split these arrays into separate .c files |
| 10 |
// 20221230 djb: rename powers array as fft_powers |
| 11 |
// 20221230 djb: rename consts array as fft_consts |
| 12 |
// 20221230 djb: rename s array as fft_scalars |
| 13 |
// 20221230 djb: add linker lines |
| 14 |
|
| 15 |
// linker define fft |
| 16 |
// linker use vec_mul |
| 17 |
// linker use fft_scalars fft_consts fft_powers |
| 18 |
|
| 19 |
#include "fft.h" |
| 20 |
#include "fft_scalars.h" |
| 21 |
#include "fft_consts.h" |
| 22 |
#include "fft_powers.h" |
| 23 |
#include "vec.h" |
| 24 |
#include "crypto_int64.h" |
| 25 |
|
| 26 |
/* input: in, polynomial in bitsliced form */ |
| 27 |
/* output: in, result of applying the radix conversions on in */ |
| 28 |
static void radix_conversions(uint64_t *in) |
| 29 |
{ |
| 30 |
int i, j, k; |
| 31 |
|
| 32 |
const uint64_t mask[5][2] = |
| 33 |
{ |
| 34 |
{0x8888888888888888, 0x4444444444444444}, |
| 35 |
{0xC0C0C0C0C0C0C0C0, 0x3030303030303030}, |
| 36 |
{0xF000F000F000F000, 0x0F000F000F000F00}, |
| 37 |
{0xFF000000FF000000, 0x00FF000000FF0000}, |
| 38 |
{0xFFFF000000000000, 0x0000FFFF00000000} |
| 39 |
}; |
| 40 |
|
| 41 |
// |
| 42 |
|
| 43 |
for (j = 0; j <= 4; j++) |
| 44 |
{ |
| 45 |
for (i = 0; i < GFBITS; i++) |
| 46 |
for (k = 4; k >= j; k--) |
| 47 |
{ |
| 48 |
in[i] ^= (in[i] & mask[k][0]) >> (1 << k); |
| 49 |
in[i] ^= (in[i] & mask[k][1]) >> (1 << k); |
| 50 |
} |
| 51 |
|
| 52 |
vec_mul(in, in, fft_scalars[j]); // scaling |
| 53 |
} |
| 54 |
} |
| 55 |
|
| 56 |
/* input: in, result of applying the radix conversions to the input polynomial */ |
| 57 |
/* output: out, evaluation results (by applying the FFT butterflies) */ |
| 58 |
static void butterflies(uint64_t out[][ GFBITS ], uint64_t *in) |
| 59 |
{ |
| 60 |
int i, j, k, s, b; |
| 61 |
|
| 62 |
uint64_t tmp[ GFBITS ]; |
| 63 |
uint64_t consts_ptr = 0; |
| 64 |
|
| 65 |
const unsigned char reversal[64] = |
| 66 |
{ |
| 67 |
0, 32, 16, 48, 8, 40, 24, 56, |
| 68 |
4, 36, 20, 52, 12, 44, 28, 60, |
| 69 |
2, 34, 18, 50, 10, 42, 26, 58, |
| 70 |
6, 38, 22, 54, 14, 46, 30, 62, |
| 71 |
1, 33, 17, 49, 9, 41, 25, 57, |
| 72 |
5, 37, 21, 53, 13, 45, 29, 61, |
| 73 |
3, 35, 19, 51, 11, 43, 27, 59, |
| 74 |
7, 39, 23, 55, 15, 47, 31, 63 |
| 75 |
}; |
| 76 |
|
| 77 |
// boradcast |
| 78 |
|
| 79 |
for (j = 0; j < 64; j++) |
| 80 |
for (i = 0; i < GFBITS; i++) |
| 81 |
{ |
| 82 |
out[j][i] = crypto_int64_bitmod_mask(in[i], reversal[j]); |
| 83 |
} |
| 84 |
|
| 85 |
// butterflies |
| 86 |
|
| 87 |
for (i = 0; i <= 5; i++) |
| 88 |
{ |
| 89 |
s = 1 << i; |
| 90 |
|
| 91 |
for (j = 0; j < 64; j += 2*s) |
| 92 |
{ |
| 93 |
for (k = j; k < j+s; k++) |
| 94 |
{ |
| 95 |
vec_mul(tmp, out[k+s], fft_consts[ consts_ptr + (k-j) ]); |
| 96 |
|
| 97 |
for (b = 0; b < GFBITS; b++) out[k][b] ^= tmp[b]; |
| 98 |
for (b = 0; b < GFBITS; b++) out[k+s][b] ^= out[k][b]; |
| 99 |
} |
| 100 |
} |
| 101 |
|
| 102 |
consts_ptr += (1 << i); |
| 103 |
} |
| 104 |
|
| 105 |
// |
| 106 |
|
| 107 |
// adding the part contributed by x^64 |
| 108 |
|
| 109 |
for (i = 0; i < 64; i++) |
| 110 |
for (b = 0; b < GFBITS; b++) |
| 111 |
out[i][b] ^= fft_powers[i][b]; |
| 112 |
|
| 113 |
} |
| 114 |
|
| 115 |
void fft(vec out[][ GFBITS ], vec *in) |
| 116 |
{ |
| 117 |
radix_conversions(in); |
| 118 |
butterflies(out, in); |
| 119 |
} |
| 120 |
|