# ■

1

NEM CATAPULT

LON WONG

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.

2

Table of Contents

1. Introduction..........................................................................3

2. Relevance ..............................................................................3

3. Goals......................................................................................5

4. Catapult.................................................................................7

4.1. Feature Highlights ..........................................................7

4.2. Consensus ...................................................................... 9

4.3. Perspective - Use Cases.................................................10

4.3.1. Mutual Fund – Transfer Agent ..........................10

4.3.2. Interest Rate Swap Arrangement.......................12

4.4. Extensions..................................................................... 13

5. Summary ............................................................................. 15

6. Other initiatives - A Comparison........................................16

6.1. Ethereum ......................................................................16

6.2. Bitcoin........................................................................... 17

6.3. Corda.............................................................................18

3

1. INTRODUCTION

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.

2. RELEVANCE

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.

4

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

transactions.

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

switching.

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

5

systems within financial institutions contribute much to the

operational risks and inefficiencies that we are witnessing today.

3. GOALS

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

complicated.

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.

6

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

frictionless.

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.

7

4. CATAPULT

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

blockchain.

4.1. FEATURE HIGHLIGHTS

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

include:

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

architecture

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

second)

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.

8

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

transactions

Freezing accounts

Transaction reversal with full audit trail and

accountability

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

9

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

system.

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

systems.

4.2. CONSENSUS

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

10

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.

4.3. PERSPECTIVE - USE CASES

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

solutions.

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.

11

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

expensive.

Figure 4. The asset certificate is translated into an asset and is

configured into the blockchain.

12

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

irreversible.

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.

13

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.

4.4.EXTENSIONS

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

outcome.

Figure 6. Interest Rate Swap on the blockchain.

14

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

4

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

seamlessly.

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.

15

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

technology.

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.

5. SUMMARY

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

design.

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.

16

6. OTHER INITIATIVES - A COMPARISON

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.

6.1. ETHEREUM5

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/

17

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.

6.2.BITCOIN6

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/

18

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

reliability.

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

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

# XSHの絶対あげさせないマン

シールドのこの謎の売り圧は何なんだろうか🤔

— ゆずぴ@復活のY🛡 XEM☆XSH (@yzmkyu1) 2018年4月9日

それに対して1歩も退かないのは感心するけどもね。

どういう意図があるのかなぁってずっと気になってる。蓋をして時を待ってるという気がしてならん。

普通に考えて売りさばける量じゃないからさ#シールド #XSH $XSH pic.twitter.com/Vi1S8MqCxb

見せ板は買い集めている証拠

嬉しいですね。

買い集めて正解ってこと。（個人的ｗ

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

テックビューロも止まってるわけではないので、

時期を見た一斉放出が楽しみで仕方ない。