*00:17* [Pub][ePrint]
Simulation-Based Secure Functional Encryption in the Random Oracle Model, by Vincenzo Iovino and Karol Zebrowski
In recent years, there has been great interest in Functional Encryption (FE), a generalization of traditional encryption where a token enables a user to learn a specific function of the encrypted data and nothing else.One of the main lines of research in the area has consisted in studying the security notions for FE and their achievability. This study was initiated by [Boneh et al. -- TCC\'11, O\'Neill -- ePrint\'10] where it was first shown that for FE the indistinguishability-based (IND) security notion is not sufficient in the sense that there are FE schemes that are provably IND-Secure but concretely insecure. For this reason, researchers investigated the achievability of Simulation-based (SIM) security, a stronger notion of security. Unfortunately, the above-mentioned works and others [e.g., Agrawal et al. -- CRYPTO\'13] have shown strong impossibility results for SIM-Security.

One way to overcome these impossibility results was first suggested in the work of Boneh et al. where it was shown how to construct, in the Random Oracle (RO) model, SIM-Secure FE for restricted functionalities and was asked the generalization to more complex functionalities as a challenging problem in the area.

Subsequently, [De Caro et al. -- CRYPTO\'13] proposed a candidate construction of SIM-Secure FE for all circuits in the RO model assuming the existence of an IND-Secure FE scheme for circuits {\\emph {with RO gates}}. This means that the functionality has to depend on the RO, thus it is not fixed in advance as in the standard definitions of FE. Moreover, to our knowledge there are no proposed candidate IND-Secure FE schemes for circuits with RO gates and they seem unlikely to exist.

In this paper, we propose the first constructions of SIM-Secure FE schemes in the RO model that overcome the current impossibility results in different settings. We can do that because we resort to the two following models:

In the public-key setting we assume a bound $q$ on the number of queries but this bound only affects the {\\emph {running-times}} of our encryption and decryption procedures. We stress that our FE schemes in this model are SIM-Secure and have ciphertexts and tokens of {\\emph {constant-size}}, whereas in the standard model, the current SIM-Secure FE schemes for general functionalities [De Caro et al., Gorbunov et al. -- CRYPTO\'12] have ciphertexts and tokens of size growing as the number of queries.

In the symmetric-key setting we assume a timestamp on both ciphertexts and tokens. This is reasonable because in the symmetric-key setting, there is only one user that encrypts and generates tokens. In this model, we provide FE schemes with short ciphertexts and tokens that are SIM-Secure against adversaries asking an {\\em {unbounded}} number of queries.

Both results also assume the RO model, but not functionalities with RO gates and rely on the existence of extractability obfuscation w.r.t. distributional auxiliary input [Boyle et al. -- TCC\'14] (and other standard primitives) secure only in the \\emph{standard model}.

*00:17* [Pub][ePrint]
A Polynomial-Time Key-Recovery Attack on MQQ Cryptosystems, by Jean-Charles Faugere and Danilo Gligoroski and Ludovic Perret and Simona Samardjiska and Enrico Thomae
We investigate the security of the family of MQQ public key cryptosystems using multivariate quadratic quasigroups (MQQ). These cryptosystems show especially good performance properties. In particular, the MQQ-SIG signature scheme is the fastest scheme in the ECRYPT benchmarking of cryptographic systems (eBACS). We show that both the signature scheme MQQ-SIG and the encryption scheme MQQ-ENC, although using different types of MQQs, share a common algebraic structure that introduces a weakness in both schemes. We use this weakness to mount a successful polynomial time key-recovery attack. Our key-recovery attack finds an equivalent key using the idea of so-called good keys that reveals the structure gradually. In the process we need to solve a MinRank problem that, because of the structure, can be solved in polynomial-time assuming some mild algebraic assumptions. We highlight that our theoretical results work in characteristic 2 which

is known to be the most difficult case to address in theory for MinRank attacks. Also, we emphasize that our attack works without any restriction on the number of polynomials removed from the public-key, that is, using the minus modifier. This was not the case for previous MinRank like-attacks against MQ schemes.

From a practical point of view, we are able to break an MQQ-SIG instance of $80$ bits security in less than 2 days,

and one of the more conservative MQQ-ENC instances of 128 bits security in little bit over 9 days. Altogether, our attack shows that it is very hard to design a secure public key scheme based on an easily invertible MQQ structure.

*00:17* [Pub][ePrint]
Search-and-compute on Encrypted Data, by Jung Hee Cheon and Miran Kim and Myungsun Kim
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]
Boosting Linearly-Homomorphic Encryption to Evaluate Degree-2 Functions on Encrypted Data, by Dario Catalano and Dario Fiore
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]
Navigating in the Cayley graph of $SL_2(F_p)$ and applications to hashing, by Lisa Bromberg and Vladimir Shpilrain and Alina Vdovina
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]
A New Method for Decomposition in the Jacobian of Small Genus Hyperelliptic Curves, by Palash Sarkar and Shashank Singh
Decomposing a divisor over a suitable factor basis in the Jacobian of a hyperelliptic curve is a crucial step in anindex 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]
Circulant Matrices and Differential Privacy, by Jalaj Upadhyay
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.