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

In a homomorphic signature scheme, given a vector of signatures $\\vec{\\sigma}$ corresponding to a dataset of messages $\\vec{\\mu}$, there is a {\\it public} algorithm that allows to derive a signature $\\sigma\'$ for message $\\mu\'=f(\\vec{\\mu})$ for any function $f$.

Given the tuple $(\\sigma\', \\mu\', f)$ anyone can {\\it publicly}

verify the result of the computation of function $f$.

Along with the standard notion of unforgeability

for signatures, the security of homomorphic signatures guarantees that no adversary is able to make a forgery $\\sigma^*$ for $\\mu^* \\neq f(\\vec{\\mu})$.

We construct the first homomorphic signature scheme for evaluating arbitrary functions. In our scheme, the public parameters and the size of the resulting signature grows linearly

with the depth of the circuit representation of $f$. Our scheme is secure in the standard model assuming hardness of

finding {\\it Small Integer Solutions} in hard lattices.

Furthermore, our construction has asymptotically fast verification

which immediately leads to a new solution for verifiable outsourcing with pre-processing phase. Previous state of the art constructions were limited to evaluating polynomials of constant degree, secure in random oracle model

without asymptotically fast verification.

15:17 [Pub][ePrint]

We present the design, implementation and evaluation of the root of trust for the Trusted Execution Environment (TEE) provided by ARM TrustZone based on SRAM Physical Unclonable Functions (PUFs). We first implement a building block which provides the foundations for the root of trust: secure key storage and truly random source. The building block doesn\'t require on or off-chip secure non-volatile memory to store secrets, but provides a high-level security: resistance to physical attackers capable of controlling all external interfaces of the system on chip (SoC). Based on the building block, we build the root of trust consisting of seal/unseal primitives for secure services running in the TEE, and a software-only TPM service running in the TEE which provides rich TPM functionalities for the rich OS running in the normal world of TrustZone. The root of trust resists software attackers capable of compromising the entire rich OS. Besides, both the building block and the root of trust run on the powerful ARM processor. In one word, we leverage the SRAM PUF, commonly available on mobile devices, to achieve a low-cost, secure, and efficient design of the root of trust.

15:17 [Pub][ePrint]

We consider *semi-adaptive* security for attribute-based encryption,

where the adversary specifies the challenge attribute vector after

it sees the public parameters but before it makes any secret key

queries. We present two constructions of semi-adaptive

attribute-based encryption under static assumptions with *short*

ciphertexts. Previous constructions with short ciphertexts either

achieve the weaker notion of selective security, or require

parameterized assumptions.

As an application, we obtain improved delegation schemes for Boolean

formula with *semi-adaptive* soundness, where correctness of the

computation is guaranteed even if the client\'s input is chosen

adaptively depending on its public key. Previous delegation schemes

for formula achieve one of adaptive soundness, constant

communication complexity, or security under static assumptions; we

show how to achieve semi-adaptive soundness and the last two

simultaneously.

15:17 [Pub][ePrint]

In this paper, we introduce the concept of the derivative of sequence of numbers and define new statistical indices by which we discoverd new properties of randomly generated number sequences.

We also build a test for pseudo random generators based on these properties and use it to confirm the weakness of RC4 key scheduling algorithm that has been reported in the litterature.

In this rescpect we publish a new RC4\'s key scheduling algorithm that don\'t have this weakness.

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

One-time memories (OTM\'s) are simple, tamper-resistant cryptographic devices, which can be used to implement sophisticated functionalities such as one-time programs. Can one construct OTM\'s whose security follows from some physical principle? This is not possible in a fully-classical world, or in a fully-quantum world, but there is evidence that OTM\'s can be built using \"isolated qubits\" -- qubits that cannot be entangled, but can be accessed using adaptive sequences of single-qubit measurements.

Here we present new constructions for OTM\'s using isolated qubits, which improve on previous work in several respects: they achieve a stronger \"single-shot\" security guarantee, which is stated in terms of the (smoothed) min-entropy; they are proven secure against adversaries who can perform arbitrary local operations and classical communication (LOCC); and they are efficiently implementable.

These results use Wiesner\'s idea of conjugate coding, combined with error-correcting codes that approach the capacity of the q-ary symmetric channel, and a high-order entropic uncertainty relation, which was originally developed for cryptography in the bounded quantum storage model.

12:17 [Pub][ePrint]

Formal verification of the security of software systems is gradually moving from the traditional focus on idealized models, to the more ambitious goal of producing verified implementations. This trend is also present in recent work targeting the verification of cryptographic software, but the reach of existing tools has so far been limited to cryptographic primitives, such as RSA-OAEP encryption, or standalone protocols, such as SSH. This paper presents a scalable

approach to formally verifying implementations of higher-level cryptographic systems, directly in the computational model.

We consider circuit-based cloud-oriented cryptographic protocols for secure and verifiable computation over encrypted data. Our examples share as central component Yao\'s celebrated transformation of a boolean circuit into an equivalent garbled form that can be evaluated securely in an untrusted environment. We leverage the foundations of garbled circuits set forth by Bellare, Hoang, and Rogaway (CCS 2012, ASIACRYPT 2012) to build verified implementations of garbling schemes, a verified implementation of Yao\'s secure

function evaluation protocol, and a verified (albeit partial) implementation of the verifiable computation protocol by Gennaro, Gentry, and Parno (CRYPTO 2010). The implementations are formally verified using EasyCrypt, a tool-assisted framework for building high-confidence cryptographic proofs, and critically rely on two novel features: a module and theory system that supports compositional reasoning, and a code extraction mechanism for generating

implementations from formalizations.

12:17 [Pub][ePrint]

We introduce the notion of a class of lattice-based digital signature schemes based on modular properties of the coordinates of lattice vectors. We also suggest a method of making such schemes transcript secure via a rejection sampling technique of Lyubashevsky (2009). A particular instantiation of this approach is given, using NTRU lattices. Although the scheme is not supported by a formal security reduction, we present arguments for its security and derive concrete parameters based on the performance of state-of-the-art lattice reduction and enumeration techniques.

12:17 [Pub][ePrint]

We initiate the study of principled, automated, methods for analyzing hardness assumptions in generic group models, following the approach of symbolic cryptography. We start by defining a broad class of generic and symbolic group models for different

settings---symmetric or asymmetric (leveled) k-linear groups---and by

proving \"computational soundness\" theorems for the symbolic models.

Based on this result, we formulate a very general master theorem that formally relates the hardness of a (possibly interactive) assumption in these models to solving problems in polynomial algebra. Then, we systematically analyze these problems. We identify different classes of assumptions and obtain decidability and undecidability results.

Then, we develop and implement automated procedures for verifying the conditions of master theorems, and thus the validity of hardness assumptions in generic group models. The concrete outcome of this work is an automated tool which takes as input the statement of an assumption, and outputs either a proof of its

generic hardness or shows an algebraic attack against the assumption.

12:17 [Pub][ePrint]

Template attacks remain a most powerful side-channel technique to

eavesdrop on tamper-resistant hardware. They use a profiling step to

compute the parameters of a multivariate normal distribution from a

training device and an attack step in which the parameters obtained

during profiling are used to infer some secret value (e.g.

cryptographic key) on a target device. Evaluations using the same

device for both profiling and attack can miss practical problems

that appear when using different devices. Recent

studies showed that variability caused by the use of either

different devices or different acquisition campaigns on the same

device can have a strong impact on the performance of template

attacks. In this paper, we explore further the effects that lead to

this decrease of performance, using four different Atmel XMEGA 256

A3U 8-bit devices. We show that a main difference between devices is

a DC offset and we show that this appears even if we use the same

device in different acquisition campaigns. We then explore several

variants of the template attack to compensate for these differences.

Our results show that a careful choice of compression method and

parameters is the key to improving the performance of these attacks

across different devices. In particular we show how to maximise the

performance of template attacks when using Fisher\'s Linear

Discriminant Analysis or Principal Component Analysis. Overall, we

can reduce the entropy of an unknown 8-bit value below 1.5 bits even

when using different devices.

12:17 [Pub][ePrint]

Most implementations of Yao\'s garbled circuit approach for 2-party secure computation use the {\\em free-XOR} optimization of Kolesnikov \\& Schneider (ICALP 2008). We introduce an alternative technique called {\\em flexible-XOR} (fleXOR) that generalizes free-XOR and offers several advantages. First, fleXOR can be instantiated under a weaker hardness assumption on the underlying cipher/hash function (related-key security only, compared to related-key and circular security required for free-XOR) while maintaining most of the performance improvements that free-XOR offers. Alternatively, even though XOR gates are not always free\'\' in our approach, we show that the other (non-XOR) gates can be optimized more heavily than what is possible when using free-XOR. For many circuits of cryptographic interest, this can yield a significantly (over 30\\%) smaller garbled circuit than any other known techniques (including free-XOR) or their combinations.

06:17 [Pub][ePrint]

In a homomorphic signature scheme, a user Alice signs some large data $x$ using her secret signing key and stores the signed data on a server. The server can then run some computation $y=g(x)$ on the signed data and homomorphically produce a short signature $\\sigma$. Anybody can verify the signature using Alice\'s public verification key and become convinced that $y$ is the correct output of the computation $g$ over Alice\'s data, without needing to have the underlying data itself.

In this work, we construct the first leveled fully homomorphic signature schemes that can evaluate arbitrary circuits over signed data, where only the maximal depth $d$ of the circuit needs to be fixed a priori. The size of the evaluated signature grows polynomially in $d$, but is otherwise independent of the circuit size or the data size. Our solutions are based on the hardness of the small integer solution (SIS) problem, which is in turn implied by the worst-case hardness of problems in standard lattices. We get a scheme in the standard model, albeit with large public parameters whose size must exceed the total size of all signed data. In the random-oracle model, we get a scheme with short public parameters. These results offer a significant improvement in capabilities and assumptions over the best prior homomorphic signature scheme due to Boneh and Freeman (Eurocrypt \'11).

As a building block of independent interest, we introduce a new notion called homomorphic trapdoor functions (HTDF). We show to how construct homomorphic signatures using HTDFs as a black box. We construct HTDFs based on the SIS problem by relying on a recent technique developed by Boneh et al. (Eurocrypt \'14) in the context of attribute based encryption.