An encryption relation $f \subseteq {\mathbb Z} \times {\mathbb Z}$ with decryption function $f^{-1}$ is {\it ``group-homomorphic''} if, for any suitable plaintexts $x_1$ and $x_2$, $\, x_1+x_2 = f^{-1} ( f(x_1) + f(x_2) )$. It is {\it ``ring-homomorphic''} if furthermore $x_1 x_2 = f^{-1} ( f(x_1) f(x_2) )$; it is {\it ``field-homomorphic''} if furthermore $1/x_1 = f^{-1} ( f(1/x_1) )$. Such relations would support oblivious processing of encrypted data. We propose a simple randomized encryption relation~$f$ over the integers, called\linebreak {\it \mbox{DoubleMod}}, which is ``bounded ring-homomorphic'' or what some call "somewhat homomorphic." Here, ``bounded'' means that the number of additions and multiplications that can be performed, while not allowing the encrypted values to go out of range, is limited~(any pre-specified bound on the operation-count can be accommodated). Let $R$ be any large integer. For any plaintext $x \in {\mathbb Z}_R$, DoubleMod encrypts $x$ as $f(x) = x + au + bv$, where $a$ and $b$ are randomly chosen integers in some appropriate interval, while $(u,v)$ is the secret key. Here $u>R^2$ is a large prime and the smallest prime factor of $v$ exceeds $u$. With knowledge of the key, but not of $a$ and $b$, the receiver decrypts the ciphertext by computing $f^{-1}(y) =(y \bmod v) \bmod u$. DoubleMod generalizes an independent idea of van Dijk {\it et al.} 2010. We present and refine a new CCA1 chosen-ciphertext attack that finds the secret key of both systems (ours and van Dijk {\it et al.}'s) in linear time in the bit length of the security parameter. Under a known-plaintext attack, breaking DoubleMod is at most as hard as solving the {\it Approximate GCD (AGCD)} problem. The complexity of AGCD is not known. We also introduce the \mbox{{\it SingleMod}} {field}-homomorphic cryptosystems. The simplest\linebreak \mbox{SingleMod} system based on the integers can be broken trivially. We had hoped, that if SingleMod is implemented inside non-Euclidean quadratic or higher-order fields with large discriminants, where GCD computations appear difficult, it may be feasible to achieve a desired level of security. We show, however, that a variation of our chosen-ciphertext attack works against SingleMod even in non-Euclidean fields.

We study the communication complexity of secure function evaluation (SFE). Consider a setting where Alice has a short input $x_A$, Bob has an input $x_B$ and we want Bob to learn some function $y = f(x_A, x_B)$ with large output size. For example, Alice has a small secret decryption key, Bob has a large encrypted database and we want Bob to learn the decrypted data without learning anything else about Alice's key. In a trivial insecure protocol, Alice can just send her short input $x_A$ to Bob. However, all known SFE protocols have communication complexity that scales with size of the output $y$, which can potentially be much larger. Is such ``output-size dependence'' inherent in SFE? Surprisingly, we show that output-size dependence can be avoided in the \emph{honest-but-curious} setting. In particular, using indistinguishability obfuscation (iO) and fully homomorphic encryption (FHE), we construct the first honest-but-curious SFE protocol whose communication complexity only scales with that of the best insecure protocol for evaluating the desired function, independent of the output size. Our construction relies on a novel way of using iO via a new tool that we call a ``somewhere statistically binding (SSB) hash'', and which may be of independent interest. On the negative side, we show that output-size dependence is inherent in the \emph{fully malicious} setting, or even already in an \emph{honest-but-deterministic} setting, where the corrupted party follows the protocol as specified but fixes its random tape to some deterministic value. Moreover, we show that even in an offline/online protocol, the communication of the online phase must have output-size dependence. This negative result uses an incompressibility argument and it generalizes several recent lower bounds for functional encryption and (reusable) garbled circuits, which follow as simple corollaries of our general theorem.

In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their private inputs. The computation should preserve security properties such as privacy, correctness, independence of inputs, fairness and guaranteed output delivery. In the case of no honest majority, fairness and guaranteed output delivery cannot always be obtained. Thus, protocols for secure multiparty computation are typically of two disparate types: protocols that assume an honest majority (and achieve all properties \emph{including} fairness and guaranteed output delivery), and protocols that do not assume an honest majority (and achieve all properties \emph{except for} fairness and guaranteed output delivery). In addition, in the two-party case, fairness and guaranteed output delivery are equivalent. As a result, the properties of fairness (which means that if corrupted parties receive output then so do the honest parties) and guaranteed output delivery (which means that corrupted parties cannot prevent the honest parties from receiving output in any case) have typically been considered to be the same. In this paper, we initiate a study of the relation between fairness and guaranteed output delivery in secure multiparty computation. We show that in the multiparty setting these properties are distinct and proceed to study under what conditions fairness implies guaranteed output delivery (the opposite direction always holds). We also show the existence of non-trivial functions for which complete fairness is achievable (without an honest majority) but guaranteed output delivery is not, and the existence of non-trivial functions for which complete fairness and guaranteed output delivery are achievable. Our study sheds light on the role of broadcast in fairness and guaranteed output delivery, and shows that these properties should sometimes be considered separately.

Protocols for secure two-party computation enable a pair of mistrusting parties to compute a joint function of their private inputs without revealing anything but the output. One of the fundamental techniques for obtaining secure computation is that of Yao's garbled circuits. In the setting of malicious adversaries, where the corrupted party can follow any arbitrary (polynomial-time) strategy in an attempt to breach security, the cut-and-choose technique is used to ensure that the garbled circuit is constructed correctly. The cost of this technique is the construction and transmission of multiple circuits; specifically, $s$ garbled circuits are used in order to obtain a maximum cheating probability of $2^{-s}$. In this paper, we show how to reduce the amortized cost of cut-and-choose based secure two-party computation to ${\cal O}\(\frac{s}{\log N}\)$ garbled circuits when $N$ secure computations are run. We use this method to construct a secure protocol in the batch setting. Next, we show how the cut-and-choose method on garbled circuits can be used in an online/offline setting in order to obtain a very fast online phase with very few exponentiations, and we apply our amortization method to this setting as well. Our online/offline protocols are competitive with the TinyOT and SPDZ protocols due to the minimal interaction in the online phase (previous protocols require only information-theoretic operations in the online phase and are therefore very efficient; however, they also require many rounds of communication which increases latency). Although ${\cal O}(\frac{s}{\log N})$ may seem to be a mild efficiency improvement asymptotically, it is a \emph{dramatic improvement} for concrete parameters since $s$ is a statistical security parameter and so is typically small. Specifically, instead of $40$ circuits to obtain an error of $2^{-40}$, when running $2^{10}$ executions we need only $7.06$ circuits on average per secure computation, and when running $2^{20}$ executions this is reduced to an average of just $4.08$. In addition, in the online/offline setting, the online phase per secure computation consists of evaluating only $6$ garbled circuits for $2^{10}$ executions and $4$ garbled circuits for $2^{20}$ executions (plus some small additional overhead). In practice, when using fast implementations (like the JustGarble framework of Bellare et al.), the resulting protocol is remarkably fast. We present a number of variants of our protocols with different assumptions and efficiency levels. Our basic protocols rely on the DDH assumption alone, while our most efficient variants are proven secure in the random-oracle model. Interestingly, the variant in the random-oracle model of our protocol for the online/offline setting has online communication that is independent of the size of the circuit in use. None of the previous protocols in the online/offline setting achieves this property, which is very significant since communication is usually a dominant cost in practice.

Previously known functional encryption (FE) schemes for general circuits relied on indistinguishability obfuscation, which in turn either relies on an exponential number of assumptions (basically, one per circuit), or a polynomial set of assumptions, but with an exponential loss in the security reduction. Additionally these schemes are proved in the weaker selective security model, where the adversary is forced to specify its target before seeing the public parameters. For these constructions, full security can be obtained but at the cost of an exponential loss in the security reduction. In this work, we overcome the above limitations and realize a fully secure functional encryption scheme without using indistinguishability obfuscation. Specifically the security of our scheme relies only on the polynomial hardness of simple assumptions on multilinear maps. As a separate technical contribution of independent interest, we show how to add to existing graded encoding schemes a new \emph{extension function}, that can be though of as dynamically introducing new encoding levels.

Secure elements, such as smartcards or trusted platform modules (TPMs), must be protected against implementation-level attacks. Those include side-channel and fault injection attacks. We introduce ODSM, Orthogonal Direct Sum Masking, a new computation paradigm that achieves protection against those two kinds of attacks. A large vector space is structured as two supplementary orthogonal subspaces. One subspace (called a code $\mathcal{C}$) is used for the functional computation, while the second subspace carries random numbers. As the random numbers are entangled with the sensitive data, ODSM ensures a protection against (monovariate) side-channel attacks. The random numbers can be checked either occasionally, or globally, thereby ensuring a fine or coarse detection capability. The security level can be formally detailed: it is proved that monovariate side-channel attacks of order up to $d_\mathcal{C}-1$, where $d_\mathcal{C}$ is the minimal distance of $\mathcal{C}$, are impossible, and that any fault of Hamming weight strictly less than $d_\mathcal{C}$ is detected. A complete instantiation of ODSM is given for AES. In this case, all monovariate side-channel attacks of order strictly less than $5$ are impossible, and all fault injections perturbing strictly less than $5$ bits are detected.

Koblitz curves have been a nice subject of consideration for both theoretical and practical interests. The window $\tau$-adic algorithm of Solinas (window $\tau$NAF) is the most powerful method for computing point multiplication for Koblitz curves. Pre-computation plays an important role in improving the performance of point multiplication. In this paper, the concept of optimal pre-computation for window $\tau$NAF is formulated. In this setting, an optimal pre-computation has some mathematically natural and clean forms, and requires $2^{w-2}-1$ point additions and two evaluations of the Frobenius map $\tau$, where $w$ is the window width. One of the main results of this paper is to construct an optimal pre-computation scheme for each window width $w$ from $4$ to $15$ (more than practical needs). These pre-computations can be easily incorporated into implementations of window $\tau$NAF. The ideas in the paper can also be used to construct other suitable pre-computations. This paper also includes a discussion of coefficient sets for window $\tau$NAF and the divisibility by powers of $\tau$ through different approaches.

Non-malleable codes, introduced as a relaxation of error-correcting codes by Dziembowski, Pietrzak and Wichs (ICS '10), provide the security guarantee that the message contained in a tampered codeword is either the same as the original message or is set to an unrelated value. Various applications of non-malleable codes have been discovered, and one of the most significant applications among these is the connection with tamper-resilient cryptography. There is a large body of work considering security against various classes of tampering functions, as well as non-malleable codes with enhanced features such as leakage resilience. In this work, we propose combining the concepts of non-malleability, leakage resilience, and locality in a coding scheme. The contribution of this work is three-fold: 1. As a conceptual contribution, we define a new notion of locally decodable and updatable non-malleable code that combines the above properties. 2. We present two simple and efficient constructions achieving our new notion with different levels of security. 3. We present an important application of our new tool--securing RAM computation against memory tampering and leakage attacks. This is analogous to the usage of traditional non-malleable codes to secure implementations in the circuit model against memory tampering and leakage attacks.

In secure delegatable computation, computationally weak devices (or clients) wish to outsource their computation and data to an untrusted server in the cloud. While most earlier work considers the general question of how to securely outsource any computation to the cloud server, we focus on concrete and important functionalities and give the first protocol for the pattern matching problem in the cloud. Loosely speaking, this problem considers a text $T$ that is outsourced to the cloud $\bfS$ by a sender $\sen$. In a query phase, receivers $\rec_1, \ldots , \rec_l$ run an efficient protocol with the server $\bfS$ and the sender $\sen$ in order to learn the positions at which a pattern of length $m$ matches the text (and nothing beyond that). This is called the outsourced pattern matching problem which is highly motivated in the context of delegatable computing since it offers storage alternatives for massive databases that contain confidential data (e.g., health related data about patient history). Our constructions are simulation-based secure in the presence of semi-honest and malicious adversaries (in the random oracle model) and limit the communication in the query phase to $O(m)$ bits plus the number of occurrences---which is optimal. In contrast to generic solutions for delegatable computation, our schemes do not rely on fully homomorphic encryption but instead use novel ideas for solving pattern matching, based on a reduction to the subset sum problem. Interestingly, we do not rely on the hardness of the problem, but rather we exploit instances that are solvable in polynomial-time. A follow-up result demonstrates that the random oracle is essential in order to meet our communication bound.

In response to the need for secure one-round authenticated key exchange protocols providing both perfect forward secrecy and full deniability, we put forward a new paradigm for constructing protocols from a Diffie-Hellman type protocol plus a non-interactive designated verifier proof of knowledge (DV-PoK) scheme. We define the notion of DV-PoK which is a variant of non-interactive zero-knowledge proof of knowledge, and provide an efficient DV-PoK scheme as a central technical building block of our protocol. The DV-PoK scheme possesses nice properties such as unforgeability and symmetry which help our protocol to achieve perfect forward secrecy and full deniability respectively. Moreover, the security properties are formally proved in the Canetti-Krawczyk model under the Gap Diffie-Hellman assumption. In sum, our protocol offers a remarkable combination of salient security properties and efficiency, and the notion of DV-PoK is of independent interests.

We consider the task of constructing interactive proofs for NP which can provide meaningful security for a prover even in the presence of continual memory leakage. We imagine a setting where an adversarial verifier participates in multiple sequential interactive proof executions for a fixed NP statement x. In every execution, the adversarial verifier is additionally allowed to leak a fraction of the (secret) memory of the prover. This is in contrast to the recently introduced notion of leakage-resilient zero-knowledge (Garg-Jain-Sahai'11) where there is only a single execution. Under multiple executions, in fact the entire prover witness might end up getting leaked thus leading to a complete compromise of prover security. Towards that end, we define the notion of non-transferable proofs for all languages in NP. In such proofs, instead of receiving w as input, the prover will receive an "encoding'' of the witness w such that the encoding is sufficient to prove the validity of x; further, this encoding can be "updated'' to a fresh new encoding for the next execution. We then require that if (x,w) are sampled from a "hard'' distribution, then no PPT adversary A* can gain the ability to prove x (on its own) to an honest verifier, even if A* has participated in polynomially many interactive proof executions (with leakage) with an honest prover whose input is (x,w). Non-transferability is a strong security guarantee which suffices for many cryptographic applications (and in particular, implies witness hiding). We show how to construct non-transferable proofs for all languages in NP which can tolerate leaking a constant fraction of prover's secret-state during each execution. Our construction is in the common reference string (CRS) model. To obtain our results, we build a witness-encoding scheme which satisfies the following continual-leakage-resilient (CLR) properties: - The encodings can be randomized to yield a fresh new encoding, - There does not exist any efficient adversary, who receiving only a constant fraction of leakage on polynomially many fresh encodings of the same witness w, can output a valid encoding provided that the witness w along with its corresponding input instance x were sampled from a hard distribution. Our encoding schemes are essentially re-randomizable non-interactive zero-knowledge (NIZK) proofs for circuit satisfiability, with the aforementioned CLR properties. We believe that our CLR-encodings, as well as our techniques to build them, may be of independent interest.

In this paper, we explore the primitivity of trinomials over small finite fields. We extend the results of the primitivity of trinomials $x^{n}+ax+b$ over ${\mathbb{F}}_{4}$ \cite{Li} to the general form $x^{n}+ax^{k}+b$. We prove that for given $n$ and $k$, one of all the trinomials $x^{n}+ax^{k}+b$ with $b$ being the primitive element of ${\mathbb{F}}_{4}$ and $a+b\neq1$ is primitive over ${\mathbb{F}}_{4}$ if and only if all the others are primitive over ${\mathbb{F}}_{4}$. And we can deduce that if we find one primitive trinomial over ${\mathbb{F}}_{4}$, in fact there are at least four primitive trinomials with the same degree. We give the necessary conditions if there exist primitive trinomials over ${\mathbb{F}}_{4}$. We study the trinomials with degrees $n=4^{m}+1$ and $n=21\cdot4^{m}+29$, where $m$ is a positive integer. For these two cases, we prove that the trinomials $x^{n}+ax+b$ with degrees $n=4^{m}+1$ and $n=21\cdot4^{m}+29$ are always reducible if $m>1$. If some results are obviously true over ${\mathbb{F}}_{3}$, we also give it.

The adjacency graphs of feedback shift registers (FSRs) with characteristic function of the form g=(x_0+x_1)*f are considered in this paper. Some properties about these FSRs are given. It is proved that these FSRs contains only prime cycles and these cycles can be divided into two sets such that each set contains no adjacent cycles. When f is a linear function, more properties about these FSRs are derived. It is shown that, when f is a linear function and contains an odd number of terms, the adjacency graph of \mathrm{FSR}((x_0+x_1)*f) can be determined directly from the adjacency graph of \mathrm{FSR}(f). As an application of these results, we determine the adjacency graphs of \mathrm{FSR}((1+x)^4p(x)) and \mathrm{FSR}((1+x)^5p(x)), where p(x) is a primitive polynomial, and construct a large class of de Bruijn sequences from them.

Recently, Kalikinkar Mandal and Guang Gong presented a family of nonlinear pseudorandom number generators using Welch-Gong Transformations in their paper [6]. They also performed the cycle decomposition of the WG-NLFSR recurrence relations over different finite fields by computer simulations where the nonlinear recurrence relation is composed of a characteristic polynomial and a WG permutation. In this paper, we mainly prove that the state transition transformation of the WG-NLFSR is an even permutation. We also prove that the number of the cycles in the cycle decomposition of WG-NLFSR is even. And we apply our results to the filtering WG7-NLFSR to prove that the period of the sequences generated by WG7-NLFSR can not be maximum.

The FX-construction was proposed in 1996 by Kilian and Rogaway as a generalization of the DESX scheme. The construction increases the security of an $n$-bit core block cipher with a $\kappa$-bit key by using two additional $n$-bit masking keys. Recently, several concrete instances of the FX-construction were proposed, including PRINCE (proposed at Asiacrypt 2012) and PRIDE (proposed at CRYPTO 2014). These ciphers have $n=\kappa=64$, and are proven to guarantee about $127-d$ bits of security, assuming that their core ciphers are ideal, and the adversary can obtain at most $2^d$ data. In this paper, we devise new cryptanalytic time-memory-data tradeoff attacks on FX-constructions. While our attacks do not contradict the security proof of PRINCE and PRIDE, nor pose an immediate threat to their users, some specific choices of tradeoff parameters demonstrate that the security margin of the ciphers against practical attacks is smaller than expected. Our techniques combine a special form of time-memory-data tradeoffs, typically applied to stream ciphers, with recent analysis of FX-constructions by Fouque, Joux and Mavromati.

Password-based authentication has been widely deployed in practice due to its simplicity and efficiency. Storing passwords and deriving cryptographic keys from passwords in a secure manner are crucial for many security systems and services. However, choices of well-studied password hashing algorithms are extremely limited, as their security requirements and design principles are different from common cryptographic algorithms. In this paper, we propose two practical password hashing algorithms, Pleco and Plectron. They are built upon well-understood cryptographic algorithms, and combine advantages of symmetric and asymmetric primitives. By employing the Rabin cryptosystem, we prove that the one-wayness of Pleco is at least as strong as the hard problem of integer factorization. In addition, both password hashing algorithms are designed to be sequential memory-hard, in order to thwart large-scale password cracking by parallel hardware, such as GPUs, FPGAs, and ASICs. Moreover, total computation and memory consumptions of Pleco and Plectron are tunable through their cost parameters.

Very few differential fault attacks (DFA) were reported on {\em Grain-128} so far. In this paper we present a generic attack strategy that allows the adversary to challenge the cipher under different multi-bit fault models with faults at a targeted keystream generation round even if bit arrangement of the actual cipher device is unknown. Also unique identification of fault locations is not necessary. To the best of our knowledge, this paper assumes the weakest adversarial power ever considered in the open literature for DFA on {\em Grain-128} and develops the most realistic attack strategy so far on {\em Grain-128}. In particular, when a random area within $k \in \{1,2,3,4,5\}$ neighbourhood bits can only be disturbed by a single fault injection at the first keystream generation round ($k$-neighbourhood bit fault), without knowing the locations or the exact number of bits the injected fault has altered, our attack strategy always breaks the cipher with $5$ faults. In a weaker setup even if bit arrangement of the cipher device is unknown, bad-faults (at the first keystream generation round) are rejected with probabilities $0.999993$, $0.999979$, $0.999963$, $0.999946$ and $0.999921$ assuming that the adversary will use only 1, 2, 3, 4 and 5 neighbourhood bit faults respectively for {\em key-IV} recovery.

We present work in progress to fully factor seventeen Mersenne numbers using a variant of the special number field sieve where sieving on the algebraic side is shared among the numbers. It is expected that it reduces the overall factoring effort by more than 50\%. As far as we know this is the first practical application of Coppersmith's ``factorization factory'' idea. Most factorizations used a new double-product approach that led to additional savings in the matrix step.

As far as the Differential Cryptanalysis of reduced round Grain v1 is concerned, the best results were those published by Knellwolf et al. in Asiacrypt $2011$. In an extended version of the paper, it was shown that it was possible to retrieve {\bf (i)} $5$ expressions in the Secret Key bits for a variant of Grain v1 that employs $97$ rounds (in place of $160$) in its Key Scheduling process using $2^{27}$ chosen IVs and {\bf (ii)} $1$ expression in Secret Key bits for a variant that employs $104$ rounds in its Key Scheduling using $2^{35}$ chosen IVs. However, the second attack on $104$ rounds, had a success probability of around $50$\%, which is to say that the attack worked for only around one half of the Secret Keys. In this paper we propose a dynamic cube attack on $105$ round Grain v1, that has a success probability of $100$\%, and thus we report an improvement of $8$ rounds over the previous best attack on Grain v1 that attacks the entire Keyspace. We take the help of the tool $\Delta${\sf Grain}$_{\sf KSA}$, proposed by Banik at ACISP 2014, to track the differential trails induced in the internal state of Grain v1 by any difference in the IV bits, and we prove that a suitably introduced difference in the IV leads to a distinguisher for the output bit produced in the $105^{th}$ round. This, in turn, helps determine the values of $6$ expressions in the Secret Key bits.

We show that the plaintext of some of the proposed CCA2 conversions of McEliece cryptosystem with a public key in systematic form can be recovered faster than with a general linear decoding. This is due to the fact that an attacker only needs to recover a part of the cleartext to decrypt the relevant plaintext.

In a Password-Protected Secret Sharing (PPSS) scheme with parameters (t,n) (formalized by Bagherzandi et al), a user Alice stores secret information s among n servers so that she can later recover the information solely on the basis of her password. The security requirement is similar to a (t,n)-threshold secret sharing, i.e., Alice can recover her secret as long as she can communicate with t + 1 honest servers but an attacker gaining access to t servers cannot learn information about the secret. In particular, the system is secure against o-line attacks by an attacker controlling up to t servers. On the other hand, accounting for inevitable on-line attacks one allows the attacker an advantage proportional to the fraction of dictionary passwords tested in on-line interactions with the user and servers. We present the first round-optimal PPSS scheme, requiring just one message from user to server, and from server to user, and that works in the password-only setting where users do not have access to an authenticated public key. The scheme uses an Oblivious PRF whose security we define using a UC-style ideal functionality and denote as V-OPRF due to its verifiability, and for which we show concrete, very practical realizations in the random oracle model, as well as standard-model instantiations. As an important application we use this scheme to build the first single-round password-only Threshold-PAKE protocol in the CRS and ROM models for arbitrary (t,n) parameters with no PKI requirements for any party (clients or servers) and no inter-server communication. Our T-PAKE protocols are built by combining suitable key exchange protocols on top of our V-OPRF-based PPSS schemes. We prove T-PAKE security via a generic composition theorem showing the security of any such composed protocol.

This paper investigates a novel attack vector against cryptography realized on FPGAs, which poses a serious threat to real-world applications.We demonstrate how a targeted bitstream modification can seriously weaken cryptographic algorithms, which we show with the examples of AES and 3DES. The attack is performed by modifying the FPGA bitstream that configures the hardware elements during initialization. Recently, it has been shown that cloning of FPGA designs is feasible, even if the bitstream is encrypted. However, due to its proprietary file format, a meaningful modification is very challenging. While some previous work addressed bitstream reverse-engineering, so far it has not been evaluated how difficult it is to detect and modify cryptographic elements. We outline two possible practical attacks that have serious security implications. We target the S-boxes of block ciphers that can be implemented in look-up tables or stored as precomputed set of values in the memory of the FPGA. We demonstrate that it is possible to detect and apply meaningful changes to cryptographic elements inside an unknown, proprietary and undocumented bitstream. Our proposed attack does not require any knowledge of the internal routing. Furthermore, we show how an AES key can be revealed within seconds. Finally, we discuss countermeasures that can raise the bar for an adversary to successfully perform this kind of attack.

Differentially $4$-uniform permutations on $\gf_{2^{2k}}$ with high nonlinearity are often chosen as substitution boxes in block ciphers. Recently, Qu et al. used the powerful switching method to construct permutations with low differential uniformity from the inverse function \cite{QTTL, QTLG} and proposed a sufficient but not necessary condition for these permutations to be differentially $4$-uniform. In this paper, a sufficient and necessary condition is presented. We also give a compact estimation for the number of constructed differentially $4$-uniform permutations. Comparing with those constructions in \cite{QTTL, QTLG}, the number of functions constructed here is much bigger. As an application, a new class of differentially $4$-uniform permutations is constructed. The obtained functions in this paper may provide more choices for the design of substitution boxes.

This paper analyzes group communication within the universally composable framework. We first propose the group communication model, identity-based signcrytion model and group key distribution model in the UC framework by designing the ideal functionality $\mathcal {F}_{SAGCOM}$, $\mathcal {F}_{IDSC}$ and $\mathcal {F}_{GKD}$, respectively. Then, we construct a UC secure identity-based signcryption protocol $\pi_{IDSC}$. Moreover, we shows that the identity-based signcryption $\pi_{IDSC}$ securely realizes the ideal functionality $\mathcal {F}_{IDSC}$ if and only if the corresponding protocol IDSC is secure. Finally, based on the identity-based protocol, we propose a group communication scheme $\pi_{SAGCOM}$, which can securely realizes the ideal functionality $\mathcal {F}_{SAGCOM}$ in the $(\mathcal {F}_{IDSC},\mathcal {F}_{GKD})$-hybrid model.

Polynomial multiplication is the basic and most computationally intensive operation in ring-Learning With Errors (ring-LWE) encryption and ``Somewhat" Homomorphic Encryption (SHE) cryptosystems. In this paper, the Fast Fourier Transform (FFT) with a linearithmic complexity of $O(n\log n)$, is exploited in the design of a high-speed polynomial multiplier. A constant geometry FFT datapath is used in the computation to simplify the control of the architecture. The contribution of this work is three-fold. First, parameter sets which support both an efficient modular reduction design and the security requirements for ring-LWE encryption and SHE are provided. Second, a versatile pipelined architecture accompanied with an improved dataflow are proposed to obtain a high-speed polynomial multiplier. Third, the proposed architecture supports polynomial multiplications for different lengths $n$ and moduli $p$. The experimental results on a Spartan-6 FPGA show that the proposed design results in a speedup of 3.5 times on average when compared with the state of the art. It performs a polynomial multiplication in the ring-LWE scheme ($n = 256, p = 1049089$) and the SHE scheme ($n = 1024, p = 536903681$) in only 6.3$\mu$s and 33.1$\mu$s, respectively.

Graded multilinear encodings have found extensive applications in cryptography ranging from non-interactive key exchange protocols, to broadcast and attribute-based encryption, and even to software obfuscation. Despite seemingly unlimited applicability, essentially only two candidate constructions are known (GGH and CLT). In this work, we describe a new graph-induced multilinear encoding scheme from lattices. In a graph-induced multilinear encoding scheme the arithmetic operations that are allowed are restricted through an explicitly defined directed graph (somewhat similar to the "asymmetric variant" of previous schemes). Our construction encodes Learning With Errors (LWE) samples in short square matrices of higher dimensions. Addition and multiplication of the encodings corresponds naturally to addition and multiplication of the LWE secrets.

Over a decade, cryptographers are more attentive on designing lightweight ciphers in focus to compact cryptographic devices. More often, the security of these algorithms are defined in terms of its resistance to mathematical cryptanalysis methods. Nevertheless, designers are well aware of implementation attacks and concentrating on new design strategies to improve the defence quality against implementation attack. PRINCE ~\cite{Julia2012} and RECTANGLE ~\cite{cryptoeprint:2014:084} lightweight block ciphers are designed using new design strategies for efficiency and security. In this paper we analyse the security of PRINCE and RECTANGLE against a type of implementation attack called Differential Power Analysis (DPA) attack. Our attack reduces key search space from $2^{128}$ to $33008$ for PRINCE and $2^{80}$ to $288$ for RECTANGLE.

In 2013, Althobaiti et al. proposed an efficient biometric-based user authentication scheme for wireless sensor networks. We analyze their scheme for the security against known attacks. Though their scheme is efficient in computation, in this paper we show that their scheme has some security pitfalls such as (1) it is not resilient against node capture attack, (2) it is insecure against impersonation attack and (3) it is insecure against man-in-the-middle attack. Finally, we give some pointers for improving their scheme so that the designed scheme needs to be secure against various known attacks.

The $r$-rounds Even-Mansour block cipher uses $r$ public permutations of $\{0, 1\}^n$ and $r+1$ secret keys. An attack on this construction was described in \cite{DDKS}, for $r = 2, 3$. Although this attack is only marginally better than brute force, it is based on an interesting observation (due to \cite{NWW}): for a "typical" permutation $P$, the distribution of $P(x) \oplus x$ is not uniform. To address this, and other potential threats that might stem from this observation in this (or other) context, we introduce the notion of a ``balanced permutation'' for which the distribution of $P(x) \oplus x$ is uniform, and show how to generate families of balanced permutations from the Feistel construction. This allows us to define a $2n$-bit block cipher from the $2$-rounds Even-Mansour scheme. The cipher uses public balanced permutations of $\{0, 1\}^{2n}$, which are based on two public permutations of $\{0, 1\}^{n}$. By construction, this cipher is immune against attacks that rely on the non-uniform behavior of $P(x) \oplus x$. We prove that this cipher is indistinguishable from a random permutation of $\{0, 1\}^{2n}$, for any adversary who has oracle access to the public permutations and to an encryption/decryption oracle, as long as the number of queries is $o (2^{n/2})$. As a practical example, we discuss the properties and the performance of a $256$-bit block cipher that is based on AES.

In this short paper, we propose a variant of the Number Field Sieve to compute discrete logarithms in medium characteristic finite fields. We propose an algorithm that combines two recent ideas, namely the Multiple variant of the Number Field Sieve taking advantage of a large number of number fields in the sieving phase and the Conjugation Method giving a new polynomial selection for the classical Number Field Sieve. The asymptotic complexity of our improved algorithm is L_Q (1/3, (8 (9+4 \sqrt{6})/15)^1/3), where F_Q is the target finite field and (8 (9+4 \sqrt{6})/15)^1/3) is approximately equal to 2.156. This has to be compared with the complexity of the previous state-of-the-art algorithm for medium characteristic finite fields, the Number Field Sieve with Conjugation Method, that has a complexity of approximately L_Q(1/3, 2.201).

The combination of software-as-a-service and the increasing use of mobile devices gives rise to a considerable difference in computational power between servers and clients. Thus, there is a desire for clients to outsource the evaluation of complex functions to an external server. Servers providing such a service may be rewarded per computation, and as such have an incentive to cheat by returning garbage rather than devoting resources and time to compute a valid result. In this work, we introduce the notion of Revocable Publicly Verifiable Computation (RPVC), where a cheating server is revoked and may not perform future computations (thus incurring a financial penalty). We introduce a Key Distribution Center (KDC) to efficiently handle the generation and distribution of the keys required to support RPVC. The KDC is an authority over entities in the system and enables revocation. We also introduce a notion of blind verification such that results are verifiable (and hence servers can be rewarded or punished) without learning the value. We present a rigorous definitional framework, define a number of new security models and present a construction of such a scheme built upon Key-Policy Attribute-based Encryption.

This paper proposes a novel approach for automated implementation of an arbiter-based physical unclonable function (PUF) on field programmable gate arrays (FPGAs). We introduce a high resolution programmable delay logic (PDL) that is implemented by harnessing the FPGA lookup-table (LUT) internal structure. PDL allows automatic fine tuning of delays that can mitigate the timing skews caused by asymmetries in interconnect routing and systematic variations. To thwart the arbiter metastability problem, we present and analyze methods for majority voting of responses. A method to classify and group challenges into different robustness sets is introduced that enhances the corresponding responses’ stability in the face of operational variations. The trade-off between response stability and response entropy (uniqueness) is investigated through comprehensive measurements. We exploit the correlation between the impact of temperature and power supply on responses and perform less costly power measurements to predict the temperature impact on PUF. The measurements are performed on 12 identical Virtex 5 FPGAs across 9 different accurately controlled operating temperature and voltage supply points. A database of challenge response pairs (CRPs) are collected and made openly available for the research community.

In this paper, we consider a setting where a client wants to outsource storage of a large amount of private data and then perform substring search queries on the data -- given a data string s and a search string p, find all occurrences of p as a substring of s. First, we formalize an encryption paradigm that we call queryable encryption, which generalizes searchable symmetric encryption (SSE) and structured encryption. Then, we construct a queryable encryption scheme for substring queries. Our construction uses suffix trees and achieves asymptotic efficiency comparable to that of unencrypted suffix trees. Encryption of a string of length n takes O(kn) time and produces a ciphertext of size O(kn), and querying for a substring of length m that occurs z times takes O(km+z) time and three rounds of communication, where k is the security parameter. Our security definition guarantees correctness of query results and privacy of data and queries against a malicious, adaptive adversary. Following the line of work started by Curtmola et al. (ACM CCS 2006), in order to construct more efficient schemes we allow the query protocol to leak some limited information that is captured precisely in the definition. We prove security of our substring-searchable encryption scheme against malicious adversaries, where the query protocol leaks limited information about memory access patterns through the suffix tree of the encrypted string.

We study generic hardness of the multiple discrete logarithm problem, where the solver has to solve $n$ instances of the discrete logarithm problem simultaneously. There are known generic algorithms which perform $O(\sqrt{n p})$ group operations, where $p$ is the group order, but no generic lower bound was known other than the trivial bound. In this paper we prove the tight generic lower bound, showing that the previously known algorithms are asymptotically optimal. We establish the lower bound by studying hardness of a related computational problem which we call the search-by-hyperplane-queries problem, which may be of independent interest.

We improve the timing attack on ECDSA in [1] by Brumley and Tuveri. We use the Gaussian heuristic to analyse the length of error vectors in the lattice Close Vector Problem in order to determine the problems which are theoretically solvable. Then we cost each solution using a strengthened lattice reduction algorithm and Schnorr-Euchner enumeration to determine which problems are practically solvable. The original work by Brumley and Tuveri resulted in OpenSSL's ECDSA being updated to remove the timing information they exploited, so that application is not vulnerable to our improvements. However we publish this work as a general advance in side-channel recovery techniques which may be applicable in related scenarios.

At CRYPTO 2014, Abe et al. presented generic-signer structure-preserving signature schemes using Type 2 pairings. According to the authors, the proposed constructions are optimal with only two group elements in each signature and just one verification equation. The schemes beat the known lower bounds in the Type 3 setting and thereby establish that the Type 2 setting permits construction of cryptographic schemes with unique properties not achievable in Type 3. In this paper we undertake a concrete analysis of the Abe et al. claims. By properly accounting for the actual structure of the underlying groups and subgroup membership testing of group elements in signatures, we show that the schemes are not as efficient as claimed. We present natural Type 3 analogues of the Type 2 schemes, and show that the Type 3 schemes are superior to their Type 2 counterparts in every aspect. We also formally establish that in the concrete mathematical structure of asymmetric pairing, all Type 2 structure-preserving signature schemes can be converted to the Type 3 setting without any penalty in security or efficiency, and show that the converse is false. Furthermore, we prove that the Type 2 setting does not allow one to circumvent the known lower bound result for the Type 3 setting. Our analysis puts the optimality claims for Type 2 structure-preserving signature in a concrete perspective and indicates an incompleteness in the definition of a generic bilinear group in the Type 2 setting.

Garg, Jain, and Sahai first consider zero knowledge proofs in the presence of leakage on the local state of the prover, and present a leakage-resilient-zero-knowledge proof system for HC (Hamiltonian Cycle) problem. Their construction is called $(1+\varepsilon)$-leakage-resilient zero-knowledge, for any constant $\varepsilon>0$, because the total length of the leakage the simulator needs is $(1+\varepsilon)$ times as large as that of the leakage received by the verifier. In recent, Pandey provides a constant-round leakage-resilient zero-knowledge argument satisfying the ideal requirement of $\varepsilon=0$. Whether there exist constant round leakage-resilient zero-knowledge arguments of knowledge for all NP languages is an interesting problem. This paper focuses on this problem and presents a constant-round construction of leakage-resilient zero-knowledge arguments of knowledge for the HC problem.

The traditional setting for concurrent zero knowledge considers a server that proves a statement in zero-knowledge to multiple clients in multiple concurrent sessions, where the server's actions in a session are independent of all other sessions. Persiano and Visconti [ICALP 05] show how keeping a limited amount of global state across sessions allows the server to significantly reduce the overall complexity while retaining the ability to interact concurrently with an unbounded number of clients. Specifically, they show a protocol that has only slightly super-constant number of rounds; however the communication complexity in each session of their protocol depends on the number of other sessions and has no a priori bound. This has the drawback that the client has no way to know in advance the amount of resources required for completing a session of the protocol up to the moment where the session is completed. We show a protocol that does not have this drawback. Specifically, in our protocol the client obtains a bound on the communication complexity of each session at the start of the session. Additionally the protocol is constant-rounds. Our protocol is fully concurrent, and assumes only collision-resistant hash functions. The proof requires considerably different techniques than those of Persiano and Visconti. Our main technical tool is an adaptation of the "committed-simulator" technique of Deng et. al [FOCS 09].

Given a list L with n elements, an order query on L asks whether a given element x in L precedes or follows another element y in L. More generally, given a set of m elements from L, an order query asks for the set ordered according to the positions of the elements in L. We introduce two formal models for answering order queries on a list in a verifiable manner and in zero-knowledge. We also present efficient constructions for these models. Our first model, called \emph{zero-knowledge list} (ZKL), generalizes membership queries on a set to order queries on a list in zero-knowledge. We present a construction of ZKL based on zero-knowledge sets and a homomorphic integer commitment scheme. Our second model, \emph{privacy-preserving authenticated list} (PPAL), extends authenticated data structures by adding a zero-knowledge privacy requirement. In this model, a list is outsourced by a trusted owner to an untrusted cloud server, which answers order queries issued by clients. The server also returns a proof of the answer, which is verified by the client using a digest of the list obtained from the owner. PPAL supports the security properties of data integrity against a malicious server and privacy protection against a malicious client. Though PPAL can be implemented using our ZKL construction, this construction is not as efficient as desired in cloud applications. To this end, we present an efficient PPAL construction based on blinded bilinear accumulators and bilinear maps, which is provably secure and zero-knowledge (e.g., hiding even the size of the list). Our PPAL construction uses proofs of $O(m)$ size and allows the client to verify a proof in $O(m)$ time.~The owner executes the setup in $O(n)$ time and space. The server uses $O(n)$ space to store the list and related authentication information, and takes $O(\min(m\log n, n))$ time to answer a query and generate a proof. Both our ZKL and PPAL constructions have one round of communication and are secure in the random oracle model. Finally, we show that our ZKL and PPAL frameworks can be extended to support fundamental statistical queries (including maximum, minimum, median, threshold and top-t elements) efficiently and in zero-knowledge.

Despite more than thirty years of research efforts, textual passwords are still enveloped in mysterious veils. In this work, we make a substantial step forward in understanding the distributions of passwords and measuring the strength of password datasets by using a statistical approach. We first show that Zipf's law perfectly exists in real-life passwords by conducting linear regressions on a corpus of 56 million passwords. As one specific application of this observation, we propose the number of unique passwords used in regression and the slope of the regression line together as a metric for assessing the strength of password datasets, and prove it in a mathematically rigorous manner. Furthermore, extensive experiments (including optimal attacks, simulated optimal attacks and state-of-the-art cracking sessions) are performed to demonstrate the practical effectiveness of our metric. To the best of knowledge, our new metric is the first one that is both easy to approximate and accurate to facilitate comparisons, providing a useful tool for the system administrators to gain a precise grasp of the strength of their password datasets and to adjust the password policies more reasonably.

In this paper, we describe efficient protocols to perform in parallel many reads and writes in private arrays according to private indices. The protocol is implemented on top of the Arithmetic Black Box (ABB) and can be freely composed to build larger privacy-preserving applications. For a large class of secure multiparty computation (SMC) protocols, we believe our technique to have better practical and asymptotic performance than any previous ORAM technique that has been adapted for use in SMC. Our ORAM technique opens up a large class of parallel algorithms for adoption to run on SMC platforms. In this paper, we demonstrate how the minimum spanning tree (MST) finding algorithm by Awerbuch and Shiloach can be executed without revealing any details about the underlying graph (beside its size). The data accesses of this algorithm heavily depend on the location and weight of edges (which are private) and our ORAM technique is instrumental in their execution. Our implementation is probably the first-ever realization of a privacy-preserving MST algorithm.

We show how to realize two-factor authentication for a Bitcoin wallet employing the two-party ECDSA signature protocol adapted from MacKenzie & Reiter (2004). We also present a prototypic implementation of a Bitcoin wallet that offers both: two-factor authentication and verification over a separate channel. Since we use a smart phone as the second authentication factor, our solution can be used with hardware already available to most users and the user experience is quite similar to the existing online banking authentication methods.

In this paper, we present an efficient $k$-out-of-$n$ secret sharing scheme, which can identify up to $t$ rushing cheaters, with probability at least $1 - \epsilon$, where $0<\epsilon<1/2$, provided $t < k/2$. This is the optimal number of cheaters that can be tolerated in the setting of public cheater identification, on which we focus in this work. In our scheme, the set of all possible shares $V_i$ satisfies the condition that $|V_i|= \frac{(t+1)^{2n+k-3}|S|}{\epsilon^{2n+k-3}}$, where $S$ denotes the set of all possible secrets. In PODC-2012, Ashish Choudhury came up with an efficient $t$-cheater identifiable $k$-out-of-$n$ secret sharing scheme, which was a solution of an open problem proposed by Satoshi Obana in EUROCRYPT-2011. The share size, with respect to a secret consisting of one field element, of Choudhury's proposal in PODC-2012 is $|V_i|=\frac{(t+1)^{3n}|S|}{\epsilon^{3n}}$. Therefore, our scheme presents an improvement in share size over the above construction. Hence, to the best of our knowledge, our proposal currently has the minimal share size among existing efficient schemes with optimal cheater resilience, in the case of a single secret.

This work deals with the various requirements of encryption and authentication in cryptographic applications. The approach is to construct suitable modes of operations of a block cipher to achieve the relevant goals. A variety of schemes suitable for specific applications are presented. While none of the schemes are built completely from scratch, there is a common unifying framework which connects them. All the schemes described have been implemented and the implementation details are publicly available. Performance figures are presented when the block cipher is the AES and the Intel AES-NI instructions are used. These figures suggest that the constructions presented here compare well with previous works such as the famous OCB mode of operation. In terms of features, the constructions provide several new offerings which are not present in earlier works. This work significantly widens the range of choices of an actual designer of cryptographic system.

We demonstrate physical side-channel attacks on a popular software implementation of RSA and ElGamal, running on laptop computers. Our attacks use novel side channels, based on the observation that the "ground" electric potential, in many computers, fluctuates in a computation-dependent way. An attacker can measure this signal by touching exposed metal on the computer's chassis with a plain wire, or even with a bare hand. The signal can also be measured at the remote end of Ethernet, VGA or USB cables. Through suitable cryptanalysis and signal processing, we have extracted 4096-bit RSA keys and 3072-bit ElGamal keys from laptops, via each of these channels, as well as via power analysis and electromagnetic probing. Despite the GHz-scale clock rate of the laptops and numerous noise sources, the full attacks require a few seconds of measurements using Medium Frequency signals (around 2 MHz), or one hour using Low Frequency signals (up to 40 kHz).

The technological advance is entering almost all aspects of our everyday life. One interesting aspect is the possibility to conduct elections over the Internet. However, many proposed Internet voting schemes and systems build on unrealistic assumptions about the trustworthiness of the voting environment and other voter-side assumptions. Code voting -- first introduced by Chaum [Cha01] -- is one approach that minimizes the voter-side assumptions. The voting scheme Pretty UnderstandableDemocracy [BNOV13] builds on the idea of code voting while it ensures on the server-side an arguably practical security model based on a strict separation of duty, i.e. all security requirements are ensured if any two components do not collaborate in order to violate the corresponding requirement. As code voting and strict separation of duty realizations come along with some challenges (e.g. pre-auditing phase, usability issues, clearAPIs), the goal of our research was to implement Pretty UnderstandableDemocracy and run a trial election. This paper reports about necessary refinements of the original scheme, the implementation process, and atrial election among the different development teams (each team being responsible for one component).

This paper proposes KT-ORAM, a new hybrid ORAM-PIR construction, to protect a client's access pattern to outsourced data. KT-ORAM organizes the server storage as a $k$-ary tree with each node acting as a fully-functional PIR storage, and adopts a novel delayed eviction technique to optimize the eviction process. KT-ORAM is proved to protect the data access pattern privacy at a failure probability negligible in $N$ ($N$ is the number of exported data blocks), when system parameter $k=\log N$. Under the same configuration, KT-ORAM has an asymptotical communication cost of $O(\frac{\log N}{\log\log N}\cdot B)$ when the recursion level on meta data is of $O(1)$ depth, which can be achieved if block size $B=N^{\epsilon}$ ($0<\epsilon<1$), or $O(\frac{\log^2 N}{\log\log N}\cdot B)$ when the number of recursion levels is $O(\log N)$. The costs of KT-ORAM are compared with those of several state-of-the-art ORAMs. The results show that, KT-ORAM achieves the best communication, storage and client-side computational efficiency simultaneously, at the price of requiring $O(\frac{\log^2N}{\log\log N}\cdot B)$ computational cost at the storage server for each data query. \\ {\bf Key words:} Cloud storage, Access pattern privacy, Oblivious RAM, and PIR.

We revisit the impossibility of a variety of cryptographic tasks including privacy and differential privacy with imperfect randomness. For traditional notions of privacy, such as security of encryption, commitment or secret sharing schemes, dramatic impossibility results are known [MP90,DOPS04]. In fact, they are true even if the imperfect source is modeled as a seemingly very "nice and friendly" Santha-Vazirani (SV) source. Moreover, Bosley and Dodis [BD07] gave strong evidence that many traditional privacy tasks (e.g., encryption) inherently require an "extractable" source of randomness. The common interpretation of these negative results is that traditional privacy is impossible even with "very structured" imperfect sources. Somewhat surprisingly, Dodis et al. [DLMV12] put a slight dent in this belief, by showing that non-trivial *differential* privacy is possible with SV sources. This suggested a qualitative gap between traditional and differential privacy, and left open the question if differential privacy is possible with more realistic (i.e., less structured) sources than the SV sources. Motivated by solving this question, we introduce a new, modular framework for showing strong impossibility results for (either traditional or differential) privacy under a *general* imperfect source R. In particular, we introduce natural and easy-to-understand concepts of expressiveness and separability of a given imperfect source R, and show the following results: (1) Low levels of expressiveness generically imply strong impossibility results for both traditional and *differential* privacy. (2) Separability implies expressiveness; NON-separability is equivalent to ``weak bit extraction''. (3) While the separability of some concrete (e.g., SV) sources R was implicitly known, we show new separability results for several important sources, including general "block sources". As direct corollaries of these general results, we get the following corollaries: (1) Existing, but quantitatively improved, impossibility results for traditional privacy, but under a wider variety of sources R. (2) First impossibility results for differential privacy. Although, unsurprisingly, these results (barely) miss the highly structured SV sources, they come back *extremely quickly* once the source becomes slightly more realistic (e.g., a realistic "block source"). (3) Any imperfect source allowing (either traditional or differential) privacy admits a certain type of deterministic bit extraction. (This result is incomparable to the result of [BD07].) Overall, we believe our results provide an intuitive, modular and unified picture elucidating the (im)possibility of privacy with general imperfect sources.

We construct the first fully secure attribute based encryption (ABE) scheme that can handle access control policies expressible as polynomial-size circuits. Previous ABE schemes for general circuits were proved secure only in an unrealistic selective security model, where the adversary is forced to specify its target before seeing the public parameters, and full security could be obtained only by complexity leveraging, where the reduction succeeds only if correctly guesses the adversary’s target string x*, incurring a 2^{|x^*|} loss factor in the tightness of the reduction. At a very high level, our basic ABE scheme is reminiscent of Yao’s garbled circuits, with 4 gadgets per gate of the circuit, but where the decrypter in our scheme puts together the appropriate subset of gate gadgets like puzzle pieces by using a cryptographic multilinear map to multiply the pieces together. We use a novel twist of Waters’ dual encryption methodology to prove the full security of our scheme. Most importantly, we show how to preserve the delicate information-theoretic argument at the heart of Waters’ dual system by enfolding it in an information-theoretic argument similar to that used in Yao’s garbled circuits.

In this paper we present MATor: a framework for rigorously assessing the degree of anonymity in the Tor network. The framework explicitly addresses how user anonymity is impacted by real-life characteristics of actually deployed Tor, such as its path selection algorithm, Tor consensus data, and the preferences and the connections of the user. The anonymity assessment is based on rigorous anonymity bounds that are derived in an extension of the AnoA framework (IEEE CSF 2013). We show how to apply MATor on Tor's publicly available consensus and server descriptor data, thereby realizing the first real-time anonymity monitor. Based on experimental evaluations of this anonymity monitor on Tor Metrics data, we propose an alternative path selection algorithm that provides stronger anonymity guarantees without decreasing the overall performance of the Tor network.

M3dcrypt is a password hashing function built around the Advanced Encryption Standard (AES) algorithm and the arcfour pseudorandom function. It uses up to 256-bit pseudorandom salt values and supports 48-byte passwords.

SNOW 2.0 is a word oriented stream cipher that has been selected as a standard stream cipher on ISO/IEC 18033-4. One of the general attacks on the stream ciphers is Guess and Determine attack. Heuristic GD attack is GD attack that represents an algorithmic method to analysis the stream cipher with the variables of the same size. The results of HGD attack on TIPSY, SNOW 1.0 and SNOW 2.0 stream ciphers led to less complexity rather than previously known GD attacks. In this paper, the authors use of two auxiliary polynomials to improve HGD attack on SNOW 2.0. This attack reduces the complexity and the size of the guessed basis from O (2265) to O (2192) and 8 to 6, respectively, compared with previous ad-hoc and heuristic GD attacks.

We provide a proof of correctness and security of a two-party-computation protocol based on garbled circuits and oblivious transfer in the presence of a semi-honest sender. To achieve this we are the first to combine a machine-assisted proof of correctness with advanced cryptographic primitives to prove security properties of Java code. The machine-assisted part of the proof is conducted with KeY, an interactive theorem prover. The proof includes a correctness result for the construction and evaluation of garbled circuits. This is particularly interesting since checking such an implementation by hand would be very tedious and error-prone. Although we stick to the secure two-party-computation of an n-bit AND in this paper, our approach is modular, and we explain how our techniques can be applied to other functions. To prove the security of the protocol for an honest-but-curious sender and an honest receiver, we use the framework presented by Kuesters et al. for the cryptographic verification of Java programs. As part of our work, we add oblivious transfer to the set of cryptographic primitives supported by the framework. This is a general contribution beyond our results for concrete Java code.

We study the problem of privacy-preserving proofs on authenticated data, where a party receives data from a trusted source and is requested to prove computations over the data to third parties in a correct and private way, i.e., the third party learns no information on the data but is still assured that the claimed proof is valid. Our work particularly focuses on the challenging requirement that the third party should be able to verify the validity with respect to the specific data authenticated by the source — even without having access to that source. This problem is motivated by various scenarios emerging from several application areas such as wearable computing, smart metering, or general business-to-business interactions. Furthermore, these applications also demand any meaningful solution to satisfy additional properties related to usability and scalability. In this paper, we formalize the above three-party model, discuss concrete application scenarios, and then we design, build, and evaluate ADSNARK, a nearly practical system for proving arbitrary computations over authenticated data in a privacy-preserving manner. ADSNARK improves significantly over state-of-the-art solutions for this model. For instance, compared to corresponding solutions based on Pinocchio (Oakland’13), ADSNARK achieves up to 25× improvement in proof computation time and a 20× reduction in prover storage space.

In Ciphertext-Policy Attribute-Based Encryption (CP-ABE), a user's decryption key is associated with attributes which in general are not related to the user's identity, and the same set of attributes could be shared between multiple users. From the decryption key, if the user created a decryption blackbox for sale, this malicious user could be difficult to identify from the blackbox. Hence in practice, a useful CP-ABE scheme should have some tracing mechanism to identify this `traitor' from the blackbox. In addition, being able to revoke compromised keys is also an important step towards practicality, and for scalability, the scheme should support an exponentially large number of attributes. However, none of the existing traceable CP-ABE schemes simultaneously supports revocation and large attribute universe. In this paper, we construct the first practical CP-ABE which possesses these three important properties: (1) blackbox traceability, (2) revocation, and (3) supporting large universe. This new scheme achieves the fully collusion-resistant blackbox traceability, and when compared with the latest fully collusion-resistant blackbox traceable CP-ABE schemes, this new scheme achieves the same efficiency level, enjoying the sub-linear overhead of $O(\sqrt{N})$, where $N$ is the number of users in the system, and attains the same security level, namely, the fully collusion-resistant traceability against policy-specific decryption blackbox, which is proven in the standard model with selective adversaries. The scheme supports large attribute universe, and attributes do not need to be pre-specified during the system setup. In addition, the scheme supports revocation while keeping the appealing capability of conventional CP-ABE, i.e. it is highly expressive and can take any monotonic access structures as ciphertext policies. We also present the analogous results in the Key-Policy Attribute-Based Encryption (KP-ABE) setting, where users' description keys are described by access policies and ciphertexts are associated with attributes. We construct the first practical KP-ABE which possesses the three important properties: (1) blackbox traceability, (2) revocation, and (3) supporting large universe. The scheme is highly expressive and can take any monotonic access structures as key policies, and is efficient, namely, enjoys the sub-linear overhead of $O(\sqrt{N})$ while supporting fully collusion-resistant blackbox traceability and revocation, and does not need to pre-specify the attributes during the system setup. The scheme is proven selectively secure in the standard model.

Secure multi-party computation (MPC) has been thoroughly studied over the past decades. The vast majority of works assume a full communication pattern: every party exchanges messages with {\em all} the network participants over a complete network of point-to-point channels. This can be problematic in modern large scale networks, where the number of parties can be of the order of millions, as for example when computing on large distributed data. Motivated by the above observation, Boyle, Goldwasser, and Tessaro [TCC 2013] recently put forward the notion of {\em communication locality}, namely, the total number of point-to-point channels that each party uses in the protocol, as a quality metric of MPC protocols. They proved that assuming a public-key infrastructure (PKI) and a common reference string (CRS), an MPC protocol can be constructed for computing any $n$-party function, with communication locality $\bigo[\log^c n]$ and round complexity $\bigo[\log^{c'} n]$, for appropriate constants $c$ and $c'$. Their protocol tolerates a static (i.e., non-adaptive) adversary corrupting up to $t<(\frac{1}{3}-\epsilon)n$ parties for any given constant $0<\epsilon<\frac{1}{3}$. These results leave open the following questions: (1) Can we achieve low communication locality and round complexity while tolerating {\em adaptive} adversaries? \\ (2) Can we achieve low communication locality with {\em optimal resiliency} $t<n/2$? In this work we answer both questions affirmatively. First, we consider the model from [TCC 2013], where we replace the CRS with a symmetric-key infrastructure (SKI). In this model we give a protocol with communication locality and round complexity \polylog[n] (as in the [TCC~2013] work) which tolerates up to $t<n/2$ {\em adaptive} corruptions, under a standard intractability assumption for adaptively secure protocols, \vaddon{namely, the existence of enhanced trapdoor permutations and secure erasures.} This is done by using the SKI to derive a sequence of random {\it hidden communication graphs} among players. A central new technique then shows how to use these graphs to emulate a complete network in \polylog[n] rounds while preserving the \polylog[n] locality. Second, we show how we can even remove the SKI setup assumption at the cost, however, of increasing the communication locality (but not the round complexity) by a factor of~$\sqrt{n}$.

Searchable encryption allows an untrusted server to search on encrypted data without knowing the underlying data contents. Traditional searchable encryption schemes focus only on single keyword or conjunctive keyword search. Several solutions have been recently proposed to design more expressive search criteria, but most of them are in the setting of symmetric key encryption. In this paper, based on the composite-order groups, we present an expressive and secure asymmetric searchable encryption (ESASE) scheme, which is the first that simultaneously supports conjunctive, disjunctive and negation search operations. We analyze the efficiency of ESASE and prove it is secure under the standard model. In addition, we show that how ESASE could be extended to support the range search and the multi-user setting.

This note contains a security reduction to demonstrate that Langley's composition of Bernstein's ChaCha20 and Poly1305, as proposed for use in IETF protocols, is a secure authenticated encryption scheme. The reduction assumes that ChaCha20 is a PRF, that Poly1305 is epsilon-almost-Delta-universal, and that the adversary is nonce respecting.

In this work, we aim to make attribute-based encryption (ABE) more suitable for access control to data stored in the cloud. For this purpose, we concentrate on giving to the encryptor full control over the access rights, providing feasible key management even in case of multiple independent authorities, and enabling viable user revocation, which is essential in practice. Our main result is an extension of the decentralized CP-ABE scheme of Lewko and Waters with identity-based user revocation. Our revocation system is made feasible by removing the computational burden of a revocation event from the cloud service provider, at the expense of some permanent, yet acceptable overhead of the encryption and decryption algorithms run by the users. Thus, the computation overhead is distributed over a potentially large number of users, instead of putting it on a single party (e.g., a proxy server), which would easily lead to a performance bottleneck. Besides describing our scheme, we also give a formal proof of its security in the generic bilinear group and random oracle models.

Information theoretically secure multi-party computation implies severe communication overhead among the computing participants, as there is a need to reduce the polynomial degree after each multiplication. In particular, when the input is (practically) unbounded, the number of multiplications and therefore the communication bandwidth among the participants may be practically unbounded. In some scenarios the communication among the participants should better be avoided altogether, avoiding linkage among the secret share holders. For example, when processes in clouds operate over streaming secret shares without communicating with each other, they can actually hide their linkage and activity in the crowd. An adversary that is able to compromise processes in the cloud may need to capture and analyze a very large number of possible shares. Consider a dealer that wants to repeatedly compute functions on a long file with the assistance of $m$ servers. The dealer does not wish to leak either the input file or the result of the computation to any of the servers. We investigate this setting given two constraints. The dealer is allowed to share each symbol of the input file among the servers and is allowed to halt the computation at any point. However, the dealer is otherwise stateless. Furthermore, each server is not allowed any communication beyond the shares of the inputs that it receives and the information it provides to the dealer during reconstruction. We present a protocol in this setting for generalized string matching, including wildcards. We also present solutions for identifying other regular languages, as well as particular context free and context sensitive languages. The results can be described by a newly defined {\em accumulating automata} and {\em cascaded equations automata} which may be of an independent interest. As an application of {\em accumulating automata} and {\em cascaded equations automata}, secure and private repeated computations on a secret shared file among communicationless clouds are presented.

This survey, aimed mainly at mathematicians rather than practitioners, covers recent developments in homomorphic encryption (computing on encrypted data) and program obfuscation (generating encrypted but functional programs). Current schemes for encrypted computation all use essentially the same "noisy" approach: they encrypt via a noisy encoding of the message, they decrypt using an "approximate" ring homomorphism, and in between they employ techniques to carefully control the noise as computations are performed. This noisy approach uses a delicate balance between structure and randomness: structure that allows correct computation despite the randomness of the encryption, and randomness that maintains privacy against the adversary despite the structure. While the noisy approach "works", we need new techniques and insights, both to improve efficiency and to better understand encrypted computation conceptually.

Indistinguishability under chosen-ciphertext attack (INDCCA) is now considered the de facto security notion for public-key encryption. However, this sometimes offers a stronger security guarantee than what is needed. In this paper, we consider a weaker security notion, termed indistinguishability under plaintext-checking attacks (INDPCA), in which the adversary has only access to an oracle indicating whether or not a given ciphertext encrypts a given message. After formalizing this notion, we design a new public-key encryption scheme satisfying it. The new scheme is a variant of the Cramer-Shoup encryption scheme with shorter ciphertexts. Its security is also based on the plain Decisional Diffie-Hellman (DDH) assumption. Additionally, the algebraic properties of the new scheme allow proving plaintext knowledge using Groth-Sahai non-interactive zero-knowledge proofs or smooth projective hash functions. Finally, as a concrete application, we show that, for many password-based authenticated key exchange (PAKE) schemes in the Bellare-Pointcheval-Rogaway security model, we can safely replace the underlying INDCCA encryption schemes with our new INDPCA one. By doing so, we reduce the overall communication complexity of these protocols and obtain the most efficient PAKE schemes to date based on plain DDH.

We propose the first Key-policy Attribute-based Encryption (KP-ABE) scheme for (monotone) Boolean circuits based on bilinear maps. The construction is based on secret sharing and just one bilinear map, and can be viewed as an extension of the KP-ABE scheme in [7]. Selective security of the proposed scheme in the standard model is proved, and comparisons with the scheme in [5] based on leveled multilinear maps, are provided. Thus, for Boolean circuits representing multilevel access structures, our KP-ABE scheme is more efficient than the one in [5].

Group signatures, which allow users of a group to anonymously produce signatures on behalf of the group, are an important cryptographic primitive for privacy-enhancing applications. Over the years, various approaches to enhanced anonymity management mechanisms, which extend the standard feature of opening of group signatures, have been proposed. In this paper we show how pairing-based group signature schemes (PB-GSSs) following the sign-and-encrypt-and-prove (SEP) paradigm that are secure in the BSZ model can be generically transformed in order to support one particular enhanced anonymity management mechanism, i.e., we propose a transformation that turns every such PB-GSS into a PB-GSS with controllable linkability. Basically, this transformation replaces the public key encryption scheme used for identity escrow within a group signature scheme with a modified all-or-nothing public key encryption with equality tests scheme (denoted AoN-PKEET$^*$) instantiated from the respective public key encryption scheme. Thereby, the respective trapdoor is given to the linking authority as a linking key. The appealing benefit of this approach in contrast to other anonymity management mechanisms (such as those provided by traceable signatures) is that controllable linkability can be added to PB-GSSs based on the SEP paradigm for free, i.e., it neither influences the signature size nor the computational costs for signers and verifiers in comparison to the scheme without this feature.

In order to satisfy the different requirements of provable data possession in cloud computing, a multi-function provable data possession (MF-PDP) is proposed, which supports public verification, data dynamic, unlimited times verification, sampling verification. Besides, it is security in RO model and it is verification privacy under half trust model and can prevent from replacing attack and replay attack. The detail design is provided and the theory analysis about the correct, security and performance are also described. The experiment emulation and compare analysis suggest the feasibility and advantage.

We present a negative result of fuzzy extractors with computational security. Specifically, we show that, under a certain computational condition, the existence of a computational fuzzy extractor implies the existence of an information-theoretic fuzzy extractor with slightly weaker parameters. The condition is that the generation procedure of the fuzzy extractor is efficiently invertible by an injective function. Our result implies that to circumvent the limitations of information-theoretic fuzzy extractors, we need to employ computational fuzzy extractors that are not invertible by injective functions.

Web search is increasingly becoming an essential activity as it is frequently the most effective and convenient way of finding information. However, it can be a threat for the privacy of users because their queries may reveal their sensitive information. Private web search (PWS) solutions allow users to find information in the Internet while preserving their privacy. In particular, cryptography-based PWS (CB-PWS) systems provide strong privacy guarantees. This paper introduces a constant-round CB-PWS protocol which remains computationally efficient, compared to known CB-PWS systems. Our construction is comparable to similar solutions regarding users' privacy.

We present a new, general data structure that reduces the communication cost of recent tree-based ORAMs. Contrary to ORAM trees with constant height and path lengths, our new construction r-ORAM allows for trees with varying shorter path length. Accessing an element in the ORAM tree results in different communication costs depending on the location of the element. The main idea behind r-ORAM is a recursive ORAM tree structure, where nodes in the tree are roots of other trees. While this approach results in a worst-case access cost (tree height) at most as any recent tree-based ORAM, we show that the average cost saving is around 35% for recent binary tree ORAMs. Besides reducing communication cost, r-ORAM also reduces storage overhead on the server by 4% to 20% depending on the ORAM's client memory type. To prove r-ORAM's soundness, we conduct a detailed overflow analysis. r-ORAM's recursive approach is general in that it can be applied to all recent tree ORAMs, both constant and poly-log client memory ORAMs. Finally, we implement and benchmark r-ORAM in a practical setting to back up our theoretical claims.

Payments through cards have become very popular in today's world. All businesses now have options to receive payments through this instrument, moreover most organizations store card information of its customers in some way to enable easy payments in future. Credit card data is a very sensitive information and theft of this data is a serious threat to any company. Any organization that stores credit card data needs to achieve payment card industry (PCI) compliance, which is an intricate process where the organization needs to demonstrate that the data it stores is safe. Recently there has been a paradigm shift in treatment of the problem of storage of payment card information. In this new paradigm instead of the real credit card data a token is stored, this process is called ``tokenization". The token resembles the credit/debit card number but is in no way related to it. This solution relieves the merchant from the burden of PCI compliance in several ways. Though tokenization systems are heavily in use, to our knowledge, a formal cryptographic study of this problem has not yet been done. In this paper we initiate a study in this direction. We formally define the syntax of a tokenization system, and several notions of security for such systems. Finally, we provide some constructions of tokenizers and analyze their security in the light of our definitions.

We show that for certain class of unconditionally secure protocols and target functionalities, static security implies adaptive security in the UC model. Similar results were previously only known for models with weaker security and/or composition guarantees. The result is, for instance, applicable to a wide range of protocols based on secret sharing. It ``explains'' why an often used proof technique for such protocols works, namely where the simulator runs in its head a copy of the honest players using dummy inputs and generates a protocol execution by letting the dummy players interact with the adversary. When a new player $P_i$ is corrupted, the simulator adjusts the state of its dummy copy of $P_i$ to be consistent with the real inputs and outputs of $P_i$ and gives the state to the adversary. Our result gives a characterisation of the cases where this idea will work to prove adaptive security. As a special case, we use our framework to give the first proof of adaptive security of the seminal BGW protocol in the UC framework.

The security of public key validation protocols for web-based applications has recently attracted attention because of weaknesses in the certificate authority model, and consequent attacks. Recent proposals using public logs have succeeded in making certificate management more transparent and verifiable. How- ever, those proposals involve a fixed set of authorities which create a monopoly, and they have heavy reliance on trusted parties that monitor the logs. We propose a distributed transparent key infrastructure (DTKI), which greatly reduces the monopoly of service providers and removes the reliance on trusted parties. In addition, this paper formalises the public log data structure and provides a formal analysis of the security that DTKI guarantees.

Lattice-based cryptographic primitives are believed to offer resilience against attacks by quantum computers. We demonstrate the practicality of post-quantum key exchange by constructing ciphersuites for the Transport Layer Security (TLS) protocol that provide key exchange based on the ring learning with errors (R-LWE) problem; we accompany these ciphersuites with a rigorous proof of security. Our approach ties lattice-based key exchange together with traditional authentication using RSA or elliptic curve digital signatures: the post-quantum key exchange provides forward secrecy against future quantum attackers, while authentication can be provided using RSA keys that are issued by today's commercial certificate authorities, smoothing the path to adoption. Our cryptographically secure implementation, aimed at the 128-bit security level, reveals that the performance price when switching from non-quantum-safe key exchange is not too high. With our R-LWE ciphersuites integrated into the OpenSSL library and using the Apache web server on a 2-core desktop computer, we could serve 506 RLWE-ECDSA-AES128-GCM-SHA256 HTTPS connections per second for a 10 KiB payload. Compared to elliptic curve Diffie--Hellman, this means an 8 KiB increased handshake size and a reduction in throughput of only 21%. This demonstrates that provably secure post-quantum key-exchange can already be considered practical.

In the last few years garbled circuits (GC) have been elevated from being merely a compo- nent in Yao’s protocol for secure two-party computation, to a cryptographic primitive in its own right, following the growing number of applications that use GCs. Zero-Knowledge (ZK) protocols is one of these examples: In a recent paper Jawurek et al. [JKO13] showed that GCs can be used to construct efficient ZK proofs for unstructured languages. In this work we show that due to the property of this particular scenario (i.e., one of the parties knows all the secret input bits, and therefore all intermediate values in the computation), we can construct more efficient garbling schemes specifically tailored to this goal. As a highlight of our result, in one of our constructions only one ciphertext per gate needs to be communicated and XOR gates never require any cryptographic operations. In addition to making a step forward towards more practical ZK, we believe that our contribution is also interesting from a conceptual point of view: in the terminology of Bellare et al. [BHR12] our garbling schemes achieve au- thenticity, but no privacy nor obliviousness, therefore representing the first natural separation between those notions.

We introduce the concept of an \emph{invisible adaptive attack} (IAA) against cryptographic protocols. Or rather, it is a class of attacks, where the protocol itself is the attack, and where this cannot be seen by the security model. As an example, assume that we have some cryptographic security \emph{model} $M$ and assume that we have a current setting of the \emph{real world} with some cryptographic infrastructure in place, like a PKI. Select some object from this real world infrastructure, like the public key, $pk_0$, of some root certificate authority (CA). Now design a protocol $\pi$, which is secure in $M$. Then massage it into $\hat{\pi}$, which runs exactly like $\pi$, except that if the public key $pk$ of the root CA happens to be $pk_0$, then it will be completely insecure. Of course $\hat{\pi}$ should be considered insecure. However, in current security models existing infrastructure is modelled by generating it at random in the experiment defining security. Therefore, \emph{in the model}, the root CA will have a fresh, random public key $pk$. Hence $pk \ne pk_0$, except with negligible probability, and thus $M$ will typically deem $\hat{\pi}$ secure. The problem is that to notice the above attack in a security model, we need to properly model the correlation between $\hat{\pi}$ and $pk$. However, this correlation was made by the \emph{adversary} and it is naïve to believe that he will report this correlation correctly to the security model. It is the protocol itself and how to model it which is the attack. Furthermore, since a model cannot see a real world object, like "the current infrastructure", the correlation is invisible to the model when not reported by the adversary. Besides introducing the new concept of an invisible adaptive attack, we have the following contributions: \begin{enumerate} \item We show that a popular security model, the generalized universal composability (GUC) model introduced by Canetti, Dodis, Pass and Walfish in 2007\cite{CDPW07GUC}, allows an IAA, along the lines of the attack sketched above. This is not a problem specific to the GUC model, but it is more interesting to demonstrate this for the GUC model, as it was exactly developed to model security for protocols running with a common infrastructure which has been set up once and for all before the protocols are run. \item We show how to modify the GUC model to catch invisible adaptive attacks relative to existing infrastructure, introducing the \emph{strong externalized universal composability (SEUC)} model. Conceptually, when given a protocol to analyse, we will assume the \emph{worst case correlation} to the existing infrastructure, and we will deem it secure if it is secure in presence of this worst case correlation. I.e., a protocol is deemed insecure if there could \emph{exist} an IAA which is using the given protocol. We consider this new way to define security a main conceptual contribution of the paper. Properly modelling this conceptual idea is technical challenging and requires completely novel ideas. We consider this the main technical contribution of the paper. We prove that the new model has secure modular composition as the UC and the GUC model. \item We show that in the SEUC model any well-formed ideal functionality can be realised securely under standard computational assumptions and using an infrastructure, or setup assumption, known as an augmented common reference string. We do that by slightly modifying a protocol from \cite{CDPW07GUC} and reproving its security in the SEUC model. \end{enumerate} Our techniques seem specific to modelling IAAs relative to \emph{existing infrastructure}. One can, however, imagine more general IAAs, relative, for instance, to values being dynamically generated by secure protocols currently running in practice, like a broadcast service or a cloud service. We do not know how to model IAAs in general and hence open up a new venue of investigation.

The increasing availability and use of biometric data for authentication and other purposes leads to situations when sensitive biometric data is to be handled or used in computation by entities who may not be fully trusted or otherwise are not authorized to have full access to such data. This calls for mechanisms of provably protecting biometric data while still allowing the computation to take place. This work is motivated by the problem of privacy-preserving matching of two fingerprints (used for secure fingerprint authentication or identification) using traditional minutia-based representation of fingerprints that leads to the most discriminative (i.e., accurate) fingerprint comparisons. Unlike previous work in the security literature, we would like to focus on algorithms that are guaranteed to find the maximum number of minutiae that can be paired together between two fingerprints leading to more accurate comparisons. To address this problem, we formulate it as a flow network problem and reduce it to finding maximum matching size in bipartite graphs. The resulting problem is in turn reduced to computing the rank of a (non-invertible) matrix, formed as a randomized adjacency matrix of the bipartite graph. We then provide data-oblivious algorithms for matrix rank computation and consecutively finding maximum matching size in a bipartite graph and also extend the algorithms to solve the problem of accurate fingerprint matching. These algorithms lead to their secure counterparts using standard secure two-party or multi-party techniques as we show later in this work. Lastly, we implement secure fingerprint matching in the secure two-party computation setting using garbled circuit evaluation techniques. Our experimental results demonstrate that the techniques are very efficient, leading to performance similar to that of other fastest secure fingerprint matching techniques, despite higher complexity of our solution that higher accuracy demands.

Non-interactive zero-knowledge proofs of knowledge for general NP statements are a powerful cryptographic primitive, both in theory and in practical applications. Recently, much research has focused on achieving an additional property, succinctness, requiring the proof to be very short and easy to verify. Such proof systems are known as zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs), and are desired when communication is expensive, or the verifier is computationally weak. Existing zk-SNARK implementations have severe scalability limitations, in terms of space complexity as a function of the size of the computation being proved (e.g., running time of the NP statement’s decision program). First, the size of the proving key is quasilinear in the upper bound on the computation size. Second, producing a proof requires "writing down" all intermediate values of the entire computation, and then conducting global operations such as FFTs. The bootstrapping technique of Bitansky et al. (STOC ’13), following Valiant (TCC ’08), offers an approach to scalability, by recursively composing proofs: proving statements about acceptance of the proof system’s own verifier (and correctness of the program’s latest step). Alas, recursive composition of known zk-SNARKs has never been realized in practice, due to enormous computational cost. Using new elliptic-curve cryptographic techniques, and methods for exploiting the proof systems’ field structure and nondeterminism, we achieve the first zk-SNARK implementation that practically achieves recursive proof composition. Our zk-SNARK implementation runs random-access machine programs and produces proofs of their correct execution, on today’s hardware, for any program running time. It takes constant time to generate the keys that support all computation sizes. Subsequently, the proving process only incurs a constant multiplicative overhead compared to the original computation’s time, and an essentially-constant additive overhead in memory. Thus, our zk-SNARK implementation is the first to have a well-defined, albeit low, clock rate of "verified instructions per second".

We initiate the study of cryptography for parallel RAM (PRAM) programs. The PRAM model captures modern multi-core architectures and cluster computing models, where several processors execute in parallel and make accesses to shared memory, and provides the “best of both” circuit and RAM models, supporting both cheap random access and parallelism. We propose and attain the notion of Oblivious PRAM. We present a compiler taking any PRAM into one whose distribution of memory accesses is statistically independent of the data (with negligible error), while only incurring a polylogarithmic slowdown (in both total and parallel complexity). We discuss applications of such a compiler, building upon recent advances relying on Oblivious (sequential) RAM (Goldreich Ostrovsky JACM’12). In particular, we demonstrate the construction of a garbled PRAM compiler based on an OPRAM compiler and secure identity-based encryption.

The paper is about algorithms for the inhomogeneous short integer solution problem: Given $(A,s)$ to find a short vector $x$ such that $Ax \equiv s \pmod{q}$. We consider algorithms for this problem due to Camion and Patarin; Wagner; Schroeppel and Shamir; Minder and Sinclair; Howgrave-Graham and Joux (HGJ); Becker, Coron and Joux (BCJ). Our main results include: Applying the Hermite normal form (HNF) to get faster algorithms; A heuristic analysis of the HGJ and BCJ algorithms in the case of density greater than one; An improved cryptanalysis of the SWIFFT hash function; A new method that exploits symmetries to speed up algorithms for Ring-SIS in some cases. This paper is published in Journal of Cryptology, Volume 32, Issue 1 (2019) 35--83.

This paper presents new speed records for multiprecision multiplication on the AVR ATmega family of 8-bit microcontrollers. For example, our software takes only 1976 cycles for the multiplication of two 160-bit integers; this is more than 15% faster than previous work. For 256-bit inputs, our software is not only the first to break through the 6000-cycle barrier; with only 4797 cycles it also breaks through the 5000-cycle barrier and is more than 21% faster than previous work.We achieve these speed records by carefully optimizing the Karatsuba multiplication technique for AVR ATmega. One might expect that subquadratic-complexity Karatsuba multiplication is only faster than algorithms with quadratic complexity for large inputs. This paper shows that it is in fact faster than fully unrolled product-scanning multiplication already for surprisingly small inputs, starting at 48 bits. Our results thus make Karatsuba multiplication the method of choice for high-performance implementations of elliptic-curve cryptography on AVR ATmega microcontrollers.

Discrete Gaussian sampling is an integral part of many lattice based cryptosystems such as public-key encryption, digital signature schemes and homomorphic encryption schemes. In this paper we propose a compact and fast Knuth-Yao sampler for sampling from a narrow discrete Gaussian distribution with very high precision. The designed samplers have a maximum statistical distance of $2^{-90}$ to a true discrete Gaussian distribution. In this paper we investigate various optimization techniques to achieve minimum area and cycle requirement. For the standard deviation 3.33, the most area-optimal implementation of the bit-scan operation based Knuth-Yao sampler consumes 30 slices on the Xilinx Virtex 5 FPGAs, and requires on average 17 cycles to generate a sample. We improve the speed of the sampler by using a precomputed table that directly maps the initial random bits into samples with very high probability. The fast sampler consumes 35 slices and spends on average 2.5 cycles to generate a sample. However the sampler architectures are not secure against timing and power analysis based attacks. In this paper we propose a random shuffle method to protect the Gaussian distributed polynomial against such attacks. The side channel attack resistant sampler architecture consumes 52 slices and spends on average 420 cycles to generate a polynomial of 256 coefficients.

Structure-preserving signature schemes can be very useful in the construction of new cryptographic operations like blind signatures. Recently several of these schemes have been proposed. The security of signature-preserving signature schemes is still proved by hand, which can be a laborious task. One of the ways to prove security of these schemes algebraic analysis can be used. We present an approach to perform this analysis and the first tool, CheckSPS, that can do an algebraic security analysis of these schemes, using SMT solvers as backend. This can help in constructing new schemes and analyse existing schemes. Our tool can handle all the common security objectives for signature schemes, i.e. existential unforgeability and strong existential unforgeability, and all the common capabilities for adversaries, i.e. random message attacks, non-adaptive chosen message attacks and adaptive chosen message attacks. The tool is sound, so if an attack is found it is actually possible to construct a forged signature.

Authenticated key exchange (AKE) protocols, such as IKE and SSL/TLS, have been widely used to ensure secure communication over the Internet. We present in this paper a practical and provably secure AKE protocol from ideal lattices, which is conceptually simple and has similarities to the Diffie-Hellman based protocols such as HMQV (CRYPTO 2005) and OAKE (CCS 2013). Our protocol does not rely on other cryptographic primitives---in particular, it does not use signatures---simplifying the protocol and resting the security solely on the hardness of the ring learning with errors (RLWE) problem. The security is proven in a version of the Bellare-Rogaway model, with enhancements to capture weak Perfect Forward Secrecy. We also present concrete choices of parameters for different security levels. A proof-of-concept implementation shows our protocol is a practical candidate post-quantum key exchange protocol.

We propose the first construction for achieving adaptively secure functional encryption (FE) for poly-sized circuits (without complexity leveraging) from indistinguishability obfuscation (iO). Our reduction has polynomial loss to the underlying primitives. We develop a "punctured programming'' approach to constructing and proving systems where outside of obfuscation we rely only on primitives realizable from pseudo random generators. Our work consists of two constructions. Our first FE construction is provably secure against any attacker that is limited to making all of its private key queries after it sees the challenge ciphertext. (This notion implies selective security.) Our construction makes use of an we introduce called puncturable deterministic encryption (PDE) which may be of independent. With this primitive in place we show a simpleconstruction FE construction. We then provide a second construction that achieves adaptive security from indistinguishability obfuscation. Our central idea is to achieve an adaptively secure functional encryption by bootstrapping from a one-bounded FE scheme that is adaptively secure. By using bootstrapping we can use "selective-ish'' techniques at the outer level obfuscation level and push down the challenge of dealing with adaptive security is then FE scheme, where it has been already been solved. We combine our bootstrapping framework with a new "key signaling'' technique to achieve our construction and proof.

We present a construction for non-interactive zero-knowledge proofs of knowledge in the random oracle model from general sigma-protocols. Our construction is secure against quantum adversaries. Prior constructions (by Fiat-Shamir and by Fischlin) are only known to be secure against classical adversaries, and Ambainis, Rosmanis, Unruh (FOCS 2014) gave evidence that those constructions might not be secure against quantum adversaries in general. To prove security of our constructions, we additionally develop new techniques for adaptively programming the quantum random oracle.

In their seminal work on non-malleable cryptography, Dolev, Dwork and Naor, showed how to construct a non-malleable commitment with logarithmically-many "rounds"/"slots", the idea being that any adversary may successfully maul in some slots but would fail in at least one. Since then new ideas have been introduced, ultimately resulting in constant-round protocols based on any one-way function. Yet, in spite of this remarkable progress, each of the known constructions of non-malleable commitments leaves something to be desired. In this paper we propose a new technique that allows us to construct a non-malleable protocol with only a single ``slot", and to improve in at least one aspect over each of the previously proposed protocols. Two direct byproducts of our new ideas are a four round non-malleable commitment and a four round non-malleable zero-knowledge argument, the latter matching the round complexity of the best known zero-knowledge argument (without the non-malleability requirement). The protocols are based on the existence of one-way functions and admit very efficient instantiations via standard homomorphic commitments and sigma protocols. Our analysis relies on algebraic reasoning, and makes use of error correcting codes in order to ensure that committers' tags differ in many coordinates. One way of viewing our construction is as a method for combining many atomic sub-protocols in a way that simultaneously amplifies soundness and non-malleability, thus requiring much weaker guarantees to begin with, and resulting in a protocol which is much trimmer in complexity compared to the existing ones.

The SPEKE protocol is commonly considered one of the classic Password Authenticated Key Exchange (PAKE) schemes. It has been included in international standards (particularly, ISO/IEC 11770-4 and IEEE 1363.2) and deployed in commercial products (e.g., Blackberry). We observe that the original SPEKE specification is subtly different from those defined in the ISO/IEC 11770-4 and IEEE 1363.2 standards. We show that those differences have critical security implications by presenting two new attacks on SPEKE: an impersonation attack and a key-malleability attack. The first attack allows an attacker to impersonate a user without knowing the password by engaging in two parallel sessions with the victim. The second attack allows an attacker to manipulate the session key established between two honest users without being detected. Both attacks are applicable to the original SPEKE scheme, and are only partially addressed in the ISO/IEC 11770-4 and IEEE 1363.2 standards. We highlight deficiencies in both standards and suggest concrete changes.

Membership encryption is a newly developed cryptographic primitive that combines membership proof and encryption into an unified setting. This paper presents a new flexible membership encryption scheme which is provably secure and significantly more efficient than the previous scheme. Further we apply our proposed membership encryption to construct a round optimal 1-out-of-$n$ priced oblivious transfer (POT) protocol which, unlike the existing 1-out-of-n POT schemes,is proven secure under the universally composable (UC) security model and thus preserves security when it is executed with multiple protocol instances that run concurrently in an adversarily controlled way. Moreover, using our membership encryption, the POT protocol exhibits constant communication complexity on the buyer's side and $O(n)$ communication cost on the vendor's side, which is so far the best known in the literature.

Template attacks are widely accepted as the strongest side-channel attacks from the information theoretic point of view, and they can be used as a very powerful tool to evaluate the physical security of cryptographic devices. Template attacks consist of two stages, the profiling stage and the extraction stage. In the profiling stage, the attacker is assumed to have a large number of power traces measured from the reference device, using which he can accurately characterize signals and noises in different points. However, in practice, the number of profiling power traces may not be sufficient. In this case, signals and noises are not accurately characterized, and the key-recovery efficiency of template attacks is significantly influenced. We show that, the attacker can still make template attacks powerfully enough in practice as long as the priori knowledge about the reference device be obtained. We note that, the priori knowledge is just a prior distribution of the signal component of the instantaneous power consumption, which the attacker can easily obtain from his previous experience of conducting template attacks, from Internet and many other possible ways. Evaluation results show that, the priori knowledge, even if not accurate, can still help increase the power of template attacks, which poses a serious threat to the physical security of cryptographic devices.

We use cryptographic techniques to study zone enumeration in DNSSEC. DNSSEC is designed to prevent attackers from tampering with domain name system (DNS) messages. The cryptographic machinery used in DNSSEC, however, also creates a new vulnerability, zone enumeration, enabling an adversary to use a small number of online DNSSEC queries combined with offline dictionary attacks to learn which domain names are present or absent in a DNS zone. We prove that the current DNSSEC standard, with NSEC and NSEC3 records, inherently suffers from zone enumeration: specifically, we show that security against (1) attackers that tamper with DNS messages and (2) privacy against zone enumeration cannot be satisfied simultaneously, unless the DNSSEC nameserver performs online public-key cryptographic operations. We then propose a new construction that uses online public-key cryptography to solve the problem of DNSSEC zone enumeration. NSEC5 can be thought of as a variant of NSEC3, in which the unkeyed hash function is replaced with a deterministic RSA-based keyed hashing scheme. With NSEC5, a zone remains protected against network attackers and compromised nameservers even if the secret NSEC5-hashing key is compromised; leaking the NSEC5-hashing key only harms privacy against zone enumeration, effectively downgrading the security of NSEC5 back to that of the current DNSSEC standard (with NSEC3).

We provide a generic transformation from any \emph{affine} message authentication code (MAC) to an identity-based encryption (IBE) scheme over pairing groups of prime order. If the MAC satisfies a security notion related to unforgeability against chosen-message attacks and, for example, the $k$-Linear assumption holds, then the resulting IBE scheme is adaptively secure. Our security reduction is tightness preserving, i.e., if the MAC has a tight security reduction so has the IBE scheme. Furthermore, the transformation also extends to hierarchical identity-based encryption (HIBE). We also show how to construct affine MACs with a tight security reduction to standard assumptions. This, among other things, provides a tightly secure IBE in the standard model.

The existence of succinct non-interactive arguments for NP (i.e., non-interactive computationally-sound proofs where the verifier's work is essentially independent of the complexity of the NP nondeterministic verifier) has been an intriguing question for the past two decades. Other than CS proofs in the random oracle model [Micali, FOCS '94], the only existing candidate construction is based on an elaborate assumption that is tailored to a specific protocol [Di Crescenzo and Lipmaa, CiE '08]. We formulate a general and relatively natural notion of an \emph{extractable collision-resistant hash function (ECRH)} and show that, if ECRHs exist, then a modified version of Di Crescenzo and Lipmaa's protocol is a succinct non-interactive argument for NP. Furthermore, the modified protocol is actually a succinct non-interactive \emph{adaptive argument of knowledge (SNARK).} We then propose several candidate constructions for ECRHs and relaxations thereof. We demonstrate the applicability of SNARKs to various forms of delegation of computation, to succinct non-interactive zero knowledge arguments, and to succinct two-party secure computation. Finally, we show that SNARKs essentially imply the existence of ECRHs, thus demonstrating the necessity of the assumption. Going beyond $\ECRH$s, we formulate the notion of {\em extractable one-way functions ($\EOWF$s)}. Assuming the existence of a natural variant of $\EOWF$s, we construct a $2$-message selective-opening-attack secure commitment scheme and a 3-round zero-knowledge argument of knowledge. Furthermore, if the $\EOWF$s are concurrently extractable, the 3-round zero-knowledge protocol is also concurrent zero-knowledge. Our constructions circumvent previous black-box impossibility results regarding these protocols by relying on $\EOWF$s as the non-black-box component in the security reductions.

In this paper we study a scan based side channel attack against the Grain family of stream ciphers. The attack works because scan chain test of circuits can be transformed into a powerful cryptographic attack due to the properties of scan based technique. So as a result the attack targets the test circuitry. We show how the attacker gains the knowledge about the locations of internal state bits of the NFSR and the LFSR and how he finds the secret key.

NMAC is a mode of operation which turns a fixed input-length keyed hash function f into a variable input-length function. A~practical single-key variant of NMAC called HMAC is a very popular and widely deployed message authentication code (MAC). Security proofs and attacks for NMAC can typically be lifted to HMAC. NMAC was introduced by Bellare, Canetti and Krawczyk [Crypto'96], who proved it to be a secure pseudorandom function (PRF), and thus also a MAC, assuming that (1) f is a PRF and (2) the function we get when cascading f is weakly collision-resistant. Unfortunately, HMAC is typically instantiated with cryptographic hash functions like MD5 or SHA-1 for which (2) has been found to be wrong. To restore the provable guarantees for NMAC, Bellare [Crypto'06] showed its security based solely on the assumption that f is a PRF, albeit via a non-uniform reduction. Our first contribution is a simpler and uniform proof: If f is an \eps-secure PRF (against q queries) and a \delta-non-adaptively secure PRF (against q queries), then NMAC^f is an (\eps+lq\delta)-secure PRF against q queries of length at most l blocks each. We then show that this \eps+lq\delta bound is basically tight. For the most interesting case where lq\delta>=\eps we prove this by constructing an f for which an attack with advantage lq\delta exists. This also violates the bound O(l\eps) on the PRF-security of NMAC recently claimed by Koblitz and Menezes. Finally, we analyze the PRF-security of a modification of NMAC called NI [An and Bellare, Crypto'99] that differs mainly by using a compression function with an additional keying input. This avoids the constant rekeying on multi-block messages in NMAC and allows for a security proof starting by the standard switch from a PRF to a random function, followed by an information-theoretic analysis. We carry out such an analysis, obtaining a tight lq^2/2^c bound for this step, improving over the trivial bound of l^2q^2/2^c. The proof borrows combinatorial techniques originally developed for proving the security of CBC-MAC [Bellare et al., Crypto'05]. We also analyze a variant of NI that does not include the message length in the last call to the compression function, proving a l^{1+o(1)}q^2/2^c bound in this case.

In Broadcast Encryption (BE) systems like Pay-TV, AACS, online content sharing and broadcasting, reducing the header length (communication overhead per session) is of practical interest. The Subset Difference (SD) scheme due to Naor-Naor-Lotspiech (NNL) is the most popularly used BE scheme. It assumes an underlying full binary tree to assign keys to subsets of users. In this work, we associate short tree structures of height $a$ to nodes in the binary tree to assign keys to more subsets. This ensures that for any set of revoked users, the header length is in general less and never more than the NNL-SD scheme. Experimental studies show that the average header length is always less than that of the NNL-SD scheme and decreases as $a$ increases. User storage in the new scheme is more than that of the NNL-SD scheme but is not prohibitively expensive. By choosing a suitable value of $a$, it is possible to obtain substantial reduction in the communication overhead at the cost of a tolerable increase in the user storage.

This is to announce a more efficient and safe cryptographic engine than the current AES standard. A way has been developed using a long-standing cryptographic algorithm along with Algebraic law to produce a system that is at least 4 times faster than the AES and is more secure.

Simple AEAD Hardware Interface (SÆHI) is a hardware cryptographic interface aimed at CAESAR Authenticated Encryption with Associated Data (AEAD) algorithms. Cryptographic acceleration is typically achieved either with a coprocessor or via instruction set extensions. ISA modifications require re-engineering the CPU core, making the approach inapplicable outside the realm of open source processor cores. At minimum, we suggest implementing CAESAR AEADs as universal memory-mapped cryptographic coprocessors, synthesizable even on low end FPGA platforms. AEADs complying to SÆHI must also include C language API drivers targeting low-end MCUs that directly utilize the memory mapping in a ``bare metal'' fashion. This can also be accommodated on MMU-equipped mid-range CPUs. Extended battery life and bandwidth resulting from dedicated cryptographic hardware is vital for currently dominant computing and communication devices: mobile phones, tablets, and Internet-of-Things (IoT) applications. We argue that these should be priority hardware optimization targets for AEAD algorithms with realistic payload profiles. We demonstrate a fully integrated implementation of WhirlBob and Keyak AEADs on the FPGA fabric of Xilinx Zynq 7010. This low-cost System-on-Chip (SoC) also houses a dual-core Cortex-A9 CPU, closely matching the architecture of many embedded devices. The on-chip coprocessor is accessible from user space with a Linux kernel driver. An integration path exists all the way to end-user applications.

At Crypto 2013, Coron, Lepoint, and Tibouchi~(CLT) proposed a practical Graded Encoding Scheme (GES) over the integers, which has very similar cryptographic features to ideal multilinear maps. In fact, the scheme of Coron~{\em et al.} is the second proposal of a secure GES, and has advantages over the first scheme of Garg, Gentry, and Halevi~(GGH). For example, unlike the GGH construction, the subgroup decision assumption holds in the CLT construction. Immediately following the elegant innovations of the GES, numerous GES-based cryptographic applications were proposed. Although these applications rely on the security of the underlying GES, the security of the GES has not been analyzed in detail, aside from the original papers produced by Garg~{\em et~al.} and Coron~{\em et~al.} We present an attack algorithm against the system parameters of the CLT GES. The proposed algorithm's complexity $\tilde\bO(2^{\rho/2})$ is exponentially smaller than $\tilde\bO(2^{\rho})$ of the previous best attack of Coron~{\em et al.}, where $\rho$ is a function of the security parameter. Furthermore, we identify a flaw in the generation of the zero-testing parameter of the CLT GES, which drastically reduces the running time of the proposed algorithm. The experimental results demonstrate the practicality of our attack.

In this paper a new public key system based on polynomials over finite fields GF(2) is developed.The security of the system is based on the difficulty of solving discrete logarithms over GF(2^k) with sufficiently large k. The presented system has all features of ordinary public key schemes such as public key encryption and digital signatures. The security and implementation aspects of the presented system are also introduced along with comparison with other well known public- key systems.

Differential Fault Analysis is a powerful cryptanalytic tool to reveal secret keys of cryptographic algorithms. By corrupting the computation of an algorithm, an attacker gets additional information about the secret key. In 2012, several Differential Fault Analyses on the AES cipher were analyzed from an information-theoretic perspective. This analysis exposed whether or not the leaked information was fully exploited. It revealed if an analysis was already optimal or if it could still be improved. We applied the same approach to all existing Differential Fault Analyses on the CLEFIA cipher. We show that only some of these attacks are already optimal. We improve those analyses which did not exploit all information. With one exception, all attacks against CLEFIA-128 reach the theoretical limit after our improvement. Our improvement of an attack against CLEFIA-192 and CLEFIA-256 reduces the number of fault injections to the lowest possible number reached to date.

This paper analyzes the cost of breaking ECC under the following assumptions: (1) ECC is using a standardized elliptic curve that was actually chosen by an attacker; (2) the attacker is aware of a vulnerability in some curves that are not publicly known to be vulnerable. This cost includes the cost of exploiting the vulnerability, but also the initial cost of computing a curve suitable for sabotaging the standard. This initial cost depends upon the acceptability criteria used by the public to decide whether to allow a curve as a standard, and (in most cases) also upon the chance of a curve being vulnerable. This paper shows the importance of accurately modeling the actual acceptability criteria: i.e., figuring out what the public can be fooled into accepting. For example, this paper shows that plausible models of the “Brainpool acceptability criteria” allow the attacker to target a one-in-a-million vulnerability.