/nix/nix-daemon/

ogo' rowspan='2'>cgit logo index : pq-blind-sigs-impl
A toy post-quantum blind signatures implementation
aboutsummaryrefslogtreecommitdiff

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/