## CryptoDB

### Roberto Maria Avanzi

#### Publications

**Year**

**Venue**

**Title**

2017

TOSC

The QARMA Block Cipher Family. Almost MDS Matrices Over Rings With Zero Divisors, Nearly Symmetric Even-Mansour Constructions With Non-Involutory Central Rounds, and Search Heuristics for Low-Latency S-Boxes
Abstract

This paper introduces QARMA, a new family of lightweight tweakable block ciphers targeted at applications such as memory encryption, the generation of very short tags for hardware-assisted prevention of software exploitation, and the construction of keyed hash functions. QARMA is inspired by reflection ciphers such as PRINCE, to which it adds a tweaking input, and MANTIS. However, QARMA differs from previous reflector constructions in that it is a three-round Even-Mansour scheme instead of a FX-construction, and its middle permutation is non-involutory and keyed. We introduce and analyse a family of Almost MDS matrices defined over a ring with zero divisors that allows us to encode rotations in its operation while maintaining the minimal latency associated to {0, 1}-matrices. The purpose of all these design choices is to harden the cipher against various classes of attacks. We also describe new S-Box search heuristics aimed at minimising the critical path. QARMA exists in 64- and 128-bit block sizes, where block and tweak size are equal, and keys are twice as long as the blocks. We argue that QARMA provides sufficient security margins within the constraints determined by the mentioned applications, while still achieving best-in-class latency. Implementation results on a state-of-the art manufacturing process are reported. Finally, we propose a technique to extend the length of the tweak by using, for instance, a universal hash function, which can also be used to strengthen the security of QARMA.

2011

PKC

2010

EPRINT

Arithmetic of Supersingular Koblitz Curves in Characteristic Three
Abstract

We consider digital expansions of scalars for supersingular
Koblitz curves in characteristic three. These are positional
representations of integers to the base of $\tau$,
where $\tau$ is a zero of the characteristic polynomial $T^2 \pm 3\,T + 3$ of
a Frobenius endomorphism.
They are then applied to the improvement of scalar multiplication on the
Koblitz curves.
A simple connection between $\tau$-adic expansions and balanced
ternary representations is given.
Windowed non-adjacent representations are considered whereby the digits are elements of minimal norm.
We give an explicit description of the elements of the digit set, allowing for a very simple and efficient precomputation strategy, whereby the rotational symmetry of the digit set is also used to reduce the memory requirements.
With respect to the current state of the art for computing scalar multiplications on supersingular Koblitz curves we achieve the following improvements:
\rm{(i)} speed-ups of up to 40\%,
\rm{(ii)} a reduction of memory consumption by a factor of three,
\rm{(iii)} our methods apply to all window sizes without requiring operation sequences for
the precomputation stage to be determined offline first.
Additionally, we explicitly describe the action of some endomorphisms on the Koblitz curve as a scalar multiplication by an explicitly given integer.

2008

EPRINT

Redundant $\tau$-adic Expansions I: Non-Adjacent Digit Sets and their Applications to Scalar Multiplication
Abstract

This paper investigates some properties of $\tau$-adic expansions of
scalars. Such expansions are widely used in the design of scalar
multiplication algorithms on Koblitz Curves, but at the same
time they are much less understood than their binary counterparts.
Solinas introduced the width-$w$ $\tau$-adic non-adjacent form for
use with Koblitz curves. This is an expansion of integers
$z=\sum_{i=0}^\ell z_i\tau^i$, where $\tau$ is
a quadratic integer depending on the curve, such that $z_i\ne 0$
implies $z_{w+i-1}=\ldots=z_{i+1}=0$,
like the sliding window binary recodings of integers.
It uses a redundant digit set, i.e., an expansion of an integer using
this digit set need not be uniquely determined if the
syntactical constraints are not enforced.
We show that the digit sets described by Solinas, formed by elements
of minimal norm in their residue classes, are uniquely determined.
Apart from this digit set of minimal norm representatives, other digit sets
can be chosen such that all integers can be represented by a width-$w$
non-adjacent form using those digits. We describe an algorithm
recognizing admissible digit sets.
Results by Solinas and by Blake, Murty, and Xu are generalized.
In particular, we introduce two new useful families of digit sets.
The first set is syntactically defined.
As a consequence of its adoption we can
also present improved and streamlined algorithms to perform the
precomputations in $\tau$-adic scalar multiplication methods.
The latter use an improvement of the computation of sums and differences of
points on elliptic curves with mixed affine and L\'opez-Dahab
coordinates.
The second set is suitable for low-memory applications, generalizing an approach
started by Avanzi, Ciet, and Sica. It permits to devise a scalar multiplication
algorithm that dispenses with the initial precomputation stage
and its associated memory space. A suitable choice of the parameters of the
method leads to a scalar multiplication algorithm on Koblitz Curves
that achieves sublinear complexity in the number of expensive curve operations.

2007

EPRINT

Another Look at Square Roots and Traces (and Quadratic Equations) in Fields of Even Characteristic
Abstract

We discuss irreducible polynomials that can be
used to speed up square root extraction in fields of characteristic two.
We call such polynomials \textit{square root friendly}.
The obvious applications are to point halving methods for elliptic curves
and divisor halving methods for hyperelliptic curves.
We note the existence of square root friendly trinomials of a given
degree when we already know that an irreducible trinomial of the same
degree exists, and formulate a conjecture on the degrees of the terms of
square root friendly polynomials.
We also give a partial result
that goes in the direction of the conjecture.
Irreducible polynomials $p(X)$ such that the square root
$\zeta$ of a zero $x$ of $p(X)$ is a sparse polynomial are considered
and those for which $\zeta$ has minimal degree are characterized.
In doing this we discover a surprising connection
these polynomials
and those defining polynomial bases
with an extremal number of trace one elements.
We also show how to improve the speed of solving quadratic equations and
that the increase in the time required to perform modular reduction is
marginal and does not affect performance adversely.
Experimental results confirm that the new polynomials mantain their
promises; These results generalize work by Fong et al.\ to polynomials
other than trinomials. Point halving gets a speed-up of $20\%$ and the
performance of scalar multiplication based on point halving is improved
by at least $11\%$.

2006

EPRINT

Scalar Multiplication on Koblitz Curves using Double Bases
Abstract

The paper is an examination of double-base decompositions of
integers $n$, namely expansions loosely of the form
$$
n = \sum_{i,j} A^iB^j
$$
for some base $\{A,B\}$. This was examined in previous
works in the case when $A,B$ lie in
$\mathbb{N}$.
On the positive side, we show how to extend previous results
of to Koblitz curves over binary fields. Namely, we
obtain a sublinear scalar algorithm to compute, given a generic
positive integer $n$ and an elliptic curve point $P$, the point $nP$
in time $O\left(\frac{\log n}{\log\log n}\right)$ elliptic curve
operations with essentially no storage, thus making the method
asymptotically faster than any know scalar multiplication algorithm
on Koblitz curves.
On the negative side, we analyze scalar multiplication using double
base numbers and show that on a generic elliptic curve over a finite
field, we cannot expect a sublinear algorithm with double bases. Finally, we show that
all algorithms used hitherto need at least $\frac{\log n}{\log\log
n}$ curve operations.

2005

EPRINT

Side Channel Attacks on Implementations of Curve-Based Cryptographic Primitives
Abstract

The present survey deals with the recent research in side channel
analysis and related attacks on implementations of cryptographic
primitives. The focus is on software contermeasures for primitives
built around algebraic groups. Many countermeasures are described,
together with their extent of applicability, and their weaknesses.
Some suggestions are made, conclusion are drawn, some directions for
future research are given. An extensive bibliography on recent
developments concludes the survey.

2005

EPRINT

Minimality of the Hamming Weight of the \tau-NAF for Koblitz Curves and Improved Combination with Point Halving
Abstract

In order to efficiently perform scalar multiplications on
elliptic Koblitz curves, expansions of the scalar to a
complex base associated with the Frobenius endomorphism
are commonly used. One such expansion is the
$\tau$-adic NAF, introduced by Solinas.
Some properties of this expansion, such as
the average weight, are well known, but in the literature
there is no proof of its {\em optimality},
i.e.~that it always has minimal weight.
In this paper we provide the first proof of this fact.
Point halving, being faster than doubling, is also used to
perform fast scalar multiplications on generic elliptic curves
over binary fields. Since its computation is more expensive
than that of the Frobenius, halving was thought to be
uninteresting for Koblitz curves.
At PKC 2004, Avanzi, Ciet, and Sica combined Frobenius
operations with one point halving to compute scalar
multiplications on Koblitz curves using
on average 14\% less group additions than with the
usual $\tau$-and-add method without increasing memory usage.
The second result of this paper is an improvement over their
expansion, that is simpler to compute, and optimal in a suitable
sense, i.e.\ it has minimal Hamming weight among all $\tau$-adic
expansions with digits $\{0,\pm1\}$
that allow one halving to be inserted in the corresponding scalar
multiplication algorithm.
The resulting scalar multiplication requires on average
25\% less group operations than the Frobenius method, and is thus
12.5\% faster than the previous known combination.

2003

EPRINT

Aspects of Hyperelliptic Curves over Large Prime Fields in Software Implementations
Abstract

This paper presents an implementation of genus 2 and 3
hyperelliptic curves over prime fields, with a comparison with
elliptic curves. To allow a fair comparison, we developed an ad-hoc
arithmetic library, designed to remove most of the overheads that
penalise implementations of curve-based cryptography over prime
fields. These overheads get worse for smaller fields, and thus for
large genera. We also use techniques such as lazy and incomplete
modular reduction, originally developed for performing arithmetic in
field extensions, to reduce the number of modular reductions occurring
in the formulae for the group operations.
The result is that the performance of hyperelliptic curves of genus
2 over prime fields is much closer to the performance of elliptic
curves than previously thought. For groups of 192 and 256 bits the
difference is about 18% and 15% respectively.

2002

EPRINT

On multi-exponentiation in cryptography
Abstract

We describe and analyze new combinations of multi-exponentiation
algorithms with representations of the exponents. We deal mainly but
not exclusively with the case where the inversion of group elements is fast: These methods are most attractive with exponents in the range from 80
to 256 bits, and can also be used for computing single
exponentiations in groups which admit an automorphism satisfying
a monic equation of small degree over the integers.
The choice of suitable exponent representations allows us to match or
improve the running time of the best multi-exponentiation techniques
in the aforementioned range, while keeping the memory
requirements as small as possible. Hence some of the methods
presented here are particularly attractive for deployment in
memory constrained environments such as smart cards.
By construction, such methods provide good resistance
against side channel attacks.
We also describe some applications of these algorithms.

#### Program Committees

- Crypto 2020
- CHES 2018
- CHES 2004

#### Coauthors

- Mathieu Ciet (1)
- Vassil S. Dimitrov (1)
- Christophe Doche (1)
- Johann Großschädl (1)
- Clemens Heuberger (4)
- Helmut Prodinger (3)
- Erkay Savas (1)
- Francesco Sica (3)
- Stefan Tillich (1)