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

2014-10-20
15:17 [Pub][ePrint]

Barak, Shaltiel Tromer showed how to construct a True Random Number Generator (TRNG) which is secure against an adversary who has some limited control over the environment.

In this paper we improve the security analysis of this TRNG. Essentially, we significantly reduce the entropy loss and running time needed to obtain a required level of security and robustness.

Our approach is based on replacing the combination of union bounds and tail inequalities for $\\ell$-wise independent random variables in the original proof, by a more refined of the deviation of the probability that a randomly chosen item is hashed into a particular location.

15:17 [Pub][ePrint]

Homomorphic encryption (HE) systems enable computations on encrypted data, without decrypting and without knowledge of the secret key. In this work, we describe an optimized RLWE-based implementation of a variant of the HE system recently proposed by Gentry, Sahai and Waters (henceforth called GSW). Although this system was widely believed to be less efficient than its contemporaries, we demonstrate quite the opposite behavior for a large class of applications.

We first highlight and carefully exploit the algebraic features of the system to achieve significant speedup over the state-of-the-art HE implementation, namely the IBM homomorphic encryption library (HElib). We introduce several optimizations on top of our HE implementation, and use the resulting scheme to construct a homomorphic Bayesian spam filter, secure multiple keyword search, and a homomorphic evaluator for binary decision trees.

Our results show a factor of 10x improvement in performance (under the same security settings and platforms) compared to HElib for these applications. Our system is built to be easily portable to GPUs (unlike HElib) which results in an additional speedup of up to a factor of 10x to offer an overall speedup of 100x.

15:17 [Pub][ePrint]

Given two integers $N_1 = p_1q_1$ and $N_2 = p_2q_2$ with $\\alpha$-bit primes $q_1,q_2$, suppose that the $t$ least significant bits of $p_1$ and $p_2$ are equal. May and Ritzenhofen (PKC 2009) developed a factoring algorithm for $N_1,N_2$ when $t \\geq 2\\alpha + 3$; Kurosawa and Ueda (IWSEC 2013) improved the bound to $t \\geq 2\\alpha + 1$. In this paper, we propose a polynomial-time algorithm in a parameter $\\kappa$, with an improved bound $t = 2\\alpha - O(\\log \\kappa)$; it is the first non-constant improvement of the bound. Both the construction and the proof of our algorithm are very simple; the worst-case complexity of our algorithm is evaluated by an easy argument, without any heuristic assumptions. We also give some computer experimental results showing the efficiency of our algorithm for concrete parameters, and discuss potential applications of our result to security evaluations of existing factoring-based primitives.

15:17 [Pub][ePrint]

A constrained pseudorandom function $F: K \\times X \\to Y$ for family of subsets of $X$ is a function where for any key $k \\in K$ and set $S$ from the family one can efficiently compute a short constrained key $k_S$ which allows to evaluate $F(k,.)$ on all inputs $x\\in S$, while given this key, the outputs on all inputs $x \\notin S$ look random.

Constrained PRFs have been constructed for several families of sets, the most general being the circuit-constrained PRF by Boneh and Waters [Asiacrypt\'13]. Their construction allows for constrained keys $k_C$, where $C$ is a boolean circuit that defines the set $S = \\{ x \\in X | C(x) = 1 \\}$. In their construction the input length and the size of the circuits $C$ for which constrained keys can be computed must be fixed a priori during key generation.

In this paper we construct a constrained PRF that has an unbounded input length and constrained keys can be defined for any set that can be decided by a polynomial-time Turing machine. The only a priori bound we make is on the size of the Turing machines. We discuss applications of our CPRF, such as broadcast encryption where the number of potential receivers need not be fixed at setup (in particular, the length of the keys is independent of the number of parties), and identity-based non-interactive key-agreement between sets of users where again there is no bound on the number of parties that can agree on a shared key.

Our CPRF is simply defined as $F(k,H(x))$ where $F$ is a puncturable PRF (e.g. the GGM construction) and $H$ is a collision-resistant hash function. A constrained key for a Turing machine $M$ is a signature on $M$. At setup we also publish an obfuscated circuit, which on input $M$, a signature $\\sigma$, a value $h$ and a short non-interactive argument of knowledge $\\pi$ outputs $F(k,h)$ if (1) $\\sigma$ is a valid signature on $M$ and (2) $\\pi$ proves knowledge of some $x$ s.t.\\ $H(x)=h$ and $M(x)=1$. For our security proof, we assume extractability obfuscation for the particular circuit just explained.

15:17 [Pub][ePrint]

A non-malleable code protects messages against various classes of tampering.

Informally, a code is non-malleable if the message contained in a tampered

codeword is either the original message, or a completely unrelated one.

Although existence of such codes for

various rich classes of tampering functions is known, \\emph{explicit} constructions

exist only for compartmentalized\'\' tampering functions: \\ie the codeword

is partitioned into {\\em a priori fixed} blocks and each block can {\\em only

be tampered independently}. The prominent examples of this model are the

family of bit-wise independent tampering functions and the split-state

model.

In this paper, for the first time we construct explicit non-malleable codes

against a natural class of non-compartmentalized tampering functions. We

allow the tampering functions to {\\em permute the bits} of the codeword and

(optionally) perturb them by flipping or setting them to 0 or 1. We

construct an explicit, efficient non-malleable code for arbitrarily long

messages in this model (unconditionally).

We give an application of our construction to non-malleable commitments, as

one of the first direct applications of non-malleable codes to

computational cryptography. We show that non-malleable {\\em string} commitments

can be entirely based on\'\' non-malleable {\\em bit} commitments. More

precisely, we show that simply encoding a string using our code, and then

committing to each bit of the encoding using a {\\em CCA-secure bit

commitment} scheme results in a non-malleable string commitment scheme. This

reduction is unconditional, does not require any extra properties from the

bit-commitment such as tag-based\'\' non-malleability, and works even with

physical implementations (which may not imply standard one-way functions).

Further, even given a partially malleable bit commitment scheme which allows

toggling the committed bit (instantiated, for illustration, using a variant

of the Naor commitment scheme under a non-standard assumption on the PRG

involved), this transformation gives a fully non-malleable string commitment

scheme. This application relies on the non-malleable code being explicit.

15:17 [Pub][ePrint]

A non-malleable code protects messages against various classes of tampering.

Informally, a code is non-malleable if the effect of applying any tampering

function on an encoded message is to either retain the message or to replace

it with an unrelated message.

Two main challenges in this area -- apart from establishing

the feasibility against different families of tampering -- are to obtain

{\\em explicit constructions} and to obtain {\\em high-rates} for such

constructions.

In this work, we present a compiler to transform low-rate (in fact, zero

rate) non-malleable codes against certain class of tampering into an

optimal-rate -- i.e., rate 1 -- non-malleable codes against the same class.

If the original code is explicit, so is the new one.

When applied to the family of bit-wise tampering functions, this subsumes

(and greatly simplifies) a recent result of Cheraghchi and Guruswami (TCC

2014). Further, our compiler can be applied to non-malleable codes against

the class of bit-wise tampering and bit-level permutations. Combined with

the rate-0 construction in a companion work, this yields the first explicit

rate-1 non-malleable code for this family of tampering functions.

Our compiler uses a new technique for boot-strapping non-malleability by

introducing errors, that may be of independent interest.

15:17 [Pub][ePrint]

In this paper we revisit the modular inversion hidden number problem and the inversive congruential pseudo random number generator and consider how to more efficiently attack them in terms of fewer samples or outputs. We reduce the attacking problem to finding small solutions of systems of modular polynomial equations of the form $a_i+b_ix_0+c_ix_i+x_0x_i=0 (\\mod p)$, and present two strategies to construct lattices in Coppersmith\'s lattice-based root-finding technique for the solving of the equations. Different from the choosing of the polynomials used for constructing lattices in previous methods, a part of polynomials chosen in our strategies are linear combinations of some polynomials generated in advance and this enables us to achieve a larger upper bound for the desired root. Applying the solving of the above equations to analyze the modular inversion hidden number problem, we put forward an explicit result of Boneh et al. which was the best result so far, and give a further improvement in the involved lattice construction in the sense of requiring fewer samples. Our strategies also give a method of attacking the inversive congruential pseudo random number generator, and the corresponding result is the best up to now.

12:17 [Pub][ePrint]

In this work, we first formalize the notion of dynamic group signatures with distributed traceability, where the capability to trace signatures is distributed among $n$ managers without requiring any interaction. This ensures that only the participation of all tracing managers permits tracing a signature, which reduces the trust placed in a single tracing manager. The threshold variant follows easily from our definitions and constructions. Our model offers strong security requirements.

Our second contribution is a generic construction for the notion which has a concurrent join protocol, meets strong security requirements, and offers efficient traceability, i.e.\\ without requiring tracing managers to produce expensive zero-knowledge proofs for tracing correctness. To dispense with the expensive zero-knowledge proofs required in the tracing, we deploy a distributed tag-based encryption with public verifiability.

Finally, we provide some concrete instantiations, which, to the best of our knowledge, are the first efficient provably secure realizations in the standard model simultaneously offering all the aforementioned properties. To realize our constructions efficiently, we construct an efficient distributed (and threshold) tag-based encryption scheme that works in the efficient Type-III asymmetric bilinear groups. Our distributed tag-based encryption scheme yields short ciphertexts (only 1280 bits at 128-bit security), and is secure under an existing variant of the standard decisional linear assumption.

Our tag-based encryption scheme is of independent interest and is useful for many applications beyond the scope of this paper. As a special case of our distributed tag-based encryption scheme, we get an efficient tag-based encryption scheme in Type-III asymmetric bilinear groups that is secure in the standard model.

2014-10-19
17:13 [Event][New]

Submission: 27 October 2014
From January 19 to January 19
Location: Amsterdam, The Netherlands

2014-10-16
18:17 [Pub][ePrint]

Currently, the Internet Research Task Force (IRTF) discusses requirements for new elliptic curves to be standardized in TLS and other internet protocols. This position paper discusses the view of the members of the ECC Brainpool on these requirements, in particular with respect to hardware implementations.

16:50 [Job][New]

Following recent advances in high throughput sequencing, it can be expected that, in the near future, more and more individuals will have their whole genome extracted, stored and analyzed in a routine fashion. Although this perspective is full of promises in terms of personalized preventive and curative medicine as well as medical research, it should also be acknowledged that the genome of an individual is in essence extremely sensitive data from (at least) a privacy standpoint. Thus, for such personalized medicine-oriented platforms to reliably exist, it is necessary to develop specific counter-measures providing intrinsic protection of the genomic data when manipulated by an IT infrastructure.

In this context, a very promising approach is grounded in homomorphic encryption as a means of computing directly over encrypted data.

The purpose of the present postdoctoral offer is thus to investigate the practical relevance of using homomorphic encryption techniques for privacy-preserving genetic data processing. The main use case will consist in performing requests on a database of genomes represented by their variants. Several scenarios will be investigated in particular with respect to the privacy of the request itself on top of the privacy of the genetic data. In this various scenarios, the candidate is expected to identify the most suitable homomorphic encryption techniques ranging from additive-only (e.g. suitable for private requests on unencrypted data) and multiplicative-only (e.g. suitable for disjunctive public requests on encrypted genetic data) homomorphic encryption systems to the use of the more recent (and more costly) fully homomorphic encryption techniques. The candidate will also be expected to build prototypes for one or more of the above scenarios in order to experimentally demonstrate the practical viability of the solutions, in particular with respect to performances.