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-01-14
19:17 [Pub][ePrint]

Field inversion in GF($2^m$) dominates the cost of modern software implementations of certain elliptic curve cryptographic operations, such as point encoding/hashing into elliptic curves. Itoh--Tsujii inversion using a polynomial basis and precomputed table-based multi-squaring has been demonstrated to be highly effective for software implementations, but the performance and memory use depend critically on the choice of addition chain and multi-squaring tables, which in prior work have been determined only by suboptimal ad-hoc methods and manual selection. We thoroughly investigated the performance/memory tradeoff for table-based linear transforms used for efficient multi-squaring. Based upon the results of that investigation, we devised a comprehensive cost model for Itoh--Tsujii inversion and a corresponding optimization procedure that is empirically fast and provably finds globally-optimal solutions. We tested this method on 8 binary fields commonly used for elliptic curve cryptography; our method found lower-cost solutions than the ad-hoc methods used previously, and for the first time enables a principled exploration of the time/memory tradeoff of inversion implementations.

19:17 [Pub][ePrint]

In predicate encryption, a ciphertext is associated with descriptive

attribute values $x$ in addition to a plaintext $\\mu$, and a secret key is associated with a predicate $f$. Decryption returns plaintext

$\\mu$ if and only if $f(x) = 1$. Moreover, security of predicate

encryption guarantees that an adversary learns nothing about the attribute $x$ or the plaintext $\\mu$ from a ciphertext, given arbitrary many secret keys that are not authorized to decrypt the ciphertext individually.

We construct a leveled predicate encryption scheme for all circuits, assuming the hardness of the subexponential learning with errors (LWE) problem. That is, for any polynomial function $d = d(\\secp)$,

we construct a predicate encryption scheme for the class of all circuits with depth bounded by $d(\\secp)$, where $\\secp$ is the security parameter.

19:17 [Pub][ePrint]

We present a detailed security analysis of the CAESAR candidate Ascon. Amongst others, cube-like, differential and linear cryptanalysis are used to evaluate the security of Ascon. Our results are practical key-recovery attacks on round-reduced versions of Ascon-128, where the initialization is reduced to 5 out of 12 rounds. Theoretical key-recovery attacks are possible for up to 6 rounds of initialization. Moreover, we present a practical forgery attack for 3 rounds of the finalization, a theoretical forgery attack for 4 rounds finalization and zero-sum distinguishers for the full 12-round Ascon permutation. Besides, we present the first results regarding linear cryptanalysis of Ascon, improve upon the results of the design document regarding differential cryptanalysis, and prove bounds on the minimum number of (linearly and differentially) active S-boxes for the Ascon permutation.

19:17 [Pub][ePrint]

We present a new and conceptually simpler proof of a tight parallel-repetition theorem for public-coin arguments (Pass-Venkitasubramaniam, STOC\'07, Hastad et al, TCC\'10, Chung-Liu, TCC\'10). We follow the same proof framework as the previous non-tight parallel-repetition theorem of Hastad et al---which relied on *statistical distance* to measure the distance between experiments---and show that it can be made tight (and further simplied) if instead relying on *KL-divergence* as the distance between the experiments.

We then show that our proof technique directly yields tight Chernoff-type\'\' parallel-repetition theorems (where one considers a threshold\'\' verifier that accepts iff the prover manages to convince a certain fraction of the parallel verifiers, as opposed to all of them) for any public-coin interactive argument; previously, tight results were only known for either constant-round protocols, or when the gap between the threshold and the original error-probability is a constant.

19:17 [Pub][ePrint]

Boneh et al. (Crypto 13) and Banerjee and Peikert (Crypto 14) constructed pseudorandom functions (PRFs) from the Learning with Errors (LWE) assumption by embedding combinatorial objects, a path and a tree respectively, in instances of the LWE problem. In this work, we show how to generalize this approach to embed circuits, inspired by recent progress in the study of Attribute Based Encryption.

Embedding a universal circuit for some class of functions allows us to produce constrained keys for functions in this class, which gives us the first standard-lattice-assumption-based constrained PRF (CPRF) for general bounded-description bounded-depth functions, for arbitrary polynomial bounds on the description size and the depth. (A constrained key w.r.t a circuit $C$ enables one to evaluate the PRF on all $x$ for which $C(x)=1$, but reveals nothing on the PRF values at other points.) We rely on the LWE assumption and on the one-dimensional SIS (Short Integer Solution) assumption, which are both related to the worst case hardness of general lattice problems. Previous constructions for similar function classes relied on such exotic assumptions as the existence of multilinear maps or secure program obfuscation. The main drawback of our construction is that it does not allow collusion (i.e. to provide more than a single constrained key to an adversary).

Similarly to the aforementioned previous works, our PRF family is also key homomorphic.

Interestingly, our constrained keys are very short. Their length does not depend directly either on the size of the constraint circuit or on the input length.

We are not aware of any prior construction achieving this property, even relying on strong assumptions such as indistinguishability obfuscation.

03:30 [Job][New]

For two NSF projects in the area of hardware Trojans we are looking for post-docs and Ph.D. students who are interested in research that bridge applied cryptography and modern hardware design. Both projects are very exciting and cutting-edge. We are looking for candidates which have previous experience in one of the two areas:

Topic Area 1) Applied cryptography, hardware security, implementation attacks

Topic Area 2) VLSI design, FPGA design, circuit design, embedded systems

Candidates for the post-doc position should have a strong publication record in the leading cryptography conferences (Topic Area 1) or leading computer engineering journals (Topic Area 2). Candidates for the Ph.D. position should have a BS&MS degree with excellent grades, relevant course work and some initial experience in one of the topic areas, either through MS-level research or industry.

The candidates should be open to work in an interdisciplinary fashion, i.e., to conduct high-quality research that bridges applied cryptography and modern hardware design. They will collaborate with Christof Paar (applied cryptography, on leave from the Univ. of Bochum) as well as Sandip Kundu and Russ Tessier (both computer engineering) at UMass Amherst. It is expected that the candidates also interact with researchers at the University of Bochum.

Sounds interesting? Please send your resume (CV, transcript of records) and names/email addresses of two people how can provide references.

2015-01-12
11:58 [Event][New]

Submission: 23 January 2015
From May 19 to May 19
Location: Florence, Italy

11:56 [Job][New]

The Department of Computing at the University of Surrey (http://www.surrey.ac.uk/computing/) seeks to recruit a motivated doctoral student to work in the area of Information Security.

The studentship is for three years and includes a stipend of £16,000 per year and tuition fees, and is available to students of UK/EU residency.

The successful candidate will participate in the Formal Methods and Security group (http://www.surrey.ac.uk/computing/research/fms/index.htm), will work in an exciting international environment and will have the opportunity to participate in the development of the recently launched Surrey Centre for Cyber Security (http://www.surrey.ac.uk/sccs/index.htm).

The main tasks of the Ph.D. student will be to develop state-of-the-art techniques for the security analysis of real world protocols. In particular, he/she will work in one of the following areas:

- Formal methods applied to security protocols;

- Applied Cryptography and Provable Security.

The position will remain open until a suitable candidate is found so there is no fixed closing date for applications.

10:17 [Pub][ePrint]

Private Information Retrieval (PIR) protects users\' privacy in outsourced storage applications and can be achieved using additively homomorphic encryption schemes. Several PIR schemes with a \"real world\" level of practicality, both in terms of computational and communication complexity, have been recently studied and implemented. One of the possible building block is a conceptually simple and computationally efficient protocol proposed by Trostle and Parrish at ISC 2010, that relies on an underlying secret-key (somewhat) additively homomorphic encryption scheme, and has been reused in numerous subsequent works in the PIR community (PETS 2012, FC 2013, NDSS 2014, etc.).

In this paper, we show that this encryption scheme is not one-way: we present an attack that decrypts arbitrary ciphertext without the secret key, and is quite efficient: it amounts to applying the LLL algorithm twice on small matrices. Used against existing practical instantiations of PIR protocols, it allows the server to recover the

users\' access pattern in a matter of seconds.

10:17 [Pub][ePrint]

Cryptography based on the Learning Parity with Noise (LPN) problem has several very desirable aspects: Low computational overhead, simple implementation and conjectured post-quantum hardness. Choosing the LPN noise parameter sufficiently low allows for public key cryptography. In this work, we construct the first standard model public key encryption scheme with key dependent message security based solely on the low noise LPN problem. Additionally, we establish a new connection between LPN with a bounded number of samples and LPN with an unbounded number of samples. In essence, we show that if LPN with a small error and a small number of samples is hard, then LPN with a slightly larger error and an unbounded number of samples is also hard. The key technical ingredient to establish both results is a variant of the LPN problem called the extended LPN problem.

10:17 [Pub][ePrint]

We introduce a lattice-based group signature scheme that provides several noticeable improvements over the contemporary ones: simpler construction, weaker hardness assumptions, and shorter sizes of keys and signatures. Moreover, our scheme can be transformed into the ring setting, resulting in a scheme based on ideal lattices, in which the public key and signature both have bit-size soft-O(n log N), for security parameter n, and for group of N users. Towards our goal, we construct a new lattice-based cryptographic tool: a statistical zero-knowledge argument of knowledge of a valid message-signature pair for Boyen\'s signature scheme (Boyen, PKC\'10), which potentially can be used as the building block to design various privacy-enhancing cryptographic constructions.