■
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
