Post-quantum Signature Bliss

Post-quantum Signature Bliss

Sometime soon, we need to deprecate RSA and ECC, as they will not be seen as robust in a post quantum computing world. One of the alteratives to these methods is the usage of lattice cryptography, and especially in the usage of Ring Learning With Errors (RLWE). An important application of this is within key exchange, and where Bob and Alice can exchange information, and then end-up with the same shared key. Here is a presentation which outlines this method:

Another application is within digital signatures, and where Bob will sign something with his private key, and then Alice can prove that he signed it with his public key. One post-quantum signature method is BLISS (short for Bimodal Lattice Signature Scheme). It was created by Léo Ducas, Alain Durmus, Tancrède Lepoint and Vadim Lyubashevsky in 2013 [here]:

While it produces a small signature and has good security, it was not entered into the NIST candidate list for standardization. It uses a Fiat-Shamir lattice signature scheme, and his an improved method for selecting samples for the parameters. It also uses Huffman coding to compress the signature.

The following is some sample code [here]:

package main

import (
	"fmt"
	"github.com/LoCCS/bliss"
	"os"
	"github.com/LoCCS/bliss/sampler"

)

func main() {

	m1:="Hello"

	argCount := len(os.Args[1:])

        if (argCount>0) {m1= string(os.Args[1])}

	seed := make([]uint8, sampler.SHA_512_DIGEST_LENGTH)
	for i := 0; i < len(seed); i++ {
			seed[i] = uint8(i % 8)
	}

	entropy, _ := sampler.NewEntropy(seed)

	key, _ := bliss.GeneratePrivateKey(0, entropy)

	pub := key.PublicKey()
	msg := []byte(m1)
	sig, _ := key.Sign(msg, entropy)

	fmt.Printf("Pub key: %s:\n", pub.String())
	fmt.Printf("Signature: %s:\n", sig.String())

	_, err := pub.Verify(msg, sig)

	if err == nil {
		fmt.Printf("Verify signature for version\n")
	}

	key.Destroy()

}

And a sample run [here]:

Message: Testing 1234:
Private key (first 800 chars): {s1:[0 -1 1 1 0 -1 0 1 -1 -2 -1 0 1 -1 -1 0 2 0 1 0 -1 -1 -1 0 1 1 -1 0 -1 1 1 -1 0 1 -2 1 -2 0 -1 0 1 -1 0 -1 2 -1 0 0 1 0 -1 0 1 -1 0 -1 -1 2 1 -1 1 0 -1 1 -1 0 0 0 0 -1 1 0 2 0 0 -1 -1 1 -1 1 1 2 2 0 2 0 -1 0 2 -1 -1 0 -1 1 1 0 -1 0 -1 0 0 1 1 0 0 -1 -1 1 0 0 -1 -1 -2 -2 0 0 -2 0 -1 -1 1 -1 0 -1 -1 -2 1 0 1 0 0 0 -1 1 0 -1 1 0 1 0 -1 0 -2 -1 1 0 1 0 0 -2 2 -1 1 -1 0 0 0 1 -1 1 0 1 1 -1 1 -1 0 -2 1 1 2 1 -1 0 1 2 -1 2 2 1 1 0 1 1 -1 -1 -1 -2 -2 1 0 -1 1 0 -1 2 1 0 1 2 2 1 0 -2 -2 -1 -1 0 -2 2 0 0 -1 -1 0 1 0 2 1 0 -1 1 1 0 2 1 2 1 -1 0 -1 1 -2 1 1 -1 -1 0 2 1 0 -1 -1 -1 0 1 -1 -1 -1 2 -1 1 -2 -1 0 1],s2:[-1 2 0 2 0 -2 2 0 -2 2 -2 -2 2 0 -2 2 2 2 2 -2 2 2 2 0 2 0 0 0 -2 -2 2 -2 -2 2 0 2 -2 0 -2 -2 0 -2 2 2 0 2 -2 -2 0 -2 0 -2 0 -2 0 2 -2 -2 -4 0 -2 -4 2 0 -4 0 0 0 0 0 -2 0 0 0 2 0 0 -2 2 :

Pub key (first 800 chars): {a:[6537 1872 371 2364 533 5969 2320 577 1516 4145 6325 2298 3333 7159 7000 6710 1580 6312 1248 3423 6413 7405 2776 6127 3215 5786 4689 3445 4715 1204 6822 5794 7081 253 4257 4356 3090 2803 6099 2512 1949 3495 3625 1634 5701 1929 976 1768 658 3857 6423 853 5310 1734 1139 3869 6646 7366 5934 4986 3790 7510 970 240 7154 6418 7667 1204 1304 5074 6735 3392 6774 4827 6554 1467 4442 4557 2247 2330 2503 655 4024 4403 5138 3194 171 4339 4003 1582 6180 2939 6967 2483 1825 7559 4118 1774 32 7193 1659 6441 5613 7440 4849 7499 3307 6445 5736 7540 6082 7156 2335 2332 6979 1851 4052 3757 3219 40 5378 2697 3428 6966 2910 4668 7305 4159 2296 6295 3510 7546 7336 332 2812 1621 2513 945 5055 1315 3504 765 4185 2107 4893 982 4434 3782 6263 6596 1990 4488 7255 4732 1556 3499 4869 1937 4719 6024 7665 5564 216 6:

Signature: {z1:[9 -187 146 101 31 49 74 37 -19 95 34 137 -37 -190 111 151 114 82 48 -41 85 -124 35 -72 102 -87 77 -24 81 22 3 42 16 -168 -13 -91 -10 116 8 -14 18 327 -155 -46 -124 -33 287 57 -16 -18 6 -35 -27 13 138 114 -99 46 -102 141 61 -44 -53 166 230 85 24 48 -172 1 -86 -5 130 26 32 108 -99 -195 -136 -11 66 -38 15 -2 -179 -90 0 -170 60 -24 -71 18 -14 -56 -155 83 -53 -97 -89 -50 -10 3 86 51 -220 -68 83 21 112 -126 15 5 178 -18 -82 39 8 20 -39 164 -21 171 75 25 84 11 -158 1 6 -94 -111 19 38 -39 -58 -81 -194 35 -64 34 -114 18 56 -57 105 13 44 162 82 -31 -69 -183 94 -52 73 9 43 89 34 -124 -12 168 -60 142 -69 171 62 -24 -14 -111 -96 -32 8 -28 20 3 161 35 73 15 75 -74 111 79 48 54 3 213 -129 -210 70 -80 -91 -95 20 -61 53 83 -70 -30 143 150 52 -247 -22 48 -82 149 81 88 -186 141 -96 -163 183 -72 81 -5 204 -89 -62 -15 -5 -92 -111 164 -46 -29 21 175 -106 25 230 144 52 -79 -130 -62 -11 -23 -17 17 -103 -28 -64 193 86 48 77 12 249 113 -98 -40 -59 -198],z2:[1 1 1 5 1 1 8 -4 -1 -4 2 -2 -4 -1 1 -2 -2 -4 -4 3 -2 -5 -2 -4 2 1 4 -1 -5 -1 2 3 -4 7 -3 2 1 -1 0 -4 -1 1 2 5 2 -2 0 1 0 4 -8 -2 4 -3 0 3 -2 -3 -3 3 -3 -4 7 -2 -3 0 -1 0 2 0 1 6 2 6 -3 2 2 -3 -5 3 3 1 -3 -1 -3 2 5 5 4 4 -1 0 3 -4 0 3 3 -2 1 -2 3 5 -2 2 1 0 0 2 5 -8 6 5 3 -2 -5 2 -3 -4 2 -1 0 2 4 -3 -3 -1 -2 -5 4 1 0 -1 0 -3 0 -2 1 1 4 -3 0 -7 4 7 4 4 0 3 -3 3 3 1 1 3 -4 0 4 1 3 -4 0 -1 5 1 0 -3 -2 4 2 -3 -5 1 5 -3 -1 1 -7 0 -4 -3 3 0 1 4 1 -2 -2 1 -3 4 2 -1 4 1 -2 0 3 2 0 -2 -1 2 -6 -1 2 -5 5 -2 3 -9 -3 -6 -7 0 -1 3 0 3 -2 0 -1 2 -6 4 -6 -4 -2 0 3 -2 6 1 -1 -1 0 7 -7 -1 2 6 -5 -4 5 -3 7 2 -7 3 -1 2 -1 4 8 -2 -3 -1],c:[94 39 237 207 106 50 30 186 133 169 116 223]}:
Verified signature!!

Conclusions

The good money is on lattice cryptography to win the NIST competition for signatures, so go learn some lattice cryptography.