*15:17* [Pub][ePrint]
Efficient Stochastic Methods: Profiled Attacks Beyond 8 Bits, by Omar Choudary and Markus G. Kuhn
Template attacks and stochastic models are among the most powerfulside-channel attacks. However, they can be computationally expensive

when processing a large number of samples. Various compression

techniques have been used very successfully to reduce the data

dimensionality prior to applying template attacks, most notably

Principal Component Analysis (PCA) and Fisher\'s Linear Discriminant

Analysis (LDA). These make the attacks more efficient computationally

and help the profiling phase to converge faster. We show how these

ideas can also be applied to implement stochastic models more

efficiently, and we also show that they can be applied and evaluated

even for more than eight unknown data bits at once.

*15:17* [Pub][ePrint]
Accountable Storage, by Giuseppe Ateniese and Michael T. Goodrich and Vassilios Lekakis and Charalampos Papamanthou and Evripidis Paraskevas and Roberto Tamassia
We introduce Accountable Storage (AS), a framework allowing a client with small local space to outsource n file blocks to an untrusted server and be able (at any point in time after outsourcing) to provably compute how many bits have been discarded by the server. Such protocols offer ``provable storage insurance\" to a client: In case of a data loss, the client can be compensated with a dollar amount proportional to the damage that has occurred, forcing the server to be more ``accountable\" for his behavior.

The insurance can be captured in the SLA between the client and the server.

Although applying existing techniques (e.g., proof-of-storage protocols) could address the problem,

the related costs of such approaches are prohibitive. Instead, our protocols can provably compute the damage that has occurred through an efficient recovery process of the lost or corrupted file blocks, which requires only sublinear $O(\\delta\\log n)$ communication, computation and local space, where $\\delta$ is the maximum number of corrupted file blocks that can be tolerated. Our technique is based on an extension of invertible Bloom filters, a data structure used to quickly compute the distance between two sets.

Finally, we show how our protocol can be integrated with Bitcoin,

to support automatic compensations proportional to the number of corrupted bits at the server. We also build and evaluate our protocols showing that they perform well in practice.

*15:17* [Pub][ePrint]
Efficient Zero-Knowledge Proofs for Commitments from Learning With Errors over Rings, by Fabrice Benhamouda and Stephan Krenn and Vadim Lyubashevsky and Krzysztof Pietrzak
We design an efficient commitment scheme, and companion zero-knowledge proofs of knowledge, based on the learning with errors over rings (RLWE) problem. In particular, for rings in which almost all elements have inverses, we construct a perfectly binding commitment scheme whose hiding property relies on the RLWE assumption. Our scheme maps elements from the ring (or equivalently, n elements from F_q) to a small constant number of ring elements. We then construct Sigma-protocols for proving, in a zero-knowledge manner, knowledge of the message contained in a commitment. We are able to further extend our basic protocol to allow us to prove additive and multiplicative relations among committed values.

Our protocols have a communication complexity of O(Mn\\log q) and achieve a negligible knowledge error in one run.

Here M is the constant from a rejection sampling technique that we employ, and can be set close to 1 by adjusting other parameters.

Previously known Sigma-protocols for LWE-related languages either relied on ``smudging\'\' out the error (which necessitates working over large fields, resulting in poor efficiency) or only achieved a noticeable or even constant knowledge error (thus requiring many repetitions of the protocol).

*15:17* [Pub][ePrint]
Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-channel Countermeasures, by Jean-Sebastien Coron and Arnab Roy and Srinivas Vivek
We describe a new technique for evaluating polynomials over binary finite fields. This is useful in the context of anti-DPA countermeasures when an S-box is expressed as a polynomial over a binary finite field. For $n$-bit S-boxes our new technique has heuristic complexity ${\\cal O}(2^{n/2}/\\sqrt{n})$ instead of ${\\cal O}(2^{n/2})$ proven complexity for the Parity-Split method. We also prove a lower bound of ${\\Omega}(2^{n/2}/\\sqrt{n})$ on the complexity of any method to evaluate $n$-bit S-boxes; this shows that our method is asymptotically optimal. Here, complexity refers to the number of non-linear multiplications required to evaluate the polynomial corresponding to an S-box.In practice we can evaluate any $8$-bit S-box in $10$ non-linear multiplications instead of $16$ in the Roy-Vivek paper from CHES 2013, and the DES S-boxes in $4$ non-linear multiplications instead of $7$. We also evaluate any $4$-bit S-box in $2$ non-linear multiplications instead of $3$. Hence our method achieves optimal complexity for the PRESENT S-box.

*15:17* [Pub][ePrint]
Conversion from Arithmetic to Boolean Masking with Logarithmic Complexity, by Jean-Sebastien Coron and Johann Groszschaedl and Praveen Kumar Vadnala and Mehdi Tibouchi
A general method to protect a cryptographic algorithm against side-channel attacks consists in masking all intermediate variables with a random value. For cryptographic algorithms combining Boolean operations with arithmetic operations, one must then perform conversions between Boolean masking and arithmetic masking. At CHES 2001, Goubin described a very elegant algorithm for converting from Boolean masking to arithmetic masking, with only a constant number of operations. Goubin also described an algorithm for converting from arithmetic to Boolean masking, but with O(k) operations where k is the addition bit size. In this paper we describe an improved algorithm with time complexity O(log k) only. Our new algorithm is based on the Kogge-Stone carry look-ahead adder, which computes the carry signal in O(log k) instead of O(k) for the classical ripple carry adder. We also describe an algorithm for performing arithmetic addition modulo 2^k directly on Boolean shares, with the same complexity O(log k) instead of O(k). We prove the security of ournew algorithms against first-order attacks.

*15:17* [Pub][ePrint]
Advanced Algebraic Attack on Trivium, by Frank Quedenfeld and Christopher Wolf
This paper presents an algebraic attack against Triviumthat breaks 625 rounds using only $4096$ bits of output

in an overall time complexity of $2^{42.2}$ Trivium computations.

While other attacks can do better in terms of rounds ($799$), this is a practical attack with a very low data usage (down from $2^{40}$ output bits) and low computation time (down from $2^{62}$).

From another angle, our attack can be seen as a proof of concept,

how far algebraic attacks can be pushed when several known

techniques are combined into one implementation.

All attacks have been fully implemented and tested; our figures

are therefore not the result of any potentially error-prone extrapolation.

*15:17* [Pub][ePrint]
THE UBERCRYPT FRAMEWORK: A NEW APPROACH IN CRYPTOSYSTEMS, by Joe Chiarella and Greg Mosher and Dr. J. Robert Buchanan
This article describes a novel and unique cryptosystem making use of a small set of private security parameters and public initialization values to produce a pseudorandom byte stream with large period. The byte stream can be used as a one-time stream cipher for securing communication between parties and for data archival. The cryptosystem makes use of geometry and number theory to generate a set of large prime integers and then from the primes a column-periodic matrix of bytes from which further calculation produces a pseudorandom, long period byte stream. The cryptosystem is extensible

in that additional private user-supplied security parameters can supplement the private geometric security parameters while adding strength in the process. The article discusses the design and operation of the system and lists many potential questions of interest to the community of mathematical and cryptological researchers. Foremost among these questions are determining the most appropriate method for assessing the cryptographic strength of the algorithm and determining any weaknesses in the security of the algorithm.

*15:17* [Pub][ePrint]
Analysis of ARX Functions: Pseudo-linear Methods for Approximation, Differentials, and Evaluating Diffusion, by Kerry A. McKay and Poorvi L. Vora
This paper explores the approximation of addition mod $2^n$ by addition mod $2^w$, where $1 \\le w \\le n$, in ARX functions that use large words (e.g., 32-bit words or 64-bit words).Three main areas are explored.

First, \\emph{pseudo-linear approximations} aim to approximate the bits of a $w$-bit window of the state after some rounds.

Second, the methods used in these approximations are also used to construct truncated differentials.

Third, branch number metrics for diffusion are examined for ARX functions with large words, and variants of the differential and linear branch number characteristics based on pseudo-linear methods are introduced.

These variants are called \\emph{effective differential branch number} and \\emph{effective linear branch number}, respectively.

Applications of these approximation, differential, and diffusion evaluation techniques are demonstrated on Threefish-256 and Threefish-512.