International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Svetla Nikova

Affiliation: KU Leuven, Belgium

Publications

Year
Venue
Title
2019
TCHES
M&M: Masks and Macs against Physical Attacks
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 📺
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 📺
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-
2016
CHES
2015
EPRINT
2015
EPRINT
2015
CRYPTO
2014
ASIACRYPT
2012
CHES
2011
JOFC
2007
EPRINT
On Asymptotic Behavior of the Ratio Between the Numbers of Binary Primitive and Irreducible Polynomials
Yuri Borissov Moon Ho Lee Svetla Nikova
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
ASIACRYPT
2006
EPRINT
A Weakness in Some Oblivious Transfer and Zero-Knowledge Protocols
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
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
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
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
Yuri Borissov An Braeken Svetla Nikova
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
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
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
Ventzislav Nikov Svetla Nikova
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
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
Ventzislav Nikov Svetla Nikova
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
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
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