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]

A recent line of work has explored the use of physically uncloneable functions (PUFs) for secure computation, with the goals of (1) achieving universal composability without (additional) setup, and/or (2) obtaining unconditional security (i.e., avoiding complexity-theoretic assumptions).

Initial work assumed that all PUFs, even those created by an attacker, are honestly generated.

Subsequently, researchers have investigated models in which an adversary can create malicious PUFs with arbitrary behavior. Researchers have considered both malicious PUFs that might be stateful, as well as malicious PUFs that can have arbitrary behavior but are guaranteed to be stateless.

We settle the main open questions regarding secure computation in the malicious-PUF model:

-- We prove that unconditionally secure oblivious transfer is impossible, even in the stand-alone setting, if the adversary can construct (malicious) stateful PUFs.

-- We show that universally composable two-party computation is possible if the attacker is limited to creating (malicious) stateless PUFs. Our protocols are simple and efficient, and do not require any cryptographic assumptions.

15:17 [Pub][ePrint]

We introduce a new, instance-based notion of indistinguishability obfuscation, called computation-trace indistinguishability obfuscation (CiO), for (parallel) RAM computation. CiO only obfuscates a fixed, single computation instance, as opposed to iO which obfuscates a function on all input instances. Specifically, for $\\Pi$ defined by (P, x) consisting of a (parallel) RAM program P and an input x, the obfuscations of two instances $\\Pi$ and $\\Pi\'$ are required to be indistinguishable only when the execution of $\\Pi$ and $\\Pi\'$ generate an identical computation trace; namely, identical sequences of CPU states and memory content. On the other hand, we require the obfuscation to be (i) fully succinct: the runtime of the obfuscator (and thus the size of the obfuscated instance) depends only on the description and input/output size of $\\Pi$, but is independent of the time and space complexities of $\\Pi$, and (ii) efficiency preserving: the obfuscated instance is a (parallel) RAM program that preserves parallel/total time and space complexities of $\\Pi$ up to polylogarithmic factors.

As our main results, we construct CiO for parallel RAM (PRAM) computation based on iO for circuits and one-way functions, and demonstrate the power of CiO by the following applications.

o With digital signatures, our CiO for PRAM immediately implies the first two-message (publicly-

verifiable) delegation scheme for outsourcing PRAM computation, where the delegator\'s runtime depends only on the program description and input/output size, and the server\'s complexity matches the PRAM complexity of the computation up to polylogarithmic factors.

o With public-key encryption, our CiO for PRAM, and a specific oblivious PRAM construction, we construct the first fully succinct randomized encoding (RE) for PRAM computation, where the encoder\'s runtime (and thus the encoding size) depends only on the program description and input/output size, and the decoding complexity matches PRAM complexity of the computation up to polylogarithmic factors.

o By plugging our fully succinct RE for PRAM into existing transformations, we obtain the first constructions of several cryptographic primitives for PRAM, such as functional encryptions with succinct (PRAM) function keys, succinct reusable garbling schemes, and succinct indistinguishability obfuscations (the later requires sub-exponential security). Notably, this implies that, while CiO is weaker than iO, sub-exponentially secure CiO for PRAM implies sub-exponentially secure iO for PRAM.

15:17 [Pub][ePrint]

LowMC is a family of block ciphers developed particularly for use in multi-party computations and fully homomorphic encryption schemes, where the main performance penalty comes from non-linear operations. Thus, LowMC has been designed to minimize the total quantity of logical \"and\" operations, as well as the \"and\" depth. To achieve this, the LowMC designers opted for an incomplete S-box layer that does not cover the complete state, and compensate for it with a very dense, randomly chosen linear layer. In this work, we exploit this design strategy in a cube-like key-recovery attack. We are able to recover the secret key of a round-reduced variant of LowMC with PRESENT-like security, where the number of rounds is reduced from 11 to 9. Our attacks are independent of the actual instances of the used linear layers and therefore, do not exploit possible weak choices of them. From our results, we conclude that the resulting security margin of 2 rounds is smaller than expected.

15:17 [Pub][ePrint]

This paper deals with the protection of elliptic curve scalar

multiplications against side-channel analysis by using the atomicity principle.

Unlike other atomic patterns, we investigate new formul\\ae{} with

same cost for both doubling and addition. This choice is particularly well

suited to evaluate double scalar multiplications with the Straus-Shamir

trick. Since fixed point multiplications highly benefit from this trick, our

pattern allows a huge improvement in this case as other atomic patterns

cannot use it. Surprisingly, in other cases our choice remains very

efficient. Besides, we also point out a security threat when the curve

parameter $a$ is null and propose an even more efficient pattern in this

case.

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.