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-04
01:07 [Event][New]

Submission: 20 June 2015
From October 7 to October 10
Location: Tokyo, Japan

2015-05-02
20:21 [Event][New]

Submission: 15 April 2015
From July 21 to July 23
Location: İzmir, Turkey

20:15 [Job][New]

The Department of Pervasive Computing at Tampere University of Technology (TUT) is seeking applications for an open post-doc position, funded by a collaborative project within the TEKES Innovative Cities program (INKA). The specific role of TUT in the project is side-channel analysis of real-world devices and software. Qualified candidates should have interests in one or more of the following areas:

• side-channel analysis
• software-based side-channels
• cryptography engineering
• embedded security
• hardware-assisted security

The contract is for one year with the possibility of extension and TUT offers extremely competitive post-doc salaries. The start date is flexible and review of applications begins immediately and continues until the position is filled. Interested candidates should submit a CV via email.

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

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]

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]

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.