International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2014-06-05
21:17 [Pub][ePrint]

In 1993, Coppersmith introduced the \"factorization factory\" approach as a means to speed up the Number Field Sieve algorithm (NFS) when factoring batches of integers of similar size: at the expense of a large precomputation whose cost is amortized when considering sufficiently many integers to factor, the complexity of each individual factorization can then be lowered.

We suggest here to extend this idea to the computation of discrete logarithms in finite fields of small characteristic using the Function Field Sieve (FFS), thus referring to this approach as the \"FFS factory\". In this paper, the benefits of the proposed technique are established thanks to both a theoretical complexity analysis along with a practical experiment in which we solved the discrete logarithm problem in fifty different binary fields of sizes ranging from 601 to 699 bits.

21:17 [Pub][ePrint]

Homomorphic signatures enable anyone to publicly perform computations on signed data and produce a compact tag to authenticate the results.

In this paper, we construct two bounded fully homomorphic signature schemes, as follows.

\\begin{itemize}

\\item For any two polynomials $d=d(\\lambda), s=s(\\lambda)$, where $\\lambda$ is the security parameter.

Our first scheme is able to evaluate any circuit on the signatures, as long as the depth and size of the circuit are bounded by $d$ and $s$, respectively.

The construction relies on indistinguishability obfuscation and injective (or polynomially bounded pre-image size) one-way functions.

\\medskip

\\item The second scheme, removing the restriction on the size of the circuits, is an extension of the first one,

with succinct verification and evaluation keys.

More specifically, for an a-prior polynomial $d=d(\\lambda)$, the scheme allows to evaluate any circuit on the signatures, as long as the depth of the circuit is bounded by $d$.

This scheme is based on differing-inputs obfuscation and collision-resistant hash functions and

relies on a technique called recording hash of circuits.

\\end{itemize}

Both schemes enjoy the composition property.

Namely, outputs of previously derived signatures can be re-used as inputs for new computations.

The length of derived signatures in both schemes is independent of the size of the data set.

Moreover, both constructions satisfy a strong privacy notion, we call {\\em semi-strong context hiding}, which requires that

the derived signatures of evaluating any circuit on the signatures of two data sets are {\\em identical} as long as the evaluations of the circuit on these two data sets are the same.

2014-06-04
15:17 [Pub][ePrint]

We describe a method to bootstrap a packed BGV ciphertext which does not depend (as much) on any special properties of the plaintext and ciphertext moduli. Prior efficient\'\' methods such as that of Gentry et al (PKC 2012) required a ciphertext modulus $q$ which was close to a power of the plaintext modulus $p$. This enables our method to be applied in a larger number of situations. Also unlike previous methods our depth grows only as $\\log \\log q$ as opposed to the $\\log q$ of previous methods. The basic bootstrapping technique makes use of a representation of the group $\\Z_q^+$ over the finite field $\\F_p$ (either based on polynomials or elliptic curves). This technique is then extended to the full BGV packed ciphertext space, using a method whose depth depends only logarithmically on the number of packed elements. This method may be of interest as an alternative to the method of Alperin-Sheriff and Peikert (CRYPTO 2013). To aid efficiency we utilize the ring/field switching technique of Gentry et al (SCN 2012, JCS 2013).

15:17 [Pub][ePrint]

We generalize correlation-enhanced power analysis collision attacks into moments-correlating DPA. The resulting distinguisher is applicable to the profiled and non-profiled (collision) settings and is able to exploit information lying in any statistical moment. It also benefits from a simple rule-of-thumb to estimate its data complexity. Experimental results show that such a tool allows answering with confidence to some important questions regarding the design of side-channel countermeasures (e.g. what is the most informative statistical moment in the leakages of a threshold implementation). We further argue that moments-correlating DPA is a natural candidate for leakage detection tests, enjoying the simplicity of correlation power analysis and advanced features for the evaluation of higher-order attacks with an easy-to-compute confidence level.

15:17 [Pub][ePrint]

In this paper, we introduce a new approach to side-channel key recovery, that combines the low time/memory complexity and noise tolerance of standard (divide and conquer) differential power analysis with the optimal data complexity of algebraic side-channel attacks. Our fundamental contribution for this purpose is to change the way of expressing the problem, from the system of equations used in algebraic attacks to a code, essentially inspired by low density parity check codes. We then show that such codes can be efficiently decoded, taking advantage of the sparsity of the information corresponding to intermediate variables in actual leakage traces. The resulting soft analytical side-channel attacks work under the same profiling assumptions as template attacks, and directly exploit the vectors of probabilities produced by these attacks. As a result, we bridge the gap between popular side-channel distinguishers based on simple statistical tests and previous approaches to analytical side-channel attacks that could only exploit hard information so far.

15:17 [Pub][ePrint]

Combining countermeasures is usually assumed to be the best way to protect embedded devices against side-channel attacks. These combinations are at least expected to increase the number of measurements of successful attacks to some reasonable extent, and at best to guarantee a bounded time complexity independent of the number of measurements. This latter guarantee, only possible in the context of leakage-resilient constructions, was only reached either for stateful (pseudo-random generator) constructions, or large parallel implementations so far. In this paper, we describe a first proposal of stateless (pseudo-random function) construction, for which we have strong hints that security bounded implementations are reachable under the constraints of small embedded devices. Our proposal essentially combines the well-known shuffling countermeasure with a tweaked pseudo-random function introduced at CHES 2012. We first detail is performances. Then we analyze it against standard differential power analysis and discuss the different parameters influencing its security bounds. Finally, we put forward that its implementation in 8-bit microcontrollers can provide a better security vs. performance tradeoff than state-of-the art (combinations of) countermeasures.

15:17 [Pub][ePrint]

The selection of points-of-interest in leakage traces is a frequently neglected problem in the side-channel literature. However, it can become the bottleneck of practical adversaries/evaluators as the size of the measurement traces increases, especially in the challenging context of masked implementations, where only a combination of multiple shares reveals information in higher-order statistical moments. In this paper, we describe new (black box) tools for efficiently dealing with this problem. The proposed techniques exploit projection pursuits and optimized local search algorithms, work with minimum memory requirements and practical time complexity. We validate them with two case-studies of unprotected and first-order masked implementations in an 8-bit device, the latter one being hard to analyze with previously known methods.

15:17 [Pub][ePrint]

Masking is one of the most popular countermeasures to mitigate side-channel analysis. Yet, its deployment in actual cryptographic devices is well known to be challenging, since designers have to ensure that the leakage corresponding to different shares is independent. Several works have shown that such an independent leakage assumption may be contradicted in practice, because of physical effects such as glitches\" or transition-based\" leakages. As a result, implementing masking securely can be a time-consuming engineering problem. This is in strong contrast with recent and promising approaches for the automatic insertion of countermeasures exploiting compilers, that aim to limit the development time of side-channel resistant software. Motivated by this contrast, we question what can be hoped for these approaches - or more generally for masked software implementations based on careless assembly generation. For this purpose, our first contribution is a simple reduction from security proofs obtained in a (usual but not always realistic) model where leakages depend on the intermediate variables manipulated by the target device, to security proofs in a (more realistic) model where the transitions between these intermediate variables are leaked. We show that the cost of moving from one context to the other implies a division of the security order by two for masking schemes. Next, our second and main contribution is to provide an exhaustive empirical validation of this reduction, based on two microcontrollers, several (handwritten and compiler-based) ways of generating assembly codes, with and without recycling\" the randomness used for sharing. These experiments confirm the relevance of our analysis, and therefore quantify the cost of lazy engineering for masking.

15:17 [Pub][ePrint]

We describe a tight security reduction to the discrete logarithm problem for KCDSA under an extended Random Oracle Model. This is achieved by generalising the signature scheme and producing a security proof for the generalised scheme. We require the application of Randomized Hashing. We also introduce a Challenger to the Random Oracle Model, who is external to the Simulator and Adversary. The Challenger provides oracle returns for one hash function, and challenges which have a low probability of being met. On presentation of a forged signature the Simulator either identifies an edge case which allows solving of a challenge, or solves the discrete logarithm problem. Hence the tight reduction.

05:36 [Pub]

The following reviews shall help the IACR members and the community to buy books in cryptology and related areas. The full list of reviews / books is available at www.iacr.org/books

If you have any questions regarding the IACR book reviewing system, or would like to volunteer a review, please contact Edoardo Persichetti (University of Warsaw, Poland) via /books at iacr.org/.

New reviews in 2014:
• R. Lidl, H. Niederreiter: Finite Fields (2nd Edition)
"This volume gives a comprehensive coverage of the theory of finite fields and its most important applications such as combinatorics and coding theory. Its simple and reader-friendly style, and the inclusion of many worked examples and exercises make it suitable not only as a reference volume for the topic, but also as a textbook for a dedicated course. I highly recommend the book to any person interested in the theory of finite fields and its applications."
Year: 2008
ISBN: 978-0-521-06567-2
Review by Edoardo Persichetti (Warsaw University, Warsaw, Poland). (Date: 2014-01-30)
• A. McAndrew: Introduction to Cryptography with Open-Source Software
"This very well written book is recommended to graduate or final year undergraduate students intended to start research work on both theoretical and experimental cryptography. Most of the cryptographic protocols are illustrated by various examples and implemented using the open-source algebra software Sage. The book provides a rigorous introduction to the mathematics used in cryptographic and covers almost all modern practical cryptosystems. Also, the book is certainly a valuable resource for practitioners looking for experimental cryptography with a computer algebra system."
Year: 2011
ISBN: 978-1-4398-2570-9
Review by Abderrahmane Nitaj (LMNO, Université de Caen Basse Normandie, France). (Date: 2014-02-13)
• B. Martin: Codage, Cryptologie et Applications [French]
"This French book succinctly describes the mathematical principles of cryptography and error correcting codes. Once these principles are introduced, the book presents their use in some telecommunication applications (at the state of the art in 2004). The book does not define its target audience. It is probably not enough detailed for a skilled audience, nor particularly suitable for beginners and students, since it requires mathematical background that they would have to find elsewhere."
Year: 2006
ISBN: 2-88074-569-1
Review by Eric Diehl (Technicolor, Paris, France). (Date: 2014-02-12)
• T. Baignères, P. Junod, Y. Lu, J. Monnerat, S. Vaudenay: A Classical Introduction To Cryptography Exercise Book
"The book's main goal is to show how some mathematical notions of calculus, algebra, and computer science are used to study the security of various cryptosystems. The volume is a collection of exercises, including hints and solutions, and is suitable for advanced undergraduate and graduate students as well as students in computer science and engineering and practitioners who want to understand the mathematical techniques behind cryptography."
Year: 2006
ISBN: 978-0-387-27934-3
Review by Abdelhak Azhari (Hassan II University, Casablanca, Morocco). (Date: 2014-02-12)
• J. Buchmann, U. Vollmer: Binary Quadratic Forms
"The theory of binary quadratic forms is important in algebraic number theory. This book offers a good introduction to binary quadratic forms by following an algorithmic approach. It will be useful for students and teachers interested in binary quadratic forms and their cryptographic applications."
Year: 2007
ISBN: 978-3-540-46367-2
Review by S.V. Nagaraj (RMK Engineering College, Kavaraipettai, Tamil Nadu, India). (Date: 2014-05-19)
• J. Hoffstein, J. Pipher, J. Silverman: An Introduction to Mathematical Cryptography
"This volume provides an excellent introduction to the mathematics of cryptography. Its simple style make it accessible even to readers without a consistent mathematical background. I highly recommend this book to anyone, in particular non-specialists that are interested in the topic, and students that want to approach cryptography from a mathematical point of view. It is also very useful for instructors in the same context - I personally found it an an invaluable tool for preparing my graduate cryptography course."
Year: 2008
ISBN: 978-0-387-77993-5
Review by Edoardo Persichetti (University of Warsaw, Poland). (Date: 2014-03-27)

2014-06-02
17:33 [Event][New]

Submission: 4 September 2014