Public key and signature format modification

[simonmasson]

The initial python algorithm of verification is (in pseudo-code) :

def verify(self, pk_bytes, m, sig_bytes):
    # unpacking pk and sig
    ρ, t1 = unpack_pk(pk_bytes)
    c_tilde, z, h = unpack_sig(sig_bytes)

    # checks of size
    assert(h.sum_hint() > ω)
    assert(z.check_norm_bound(γ_1 - β))

    A_hat = expand_matrix_from(ρ)

    tr = H(pk_bytes, 32)
    μ = H(tr + m, 64)
    c = sample_in_ball(c_tilde, τ)

    c = c.ntt()
    z = z.ntt()

    t1 = 2^d * t1.ntt()

    Az_minus_ct1 = (A*z - c*t1).intt()

    w_prime = h.use_hint(Az_minus_ct1, 2 * γ_2)
    w_prime_bytes = w_prime.bit_pack_w(γ_2)

    return c_tilde == H(μ + w_prime_bytes, 32)

[simonmasson]

We can get rid of many hash functions by storing the matrix A_hat and tr. Also, we store 2^d * t1.ntt() instead of t1:

def verify(self, pk_bytes, m, sig_bytes):
    # unpacking pk and sig
    A_hat, tr, t1_new = unpack_pk(pk_bytes)
    c_tilde, z, h = unpack_sig(sig_bytes)

    # checks of size
    assert(h.sum_hint() > ω)
    assert(z.check_norm_bound(γ_1 - β))

    μ = H(tr + m, 64)
    c = sample_in_ball(c_tilde, τ)

    c = c.ntt()
    z = z.ntt()

    Az_minus_ct1 = (A*z - c*t1_new).intt()

    w_prime = h.use_hint(Az_minus_ct1, 2γ_2)
    w_prime_bytes = w_prime.bit_pack_w(γ_2)

    return c_tilde == H(μ + w_prime_bytes, 32)

[simonmasson]

We can store c_ntt as part of the signature. But c has coefficients ±1 but c_ntt has large coefficients.

def verify(self, pk_bytes, m, sig_bytes):
    # unpacking pk and sig
    A_hat, tr, t1_new = unpack_pk(pk_bytes)
    c_tilde, z, h, c_ntt = unpack_sig(sig_bytes)

    # checks of size
    assert(h.sum_hint() > ω)
    assert(z.check_norm_bound(γ_1 - β))

    μ = H(tr + m, 64)

    z = z.ntt()

    Az_minus_ct1 = (A*z - c_ntt*t1_new).intt()

    w_prime = h.use_hint(Az_minus_ct1, 2γ_2)
    w_prime_bytes = w_prime.bit_pack_w(γ_2)

    return c_tilde == H(μ + w_prime_bytes, 32)

[simonmasson]

In terms of size:

Public key

• The matrix A_hat: 16 field elements = 16 * 256 * 32b = 16 * 256 * 4B = 16384B.
• The bytes tr: 32B.
  Note that we can absorb tr in the hash so that we just hash the message.
  Then it would be 64B (?).
• The vector t1_new: 4 field elements = 4 * 256 * 32b = 4 * 256 * 4B = 4096B.
  Note that this is possible only because we store A_hat and tr.
  Otherwise, tr = H(ρ||t1) and the original t1 is required.

Total: 20.512 kB (assuming tr is 32B).

Signature

• The bytes of c_tilde: 32B.
• The vector z: 4 field elements = 4 * 256 * 32b = 4 * 256 * 4B = 4096B.
• The vector h: 4 field elements = 4 * 256 * 32b = 4 * 256 * 4B = 4096B.
• The element c_ntt: 256*4B = 1024B
  (although it is only 32B in the "time" domain).

Total: 9.248kB (8.256kB if we compute c.ntt()).

[simonmasson]

The cost of the verification is (mainly):

• Two hashes (for μ and the final check)
• Four NTT and Four iNTT (for z and Az-ct1)
• Some vectorized multiplication and checks that we can neglect for now(?).

Total: 2H + 8NTT.

[simonmasson]

A first version is implemented in 56f36bb. For now, we plan to pack elements in slices of 32 bits (makes more sense for solidity), so we use c_ntt.

[simonmasson]

h is actually small and can fit in 84B instead of 4096B, but the cost of the decompression in the verification will thus increase. It is not clear if we prefer a 4kB increase, or a higher gas cost.