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/