International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Frederik Vercauteren

Affiliation: KU Leuven

Publications

Year
Venue
Title
2019
PKC
Decryption Failure Attacks on IND-CCA Secure Lattice-Based Schemes
In this paper we investigate the impact of decryption failures on the chosen-ciphertext security of lattice-based primitives. We discuss a generic framework for secret key recovery based on decryption failures and present an attack on the NIST Post-Quantum Proposal ss-ntru-pke. Our framework is split in three parts: First, we use a technique to increase the failure rate of lattice-based schemes called failure boosting. Based on this technique we investigate the minimal effort for an adversary to obtain a failure in three cases: when he has access to a quantum computer, when he mounts a multi-target attack or when he can only perform a limited number of oracle queries. Secondly, we examine the amount of information that an adversary can derive from failing ciphertexts. Finally, these techniques are combined in an overall analysis of the security of lattice based schemes under a decryption failure attack. We show that an attacker could significantly reduce the security of lattice based schemes that have a relatively high failure rate. However, for most of the NIST Post-Quantum Proposals, the number of required oracle queries is above practical limits. Furthermore, a new generic weak-key (multi-target) model on lattice-based schemes, which can be viewed as a variant of the previous framework, is proposed. This model further takes into consideration the weak-key phenomenon that a small fraction of keys can have much larger decoding error probability for ciphertexts with certain key-related properties. We apply this model and present an attack in detail on the NIST Post-Quantum Proposal – ss-ntru-pke – with complexity below the claimed security level.
2018
EUROCRYPT
2017
CHES
Faster Homomorphic Function Evaluation Using Non-integral Base Encoding
In this paper we present an encoding method for real numbers tailored for homomorphic function evaluation. The choice of the degree of the polynomial modulus used in all popular somewhat homomorphic encryption schemes is dominated by security considerations, while with the current encoding techniques the correctness requirement allows for much smaller values. We introduce a generic encoding method using expansions with respect to a non-integral base, which exploits this large degree at the benefit of reducing the growth of the coefficients when performing homomorphic operations. This allows one to choose a smaller plaintext coefficient modulus which results in a significant reduction of the running time. We illustrate our approach by applying this encoding in the setting of homomorphic electricity load forecasting for the smart grid which results in a speed-up by a factor 13 compared to previous work, where encoding was done using balanced ternary expansions.
2016
EUROCRYPT
2015
EPRINT
2015
EPRINT
2015
CHES
2015
CHES
2014
EPRINT
2014
CHES
2011
CHES
2010
EPRINT
On the claimed privacy of EC-RAC III
Junfeng Fan Jens Hermans Frederik Vercauteren
In this paper we show how to break the most recent version of EC-RAC with respect to privacy. We show that both the ID-Transfer and ID&PWD-Transfer schemes from EC-RAC do not provide the claimed privacy levels by using a man-in-the-middle attack. The existence of these attacks voids the presented privacy proofs for EC-RAC.
2010
PKC
2009
CHES
2008
EPRINT
Optimal Pairings
F. Vercauteren
In this paper we introduce the concept of an \emph{optimal pairing}, which by definition can be computed using only $\log_2 r/ \varphi(k)$ basic Miller iterations, with $r$ the order of the groups involved and $k$ the embedding degree. We describe an algorithm to construct optimal ate pairings on all parametrized families of pairing friendly elliptic curves. Finally, we conjecture that any non-degenerate pairing on an elliptic curve without efficiently computable endomorphisms different from powers of Frobenius requires at least $\log_2 r/ \varphi(k)$ basic Miller iterations.
2008
EPRINT
The Hidden Root Problem
F. Vercauteren
In this paper we study a novel computational problem called the Hidden Root Problem, which appears naturally when considering fault attacks on pairing based cryptosystems. Furthermore, a variant of this problem is one of the main obstacles for efficient pairing inversion. We present an algorithm to solve this problem over extension fields and investigate for which parameters the algorithm becomes practical.
2007
EUROCRYPT
2007
EPRINT
Aspects of Pairing Inversion
Steven D. Galbraith F. Hess F. Vercauteren
We discuss some applications of the pairing inversion problem and outline some potential approaches for solving it. Our analysis of these approaches gives further evidence that pairing inversion is a hard problem.
2006
CRYPTO
2006
JOFC
2006
EPRINT
The Eta Pairing Revisited
F. Hess Nigel P. Smart F. Vercauteren
In this paper we simplify and extend the Eta pairing, originally discovered in the setting of supersingular curves by Baretto et al., to ordinary curves. Furthermore, we show that by swapping the arguments of the Eta pairing, one obtains a very efficient algorithm resulting in a speed-up of a factor of around six over the usual Tate pairing, in the case of curves which have large security parameters, complex multiplication by $D=-3$, and when the trace of Frobenius is chosen to be suitably small. Other, more minor savings are obtained for more general curves.
2006
EPRINT
Computing Zeta Functions of Nondegenerate Curves
W. Castryck J. Denef F. Vercauteren
In this paper we present a $p$-adic algorithm to compute the zeta function of a nondegenerate curve over a finite field using Monsky-Washnitzer cohomology. The paper vastly generalizes previous work since all known cases, e.g. hyperelliptic, superelliptic and $C_{ab}$ curves, can be transformed to fit the nondegenerate case. For curves with a fixed Newton polytope, the property of being nondegenerate is generic, so that the algorithm works for almost all curves with given Newton polytope. For a genus $g$ curve over $\FF_{p^n}$, the expected running time is $\widetilde{O}(n^3 g^6 + n^2 g^{6.5})$, whereas the space complexity amounts to $\widetilde{O}(n^3 g^4)$, assuming $p$ is fixed.
2005
CRYPTO
2005
EPRINT
On Computable Isomorphisms in Efficient Asymmetric Pairing Based Systems
Nigel P. Smart Frederik Vercauteren
In this paper we examine the hard problems underlying asymmetric pairings, their precise relationships and how they affect a number of existing protocols. Furthermore, we present a new model for the elliptic curve groups used in asymmetric pairings, which allows both an efficient pairing and an efficiently computable isomorphism.
2004
EPRINT
A comparison of MNT curves and supersingular curves
D. Page Nigel P. Smart F. Vercauteren
We compare both the security and performance issues related to the choice of MNT curves against supersingular curves in characteristic three, for pairing based systems. We pay particular attention to equating the relevant security levels and comparing not only computational performance and bandwidth performance. The paper focuses on the BLS signature scheme and the Boneh--Franklin encryption scheme, but a similar analysis can be applied to many other pairing based schemes.
2004
EPRINT
Fault and Side-Channel Attacks on Pairing Based Cryptography
D. Page F. Vercauteren
Current side-channel analytic attacks against public key cryptography focus on traditional schemes such as RSA and ECC, and to a lesser extent primitives such as XTR. However, bilinear maps, or pairings, have presented theorists with a new and increasingly popular way of constructing cryptographic protocols. Most notably, this has resulted in efficient methods for Identity Based Encryption (IBE). Since identity based cryptography seems an ideal partner for identity aware devices such as smart-cards, in this paper we examine the security of concrete pairing instantiations in terms of side-channel analysis.
2002
CRYPTO
2002
EPRINT
An Extension of Kedlaya's Algorithm to Hyperelliptic Curves in Characteristic 2
Jan Denef Frederik Vercauteren
We present an algorithm for computing the zeta function of an arbitrary hyperelliptic curve over a finite field $\FF_q$ of characteristic 2, thereby extending the algorithm of Kedlaya for odd characteristic. For a genus $g$ hyperelliptic curve defined over $\FF_{2^n}$, the average-case time complexity is $O(g^{4 + \varepsilon} n^{3 + \varepsilon})$ and the average-case space complexity is $O(g^{3} n^{3})$, whereas the worst-case time and space complexities are $O(g^{5 + \varepsilon} n^{3 + \varepsilon})$ and $O(g^{4} n^{3})$ respectively.
2001
EUROCRYPT

Program Committees

PKC 2020
Eurocrypt 2020
Eurocrypt 2019
Asiacrypt 2018
Eurocrypt 2018
Eurocrypt 2015
Eurocrypt 2014
Asiacrypt 2013
Crypto 2013
Eurocrypt 2011
Eurocrypt 2010