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-10-30
15:17 [Pub][ePrint]

Shamir\'s secret sharing scheme is an effective way to distribute secret to a group of shareholders. But this scheme is vulnerable to cheaters and attackers and thus how to protect the system from cheating and attacks is a big problem. In this paper, we proposed to use robust codes and algebraic manipulation detection (AMD) codes to protect the secret sharing module. Simulation and synthesis results show that the proposed architecture can improve the security level significantly even under strong cheating and attack models with some extra area and timing overheads.

15:17 [Pub][ePrint]

Distance (upper)-bounding (DUB) allows a verifier to know whether a proving party is located within a certain distance bound. DUB protocols have many applications in secure authentication and location based services. We consider the dual problem of distance lower bounding (DLB), where the prover proves it is outside a distance bound to the verifier. We motivate this problem through a number of application scenarios, and model security against distance fraud (DF), Man-in-the-Middle (MiM), and collusion fraud (CF) attacks. We prove impossibility of security against these attacks without making physical assumptions. We propose approaches to the construction of secure protocols under reasonable assumptions, and give detailed design of our DLB protocol and prove its security using the above model. This is the first treatment of the DLB problem in the untrusted prover setting, with a number of applications and raising new research questions. We discuss our results and propose directions for future research.

15:17 [Pub][ePrint]

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]

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]

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 our

new algorithms against first-order attacks.

15:17 [Pub][ePrint]

We show how to compute an existential forgery after querying 4 signatures on chosen messages for a signature scheme presented at Asiacrypt 2014.

15:17 [Pub][ePrint]

This paper presents an algebraic attack against Trivium

that 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]

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]

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.

15:17 [Pub][ePrint]

Secure two-party computation cannot be fair in general against malicious adversaries, unless a trusted third party (TTP) is involved, or gradual-release type of costly protocols with super-constant rounds are employed. Existing optimistic fair two-party computation protocols with constant rounds are either too costly to arbitrate (e.g., the TTP may need to re-do almost the whole computation), or require the use of electronic payments. Furthermore, most of the existing solutions were proven secure and fair separately, which, we show, may lead to insecurity overall.

We propose a new framework for fair and secure two-party computation that can be applied on top of any secure two party computation protocol based on Yao\'s garbled circuits. We show that our fairness overhead is minimal, compared to all known existing work. Furthermore, our protocol is fair even in terms of the work performed by Alice and Bob. We also prove our protocol is fair and secure simultaneously, through one simulator, which guarantees that our fairness extensions do not leak any private information. Lastly, we ensure that the TTP never learns the inputs or outputs of the computation. Therefore even if the TTP becomes malicious and causes unfairness, the security of the underlying protocol is still preserved.

15:17 [Pub][ePrint]

In a homomorphic signature scheme, a user Alice signs some large dataset $x$ using her secret signing key and uploads the signed data to an untrusted remote server. The server can then run some computation $y=f(x)$ over the signed data and homomorphically derive a short signature $\\sigma_{f,y}$ certifying that $y$ is the correct output of the computation $f$. Anybody can verify the tuple $(f, y, \\sigma_{f,y})$ using Alice\'s public verification key and become convinced of this fact without having to retrieve the entire underlying data.

In this work, we construct the first (leveled) fully homomorphic signature schemes that can evaluate arbitrary circuits over signed data. Only the maximal depth $d$ of the circuits needs to be fixed a-priori at setup, and the size of the evaluated signature grows polynomially in $d$, but is otherwise independent of the circuit size or the data size. Our solution is based on the (sub-exponential) hardness of the small integer solution (SIS) problem in standard lattices and satisfies full (adaptive) security. In the standard model, we get a scheme with large public parameters whose size exceeds the total size of a data-set. In the random-oracle model, we get a scheme with short public parameters. In both cases, the schemes can be used to sign many different data-sets. The complexity of verifying a signature for a computation $f$ is at least as large as that of computing $f$, but can be amortized when verifying the same computation over many different data-sets. Furthermore, the signatures can be made context-hiding so as not to reveal anything about the data beyond the outcome of the computation.

These results offer a significant improvement in capabilities and assumptions over the best prior homomorphic signature schemes, which were limited to evaluating polynomials of constant degree.

As a building block of independent interest, we introduce a new notion called homomorphic trapdoor functions (HTDF) which conceptually unites homomorphic encryption and signatures. We construct HTDFs by relying on the techniques developed by Gentry et al. (CRYPTO \'13) and Boneh et al. (EUROCRYPT \'14) in the contexts of fully homomorphic and attribute-based encryptions.