International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also receive updates via:

To receive your credentials via mail again, please click here.

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] Sequential Secret Sharing as a New Hierarchical Access Structure, by Mehrdad Nojoumian and Douglas R. Stinson

  Due to the rapid growth of the next generation networking and system technologies, computer networks require new design and management. In this context, security, and more specifically, access structures have been one of the major concerns. As such, in this article, sequential secret sharing (SQS), as an application of dynamic threshold schemes, is introduced. In this new cryptographic primitive, different (but related) secrets with increasing thresholds are shared among a set of players who have different levels of authority. Subsequently, each subset of the players can only recover the secret in their own level. Finally, the master secret will be revealed if all the secrets in the higher levels are first recovered. We briefly review the existing threshold modification techniques. We then present our construction and compare it with other hierarchical secret sharing schemes such as disjunctive and conjunctive multilevel secret sharing protocols.



15:17 [Pub][ePrint] Zero-Knowledge Accumulators and Set Operations, by Esha Ghosh and Olga Ohrimenko and Dimitrios Papadopoulos and Roberto Tamassia and Nikos Triandopoulos

  Accumulators provide a way to succinctly represent a set with elements drawn from a given domain, using an \\emph{accumulation value}. Subsequently, short proofs for the set-\\emph{membership} (or \\emph{non-membership}) of any element from the domain can be constructed and efficiently verified with respect to this accumulation value. Accumulators have been widely studied in the literature, primarily, as an \\emph{authentication} primitive:

a malicious prover (e.g., an untrusted server) should not be able to provide convincing proofs on false statements (e.g., successfully prove membership for a value not in the set) to a verifier that issues membership queries (of course, having no access to set itself).

In essence, in existing constructions the accumulation value acts as a (honestly generated) ``commitment\'\' to the set that allows selective ``opening\'\' as specified by membership queries---but with no ``hiding\'\' properties.

In this paper we revisit this primitive and propose a privacy-preserving enhancement. We define the notion of a \\emph{zero-knowledge accumulator} that provides the following very strong privacy notion: Accumulation values and proofs constructed during the protocol execution leak nothing about the set itself, or any subsequent updates to it (i.e., via element insertions/deletions). We formalize this property by a standard real/ideal execution game. An adversarial party that is allowed to choose the set and is given access to query and update oracles, cannot distinguish whether this interaction takes place with respect to the honestly executed algorithms of the scheme or with a simulator that is not given access to the set itself (and for updates, it does not even learn the type of update that occurred---let alone the inserted/deleted element). We compare our new privacy definition with other recently proposed similar notions showing that it is strictly stronger: We give a concrete example of the update-related information that can be leaked by previous definitions.

We provide a mapping of the relations between zero-knowledge accumulators and primitives that

are either set in the same security model or solve the same problem.

We formally show and discuss a number of implications among primitives, some of which are not immediately evident.

We believe this contribution is interesting on its own, as the area has received considerable attention recently (e.g., with the works of [Naor et al., TCC~2015] and [Derler et al., CT-RSA~2015]).

We then construct the first dynamic universal zero-knowledge accumulator. Our scheme is perfect zero-knowledge and is secure under the $q$-Strong Bilinear Diffie-Hellman assumption.

Finally, building on our dynamic universal zero-knowledge accumulator, we define a \\emph{zero-knowledge authenticated set collection} to handle more elaborate set operations (beyond set-membership). In particular, this primitive allows one to outsource a collection of sets to an untrusted server that is subsequently responsible for answering union, intersection and set difference queries over these sets issued by multiple clients. Our scheme provides proofs that are succinct and efficiently verifiable and, at the same time, leak nothing beyond the query result. In particular, it offers verification time that is asymptotically optimal (namely, the same as simply reading the answer), and proof construction that is asymptotically as efficient as existing state-of-the-art constructions--- that however, do not offer privacy.



15:17 [Pub][ePrint] Feasibility and Infeasibility of Secure Computation with Malicious PUFs, by Dana Dachman-Soled and Nils Fleischhacker and Jonathan Katz and Anna Lysyanskaya and Dominique Schröder

  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] Computation-Trace Indistinguishability Obfuscation and its Applications, by Yu-Chi Chen and Sherman S. M. Chow and Kai-Min Chung and Russell W. F. Lai and Wei-Kai Lin and Hong-Sheng Zhou

  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] Higher-order cryptanalysis of LowMC, by Christoph Dobraunig and Maria Eichlseder and Florian Mendel

  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] Revisiting Atomic Patterns for Scalar Multiplications on Elliptic Curves, by Franck Rondepierre

  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] Improved Dual System ABE in Prime-Order Groups via Predicate Encodings, by Jie Chen and Romain Gay and Hoeteck Wee

  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] Efficient Ring-LWE Encryption on 8-bit AVR Processors, by Zhe Liu and Hwajeong Seo and Sujoy Sinha Roy and Johann Gro{\\ss}sch{\\\"a}dl and Howon Kim and Ingrid Verbauwhede

  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] Side-Channel Analysis of MAC-Keccak Hardware Implementations, by Pei Luo and Yunsi Fei and Xin Fang and A. Adam Ding and David R. Kaeli and Miriam Leeser

  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] Augmented Secure Channels and the Goal of the TLS 1.3 Record Layer, by Christian Badertscher and Christian Matt and Ueli Maurer and Phillip Rogaway and Björn Tackmann

  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] Efficient Unlinkable Sanitizable Signatures from Signatures with Rerandomizable Keys, by Nils Fleischhacker and Johannes Krupp and Giulio Malavolta and Jonas Schneider and Dominique Schröder and Mark

  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.