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-21
03:17 [Pub][ePrint]

We present the first two-round, two-party general function evaluation protocol that is secure against honest-but-curious adaptive corruption of both parties. In addition, the protocol is incoercible for one of the parties, and fully leakage tolerant. It requires a global (non-programmable) reference string and is based on one way functions and general-purpose indistinguishability obfuscation with sub-exponential security, as well as augmented non-committing encryption.

A Byzantine version of the protocol, obtained by applying the Canetti et al. [STOC 02] compiler, achieves UC security with comparable efficiency parameters, but is no longer incoercible.

2014-10-20
16:33 [Event][New]

Submission: 1 March 2015
From June 11 to June 12
Location: Bucharest, Romania

16:33 [Job][New]

The Computer Security Group in the Department of Computer Science conducts basic and applied research in computer security. The group is supported externally by national funding agencies and Irish and international companies.

Applications are invited for a post-doctoral researcher position (Drone System Security). The selected applicant will be supported in making a submission to the Irish Research Council for a Post-Doctoral Fellowship award. Recipients of this award receive funding of approximately Euro31,000 per annum for two years. The offer is conditional on obtaining this award from the Irish Research Council. The position is open to applicants of any nationality or residency.

The project will consider system security issues in Unmanned Autonomous Vehicles (UAV). The research will focus on platform vulnerabilities and the development of new security mechanisms.

Applicants should have a PhD in Computer Science or a closely related discipline with research interests in computer security, preferably at systems and/or networking level. Candidates are expected to have a high-quality publication record in the related field. Experience with embedded systems development will be an advantage.

The deadline for submitting an application to the Irish Research Council is November 27, 2014, with the successful applicant starting work at UCC in October 2015. Interested candidates should submit a Curriculum Vitae and the name of two referees to Dr. Simon Foley (s.foley (at) cs.ucc.ie) and Dr. Jonathan Petit (j.petit (at) cs.ucc.ie), not later than November 1, 2014.

15:17 [Pub][ePrint]

Deciding \"greater-than\" relations among data items just given their encryptions is at the heart of search algorithms on encrypted data, most notably, non-interactive binary search on encrypted data. Order-preserving encryption provides one solution, but provably provides only limited security guarantees. Two-input functional encryption is another approach, but requires the full power of obfuscation machinery and is currently not implementable.

We construct the first implementable encryption system supporting greater-than comparisons on encrypted data that provides the \"best-possible\" semantic security. In our scheme there is a public algorithm that given two ciphertexts as input, reveals the order of the corresponding plaintexts and nothing else. Our constructions are inspired by obfuscation techniques, but do not use obfuscation. For example, to compare two 16-bit encrypted values (e.g., salaries or age) we only need a 9-way multilinear map. More generally, comparing $k$-bit values requires only a $(k/2+1)$-way multilinear map. The required degree of multilinearity can be further reduced, but at the cost of increasing ciphertext size.

Beyond comparisons, our results give an implementable secret-key multi-input functional encryption scheme for functionalities that can be expressed as (generalized) branching programs of polynomial length and width. Comparisons are a special case of this class, where for $k$-bit inputs the branching program is of length $k+1$ and width $4$.

15:17 [Pub][ePrint]

Leakage-resilient cryptography aims to extend the rigorous guarantees achieved through the provable security paradigm to physical implementations. The constructions and mechanisms designed on basis of this new approach inevitably suffer from an Achilles heel: a bounded leakage assumption is needed. Currently, a huge gap exists between the theory of such designs and their implementation to confirm the leakage resilience in practice. The present work tries to narrow this gap for the leakage-resilient bilinear ElGamal key encapsulation mechanism (BEG-KEM) proposed by Kiltz and Pietrzak in 2010. Our first contribution is a variant of the bounded-leakage and the only-computation-leaks model that is closer to practice. We weaken the restriction on the image size of~the leakage functions in these models and only insist that the inputs to the leakage functions have sufficient min-entropy left, in spite of the leakage, with no limitation on the quantity of this leakage. We provide a novel security reduction for BEG-KEM in this relaxed leakage model using the generic bilinear group axiom. Secondly, we show that a naive implementation of the exponentiation in BEG-KEM makes it impossible to meet the leakage bound. Instead of trying to find an exponentiation algorithm that meets the leakage axiom (which is a non-trivial problem in practice), we propose an advanced scheme, BEG-KEM+, that avoids exponentiation by a secret value, but rather uses an encoding into the base group due to Fouque and Tibouchi. Thirdly, we present a software implementation of BEG-KEM+ based on the Miracl library and provide detailed experimental results. We also assess its (theoretical) resistance against power analysis attacks from a practical perspective, taking into account the state-of-the-art in side-channel cryptanalysis.

15:17 [Pub][ePrint]

HILL Entropy and Metric Entropy are generalizations of the information-theoretic notion of min-entropy to the setting where an adversary is computationally bounded.

The notion of HILL Entropy appeared in the breakthrough construction of a PRG from any one-way function, and has become the most important and most widely used definition of computational entropy. In turn, Metric Entropy which is defined as a relaxation of HILL Entropy, has been proven to be much easier to handle, in particular in the context of computational generalizations of the Dense Model Theorem.

Fortunately, Metric Entropy can be converted, with some loss in quality, to HILL Entropy as shown by Barak, Shaltiel and Wigderson.

In this paper we improve their result, slightly reducing the loss in quality of entropy. Interestingly, our bound is independent of size of the probability space in comparison to the result of Barak et al. Our approach is based on the theory of convex approximation in $L^p$-spaces.

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.