International Association
for Cryptologic Research

Web applications rely on servers to store and process confidential information. However, anyone who gains access to the server (e.g., an attacker, a curious administrator, or a government) can obtain all of the data stored there. This paper presents Mylar, a platform that provides end-to-end encryption to web applications. Mylar protects the confidentiality of sensitive data fields against attackers that gained access to servers. Mylar stores sensitive data encrypted on the server, and decrypts that data only in users’ browsers. Mylar addresses three challenges in making this approach work. First, Mylar allows the server to perform keyword search over encrypted documents, even if the documents are encrypted with different keys. Second, Mylar allows users to share keys securely in the presence of an active adversary. Finally, Mylar ensures that client-side application code is authentic, even if the server is malicious. Results with a prototype of Mylar built on top of the Meteor framework are promising: porting 6 applications required changing just 36 lines of code on average, and the performance overheads are modest, amounting to a 17% throughput loss and a 50 ms latency increase for sending a message in a chat application.

We propose multi-party computation protocols for securely computing a linear regression model from a training dataset whose columns are distributed among several parties. Our solution enables organizations to collaborate in the construction of a predictive model while keeping their training data private. Our approach is based on a hybrid MPC protocol combining garbled circuits with an offline phase enabled by a semi-trusted external party. As part of our contribution, we evaluate several algorithms and implementations for solving systems of linear equations using garbled circuits. Experiments conducted with an implementation of our protocols show that our approach leads to highly scalable solutions that can solve data analysis problems with one million records and one hundred features in less than one hour.

This paper proposes an IBE scheme with tight security reduction and constant-size master public key. This (partially) solves the first open problem posed by Chen and Wee [CRYPTO, 2013]. Concretely, the IBE scheme is built based on Wee's petit IBE scheme [TCC, 2016] in the composite-order bilinear group whose order is product of four primes. The size of master public key, ciphertexts, and secret keys are not only constant-size but also nearly optimal as Wee's [TCC, 2016]. We prove the adaptive security based on the decisional subgroup assumption with security loss $\mathcal{O}(\log \lambda)$ where $\lambda$ is the security parameter. Therefore we also make progress on the second open problem from Chen and Wee [CRYPTO, 2013].

In this paper, we propose a parallel implementation of LDSieve, a recently published sieving algorithm for the SVP, which achieves the best theoretical complexity to this day, on parallel shared-memory systems. In particular, we propose a scalable parallel variant of LDSieve that is probabilistically lock-free and relaxes the properties of the algorithm to favour parallelism. We use our parallel variant of LDSieve to answer a number of important questions pertaining to the algorithm. In particular, we show that LDSieve scales fairly well on sharedmemory systems and uses much less memory than HashSieve on random lattices, for the same or even less execution time.

We present a provably-secure blockchain protocol based on “proof of stake.” As far as we are aware, this is the first proof of stake blockchain protocol which provides rigorous security guarantees. The security properties of the system are analyzed in the model of [9] and are comparable to the ones possessed by the bitcoin blockchain protocol which utilizes proof of work. Furthermore, an incentive mechanism for the protocol is also proposed.

Lattice-based cryptography has recently emerged as a prime candidate for efficient and secure post-quantum cryptography. The two classical hard problems underlying its security are the shortest vector problem (SVP) and the closest vector problem (CVP). For SVP, lattice sieving currently has the best asymptotic time complexity: in high dimensions $d$, sieving can solve SVP in time $2^{0.292d + o(d)}$, using $2^{0.208d + o(d)}$ memory [Becker-Ducas-Gama-Laarhoven, SODA'16]. The best heuristic time complexity to date for CVP is $2^{0.377d + o(d)}$, using $2^{0.292d + o(d)}$ memory [Becker-Gama-Joux, ANTS'14].

In practice, the large memory footprint makes it problematic to run sieving directly on high-dimensional lattices, and perhaps the most promising application of such algorithms is as part of a hybrid with lattice enumeration. It is well-known that a faster algorithm for solving the closest vector problem with preprocessing (CVPP) in low dimensions could be used to speed up enumeration for SVP or CVP in high dimensions, but so far it is not even clear whether the fastest sieving methods can be used to solve CVP at all.

Our contributions are two-fold. First, we show that with sieving, we can solve CVP with similar costs as SVP, improving upon the results of Becker-Gama-Joux. Our second and main contribution is that with lattice sieving we can construct a truly efficient CVPP solver. Heuristically, we can for instance solve CVPP in $2^{d/4 + o(d)}$ time and space, while the time complexity can be reduced to as little as $2^{\varepsilon d + o(d)}$ for arbitrary $\varepsilon > 0$ at the cost of $(1/\varepsilon)^{O(d)}$ space. Preliminary experiments support these claims, and in dimension $50$ we roughly obtain a factor $2000$ speedup for CVPP compared to solving SVP with sieving. This may be a first step towards a practical hybrid between enumeration and sieving.

The existence of Almost Perfect Nonlinear (APN) permutations operating on an even number of variables was a long-standing open problem, until an example with six variables was exhibited by Dillon et al. in 2009. However it is still unknown whether this example can be generalised to any even number of inputs. In a recent work, Perrin et al. described an infinite family of permutations, named butterflies, operating on (4k+2) variables and with differential uniformity at most 4, which contains the Dillon APN permutation. In this paper, we generalise this family, and we completely solve the two open problems raised by Perrin et al.. Indeed we prove that all functions in this larger family have the best known nonlinearity. We also show that this family does not contain any APN permutation besides the Dillon permutation, implying that all other functions have differential uniformity exactly four.

Ever since Keccak won the SHA3 competition, sponge-based constructions are being suggested for many different applications, including pseudo-random number generators (PRNGs). Sponges are very desirable, being well studied, increasingly efficient to implement and simplistic in their design. The initial construction of a sponge-based PRNG (Bertoni et al. CHES 2010) based its security on the well known sponge indifferentiability proof in the random permutation model and provided no forward security.

Since then, another improved sponge-based PRNG has been put forward by Ga\v{z}i and Tessaro (Eurocrypt 2016) who point out the necessity for a public seed to prevent an adversarial sampler from gaining non-negligible advantage. The authors further update the security model of Dodis et al. (CCS 2013) to accommodate a public random permutation, modelled in the ideal cipher model, and how this affects the notions of security.

In this paper we introduce \reverie, an improved and practical, sponge-like pseudo-random number generator together with a formal security analysis in the PRNG with input security model of Dodis et al. with the modifications of the Ga\v{z}i and Tessaro paper.

We prove that \reverie is \emph{robust} when used with a public random permutation; robustness is the strongest notion of security in the chosen security model. Robustness is proved by establishing two weaker notions of security, preserving and recovering security, which together, can be shown to imply the robustness result. The proofs utilise the H-coefficient technique that has found recent popularity in this area; providing a very useful tool for proving the generator meets the necessary security notions.

The hardness of finding short vectors in ideals of cyclotomic number fields (Ideal-SVP) serves as the worst-case hypothesis underlying the security of numerous cryptographic schemes, including key-exchange, public-key encryption and fully-homomorphic encryption. A series of recent works has shown that, for large approximation factors, Principal Ideal-SVP is not as hard as finding short vectors in general lattices. Namely, there exists a quantum polynomial time algorithm for an approximation factor of $\exp(\tilde O(\sqrt n))$, even in the worst-case. Some schemes were broken, but more generally this exposed an unexpected hardness gap between general lattices and some structured ones, and called into question the exact security of various assumption over structured lattices.

In this work, we generalize the previous result to general ideals. We show an efficient way of finding a close enough principal multiple of any ideal by exploiting the classical theorem that, in our setting, the class-group is annihilated by the (Galois-module action of) the so-called Stickelberger ideal. Under some plausible number-theoretical hypothesis, we conclude that worst-case Ideal-SVP in this same set-up --- choice of ring, and approximation factor $\exp(\tilde O(\sqrt n))$ --- is also solvable in quantum polynomial time.

Although it is not yet clear whether the security of further cryptosystems is directly affected, we contribute novel ideas to the cryptanalysis of schemes based on structured lattices. Moreover, our result shows a deepening of the gap between general lattices and structured one.

This paper presents an architecture for a discrete, high-entropy hardware random number generator. Because it is constructed out of simple hardware components, its operation is transparent and auditable. Using avalanche noise, a nondeterministic physical phenomenon, the circuit is inherently probabilistic and resists adversarial control. Furthermore, because it compares the outputs from two matched noise sources, it rejects environmental disturbances like power supply ripple. The resulting hardware produces more than 0.98 bits of entropy per sample, is inexpensive, has a small footprint, and can be disabled to conserve power when not in use.

Secure multi-party computation (MPC) allows multiple parties to perform a joint computation without disclosing their private inputs. Many real-world joint computation use cases, however, involve data analyses on very large data sets, and are implemented by software engineers who lack MPC knowledge. Moreover, the collaborating parties -- e.g., several companies -- often deploy different data analytics stacks internally. These restrictions hamper the real-world usability of MPC. To address these challenges, we combine existing MPC frameworks with data-parallel analytics frameworks by extending the Musketeer big data workflow manager. Musketeer automatically generates code for both the sensitive parts of a workflow, which are executed in MPC, and the remaining portions of the computation, which run on scalable, widely-deployed analytics systems. In a prototype use case, we compute the Herfindahl-Hirschman Index (HHI), an index of market concentration used in antitrust regulation, on an aggregate 156GB of taxi trip data over five transportation companies. Our implementation computes the HHI in about 20 minutes using a combination of Hadoop and VIFF, while even ``mixed mode'' MPC with VIFF alone would have taken many hours. Finally, we discuss future research questions that we seek to address using our approach.

This paper proposes MSKT-ORAM, an efficient multiple server ORAM construction, to protect a client’s access pattern to outsourced data. MSKT-ORAM organizes each of the server storage as a k-ary tree and adopts XOR based PIR and a novel delayed eviction technique to optimize both the data query and data eviction process. MSKT-ORAM is proved to protect the data access pattern privacy at a failure probability of $2^{80}$ when $k\geq 128$. Meanwhile, given constant local storage, when $N$ (i.e., the total number of outsourced data blocks) ranges from $2^{16}$ to $2^{34}$ and data block size $B\geq 20$KB, the communication cost of MSKT-ORAM is only $22$ to $46$ data blocks. Asymptotical analysis and detailed implementation comparisons are conducted to show that MSKT-ORAM achieves better communication, storage and access delay in practical scenario over the compared state-of-the-art ORAM schemes.

In this paper we explore the intriguing factors involved in the non one-one nature of the RC4, and explore new techniques and present interesting findings regarding the same. The first part of this paper studies near colliding keys of the RC4, and discusses how these keys are localized into clusters in the key-space. The second part of this paper proposes a new collision search algorithm specifically for 16-byte keys. It is generally the practice to choose the byte that differs between two keys to be near the end of the key. However, this is not necessary for 16-byte keys, and the second part of this paper discusses how this may be used to grant us an additional degree of control.

The Naor-Yung paradigm (Naor and Yung, STOC '90) allows to generically boost security under chosen-plaintext attacks (CPA) to security against chosen-ciphertext attacks (CCA) for public-key encryption (PKE) schemes. The main idea is to encrypt the plaintext twice (under independent public keys), and to append a non-interactive zero-knowledge (NIZK) proof that the two ciphertexts indeed encrypt the same message. Later work by Camenisch, Chandran, and Shoup (Eurocrypt '09) and Naor and Segev (Crypto '09 and SIAM J. Comput. '12) established that the very same techniques can also be used in the settings of key-dependent message (KDM) and key-leakage attacks (respectively).

In this paper we study the conditions under which the two ciphertexts in the Naor-Yung construction can share the same random coins. We find that this is possible, provided that the underlying PKE scheme meets an additional simple property. The motivation for re-using the same random coins is that this allows to design much more efficient NIZK proofs. We showcase such an improvement in the random oracle model, under standard complexity assumptions including Decisional Diffie-Hellman, Quadratic Residuosity, and Subset Sum. The length of the resulting ciphertexts is reduced by 50\%, yielding truly efficient PKE schemes achieving CCA security under KDM and key-leakage attacks.

As an additional contribution, we design the first PKE scheme whose CPA security under KDM attacks can be directly reduced to (low-density instances of) the Subset Sum assumption. The scheme supports key-dependent messages computed via any affine function of the secret key.

Group encryption (GE) is the natural encryption analogue of group signatures in that it allows verifiably encrypting messages for some anonymous member of a group while providing evidence that the receiver is a properly certified group member. Should the need arise, an opening authority is capable of identifying the receiver of any ciphertext. As introduced by Kiayias, Tsiounis and Yung (Asiacrypt'07), GE is motivated by applications in the context of oblivious retriever storage systems, anonymous third parties and hierarchical group signatures. This paper provides the first realization of group encryption under lattice assumptions. Our construction is proved secure in the standard model (assuming interaction in the proving phase) under the Learning-With-Errors (LWE) and Short-Integer-Solution (SIS) assumptions. As a crucial component of our system, we describe a new zero-knowledge argument system allowing to demonstrate that a given ciphertext is a valid encryption under some hidden but certified public key, which incurs to prove quadratic statements about LWE relations. Specifically, our protocol allows arguing knowledge of witnesses consisting of $\mathbf{X} \in \mathbb{Z}_q^{m \times n}$, $\mathbf{s} \in \mathbb{Z}_q^n$ and a small-norm $\mathbf{e} \in \mathbb{Z}^m$ which underlie a public vector $\mathbf{b}=\mathbf{X} \cdot \mathbf{s} + \mathbf{e} \in \mathbb{Z}_q^m$ while simultaneously proving that the matrix $\mathbf{X} \in \mathbb{Z}_q^{m \times n}$ has been correctly certified. We believe our proof system to be useful in other applications involving zero-knowledge proofs in the lattice setting.

In this paper, we analyze the security of round-reduced versions of the Keccak hash function family. Based on the work pioneered by Aumasson and Meier, and Dinur et al., we formalize and develop a technique named linear structure, which allows linearization of the underlying permutation of Keccak for up to 3 rounds with large number of variable spaces. As a direct application, it extends the best zero-sum distinguishers by 2 rounds without increasing the complexities. We also apply linear structures to preimage attacks against Keccak. By carefully studying the properties of the underlying Sbox, we show bilinear structures and find ways to convert the information on the output bits to linear functions on input bits. These findings, combined with linear structures, lead us to preimage attacks against up to 4-round Keccak with reduced complexities. An interesting feature of such preimage attacks is low complexities for small variants. As extreme examples, we can now find preimages of 3-round SHAKE128 with complexity 1, as well as the first practical solutions to two 3-round instances of Keccak challenge. Both zero-sum distinguishers and preimage attacks are verified by implementations. It is noted that the attacks here are still far from threatening the security of the full 24-round Keccak.

In this paper, we bridge the gap between structure-preserving signatures (SPSs) and fully structure-preserving signatures (FSPSs). In SPSs, all the messages, signatures, and verification keys consist only of group elements, while in FSPSs, even signing keys are required to be a collection of group elements. To achieve our goal, we introduce two new primitives called trapdoor signature and signature with auxiliary key, both of which can be derived from SPSs. By carefully combining both primitives, we obtain generic constructions of FSPSs from SPSs. Upon instantiating the above two primitives, we get many instantiations of FSPS with unilateral and bilateral message spaces. Different from previously proposed FSPSs, many of our instantiations also have the automorphic property, i.e., a signer can sign his own verification key. As by-product results, one of our instantiations has the shortest verification key size, signature size, and lowest verification cost among all previous constructions based on standard assumptions, and one of them is the first FSPS scheme in the type I bilinear groups.

This paper focuses on building a tweakable blockcipher from a classical blockcipher whose input and output wires all have a size of $n$ bits. The main goal is to achieve full $2^n$ security. Such a tweakable blockcipher was proposed by Mennink at FSE'15, and it is also the only tweakable blockcipher so far that claimed full $2^n$ security to our best knowledge. However, we find a key-recovery attack on Mennink's proposal (in the proceeding version) with a complexity of about $2^{n/2}$ adversarial queries. The attack well demonstrates that Mennink's proposal has at most $2^{n/2}$ security, and therefore invalidates its security claim. In this paper, we study a construction of tweakable blockciphers denoted as $\tilde{\mathbb E}[s]$ that is built on $s$ invocations of a blockcipher and additional simple XOR operations. As proven in previous work, at least two invocations of blockcipher with linear mixing are necessary to possibly bypass the birthday-bound barrier of $2^{n/2}$ security, we carry out an investigation on the instances of $\tilde{\mathbb E}[s]$ with $s \ge 2$, and find $32$ highly efficient tweakable blockciphers $\widetilde{E1}$, $\widetilde{E2}$, $\ldots$, $\widetilde{E32}$ that achieve $2^n$ provable security. Each of these tweakable blockciphers uses two invocations of a blockcipher, one of which uses a tweak-dependent key generated by XORing the tweak to the key (or to a secret subkey derived from the key). We point out the provable security of these tweakable blockciphers is obtained in the ideal blockcipher model due to the usage of the tweak-dependent key.

There is growing interest in the security community in functions which are moderately hard to compute on a normal single-processor machine, but which cannot be computed at a significantly lower (hardware/energy) cost on dedicated hardware. Such functions are required for password-hashing to prevent brute-force attacks implemented on custom circuits or in proofs-of-work for decentralized cryptocurrencies.

Towards this goal memory-hard functions (MHF) have been suggested, leveraging the fact that -- unlike computation -- memory cost on custom hardware is not cheaper than on general architectures. MHFs come in two flavors, data-dependent and data independent MHFs, the former are potentially easier to construct, but they succumb to side-channel attacks.

Data independent MHFs can be specified by a directed acyclic graph (DAG) $G_n$ on $n$ nodes of constant indegree and a single sink, the function is then defined as the label of the sink, where a label of a node is computed as the hash of the labels of its parents and the function input. The quality of the memory-hard function is captured by two parameters on the pebbling complexity of the underlying graph:

- The parallel cumulative pebbling complexity $\Pi^{\parallel}_{cc}(G_n)$ must be as high as possible (to ensure that the amortized cost of computing the function on dedicated hardware is dominated by the cost of memory).

- The sequential space-time pebbling complexity $\Pi_{st}(G_n)$ should be as close as possible to $\Pi^{\parallel}_{cc}(G_n)$ (to ensure that using many cores in parallel and amortizing over many instances does not give much of an advantage).

In this paper we construct a family of DAGs with best possible parameters, i.e., where $\Pi^{\parallel}_{cc}(G_n)=\Omega(n^2/\log(n))$ (which matches a known upper bound) and $\Pi_{st}(G_n)$ is within a constant factor of $\Pi^{\parallel}_{cc}(G_n)$.

Our analysis relies on a new connection between depth-robustness (DR) of DAGs -- a well studied combinatorial property -- and their pebbling complexities. We show that high DR is _sufficient_ for high $\Pi^{\parallel}_{cc}$. This contrasts the recent results of Alwen and Blocki (ePrint/2016/115) showing that high DR is _necessary_. Together these results fully characterizes DAGs with high $\Pi^{\parallel}_{cc}$ in terms of DR. Along the way we also give a new tool for reducing the indegree of a DAG without loosing too much in $\Pi^{\parallel}_{cc}$ which may be of interest beyond this work.

Previous to our work the graphs with best asymptotic complexity were due to Alwen and Serbinenko (STOC'15) achieve $\Pi^{\parallel}_{cc}(G_n)\in\Omega(n^2/\log^{10}(n))$. Most of the constructions used in practice have recently been broken in strong sense, the graph underlying Arogon2i, the winner of the recent password hashing competition, has $\Pi^{\parallel}_{cc}$ complexity $\tilde{O}(n^{1.75})$, for the recently proposed Balloon-Hashing the upper bound is $O(n^{1.67})$ and the same bound holds for Catena. We prove a $\tilde{\Omega}(n^{5/3})$ lower bound on $\Pi^{\parallel}_{cc}$ for Argon2i, and a $\tilde{\Omega}(n^{1.5})$ lower bound for Catena and Balloon hashing. The lower bound for Argon2i leverages our connection between $\Pi^{\parallel}_{cc}$ and depth-robustness. To prove the lower bounds for Catena and Balloon hashing we identify a graph property dubbed ``dispersity", and show how it also lower bounds $\Pi^{\parallel}_{cc}$. We also present an improved recursive version of the pebbling attack of Alwen and Blocki (ePrint/2016/115) and show that it implies upper bounds of $O\left(n^{1.71} \right)$ and $O(n^{1.62})$ for Argon2i and Catena respectively.

The department of mathematics of the University of South Florida has funding for a PhD student working on mathematical cryptography and computational number theory under the supervision of Jean-François Biasse (personal page: http://www.lix.polytechnique.fr/Labo/Jean-Francois.Biasse/).

Potential research topics include:

1) Algorithms for ideal lattices.

2) Post quantum cryptography.

3) Fully homomorphic encryption.

The deadline for applications for a January 2017 start date is October 1rst (US citizens and green card holders only).

The deadline for an August 2017 start date is February 1rst 2017 (no residency restrictions).

General instructions for applying to the maths graduate program of the USF can be found here: http://math.usf.edu/grad/apply/.

The conditions are:

a) 3 years of funding.

b) Stipend of $16,000 per year.

c) Teaching duties 5h/week.

d) Tuition waiver.

Please contact me if you are interested.

Closing date for applications: 1 October 2016

Contact: Jean-François Biasse (usf.phd.crypto (at) gmail.com)