README.md


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

# 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 to multiply:
12 3 4 5
Read polynomial: 5*x^3+4*x^2+3*x+12
Give second polynomial to multiply:
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
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
```

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/