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).

2015-05-01
15:17 [Pub][ePrint]

We present a modular framework for the design of efficient

adaptively secure attribute-based encryption (ABE) schemes for a

large class of predicates under the standard k-Lin assumption

in prime-order groups; this is the first uniform treatment of dual

system ABE across different predicates and across both composite and

prime-order groups. Via this framework, we obtain concrete

efficiency improvements for several ABE schemes. Our framework has

three novel components over prior works: (i) new techniques for

simulating composite-order groups in prime-order ones, (ii) a

refinement of prior encodings framework for dual system ABE in

composite-order groups, (iii) an extension to weakly

attribute-hiding predicate encryption (which includes anonymous

identity-based encryption as a special case).

15:17 [Pub][ePrint]

Lattice-based cryptography is considered to be a big challenge to implement on resource-constraint microcontrollers. In this paper, we focus on efficient arithmetic that can be used for the ring variant of the Learning with Errors (ring-LWE) encryption scheme on 8-bit AVR processors. Our contributions include the following optimizations: for the Number Theoretic Transform (NTT) based polynomial multiplication, (1) we propose the MOV-and-ADD and Shifting-Addition-Multiplication-Subtraction-Subtraction (SAMS2) techniques for speeding up the modular coefficient multiplication, (2) we exploit the incomplete arithmetic for representing the coefficient to reduce the number of reduction operations, (3) and we reduce the running memory requirement of NTT multiplication with a refined memory-access scheme, finally, we propose to perform the Knuth-Yao Gaussian distribute sampler with a byte-wise scanning strategy to reduce the memory footprint of the probability matrix. For medium-term security level, our high-speed optimized ring-LWE implementation requires only 590K, 666K and 299K clock cycles for key-generation, encryption and decryption, respectively. Similarly for long-term security level, the key-generation, encryption and decryption take 2.3M, 2.7M and 700K clock cycles, respectively. These achieved results speed up the previous fastest LWE implementation by a factor of 4.5, while at least one order of magnitude faster than state of the art RSA and ECC implementations on the same platform.

15:17 [Pub][ePrint]

As Keccak has been selected as the new SHA-3 standard, Message Authentication Code (MAC) (MAC-Keccak) using a secret key will be widely used for integrity checking and authenticity assurance. Recent works have shown the feasibility of side-channel attacks against software implementations of MAC-Keccak to retrieve the key, with the security assessment of hardware implementations remaining an open problem. In this paper, we present a comprehensive and practical side-channel analysis of a hardware implementation of MAC-Keccak on FPGA. Different from previous works, we propose a new attack method targeting the first round output of MAC-Keccak rather than the linear operation $\\theta$ only. The results on sampled power traces show that the unprotected hardware implementation of MAC-Keccak is vulnerable to side-channel attacks, and attacking the nonlinear operation of MAC-Keccak is very effective. We further discuss countermeasures against side-channel analysis on hardware MAC-Keccak. Finally, we discuss the impact of the key length on side-channel analysis and compare the attack complexity between MAC-Keccak and other cryptographic algorithms.

12:17 [Pub][ePrint]

Motivated by the wide adoption of authenticated encryption and TLS, we suggest a basic channel abstraction, an \\emph{augmented secure channel} (ASC), that allows a sender to send a receiver messages consisting of two parts, where one is privacy-protected and both are authenticity-protected. Working in the tradition of constructive cryptography, we formalize this idea and provide a construction of this kind of channel using the lower-level tool authenticated-encryption.

We look at recent proposals on TLS 1.3 and suggest that the criterion by which their security can be judged is quite simple: do they construct an ASC? Due to this precisely defined goal, we are able to give a natural construction that comes with a rigorous security proof and directly leads to a proposal on TLS 1.3 that, in addition to being provably secure, is more efficient than existing ones.

12:17 [Pub][ePrint]

Sanitizable signature schemes are a type of malleable signatures where the signer grants

a designated third party, called the sanitizer, signing rights in the sense that the

sanitizer can modify designated parts and adapt the signature accordingly. Ateniese et al. (ESORICS 2005)

introduced this primitive and proposed five security properties, which were formalized by Brzuska et al. (PKC 2009).

Subsequently, Brzuska et al. (PKC 2010) suggested an additional security notion, called unlinkability,

which says one cannot link sanitized message-signature pairs of the same document and gave a generic

construction based on group signatures that have a certain structure.

Here, we present the first efficient instantiation of unlinkable sanitizable signatures. Our construction is

based on a novel type of signature schemes with rerandomizable keys. Intuitively, this property allows to rerandomize both the signing and the verification key independently but consistently.

This allows us to sign the message with a rerandomized key and to prove in zero-knowledge

that the derived key originates from either the signer or the sanitizer. We instantiate this generic idea with

Schnorr signatures and efficient $\\Sigma$-protocols which we convert into

non-interactive zero-knowledge proofs via the Fiat-Shamir transformation. Our construction is

at least one order of magnitude faster than the fastest known construction.

12:17 [Pub][ePrint]

Homomorphic MACs, introduced by Gennaro and Wichs in 2013, allow anyone to validate computations on authenticated data without knowledge of the secret key. Moreover, the secret-key owner can verify the validity of the computation without needing to know the original (authenticated) inputs. Beyond security, homomorphic MACs are required to produce short tags (succinctness) and to support composability (i.e., outputs of authenticated computations should be re-usable as inputs for new computations).

At Eurocrypt 2013, Catalano and Fiore proposed two realizations of homomorphic MACs that support a restricted class of computations (arithmetic circuits of polynomial degree), are practically efficient, but fail to achieve both succinctness and composability at the same time.

In this paper, we generalize the work of Catalano and Fiore in several ways. First, we abstract away their results using the notion of encodings with limited malleability, thus yielding new schemes based on different algebraic settings. Next, we generalize their constructions to work with graded encodings, and more abstractly with $k$-linear groups. The main advantage of this latter approach is that it allows for homomorphic MACs which are (somewhat) composable while retaining succinctness. Interestingly, our construction uses graded encodings in a generic way. Thus, all its limitations (limited composability and non-constant size of the tags) solely depend on the fact that currently known multilinear maps share similar constraints. This means, for instance, that our scheme would support arbitrary circuits (polynomial depth) if we had compact multilinear maps with an exponential number of levels.

12:17 [Pub][ePrint]

We revisit the security (as a pseudorandom permutation) of cascading-based constructions for block-cipher key-length extension. Previous works typically considered the extreme case where the adversary is given the entire codebook of the construction, the only complexity measure being the number $q_e$ of queries to the underlying ideal block cipher, representing adversary\'s secret-key-independent computation. Here, we initiate a systematic study of the more natural case of an adversary restricted to adaptively learning a number $q_c$ of plaintext/ciphertext pairs that is less than the entire codebook. For any such $q_c$, we aim to determine the highest number of block-cipher queries $q_e$ the adversary can issue without being able to successfully distinguish the construction (under a secret key) from a random permutation.

More concretely, we show the following results for key-length extension schemes using a block cipher with $n$-bit blocks and $\\kappa$-bit keys:

- Plain cascades of length $\\ell = 2r+1$ are secure whenever $q_c q_e^r \\ll 2^{r(\\kappa+n)}$, $q_c \\ll 2^\\ka$ and $q_e \\ll 2^{2\\ka}$. The bound for $r = 1$ also applies to two-key triple encryption (as used within Triple DES).

- The $r$-round XOR-cascade is secure as long as $q_c q_e^r \\ll 2^{r(\\kappa+n)}$, matching an attack by Gazi (CRYPTO 2013).

- We fully characterize the security of Gazi and Tessaro\'s two-call 2XOR construction (EUROCRYPT 2012) for all values of $q_c$, and note that the addition of a third whitening step strictly increases security for $2^{n/4} \\le q_c \\le 2^{3/4n}$. We also propose a variant of this construction without re-keying and achieving comparable security levels.

12:17 [Pub][ePrint]

In this paper, we study the problem of factoring an RSA modulus $N=pq$ in polynomial time, when $p$ is a weak prime, that is, $p$ can be expressed as $ap=u_0+M_1u_1+\\ldots+M_ku_k$ for some $k$ integers $M_1,\\ldots, M_k$ and $k+2$ suitably small parameters $a$, $u_0,\\ldots u_k$. We further compute a lower bound for the set of weak moduli, that is, moduli made of at least one weak prime, in the interval $[2^{2n},2^{2(n+1)}]$ and show that this number is much larger than the set of RSA prime factors satisfying Coppersmith\'s conditions, effectively extending the likelihood for factoring RSA moduli. We also prolong our findings to moduli composed of two weak primes.

12:17 [Pub][ePrint]

We present three attacks on the Prime Power RSA with modulus $N=p^rq$. In the first attack, we consider a public exponent $e$ satisfying an equation $ex-\\phi(N)y=z$ where $\\phi(N)=p^{r-1}(p-1)(q-1)$. We show that one can factor $N$ if the parameters $|x|$ and $|z|$ satisfy \$|xz|

12:17 [Pub][ePrint]

Attribute-based signatures, introduced by Maji \\emph{et al.}, are

signatures that prove that an authority has issued the signer

attributes\'\' that satisfy some specified predicate. In existing

attribute-based signature schemes, keys are valid indefinitely once

issued. In this paper, we initiate the study of incorporating time into

attribute-based signatures, where a time instance is embedded in every

signature, and attributes are restricted to producing signatures with

times that fall in designated validity intervals. We provide

three implementations that vary in granularity of assigning validity

intervals to attributes, including a scheme in which each attribute

has its own independent validity interval, a scheme in which all

attributes share a common validity interval, and a scheme in which

sets of attributes share validity intervals. All of our schemes provide anonymity to a signer, hide the attributes used to create the signature, and provide collusion-resistance between

users.

12:17 [Pub][ePrint]

Recently, D\\\"ottling et al. (ASIACRYPT 2012) proposed the first

chosen-ciphertext (IND-CCA) secure public-key encryption scheme from the learning parity with noise (LPN) assumption.

In this work we give an alternative scheme which is conceptually simpler and more efficient.

At the core of our construction is a trapdoor technique originally proposed for lattices by Micciancio and Peikert (EUROCRYPT 2012), which we adapt to the LPN setting. The main technical tool is a new double-trapdoor mechanism, together with a trapdoor switching lemma based on a computational variant of the leftover hash lemma.