Dragonfly Fintech Pte Ltd.
NEM Core Team Member
E-mail: lwong@dfintech.com
November, 2016
Abstract: A major challenge for financial institutions is the
inherent inefficiencies of multiple ledgers within their systems. A
blockchain solution with multiple ledgers for multiple assets
provides a transformation approach to addressing this issue. We
present the all new Catapult blockchain solution platform based
on the original NEM technology and concepts. An open platform,
the solution is designed to bring down the cost of implementation
and ownership, and is a solution that will power the present and
future needs for blockchain driven solutions. The Catapult
solution is architected to allow for easy integration with most
applications, and therefore is agnostic to existing banking
standards. It allows for interoperability between blockchain
instances thereby permitting shareable and non-shareable data
to co-exist in a homogenous environment. This paper is
intentionally written to address a wide spectrum of readers.
Keywords: Catapult, Mijin, NEM, Tech Bureau, Dragonfly
Fintech, blockchain, smart contract, permissible chain, open
system blockchain, banking standards, multi-ledger.
Table of Contents
4.3.1. Mutual Fund – Transfer Agent ..........................10
4.3.2. Interest Rate Swap Arrangement.......................12
The NEM blockchain technology has been around for more than
two years. Designed with mainstream applications in mind, it is
the intent, therefore, that the NEM team should develop a
solution based on what it can do in the most extensible manner.
The focus of the NEM project has always been to unleash the
power of the blockchain technology as a priority and quickly
allow projects to build applications on top of this platform and
realise the power of the blockchain technology.
We are of the opinion that blockchain technology is trying to find
its place in the industry, but lacks uniformity in approach and
standards. From what is available in the market space, one can
immediately conclude that most blockchain initiatives revolve
around the blockchain ledger, all with subtle variances on how
the blockchain is run, and with slightly different flavours.
Our approach takes a different twist. Functionalities and features
of a powerful blockchain are not our only emphasis. We have
incorporated equally important elements that are hitherto
subject to much neglect. These include:
1. allowing any solution to sit on it independently;
2. an abstraction layer with a full suite of APIs, allowing for
ease of integration, and thereby harnessing the power of
the blockchain ledger; and
3. scalability.
The purpose of this paper is to describe how NEM achieves this
and how NEM as a solution, is a best of breed solution that not
only serves a very important role as a blockchain technology but
also sets a new standard for blockchain technology.
Blockchain technology is a ledger solution. Naturally, as a ledger,
its distinct feature is particularly relevant to the financial
industry, too. All financial institutions use the ledger as the single
most important element in its core banking solution.
Unfortunately, it is a well-known fact that many applications
built upon the ledger for various banking services are designed
based on proprietary ledgers befitting each service application.
Over the years, the number of ledgers and applications grow and
reconciliation becomes a massive problem.
A compounding effect and risk exist when banks start to transact
among each other, each with a plurality of systems that may or
may not be compatible. Built over decades, these systems have
become a monolithic mash that is too expensive and almost
impossible to streamline. The best way forward for any bank to
add new services and solutions is to continue to patch them onto
their existing systems. Workarounds are often made by making
sure these solutions fit into existing platform solutions.
From a technology standpoint, middleware becomes a thick layer
that binds this monolithic construct with a potpourri mix of
traffic and information traversing across all different ledgers,
applications, and services. It not only poses operational risk, but
it also takes a lot of the resources which the bank could otherwise
do without in managing problems and errors in these
There is a need to standardise the existing core banking solution
to make it more efficient. Currently, standardisation happens at
the middleware layer and systems rely on this middleware layer
to talk to one another.
Transaction arrangements between banks are being served by an
external messaging system, often conforming to a standard. A
dominant service is the SWIFT1 messaging and transaction
system. Designed more than 40 years ago, the SWIFT system is a
proven piece of technology, albeit it is extremely inefficient by
today’s standard, requiring some of these messages to be
managed manually as it goes through multiple hops and
Such a solution can be slow and tedious while posing some
operational risks. Banks and corporations spend hundreds of
millions of dollars every year to use the SWIFT system. When
dissected, the Internet is just as good a message routing system,
more efficient and much cheaper to use. However, the effort to
switch is a mammoth task, requiring everyone to participate and
to switchover, which in itself, is an expensive exercise and
resource consuming.
For all intents and purposes, there is enough evidence to suggest
that the plurality of systems coupled by disjointed monolithic

1 Society for Worldwide Interbank Financial Telecommunication
systems within financial institutions contribute much to the
operational risks and inefficiencies that we are witnessing today.
It is not as if these problems that we are seeing were problems of
recent times. It has been a perennial issue, with a compounding
effect each passing year as financial services and offerings get
added onto the core banking system. This is further exacerbated
by each new service offering getting more complex and
The blockchain technology poses a possible long term solution to
reducing costs; improving efficiency; allowing settlement
finality; increasing efficiency of compliance efforts; providing
greater auditability and traceability; enhancing structured
processes (recently, termed as smart contracts); and cutting
multiparty dependencies on global and local transactions.
By providing a blockchain platform that can satisfy the unmet
needs above, any financial institution would see the benefits
immediately. The blockchain platform is a standard by itself and
allows any add-on application to integrate with it using an
industry standard compliant instruction set.
We have been analysing the financial industry for 3 years, long
before the industry itself took cognisance of the impact of
blockchain and the role it can play.
Our 3-year long analysis and assessment point to a very
important conclusion from where we now unveil this blockchain
platform as an important means to an end. These goals were
drawn upon the following important conclusions:
 Smart contracts have long been in existence in all financial
institutions. They have been programmed into the core
banking solution (automated) or acted upon manually
based on agreements and protocols between parties,
internally or externally. These smart contracts cost
financial institutions billions of dollars to set up the
infrastructure over the years, and to be able to transcribe
that to a new platform will incur much more resources,
time, and risks. It is a complicated web of work that is not
quite possible to just change instantaneously. NEM has
recognised this and is approaching it in another manner.
The approach here is to make the smart contract an
external component, whether centralised (i.e., status quo
with existing systems) or decentralised. The outputs of
these smart contracts will then enter their transactions
into the ledger through a secure transaction process.
 Build a platform that is inexpensive to deploy with
minimal risk, time, and resources, while at the same time
allow a financial institution to carry on business as usual
with minimal interruptions – enabling organic growth.
 Create a blockchain platform with multiple ledgers for
multiple use cases – mutually exclusive or not – and at the
same time, allowing transactions between ledgers to be
 Create one single abstraction layer for all the ledgers in
this same blockchain to be integrated into any existing
core banking system and solutions.
 Recognise privacy and allow each financial institution to
control and manage its very own blockchain platform.
 Allow for seamless cross-platform transactions,
payments, and settlements through direct transactions
without the need to implement an expensive, standards
and protocol driven messaging system. The end result is a
reduced infrastructure system with settlement finality as
well as less reconciliation work, risks, and errors.
Figure 1. Blockchain Platform added initially as an adjunct
solution to be built over the long term as the core ledger system.
Catapult2 is a second iteration and an extension of the NEM
blockchain technology that was launched in March 2015. It is
scheduled to be released in various stages, starting from the first
quarter of 2017. Its predecessor is Mijin, which itself had
undergone vigorous tests. Mijin and Catapult are permissible
blockchains. The development difference is that Mijin is an
extension of the NEM public blockchain. The second version,
Catapult, shall be the reverse, i.e., it shall be an extension of the
private chain into the NEM public chain. It is specially designed
to add more functions and features to support the financial
industry where critical features and functions are required of the
Catapult is re-written entirely new in the C++ language,
borrowing the core concepts from its first generation NEM
release, augmenting these concepts from lessons learned, and
amending and extending these concepts to enhance the offering.
The end objective is a high performing, secure enterprise-class
solution with open connectivity. Some of the more notable
feature highlights that are being developed now for Catapult
 High scalability, design based on the industry standard
tiered web architecture commonly found in enterprise
computing, a holistic offering yet to be seen in any
blockchain solution
 Introduction of a high performance and highly scalable
API gateway server layer with an open integration
 High throughput message queues for real-time analysis
and big data analytics of transactions
 Use of nosql database at the API layer, which is more
suited for high speed messaging
 Embedded escrow service for exchange of assets on the
blockchain – a special transaction contract
 High transaction rates (in excess of 3000 transactions per

2 Catapult and Mijin are developed and marketed by Tech Bureau, Corporation
as a permissioned ledger. Both Catapult and Mijin shall be released as part of
NEM’s Open Source solution at a later date.
 Permissible access to accounts, i.e., each person can only
access what she can see.
 Interoperability – allow external decentralised or
centralised applications or smart contract solutions to
transact using the blockchain.
 Business Rules – rules where object states can result in an
indisputable transition to a new state as a result of a
definite and conclusive action, specifically on the
calculation of transaction charges based on a predefined
set of irrevocable and immutable input criteria.
 Metadata – Accounts and assets shall have configurable
metadata fields.
In addition to the above, the existing functions and features
already present in the current release of NEM, will be enhanced
and ported across to the Catapult project. These include:
 A built-in messaging solution
 A process activated or manual sign-off function for
transactions, with multiple approvals, where needed.
 A multiple ledger with multiple corresponding assets in
one blockchain
 Every account can hold multiple assets from multiple
ledgers in the same blockchain so that these accounts can
be used for all products and services the bank is offering,
e.g., one account can be holding USD, EUR,GBP, Gold,
Interest Rate Swap, ETF units, etc., each with its own
history of transaction records and balance.
 Every account can be controlled by the financial
institution – allowing for compliance and AML control
mechanisms to be implemented in order to manage these
 Freezing accounts
 Transaction reversal with full audit trail and
The end result of the Catapult solution is a strong and highly
customisable blockchain solution that can be utilised by financial
institutions as a basis to form its core operating platform in the
long term.
The principle behind the design is to provide a universal and core
blockchain solution as the basis for the greater system of a bank.
Further, it is premised on not creating a disequilibrium to the
existing system but allow for sub-system migrations over time.
Outlier and non-critical solutions can be ported across without
risking the banking system. New and older uncomplicated
products and services can be developed, or ported, and launched
using the blockchain.
This bespoke and yet highly flexible solution allows the bank time
to get accustomed to it and implement solutions on the fly while
not losing out on its growth path towards a blockchain driven
Its API gateway allows the blockchain to be easily dovetailed into
other centralised (new or existing solutions) or decentralised
(new consensus driven solutions implemented by other
initiatives) systems including smart contract systems, internal
process driven solutions, settlement, payment, and clearing
The Catapult blockchain platform is, like most things blockchain,
driven by a consensus mechanism. It consists of a network of
nodes (either permissioned or permission-less) networked
together in a peer-to-peer (P2P) configuration. Transactions are
broadcast out and each P2P node will record these transactions
and verify them as they come in. At periodic intervals, called the
block time, these transactions are grouped together and the
transactions undergo a hash process (digital fingerprinting)
linking it to the previous block, and then added on as a new block
of information in the blockchain. The permissioned ledger does
not have mining per se, and follows a controlled Proof-of-stake
algorithm, while the permission-less (Public Chain) is based on
an algorithm called Proof-of-importance3.
Built into the NEM blockchain solution is a mechanism
(Eigentrust++ reputation management algorithm) for ensuring
each P2P node is reputable and therefore not fraudulent.

3 NEM Technical Reference - https://www.nem.io/NEM_techRef.pdf
Figure 2. Principals of design. Simple and yet highly flexible
The NEM blockchain solution also created an all new P2P time
synchronisation algorithm to ensure that each node is
synchronised with one another in the right time slot.
The blockchain is intentionally designed as an open system
satisfied through a set of industry standard JSON RESTful APIs.
Therefore it is standards agnostic and is compatible with any
application that conforms to a messaging standard such as
ISO20022, or the FpML markup language. Catapult treats them
as processes with defined outputs to update or broadcast
transactions into the ledger. This method of integration and
interoperability allows for the reuse of legacy applications and
4.3.1. Mutual Fund – Transfer Agent
We now examine a typical contract and settlement solution for a
mutual fund purchase.
In a typical mutual fund scenario the actors are:
1. Mutual Fund Manager
2. Transfer Agent
3. Customer
Figure 3. Tiered Architecture with API Gateways to integrate
with other systems, or directly with thin client devices. Agnostic
in standards.
The legal contract of the mutual fund spells out certain key points
that results in the value of the sale and purchase of each unit of
asset in the mutual fund. These include, but not limited to:
1. Net Asset Value (NAV) derivation
2. Investment details and conditions
3. Dividends
4. Discounts
5. Management fee
6. Trustee fee
7. Transfer fee
8. Commissions
This legal contract in the traditional sense would have been
translated into a calculator application of which the outputs
would result in one or multiple writes into the database followed
by a series of actions, automatic or manual.
The buy and sell process initiates a request which is either
manually processed or automatically triggers a series of
operations. These operations eventually result in an outcome. In
a buy process, the outcome is:
1. Await a settlement period
2. Upon settlement, make transfer of units
3. Issue a certificate of ownership
The function of a Transfer Agent is to manage the sale, purchase,
and distribution of these assets. The job can be tedious and
Figure 4. The asset certificate is translated into an asset and is
configured into the blockchain.
Every unit holder, when she buys units of a mutual fund, will get
certificates, each representing one unit that she owns in the
blockchain. Each transaction becomes immutable and
Calculation of fees and dividends thereof will be extracted from
the blockchain from another application via an API call.
The original contract document, with its hash stored in the
blockchain, could be stored in a distributed file system. Order
processing could be another solution of which the outputs will
transact with the blockchain via an API call. User balance can be
accessed by the user with the same front end application to read
from the blockchain through an API call. Analytics again, can be
implemented on top and data extracted from the blockchain
through an API message queue call. Payment and settlement is
done through the user account directly with the blockchain.
The blockchain system is border agnostic and can be multiple
ledgers sitting in the same set of nodes. This gives rise to a very
powerful system that transgresses beyond the shores of a country
and allows for multiple countries to operate, each with their own
set of regulated rules - pertinent to the country of offer - and
conditions (smart contracts) that can be implemented in a
decentralised or centralised manner.
Smart contract templates can be built and applied across to any
fund, independently.
Blockchain solution has its settlement mechanism that can easily
be automated, cutting down settlement time to almost
instantaneous, and without intervention.
While this solution is already available in version 1 of the NEM
project, Catapult will enhance its performance and take it to the
next level based on the aforementioned improvements.
4.3.2.Interest Rate Swap Arrangement
When two parties decide to exchange interest rate contracts,
there is first an agreement. It is made between the parties
concerned and the quantitative outcome would have been
affirmed. This agreement is digitally notarised and a hash digest
is stored in the blockchain while the agreement is put onto the
distributed file system.
The computational outcome can be commonly agreed based on a
templated decentralised smart contract, or separately computed
by the participants. In any case, the blockchain will trigger the
pay-offs based on the outputs of these computed actions.
The above are two of many use cases that can be implemented
using the NEM blockchain. In a financial institution, everything
revolves around a ledger which is a core element to all processes.
Often, the cause of reconciliation issues, delays, risks, and
failures is the absence of a central ledger system with multiple
sub-ledgers that can work together in a homogenous platform.
Even if there is a central ledger system requiring sub-ledgers to
Figure 5. An IRS agreement with the quantitative
Figure 6. Interest Rate Swap on the blockchain.
individually update the central ledger, it can be an integration
nightmare, usually causing more issues.
Identifying the root cause of these problems and providing the
necessary platform not only takes away much of the risks and
problems, but will also allow financial institutions to take on new
and more complicated service offerings that have otherwise been
too costly to do.
The NEM technology solves that issue and the design guarantees
absolute finality and integrity of transactions that are immutable
and irreversible. Any reversal of transaction can only be done by
an opposing transaction, and which can be controlled with a full
audit trail.
The existence of API server gateways enable the blockchain to act
as a core to applications that require the use of a ledger. It is
therefore, an open system and allows for standard conforming
applications, including legacy and new decentralised smart
contracts to integrate with the ledger seamlessly.
The design of Catapult is premised on a single private blockchain
for each entity or financial institution. There is a parallel project
within the NEM initiative to develop a special routing system to
allow interoperability across entities using a common shared
ledger system. This common shared ledger system brings out the
power of the NEM blockchain technology and enables seamless
transactions, thereby disintermediating the need to have multihop
settlement and payment systems. It opens up a new
dimension where payments are straight through transactions
from account to account with minimal messaging.
The option of each financial institution being able to operate its
own single private blockchain allows privacy of data to be
confined to the financial institution. The existence of a shared
ledger system allows financial institutions interoperability so
that they can settle and make payments with one another
In fact, the shared ledger system can stand on its own, offering a
seamless solution that does not require any bank to own a private
blockchain to be able to participate. It is, after all, a ledger of
records and transactions, allowing for settlements and payments.

4 Dragonfly Fintech is the developer for the homogenous cross-chain
interoperability solution to link multiple instances of blockchains together.
It calls on a slightly different set of rules, away from traditional
methods of settlement and payment. Additionally, it conforms to
regulatory frameworks that are put in place today.
It can be seen that the NEM blockchain technology is an offering
that helps in the transition of financial institutions from using
traditional solutions into one that is powered by the blockchain
The NEM project team strongly believes this is the way forward
for transitioning. It gives rise to a low entry barrier for financial
institutions to embrace the blockchain technology while at the
same time, it also allows a financial institution to work on the
blockchain technology and be familiar with it.
The Catapult project is in its late stage development. It shall be
released in multiple stages where the features highlighted in
section 4.1 will be added on at each stage. It is scheduled for its
first release in Q1, 2017. The enhancements of the solution are
unique and powerful, setting a new standard in blockchain
Its powerful abstraction layer makes it agnostic to existing
banking standards, the intent of which is not to disrupt currently
installed solutions, but instead to dovetail into these existing
systems seamlessly. Current systems running standards
complying solutions - such as FpML and ISO20022 –will only
need to make use of the outputs to integrate with the blockchain
via the abstraction layer. This method of deployment allows
financial institutions to migrate their systems in a timeframe that
better suit their business operations – as soon as they minimise
their need for some of these standards – into the blockchain
platform. At the same time, the Catapult solution can then be
used by financial institutions to enable growth, expansion, and
creation of new products, leveraging on the use of the blockchain
for faster and inexpensive deployment.
Catapult is a uniquely positioned solution and is a second
iteration of its first solution, Mijin. Most other projects are
derivatives and add-ons to existing blockchain solutions, which
makes it rather clumsy as a holistic offering.
We present here 3 initiatives that may be relevant to what the
NEM project is working on. While Ethereum and Bitcoin are in
production phase, Corda is still in the conceptual stage at the
time of writing.
This project premise on a virtual machine, having its own
programming language to run smart contracts that are loaded
onto the blockchain. A smart contract once loaded onto the
blockchain, is immutable and irreversible, and the ramifications
can be severe if there is a bug. Additionally, it often relies on
external data known as oracles, to feed inputs into the program
to change its state. These changed states are written onto the
blockchain storage.
Our solution has no smart contracts as we are of the opinion that
this should be left to the bank to decide how they will want to
incorporate that as a separate exercise. In a way, we are
optimising the blockchain to do exactly what it is designed for,
i.e., a ledger solution, and a multi-ledger solution at that with lots
more features that are not only suited for the financial industry
but generic enough to suit a spectrum of applications outside the
financial industry. In a way, we have also built some smarts into
the blockchain that can be used readily, with certainty and more
often used. These include our multisig solution and the smart
escrow solution where there is no need for a third party to
facilitate a transfer. This smart escrow solution is based on two
parties signing off before assets can be exchanged. If either party
does not sign, there shall be no exchange of assets.
The very existence of smart contracts in an immutable and
irreversible state can only lead to much resources wasted on the
deployment of it, especially if it needs to be 100% full proof and
tested. This is never usually the case in any software solution
project. The more complicated the project is, the more prone it is

5 https://www.ethereum.org/
to have bugs. A slight mistake can result in a systemic failure, and
no financial institution should even consider that as a possibility.
Square pegs will never fit perfectly into a round hole. Having a
smart contract on a blockchain is one such example. As it is now,
most financial institutions already have well defined centralised
smart contracts that they have been using for years. These are all
controlled and they can be stopped, corrected of bugs, and run
again. Outputs are final and definite. Any such bilateral or
multilateral contract is cross-verified between multiple parties. A
smart contract on blockchain is not possible to do that, i.e., the
smart contract cannot be replaced with another program after
being put onto the blockchain.
A smart contract cannot work in isolation. It still relies on
external inputs or oracles. It cannot execute in a void and reliance
on third party input has a trust issue, which in the first place is
meant to be trustless. It is a paradox because the main value
proposition of a decentralised smart contract solution was to be
a trustless smart contract platform, which is not possible. In fact,
having smart contracts in a blockchain could increase the cost of
implementation exponentially. The end does not seem to justify
the means.
Bitcoin is a blockchain project and is a proof of concept on the
use of a decentralised blockchain to manage transactions.
Catapult has the same end point objective of hashing and storing
transactions on the blockchain, like the Bitcoin project. In fact,
most blockchain projects follow this same principle
Where NEM differs is the method of competing for the right to
create blocks of data onto the blockchain. Other differences are:
 System Architecture – NEM is much more scalable
NEM does not have unspent transaction output (UXTO).
It follows the standard ledger convention of using an
account with multiple balances of assets - multiple ledgers
in one account - inside it. All inputs and outputs go
through this single account.
 Business logic – Bitcoin is a plain ledger. For example,
NEM has on-chain signing of transactions - do not rely on
additional centralised servers to queue transactions for

6 https://bitcoin.org/en/
signing before broadcasting onto the blockchain - which
gives it a very powerful utility.
 Bitcoin does not have an inherent, purpose built multiple
ledger solution
 Bitcoin does not have a node reputation management
solution as part of its core offering
Most of Bitcoin offerings are workarounds patched on
solutions that require dependent third party providers,
thus introducing another layer of concern for service level
and quality dependence, security, performance, and
 Machine competition – Bitcoin is designed with mining in
mind. They have proof-of-work as a necessary element to
secure the blockchain. For a permissioned blockchain
solution, there is no need to compete in order to mine a
block. NEM’s approach has been a simple and yet very
powerful way of securing the blockchain, requiring much
less computing and energy resources to manage and
maintain it.
 Transaction throughputs of Bitcoin are too low to be
practical for a financial application. Their transaction rate
per second is single digit in magnitude. NEM’s Catapult
transaction rates are 4-figure.
 Bitcoin confirmation time takes too long and is not
suitable for the financial industry.
6.3. CORDA7
Corda is in concept stage and it appears that they are following
the route of Ethereum with some subtle differences in the way
they manage oracles and having stateless functions in a shareable
ledger. They are proposing to use Java Virtual Machine to
develop their solution. If at all, it appears that NEM could use the
outcomes of these smart contracts to drive processes and outputs
into the Catapult ledger system.

7 https://r3cev.com/blog/2016/8/24/the-corda-non-technical-whitepaper

Accelerating Bliss: the geometry of ternary polynomials
L´eo Ducas
University of California, San Diego
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
[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.
IEEE Std 1363.1 and standard X9.98.
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
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
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) ≈

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
, 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
, 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.
the choice of σ is determined by security constraints, which we won’t discuss in this paper.
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
, 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
κ denotes the set of vectors of n
binary coordinates with exactly κ coordinates set to 1: B
κ = {c ∈ B
|kck1 = κ}. For such binary
vectors c ∈ B
, 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
, where each ring element a = a0+a1x+. . .+an−1x
n−1 ∈ R is associated
with the coefficient vector a = (a0, . . . , an−1) ∈ Z
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.
Prover Verifier
Secret Key S ∈ R2×1
, short A · S = q mod 2q A = [a, q − 2] ∈ R1×2
(S ∈ Z
) (A ∈ Z
Sample y ← D2n
Compute u = A · y mod q
u −−−−→
c ←−−−− Sample c ∈ B
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 σ
· Id
in dimension 2n.
The repetition rate is set to M = e
) and the correctness of the rejection sampling (which
is required by the security proof) is ensured if for all challenges c ∈ B
, σ ≥ α · 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
· S. The bound used in Bliss follows
from rewriting
2 = c
tGc =
(we recall that Ic is the indicator set of c, defined by Ic = {i|ci = 1}). Such sum can be bounded
independently of c :
2 ≤ Nκ(S) where Nκ(S) = max

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
κ = B
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
· 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
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)κ + κ

nδ · ω(
log n)
with overwhelming probability. Note that the only constraint on κ is that c ← B
κ 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
is less than kak
2 + kbk
. 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
Output: v = Sc0
for some c
0 ≡ c mod 2 such that kSc0k
2 ≤ kSk
· kck
2 = kSk
· κ.
1: v ← 0 ∈ Z
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
the algorithm outputs v = GreedySC(S, c) such that v = Sc0
for some ternary vector c
0 ≡ c mod 2
2 ≤ kSk
· kck
2 = kSk
· κ.
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
k = −
· ei (ei ∈ Z
n being the i-th canonical unit vector).
We will prove the following invariant: c
is a ternary vector such that Ic
= Jk and vk = S · c
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:
2 ≤ kvkk
2 + ksik
2 ≤ kSk
· k + kSk
2 ≤ kSk
· (k + 1).
We conclude that the output v = vκ = Sc0
κ verifies kvk
2 ≤ kSk
· κ and that c
0 = c
is a ternary
vector verifying Ic
0 = Ic.
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
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

κ. 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.
Algorithm 2: Modified Bliss Signature Algorithm
Input: Message µ, public key A = (a1, q − 2) ∈ R1×2
, secret key S = (s1, s2)
t ∈ R2×1
Output: A signature (z1, z

, 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


hz , vi
otherwise restart
8: z

2 ← (bued − bu − z2ed) mod p
9: Output (z1, z

, 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α
)). 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
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).
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.
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.
[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.
[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
[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,
[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.
[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/
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: S = (s1, s2)
t ← (f, 2g + 1)t // Implicitly defining the set S0
3: if Nκ(S) ≥ C
· 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
, secret key S = (s1, s2)
t ∈ R2×1
Output: A signature (z1, z

, c) of the message µ
1: y1, y2 ← DZn,σ
3: c ← H(bued mod p, µ)
4: Choose a random bit b
5: z1 ← y1 + (−1)b
s1c; z2 ← y2 + (−1)b
6: Continue with probability 1. M exp


hz , Sci
otherwise restart
7: z

2 ← (bued − bu − z2ed) mod p
8: Output (z1, z

, c)
Algorithm 5: Bliss Verification Algorithm
, signature (z1, z

, c)
Output: Accept or Reject the signature
1: if k(z1|2
· z

)k2 > B2 then Reject
2: if k(z1|2
· z

)k∞ > B∞ then Reject
3: Accept iff c = H
· a1 · z1 + ζ · q · c

+ z

2 mod p, µ)
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
κ 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






実力で勝負できる #NEM #XSH はこれからも集めねば。