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-12
00:17 [Pub][ePrint]

Private query processing on encrypted databases allows users to obtain data from encrypted databases in such a way that the user\'s sensitive data will be protected from exposure. Given an encrypted database, the users typically submit queries similar to the following examples:

- How many employees in an organization make over 100,000?

- What is the average age of factory workers suffering from leukemia?

Answering the above questions requires one to \\textbf{search} and then \\textbf{compute} over the encrypted databases \\emph{in sequence}. In the case of privately processing queries with only one of these operations, many efficient solutions have been developed using a special-purpose encryption scheme (e.g., searchable encryption). In this paper, we are interested in efficiently processing queries that need to perform both operations on \\emph{fully} encrypted databases. One immediate solution is to use several special-purpose encryption schemes at the same time, but this approach is associated with a high computational cost for maintaining multiple encryption contexts. The other solution is to use a privacy homomorphism (or fully homomorphic encryption) scheme. However, no secure solutions have been developed that meet the efficiency requirements.

In this work, we construct a unified framework so as to efficiently and privately process queries with search\'\' and compute\'\' operations. To this end, the first part of our work involves devising some underlying circuits as primitives for queries on encrypted data. Second, we apply two optimization techniques to improve the efficiency of the circuit primitives. One technique is to exploit SIMD techniques to accelerate their basic operations. In contrast to general SIMD approaches, our SIMD implementation can be applied even when one basic operation is executed. The other technique is to take a large integer ring (\\textit{e.g.}, $\\Z_{2^{t}}$) as a message space instead of a binary field. Even for an integer of $k$ bits with $k>t$, addition can be performed with degree 1 circuits with lazy carry operations.

As a result, search queries including a conjunctive or disjunctive query on encrypted databases of $N$ tuples with $\\mu$-bit attributes require $\\bigo(N \\log \\mu)$ homomorphic operations with depth $\\bigo(\\log \\mu)$ circuits. Search-and-compute queries, such as a conjunctive query with aggregate functions in the same conditions, are processed using $\\bigo(\\mu N)$ homomorphic operations with at most depth $\\bigo(\\log \\mu \\log N)$ circuits. Further, we can process search-and-compute queries using only $\\bigo(N \\log \\mu)$ homomorphic operations with depth $\\bigo(\\log \\mu)$ circuits, even in the large domain. Finally, we present various experiments by varying the parameters, such as the query type and the number of tuples.

00:17 [Pub][ePrint]

We show a technique to transform a linearly-homomorphic encryption into a homomorphic encryption scheme capable of evaluating degree-2 computations on ciphertexts. Our transformation is surprisingly simple and requires only one very mild property on the underlying linearly-homomorphic scheme: the message space must be a public ring in which it is possible to sample elements uniformly at random. This essentially allows us to instantiate our transformation with virtually all existing number-theoretic linearly-homomorphic schemes, such as Goldwasser-Micali, Paillier, or ElGamal. Our resulting schemes achieve circuit privacy and are compact when considering a subclass of degree-2 polynomials in which the number of additions of degree-2 terms is bounded by a constant.

As an additional contribution we extend our technique to build a protocol for outsourcing computation on encrypted data using two (non-communicating) servers. Somewhat interestingly, in this case we can boost a linearly-homomorphic scheme to support the evaluation of any degree-2 polynomial while achieving full compactness.

00:17 [Pub][ePrint]

Cayley hash functions are based on a simple idea of using a pair of

(semi)group elements, $A$ and $B$, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of elements in the (semi)group. In this paper, we focus on hashing with $2 \\times 2$ matrices over $F_p$. Since there are many known pairs of $2 \\times 2$ matrices over $Z$ that generate a free monoid, this yields numerous pairs of matrices over $F_p$, for a sufficiently large prime $p$, that are candidates for collision-resistant hashing. However, this trick can backfire\", and lifting matrix entries to $Z$ may facilitate finding a collision. This lifting attack\" was successfully used by Tillich and Z\\\'emor in the special case where two matrices $A$ and $B$ generate (as a monoid) the whole monoid $SL_2(\\Z_+)$. However, in this paper we show that the situation with other, similar\", pairs of matrices from $SL_2(Z)$ is different, and the lifting attack\" can (in some cases) produce collisions in the {\\it group} generated by $A$ and $B$, but not in the positive {\\it monoid}. Therefore, we argue that for these pairs of matrices, there are no known attacks at this time that would affect security of the corresponding hash functions. We also give explicit lower bounds on the length of collisions for hash functions corresponding to some particular pairs of matrices from $SL_2(F_p)$.

00:17 [Pub][ePrint]

Decomposing a divisor over a suitable factor basis in the Jacobian of a hyperelliptic curve is a crucial step in an

index calculus algorithm for the discrete log problem in the Jacobian. For small genus curves, in the year 2000, Gaudry had proposed

a suitable factor basis and a decomposition method. In this work, we provide a new method for decomposition over the same factor

basis. The advantage of the new method is that it admits a sieving technique which removes smoothness checking of polynomials

required in Gaudry\'s method. Also, the total number of additions in the Jacobian required by the new method is less than

that required by Gaudry\'s method. The new method itself is quite simple and we present some example decompositions and timing

results of our implementation of the method using Magma.

00:17 [Pub][ePrint]

The main bottleneck affecting the efficiency of all known fully homomorphic encryption (FHE) schemes is Gentry\'s bootstrapping procedure, which is required to refresh noisy ciphertexts and keep computing on encrypted data. Bootstrapping in the latest implementation of FHE, the HElib library of Halevi and Shoup (Crypto 2014), requires about half an hour. We present a new method to homomorphically compute simple bit operations, and refresh (bootstrap) the resulting output, which runs on a personal computer in just about half a second. We present a detailed technical analysis of the scheme (based on the worst-case hardness of standard lattice problems) and report on the performance of our prototype implementation.

00:17 [Pub][ePrint]

Multi-precision squaring is a crucial operation for implementation of Elliptic Curve Cryptography. Particularly, when it comes to embedded processors, the operation should be designed carefully to execute expensive ECC operation on resource constrained devices. In order to bridge the gap between high overheads and limited computation capabilities, we present optimized Karatsuba squaring method for embedded processors. Traditional squaring computation can be divided into two sub-squaring and one sub-multiplication parts. Firstly we compute the multiplication part with the fastest Karatsuba multiplication and then remaining two squaring parts are conducted with the fastest sliding block doubling squaring. Proposed method sets the new speed records for multi-precision squaring, improving the execution time by up to 8.49% comparing to the best known works.

00:17 [Pub][ePrint]

This paper resolves an open problem raised by Blocki {\\it et al.} (FOCS 2012), i.e., whether other variants of the Johnson-Lindenstrauss transform preserves differential privacy or not? We prove that a general class of random projection matrices that satisfies the Johnson-Lindenstrauss lemma also preserves differential privacy. This class of random projection matrices requires only $n$ Gaussian samples and $n$ Bernoulli trials and allows matrix-vector multiplication in $O(n \\log n)$ time. In this respect, this work unconditionally improves the run time of Blocki {\\it et al.} (FOCS 2012) without using the graph sparsification trick of Upadhyay (ASIACRYPT 2013). For the metric of measuring randomness, we stick to the norm used by earlier researchers who studied variants of the Johnson-Lindenstrauss transform and its applications, i.e., count the number of random samples made. In concise, we improve the sampling complexity by quadratic factor, and the run time of cut queries by an $O(n^{o(1)})$ factor and that of covariance queries by an $O(n^{0.38})$ factor.

Our proof for both the privacy and utility guarantee uses several new ideas. In order to improve the dimension bound, we use some known results from the domain of statistical model selection. This makes our proof short and elegant, relying just on one basic concentration inequality. For the privacy proof, even though our mechanism closely resembles that of Blocki {\\it et al.} (FOCS 2012) and Upadhyay (ASIACRYPT 2013), we cannot use their proof idea. This is because the projection matrices we are interested in introduces non-trivial correlations between any two rows of the published matrix, and, therefore, we cannot invoke the composition theorem of Dwork, Rothblum and Vadhan (STOC 2009). We argue that the published matrix is not $r$-multivariate distribution; rather one matrix-variate distribution. We compute the distribution of the published matrix and then prove it preserves differential privacy.

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

Often S-boxes are the only nonlinear component in a block cipher and as such play an important role in ensuring its resistance to cryptanalysis. Cryptographic properties and constructions of S-boxes have been studied for many years. The most common techniques for constructing S-boxes are: algebraic constructions, pseudo-random generation and a variety of heuristic approaches. Among the latter are the genetic algorithms. In this paper, a genetic algorithm working in a reversed way is proposed. Using the algorithm we can rapidly and repeatedly generate a large number of strong bijective S-boxes of each dimension from $(8 \\times 8)$ to $(16 \\times 16)$, which have sub-optimal properties close to the ones of S-boxes based on finite field inversion, but have more complex algebraic structure and possess no linear redundancy.

15:17 [Pub][ePrint]

As intended by its name, Physically Unclonable Functions (PUFs) are considered as an ultimate solution to deal with insecure stor- age, hardware counterfeiting, and many other security problems. How- ever, many different successful attacks have already revealed vulnera- bilities of certain digital intrinsic PUFs. Although settling-state-based PUFs, such as SRAM PUFs, can be physically cloned by semi-invasive and fully-invasive attacks, successful attacks on timing-based PUFs were so far limited to modeling attacks. Such modeling requires a large sub- set of challenge-response-pairs (CRP) to successfully model the targeted PUF. In order to provide a final security answer, this paper proves that all arbiter-based (i.e. controlled and XOR-enhanced) PUFs can be com- pletely and linearly characterized by means of photonic emission analy- sis. Our experimental setup is capable of measuring every PUF-internal delay with a resolution of 6 picoseconds. Due to this resolution we in- deed require only the theoretical minimum number of linear independent equations (i.e. physical measurements) to directly solve the underlying inhomogeneous linear system. Moreover, we neither require to know the actual PUF challenges nor the corresponding PUF responses for our physical delay extraction. On top of that devastating result, we are also able to further simplify our setup for easier physical measurement han- dling. We present our practical results for a real arbiter PUF implemen- tation on a Complex Programmable Logic Device (CPLD) from Altera manufactured in a 180 nanometer process.

15:17 [Pub][ePrint]

Public key infrastructures (PKIs) enable users to look up and verify one another\'s public keys based on identities.

Current approaches to PKIs are vulnerable because they do not offer sufficiently strong guarantees of \\emph{identity retention}; that is, they do not effectively prevent one user from registering a public key under another\'s already-registered identity.

In this paper, we leverage the consistency guarantees provided by cryptocurrencies such as Bitcoin and Namecoin to build a PKI that ensures identity retention.

Our system, called Certcoin, has no central authority and thus requires the use of secure distributed dictionary data structures to provide efficient support for key lookup.

12:30 [Job][Update]

This is a permanent research and teaching position in one of UK\\\'s top research-led universities. The Security and Privacy group undertakes research in all fields related to information and cyber security, privacy, cryptography, etc.