Accelerating Bliss: the geometry of ternary polynomials

L´eo Ducas

University of California, San Diego

lducas@eng.ucsd.edu

Abstract

The signature scheme Bliss proposed by Ducas, Durmus, Lepoint and Lyubashevsky at

Crypto’13, is currently the most compact and efficient lattice-based signature scheme that is

provably secure under lattice assumptions. It does compare favourably with the standardized

schemes RSA and ECDSA on both Software and Hardware.

In this work, we introduce a new technique that improves the above scheme, offering an

acceleration factor up to 2.8, depending on the set of parameters.

Namely, we improve the unnatural geometric bound used in Bliss to a tighter and much

more natural bound by using some extra degree of freedom: the ternary representations of

binary challenges. Precisely, we efficiently choose a ternary representation that makes the result

deterministically shorter than the expected length for a random challenges.

Our modified scheme Bliss-b is rather close to the original scheme, and both versions are

compatible. The patch has been implemented on the Open-Source Software implementation of

Bliss, and will be released under similar license.

1 Introduction

Lattice based cryptography [Ajt96, AD97], has received a lot of attention in the last decade, mostly

for theoretical interest. First for security: lattices enjoy worst-case hardness properties and seem

resistant to quantum attacks. Later, lattices have shown exceptional versatility, allowing new

constructions such as the breakthrough result of Gentry [Gen09] for Fully Homomorphic Encryption.

On the practical side, lattice-based cryptography has long been a promising alternative to RSA

and discrete-log cryptography. Indeed, the use of algebraic lattices [Mic02] can boost many latticebased

constructions as already noticed in the late 90’s for the construction of the NTRU Encryption

scheme1

[HPS98]. While efficient lattice-based encryption has quickly found satisfactory solutions,

lattice-based signatures have been more problematic: the natural lattice trapdoor leaks some secret

information [NR06, DN12]. It is only in 2008 that provably secure solutions to prevent such leakage

have been found [GPV08, Lyu09].

Both solutions were originally not so practical, and could only be proved secure in the randomoracle

model. Despite several efforts [SS11, DPL14] the hash-then-sign approach of [GPV08] is

indeed quite slow for signatures in practice. But the trapdoors of [GPV08, MP12] remain useful

for more advanced constructions such as attribute based encryption [CHKP12, GVW13, DPL14]

or to avoid relying on random oracles [Boy10, DM14] when building signatures.

1

IEEE Std 1363.1 and standard X9.98.

1

On the other hand, the Fiat-Shamir with aborts approach of Lyubashevsky [Lyu09, Lyu12,

GLP12, DDLL13, BG14, PDG14, MBDG14] has demonstrated very good performances. In particular,

the recent scheme Bliss has proved to compete with the standardized signature schemes

RSA and ECDSA both on software and hardware [DDLL13, PDG14]. Nevertheless, Bliss seems

to have room for improvements, both at the implementation level2 and at the design level.

In particular, there is a geometric constant C used to bound the length of certain vectors during

the execution of Bliss. Because of the abort technique, this constant C has a direct impact on

the overall speed of the protocol. Experiments suggest that this bound should not be much larger

that 1: over 20000 random challenges, C = 1.1 is sufficient with some margin. Yet we need this

bound to hold for all keys and all challenges, for which Ducas et al. [DDLL13] could only prove, a

constant C ∈ [1.5, 1.9] depending on the parameter set.

1.1 This work

The problem. The speed of Bliss is related to the `2 norm of the product Sc where the matrix

S is the secret key and c the challenge vector. More precisely, one requires a bound kSck ≤ B,

independent of the secret key S ∈ S in order to avoid leaking information on the secret key S while

signing. This bound dictates the running time of the Bliss signing procedure: the main loop needs

to be repeated M = e

B2/2σ

2

times on average3

, and M is called the repetition rate. Therefore any

improvement on this bound kSck ≤ B directly leads to an acceleration of Bliss without altering

the rest of the scheme.

The set of challenges B

n

κ

is the set of binary vector with exactly κ entries equal to 1, in particular

we have kck =

√

κ. Quite naturally one could bound kSck by s1(S) · kck where s1(S) denotes the

singular norm (a.k.a. the spectral radius) of S. Unfortunately the singular norm of S is quite

larger in the ring setting than in the standard setting: for ternary entries {0, ±1} with density δ

of ±1 entries, we expect s1(S) ≈

√

δn√

log n in the ring setting against s1(S) = Θ(√

δn) without

ring structure (see Section 2.3). This √

log n factor may seem anecdotal in theory but is quite

relevant in practice: in the design of Bliss a lot of effort was done to cut such corners, pushing

the proof of concepts [Lyu09, Lyu12] to an actual, practical scheme, competing with standardized

cryptography [DDLL13, PDG14].

To improve on such a bound, Ducas et al. [DDLL13] exploit the binary structure of the challenge

vector c and discuss the Gram matrix of the secret matrix G = S

tS. In practice, rejecting a

reasonable (up to 90%) proportion of secret keys S during key generation depending on G they

obtain the provable guarantee that kSck ≤ Cδ√

nκ for any c ∈ B

n

κ

, where the value C varies

between 1.5 and 1.9 from Bliss-0 to Bliss-IV. While this is much better than the singular norm

bound (in practice measured to be around 5), this is still quite far from 1.

Our solution. The introduction of the bimodal trick in [DDLL13] had a small drawback compared

to previous similar constructions [Lyu09, Lyu12, GLP12]: the challenge vector c inherently

became a modulo 2 object, and it was no longer possible to increase the entropy by using coefficients

in {0, ±1} rather than {0, 1}.

Nevertheless, it does not restrict us to using the canonical binary representation c

0 ∈ Z

n of

c ∈ Z

n

2

, in particular one may negate at will individual coordinates of c

0 at the beginning of the

2The open source software implementation [DL] does not use vectorized operations (MMX/SSE) for the Number

Theoretic Transform. Pseudo random number generation could also benefit from AES instructions.

3

the choice of σ is determined by security constraints, which we won’t discuss in this paper.

2

response phase, as long as the bound on kSc0k is preserved. And in fact, choosing an appropriate

representation c

0 may give a smaller result. We propose a simple algorithm that efficiently compute

the product v = Sc0

for some c

0 ≡ c mod 2 such that kSc0k ≤ kSk · √

κ (where kSk denote the

largest norm among the columns of S). This result is optimal considering the case where S would

have perfectly orthogonal rows.

Results. Using the technique above, we are able to remove the unnatural constant C ∈ [1.5, 1.9]

and replace it by 1. We propose a variant Bliss-b of Bliss, with similar set of parameters but

for the rejection rate M, which is improved by a factor from 1.4 to 3.4. We have implemented our

modification on the open-source implementation [DL]. Due to additional algorithmic efforts, the

speed-up in practice is slightly less than what is predicted by the rejection rate. Our modification

also speeds-up the key generation by a factor 5 to 10. Our patch will be made available under the

terms of the original CeCILL license.

Organization. The rest of the paper is organized as follows. In Section 2 we give the necessary

preliminaries on the construction of Bliss. Then, in Section 3 we present the efficient sign choosing

algorithm and prove the associated bound on the product kSc0k. We conclude with Section 4 by

detailing the modification to obtain the new scheme Bliss-b: the algorithmic modifications, the

new parameters, and the comparative benchmarks.

2 Preliminaries

Notations Lower-case bold letters will denote column vectors over Z, and upper-case bold letters

will denote matrices. The norm k · k notation refers to the euclidean norm for vectors. For a

matrix M = [m1 . . . mk] ∈ Z

`×k

, the norm kMk refers to the maximal norm among its columns:

kMk = maxi kmik. We note B for the binary set {0, 1}, and B

n

κ denotes the set of vectors of n

binary coordinates with exactly κ coordinates set to 1: B

n

κ = {c ∈ B

n

|kck1 = κ}. For such binary

vectors c ∈ B

n

κ

, we define the indicator set Ic = {i|ci 6= 0}.

2.1 The Cyclotomic Ring

As several prior constructions [LMPR08, LPR10], Bliss relies on a power of 2 cyclotomic ring: we

let n be a power of 2 defining the (2n)th cyclotomic polynomial Φ2n(X) = Xn + 1 and associated

cyclotomic ring R = Z[X]/(Xn + 1). Those rings have convenient geometric properties, and allows

very efficient Number Theoretic Transform for well chosen modulus q. We also write Rq = R/(qR)

for the residue ring of R modulo an integer q. Elements in R have a natural representation as

polynomials of degree n − 1 with coefficients in Z, and R can be identified (as an additive group)

with the integer lattice Z

n

, where each ring element a = a0+a1x+. . .+an−1x

n−1 ∈ R is associated

with the coefficient vector a = (a0, . . . , an−1) ∈ Z

n

.

The ring R is also identified with the sub-ring of anti-circulant square matrices of dimension

n by regarding each ring element r ∈ R as a linear transformation x 7→ r · x over (the coefficient

embedding) of R.

More specifically, we will see the secret and public keys S, A as matrices with two anti-circulant

blocks of size n × n, while the polynomials u, c will be seen as column vectors of dimension n over

Z2q, and vectors of polynomials v, y, z will be seen as column vectors over Z2q of dimension 2n.

3

Prover Verifier

Secret Key S ∈ R2×1

, short A · S = q mod 2q A = [a, q − 2] ∈ R1×2

2q

(S ∈ Z

2n×n

) (A ∈ Z

n×2n

2q

)

Commit

Sample y ← D2n

σ

Compute u = A · y mod q

u −−−−→

Challenge

c ←−−−− Sample c ∈ B

n

κ

Compute z = y ± Sc Response

Abort except with proba

1 − D2n

σ

(z)/M · D2n

σ

(z ± Sc)

z −−−−→ Accept if kzk is small

and Az = u + qc, Accept

Figure 1: Bliss as a Σ-protocol

2.2 The original Bliss

The full description of Bliss is given in Appendix A, for our purpose we require only a simplified

description of the scheme. It is designed using the so-called Fiat-Shamir paradigm [FS86] with

an extra abort step as introduced in [Lyu09] to prevent leaks of secret information. The scheme

can be described as a Σ-protocol (a 3-round identification protocol). It is then transformed into a

signature scheme by replacing the challenge generation step by a call to a hash function (modelled

as a Random Oracle) to generate the challenge c. The Σ-protocol associated to Bliss is described

in Figure 1. In this description, D2n

σ denotes the discrete gaussian distribution of covariance σ

2

· Id

in dimension 2n.

The repetition rate is set to M = e

1/(2α

2

) and the correctness of the rejection sampling (which

is required by the security proof) is ensured if for all challenges c ∈ B

n

κ

, σ ≥ α · kSck. This article

focuses on the improvement of the bound on kSck, hoping to increase the parameter α and therefore

accelerating the whole scheme with minimal modifications. Modifying other parameters (σ, δ, . . .)

one could trade this speed improvement for compactness or security, but that would be a more

substantial alteration of Bliss. Modifying only α and M does preserve the whole security claims

of [DDLL13], as well as the optimized CDT tables precomputed in [PDG14].

The original bound. Let us recall how such bound is established in [DDLL13]. Let G denotes

the Gram matrix associated to the secret key S ∈ S: G = S

t

· S. The bound used in Bliss follows

from rewriting

kSck

2 = c

tGc =

X

i∈Ic

X

j∈Ic

Gi,j

(we recall that Ic is the indicator set of c, defined by Ic = {i|ci = 1}). Such sum can be bounded

independently of c :

kSck

2 ≤ Nκ(S) where Nκ(S) = max

I⊂{1,...,n}

#I=κ

X

i∈I

max

J⊂{1,...,n}

#J=κ

X

j∈J

Gi,j!

4

Name of the scheme Bliss-0 Bliss-I Bliss-II Bliss-III Bliss-IV

Security Toy 128 bits 128 bits 160 bits 192 bits

Optimized for Fun Speed Size Security Security

Signature size 3.3kb 5.6kb 5kb 6kb 6.5kb

dimension n 256 512 512 512 512

α .5 1 .5 .7 .55

κ 12 23 23 30 39

Secret key Nκ-Threshold C 1.5 1.62 1.62 1.75 1.88

Repetition rate M 7.39 1.65 7.39 2.77 5.22

Table 1: Selected parameters of Bliss

Out of the set S0 of all sampleable secret keys (see Alg. 3 in Appendix A), some will be rejected,

restricting the set of keys to S = {S ∈ S0|Nκ(S) ≤ B}. This ensures the bound kSck

2 ≤ B

independently of both the choices S ∈ S and c ∈ B

n

κ = B

n

κ

.

Original parameter. The (relevant) parameters of Bliss are given in Table 1 (a full table is

given in Appendix A). The Nκ-threshold C defines the ratio between the bound on kSck and its

expected value kSk · kck ≈ p

5 · dδne · κ (δ denotes the density of ±1 among the ternary entries

{0, ±1} of the secret key S). That is, the set of acceptable secret keys in Bliss is defined as

S = {S ∈ S0|Nκ(S) ≤ C

2

· 5dδne · κ}

for some set S0 implicitly defined in the Key Generation algorithm (Alg. 3).

2.3 Asymptotics of various geometric bounds

For the sake of this discussion we may drop the parameter δ and consider that the coefficients of

S are uniformly randomly chosen from {±1}. We here detail the argument behind the asymptotic

claims made during the introduction.

Singular norm, non-Ring setting. The spectral theory of random matrices [Ver10] ensures

that s1(S) = Θ(√

n) with overwhelming probability. This would lead to a constant C = Θ(1).

Singular norm, ring setting. Let us drop, for the sake of this discussion the binary structure of

the secret and the challenge. Consider two polynomials s, c ∈ R = R[X]/Φ2n(X) where s is drawn

with spherical gaussian distribution in the coefficient representation (s =

PfjXj , fj ← χ). Now

consider the complex representation (a.k.a. the Fourier transform of s) ˆs of s (ˆsj = s(e

π(2j+1)ı/n)),

we remind that the Fourier transform is a scaled orthogonal map: kxˆk =

√

n · kxk. Because in

the complex embedding multiplication occurs component-wise, that is scb = ˆs cˆ, we conclude that

s1(s) = ksˆk∞. We expect from order statistic theory ksˆk∞ = O(

√

n log n) as the maximum of n

many Gaussian of variance √

n (see [Roy82]). This would lead to C = O(

√

log n).

The Nκ-norm, Ring Setting. A small modification of the proof of [DDLL13, Prop. 4.1 of the

full version] can establish that

Nκ(S) ≤ (5dδne + 1)κ + κ

2

√

nδ · ω(

p

log n)

5

with overwhelming probability. Note that the only constraint on κ is that c ← B

n

κ has at least Θ(n)

bits of entropy, requiring κ ≥ Θ(n/ log n). If the second term were negligible one would be able to

choose C = 1 +o(1). While it is not asymptotically negligible, this second term remains reasonably

small for the parameter of Bliss explaining why the constant C could be chosen as small as 1.5.

3 The Sign Choices algorithm and its Geometry

As detailed in the introduction, we will exploit ternary representation in Z

n of challenge vectors

modulo 2, by individually negating some coordinates of the binary vector c in order to greedily

minimize the norm of kSck. More specifically, we rely on the identity:

ka + bk

2 = kak

2 + kbk

2 + 2 ha , bi (1)

which implies that either ka + bk

2 or ka − bk

2

is less than kak

2 + kbk

2

. Precisely,

ka − ςbk

2 ≤ kak

2 + kbk

2 where ς = sgn(ha , bi) ∈ {±1} (2)

where the sign function takes (arbitrarily) the value 1 on input 0.

Algorithm 1: GreedySC(S, c), The Greedy Sign Choices Algorithm.

Input: a matrix S = [s1 . . . sn] ∈ Z

m×n and a binary vector c ∈ B

n

κ

Output: v = Sc0

for some c

0 ≡ c mod 2 such that kSc0k

2 ≤ kSk

2

· kck

2 = kSk

2

· κ.

1: v ← 0 ∈ Z

m

2: for i ∈ Ic do

3: ςi ← sgn(hv , sii)

4: v ← v − ςi

· si

5: end for

6: return v

Theorem 1 (Correctness of the Greedy Sign Choices Algorithm). On inputs S ∈ Z

m×n and c ∈ B

n

κ

,

the algorithm outputs v = GreedySC(S, c) such that v = Sc0

for some ternary vector c

0 ≡ c mod 2

and

kSc0

k

2 ≤ kSk

2

· kck

2 = kSk

2

· κ.

Proof. We prove an invariant of the for-loop of GreedySC, assuming the set Ic is visited in some

fixed order. We consider the subset Jk ⊂ Ic of indexes i that have been visited after k steps and

set

c

0

k = −

X

i∈Jk

ςi

· ei (ei ∈ Z

n being the i-th canonical unit vector).

We will prove the following invariant: c

0

k

is a ternary vector such that Ic

0

k

= Jk and vk = S · c

0

k

verifies kvkk

2 ≤ kSk · k. It is trivially verified for k = 0. For the induction, first decompose

Jk+1 = Jk ∪ {i} where i ∈ Ic \ Jk. Following inequality (2) we derive:

kvk+1k

2 ≤ kvkk

2 + ksik

2 ≤ kSk

2

· k + kSk

2 ≤ kSk

2

· (k + 1).

We conclude that the output v = vκ = Sc0

κ verifies kvk

2 ≤ kSk

2

· κ and that c

0 = c

0

κ

is a ternary

vector verifying Ic

0 = Ic.

6

Efficiency. One may note the algorithm is not technically running in quasilinear time: it requires

O(mκ) integer additions, where m = 2n and κ = Ω(n/ log n) to ensure that c ← B

n

κ

contains at

least Θ(n) bits of entropy. Yet in practice the parameter κ is quite small (at most κ = 39 against

n = 512 for Bliss-IV) making the sparse subset-sum algorithm to compute Sc faster than the

Number Theoretic Transform based algorithm, especially considering that the entries of S are quite

small. The implementation [DL] of Bliss indeed use a 64-bits vectorized subset-sum algorithm with

8-bits chunks.

Still, this new algorithm will be substantially slower: we need twice as many operations because

of the added inner product, and those require computing with larger numbers. We need to be careful

to avoid making this part of the algorithm way too costly in practice. The following vectorization

should be enough to keep the cost of GreedySC much smaller than the Gaussian sampling of y1, y2

and the NTT product a1 · y1.

Vectorized Implementation with 16-bits chunks. For the parameters of Bliss, we always

have kSk∞ ≤ 5 (see Algorithm 4 in Appendix A) which guarantees that kvk∞ ≤ 5κ ≤ 195

during the whole algorithm: the entries of v can definitely be stored as 16-bit signed integers.

Additionally, any partial sum during the computation of hv , sii must be less in absolute value

than m = kvk · kSk ≤ kSk

2

·

√

κ. For all parameter sets Bliss-0 to Bliss-IV one easily checks that

m is much less than 215. The whole GreedySC can therefore benefit from vectorized instructions

with 16-bits signed chunks.

4 The modified scheme and instantiations

4.1 Modifications of the scheme

We define a modified version Bliss-b of the scheme Bliss from [DDLL13]. The modifications to

the original scheme are listed below:

• We remove the constant C and the ad-hoc norm Nκ from the definitions

• A constant

Pmax =

(5dδ1ne + 5) · κ if δ2 = 0

(5dδ1ne + 20dδ2ne + 9) · κ otherwise

is defined (syntactic sugar). The output product Sc0 = GreedySC(S, c) verifies kSc0k

2 ≤ Pmax

since kSk

2 = 5(dδ1ne + 4dδ2ne) + 4g0 + 1.

• Line 3 of Algorithm 3 is removed: keys are no longer rejected during Key Generation.

• The Signature algorithm (Algorithm 4) is replaced by Algorithm 2, described below.

One may note that leaking the sign choices made in c

0 during the algorithm GreedySC would

reveal information on the secret key S. Fortunately, such information is only carried by v, and the

rejection step is exactly designed to perfectly hide v assuming kvk ≤ Pmax.

7

Algorithm 2: Modified Bliss Signature Algorithm

Input: Message µ, public key A = (a1, q − 2) ∈ R1×2

2q

, secret key S = (s1, s2)

t ∈ R2×1

2q

Output: A signature (z1, z

†

2

, c) of the message µ

1: y1, y2 ← DZn,σ

2: u = ζ · a1 · y1 + y2 mod 2q

3: c ← H(bued mod p, µ)

4: (v1, v2) ← GreedySC(S, c)

5: Choose a random bit b

6: (z1, z2) ← (y1, y2) + (−1)b

· (v1, v2)

7: Continue with probability 1. M exp

−

kvk

2

2σ2

cosh

hz , vi

σ2

otherwise restart

8: z

†

2 ← (bued − bu − z2ed) mod p

9: Output (z1, z

†

2

, c)

4.2 New parameters and benchmarks

We left all parameters related to security unmodified, so that the security claims of [DDLL13] are

preserved, our modifications only affect the efficiency of the scheme. we recall that the rejection

rate is defined as M = exp(1/(2α

2

)). The new value of α is given by α = σ/Pmax. We obtain

a theoretical speed-up ranging from 1.4 to 3.4 as detailed in Table 2. The Key Generation is

also accelerated by a factor 5 to 10 since secret keys are not rejected according to Nκ anymore.

Our implementation conforms to those predictions considering a small slowdown related to the

added cost of the greedy algorithm: the actual speed-up factor varies from 1.2 (Bliss-bI) to 2.8

(Bliss-bII). Table 3 compares the running time of Bliss and Bliss-b.

Scheme Bliss-b0 Bliss-bI Bliss-bII Bliss-bIII Bliss-bIV

Security Toy 128 bits 128 bits 160 bits 192 bits

Optimized for Fun Speed Size Security Security

Signature size 3.3kb 5.6kb 5kb 6kb 6.5kb

dimension n 256 512 512 512 512

α .748 1.610 .801 1.216 1.027

Repetition rate M 2.44 1.21 2.18 1.40 1.61

Predicted Speed-up ×3.0 ×1.4 ×3.4 ×2.0 ×3.3

Table 2: Parameters of the modified scheme Bliss-b

Scheme Bliss-0 Bliss-I Bliss-II Bliss-III Bliss-IV

Sign Run Time 256 µs 154 µs 520 µs 240 µs 419 µs

Scheme Bliss-b0 Bliss-bI Bliss-bII Bliss-bIII Bliss-bIV

Sign Run Time 108 µs 128 µs 185 µs 146 µs 167 µs

Speed-up ×2.4 ×1.2 ×2.8 ×1.6 ×2.5

Table 3: Running Time in microseconds averaged over 10 000 signatures. (Intel Core @ 3.40GHz).

8

Backward and Forward compatibility. Signatures are both backward and forward compatible,

that is signature generated using Bliss-b will also be valid for Bliss and reciprocally, since

both schemes are corrects and have the same verification algorithm. Secret keys are only forward

compatible, that is secret keys generated by Bliss can be used in Bliss-b and do benefit from the

speed-up as well. Yet secret keys generated by Bliss-b should not be used in Bliss: the condition

σ ≥ α · kSck may not always hold leading to information leakage.

Acknowledgements

The authors wish to thank V. Lyubashevsky, T. Lepoint, and J.C. Deneuville for helpful comments.

This research was supported in part by the DARPA PROCEED program and NSF grant CNS1117936.

Opinions, findings and conclusions or recommendations expressed in this material are

those of the author(s) and do not necessarily reflect the views of DARPA or NSF.

References

[AD97] Mikl´os Ajtai and Cynthia Dwork. A public-key cryptosystem with worst-case/average-case equivalence.

In 29th ACM STOC, pages 284–293. ACM Press, May 1997.

[Ajt96] Mikl´os Ajtai. Generating hard instances of lattice problems (extended abstract). In 28th ACM

STOC, pages 99–108. ACM Press, May 1996.

[BG14] Shi Bai and Steven D. Galbraith. An improved compression technique for signatures based on

learning with errors. In Josh Benaloh, editor, CT-RSA 2014, volume 8366 of LNCS, pages 28–47.

Springer, February 2014.

[Boy10] Xavier Boyen. Lattice mixing and vanishing trapdoors: A framework for fully secure short

signatures and more. In Phong Q. Nguyen and David Pointcheval, editors, PKC 2010, volume

6056 of LNCS, pages 499–517. Springer, May 2010.

[CHKP12] David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. Bonsai trees, or how to delegate a

lattice basis. Journal of Cryptology, 25(4):601–639, October 2012.

[DDLL13] L´eo Ducas, Alain Durmus, Tancr`ede Lepoint, and Vadim Lyubashevsky. Lattice signatures and

bimodal gaussians. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume

8042 of LNCS, pages 40–56. Springer, August 2013.

[DL] L´eo Ducas and Tancr`ede Lepoint. A Proof-of-concept Implementation of BLISS. Available under

the CeCILL License at http://bliss.di.ens.fr.

[DM14] L´eo Ducas and Daniele Micciancio. Improved short lattice signatures in the standard model. In

Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014, Part I, volume 8616 of LNCS,

pages 335–352. Springer, August 2014.

[DN12] L´eo Ducas and Phong Q. Nguyen. Learning a zonotope and more: Cryptanalysis of NTRUSign

countermeasures. In Xiaoyun Wang and Kazue Sako, editors, ASIACRYPT 2012, volume 7658

of LNCS, pages 433–450. Springer, December 2012.

[DPL14] Leo Ducas, Thomas Prest, and Vadim Lyubashevsky. Efficient identity-based encryption over

ntru lattices. 2014. To be Published at Asiacrypt 2014.

[FS86] Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and

signature problems. In Andrew M. Odlyzko, editor, CRYPTO’86, volume 263 of LNCS, pages

186–194. Springer, August 1986.

9

[Gen09] Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher,

editor, 41st ACM STOC, pages 169–178. ACM Press, May / June 2009.

[GLP12] Tim G¨uneysu, Vadim Lyubashevsky, and Thomas P¨oppelmann. Practical lattice-based cryptography:

A signature scheme for embedded systems. In Emmanuel Prouff and Patrick Schaumont,

editors, CHES 2012, volume 7428 of LNCS, pages 530–547. Springer, September 2012.

[GPV08] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new

cryptographic constructions. In Richard E. Ladner and Cynthia Dwork, editors, 40th ACM

STOC, pages 197–206. ACM Press, May 2008.

[GVW13] Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. Attribute-based encryption for

circuits. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th ACM STOC,

pages 545–554. ACM Press, June 2013.

[HPS98] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A ring-based public key cryptosystem.

In Algorithmic Number Theory – Proc. ANTS-III, volume 1423 of Lecture Notes in

Computer Science, pages 267–288. Springer, 1998.

[LMPR08] Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, and Alon Rosen. SWIFFT: A modest

proposal for FFT hashing. In Kaisa Nyberg, editor, FSE 2008, volume 5086 of LNCS, pages

54–72. Springer, February 2008.

[LPR10] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors

over rings. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 1–23.

Springer, May 2010.

[Lyu09] Vadim Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and factoring-based

signatures. In Mitsuru Matsui, editor, ASIACRYPT 2009, volume 5912 of LNCS, pages 598–

616. Springer, December 2009.

[Lyu12] Vadim Lyubashevsky. Lattice signatures without trapdoors. In David Pointcheval and Thomas

Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 738–755. Springer, April

2012.

[MBDG14] Carlos Aguilar Melchor, Xavier Boyen, Jean-Christophe Deneuville, and Philippe Gaborit. Sealing

the leak on classical ntru signatures. In Post-Quantum Cryptography, pages 1–21. Springer,

2014.

[Mic02] Daniele Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions

from worst-case complexity assumptions. In 43rd FOCS, pages 356–365. IEEE Computer

Society Press, November 2002.

[MP12] Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In

David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS,

pages 700–718. Springer, April 2012.

[NR06] Phong Q. Nguyen and Oded Regev. Learning a parallelepiped: Cryptanalysis of GGH and

NTRU signatures. In Serge Vaudenay, editor, EUROCRYPT 2006, volume 4004 of LNCS, pages

271–288. Springer, May / June 2006.

[PDG14] Thomas P¨oppelmann, L´eo Ducas, and Tim G¨uneysu. Enhanced lattice-based signatures on

reconfigurable hardware. In Lejla Batina and Matthew Robshaw, editors, CHES 2014, volume

8731 of LNCS, pages 353–370. Springer, September 2014.

[Roy82] J. P. Royston. Algorithm AS 177: Expected Normal Order Statistics (Exact and Approximate).

Journal of the Royal Statistical Society. Series C (Applied Statistics), 31(2):161–165, 1982.

10

[SS11] Damien Stehl´e and Ron Steinfeld. Making NTRU as secure as worst-case problems over ideal

lattices. In Kenneth G. Paterson, editor, EUROCRYPT 2011, volume 6632 of LNCS, pages

27–47. Springer, May 2011.

[Ver10] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices.

CoRR, abs/1011.3027, 2010. http://www-personal.umich.edu/~romanv/papers/

non-asymptotic-rmt-plain.pdf.

A Full Description of Original Bliss and parameters

Algorithm 3: Bliss Key Generation

Output: Key pair (A, S) such that AS = q mod 2q

1: Choose f, g as uniform polynomials with exactly d1 = dδ1ne entries in {±1} and d2 = dδ2ne entries in

{±2}

2: S = (s1, s2)

t ← (f, 2g + 1)t // Implicitly defining the set S0

3: if Nκ(S) ≥ C

2

· 5 · (dδ1ne + 4dδ2ne) · κ then restart

4: aq = (2g + 1)/f mod q (restart if f is not invertible)

5: Output(A, S) where A = (2aq, q − 2) mod 2q

Algorithm 4: Bliss Signature Algorithm

Input: Message µ, public key A = (a1, q − 2) ∈ R1×2

2q

, secret key S = (s1, s2)

t ∈ R2×1

2q

Output: A signature (z1, z

†

2

, c) of the message µ

1: y1, y2 ← DZn,σ

2: u = ζ · a1 · y1 + y2 mod 2q

3: c ← H(bued mod p, µ)

4: Choose a random bit b

5: z1 ← y1 + (−1)b

s1c; z2 ← y2 + (−1)b

s2c

6: Continue with probability 1. M exp

−

kSck

2

2σ2

cosh

hz , Sci

σ2

otherwise restart

7: z

†

2 ← (bued − bu − z2ed) mod p

8: Output (z1, z

†

2

, c)

Algorithm 5: Bliss Verification Algorithm

Input: Message µ, public key A = (a1, q − 2) ∈ R1×2

2q

, signature (z1, z

†

2

, c)

Output: Accept or Reject the signature

1: if k(z1|2

d

· z

†

2

)k2 > B2 then Reject

2: if k(z1|2

d

· z

†

2

)k∞ > B∞ then Reject

3: Accept iff c = H

ζ

· a1 · z1 + ζ · q · c

d

+ z

†

2 mod p, µ)

1

Name of the scheme BLISS-0 BLISS-I BLISS-II BLISS-III BLISS-IV

Security Toy (≤ 60 bits) 128 bits 128 bits 160 bits 192 bits

Optimized for Fun Speed Size Security Security

n 256 512 512 512 512

Modulus q 7681 12289 12289 12289 12289

Secret key densities δ1, δ2 .55 , .15 .3 , 0 .3 , 0 .42 , .03 .45, .06

Gaussian standard deviation σ 100 215 107 250 271

α .5 1 .5 .7 .55

κ 12 23 23 30 39

Secret key Nκ-Threshold C 1.5 1.62 1.62 1.75 1.88

Dropped bits d in z2 5 10 10 9 8

Verification thresholds B2, B∞ 2492, 530 12872, 2100 11074, 1563 10206,1760 9901, 1613

Repetition rate 7.4 1.6 7.4 2.8 5.2

Entropy of challenge c ∈ B

n

κ 66 bits 132 bits 132 bits 161 bits 195 bits

Signature size 3.3kb 5.6kb 5kb 6kb 6.5kb

Secret key size 1.5kb 2kb 2kb 3kb 3kb

Public key size 3.3kb 7kb 7kb 7kb 7kb

12