blob: e109b0292c53e586c2d7f8c7fe90d85e8937d5a2 (
about) (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
# Post-quantum blind signatures implementation (in progress)
This is a small university project with the goal of implementing Markus
Rückert's lattice-based blind signature scheme from 2008[1].
Please consider it a toy program — it's being developed with shortcuts
(e.g. using a big scientific library (FLINT[2]) for efficient polynomial
multiplication). Also, there are possibly better BS algorithms by now.
## How it works
Well, the actual program is not there yet. There's just some code to facilitate
polynomial multiplication in a ring modulo X^m+1 over a modulo field with
non-canonical range — [-(n-1)/2, (n-1)/2] rather than [0, n-1].
```
$ make run_poly_mul
guix shell qemu -- qemu-x86_64 -cpu max poly_mul
Prime used for modulo operations: 127
55 + 31 mod [-63,63] = -41
Give first polynomial for the experiment:
12 3 4 5
Read polynomial: 5*x^3+4*x^2+3*x+12
Give second polynomial for the experiment:
11 1 2 3
Read polynomial: 3*x^3+2*x^2+x+11
Normal product of polynomials:
15*x^6+22*x^5+22*x^4+101*x^3+71*x^2+45*x+132
Normal sum of polynomials:
8*x^3+6*x^2+4*x+23
Give the degree m of X^m+1 polynomial to be used as divisor in the ring:
7
Product of polynomials in the ring:
15*x^6+22*x^5+22*x^4-26*x^3-56*x^2+45*x+5
Sum of polynomials in the ring:
8*x^3+6*x^2+4*x+23
```
Interestingly, only modulo operations in the latter range seem to be directly
supported in FLINT as of today.
## Building
You can install the dependencies with GNU Guix using `dev-shell` script that you
can find in project's root. For the rest, please consult the included Makefile
:)
- [1] https://eprint.iacr.org/2008/322
- [2] https://flintlib.org/
|
