path: root/README.md

# 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 to build it

First, make sure make and GCC, as well as the libraries FLINT and Libgcrypt are
installed.  You can get the dependencies with the help of GNU Guix, using
`dev-shell` script that you can find in the project's root.

Then, make use of the included `Makefile`.

```
make
```

## How to run it

This implementation includes a simple program that generates a keypair, signs
something in memory (while printing some diagnostic messages), verifies the
signature and discards everything.  It can be invoked like this.

```
$ ./run_blind_sig_example
Preparing blind signature context ("Current III" set from Rückert's paper).
n = 1024
d_s = 283
m = 9
phi = 4
psi = 1
d_alpha = 1024
d_epsilon_star = 1023
d_y = 10928598810624
d_g_star = 10928302353408
d_beta = 402860937956032512
d_g = 402850009653679104
q = 1208925819614629174706189
Making a test signature for ASCII buffer: "This is a message to blind-sign.".
User retries with new alpha.
User retries with new alpha.
User retries with new alpha.
User successfully obtained signature.
Signer acknowledged success in signing.
Signature verified successfully.
Done, cleaning up.
$ make run_blind_sig_example
guix shell qemu -- qemu-x86_64 -cpu max blind_sig_example
Preparing blind signature context ("Current III" set from Rückert's paper).
n = 1024
d_s = 283
m = 9
phi = 4
psi = 1
d_alpha = 1024
d_epsilon_star = 1023
d_y = 10928598810624
d_g_star = 10928302353408
d_beta = 402860937956032512
d_g = 402850009653679104
q = 1208925819614629174706189
Making a test signature for ASCII buffer: "This is a message to blind-sign.".
User couldn't get a signature in step 4, restart is being requested from signer.
Restart triggered by signer from step 5.
User retries with new alpha.
Restart triggered by signer from step 3.
Restart triggered by signer from step 3.
User successfully obtained signature.
Signer acknowledged success in signing.
Signature verified successfully.
Done, cleaning up.
```

The individual steps can also be performed one-by-one, with intermediary data
used by the protocol written to files named `*.example` (because implementing a
networked protocol would be an overkill for a sample implementation like this).
You can choose your own 1-line message to blind-sign in this case.

```
$ STEPS="key_gen $(seq 1 5 | awk '{print "signing_p" $0}') verification"
$ go() { [ 0 = $# ] || (./blind_sig_example "$1" && shift && go "$@"); }
$ while ! (echo 'Hello World' | go $STEPS); do echo 'Restart from step 1.'; done
Write a line-one message to blind-sign.
> 
Restart triggered by signer from step 3.
Restart from step 1.
Write a line-one message to blind-sign.
>
User couldn't get a signature in step 4, restart is being requested from signer.
Restart from step 1.
Write a line-one message to blind-sign.
> 
User retries with new alpha.
User couldn't get a signature in step 4, restart is being requested from signer.
Restart from step 1.
Write a line-one message to blind-sign.
> 
User couldn't get a signature in step 4, restart is being requested from signer.
Restart from step 1.
Write a line-one message to blind-sign.
> 
User retries with new alpha.
User retries with new alpha.
User retries with new alpha.
User retries with new alpha.
User retries with new alpha.
User retries with new alpha.
User retries with new alpha.
User retries with new alpha.
User retries with new alpha.
User retries with new alpha.
User successfully obtained signature in step 4.
Signer acknowledged success in signing.
Got valid signature for message.
Hello World
```

You can also use the `*.example` files to experiment.  E.g., try to substitute
the signed message and see that verification now fails.

```
$ echo Funny | dd bs=1 seek=8 count=5 conv=notrunc of=sig.example 2>/dev/null             
$ dd bs=1 skip=8 count=12 if=sig.example 2>/dev/null
Funny World
$ ./blind_sig_example verification
Got invalid signature.
```

It's easy to see how much space (more or less) the signature and intermediate
protocol messages take.

```
$ ls -lh *.example
-rw-r--r-- 1 user user  15K Jan 25 18:23 p1_result.example
-rw-r--r-- 1 user user 5.8K Jan 25 18:23 p2_result.example
-rw-r--r-- 1 user user  90K Jan 25 18:23 p3_result.example
-rw-r--r-- 1 user user    1 Jan 25 18:23 p4_result.example
-rw-r--r-- 1 user user 199K Jan 25 18:23 p5_result.example
-rw-r--r-- 1 user user  46K Jan 25 18:23 priv_key.example
-rw-r--r-- 1 user user  14K Jan 25 18:23 pub_key.example
-rw-r--r-- 1 user user 112K Jan 25 18:23 sig.example
-rw-r--r-- 1 user user 199K Jan 25 18:23 signer_state.example
-rw-r--r-- 1 user user 123K Jan 25 18:23 user_state.example
```

The parameters (the "Current III" set from Rückert's paper in this case) are
implicit and not encoded in the signature nor in other files.  You can see that
the signature is nevertheless significantly bigger (~112 kB) than what Rückert
gives for this parameter set (66.9 kB).  Most of it likely comes from the
encoding of coefficients where only ~81 bits are really needed for each one.
Here, FLINT's (actually, GMP's) serialization is used to encode them.  It adds 4
bytes of length information to each coefficient and doesn't do any bit-packing.

There is also a program (remnant of initial development) that serves as an
example of polynomial operations 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.

- [1] https://eprint.iacr.org/2008/322
- [2] https://flintlib.org/