## CryptoDB

### Ventzislav Nikov

#### 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.

2016

ASIACRYPT

2012

ASIACRYPT

2008

EPRINT

Yet Another Secure Distance-Bounding Protocol
Abstract

Distance-bounding protocols have been proposed by Brands and Chaum in 1993
in order to detect \emph{relay attacks}, also known as \emph{mafia fraud}.
Although the idea has been introduced fifteen years ago, only recently distance-bounding protocols
attracted the attention of the researchers.
Several new protocols have been proposed the last five years.
In this paper, a new secure distance-bounding protocol is presented. It is self-contained and composable
with other protocols for example for authentication or key-negotiation. It allows periodically execution
and achieves better use of the communication channels by exchanging authenticated nonces.
The proposed protocol becomes suitable for wider class of devices, since the resource
requirements to the prover are relaxed.

2006

EPRINT

A DoS Attack Against the Integrity-Less ESP (IPSec)
Abstract

This paper describes a new practical DoS attack that can be mounted
against the ``encryption-only'' configuration (i.e. without
authenticated integrity) of ESP as allowed by IPSec.
This finding can serve as a strong argument to convince those in
charge of the IPSec standardization to improve it by banning the
``encryption-only'' configuration from the standard.

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.

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.

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

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).

#### Coauthors

- Victor Arribas (2)
- Begül Bilgin (4)
- Julia Borghoff (1)
- An Braeken (3)
- Anne Canteaut (1)
- Thomas De Cnudde (1)
- Lauren De Meyer (2)
- Martin Feldhofer (1)
- Benedikt Gierlichs (1)
- Tim Güneysu (1)
- Elif Bilge Kavun (1)
- Miroslav Knezevic (2)
- Lars R. Knudsen (1)
- Gregor Leander (1)
- Marcel Medwed (1)
- Svetla Nikova (15)
- Christof Paar (1)
- Bart Preneel (6)
- Christian Rechberger (1)
- Oscar Reparaz (2)
- Vincent Rijmen (4)
- Peter Rombouts (2)
- Nigel P. Smart (1)
- François-Xavier Standaert (1)
- Georg Stütz (1)
- Søren S. Thomsen (1)
- Joos Vandewalle (2)
- Marc Vauclair (1)
- Tolga Yalçin (1)