International Association
for Cryptologic Research

In this work we study the feasibility of knowledge extraction for succinct non-interactive arguments of knowledge (SNARKs) in a scenario that, to the best of our knowledge, has not been analyzed before. While prior work focuses on the case of adversarial provers that may receive (statically generated) {\em auxiliary information}, here we consider the scenario where adversarial provers are given {\em access to an oracle}. For this setting we study if and under what assumptions such provers can admit an extractor. Our contribution is mainly threefold.

First, we formalize the question of extraction in the presence of oracles by proposing a suitable proof of knowledge definition for this setting. We call SNARKs satisfying this definition O-SNARKs.

Second, we show how to use O-SNARKs to obtain formal and intuitive security proofs for three applications (homomorphic signatures, succinct functional signatures, and SNARKs on authenticated data) where we recognize an issue while doing the proof under the standard proof of knowledge definition of SNARKs.

Third -- and this is the most prominent part of our work -- we study whether O-SNARKs exist, providing both negative and positive results. On the negative side, we show that, assuming collision-resistant hash functions, there do not exist O-SNARKs in the standard model for every oracle family. Next, we study the interesting case of {\em signing} oracles. We give a negative result showing that even O-SNARKs for every signing oracle family do not exist. On the positive side, instead, we show that, when considering signature schemes with appropriate restrictions on the message length, O-SNARKs for the corresponding signing oracles exist, based on classical SNARKs and assuming extraction with respect to specific distributions of auxiliary input.

Logistic regression is a powerful machine learning tool to classify data. When dealing with sensitive data such as private or medical information, cares are necessary. In this paper, we propose a secure system for protecting both the training and predicting data in logistic regression via homomorphic encryption. Perhaps surprisingly, despite the non-polynomial tasks of training and predicting in logistic regression, we show that only additively homomorphic encryption is needed to build our system. Indeed, we instantiate our system with Paillier, LWE-based, and ring-LWE-based encryption schemes, highlighting the merits and demerits of each instance. Our system is very scalable in both the dataset size and dimension, tolerating big size for example of hundreds of millions ($10^8$s) records. Besides examining the costs of computation and communication, we carefully test our system over real datasets to demonstrate its accuracies and other related measures such as F-score and AUC.

Informally, a public-key encryption scheme is \emph{$k$-circular secure} if a cycle of~$k$ encrypted secret keys $(\pkcenc_{\pk_{1}}(\sk_{2}), \pkcenc_{\pk_{2}}(\sk_{3}), \ldots, \pkcenc_{\pk_{k}}(\sk_{1}))$ is indistinguishable from encryptions of zeros. Circular security has applications in a wide variety of settings, ranging from security of symbolic protocols to fully homomorphic encryption. A fundamental question is whether standard security notions like IND-CPA/CCA imply $k$-circular security.

For the case $k=2$, several works over the past years have constructed counterexamples---i.e., schemes that are CPA or even CCA secure but not $2$-circular secure---under a variety of well-studied assumptions (SXDH, decision linear, and LWE). However, for $k > 2$ the only known counterexamples are based on strong general-purpose obfuscation assumptions.

In this work we construct $k$-circular security counterexamples for any $k \geq 2$ based on (ring-)LWE. Specifically: \begin{itemize} \item for any constant $k=O(1)$, we construct a counterexample based on $n$-dimensional (plain) LWE for $\poly(n)$ approximation factors; \item for any $k=\poly(\lambda)$, we construct one based on degree-$n$ ring-LWE for at most subexponential $\exp(n^{\varepsilon})$ factors. \end{itemize} Moreover, both schemes are $k'$-circular insecure for $2 \leq k' \leq k$.

Notably, our ring-LWE construction does not immediately translate to an LWE-based one, because matrix multiplication is not commutative. To overcome this, we introduce a new ``tensored'' variant of LWE which provides the desired commutativity, and which we prove is actually equivalent to plain LWE.

We study the question of securely multiplying N-bit integers that are stored in binary representation, in the context of protocols for dishonest majority with preprocessing. We achieve communication complexity O(N) using only secure operations over small fields F_2 and F_p with log(p) \approx log(N). For semi-honest security we achieve communication O(N)2^{O(log∗(N))} using only secure operations over F_2. This improves over the straightforward solution of simulating a Boolean multiplication circuit, both asymptotically and in practice.

Private set operation (PSO) protocols provide a natural way of securely performing operations on data sets, such that crucial details of the input sets are not revealed. Such protocols have an ever-increasing number of practical applications, particularly when implementing privacy-preserving data mining schemes. Protocols for computing private set operations have been prevalent in multi-party computation literature over the past decade, and in the case of private set intersection (PSI), have become practically feasible to run in real applications. In contrast, other set operations such as union have received less attention from the research community, and the few existing designs are often limited in their feasibility. In this work we aim to fill this gap, and present a new technique using Bloom filter data structures and additive homomorphic encryption to develop the first private set union (PSU) protocol with both linear computation and communication complexities. The overheads of our protocol scale better with increasing set sizes than existing PSU designs and we thus provide the first potentially practical realisation of the PSU functionality. Moreover, we show how to adapt this protocol to give novel ways of computing PSI and private set intersection/union cardinality (PSI/PSU-CA). The resulting schemes have complexities that are comparable to current solutions that are considered practical. We therefore present an adaptable way for efficiently computing the main set operations, with linear complexities, and with the possibility of extending to compute other more complex functionalities. Our constructions can be proven secure with respect to both semi-honest and malicious adversaries.

Numerous electronic cash schemes have been proposed over the years ranging from Ecash, Mondex to Millicent. However none of these schemes have been adopted by the financial institutions as an alternative to traditional paper based currency. The Ecash scheme was the closest to a system that mimicked fiat currency with the property that it provided anonymity for users when buying coins from the Bank and spending them at a merchant premises (from the Bank's perspective). However Ecash lacked one crucial element present in current fiat based systems i.e., the ability to continuously spend or transfer coins within the system. In this paper we propose an extension to the Ecash scheme which allows for the anonymous transfer of coins between users without the involvement of a trusted third party. We make use of a powerful technique which allows for distributed decision making within the network - namely the Bitcoin blockchain protocol. Combined with the proof-of-work technique and the classical discrete logarithm problem we are able to continuously reuse coins within our system, and also prevent double-spending of coins without revealing the identities of the users.

We initiate the study of Access Control Encryption (ACE), a novel cryptographic primitive that allows fine-grained access control, by giving different rights to different users not only in terms of which messages they are allowed to receive, but also which messages they are allowed to send.

Classical examples of security policies for information flow are the well known Bell-Lapadula [BL73] or Biba [Bib75] model: in a nutshell, the Bell-Lapadula model assigns roles to every user in the system (e.g., public, secret and top-secret). A users' role specifies which messages the user is allowed to receive (i.e., the no read-up rule, meaning that users with public clearance should not be able to read messages marked as secret or top-secret) but also which messages the user is allowed to send (i.e., the no write-down rule, meaning that a user with top-secret clearance should not be able to write messages marked as secret or public).

To the best of our knowledge, no existing cryptographic primitive allows for even this simple form of access control, since no existing cryptographic primitive enforces any restriction on what kind of messages one should be able to encrypt.

Our contributions are: - Introducing and formally defining access control encryption (ACE); - A construction of ACE with complexity linear in the number of the roles based on classic number theoretic assumptions (DDH, Paillier); - A construction of ACE with complexity polylogarithmic in the number of roles based on recent results on cryptographic obfuscation;

In 1978, Rivest, Adleman and Dertouzos asked for algebraic systems for which useful privacy homomorphisms exist. To date, the only acknownledged result is noise based encryption combined with bootstrapping. Before that, there were several failed attempts.

We prove that fully homomorphic schemes are impossible for several algebraic structures. Then we develop a characterisation of all fully homomorphic schemes and use it to analyse three examples. Finally, we propose a conjecture stating that secure FHE schemes must either have a significant ciphertext expansion or use unusual algebraic structures.

In this document we present an overview of the background to and goals of the Password Hashing Competition (PHC) as well as the design of its winner, Argon2, and its security requirements and properties.

Event date: 1 January to 15 May 2016
Submission deadline: 5 March 2016

Event date: 24 October to 28 October 2016
Submission deadline: 23 May 2016
Notification: 22 July 2016

Event date: 25 July 2016
Submission deadline: 15 May 2016

In this paper we study and give the first detailed benchmarks on existing implementations of the secp256k1 elliptic curve used by at least hundreds of thousands of users in Bitcoin and other cryptocurrencies. Our implementation improves the state of the art by a factor of 2.5, with focus on the cases where side channel attacks are not a concern and a large quantity of RAM is available. As a result, we are able to scan the Bitcoin blockchain for weak keys faster than any previous implementation. We also give some examples of passwords which have we have cracked, showing that brain wallets are not secure in practice even for quite complex passwords.

Indistinguishability obfuscation (\io) has emerged as a surprisingly powerful notion. Almost all known cryptographic primitives can be constructed from general purpose \io\ and other minimalistic assumptions such as one-way functions. The primary challenge in this direction of research is to develop novel techniques for using \io\ since \io\ by itself offers virtually no protection to secret information in the underlying programs. When dealing with complex situations, often these techniques have to consider an exponential number of hybrids (usually one per input) in the security proof. This results in a {\em sub-exponential} loss in the security reduction. Unfortunately, this scenario is becoming more and more common and appears to be a fundamental barrier to current techniques.

In this work, we explore the possibility of getting around this {\em sub-exponential loss barrier} in constructions based on \io\ as well as the weaker notion of {\em functional encryption} (\fe). Towards this goal, we achieve the following results:

\begin{enumerate} \item We construct trapdoor one-way permutations from {\em polynomially-hard} \io\ (and standard one-way permutations). This improves upon the recent result of Bitansky, Paneth, and Wichs (TCC 2016) which requires \io\ of sub-exponential strength.

\item We present a different construction of trapdoor one-way permutations based on standard, polynomially-secure, public-key functional encryption. This qualitatively improves upon our first result since \fe\ is a weaker primitive than \io\ --- it can be based on polynomially-hard assumptions on multi-linear maps whereas \io\ inherently seems to requires assumptions of sub-exponential strength.

\item We present a construction of {\em universal samplers} also based only on polynomially-secure public-key \fe. Universal samplers, introduced in the work of Hofheinz, Jager, Khurana, Sahai, Waters and Zhandry (EPRINT 2014), is an appealing notion which allows a {\em single} trusted setup for {\em any} protocol. As an application of this result, we construct a {\em non-interactive multiparty key exchange} (NIKE) protocol for an unbounded number of users without a trusted setup. Prior to this work, such constructions were only known from indistinguishability obfuscation. \end{enumerate}

In obtaining our results, we build upon and significantly extend the techniques of Garg, Pandey, and Srinivasan (EPRINT 2015) introduced in the context of reducing $\PPAD$-hardness to polynomially-secure \io\ and \fe.

A recent line of works - initiated by Gordon, Katz and Vaikuntanathan (Asiacrypt 2010) - gave lattice-based constructions allowing users to authenticate while remaining hidden in a crowd. Despite five years of efforts, known constructions are still limited to static sets of users, which cannot be dynamically updated. This work provides new tools enabling the design of anonymous authentication systems whereby new users can join the system at any time.

Our first contribution is a signature scheme with efficient protocols, which allows users to obtain a signature on a committed value and subsequently prove knowledge of a signature on a committed message. This construction is well-suited to the design of anonymous credentials and group signatures. It indeed provides the first lattice-based group signature supporting dynamically growing populations of users.

As a critical component of our group signature, we provide a simple joining mechanism of introducing new group members using our signature scheme. This technique is combined with zero-knowledge arguments allowing registered group members to prove knowledge of a secret short vector of which the corresponding public syndrome was certified by the group manager. These tools provide similar advantages to those of structure-preserving signatures in the realm of bilinear groups. Namely, they allow group members to generate their own public key without having to prove knowledge of the underlying secret key. This results in a two-message joining protocol supporting concurrent enrollments, which can be used in other settings such as group encryption.

Our zero-knowledge arguments are presented in a unified framework where: (i) The involved statements reduce to arguing possession of a $\{-1,0,1\}$-vector $\mathbf{x}$ with a particular structure and satisfying $\mathbf{P}\cdot \mathbf{x} = \mathbf{v} \bmod q$ for some public matrix $\mathbf{P}$ and vector $\mathbf{v}$; (ii) The reduced statements can be handled using permuting techniques for Stern-like protocols. Our framework can serve as a blueprint for proving many other relations in lattice-based cryptography.

We investigate lower bounds in terms of time and memory on the {\em parallel} complexity of an adversary $\cal A$ computing labels of randomly selected challenge nodes in direct acyclic graphs, where the $w$-bit label of a node is the hash $H(.)$ (modelled as a random oracle with $w$-bit output) of the labels of its parents. Specific instances of this general problem underlie both proofs-of-space protocols [Dziembowski et al. CRYPTO'15] as well as memory-hardness proofs including {\sf scrypt}, a widely deployed password hashing and key-derivation function which is e.g. used within Proofs-of-Work for digital currencies like Litecoin.

Current lower bound proofs for these problems only consider {\em restricted} algorithms $\cal A$ which perform only a single $H(.)$ query at a time and which only store individual labels (but not arbitrary functions thereof). This paper substantially improves this state of affairs; Our first set of results shows that even when allowing multiple parallel $\hash$ queries, the ``cumulative memory complexity'' (CMC), as recently considered by Alwen and Serbinenko [STOC '15], of ${\sf scrypt}$ is at least $w \cdot (n/\log(n))^2$, when ${\sf scrypt}$ invokes $H(.)$ $n$ times. Our lower bound holds for adversaries which can store (1) Arbitrary labels (i.e., random oracle outputs) and (2) Certain natural functions of these labels, e.g., linear combinations. The exact power of such adversaries is captured via the combinatorial abstraction of parallel ``entangled'' pebbling games on graphs, which we introduce and study.

We introduce a combinatorial quantity $\gamma_n$ and under the conjecture that it is upper bounded by some constant, we show that the above lower bound on the CMC also holds for arbitrary algorithms $\cal A$, storing in particular arbitrary functions of their labels. We also show that under the same conjecture, the {\em time complexity} of computing the label of a random node in a graph on $n$ nodes (given an initial $kw$-bit state) reduces tightly to the time complexity for entangled pebbling on the same graph (given an initial $k$-node pebbling). Under the conjecture, this solves the main open problem from the work of Dziembowski et al.

In fact, we note that every non-trivial upper bound on $\gamma_n$ will lead to the first non-trivial bounds for general adversaries for this problem.

The only known way to achieve Attribute-based Fully Homomorphic Encryption (ABFHE) is through indistinguishability obfsucation. The best we can do at the moment without obfuscation is Attribute-Based Leveled FHE which allows circuits of an a priori bounded depth to be evaluated. This has been achieved from the Learning with Errors (LWE) assumption. However we know of no other way without obfuscation of constructing a scheme that can evaluate circuits of unbounded depth. In this paper, we present an ABFHE scheme that can evaluate circuits of unbounded depth but with one limitation: there is a bound N on the number of inputs that can be used in a circuit evaluation. The bound N could be thought of as a bound on the number of independent senders. Our scheme allows N to be exponentially large so we can set the parameters so that there is no limitation on the number of inputs in practice. Our construction relies on multi-key FHE and leveled ABFHE, both of which have been realized from LWE, and therefore we obtain a concrete scheme that is secure under LWE.

Many efficient cryptographic hash function design strategies have been explored recently, not least because of the SHA-3 competition. Almost exclusively these design are geared towards good performance for long inputs. However, various use cases exist where performance on short inputs matters more. An example is HMAC, and such functions also constituting the bottleneck of various hash-based signature schemes like SPHINCS, or XMSS which is currently under standardization. Secure functions specifically designed for such applications are scarce. In this paper, we fill this gap by proposing two short-input hash functions (or rather simply compression functions) exploiting instructions on modern CPUs that support the AES. To our knowledge these proposals are the fastest on modern high-end CPUs, reaching throughputs below one cycle per hashed byte even for short inputs while still having a very low latency of no more than 60 cycles. Under the hood, this results comes with several innovations.

First, we study whether the number of rounds for said functions can be reduced if collision resistance is not expected, but only second-preimage resistance. The conclusions is: only a little.

Second, since their inception AES-like designs allow for supportive security arguments by means of counting and bounding the number of active S-boxes. However, this ignores powerful attack vectors using truncated differentials, of which rebound attacks are a popular example. With our design, we develop for the first time a general tool-based method to include arguments against attack vectors using truncated differentials.

Bent functions shows some vital properties among all combinatorial objects. Its links in combinatorics, cryptography and coding theory attract the scientific community to construct new class of bent functions. Since the entire characterisation of bent functions is still unexplored but several construction on different algebraic structure is in progress. In this paper we proposed a generalized Maiorana-McFarland construction of bent function from Galois ring.

Impossible differential and zero correlation linear cryptanalysis are two of the most important cryptanalytic vectors. To characterize the impossible differentials and zero correlation linear hulls which are independent of the choices of the non-linear components, Sun et al. proposed the structure deduced by a block cipher at CRYPTO 2015. Based on that, we concentrate in this paper on the security of the SPN structure and Feistel structure with SP-type round functions. Firstly, we prove that for an SPN structure, if \alpha_1\rightarrow\beta_1 and \alpha_2\rightarrow\beta_ are possible differentials, \alpha_1|\alpha_2\rightarrow\beta_1|\beta_2 is also a possible differential, i.e., the OR "|" operation preserves differentials. Secondly, we show that for an SPN structure, there exists an r-round impossible differential if and only if there exists an r-round impossible differential \alpha\not\rightarrow\beta where the Hamming weights of both \alpha and \beta are 1. Thus for an SPN structure operating on m bytes, the computation complexity for deciding whether there exists an impossible differential can be reduced from O(2^{2m}) to O(m^2). Thirdly, we associate a primitive index with the linear layers of SPN structures. Based on the matrices theory over integer rings, we prove that the length of impossible differentials of an SPN structure is upper bounded by the primitive index of the linear layers. As a result we show that, unless the details of the S-boxes are considered, there do not exist 5-round impossible differentials for the AES and ARIA. Lastly, based on the links between impossible differential and zero correlation linear hull, we projected these results on impossible differentials to zero correlation linear hulls. It is interesting to note some of our results also apply to the Feistel structures with SP-type round functions.