PUF (Physically Unclonable Function) technologies attract attention as a candidate to prevent counterfeit chips. A latch PUF is known as a high performance PUF among various types of proposed PUFs. In this paper we describe an experiment on a dynamic attack to a latch PUF consisting of RS latches, such as measuring the latch output by a probe connection after a FIB (Focused Ion Beam) processing. As a result, we confirmed that the latch PUF using the RS latch has a tolerance for the dynamic analysis, because the RS latch output was influenced and changed by the FIB processing in our experiment.

The references [9,3,1] treat timing attacks on RSA with CRT and Montgomery's multiplication algorithm in unprotected implementations. It has been widely believed that exponent blinding would prevent any timing attack on RSA. At cost of significantly more timing measurements this paper extends the before-mentioned attacks to RSA with CRT when Montgomery's multiplication algorithm and exponent blinding are applied. Simulation experiments are conducted, which confirm the theoretical results. Effective countermeasures exist. In particular, the attack efficiency is higher than in the previous version [12] while large parts of both papers coincide.

We present a construction of a private-key functional encryption scheme for any family of randomized functionalities based on any such scheme for deterministic functionalities that is sufficiently expressive. Instantiating our construction with existing schemes for deterministic functionalities, we obtain schemes for any family of randomized functionalities based on a variety of assumptions (including the LWE assumption, simple assumptions on multilinear maps, and even the existence of any one-way function) offering various trade-offs between security and efficiency. Previously, Goyal, Jain, Koppula and Sahai [Cryptology ePrint Archive, 2013] constructed a public-key functional encryption scheme for any family of randomized functionalities based on indistinguishability obfuscation. One of the key insights underlying our work is that, in the private-key setting, a sufficiently expressive functional encryption scheme may be appropriately utilized for implementing proof techniques that were so far implemented based on obfuscation assumptions (such as the punctured programming technique of Sahai and Waters [STOC 2014]). We view this as a contribution of independent interest that may be found useful in other settings as well.

Assuming the existence of indistinguishability obfuscation (iO), we show that a number of prominent transformations in the random-oracle model are uninstantiable in the standard model. We start by showing that the Encrypt-with-Hash transform of Bellare, Boldyreva and O'Neill (CRYPTO 2007) for converting randomized public-key encryption schemes to deterministic ones is not instantiable in the standard model. To this end, we build on the recent work of Brzuska, Farshim and Mittelbach (CRYPTO 2014) and rely on the existence of iO for circuits or iO for Turing machines to derive uninstantiability for hash functions of a priori bounded polynomial size and arbitrary polynomial size, respectively. The techniques that we use to establish this result are flexible and lend themselves to a number of other transformations such as the classical Fujisaki--Okamoto transform (CRYPTO 1998) and transformations akin to those by Bellare and Keelveedhi (CRYPTO 2011) and Douceur et al. (ICDCS 2002) for obtaining KDM-secure encryption and de-duplication schemes respectively. Our results call for a re-assessment of scheme design in the random-oracle model and highlight the need for new transforms that do not suffer from iO-based attacks.

=== NOTE: This submission has been replaced by a corrected version (2015/772). === We introduce a new security notion for public-key encryption (PKE) that we dub non-malleability under (chosen-ciphertext) self-destruct attacks (NM-SDA), which appears to be the strongest natural PKE security notion below full-blown chosen-ciphertext (IND-CCA) security. In this notion, the adversary is allowed to ask many adaptive ``parallel'' decryption queries (i.e., a query consists of many ciphertexts) up to the point when the first invalid ciphertext is submitted. As such, NM-SDA security generalizes non-malleability against chosen plaintext attacks (NM-CPA, where only one parallel decryption query is allowed) and recently introduced indistinguishability against (chosen-ciphertext) self-destruct attacks (IND-SDA, where each adaptive query consists of a single ciphertext). After showing that NM-SDA is a {\em strict} strengthening of NM-CPA and IND-SDA and allows for more applications, we establish the following two results: Domain Extension: For any $K > 1$, there is a black-box construction of a $K$-bit NM-SDA PKE scheme from a single-bit NM-SDA PKE scheme. Moreover, this can be done using only $O(\lambda)$ calls to the underlying single-bit NM-SDA scheme, where $\lambda$ is the security parameter. To achieve our goal, we define and construct a novel type of continuous non-malleable code (NMC), called secret-state NMC, as we show that standard continuous NMCs are not enough for the natural ``expand-then-encrypt-bit-by-bit'' approach to work. Black-Box Construction from IND-CPA: Prior work showed that NM-CPA secure PKE can be constructed from any IND-CPA secure PKE in a black-box way. Here we show that the same construction actually achieves our strictly stronger notion of NM-SDA security. (This requires a non-trivial extension of the original security proof to handle multiple parallel decryption queries.) Hence, the notions of IND-CPA, NM-CPA, IND-SDA and NM-SDA security are all equivalent, lying (plausibly, strictly?) below IND-CCA security. We also show how to improve the rate of the resulting NM-SDA scheme from quadratic to linear.

In this work, we show how to use the positive results on succinct argument systems to prove impossibility results on leakage-resilient black-box zero knowledge. This recently proposed notion of zero knowledge deals with an adversary that can make leakage queries on the state of the prover. Our result holds for black-box simulation only and we also give some insights on the non-black-box case. Additionally, we show that, for several functionalities, leakage-resilient multi-party computation is impossible (regardless of the number of players and even if just one player is corrupted). More in details, we achieve the above results by extending a technique of [Nielsen, Venturi, Zottarel -- PKC 13] to prove lower bounds for leakage-resilient security. Indeed, we use leakage queries to run an execution of a communication-efficient protocol in the head of the adversary. Moreover, to defeat the black-box simulator we connect the above technique for leakage resilience to security against reset attacks. Our results show that the open problem of [Ananth, Goyal, Pandey -- Crypto 14] (i.e., continual leakage-resilient proofs without a common reference string) has a negative answer when security through black-box simulation is desired. Moreover our results close the open problem of [Boyle et al. -- STOC 12] for the case of black-box simulation (i.e., the possibility of continual leakage-resilient secure computation without a leak-free interactive preprocessing).

Template attacks are widely accepted to be the most powerful side-channel attacks from an information theoretic point of view. For template attacks to be practical, one needs to choose some special samples as the interesting points in actual power traces. Up to now, many different approaches were introduced for choosing interesting points for template attacks. However, it is unknown that whether or not the previous approaches of choosing interesting points will lead to the best classification performance of template attacks. In this work, we give a negative answer to this important question by introducing a practical new approach which has completely different basic principle compared with all the previous approaches. Our new approach chooses the point whose distribution of samples approximates to a normal distribution as the interesting point. Evaluation results exhibit that template attacks based on the interesting points chosen by our new approach can achieve obvious better classification performance compared with template attacks based on the interesting points chosen by the previous approaches. Therefore, our new approach of choosing interesting points should be used in practice to better understand the practical threats of template attacks.

It is well known that the random oracle model is not sound in the sense that there exist cryptographic systems that are secure in the random oracle model but when instantiated by any family of hash functions become insecure. However, all known separation results require the attacker to send an appropriately crafted message to the challenger in order to break security. Thus, this leaves open the possibility that some cryptographic schemes, such as bit-encryption, are still sound in the random oracle model. In this work we refute this possibility, assuming the existence of indistinguishability obfuscation. We do so in the following way. First, we present a random oracle separation for bit-encryption; namely, we show that there exists a bit-encryption protocol secure in the random oracle model but \emph{completely insecure} when the random oracle is instantiated by any concrete function. Second, we show how to adapt this separation to work for most natural simulation-based and game-based definitions. Our techniques can easily be adapted to other idealized models, and thus we present a \emph{unified approach} to showing separations for most protocols of interest in most idealized models.

Car-to-car and Car-to-Infrastructure messages exchanged in Intelligent Transportation Systems can reach reception rates up to and over 1000 messages per second. As these messages contain ECDSA signatures this puts a very heavy load onto the verification hardware. In fact the load is so high that currently it can only be achieved by implementations running on high end CPUs and FPGAs. These implementations are far from cost-effective nor energy efficient. In this paper we present an ASIC implementation of a dedicated ECDSA verification engine that can reach verification rates of up to 27.000 verifications per second using only 1.034 kGE.

Abstract—Voting systems based on paper ballots has a long history with various problems. Vote-selling and correct outcome are two major problems among many. In this work, we propose a new solution to these problems by using UltraViolet (UV) fiber paper Physical Unclonable Function (PUF). When applied this solution not only prevents vote-selling but also ensures the correctness of the outcome. With these two problems eliminated, the voting systems based on paper ballots will have complete integrity.

A differential attack tries to capture the round keys corresponding to the S-boxes activated by a differential. In this work, we show that for a fixed output difference of an S-box, it may not be possible to distinguish the guessed keys that have a specific difference. We introduce these differences as differential factors. Existence of differential factors can reduce the time complexity of differential attacks and as an example we show that the 10, 11, and 12-round differential-linear attacks of Dunkelman et al. on SERPENT can actually be performed with time complexities reduced by a factor of 4, 4, and 8, respectively.

The blind signature scheme permits the user to acquire a signature from the signer; however, the message and the final signature are unknown to the signer. In a partially blind signature (PBS) scheme, the signer can explicitly incorporate a common information in the signature based on some agreement with the user and without violating the blindness property. Many PBS schemes have been proposed recently either by using certificate authority-based public infrastructure (CA-PKI) or pairing along with map-to-point function. The CA-PKI-based PBS scheme needs huge computation and storage to keep public keys and certificates. On the other hand, pairing and map-to-point function are costly operations. Thus, the ID-PBS scheme without pairing is more appropriate for real environments, and an efficient pairing-free ID-PBS scheme is proposed in this paper. In the random oracle model, our scheme is analyzed to be provably secure. The proposed scheme is used to design an online e-cash system, in which a bank agrees on a common piece of information with a customer and can blindly sign some messages. It may be noted that our e-cash system has the properties of unforgeability, unlinkability, and non-deniability and can prevent the double-spending of e-cash.

Cryptographic protocols with adaptive security ensure that security holds against an adversary who can dynamically determine which parties to corrupt as the protocol progresses---or even after the protocol is finished. In the setting where all parties may potentially be corrupted, and secure erasure is not assumed, it has been a long-standing open question to design secure-computation protocols with adaptive security running in constant rounds. Here, we show a constant-round, universally composable protocol for computing any functionality, tolerating a malicious, adaptive adversary corrupting any number of parties. Interestingly, our protocol can compute all functionalities, not just adaptively well-formed ones.

In standard models of distributed computation, point-to-point channels between parties are assumed to be authenticated by some pre-existing means. In other cases, even stronger pre-existing setup—e.g., a public-key infrastructure (PKI)—is assumed. These assumptions are too strong for open, peer-to-peer networks, where parties do not necessarily have any prior relationships and can come and go as they please. Nevertheless, these assumptions are made due to the prevailing belief that nothing “interesting” can be achieved without them. Taking inspiration from Bitcoin, we show that precise bounds on computational power can be used in place of pre-existing setup to achieve weaker (but nontrivial) notions of security. Specifically, under the assumption that each party can solve cryptographic puzzles only at a bounded rate (and the existence of digital signatures), we show that without prior setup and with no bound on the number of corruptions, a group of parties can agree on a PKI with which they can then realize pseudonymous notions of authenticated communication, broadcast, and secure computation. Roughly, “pseudonymous” here means that parties are identified by pseudoynms rather than by their true identities.

Side channel attacks -- attacks that exploit implementation-dependent information of a cryptosystem -- have been shown to be highly detrimental, and the cryptographic community has recently focused on developing techniques for securing implementations against such attacks. An important model called \emph{Only Computation Leaks} (OCL) [Micali and Reyzin, TCC '04] and its stronger variants were proposed to model a broad class of leakage attacks (a type of side-channel attack). These models allow for unbounded, arbitrary leakage as long as (1) information in each leakage observation is bounded, and (2) different parts of the computation leak independently. Various results and techniques have been developed for these models and we continue this line of research in the current work. We address the problem of compiling any circuit into a circuit secure against OCL attacks. In order to leverage the OCL assumption, the resulting circuit will be split into components, where at any point in time only a single component is active. Optimally, we would like to output a circuit that has only one component, and no part of the computation needs to be leak-free. However, this task is impossible due to the result of Barak et al. [JACM '12].The current state-of-the-art constructions achieve either two components with additional leak-free hardware, or many components without leak-free hardware. In this work, we show how to achieve the best of both worlds: We construct two-component OCL schemes without relying on leak-free components. Our approach is general and modular -- we develop generic techniques to remove the hardware component from hardware-based constructions, when the functionality provided by the hardware satisfies some properties. Our techniques use universal deniable encryption (recently constructed by Sahai and Water [STOC '14] using indistinguishable obfuscation) and non-committing encryption in a novel way. Then, we observe that the functionalities of the hardware used in previous two-component constructions of Juma and Vahlis [Crypto '10], and Dziembowski and Faust [TCC '12] satisfy the required properties. The techniques developed in this paper have deep connections with adaptively secure and leakage tolerant multi-party computation (MPC). Our constructions immediately yield adaptively secure and leakage tolerant MPC protocols for any no-input randomized functionality in the semi-honest model. The result holds in the CRS model, without pre-processing. Our results also have implications to two-party leakage tolerant computation for arbitrary functionalities, which we obtain by combining our constructions with a recent result of Bitansky, Dachman-Soled, and Lin [Crypto '14].

Recently it was observed that for a particular nonzero input difference to an S-Box, some bits in all the corresponding output differences may remain invariant. These specific invariant bits are called undisturbed bits. Undisturbed bits can also be seen as truncated differentials with probability 1 for an S-Box. The existence of undisturbed bits was found in the S-Box of PRESENT and its inverse. A 13-round improbable differential attack on PRESENT was provided by Tezcan and without using the undisturbed bits in the S-Box an attack of this type can only reach 7 rounds. Although the observation and the cryptanalytic application of undisturbed bits are given, their relation with other properties of an S-Box remain unknown. This paper presents some results on mathematical properties of S-Boxes having undisturbed bits. We show that an S-Box has undisturbed bits if any of its coordinate functions has a nontrivial linear structure. The relation of undisturbed bits with other cryptanalytic tools such as difference distribution table (DDT) and linear approximation table (LAT) are also given. We show that autocorrelation table is proven to be a more useful tool, compared to DDT, to obtain all nonzero input differences that yield undisturbed bits. Autocorrelation table can then be viewed as a counterpart of DDT for truncated differential cryptanalysis. Given an nxm balanced S-Box, we state that the S-Box has undisturbed bits whenever the degree of any of its coordinate function is quadratic.

Keccak is the hash function selected by NIST as the new SHA-3 standard. Keccak is built on Sponge construction and it provides a new MAC function called MAC-Keccak. These new algorithms have raised questions with regards to side-channel leakage and analysis attacks of MAC-Keccak. So far there exists prior work on attacks of software implementations of MAC-Keccak, but there has been no comprehensive side-channel vulnerability assessment of its hardware implementation. In this paper we describe an attack on the $\theta$ step of the first round of MAC-Keccak implemented on an FPGA. We construct several different side-channel leakage models and implement attacks based on them. Our work shows that an unmasked hardware implementation of SHA-3 is vulnerable to power-based side-channel attacks.

We design and implement dynamic symmetric searchable encryption schemes that efficiently and privately search server-held encrypted databases with tens of billions of record-keyword pairs. Our basic theoretical construction supports single-keyword searches and offers asymptotically optimal server index size, fully parallel searching, and minimal leakage. Our implementation effort brought to the fore several factors ignored by earlier coarse-grained theoretical performance analyses, including low-level space utilization, I/O parallelism and goodput. We accordingly introduce several optimizations to our theoretically optimal construction that model the prototype's characteristics designed to overcome these factors. All of our schemes and optimizations are proven secure and the information leaked to the untrusted server is precisely quantified. We evaluate the performance of our prototype using two very large datasets: a synthesized census database with 100 million records and hundreds of keywords per record and a multi-million webpage collection that includes Wikipedia as a subset. Moreover, we report on an implementation that uses the dynamic SSE schemes developed here as the basis for supporting recent SSE advances, including complex search queries (e.g., Boolean queries) and richer operational settings (e.g., query delegation), in the above terabyte-scale databases.

In this paper we present a new multiplication algorithm for residues modulo the Mersenne prime $2^{521} - 1$. Using this approach, on an Intel Haswell Core i7-4770, constant-time variable-base scalar multiplication on NIST's (and SECG's) curve P-521 requires 1,073,000 cycles, while on the recently proposed Edwards curve E-521 it requires just 943,000 cycles. As a comparison, on the same architecture openSSL's ECDH speed test for curve P-521 requires 1,319,000 cycles. Furthermore, our code was written entirely in C and so is robust across different platforms. The basic observation behind these speedups is that the form of the modulus allows one to multiply residues with as few word-by-word multiplications as is needed for squaring, while incurring very little overhead from extra additions, in contrast to the usual Karatsuba methods.

We initiate the study of good rate homomorphic encryption schemes. Based on previous work on securely evaluating (binary I/O) branching programs, we propose a leveled homomorphic encryption scheme for {\em large-output} polynomial-size branching programs (which we call $\mathbf{L/poly}$) that possesses near optimal-rate. The rate analysis of the new scheme is intricate: the best rate is achieved if a certain parameter $s$ is set equal to the only positive root of a degree-$m$ polynomial, where $m$ is the length of the branching program. We employ the Newton-Puiseux algorithm to find a Puiseux series for this parameter, and based on this, propose a $\Theta (\log m)$-time algorithm to find an integer approximation to $s$. We also describe a rate-optimal 1-out-of-$n$ CPIR based on rate-optimal homomorphic encryption. In concrete terms, when applied to say, a movie database with $n = 2^{16}$ elements of $\ell = 3.8 \cdot 10^{9}$-bits, the client can privately download a movie with a communication rate of almost $0.99$, hence sacrificing only about $1\%$ of bandwidth for privacy. We also analyze the optimality of the rate efficiency of our scheme in a novel model that may be of independent interest. Our $1$-out-of-$n$ CPIR has rate $ 1- 1.72 \sqrt{k / \ell} \cdot \log_{2} n + O_\ell(\ell^{-1})$, while we show that no black-box construction surpasses $1 - \sqrt{k / \ell} (\log n/ \log \log n) + O_\ell(\ell^{-1})$ in terms of rate, where $\ell$ is the length of the database elements and $k$ the security parameter.

This report summarizes our results from security analysis covering all 57 competitions for authenticated encryption: security, applicability, and robustness (CAESAR) first-round candidates and over 210 implementations. We have manually identified security issues with three candidates, two of which are more serious, and these ciphers have been withdrawn from the competition. We have developed a testing framework, BRUTUS, to facilitate automatic detection of simple security lapses and susceptible statistical structures across all ciphers. From this testing, we have security usage notes on four submissions and statistical notes on a further four. We highlight that some of the CAESAR algorithms pose an elevated risk if employed in real-life protocols due to a class of adaptive-chosen-plaintext attacks. Although authenticated encryption with associated data are often defined (and are best used) as discrete primitives that authenticate and transmit only complete messages, in practice, these algorithms are easily implemented in a fashion that outputs observable ciphertext data when the algorithm has not received all of the (attacker-controlled) plaintext. For an implementor, this strategy appears to offer seemingly harmless and compliant storage and latency advantages. If the algorithm uses the same state for secret keying information, encryption, and integrity protection, and the internal mixing permutation is not cryptographically strong, an attacker can exploit the ciphertext–plaintext feedback loop to reveal secret state information or even keying material. We conclude that the main advantages of exhaustive, automated cryptanalysis are that it acts as a very necessary sanity check for implementations and gives the cryptanalyst insights that can be used to focus more specific attack methods on given candidates.

Proxy re-encryption (PRE) schemes are cryptosystems which allow a proxy who has a re-encryption key to convert a ciphertext originally encrypted for one party into a ciphertext which can be decrypted by another party. In IWSEC 2011, Hayashi et al. proposed the new security notion for PRE called ``unforgeability of re-encryption keys against collusion attacks,'' UFReKey-CA for short. They proposed the PRE schemes and claimed that their schemes meet UFReKey-CA. However, Isshiki et al. pointed out that the schemes do not meet UFReKey-CA in IWSEC 2013. It is an open problem of constructing the scheme which meets UFReKey-CA. In this paper, we propose new PRE schemes which meet confidentiality (RCCA security) assuming that the q-wDBDHI problem is hard and meet UFReKey-CA assuming that the 2-DHI problem is hard.

In this paper we study the question of key management and practical operational security in bitcoin digital currency storage systems. We study the security two most used bitcoin HD Wallet key management solutions (e.g. in BIP032 and in earlier systems). These systems have extensive audit capabilities but this property comes at a very high price. They are excessively fragile. One small security incident in a remote corner of the system and everything collapses, all private keys can be recovered and ALL bitcoins within the remit of the system can be stolen. Privilege escalation attacks on HD Wallet solutions are not new. In this paper we take it much further. We propose new more advanced combination attacks in which the security of keys hold in cold storage can be compromised without executing any software exploit on the cold system, but through security incidents at operation such as bad random number or related random events. In our new attacks all bitcoins over whole large security domains can be stolen by people who have the auditor keys which are typically stored in hot systems connected to the Internet and can be stolen easily. Our combination attacks allow to recover private keys which none of the earlier attacks in isolation could hope to recover. Classical bad random attacks typically concern only very few bitcoin accounts, and only some very lucky holders of bitcoins can actually steal other people's bitcoins. In this paper we go beyond identical random attacks and show several attacks which also work with related random events, which events are more probable and yet less likely to be detected before it is too late. We also present several attacks which work across distinct security domains which share no common setup, code or keys. Yet in certain circumstances all the bitcoins in each domain can be stolen. All our attacks are practical and realistic given the numerous relevant events have already happened in the bitcoin blockchain hundreds of times, some as recently as September 2014. It is not clear if this problem can be repaired, i.e. if there exists a key management solution with similar audit capabilities as BIP032 which would be immune against this sort of advanced combination attacks.

Slide attacks use pairs of encryption operations which are slid against each other. Slide with a twist attacks are more sophisticated variants of slide attacks which slide an encryption operation against a decryption operation. Designed by Biryukov and Wagner in 2000, these attacks were used against several cryptosystems, including DESX, the Even-Mansour construction, and Feistel structures with four-round self-similarity. They were further extended in 2012 to the mirror slidex framework, which was used to attack the 20-round GOST block cipher and several additional variants of the Even-Mansour construction. In this paper, we revisit all the previously published applications of these techniques and show that in almost all cases, the same or better results can be achieved by a simpler attack which is based on the seemingly unrelated idea of exploiting internal fixed points. The observation that such fixed points can be useful in cryptanalysis of block ciphers is known for decades and is the basis of the reflection attack presented by Kara in 2007. However, all the examples to which reflection attacks were applied were based on particular constructions such as Feistel structures or GOST key schedules in which it was easy to explicitly list and count the fixed points. In this paper, we generalize Kara’s reflection attack by using the combinatorial result that random involutions on 2^n values are expected to have a surprisingly large number of O(2^n/2) fixed points (whereas random permutations are expected to have only O(1) fixed points). This makes it possible to reduce the complexity of the best known attack on additional cryptographic schemes in which it is difficult to explicitly characterize and count the internal fixed points.

The increasing ubiquity of the cloud computing paradigm has renewed focus on the classical problem of allowing weak clients to check the results of computation delegated to powerful servers. Recent advances in proof-based verifiable computation have led to several near-practical protocols. Protocols based on interactive proofs (IPs) work with highly restrictive models of computation and are thus efficient only for a limited class of computations. In contrast, protocols based on argument systems apply to a much larger class of computations, but efficiency requires amortization of very expensive setup costs. This paper initiates the study of the practical efficiency of multiprover interactive proofs (MIPs). We present a new MIP for delegating computation that extends insights from a powerful IP protocol (Goldwasser et al., STOC, 2008). Without reductions or amplification, our protocol uses only two provers (departing from prior work on MIPs), and achieves both the efficiency of interactive proof-based protocols and the generality of argument system-based protocols. Also, this result, together with recently developed machinery, creates a potential avenue toward concretely efficient arguments without setup costs. We describe Clover, a built system for verifiable computation, based on our protocol. Although Clover does not implement the full theory (it has setup costs), it applies to problems that existing IPs cannot efficiently handle, and achieves performance comparable to, or better than, the best argument systems.

We present the first two-round, two-party general function evaluation protocol that is secure against honest-but-curious adaptive corruption of both parties. In addition, the protocol is incoercible for one of the parties, and fully leakage tolerant. It requires a global (non-programmable) reference string and is based on one way functions and general-purpose indistinguishability obfuscation with sub-exponential security, as well as augmented non-committing encryption. A Byzantine version of the protocol, obtained by applying the Canetti et al. [STOC 02] compiler, achieves UC security with comparable efficiency parameters, but is no longer incoercible.

Adaptively secure Multi-Party Computation (MPC) first studied by Canetti, Feige, Goldreich, and Naor in 1996, is a fundamental notion in cryptography. Adaptive security is particularly hard to achieve in settings where arbitrary number of parties can be corrupted and honest parties are not trusted to properly erase their internal state. We did not know how to realize constant round protocols for this task even if we were to restrict ourselves to semi-honest adversaries and to the simpler two-party setting. Specifically the round complexity of known protocols grows with the depth of the circuit the parties are trying to compute. In this work, using indistinguishability obfuscation, we construct the first UC two-round Multi-Party computation protocol secure against any active, adaptive adversary corrupting an arbitrary number of parties.

In this paper we revisit the modular inversion hidden number problem (MIHNP) and the inversive congruential generator (ICG) and consider how to attack them more efficiently. We consider systems of modular polynomial equations of the form a_{ij}+b_{ij}x_i+c_{ij}x_j+x_ix_j=0 (mod p) and show the relation between solving such equations and attacking MIHNP and ICG. We present three heuristic strategies using Coppersmith's lattice-based root-finding technique for solving the above modular equations. In the first strategy, we use the polynomial number of samples and get the same asymptotic bound on attacking ICG proposed in PKC 2012, which is the best result so far. However, exponential number of samples is required in the work of PKC 2012. In the second strategy, a part of polynomials chosen for the involved lattice are linear combinations of some polynomials and this enables us to achieve a larger upper bound for the desired root. Corresponding to the analysis of MIHNP we give an explicit lattice construction of the second attack method proposed by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001. We provide better bound than that in the work of PKC 2012 for attacking ICG. Moreover, we propose the third strategy in order to give a further improvement in the involved lattice construction in the sense of requiring fewer samples.

A non-malleable code protects messages against a class of tampering functions. Informally, a code is non-malleable if the effect of applying any tampering function on an encoded message is to either retain the message or to replace it with an unrelated message. Two main challenges in this area -- apart from establishing the feasibility against different families of tampering -- are to obtain explicit constructions and to obtain high-rates for such constructions. In this work, we present a compiler to transform low-rate (in fact, zero rate) non-malleable codes against certain class of tampering into an optimal-rate -- i.e., rate 1 -- non-malleable codes against the same class. If the original code is explicit, so is the new one. When applied to the family of bit-wise tampering functions, this subsumes (and greatly simplifies) a recent result of Cheraghchi and Guruswami (TCC 2014). Further, our compiler can be applied to non-malleable codes against the class of bit-wise tampering and bit-level permutations. Combined with the rate-0 construction in a companion work, this yields the first explicit rate-1 non-malleable code for this family of tampering functions. Our compiler uses a new technique for boot-strapping non-malleability by introducing errors, that may be of independent interest.

A non-malleable code protects messages against various classes of tampering. Informally, a code is non-malleable if the message contained in a tampered codeword is either the original message, or a completely unrelated one. Although existence of such codes for various rich classes of tampering functions is known, \emph{explicit} constructions exist only for ``compartmentalized'' tampering functions: \ie the codeword is partitioned into {\em a priori fixed} blocks and each block can {\em only be tampered independently}. The prominent examples of this model are the family of bit-wise independent tampering functions and the split-state model. In this paper, for the first time we construct explicit non-malleable codes against a natural class of non-compartmentalized tampering functions. We allow the tampering functions to {\em permute the bits} of the codeword and (optionally) perturb them by flipping or setting them to 0 or 1. We construct an explicit, efficient non-malleable code for arbitrarily long messages in this model (unconditionally). We give an application of our construction to non-malleable commitments, as one of the first direct applications of non-malleable codes to computational cryptography. We show that non-malleable {\em string} commitments can be ``entirely based on'' non-malleable {\em bit} commitments. More precisely, we show that simply encoding a string using our code, and then committing to each bit of the encoding using a {\em CCA-secure bit commitment} scheme results in a non-malleable string commitment scheme. This reduction is unconditional, does not require any extra properties from the bit-commitment such as ``tag-based'' non-malleability, and works even with physical implementations (which may not imply standard one-way functions). Further, even given a partially malleable bit commitment scheme which allows toggling the committed bit (instantiated, for illustration, using a variant of the Naor commitment scheme under a non-standard assumption on the PRG involved), this transformation gives a fully non-malleable string commitment scheme. This application relies on the non-malleable code being explicit.

A constrained pseudorandom function $F: K \times X \to Y$ for a family $T$ of subsets of $X$ is a function where for any key $k \in K$ and set $S \in T$ one can efficiently compute a constrained key $k_S$ which allows to evaluate $F(k,.)$ on all inputs $x\in S$, while even given this key, the outputs on all inputs $x \notin S$ look random. At Asiacrypt'13 Boneh and Waters gave a construction which supports the most general set family so far. Its keys $k_C$ are defined for sets decided by boolean circuits $C$ and enable evaluation of the PRF on any $x \in X$ where $C(x)=1$. In their construction the PRF input length and the size of the circuits $C$ for which constrained keys can be computed must be fixed beforehand during key generation. We construct a constrained PRF that has an unbounded input length and whose constrained keys can be defined for any set recognized by a Turing machine. The only a priori bound we make is on the description size of the machines. We prove our construction secure assuming public-coin differing-input obfuscation. As applications of our constrained PRF we build a broadcast encryption scheme where the number of potential receivers need not be fixed at setup (in particular, the length of the keys is independent of the number of parties) and the first identity-based non-interactive key exchange protocol with no bound on the number of parties that can agree on a shared key.

Given two integers $N_1 = p_1q_1$ and $N_2 = p_2q_2$ with $\alpha$-bit primes $q_1,q_2$, suppose that the $t$ least significant bits of $p_1$ and $p_2$ are equal. May and Ritzenhofen (PKC 2009) developed a factoring algorithm for $N_1,N_2$ when $t \geq 2\alpha + 3$; Kurosawa and Ueda (IWSEC 2013) improved the bound to $t \geq 2\alpha + 1$. In this paper, we propose a polynomial-time algorithm in a parameter $\kappa$, with an improved bound $t = 2\alpha - O(\log \kappa)$; it is the first non-constant improvement of the bound. Both the construction and the proof of our algorithm are very simple; the worst-case complexity of our algorithm is evaluated by an easy argument, without any heuristic assumptions. We also give some computer experimental results showing the efficiency of our algorithm for concrete parameters, and discuss potential applications of our result to security evaluations of existing factoring-based primitives.

Homomorphic encryption (HE) systems enable computations on encrypted data, without decrypting and without knowledge of the secret key. In this work, we describe an optimized Ring Learning With Errors (RLWE) based implementation of a variant of the HE system recently proposed by Gentry, Sahai and Waters (GSW). Although this system was widely believed to be less efficient than its contemporaries, we demonstrate quite the opposite behavior for a large class of applications. We first highlight and carefully exploit the algebraic features of the system to achieve significant speedup over the state-of-the-art HE implementation, namely the IBM homomorphic encryption library (HElib). We introduce several optimizations on top of our HE implementation, and use the resulting scheme to construct a homomorphic Bayesian spam filter, secure multiple keyword search, and a homomorphic evaluator for binary decision trees. Our results show a factor of 10x improvement in performance (under the same security settings and CPU platforms) compared to IBM HElib for these applications. Our system is built to be easily portable to GPUs (unlike IBM HElib) which results in an additional speedup of up to a factor of 103.5x to offer an overall speedup of 1035x.

Barak, Shaltiel Tromer showed how to construct a True Random Number Generator (TRNG) which is secure against an adversary who has some limited control over the environment. In this paper we improve the security analysis of this TRNG. Essentially, we significantly reduce the entropy loss and running time needed to obtain a required level of security and robustness. Our approach is based on replacing the combination of union bounds and tail inequalities for $\ell$-wise independent random variables in the original proof, by a more refined of the deviation of the probability that a randomly chosen item is hashed into a particular location.

HILL Entropy and Metric Entropy are generalizations of the information-theoretic notion of min-entropy to the realistic setting where adversaries are computationally bounded. The notion of HILL Entropy appeared in the breakthrough construction of a PRG from any one-way function (Håstad et al.), and has become the most important and most widely used variant of computational entropy. In turn, Metric Entropy defined as a relaxation of HILL Entropy, has been proven to be much easier to handle, in particular in the context of computational generalizations of the Green-Tao-Ziegler Dense Model Theorem which find applications in leakage-resilient cryptography, memory delegation or deterministic encryption. Fortunately, Metric Entropy can be converted, with some loss in quality, to HILL Entropy as shown by Barak, Shaltiel and Wigderson. In this paper we improve their result, reducing the loss in quality of entropy. Our bound is tight and, interestingly, independent of size of the probability space. As an interesting example of application we derive the computational dense model theorem with best possible parameters. Our approach is based on the theory of convex approximation in $L^p$-spaces.

Leakage-resilient cryptography aims to extend the rigorous guarantees achieved through the provable security paradigm to physical implementations. The constructions designed on basis of this new approach inevitably suffer from an Achilles heel: a bounded leakage assumption is needed. Currently, a huge gap exists between the theory of such designs and their implementation to confirm the leakage resilience in practice. The present work tries to narrow this gap for the leakage-resilient bilinear ElGamal key encapsulation mechanism (BEG-KEM) proposed by Kiltz and Pietrzak in 2010. Our first contribution is a variant of the bounded leakage and the only-computation-leaks model that is closer to practice. We weaken the restriction on the image size of the leakage functions in these models and only insist that the inputs to the leakage functions have sufficient min-entropy left, in spite of the leakage, with no limitation on the quantity of this leakage. We provide a novel security reduction for BEG-KEM in this relaxed leakage model using the generic bilinear group axiom. Secondly, we show that a naive implementation of the exponentiation in BEG-KEM makes it impossible to meet the leakage bound. Instead of trying to find an exponentiation algorithm that meets the leakage axiom (which is a non-trivial problem in practice), we propose an advanced scheme, BEG-KEM+, that avoids exponentiation by a secret value, but rather uses an encoding into the base group due to Fouque and Tibouchi. Thirdly, we present a software implementation of BEG-KEM+ based on the Miracl library and provide detailed experimental results. We also assess its (theoretical) resistance against power analysis attacks from a practical perspective, taking into account the state-of-the-art in side-channel cryptanalysis.

Deciding "greater-than" relations among data items just given their encryptions is at the heart of search algorithms on encrypted data, most notably, non-interactive binary search on encrypted data. Order-preserving encryption provides one solution, but provably provides only limited security guarantees. Two-input functional encryption is another approach, but requires the full power of obfuscation machinery and is currently not implementable. We construct the first implementable encryption system supporting greater-than comparisons on encrypted data that provides the "best-possible" semantic security. In our scheme there is a public algorithm that given two ciphertexts as input, reveals the order of the corresponding plaintexts and nothing else. Our constructions are inspired by obfuscation techniques, but do not use obfuscation. For example, to compare two 16-bit encrypted values (e.g., salaries or age) we only need a 9-way multilinear map. More generally, comparing $k$-bit values requires only a $(k/2+1)$-way multilinear map. The required degree of multilinearity can be further reduced, but at the cost of increasing ciphertext size. Beyond comparisons, our results give an implementable secret-key multi-input functional encryption scheme for functionalities that can be expressed as (generalized) branching programs of polynomial length and width. Comparisons are a special case of this class, where for $k$-bit inputs the branching program is of length $k+1$ and width $4$.

In this work, we first formalize the notion of dynamic group signatures with distributed traceability, where the capability to trace signatures is distributed among $n$ managers without requiring any interaction. This ensures that only the participation of all tracing managers permits tracing a signature, which reduces the trust placed in a single tracing manager. The threshold variant follows easily from our definitions and constructions. Our model offers strong security requirements. Our second contribution is a generic construction for the notion which has a concurrent join protocol, meets strong security requirements, and offers efficient traceability, i.e.\ without requiring tracing managers to produce expensive zero-knowledge proofs for tracing correctness. To dispense with the expensive zero-knowledge proofs required in the tracing, we deploy a distributed tag-based encryption with public verifiability. Finally, we provide some concrete instantiations, which, to the best of our knowledge, are the first efficient provably secure realizations in the standard model simultaneously offering all the aforementioned properties. To realize our constructions efficiently, we construct an efficient distributed (and threshold) tag-based encryption scheme that works in the efficient Type-III asymmetric bilinear groups. Our distributed tag-based encryption scheme yields short ciphertexts (only 1280 bits at 128-bit security), and is secure under an existing variant of the standard decisional linear assumption. Our tag-based encryption scheme is of independent interest and is useful for many applications beyond the scope of this paper. As a special case of our distributed tag-based encryption scheme, we get an efficient tag-based encryption scheme in Type-III asymmetric bilinear groups that is secure in the standard model.

Currently, the Internet Research Task Force (IRTF) discusses requirements for new elliptic curves to be standardized in TLS and other internet protocols. This position paper discusses the view of the members of the ECC Brainpool on these requirements, in particular with respect to hardware implementations.

We propose the TWEAKEY framework with goal to unify the design of tweakable block ciphers and of block ciphers resistant to related-key attacks. Our framework is simple, extends the key-alternating construction, and allows to build a primitive with arbitrary tweak and key sizes, given the public round permutation (for instance, the AES round). Increasing the sizes renders the security analysis very difficult and thus we identify a subclass of TWEAKEY, that we name STK, which solves the size issue by the use of finite field multiplications on low hamming weight constants. We give very efficient instances of STK, in particular, a 128-bit tweak/key/state block cipher Deoxys-BC that is the first AES-based ad-hoc tweakable block cipher. At the same time, Deoxys-BC could be seen as a secure alternative to AES-256, which is known to be insecure in the related-key model. As another member of the TWEAKEY framework, we describe Kiasu-BC, which is a very simple and even more efficient tweakable variation of AES-128 when the tweak size is limited to 64 bits. In addition to being efficient, our proposals, compared to the previous schemes that use AES as a black box, offer security beyond the birthday bound. Deoxys-BC and Kiasu-BC represent interesting pluggable primitives for authenticated encryption schemes, for instance, OCB instantiated with Kiasu-BC runs at about 0.75 c/B on Intel Haswell. Our work can also be seen as advances on the topic of secure key schedule design for AES-like ciphers, describing several proposals in this direction.

Adaptively secure Multi-Party Computation (MPC) is an essential and fundamental notion in cryptography. In this work, we construct Universally Composable (UC) MPC protocols that are adaptively secure against all-but-one corruptions based on LWE. Our protocols have a constant number of rounds and communication complexity dependant only on the length of the inputs and outputs (it is independent of the circuit size). Such protocols were only known assuming an honest majority. Protocols in the dishonest majority setting, such as the work of Ishai et al. (CRYPTO 2008), require communication complexity proportional to the circuit size. In addition, constant-round adaptively secure protocols assuming dishonest majority are known to be impossible in the stand-alone setting with black-box proofs of security in the plain model. Here, we solve the problem in the UC setting using a set-up assumption which was shown necessary in order to achieve dishonest majority. The problem of constructing adaptively secure constant-round MPC protocols against arbitrary corruptions is considered a notorious hard problem. A recent line of works based on indistinguishability obfuscation construct such protocols with near-optimal number of rounds against arbitrary corruptions. However, based on standard assumptions, adaptively secure protocols secure against even just all-but-one corruptions with near-optimal number of rounds are not known. However, in this work we provide a three-round solution based only on LWE and NIZK secure against all-but-one corruptions. In addition, Asharov et al. (EUROCRYPT 2012) and more recently Mukherjee and Wichs (ePrint 2015) presented constant-round protocols based on LWE which are secure only in the presence of static adversaries. Assuming NIZK and LWE their static protocols run in two rounds where the latter one is only based on a common random string. Assuming adaptively secure UC NIZK, proposed by Groth et al. (ACM 2012), and LWE as mentioned above our adaptive protocols run in three rounds. Our protocols are constructed based on a special type of cryptosystem we call equivocal FHE from LWE. We also build adaptively secure UC commitments and UC zero-knowledge proofs (of knowledge) from LWE. Moreover, in the decryption phase using an AMD code mechanism we avoid the use of ZK and achieve communication complexity that does not scale with the decryption circuit.

We propose the first UC secure commitment scheme with (amortized) computational complexity linear in the size of the string committed to. After a preprocessing phase based on oblivious transfer, that only needs to be done once and for all, our scheme only requires a pseudorandom generator and a linear code with efficient encoding. We also construct an additively homomorphic version of our basic scheme using VSS. Furthermore we evaluate the concrete efficiency of our schemes and show that the amortized computational overhead is significantly lower than in the previous best constructions. In fact, our basic scheme has amortised concrete efficiency comparable with previous protocols in the Random Oracle Model even though it is constructed in the plain model.

An efficient quantum modular exponentiation method is indispensible for Shor's factoring algorithm. But we find that all descriptions presented by Shor, Nielsen and Chuang, Markov and Saeedi, et al., are flawed. We also remark that some experimental demonstrations of Shor's algorithm are misleading, because they violate the necessary condition that the selected number $q=2^s$, where $s$ is the number of qubits used in the first register, must satisfy $n^2 \leq q < 2n^2$, where $n$ is the large number to be factored.

We consider interactive proof systems over adversarial communication channels. We show that the seminal result that $\ip = \pspace$ still holds when the communication channel is malicious, allowing even a constant fraction of the communication to be arbitrarily corrupted.

We initiate the study of a novel class of group-theoretic intractability problems. Inspired by the theory of learning in presence of errors [Regev, STOC'05] we ask if noise in the exponent amplifies intractability. We put forth the notion of Learning with Errors in the Exponent (LWEE) and rather surprisingly show that various attractive properties known to exclusively hold for lattices carry over. Most notably are worst-case hardness and post-quantum resistance. In fact, LWEE's duality is due to the reducibility to two seemingly unrelated assumptions: learning with errors and the representation problem [Brands, Crypto'93] in finite groups. For suitable parameter choices LWEE superposes properties from each individual intractability problem. The argument holds in the classical and quantum model of computation. We give the very first construction of a semantically secure public-key encryption system in the standard model. The heart of our construction is an ``error recovery'' technique inspired by [Joye-Libert, Eurocrypt'13] to handle critical propagations of noise terms in the exponent.

We propose a new algorithm to solve the Implicit Factorization Problem, which was introduced by May and Ritzenhofen at PKC'09. In 2011, Sarkar and Maitra (IEEE TIT 57(6): 4002-4013, 2011) improved May and Ritzenhofen's results by making use of the technique for solving multivariate approximate common divisors problem. In this paper, based on the observation that the desired root of the equations that derived by Sarkar and Maitra contains large prime factors, which are already determined by some known integers, we develop new techniques to acquire better bounds. We show that our attack is the best among all known attacks, and give experimental results to verify the correctness. Additionally, for the first time, we can experimentally handle the implicit factorization for the case of balanced RSA moduli.

Demands for lawful access to encrypted data are a long standing obstacle to integrating cryptographic protections into communication systems. A common approach is to allow a trusted third party (TTP) to gain access to private data. However, there is no way to verify that this trust is well place as the TTP may open all messages indiscriminately. Moreover, existing approaches do not scale well when, in addition to the content of the conversation, one wishes to hide ones identity. Given the importance of metadata this is a major problem. We propose a new signature scheme as an accountable replacement for group signatures, accountable forward and backward tracing signatures.

Noisy channels are a powerful resource for cryptography as they can be used to obtain information-theoretically secure key agreement, commitment and oblivious transfer protocols, among others. Oblivious transfer (OT) is a fundamental primitive since it is complete for secure multi-party computation, and the OT capacity characterizes how efficiently a channel can be used for obtaining string oblivious transfer. Ahlswede and Csiszár (\emph{ISIT'07}) presented upper and lower bounds on the OT capacity of generalized erasure channels (GEC) against passive adversaries. In the case of GEC with erasure probability at least 1/2, the upper and lower bounds match and therefore the OT capacity was determined. It was later proved by Pinto et al. (\emph{IEEE Trans. Inf. Theory 57(8)}) that in this case there is also a protocol against malicious adversaries achieving the same lower bound, and hence the OT capacity is identical for passive and malicious adversaries. In the case of GEC with erasure probability smaller than 1/2, the known lower bound against passive adversaries that was established by Ahlswede and Csiszár does not match their upper bound and it was unknown whether this OT rate could be achieved against malicious adversaries as well. In this work we show that there is a protocol against malicious adversaries achieving the same OT rate that was obtained against passive adversaries. In order to obtain our results we introduce a novel use of interactive hashing that is suitable for dealing with the case of low erasure probability ($p^* <1/2$).

We propose a definition of ballot secrecy in the computational model of cryptography. The definition builds upon and strengthens earlier definitions by Bernhard et al. (ASIACRYPT'12, ESORICS'11 & ESORICS'13). The new definition is intended to ensure that ballot secrecy is preserved in the presence of malicious bulletin boards, whereas earlier definitions only consider trusted bulletin boards. It follows that the new definition prevents more attacks in comparison with earlier definitions.

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs~\cite{DPW10}, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely ``unrelated value''. Although such codes do not exist if the family of ``tampering functions'' \cF allowed to modify the original codeword is completely unrestricted, they are known to exist for many broad tampering families \cF. The family which received the most attention is the family of tampering functions in the so called (2-part) {\em split-state} model: here the message x is encoded into two shares L and R, and the attacker is allowed to {\em arbitrarily} tamper with each L and R individually. Despite this attention, the following problem remained open: Build efficient, information-theoretically secure non-malleable codes in the split-state model with constant encoding rate}: |L|=|R|=O(|x|). In this work, we make progress towards obtaining this result. Specifically, we (a) develop a generalization of non-malleable codes, called {\em non-malleable reductions}; (b) show simple composition theorem for non-malleable reductions; (c) build a variety of such reductions connecting various (independently interesting) tampering families $\cF$ to each other; (d) construct several new non-malleable codes in the split-state model by applying the composition theorem to a series of easy to understand reductions. In particular, we design an unconditionally secure non-malleable code with 5 parts where the size of each part is quadratic in the length of the message, and state a conjecture under which we obtain a constant rate 2 part non-malleable code in the split-state model. Of independent interest, we show several ``independence amplification'' reductions, showing how to reduce split-state tampering of very few parts to an easier question of split-state tampering with a much larger number of parts. \paragraph{Note.} Some time after publishing the paper (it was presented at STOC 2015), Xin Li pointed out that one of the proofs in the paper had a mistake. In particular, we had incorrectly claimed a proof of Conjecture 26. We would like to emphasize that we still believe that Conjecture 26 is true but we do not have a proof.

Functional encryption, as introduced by Boneh, Sahai, and Waters (TCC'11), generalizes public-key encryption systems to include functional decryption capabilities. Recently, Boyle et al. as well as Bellare and Fuchsbauer (both PKC'14) formalized analogous notions for signature schemes. Here we discuss that both their notions are limited in terms of expressiveness in the sense that they cannot cast known signature schemes supporting operations on data in their frameworks. We therefore propose a notion of what we call, for sake of distinctiveness, operational signature schemes which captures functional signatures, policy-based signatures, sanitizable signatures, P-homomorphic signatures, ring signatures, aggregate signatures etc., and also their message authentication code counterparts. We discuss possible instantiations for operational signatures. We give some positive result about achieving our general notion of operational signatures presenting a compact construction that relies on a new combination of indistinguishability obfuscation and random oracles. We then indicate that it is unlikely to be able to instantiate operational signature schemes in general using one-wayness and, under some circumstances, even using specific ``non-interactive'' assumptions like RSA.

In an Attribute-Based Encryption (ABE) scheme the ciphertext encrypting a message $\mu$, is associated with a public attribute vector $\vecx$ and a secret key $\sk_P$ is associated with a predicate $P$. The decryption returns $\mu$ if and only if $P(\vecx) = 1$. ABE provides efficient and simple mechanism for data sharing supporting fine-grained access control. Moreover, it is used as a critical component in constructions of succinct functional encryption, reusable garbled circuits, token-based obfuscation and more. In this work, we describe a new efficient ABE scheme for a family of branching programs with short secret keys and from a mild assumption. In particular, in our construction the size of the secret key for a branching program $P$ is $|P| + \poly(\secp)$, where $\secp$ is the security parameter. Our construction is secure assuming the standard Learning With Errors (LWE) problem with approximation factors $n^{\omega(1)}$. Previous constructions relied on $n^{O(\log n)}$ approximation factors of LWE (resulting in less efficient parameters instantiation) or had large secret keys of size $|P| \times \poly(\secp)$. We rely on techniques developed by Boneh et al. (EUROCRYPT'14) and Brakerski et al. (ITCS'14) in the context of ABE for circuits and fully-homomorphic encryption.

This paper resolves an open problem raised by Blocki {\it et al.} (FOCS 2012), i.e., whether other variants of the Johnson-Lindenstrauss transform preserves differential privacy or not? We prove that a general class of random projection matrices that satisfies the Johnson-Lindenstrauss lemma also preserves differential privacy. This class of random projection matrices requires only $n$ Gaussian samples and $n$ Bernoulli trials and allows matrix-vector multiplication in $O(n \log n)$ time. In this respect, this work unconditionally improves the run time of Blocki {\it et al.} (FOCS 2012) without using the graph sparsification trick of Upadhyay (ASIACRYPT 2013). For the metric of measuring randomness, we stick to the norm used by earlier researchers who studied variants of the Johnson-Lindenstrauss transform and its applications, i.e., count the number of random samples made. In concise, we improve the sampling complexity by quadratic factor, and the run time of cut queries by an $O(n^{o(1)})$ factor and that of covariance queries by an $O(n^{0.38})$ factor. Our proof for both the privacy and utility guarantee uses several new ideas. In order to improve the dimension bound, we use some known results from the domain of statistical model selection. This makes our proof short and elegant, relying just on one basic concentration inequality. For the privacy proof, even though our mechanism closely resembles that of Blocki {\it et al.} (FOCS 2012) and Upadhyay (ASIACRYPT 2013), we cannot use their proof idea. This is because the projection matrices we are interested in introduces non-trivial correlations between any two rows of the published matrix, and, therefore, we cannot invoke the composition theorem of Dwork, Rothblum and Vadhan (STOC 2009). We argue that the published matrix is not $r$-multivariate distribution; rather one matrix-variate distribution. We compute the distribution of the published matrix and then prove it preserves differential privacy.

Multi-precision squaring is a crucial operation for implementation of Elliptic Curve Cryptography. Particularly, when it comes to embedded processors, the operation should be designed carefully to execute expensive ECC operation on resource constrained devices. In order to bridge the gap between high overheads and limited computation capabilities, we present optimized Karatsuba squaring method for embedded processors. Traditional squaring computation can be divided into two sub-squaring and one sub-multiplication parts. Firstly we compute the multiplication part with the fastest Karatsuba multiplication and then remaining two squaring parts are conducted with the fastest sliding block doubling squaring. Proposed method sets the new speed records for multi-precision squaring, improving the execution time by up to 8.49% comparing to the best known works.

The main bottleneck affecting the efficiency of all known fully homomorphic encryption (FHE) schemes is Gentry’s bootstrapping procedure, which is required to refresh noisy ciphertexts and keep computing on encrypted data. Bootstrapping in the latest implementation of FHE, the HElib library of Halevi and Shoup (Crypto 2014), requires about six minutes per batch. We present a new method to homomorphically compute simple bit operations, and refresh (bootstrap) the resulting output, which runs on a personal computer in just about half a second. We present a detailed technical analysis of the scheme (based on the worst-case hardness of standard lattice problems) and report on the performance of our prototype implementation.

Decomposing a divisor over a suitable factor basis in the Jacobian of a hyperelliptic curve is a crucial step in an index calculus algorithm for the discrete log problem in the Jacobian. For small genus curves, in the year 2000, Gaudry had proposed a suitable factor basis and a decomposition method. In this work, we provide a new method for decomposition over the same factor basis. The advantage of the new method is that it admits a sieving technique which removes smoothness checking of polynomials required in Gaudry's method. Also, the total number of additions in the Jacobian required by the new method is less than that required by Gaudry's method. The new method itself is quite simple and we present some example decompositions and timing results of our implementation of the method using Magma.

Cayley hash functions are based on a simple idea of using a pair of (semi)group elements, $A$ and $B$, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of elements in the (semi)group. In this paper, we focus on hashing with $2 \times 2$ matrices over $F_p$. Since there are many known pairs of $2 \times 2$ matrices over $Z$ that generate a free monoid, this yields numerous pairs of matrices over $F_p$, for a sufficiently large prime $p$, that are candidates for collision-resistant hashing. However, this trick can ``backfire", and lifting matrix entries to $Z$ may facilitate finding a collision. This ``lifting attack" was successfully used by Tillich and Zémor in the special case where two matrices $A$ and $B$ generate (as a monoid) the whole monoid $SL_2(\Z_+)$. However, in this paper we show that the situation with other, ``similar", pairs of matrices from $SL_2(Z)$ is different, and the ``lifting attack" can (in some cases) produce collisions in the {\it group} generated by $A$ and $B$, but not in the positive {\it monoid}. Therefore, we argue that for these pairs of matrices, there are no known attacks at this time that would affect security of the corresponding hash functions. We also give explicit lower bounds on the length of collisions for hash functions corresponding to some particular pairs of matrices from $SL_2(F_p)$.

We show a technique to transform a linearly-homomorphic encryption into a homomorphic encryption scheme capable of evaluating degree-2 computations on ciphertexts. Our transformation is surprisingly simple and requires only one very mild property on the underlying linearly-homomorphic scheme: the message space must be a public ring in which it is possible to sample elements uniformly at random. This essentially allows us to instantiate our transformation with virtually all existing number-theoretic linearly-homomorphic schemes, such as Goldwasser-Micali, Paillier, or ElGamal. Our resulting schemes achieve circuit privacy and are compact when considering a subclass of degree-2 polynomials in which the number of additions of degree-2 terms is bounded by a constant. As an additional contribution we extend our technique to build a protocol for outsourcing computation on encrypted data using two (non-communicating) servers. Somewhat interestingly, in this case we can boost a linearly-homomorphic scheme to support the evaluation of any degree-2 polynomial while achieving full compactness.

Private query processing on encrypted databases allows users to obtain data from encrypted databases in such a way that the user's sensitive data will be protected from exposure. Given an encrypted database, the users typically submit queries similar to the following examples: - How many employees in an organization make over 100,000? - What is the average age of factory workers suffering from leukemia? Answering the above questions requires one to \textbf{search} and then \textbf{compute} over the encrypted databases \emph{in sequence}. In the case of privately processing queries with only one of these operations, many efficient solutions have been developed using a special-purpose encryption scheme (e.g., searchable encryption). In this paper, we are interested in efficiently processing queries that need to perform both operations on \emph{fully} encrypted databases. One immediate solution is to use several special-purpose encryption schemes at the same time, but this approach is associated with a high computational cost for maintaining multiple encryption contexts. The other solution is to use a privacy homomorphism (or fully homomorphic encryption) scheme. However, no secure solutions have been developed that meet the efficiency requirements. In this work, we construct a unified framework so as to efficiently and privately process queries with ``search'' and ``compute'' operations. To this end, the first part of our work involves devising some underlying circuits as primitives for queries on encrypted data. Second, we apply two optimization techniques to improve the efficiency of the circuit primitives. One technique is to exploit SIMD techniques to accelerate their basic operations. In contrast to general SIMD approaches, our SIMD implementation can be applied even when one basic operation is executed. The other technique is to take a large integer ring (\textit{e.g.}, $\Z_{2^{t}}$) as a message space instead of a binary field. Even for an integer of $k$ bits with $k>t$, addition can be performed with degree 1 circuits with lazy carry operations. As a result, search queries including a conjunctive or disjunctive query on encrypted databases of $N$ tuples with $\mu$-bit attributes require $\bigo(N \log \mu)$ homomorphic operations with depth $\bigo(\log \mu)$ circuits. Search-and-compute queries, such as a conjunctive query with aggregate functions in the same conditions, are processed using $\bigo(\mu N)$ homomorphic operations with at most depth $\bigo(\log \mu \log N)$ circuits. Further, we can process search-and-compute queries using only $\bigo(N \log \mu)$ homomorphic operations with depth $\bigo(\log \mu)$ circuits, even in the large domain. Finally, we present various experiments by varying the parameters, such as the query type and the number of tuples.

We investigate the security of the family of MQQ public key cryptosystems using multivariate quadratic quasigroups (MQQ). These cryptosystems show especially good performance properties. In particular, the MQQ-SIG signature scheme is the fastest scheme in the ECRYPT benchmarking of cryptographic systems (eBACS). We show that both the signature scheme MQQ-SIG and the encryption scheme MQQ-ENC, although using different types of MQQs, share a common algebraic structure that introduces a weakness in both schemes. We use this weakness to mount a successful polynomial time key-recovery attack. Our key-recovery attack finds an equivalent key using the idea of so-called good keys that reveals the structure gradually. In the process we need to solve a MinRank problem that, because of the structure, can be solved in polynomial-time assuming some mild algebraic assumptions. We highlight that our theoretical results work in characteristic 2 which is known to be the most difficult case to address in theory for MinRank attacks. Also, we emphasize that our attack works without any restriction on the number of polynomials removed from the public-key, that is, using the minus modifier. This was not the case for previous MinRank like-attacks against MQ schemes. From a practical point of view, we are able to break an MQQ-SIG instance of $80$ bits security in less than 2 days, and one of the more conservative MQQ-ENC instances of 128 bits security in little bit over 9 days. Altogether, our attack shows that it is very hard to design a secure public key scheme based on an easily invertible MQQ structure.

One of the main lines of research in functional encryption (FE) has consisted in studying the security notions for FE and their achievability. This study was initiated by [Boneh et al. -- TCC'11, O'Neill -- ePrint'10] where it was first shown that for FE the indistinguishability-based (IND) security notion is not sufficient in the sense that there are FE schemes that are provably IND-Secure but concretely insecure. For this reason, researchers investigated the achievability of Simulation-based (SIM) security, a stronger notion of security. Unfortunately, the above-mentioned works and others [e.g., Agrawal et al. -- CRYPTO'13] have shown strong impossibility results for SIM-Security. One way to overcome these impossibility results was first suggested in the work of Boneh et al. where it was shown how to construct, in the Random Oracle (RO) model, SIM-Secure FE for restricted functionalities and was asked the generalization to more complex functionalities as a challenging problem in the area. Subsequently, [De Caro et al. -- CRYPTO'13] proposed a candidate construction of SIM-Secure FE for all circuits in the RO model assuming the existence of an IND-Secure FE scheme for circuits with RO gates. This means that the functionality has to depend on the RO, thus it is not fixed in advance as in the standard definitions of FE. Moreover, to our knowledge there are no proposed candidate IND-Secure FE schemes for circuits with RO gates and they seem unlikely to exist. In this paper, we propose the first constructions of SIM-Secure FE schemes in the RO model that overcome the current impossibility results in different settings. We can do that because we resort to the two following models: In the public-key setting we assume a bound on the number of queries but this bound only affects the running-times of our encryption and decryption procedures. We stress that our FE schemes in this model are SIM-Secure and have ciphertexts and tokens of constant-size, whereas in the standard model, the current SIM-Secure FE schemes for general functionalities [De Caro et al., Gorbunov et al. -- CRYPTO'12] have ciphertexts and tokens of size growing as the number of queries. In the symmetric-key setting we assume a timestamp on both ciphertexts and tokens. This is reasonable because, in the symmetric-key setting, there is only one user that encrypts and generates tokens. In this model, we provide FE schemes with short ciphertexts and tokens that are SIM-Secure against adversaries asking an unbounded number of queries. Both results also assume the RO model, but not functionalities with RO gates and rely on extractability obfuscation w.r.t. distributional auxiliary input [Boyle et al. -- TCC'14] (and other standard primitives) secure only in the standard model.

We consider secure two-party computation in the client-server model. In our scenario, two adversaries operate \emph{separately but simultaneously}, each of them corrupting one of the parties and a restricted subset of servers that they interact with. We model security in this setting via the local universal composability framework introduced by Canetti and Vald and show that information-theoretically secure two-party computation is possible if and only if there is always at least one server which remains uncorrupted. Moreover, in our protocols each of the servers only needs to communicate with the two clients, i.e. no messages are exchanged directly between servers. This communication pattern is minimal.

The article proposes an Online/Off-line Ring Signature Scheme in random oracle model.Security of the scheme relies on both Computational Diffie-Hellman and k-CAA problems. The proposed scheme is proven the two most important security goals Existential Unforgeability and Signer Ambiguity. Also it has robustness property where the misbehavior of the signer can be detected. Signing process is performed in two phases online and offline. All heavy computations are performed in Off-line stage. So the overall computational cost is reduced and very less than the traditional signature scheme. The scheme can be applied to Mobile Ad Hoc Networks (MANETs) that undergo node mobility.

A recent trend in cryptography is to construct cryptosystems that are secure against physical attacks. Such attacks are usually divided into two classes: the \emph{leakage} attacks in which the adversary obtains some information about the internal state of the machine, and the \emph{tampering} attacks where the adversary can modify this state. One of the popular tools used to provide tamper-resistance are the \emph{non-malleable codes} introduced by Dziembowski, Pietrzak and Wichs (ICS 2010). These codes can be defined in several variants, but arguably the most natural of them are the information-theoretically secure codes in the k-split-state model (the most desired case being k=2). Such codes were constucted recently by Aggarwal et al.~(STOC 2014). Unfortunately, unlike the earlier, computationally-secure constructions (Liu and Lysyanskaya, CRYPTO 2012) these codes are not known to be resilient to leakage. This is unsatisfactory, since in practice one always aims at providing resilience against both leakage and tampering (especially considering tampering without leakage is problematic, since the leakage attacks are usually much easier to perform than the tampering attacks). In this paper we close this gap by showing a non-malleable code in the $2$-split state model that is secure against leaking almost a $1/12$-th fraction of the bits from the codeword (in the bounded-leakage model). This is achieved via a generic transformation that takes as input any non-malleable code $(\Enc,\Dec)$ in the $2$-split state model, and constructs out of it another non-malleable code $(\Enc',\Dec')$ in the $2$-split state model that is additionally leakage-resilient. The rate of $(\Enc',\Dec')$ is linear in the rate of $(\Enc,\Dec)$. Our construction requires that $\Dec$ is \emph{symmetric}, i.e., for all $x, y$, it is the case that $\Dec(x,y) = \Dec(y,x)$, but this property holds for all currently known information-theoretically secure codes in the $2$-split state model. In particular, we can apply our transformation to the code of Aggarwal et al., obtaining the first leakage-resilient code secure in the split-state model. Our transformation can be applied to other codes (in particular it can also be applied to a recent code of Aggarwal, Dodis, Kazana and Obremski constructed in the work subsequent to this one).

The paper is about the discrete logarithm problem for elliptic curves over characteristic 2 finite fields F_2^n of prime degree n. We consider practical issues about index calculus attacks using summation polynomials in this setting. The contributions of the paper include: a choice of variables for binary Edwards curves (invariant under the action of a relatively large group) to lower the degree of the summation polynomials; a choice of factor base that “breaks symmetry” and increases the probability of finding a relation; an experimental investigation of the use of SAT solvers rather than Gröbner basis methods for solving multivariate polynomial equations over F2. We show that our choice of variables gives a significant improvement to previous work in this case. The symmetry breaking factor base and use of SAT solvers seem to give some benefits in practice, but our experimental results are not conclusive. Our work indicates that Pollard rho is still much faster than index calculus algorithms for the ECDLP (and even for variants such as the oracle-assisted static Diffie-Hellman problem of Granger and Joux-Vitse) over prime extension fields F_2^n of reasonable size.

We introduce a novel concept of dual-system simulation-sound non-interactive zero-knowledge (NIZK) proofs. Dual-system NIZK proof system can be seen as a two-tier proof system. As opposed to the usual notion of zero-knowledge proofs, dual-system defines an intermediate partial-simulation world, where the proof simulator may have access to additional auxiliary information about the potential language member, for example a membership bit, and simulation of proofs is only guaranteed if the membership bit is correct. Further, dual-system NIZK proofs allow a quasi-adaptive setting where the CRS can be generated based on language parameters. This allows for the further possibility that the partial-world CRS simulator may have access to further trapdoors related to the language parameters. We show that for important hard languages like the Diffie-Hellman language, such dual-system proof systems can be given which allow unbounded partial simulation soundness, and which further allow transition between partial simulation world and single-theorem full simulation world even when proofs are sought on non-members. The construction is surprisingly simple, involving only two additional group elements in asymmetric bilinear pairing groups. As a first application we show a first single-round universally-composable password authenticated key-exchange (UC-PAKE) protocol which is secure under dynamic corruption in the erasure model. The single message flow only requires four group elements under the SXDH assumption, which is at least two times shorter than earlier schemes. Adaptive Corruption is proved for a relaxed ideal functionality using non-information oracles. As another application we give a short keyed-homomorphic CCA-secure encryption scheme. The ciphertext in this scheme consist of only six group elements (under the SXDH assumption) and the security reduction is linear-preserving. An earlier scheme of Libert et al based on their efficient unbounded simulation-sound QA-NIZK proofs only provided a quadratic-preserving security reduction, and further had ciphertexts almost twice as long as ours.

We present a lattice-based stateless signature scheme provably secure in the standard model. Our scheme has a \emph{constant} number of matrices in the public key and a single lattice vector (plus a tag) in the signatures. The best previous lattice-based encryption schemes were the scheme of Ducas and Micciancio (CRYPTO 2014), which required a logarithmic number of matrices in the public key and that of Bohl et. al (J. of Cryptology 2014), which required a logarithmic number of lattice vectors in the signature. Our main technique involves using fully homomorphic computation to compute a degree $d$ polynomial over the tags hidden in the matrices in the public key. In the scheme of Ducas and Micciancio, only functions \emph{linear} over the tags in the public key matrices were used, which necessitated having $d$ matrices in the public key. As a matter of independent interest, we extend Wichs' (eprint 2014) recent construction of homomorphic trapdoor functions into a primitive we call puncturable homomorphic trapdoor functions (PHTDFs). This primitive abstracts out most of the properties required in many different lattice-based cryptographic constructions. We then show how to combine a PHTDF along with a function satisfying certain properties (to be evaluated homomorphically) to give an eu-scma signature scheme.

Public key infrastructures (PKIs) enable users to look up and verify one another's public keys based on identities. Current approaches to PKIs are vulnerable because they do not offer sufficiently strong guarantees of \emph{identity retention}; that is, they do not effectively prevent one user from registering a public key under another's already-registered identity. In this paper, we leverage the consistency guarantees provided by cryptocurrencies such as Bitcoin and Namecoin to build a PKI that ensures identity retention. Our system, called Certcoin, has no central authority and thus requires the use of secure distributed dictionary data structures to provide efficient support for key lookup.

As intended by its name, Physically Unclonable Functions (PUFs) are considered as an ultimate solution to deal with insecure stor- age, hardware counterfeiting, and many other security problems. How- ever, many different successful attacks have already revealed vulnera- bilities of certain digital intrinsic PUFs. Although settling-state-based PUFs, such as SRAM PUFs, can be physically cloned by semi-invasive and fully-invasive attacks, successful attacks on timing-based PUFs were so far limited to modeling attacks. Such modeling requires a large sub- set of challenge-response-pairs (CRP) to successfully model the targeted PUF. In order to provide a final security answer, this paper proves that all arbiter-based (i.e. controlled and XOR-enhanced) PUFs can be com- pletely and linearly characterized by means of photonic emission analy- sis. Our experimental setup is capable of measuring every PUF-internal delay with a resolution of 6 picoseconds. Due to this resolution we in- deed require only the theoretical minimum number of linear independent equations (i.e. physical measurements) to directly solve the underlying inhomogeneous linear system. Moreover, we neither require to know the actual PUF challenges nor the corresponding PUF responses for our physical delay extraction. On top of that devastating result, we are also able to further simplify our setup for easier physical measurement han- dling. We present our practical results for a real arbiter PUF implemen- tation on a Complex Programmable Logic Device (CPLD) from Altera manufactured in a 180 nanometer process.

Often S-boxes are the only nonlinear component in a block cipher and as such play an important role in ensuring its resistance to cryptanalysis. Cryptographic properties and constructions of S-boxes have been studied for many years. The most common techniques for constructing S-boxes are: algebraic constructions, pseudo-random generation and a variety of heuristic approaches. Among the latter are the genetic algorithms. In this paper, a genetic algorithm working in a reversed way is proposed. Using the algorithm we can rapidly and repeatedly generate a large number of strong bijective S-boxes of each dimension from $(8 \times 8)$ to $(16 \times 16)$, which have sub-optimal properties close to the ones of S-boxes based on finite field inversion, but have more complex algebraic structure and possess no linear redundancy.

The research on pairing-based cryptography brought forth a wide range of protocols interesting for future embedded applications. One significant obstacle for the widespread deployment of pairing-based cryptography are its tremendous hardware and software requirements. In this paper we present three side-channel protected hardware/software designs for pairing-based cryptography yet small and practically fast: our plain ARM Cortex-M0+-based design computes a pairing in less than one second. The utilization of a multiply-accumulate instruction-set extension or a light-weight drop-in hardware accelerator that is placed between CPU and data memory improves runtime up to six times. With a 10.1 kGE large drop-in module and a 49 kGE large platform, our design is one of the smallest pairing designs available. Its very practical runtime of 162 ms for one pairing on a 254-bit BN curve and its reusability for other elliptic-curve based crypto systems offer a great solution for every microprocessor-based embedded application.

The construction of a verifiable random function (VRF) with large input space and full adaptive security from a static, non-interactive complexity assumption, like decisional Diffie-Hellman, has proven to be a challenging task. To date it is not even clear that such a VRF exists. Most known constructions either allow only a small input space of polynomially-bounded size, or do not achieve full adaptive security under a static, non-interactive complexity assumption. The only known constructions without these restrictions are based on non-static, so-called "q-type" assumptions, which are parametrized by an integer q. Since q-type assumptions get stronger with larger q, it is desirable to have q as small as possible. In current constructions, q is either a polynomial (e.g., Hohenberger and Waters, Eurocrypt 2010) or at least linear (e.g., Boneh et al., CCS 2010) in the security parameter. We show that it is possible to construct relatively simple and efficient verifiable random functions with full adaptive security and large input space from non-interactive q-type assumptions, where q is only logarithmic in the security parameter. Interestingly, our VRF is essentially identical to the verifiable unpredictable function (VUF) by Lysyanskaya (Crypto 2002), but very different from Lysyanskaya’s VRF from the same paper. Thus, our result can also be viewed as a new, direct VRF-security proof for Lysyanskaya’s VUF. As a technical tool, we introduce and construct balanced admissible hash functions.

Gentry, Sahai and Waters recently presented the first (leveled) identity-based fully homomorphic (IBFHE) encryption scheme (CRYPTO 2013). Their scheme however only works in the single-identity setting; that is, homomorphic evaluation can only be performed on ciphertexts created with the same identity. In this work, we extend their results to the multi-identity setting and obtain a multi-identity IBFHE scheme that is selectively secure in the random oracle model under the hardness of Learning with Errors (LWE). We also obtain a multi-key fully-homomorphic encryption (FHE) scheme that is secure under LWE in the standard model. This is the first multi-key FHE based on a well-established assumption such as standard LWE. The multi-key FHE of López-Alt, Tromer and Vaikuntanathan (STOC 2012) relied on a non-standard assumption, referred to as the Decisional Small Polynomial Ratio assumption.

We construct the first Authenticated Key Exchange (AKE) protocol whose security does not degrade with an increasing number of users or sessions. We describe a three-message protocol and prove security in an enhanced version of the classical Bellare-Rogaway security model. Our construction is modular, and can be instantiated efficiently from standard assumptions (such as the SXDH or DLIN assumptions in pairing-friendly groups). For instance, we provide an SXDH-based protocol whose communication complexity is only 14 group elements and 4 exponents (plus some bookkeeping information). Along the way we develop new, stronger security definitions for digital signatures and key encapsulation mechanisms. For instance, we introduce a security model for digital signatures that provides existential unforgeability under chosen-message attacks in a multi-user setting with adaptive corruptions of secret keys. We show how to construct efficient schemes that satisfy the new definitions with tight security proofs under standard assumptions.

Motivated by the recent success of Bitcoin we study the question of constructing distributed cryptographic protocols in a fully peer-to-peer scenario (without any trusted setup) under the assumption that the adversary has limited computing power. We propose a formal model for this scenario and then we construct the following protocols working in it: (i) a broadcast protocol secure under the assumption that the honest parties have computing power that is some non-negligible fraction of computing power of the adversary (this fraction can be small, in particular it can be much less than 1/2), (ii) a protocol for identifying a set of parties such that the majority of them is honest, and every honest party belongs to this set (this protocol works under the assumption that the majority of computing power is controlled by the honest parties). Our broadcast protocol can be used to generate an unpredictable beacon (that can later serve, e.g., as a genesis block for a new cryptocurrency). The protocol from Point (ii) can be used to construct arbitrary multiparty computation protocols. Our main tool for checking the computing power of the parties are the Proofs of Work (Dwork and Naor, CRYPTO 92). Our broadcast protocol is built on top of the classical protocol of Dolev and Strong (SIAM J. on Comp. 1983). Although our motivation is mostly theoretic, we believe that our ideas can lead to practical implementations (probably after some optimizations and simplifications). We discuss some possible applications of our protocols at the end of the paper.

This paper introduces a high-security post-quantum stateless hash-based signature scheme that signs hundreds of messages per second on a modern 4-core 3.5GHz Intel CPU. Signatures are 41 KB, public keys are 1 KB, and private keys are 1 KB. The signature scheme is designed to provide long-term $2^{128}$ security even against attackers equipped with quantum computers. Unlike most hash-based designs, this signature scheme is stateless, allowing it to be a drop-in replacement for current signature schemes.

Efficient implementations of lattice-based cryptographic schemes have been limited to only the most basic primitives like encryption and digital signatures. The main reason for this limitation is that at the core of many advanced lattice primitives is a trapdoor sampling algorithm(Gentry, Peikert, Vaikuntanathan, STOC 2008) that produced outputs that were too long for practical applications. In this work, we show that using a particular distribution over NTRU lattices can make GPV-based schemes suitable for practice. More concretely, we present the first lattice-based IBE scheme with practical parameters - key and ciphertext sizes are between two and four kilobytes, and all encryption and decryption operations take approximately one millisecond on a moderately-powered laptop. As a by-product, we also obtain digital signature schemes which are shorter than the previously most-compact ones of Ducas, Durmus, Lepoint, and Lyubashevsky from Crypto 2013.

With a scheme for \textit{robust} authenticated-encryption a user can select an arbitrary value $\lambda \ge 0$ and then encrypt a plaintext of any length into a ciphertext that's $\lambda$ characters longer. The scheme must provide all the privacy and authenticity possible for the requested~$\lambda$. We formalize and investigate this idea, and construct a well-optimized solution, AEZ, from the AES round function. Our scheme encrypts strings at almost the same rate as OCB-AES or CTR-AES (on Haswell, AEZ has a peak speed of about 0.7 cpb). To accomplish this we employ an approach we call \textit{prove-then-prune}: prove security and then instantiate with a \textit{scaled-down} primitive (e.g., reducing rounds for blockcipher calls).

An Authenticated encryption scheme is a scheme which provides privacy and integrity by using a secret key. In 2013, CAESAR (the ``Competition for Authenticated Encryption: Security, Applicability, and Robustness'') was co-founded by NIST and Dan Bernstein with the aim of finding authenticated encryption schemes that offer advantages over AES-GCM and are suitable for widespread adoption. The first round started with 57 candidates in March 2014; and nine of these first-round candidates where broken and withdrawn from the competition. The remaining 48 candidates went through an intense process of review, analysis and comparison. While the cryptographic community benefits greatly from the manifold different submission designs, their sheer number implies a challenging amount of study. This paper provides an easy-to-grasp overview over functional aspects, security parameters, and robustness offerings by the CAESAR candidates, clustered by their underlying designs (block-cipher-, stream-cipher-, permutation-/sponge-, compression-function-based, dedicated). After intensive review and analysis of all 48 candidates by the community, the CAESAR committee selected only 30 candidates for the second round. The announcement for the third round candidates was made on 15th August 2016 and 15 candidates were chosen for the third round.

Watrous (STOC 2006) proved that plugging classical bit commitment scheme that is secure against quantum attack into the GMW-type construction of zero-knowledge gives a classical zero-knowledge proof that is secure against quantum attack. In this paper, we showed that plugging quantum bit commitment scheme (allowing quantum computation and communication) into the GMW-type construction also gives a quantum zero-knowledge proof, as one expects. However, since the binding condition of quantum bit commitment scheme is inherently different from its classical counterpart, compared with Watrous' security proof, here we encounter new difficulty in soundness analysis. To overcome the difficulty, we take a geometric approach, managing to reduce quantum soundness analysis to classical soundness analysis. We also propose a formalization of non-interactive quantum bit commitment scheme, which may come in handy in other places. Moreover, inspired by our formalization, we generalize Naor's construction of bit commitment scheme to the quantum setting, achieving non-interactive commit stage. We hope quantum bit commitment scheme can find more applications in quantum cryptography.

Performance monitors are provided in modern day computers for observing various features of the underlying microarchitectures. However the combination of underlying micro-architectural features and performance counters lead to side-channels which can be exploited for attacking cipher implementations. In this paper, to the best of our knowledge we study for the first time, the combination of branch-predictor algorithms and performance counters to demonstrate a fault attack on the popular square-and-multiply based exponentiation algorithm, used in the RSA. The attacks exploiting branching event like branch taken can be foiled by Montgomery Ladder based implementation of the exponentiation algorithm, while attacks based on branch miss are more devastating. We demonstrate the power of the attack exploiting branch misses from performance monitors by formalizing a fault attack model, where the adversary is capable of performing a bit flip at a desired bit position of the secret exponent. The paper characterizes the branch predictors using the popular two-bit predictor and formulates the dependence on the number of branch misses on the fault induced. This characterization is exploited to develop an iterative attack algorithm where knowledge of the previously determined key-bits and the difference of branch misses (as gathered from the performance counters) are utilised to determine the next bit. The attack has been validated on several standard Intel platforms, and puts to threat several implementations of exponentiation algorithms ranging from standard square-and-multiply, Montgomery Ladder to RSA-CRT and which are often used as side-channel counter measures. The attacks show that using the fault attack model featuring branch predictors one can attack implementations of exponentiation: both square and multiply, and Montgomery ladder, which forms the central algorithm for several standard public key ciphers.

The square map is one of the functions that is used in cryptography. For instance, the square map is used in Rabin encryption scheme, block cipher RC6 and stream cipher Rabbit, in different forms. In this paper we study a special case of the square map, namely the square function modulo a power of two. We obtain probability distribution of the output of this map as a vectorial Boolean function. We find probability distribution of the component Boolean functions of this map. We present the joint probability distribution of the component Boolean functions of this function. We introduce a new function which is similar to the function that is used in Rabbit cipher and we compute the probability distribution of the component Boolean functions of this new map.

The area of lattice-based cryptography is growing ever-more prominent as a paradigm for quantum-resistant cryptography. One of the most important hard problem underpinning the security of lattice- based cryptosystems is the shortest vector problem (SVP). At present, two approaches dominate methods for solving instances of this problem in practice: enumeration and sieving. In 2010, Micciancio and Voulgaris presented a heuristic member of the sieving family, known as GaussSieve, demonstrating it to be comparable to enumeration methods in practice. With contemporary lattice-based cryptographic proposals relying largely on the hardness of solving the shortest and closest vector problems in ideal lattices, examining possible improvements to sieving algorithms becomes highly pertinent since, at present, only sieving algorithms have been successfully adapted to solve such instances more efficiently than in the random lattice case. In this paper, we propose a number of heuristic improvements to GaussSieve, which can also be applied to other sieving algorithms for SVP.

The aim of this paper is to introduce some modifications in Tor, in order to improve user’s anonymity and relay’s security. Thus, we introduced a system that will ensure anonymity for all users, while maintaining the ability to break the anonymity of a sender in case of misconduct. The revocation of the anonymity will require the use of secret sharing schemes, since we assume that, the lifting of the anonymity of the dishonest user should not depend on a single entity, but on a consensus within the network. In addition to the revocation of the anonymity, we propose in this paper further improvements such as mixing Tor traffic with those of the major internet groups, using the camouflage, or introducing a honeypot in the network.

Feistel constructions have been shown to be indifferentiable from random permutations at STOC 2011. Whereas how to properly mix the keys into an un-keyed Feistel construction without appealing to domain separation technique to obtain a block cipher which is provably secure against known-key and chosen-key attacks (or to obtain an ideal cipher) remains an open problem. We study this, particularly the basic structure of NSA's SIMON family of block ciphers. SIMON family takes a construction which has the subkey xored into a halve of the state at each round. More clearly, at the $i$-th round, the state is updated according to $$(x_i,x_{i-1})\mapsto(x_{i-1}\oplus F_i(x_i)\oplus k_i,x_i)$$ For such key-alternating Feistel ciphers, we show that 21 rounds are sufficient to achieve indifferentiability from ideal ciphers with $2n$-bit blocks and $n$-bit keys, assuming the $n$-to-$n$-bit round functions $F_1,\ldots,F_{21}$ to be random and public and an identical user-provided $n$-bit key to be applied at each round. This gives an answer to the question mentioned before, which is the first to our knowledge.

Divisible E-cash systems allow users to withdraw a unique coin of value $2^n$ from a bank, but then to spend it in several times to distinct merchants. In such a system, whereas users want anonymity of their transactions, the bank wants to prevent, or at least detect, double-spending, and trace the defrauders. While this primitive was introduced two decades ago, quite a few (really) anonymous constructions have been introduced. In addition, all but one were just proven secure in the random oracle model, but still with either weak security models or quite complex settings and thus costly constructions. The unique proposal, secure in the standard model, appeared recently and is unpractical. As evidence, the authors left the construction of an efficient scheme secure in this model as an open problem.

In this paper we present a new attack on the polynomial version of the Ring-LWE assumption, for certain carefully chosen number fields. This variant of RLWE, introduced in [BV11] and called the PLWE assumption, is known to be as hard as the RLWE assumption for 2-power cyclotomic number fields, and for cyclotomic number fields in general with a small cost in terms of error growth. For general number fields, we articulate the relevant properties and prove security reductions for number fields with those properties. We then present an attack on PLWE for number fields satisfying certain properties.

We propose two extremely stealthy hardware Trojans that facilitate fault-injection attacks in cryptographic blocks. The Trojans are carefully inserted to modify the electrical characteristics of predetermined transistors in a circuit by altering parameters such as doping concentration and dopant area. These Trojans are activated with very low probability under the presence of a slightly reduced supply voltage (0.001 for 20\% $V_{dd}$ reduction). We demonstrate the effectiveness of the Trojans by utilizing them to inject faults into an ASIC implementation of the recently introduced lightweight cipher %ip PRINCE. Full circuit-level simulation followed by differential cryptanalysis demonstrate that the secret key can be reconstructed after around 5 fault-injections.

State-of-the-art fault-based cryptanalysis methods are capable of breaking most recent ciphers after only a few fault injections. However, they require temporal and spatial accuracies of fault injection that were believed to rule out low-cost injection techniques such as voltage, frequency or temperature manipulation. We investigate selection of supply-voltage and temperature values that are suitable for high-precision fault injection even up to a single bit. The object of our studies is an ASIC implementation of the recently presented block cipher PRINCE, for which a two-stage fault attack scheme has been suggested lately. This attack requires, on average, about four to five fault injections in well-defined locations. We show by electrical simulations that voltage-temperature points exist for which faults show up at locations required for a successful attack with a likelihood of around 0.1\%. This implies that the complete attack can be mounted by approximately 4,000 to 5,000 fault injection attempts, which is clearly feasible.

The topic of this paper is collusion resistant watermarking, a.k.a. traitor tracing, in particular bias-based traitor tracing codes as introduced by G.Tardos in 2003. The past years have seen an ongoing effort to construct efficient high-performance decoders for these codes. In this paper we construct a score system from the Neyman-Pearson hypothesis test (which is known to be the most powerful test possible) into which we feed all the evidence available to the tracer, in particular the codewords of all users. As far as we know, until now simple decoders using Neyman-Pearson have taken into consideration only the codeword of a single user, namely the user under scrutiny. The Neyman-Pearson score needs as input the attack strategy of the colluders, which typically is not known to the tracer. We insert the Interleaving attack, which plays a very special role in the theory of bias-based traitor tracing by virtue of being part of the asymptotic (i.e. large coalition size) saddlepoint solution. The score system obtained in this way is universal: effective not only against the Interleaving attack, but against all other attack strategies as well. Our score function for one user depends on the other users' codewords in a very simple way: through the symbol tallies, which are easily computed. We present bounds on the False Positive probability and show ROC curves obtained from simulations. We investigate the probability distribution of the score. Finally we apply our construction to the area of (medical) Group Testing, which is related to traitor tracing.

Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O’Neill (CRYPTO 2007), is an important technique for searchable encryption; it allows quick, logarithmic-time, search over encrypted data items. The technique is most effective in scenarios where frequent search queries are performed over a huge database of unpredictable data items. We initiate the study of deterministic public-key encryption (D-PKE) in the presence of leakage. We formulate appropriate security notions for leakage-resilient D-PKE, and present constructions that achieve them in the standard model. We work in the continual leakage model, where the secret-key is updated at regular intervals and an attacker can learn arbitrary but bounded leakage on the secret key during each time interval. We, however, do not consider leakage during the updates. Our main construction is based on the (standard) linear assumption in bilinear groups, tolerat- ing up to 0.5 - o(1) fraction of arbitrary leakage. The leakage rate can be improved to 1 - o(1) by relying on the SXDH assumption. At a technical level, we propose and construct a “continual leakage resilient” version of the all-but-one lossy trapdoor functions, introduced by Peikert and Waters (STOC 2008). Our formulation and construction of leakage-resilient lossy-TDFs is of independent general interest for leakage-resilient cryptography.

Program obfuscation is the process of making a program "unintelligible" without changing the program's underlying input/output behavior. Although there is a long line of work on heuristic techniques for obfuscation, such approaches do not provide any cryptographic guarantee on their effectiveness. A recent result by Garg et al. (FOCS 2013), however, shows that cryptographic program obfuscation is indeed possible based on a new primitive called a \emph{graded encoding scheme}. In this work, we present the first implementation of such an obfuscator. We describe several challenges and optimizations we made along the way, present a detailed evaluation of our implementation, and discuss research problems that need to be addressed before such obfuscators can be used in practice.

Identity Based Encryption (IBE) has been constructed from bilinear pairings, lattices and quadratic residuosity. The latter is an attractive basis for an IBE owing to the fact that it is a well-understood hard problem from number theory. Cocks constructed the first such scheme, and subsequent improvements have been made to achieve anonymity and improve space efficiency. However, the anonymous variants of Cocks' scheme thus far are all less efficient than the original. In this paper, we present a new universally-anonymous IBE scheme based on the quadratic residuosity problem. Our scheme has better performance than the universally anonymous scheme from Ateniese and Gasti (CT-RSA 2009) at the expense of more ciphertext expansion. Another contribution of this paper is a modification to a variant of the space-efficient scheme by Boneh, Gentry and Hamburg (FOCS 07) that results in an IND-ID-CPA secure IBE scheme with comparable efficiency to Cocks, but with reduced ciphertext expansion.

In this paper, we construct a fully homomorphic encryption (FHE) scheme over integers with the message space $Z_Q$ for any prime $Q$. Even for the binary case $Q=2$, our decryption circuit has a smaller degree than that of the previous scheme; the multiplicative degree is reduced from $O(\lambda (\log \lambda)^2)$ to $O(\lambda)$, where $\lambda$ is the security parameter. We also extend our FHE scheme to a batch FHE scheme.

We propose a new way to obfuscate programs, using composite-order multilinear maps. Our construction operates directly on straight-line programs (arithmetic circuits), rather than converting them to matrix branching programs as in other known approaches. This yields considerable efficiency improvements. For an NC1 circuit of size $s$ and depth $d$, with $\n$ inputs, we require only $O(d^2s^2 + \n^2)$ multilinear map operations to evaluate the obfuscated circuit---as compared with other known approaches, for which the number of operations is exponential in $d$. We prove virtual black-box (VBB) security for our construction in a generic model of multilinear maps of hidden composite order, extending previous models for the prime-order setting. Our scheme works either with "noisy" multilinear maps, which can only evaluate expressions of degree $\lambda^c$ for pre-specified constant $c$; or with "clean" multilinear maps, which can evaluate arbitrary expressions. The "noisy" variant can be instantiated at present with the Coron-Lepoint-Tibouchi scheme, while the existence of "clean" maps is still unknown. With known "noisy" maps, our new obfuscator applies only to NC1 circuits, requiring the additional assumption of FHE in order to bootstrap to P/poly (as in other obfuscation constructions). From "clean" multilinear maps, on the other hand (whose existence is still open), we present the first approach that would achieve obfuscation for P/poly directly, without FHE. We also introduce the concept of succinct obfuscation, in which the obfuscation overhead size depends only on the length of the input and of the secret part of the circuit. Using our new techniques, along with the assumption that factoring is hard on average, we show that "clean" multilinear maps imply succinct obfuscation for P/poly. For the first time, the only remaining obstacle to implementable obfuscation in practice is the noise growth in known, "noisy" multilinear maps. Our results demonstrate that the question of "clean" multilinear maps is not a technicality, but a central open problem.

Lattice-based cryptography became a hot-topic in the past years because it seems to be quantum immune, i.e., resistant to attacks operated with quantum computers. The security of lattice-based cryptosystems is determined by the hardness of certain lattice problems, such as the Shortest Vector Problem (SVP). Thus, it is of prime importance to study how efficiently SVP-solvers can be implemented. This paper presents a parallel shared-memory implementation of the GaussSieve algorithm, a well known SVP-solver. Our implementation achieves almost linear and linear speedups with up to 64 cores, depending on the tested scenario, and delivers better sequential performance than any other disclosed GaussSieve implementation. In this paper, we show that it is possible to implement a highly scalable version of GaussSieve on multi-core CPU-chips. The key features of our implementation are a lock-free singly linked list, and hand-tuned, vectorized code. Additionally, we propose an algorithmic optimization that leads to faster convergence.

Block ciphers such as AES are deterministic, keyed functions that operate on small, fixed-size blocks. Block-cipher \emph{modes of operation} define a mechanism for probabilistic encryption of arbitrary length messages using any underlying block cipher. A mode of operation can be proven secure (say, against chosen-plaintext attacks) based on the assumption that the underlying block cipher is a pseudorandom function. Such proofs are complex and error-prone, however, and must be done from scratch whenever a new mode of operation is developed. We propose an \emph{automated} approach for the security analysis of block-cipher modes of operation based on a ``local'' analysis of the steps carried out by the mode when handling a \emph{single} message block. We model these steps as a directed, acyclic graph, with nodes corresponding to instructions and edges corresponding to intermediate values. We then introduce a set of \emph{labels} and \emph{constraints} on the edges, and prove a meta-theorem showing that any mode for which there exists a labeling of the edges satisfying these constraints is secure (against chosen-plaintext attacks). This allows us to reduce security of a given mode to a constraint-satisfaction problem, which in turn can be handled using an SMT solver. We couple our security-analysis tool with a routine that automatically generates viable modes; together, these allow us to synthesize hundreds of secure modes.

In this work, we seek to extend the capabilities of the “core obfuscator” from the work of Garg, Gentry, Halevi, Raykova, Sahai, and Waters (FOCS 2013), and all subsequent works constructing general-purpose obfuscators. This core obfuscator builds upon approximate multilinear maps, and applies to matrix branching programs. All previous works, however, limited the applicability of such core obfuscators to matrix branching programs where each matrix was of full rank. As we illustrate by example, this limitation is quite problematic, and intuitively limits the core obfuscator to obfuscating matrix branching programs that cannot “forget.” At a technical level, this limitation arises in previous work because all previous work relies on Kilian’s statistical simulation theorem, which is false when applied to matrices not of full rank. In our work, we build the first core obfuscator that can apply to matrix branching programs where matrices can be of arbitrary rank. We prove security of our obfuscator in the generic multilinear model, demonstrating a new proof technique that bypasses Kilian’s statistical simulation theorem. Furthermore, our obfuscator achieves two other notable advances over previous work: - Our construction allows for non-square matrices of arbitrary dimensions. We also show that this flexibility yields concrete efficiency gains. - Our construction allows for a single obfuscation to yield multiple bits of output. All previous work yielded only one bit of output. Our work leads to significant efficiency gains for obfuscation. Furthermore, our work can be applied to achieve efficiency gains even in applications not directly using obfuscation.

We propose new fully secure attribute based encryption (ABE) systems for polynomial-size circuits in both key-policy and ciphertext-policy flavors. All the previous ABE systems for circuits were proved only selectively secure. Our schemes are based on asymmetric graded encoding systems in composite-order settings. The assumptions consist of the Subgroup Decision assumptions and two assumptions which are similar to Multi-linear Decisional Diffie-Hellman assumption (but more complex) and are proved to hold in the generic graded encoding model. Both of our systems enjoy succinctness: key and ciphertext sizes are proportional to their corresponding circuit and input string sizes. Our ciphertext-policy ABE for circuits is the first to achieve succinctness, and the first that can deal with unbounded-size circuits (even among selectively secure systems). We develop new techniques for proving co-selective security of key-policy ABE for circuits, which is the main ingredient for the dual-system encryption framework that uses computational arguments for enforcing full security.

A {\em randomized encoding} allows to represent a ``complex'' function $f(x)$ by a ``simpler'' randomized function $\hat{f}(x;r)$ whose output distribution encodes $f(x)$, while revealing nothing else regarding $x$. Existing randomized encodings, geared mostly to allow encoding with low parallel complexity, have proven instrumental in various strong applications such as multiparty computation and parallel cryptography. This work focuses on another natural complexity measure: {\em the time required to encode}. We construct {\em succinct randomized encodings} where a computation given by a (Turing or random-access) machine $M$, and input $x$, requiring time $t$ and space $s$, can be encoded roughly in time $\poly(|x|,\log t,s)$, thus inducing significant savings in time when $s \ll t$. The scheme guarantees computational input-privacy and is based on indistinguishability obfuscation for a relatively simple circuit class, which can in turn be based on a polynomial version of the subgroup elimination assumption on multilinear graded encodings. We then invoke succinct randomized encodings to obtain several strong applications, including: \begin{itemize} \item Indistinguishability obfuscation for uniform (Turing or random-access) machines, where the obfuscated machine $\iO(M)$ computes the same function as $M$ for inputs $x$ of apriori-fixed maximal size $n$, and is computed in time $\poly(n,\log t,s)$. \item Functional encryption for uniform machines, where a functional decryption key corresponding to $M$ allows decrypting $M(x)$ from encryptions of $x$. As in the previous case, inputs $x$ are of apriori-fixed maximal size $n$, and key derivation time is roughly $\poly(n,\log t,s)$. \item Publicly-verifiable 2-message delegation where verification time is roughly $\poly(n,\log t,s)$. We also show how to transform any 2-message delegation scheme to an essentially non-interactive system where the verifier message is reusable. \end{itemize} For the first application, we also require subexponentially-secure indistinguishability obfuscation for circuits, and for the second polynomial indistinguishability obfuscation, which can be replaced by more concrete polynomial hardness assumptions on multilinear graded-encodings. Previously, both applications were only known based on various non-standard knowledge assumptions.