*19:17* [Pub][ePrint]
Symmetric Digit Sets for Elliptic Curve Scalar Multiplication without Precomputation, by Clemens Heuberger and Michela Mazzoli
We describe a method to perform scalar multiplication on two classes ofordinary elliptic curves, namely $E: y^2 = x^3 + Ax$ in prime characteristic

$p\\equiv 1$ mod~4, and $E: y^2 = x^3 + B$ in prime characteristic $p\\equiv 1$

mod 3. On these curves, the 4-th and 6-th roots of unity act as (computationally

efficient) endomorphisms. In order to optimise the scalar multiplication, we consider a width-$w$-NAF (non-adjacent form) digit expansion of positive integers to the complex base of $\\tau$, where $\\tau$ is a zero of the characteristic polynomial $x^2 - tx + p$ of the Frobenius endomorphism associated to the curve. We provide a precomputationless algorithm by means of a convenient factorisation of the unit group of residue classes modulo $\\tau$ in the endomorphism ring, whereby we construct a digit set consisting of powers of subgroup generators, which are chosen as efficient endomorphisms of the curve.

*19:17* [Pub][ePrint]
A reduction of semigroup DLP to classic DLP, by Matan Banin and Boaz Tsaban
We present a polynomial-time reduction of the discrete logarithm problem in any periodic (a.k.a. torsion)semigroup (SGDLP) to the same problem in a subgroup of the same semigroup.

It follows that SGDLP can be solved in polynomial time by quantum computers, and that

SGDLP has subexponential algorithms whenever the classic DLP in the corresponding groups has subexponential algorithms.

*19:17* [Pub][ePrint]
Key Derivation Without Entropy Waste, by Yevgeniy Dodis and Krzysztof Pietrzak and Daniel Wichs
We revisit the classical problem of converting an imperfect source of randomness into a usable cryptographic key. Assume that we have some cryptographic application $P$ that expects a uniformly random $m$-bit key $R$ and ensures that the best attack (in some complexity class) against $P(R)$ has success probability at most $\\delta$. Our goal is to design a key-derivation function (KDF) $h$ that converts any random source $X$ of min-entropy $k$ into a sufficiently ``good\'\' key $h(X)$,guaranteeing that $P(h(X))$ has comparable security $\\delta\'$ which is `close\' to $\\delta$.

Seeded randomness extractors provide a generic way to solve this problem for \\emph{all} applications $P$, with resulting security $\\delta\' = O(\\delta)$, provided that we start with entropy $k\\ge m+2\\logdel-O(1)$. By a result of Radhakrishnan and Ta-Shma, this bound on $k$ (called the ``RT-bound\'\') is also known to be tight in general. Unfortunately, in many situations the loss of $2\\logdel$ bits of entropy is unacceptable. This motivates the study KDFs with less entropy waste by placing some restrictions on the source $X$ or the application $P$.

In this work we obtain the following new positive and negative results in this regard:

- Efficient samplability of the source $X$ does not help beat the RT-bound for general applications. This resolves the SRT (samplable RT) conjecture of Dachman-Soled et al.~\\cite{DGKM12} in the affirmative, and also shows that the existence of computationally-secure extractors beating the RT-bound implies the existence of one-way functions.

- We continue in the line of work initiated by Barak et al. \\cite{BDK+11} and construct new information-theoretic KDFs which beat the RT-bound for large but restricted classes of applications. Specifically, we design efficient KDFs that work for all unpredictability applications $P$ (e.g., signatures, MACs, one-way functions, etc.) and can either: (1) extract \\emph{all} of the entropy $k = m$ with a very modest security loss $\\delta\'=O(\\delta\\cdot \\log (1/\\delta))$, or alternatively, (2) achieve essentially optimal security $\\delta\' = O(\\delta)$ with a very modest entropy loss $k \\ge m+\\log\\log(1/\\delta)$. In comparison, the best prior results from \\cite{BDK+11} for this class of applications would only guarantee $\\delta\'=O(\\sqrt{\\delta})$ when $k=m$, and would need $k\\ge m+\\logdel$ to get $\\delta\'=O(\\delta)$.

- The weaker bounds of \\cite{BDK+11} hold for a larger class of so-called ``square-friendly\'\' applications (which includes all unpredictability, but also some important indistinguishability, applications). Unfortunately, we show that these weaker bounds are tight for the larger class of applications.

- We abstract out a clean, information-theoretic notion of $(k,\\delta,\\delta\')$-unpredictability extractors, which guarantee ``induced\'\' security $\\delta\'$ for any $\\delta$-secure unpredictability application $P$, and characterize the parameters achievable for such unpredictability extractors. Of independent interest, we also relate this notion to the previously-known notion of (min-entropy) condensers, and improve the state-of-the-art parameters for such condensers.

*19:17* [Pub][ePrint]
An Approach to Reduce Storage for Homomorphic Computations, by Jung Hee Cheon and Jinsu Kim
We introduce a hybrid homomorphic encryption by combining public key encryption (PKE) and somewhat homomorphic encryption (SHE) to reduce storage for most applications of somewhat or fully homomorphic encryption (FHE). In this model, one encrypts messages with a PKE and computes on encrypted data using a SHE or a FHE after homomorphic decryption. To obtain efficient homomorphic decryption, our hybrid schemes is constructed by combining IND-CPA PKE schemes without complicated message paddings with SHE schemes with large integer message space. Furthermore, we remark that if the underlying PKE is multiplicative on a domain closed under addition and multiplication, this scheme has an important advantage that one can evaluate a polynomial of arbitrary degree without recryption.

We propose such a scheme by concatenating ElGamal and Goldwasser-Micali scheme over a ring $\\Z_N$ for a composite integer $N$ whose message space is $\\Z_N^\\times$.

To be used in practical applications, homomorphic decryption of the base PKE is too expensive. We accelerate the homomorphic evaluation of the decryption by introducing a method to reduce the degree of exponentiation circuit at the cost of additional public keys. Using same technique, we give an efficient solution to the open problem~\\cite{KLYC13} partially.

As an independent interest, we obtain another generic conversion method from private key SHE to public key SHE. Differently from Rothblum~\\cite{RothTCC11}, it is free to choose the message space of SHE.

*19:17* [Pub][ePrint]
PUF-Based RFID Authentication Secure and Private under Complete Memory Leakage, by Daisuke Moriyama and Shin\'ichiro Matsuo and Moti Yung
RFID tags are getting their presence noticeable on smartphones,credit cards, toll payment devices, and other objects. They are

expected to become an important tool for e-commerce, logistics,

point-of-sale transactions, and so on, representing ``things\'\' and

``human holding things\'\' in transactions. Since a huge amount of tags are expected to be needed to be attached to various ``objects,\'\' a low-cost tag manufacturing is necessary. Thus, it is hard to imagine they will implement hardware protection mechanisms (like co-processor, TPMs). Therefore, side-channel (leakage) attacks are a critical threat. Another threat that is well known in the RFID topic is tag tracing and violation of privacy.

In this paper, we consider physically unclonable functions (PUFs) as tamper resilient building block and propose security model with memory leaking adversary, trying to violate security and privacy of tags (we note that PUFs are structure-less and there is a hope they can be put on top of RFID chips more so than TPMs). We then design the first provably secure and provably private RFID authentication protocol withstanding information leakage from the non-volatile memory of the tag, and provides the two properties of: (1) security against impersonation, and (2) privacy protection against tag tracing.

*19:17* [Pub][ePrint]
Cryptanalysis of Zorro, by Jian Guo and Ivica Nikolic and Thomas Peyrin and Lei Wang
At CHES 2013 was presented a new block cipher called Zorro. Although it uses only 4 S-boxes per round, the designers showed the resistance of the cipher against various attacks, and concluded the cipher has a large security margin. In this paper, we give a key recovery attack on the full cipher in the single-key model that works for $2^{64}$ out of $2^{128}$ keys. Our analysis is based precisely on the fact that the non-linear layer has only 4 S-boxes. We exploit this twice in a two-stage attack: first, we show that Zorro has an equivalent description that does not have constants in the rounds, and then, we launch an internal differential attack on the newly described cipher. With computer verifications we confirm the correctness of the analysis.Our attack is the first to use internal differentials for block ciphers, thus we adapt Daemen\'s attack on Even-Mansour construction

to the case of internal differentials (instead of differentials), which allows us to recovery to full key.

This work provides as well insights on alternative descriptions of general Zorro-type ciphers (incomplete non-linear layers),

the importance of well chosen constants, and the advantages of Daemen\'s attack.

*19:17* [Pub][ePrint]
Method to secure data in the cloud while preserving summary statistics, by Sanchita Barman, Bimal Roy
In this paper we propose a method which will preserve sum-mary statistics of data organized in a two way table. We have shown that

fully homomorphic encryption is a powerful solution. However it has a

number of disadvantages which makes it impractical. We have proposed

a Restricted homomorphic encryption method which uses Pailier encryp-

tion and order preserving encryption. This new method can be used for

practical purposes owing to it\'s efficiency in terms of both speed and

storage.

*19:17* [Pub][ePrint]
Practical Privacy-Preserving Range and Sort Queries with Update-Oblivious Linked Lists, by Erik-Oliver Blass and Travis Mayberry and Guevara Noubir
We present RASP, a new protocol for privacy-preserving rangesearch and sort queries on encrypted data in the face of an

untrusted data store. The contribution of RASP over related work

is twofold: first, RASP improves privacy guarantees by ensuring

that after a query for range [a,b] any new record added to the

data store is indistinguishable from random, even if the new

record falls within range [a,b]. Second, RASP is highly

practical, abstaining from expensive asymmetric cryptography and

bilinear pairings. Instead, RASP only relies on hash and block

cipher operations. The main idea of RASP is to build upon a new

update-oblivious bucket-based data structure. We allow for data

to be added to buckets without leaking into which bucket it has

been added. As long as a bucket is not explicitly queried, the

data store does not learn anything about bucket

contents. Furthermore, no information is leaked about data

additions following a query. Besides formally proving RASP\'s

privacy, we also present a practical evaluation of RASP using

Amazon Dynamo.