## CryptoDB

### Svetla Nikova

#### Affiliation: KU Leuven, Belgium

#### Publications

**Year**

**Venue**

**Title**

2019

TCHES

M&M: Masks and Macs against Physical Attacks
Abstract

Cryptographic implementations on embedded systems need to be protected against physical attacks. Today, this means that apart from incorporating countermeasures against side-channel analysis, implementations must also withstand fault attacks and combined attacks. Recent proposals in this area have shown that there is a big tradeoff between the implementation cost and the strength of the adversary model. In this work, we introduce a new combined countermeasure M&M that combines Masking with information-theoretic MAC tags and infective computation. It works in a stronger adversary model than the existing scheme ParTI, yet is a lot less costly to implement than the provably secure MPC-based scheme CAPA. We demonstrate M&M with a SCA- and DFA-secure implementation of the AES block cipher. We evaluate the side-channel leakage of the second-order secure design with a non-specific t-test and use simulation to validate the fault resistance.

2018

CRYPTO

CAPA: The Spirit of Beaver Against Physical Attacks
📺
Abstract

In this paper we introduce two things: On one hand we introduce the Tile-Probe-and-Fault model, a model generalising the wire-probe model of Ishai et al. extending it to cover both more realistic side-channel leakage scenarios on a chip and also to cover fault and combined attacks. Secondly we introduce CAPA: a combined Countermeasure Against Physical Attacks. Our countermeasure is motivated by our model, and aims to provide security against higher-order SCA, multiple-shot FA and combined attacks. The tile-probe-and-fault model leads one to naturally look (by analogy) at actively secure multi-party computation protocols. Indeed, CAPA draws much inspiration from the MPC protocol SPDZ. So as to demonstrate that the model, and the CAPA countermeasure, are not just theoretical constructions, but could also serve to build practical countermeasures, we present initial experiments of proof-of-concept designs using the CAPA methodology. Namely, a hardware implementation of the KATAN and AES block ciphers, as well as a software bitsliced AES S-box implementation. We demonstrate experimentally that the design can resist second-order DPA attacks, even when the attacker is presented with many hundreds of thousands of traces. In addition our proof-of-concept can also detect faults within our model with high probability in accordance to the methodology.

2018

TCHES

Rhythmic Keccak: SCA Security and Low Latency in HW
📺
Abstract

Glitches entail a great issue when securing a cryptographic implementation in hardware. Several masking schemes have been proposed in the literature that provide security even in the presence of glitches. The key property that allows this protection was introduced in threshold implementations as non-completeness. We address crucial points to ensure the right compliance of this property especially for low-latency implementations. Specifically, we first discuss the existence of a flaw in DSD 2017 implementation of Keccak by Gross et al. in violation of the non-completeness property and propose a solution. We perform a side-channel evaluation on the first-order and second-order implementations of the proposed design where no leakage is detected with up to 55 million traces. Then, we present a method to ensure a non-complete scheme of an unrolled implementation applicable to any order of security or algebraic degree of the shared function. By using this method we design a two-rounds unrolled first-order Keccak-

2015

EPRINT

2007

EPRINT

On Asymptotic Behavior of the Ratio Between the Numbers of Binary Primitive and Irreducible Polynomials
Abstract

In this paper we study the ratio $\theta(n) = \frac{\lambda_2(n)}{\psi_2(n)}$,
where ${\lambda_2(n)}$ is the number of primitive polynomials and
${\psi_2(n)}$ is the number of irreducible polynomials in
$GF(2)[x]$ of degree $n$. %and $2n$, for an arbitrary odd number $n$.
Let $n=\prod_{i=1}^{\ell} p_i^{r_i}$ be the prime factorization of $n$, where $p_i$ are odd primes.
We show that $\theta(n)$ tends to 1 and $\theta(2n)$ is asymptotically
not less than 2/3 when $r_i$ are fixed and $p_i$ tend to infinity. We also, describe an infinite
series of values $n_{s}$ such that $\theta(n_{s})$ is strictly
less than $\frac{1}{2}$.

2006

EPRINT

A Weakness in Some Oblivious Transfer and Zero-Knowledge Protocols
Abstract

We consider oblivious transfer protocols and their applications that
use underneath semantically secure homomorphic encryption scheme
(e.g. Paillier's). We show that some oblivious transfer protocols
and their derivatives such as private matching, oblivious polynomial
evaluation and private shared scalar product could be subject to an
attack. The same attack can be applied to some non-interactive
zero-knowledge arguments which use homomorphic encryption schemes
underneath. The roots of our attack lie in the additional property
that some semantically secure encryption schemes possess, namely,
the decryption also reveals the random coin used for the encryption,
and that the (sender's or prover's) inputs may belong to a space,
that is very small compared to the plaintext space. In this case it
appears that even a semi-honest chooser (verifier) can derive from
the random coin bounds for all or some of the sender's (prover's)
private inputs with non-negligible probability. We propose a fix
which precludes the attacks.

2006

EPRINT

On Zigzag Functions and Related Objects in New Metric
Abstract

In \cite{BCS96}, the concept of zigzag function was introduced in
relation with oblivious transfer \cite{R84}. This subject has
later been studied in \cite{S99,DS01,CFW01}. The definition
of zigzag functions has been generalized to $s$-zigzag functions for
$2\leq s\leq n$. It turns out that zigzag functions are also interesting
combinatorial objects, thanks to their relation with self-intersecting codes and
orthogonal arrays \cite{BCS96,S99}.
The aim of this work is to formulate these objects with respect to a new metric
following the approach proposed in \cite{BNNP} and to investigate the properties
of the generalized zigzag functions and related concepts.

2005

EPRINT

Classification of Cubic $(n-4)$-resilient Boolean Functions
Abstract

Carlet and Charpin classified in \cite{CC04} the set of cubic $(n-4)$-resilient Boolean functions into four different types with respect to the Walsh spectrum and the dimension of the linear space. Based on the classification of $RM(3,6)/RM(1,6)$, we completed the classification of the cubic $(n-4)$-resilient Boolean function by deriving the corresponding ANF and autocorrelation spectrum for each of the four types. In the same time, we solved an open problem of \cite{CC04} by proving that all plateaued cubic $(n-4)$-resilient Boolean functions have dimension of the linear space equal either to $n-5$ or $n-6$.

2004

EPRINT

On Cheating Immune Secret Sharing
Abstract

This work addresses the problem of cheating prevention in secret sharing. The scheme is said to be $k$-cheating immune if any group of $k$ cheaters has no advantage over honest participants. In this paper we study the constraints of cheating immune secret sharing schemes. We give a necessary and sufficient condition for SSSs to be cheating immune. Then, we improve the upper bound of D'Arco {\textit et.~al} on the number of cheaters tolerated in such scheme. Our proof is much simpler than the proof of D'Arco {\textit et.~al} and relies on certain properties of cryptographic Boolean functions. As a result of independent interest we provide a condition given function to be $t$-resilient and to satisfy the propagation criterion of degree $\ell$ over any finite field.

2004

EPRINT

Covering Radius of the $(n-3)$-rd Order Reed-Muller Code in the Set of Resilient Functions
Abstract

In this paper, we continue the study of the covering
radius in the set of resilient functions, which has been defined by Kurosawa. This new concept is meaningful to cryptography especially in the context of the new class of algebraic attacks on stream ciphers proposed by Courtois and Meier at Eurocrypt 2003 and Courtois at Crypto 2003. In order to resist such attacks the combining Boolean function should be at high distance from lower degree functions.
Using a result from coding theory on the covering radius of
$(n-3)$-rd Reed-Muller codes, we establish exact values of the
the covering radius of $RM(n-3,n)$ in the set of $1$-resilient Boolean
functions of $n$ variables, when $\lfloor n/2 \rfloor = 1 \mod\;2$. We also improve the lower bounds for covering radius of the Reed-Muller
codes $RM(r,n)$ in the set of $t$-resilient functions, where
$\lceil r/2 \rceil = 0 \mod\;2$, $t \leq n-r-2$ and $n\geq r+3$.

2004

EPRINT

Classification of Boolean Functions of 6 Variables or Less with Respect to Cryptographic Properties
Abstract

This paper presents an efficient approach for classification of
the affine equivalence classes of cosets of the first order
Reed-Muller code with respect to cryptographic properties such as
correlation-immunity, resiliency and propagation characteristics.
First, we apply the method to completely classify all the $48$
classes into which the general affine group $AGL(2,5)$ partitions
the cosets of $RM(1,5)$. Second, we describe how to find the affine
equivalence classes together with their sizes of Boolean functions in 6 variables.
We perform the same classification for these classes. Moreover, we
also determine the classification of $RM(3,7)/RM(1,7)$.
We also study the algebraic immunity of the corresponding affine equivalence classes.
Moreover, several relations are derived between the algebraic immunity
and other cryptographic properties.
Finally, we introduce two new indicators which can be used to distinguish
affine inequivalent Boolean functions when the known criteria are
not sufficient. From these indicators a method can be derived for
finding the affine relation between two functions (if such
exists). The efficiency of the method depends on the structure of
the Walsh or autocorrelation spectrum.

2004

EPRINT

On Boolean Functions with Generalized Cryptographic Properties
Abstract

By considering a new metric, we generalize cryptographic
properties of Boolean functions such as resiliency and propagation
characteristics. These new definitions result in a better understanding
of the properties of Boolean functions and provide a better insight in
the space defined by this metric. This approach leads to the
construction of ``hand-made'' Boolean functions, i.e., functions for
which the security with respect to some specific monotone sets of inputs
is considered, instead of the security with respect to all possible
monotone sets with the same cardinality, as in the usual definitions.
This approach has the advantage that some trade-offs between important
properties of Boolean functions can be relaxed.

2004

EPRINT

New Monotone Span Programs from Old
Abstract

In this paper we provide several known and one new constructions of new
linear secret sharing schemes (LSSS) from existing ones.
This constructions are well-suited for didactic purposes, which is a main
goal of this paper. It is well known that LSSS are in one-to-one correspondence with monotone span programs (MSPs).
MSPs introduced by Karchmer and Wigderson, can be viewed as a linear algebra model for computing a monotone function (access structure).
Thus the focus is in obtaining a MSP computing the new access
structure starting from the MSPs that compute the existing ones,
in the way that the size of the MSP after the transformation is well defined.
Next we define certain new operations on access structures and prove certain related
properties.

2003

EPRINT

Multi-Party Computation from any Linear Secret Sharing Scheme Secure against Adaptive Adversary: The Zero-Error Case
Abstract

We use a general treatment of both information-theoretic and cryptographic settings for
Multi-Party Computation (MPC), based on the underlying linear secret sharing scheme.
Our goal is to study the Monotone Span Program (MSP), which is the result of local multiplication
of shares distributed by two given MSPs as well as the access structure that this resulting MSP computes.
First, we expand the construction proposed by Cramer et~al. multiplying two different general access structures
and we prove some properties of the resulting MSP ${\cal M}$.
Next we expand the definition of multiplicative MSPs and we prove that when one uses dual MSPs only all players together can compute the product, i.e., the construction proposed by Cramer et~al. gives only multiplicative MPC.
Third, we propose a solution for the strongly multiplicative MPC (in presence of adversary).
The knowledge of the resulting MSP and the access structure it computes allows us to build an analog
of the algebraic simplification protocol of Gennaro et~al.
We show how to achieve in the computational model MPC secure against adaptive adversary in the zero-error case,
through the application of homomorphic commitments.
There is an open problem how efficiently we can determine $\Gamma$ the access structure of the resulting MSP
${\cal M}$. This open problem reflects negatively on the efficiency of the proposed solution.

2003

EPRINT

On a Relation Between Verifiable Secret Sharing Schemes and a Class of Error-Correcting Codes
Abstract

In this paper we try to shed a new insight on Verifiable Secret
Sharing Schemes (VSS). We first define a new ``metric" (with slightly
different properties than the standard Hamming metric). Using
this metric we define a very particular class of codes that we call
{\it error-set correcting codes}, based on a set of forbidden distances which is a
monotone decreasing set. Next we redefine the packing problem for the new
settings and generalize the notion of error-correcting capability of the
error-set correcting codes accordingly (taking into account the new metric and the
new packing). Then we consider burst-error interleaving codes
proposing an efficient burst-error correcting technique, which is in fact the well
known VSS and Distributed Commitments (DC) pair-wise checking protocol and we prove
the error-correcting capability of the error-set correcting interleaving codes.
Using the known relationship, due to Van Dijk, between a Monotone
Span Program (MSP) and a generator matrix of the code generated by
the suitable set of vectors, we prove that the error-set
correcting codes in fact has the allowed (opposite to forbidden)
distances of the dual access structure of the access structure
that the MSP computes. We give an efficient construction for them
based on this relation and as a consequence we establish a link
between Secret Sharing Schemes (SSS) and the error-set correcting
codes.
Further we give a necessary and sufficient condition for the existence
of linear SSS (LSSS), to be secure against $(\Delta,\Delta_A)$-adversary
expressed in terms of an error-set correcting code. Finally, we present necessary
and sufficient conditions for the existence of a VSS scheme,
based on an error-set correcting code, secure against $(\Delta,\Delta_A)$-adversary.
Our approach is general and covers all known linear VSS/DC. It allows
us to establish the minimal conditions for security of VSSs. Our
main theorem states that the security of a scheme is equivalent to
a pure geometrical (coding) condition on the linear mappings describing
the scheme. Hence the security of all known schemes, e.g. all known bounds
for existence of unconditionally secure VSS/DC including the recent result of
Fehr and Maurer, can be expressed as certain (geometrical) coding conditions.

2002

EPRINT

Applying General Access Structure to Metering Schemes
Abstract

In order to decide on advertisement fees for web servers, Naor and Pinkas introduced metering schemes secure against coalition of corrupt servers and clients. In their schemes any server is able to construct a proof to be sent to an audit agency if and only if it has been
visited by at least a certain number of clients. Several researchers have generalized the idea of Naor and Pinkas: first metering scheme with pricing and dynamic multi-threshold metering schemes have been proposed; later the solution has been extended to allow for
general access structures and an approach on linear algebra has been introduced. In this paper we are interested in the efficiency of applying general access structures and linear algebra techniques to metering schemes. We propose a new model considering general access structures for clients, corrupted clients and servers. Then we bind the
access structures for clients and corrupted clients into one. We propose a new metering scheme, which is more efficient w.r.t.\ communication complexity and memory requirements than the scheme of Blundo \textit{et al.}

2002

EPRINT

Applying General Access Structure to Proactive Secret Sharing Schemes
Abstract

Verifiable secret sharing schemes (VSS) are secret sharing schemes (SSS) dealing with possible cheating by participants. In this paper we use the VSS proposed by Cramer, Damgard and Maurer \cite{CDM99,CDM00,Cra00}.
They introduced a purely linear algebraic method to transform monotone span program (MSP) based secret sharing schemes into VSS. In fact, the
monotone span program model of Karchmer and Wigderson \cite{KW93} deals with arbitrary monotone access structures and not just threshold ones. Stinson and Wei \cite{SW99} proposed a proactive SSS based on threshold (polynomial) VSS. The purpose of this paper is to build unconditionally secure proactive SSS over any access structure, as long as it admits a linear secret sharing scheme (LSSS).

#### Program Committees

- Crypto 2019
- Asiacrypt 2019
- Eurocrypt 2019
- Eurocrypt 2018
- Asiacrypt 2018
- Eurocrypt 2016
- FSE 2016
- Asiacrypt 2016
- FSE 2015
- FSE 2014

#### Coauthors

- Sergey Agievich (1)
- Victor Arribas (3)
- Begül Bilgin (7)
- Yuri Borissov (4)
- An Braeken (6)
- Thomas De Cnudde (1)
- Lauren De Meyer (2)
- Benedikt Gierlichs (3)
- Anastasiya Gorodilova (1)
- Nikolay Kolomeec (1)
- Moon Ho Lee (1)
- Ventzislav Nikov (15)
- George Petrides (1)
- Bart Preneel (9)
- Oscar Reparaz (4)
- Vincent Rijmen (7)
- Martin Schläffer (1)
- George Shushuev (1)
- Nigel P. Smart (1)
- Georg Stütz (1)
- Natalia Tokareva (1)
- Joos Vandewalle (2)
- Ingrid Verbauwhede (2)
- Valeriya Vitkup (1)