After more than a decade of usage, bilinear groups have established their place in the cryptographic canon by enabling the construction of many advanced cryptographic primitives. Unfortunately, this explosion in functionality has been accompanied by an analogous growth in the complexity of the assumptions used to prove security. Many of these assumptions have been gathered under the umbrella of the "uber-assumption," yet certain classes of these assumptions -- namely, q-type assumptions -- are stronger and require larger parameter sizes than their static counterparts. In this paper, we show that in certain groups, many classes of q-type assumptions are in fact implied by subgroup hiding (a well-established, static assumption). Our main tool in this endeavor is the dual-system technique, as introduced by Waters in 2009. As a case study, we first show that in composite-order groups, we can prove the security of the Dodis-Yampolskiy PRF based solely on subgroup hiding and allow for a domain of arbitrary size (the original proof only allowed a polynomially-sized domain). We then turn our attention to classes of q-type assumptions and show that they are implied -- when instantiated in appropriate groups -- solely by subgroup hiding. These classes are quite general and include assumptions such as q-SDH. Concretely, our result implies that every construction relying on such assumptions for security (e.g., Boneh-Boyen signatures) can, when instantiated in appropriate composite-order bilinear groups, be proved secure under subgroup hiding instead.

Enumeration algorithms are the best currently known methods to solve lattice problems, both in theory (within the class of polynomial space algorithms), and in practice (where they are routinely used to evaluate the concrete security of lattice cryptography). However, there is an uncomfortable gap between our theoretical understanding and practical performance of lattice point enumeration algorithms. The algorithms typically used in practice have worst-case asymptotic running time $2^{O(n^2)}$, but perform extremely well in practice, at least for all values of the lattice dimension for which experimentation is feasible. At the same time, theoretical algorithms (Kannan, Mathematics of Operation Research 12(3):415-440, 1987) are asymptotically superior (achieving $2^{O(n \log n)}$ running time), but they are never used in practice because they incur a substantial overhead that makes them uncompetitive for all reasonable values of the lattice dimension $n$. This gap is especially troublesome when algorithms are run in practice to evaluate the concrete security of a cryptosystem, and then experimental results are extrapolated to much larger dimension where solving lattice problems is computationally infeasible. We introduce a new class of (polynomial space) lattice enumeration algorithms that simultaneously achieve asymptotic efficiency (meeting the theoretical $n^{O(n)} = 2^{O(n \log n)}$ time bound) and practicality, matching or surpassing the performance of practical algorithms already in moderately low dimension. Key technical contributions that allow us to achieve this result are a new analysis technique that allows us to greatly reduce the number of recursive calls performed during preprocessing (from super exponential in $n$ to single exponential, or even polynomial in $n$), a new enumeration technique that can be directly applied to projected lattice (basis) vectors, without the need to remove linear dependencies, and a modified block basis reduction method with fast (logarithmic) convergence properties. The last technique is used to obtain a new SVP enumeration procedure with $\tilde O(n^{n/2e})$ running time, matching (even in the constant in the exponent) the optimal worst-case analysis (Hanrot and Stehlë, CRYPTO 2007) of Kannan's theoretical algorithm, but with far superior performance in practice. We complement our theoretical analysis with a comprehensive set of experiments that not only support our practicality claims, but also allow to estimate the cross-over point between different versions of enumeration algorithms, as well as asymptotically faster (but not quite practical) algorithms running in single exponential $2^{O(n)}$ time and space.

In this paper, we present new classes of public key cryptosystem over $F_2^8$ based on Reed-Solomon codes, referred to as K(XVII)SE(1)PKC and K(XVII)$\Sigma \Pi$PKC, a subclass of K(XVII)SE(1)PKC. We show that K(XVII)SE(1)PKC over $F_2^8$ can be secure against the various attacks. We also present K(XVII)$\Sigma \Pi$PKC over $F_2^8$, a subclass of K(XVII)SE(1)PKC. We show that any assertion of successfull attack on K(XVII)SE(1)PKC including K(XVII)$\Sigma \Pi$PKC whose parameters are properly chosen is a coding theoretical contradiction. We thus conclude that K(XVII)SE(1)PKC and K(XVII)$\Sigma \Pi$PKC would be secure against the various attacks including LLL attack. The schemes presented in this paper would yield brand-new techniques in the field of code-based PKC.

We propose the first practical attribute-based signature (ABS) scheme with attribute privacy without pairings in the random oracle model. Our strategy is in the Fiat-Shamir paradigm; we first provide a concrete construction of a $\Sigma$-protocol of \textit{boolean proof}, which is a generalization of the well-known $\Sigma$-protocol of OR-proof, so that it can treat any monotone boolean formula instead of a single OR-gate. Then, we apply the Fiat-Shamir transformation to our $\Sigma$-protocol of boolean proof and obtain a non-interactive witness-indistinguishable proof of knowledge system (NIWIPoK) which has a knowledge extractor in the random oracle model. Finally, by combining our NIWIPoK with a credential bundle scheme of the Fiat-Shamir signature, we obtain an attribute-based signature scheme (ABS) which possesses the property of attribute privacy. The series of constructions are obtained from a given $\Sigma$-protocol and can be attained without pairings.

MDS matrices allow to build optimal linear diffusion layers in block ciphers. However, MDS matrices cannot be sparse and usually have a large description, inducing costly software/hardware implementations. Recursive MDS matrices allow to solve this problem by focusing on MDS matrices that can be computed as a power of a simple companion matrix, thus having a compact description suitable even for constrained environments. However, up to now, finding recursive MDS matrices required to perform an exhaustive search on families of companion matrices, thus limiting the size of MDS matrices one could look for. In this article we propose a new direct construction based on shortened BCH codes, allowing to efficiently construct such matrices for whatever parameters. Unfortunately, not all recursive MDS matrices can be obtained from BCH codes, and our algorithm is not always guaranteed to find the best matrices for a given set of parameters.

Side-channel attacks are a powerful tool to discover the cryptographic secrets of a chip or other device but only too often do they require too many traces or leave too many possible keys to explore. In this paper we show that for side channel attacks on discrete-logarithm-based systems significantly more unknown bits can be handled by using Pollard's kangaroo method: if $b$ bits are unknown then the attack runs in $2^{b/2}$ instead of $2^b$. If an attacker has many targets in the same group and thus has reasons to invest in precomputation, the costs can even be brought down to $2^{b/3}$. Usually the separation between known and unknown keybits is not this clear cut -- they are known with probabilities ranging between 100\% and 0\%. Enumeration and rank estimation of cryptographic keys based on partial information derived from cryptanalysis have become important tools for security evaluations. They make the line between a broken and secure device more clear and thus help security evaluators determine how high the security of a device is. For symmetric-key cryptography there has been some recent work on key enumeration and rank estimation, but for discrete-logarithm-based systems these algorithms fail because the subkeys are not independent and the algorithms cannot take advantage of the above-mentioned faster attacks. We present $\epsilon$-enumeration as a new method to compute the rank of a key by using the probabilities together with (variations of) Pollard's kangaroo algorithm and give experimental evidence.

Since the advent of secret sharing scheme many researches have been allocated to study on this topic because it has a lot of application. For the first time Shamir and Blakley introduced the concepts of secret sharing. In their scheme, just one secret is shared. After a while, Harn present a scheme in which many secrets can be shared, but the secrets have to recover in predetermined order. In addition, in his scheme just one share is assigned to each participant. After a while, many scheme introduced such that they have not any constraint on the order of recovering secrets. These kind of scheme is called Multi Secret Sharing Scheme and it abbreviated by MSS. To the best of our knowledge, up until now, no exact definition for the security of MSS scheme has been presented. In this paper, a definition for secrecy of MSS scheme is introduced and a MSS scheme is presented based on Learning With Error (LWE). LWE is a one of lattice concepts which nowadays constitutes the core of many cryptographic constructions because the hardness of lattice problems is well studied and the hardness of these constructions can be reduced to NP-Hard problems. The advantage of using LWE is twofold, first is that the hardness of LWE is well understood, second working with it is very simple because just simple operations are used. At the end of the paper a verifiable version of presented MSS scheme is given. Verifiability is an important feature which has defined. In this kind of schemes, dishonest dealer or participants can be identified.

In order to obtain differential patterns over many rounds of a cryptographic primitive, the cryptanalyst often needs to work on local differential trail analysis. Examples include merging two differential trail parts into one or, in the case of boomerang and rectangle attacks, connecting two short trails within the quartet boomerang setting. In the latter case, as shown by Murphy in 2011, caution should be exercised as there is increased chance of running into contradictions in the middle rounds of the primitive. In this paper, we propose the use of a SAT-based constraint solver URSA as aid in analysis of differential trails and find that previous rectangle/boomerang attacks on XTEA and SHACAL-1 block ciphers and SM3 hash function are based on incompatible trails. Given the C specification of the cryptographic primitive, verifying differential trail portions requires minimal work on the side of the cryptanalyst.

In 2005, Juels and Weis proposed HB+, a perfectly adapted authentication protocol for resource-constrained devices such as RFID tags. The HB+ protocol is based on the Learning Parity with Noise (LPN) problem and is proven secure against active adversaries. Since a man-in-the-middle attack on HB+ due to Gilbert et al. was published, many proposals have been made to improve the HB+ protocol. But none of these was formally proven secure against general man-in-the-middle adversaries. In this paper we present a solution to make the HB+ protocol resistant to general man-in-the-middle adversaries without exceeding the computational and storage capabilities of the RFID tag.

Authors propose several approaches for increasing performance of multiplicative inversion algorithm in binary fields based on Extended Euclidean Algorithm (EEA). First approach is based on Extended Euclidean Algorithm specificity: either invariant polynomial u remains intact or swaps with invariant polynomial v. It makes it possible to avoid necessity of polynomial v degree computing. The second approach is based on searching the "next matching index" when calculating the degree of the polynomial, since degree polynomial invariant u at least decreases by 1, then it is possible to use current value while further calculation the degree of the polynomial.

In cryptography, forward secrecy is a well-known property for key agreement protocols. It ensures that a session key will remain private even if one of the long-term secret keys is compromised in the future. In this paper, we investigate some forward security properties for Public-key Encryption with Keyword Search (PEKS) schemes, which allow a client to store encrypted data and delegate search operations to a server. The proposed properties guarantee that the client's privacy is protected to the maximum extent even if his private key is compromised in the future. Motivated by the generic transformation from anonymous Identity-Based Encryption (IBE) to PEKS, we correspondingly propose some forward security properties for IBE, in which case we assume the attacker learns the master secret key. We then study several existing PEKS and IBE schemes, including a PEKS scheme by Nishioka, an IBE scheme by Boneh, Raghunathan and Segev, and an IBE scheme by Arriaga, Tang and Ryan. Our analysis indicates that the proposed forward security properties can be achieved by some of these schemes if the attacker is RO-non-adaptive (the attacker does not define its distributions based on the random oracle). Finally, we propose the concept of correlated-input indistinguishable hash function and show how to extend the Boyen-Waters anonymous IBE scheme to achieve the forward security properties against adaptive attackers.

In this paper we study the existing CRT-RSA countermeasures against fault-injection attacks. In an attempt to classify them we get to achieve deep understanding of how they work. We show that the many countermeasures that we study (and their variations) actually share a number of common features, but optimize them in different ways. We also show that there is no conceptual distinction between test-based and infective countermeasures and how either one can be transformed into the other. Furthermore, we show that faults on the code (skipping instructions) can be captured by considering only faults on the data. These intermediate results allow us to improve the state of the art in several ways: (a) we fix an existing and that was known to be broken countermeasure (namely the one from Shamir); (b) we drastically optimize an existing countermeasure (namely the one from Vigilant) which we reduce to 3 tests instead of 9 in its original version, and prove that it resists not only one fault but also an arbitrary number of randomizing faults; (c) we also show how to upgrade countermeasures to resist any given number of faults: given a correct first-order countermeasure, we present a way to design a provable high-order countermeasure (for a well-defined and reasonable fault model). Finally, we pave the way for a generic approach against fault attacks for any modular arithmetic computations, and thus for the automatic insertion of countermeasures.

By introducing extra shields on Shpilrain and Ushakov's Ko-Lee-like protocol based on the decomposition problem of group elements we propose two new key exchange schemes and then a number of public key cryptographic protocols. We show that these protocols are free of known attacks. Particularly,if the entities taking part in our protocols create their private keys composed by the generators of the Mihailova subgroups of Bn, we show that the safety of our protocols are very highly guarantied by the insolvability of subgroup membership problem of the Mihailova subgroups.

We present a round-efficient black-box construction of a general multi-party computation (MPC) protocol that satisfies composability in the plain model. The security of our protocol is proven in the angel-based UC framework [Prabhakaran and Sahai, STOC'04] under the minimal assumption of the existence of semi-honest oblivious transfer protocols. The round complexity of our protocol is \max(\tilde{O}(\log^2 n), O(R_{OT})) when the round complexity of the underlying oblivious transfer protocol is R_{OT}. Since constant-round semi-honest oblivious transfer protocols can be constructed under standard assumptions (such as the existence of enhanced trapdoor permutations), our result gives a \tilde{O}(\log^2 n)-round protocol under these assumptions. Previously, only an O(\max(n^{\epsilon}, R_{OT}))-round protocol was shown, where \epsilon>0 is an arbitrary constant. We obtain our MPC protocol by constructing a \tilde{O}(\log^2 n)-round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions.

The world just witnessed the surge of a new and powerful attacker, which was able to coerce operators and acquire the necessary keys to break the privacy of users. Once the encryption key is exposed, the only viable measure to preserve data confidentiality is to limit the adversary’s access to the ciphertext. This may be achieved, for example, using multi-cloud storage systems. These systems spread data across multiple servers in different administrative domains, to cater for availability and fault tolerance. If the adversary can only compromise a subset of these domains, multi-cloud storage systems may prevent the adversary from accessing the entire ciphertext. However, if data is encrypted using existing encryption schemes, spreading the ciphertext on multiple servers does not entirely solve the problem since an adversary which has the encryption key, can still compromise single servers and decrypt the ciphertext stored therein. In this paper, we leverage multi-cloud storage systems to provide data confidentiality against an adversary which has access to the encryption key, and can compromise a large fraction of the storage servers. For this purpose, we first introduce a novel security definition that captures data confidentiality in the new adversarial model. We then propose Bastion, a primitive that is secure according to our definition and, therefore, guarantees data confidentiality even when the encryption key is exposed, as long as the adversary cannot compromise all storage servers. We analyze the security of Bastion, and we evaluate its performance by means of a prototype implementation. Our results show that Bastion incurs less than 5% overhead compared to existing semantically secure encryption modes. We also discuss practical insights with respect to the integration of Bastion in commercial multi-cloud storage systems.

Universally composable secure computation was assumed to require trusted setups, until it was realized that parties exchanging (untrusted) tamper-proof hardware tokens allow an alternative approach (Katz; EUROCRYPT 2007). This discovery initialized a line of research dealing with two different types of tokens. Using only a single stateful token, one can implement general statistically secure two-party computation (Döttling, Kraschewski, Müller-Quade; TCC 2011); though all security is lost if an adversarial token receiver manages to physically reset and rerun the token. Stateless tokens, which are secure by definition against any such resetting-attacks, however, do provably not suffice for arbitrary secure computations (Goyal, Ishai, Mahmoody, Sahai; CRYPTO 2010). We investigate the natural question of what is possible if an adversary can reset a token at most a bounded number of times (e.g., because each resetting attempt imposes a significant risk to trigger a self-destruction mechanism of the token). Somewhat surprisingly, our results come close to the known positive results with respect to non-resettable stateful tokens. In particular, we construct polynomially many instances of statistically secure and universally composable oblivious transfer, using only a constant number of tokens. Our techniques have some abstract similarities to previous solutions, which we grasp by defining a new security property for protocols that use oracle access. Additionally, we apply our techniques to zero-knowledge proofs and obtain a protocol that achieves the same properties as bounded-query zero-knowledge PCPs (Kilian, Petrank, Tardos; STOC 1997), even if a malicious prover may issue stateful PCP oracles.

An obfuscator $\O$ is Virtual Grey Box (VGB) for a class $\C$ of circuits if, for any $C\in\C$ and any predicate $\pi$, deducing $\pi(C)$ given $\O(C)$ is tantamount to deducing $\pi(C)$ given unbounded computational resources and polynomially many oracle queries to $C$. VGB obfuscation is often significantly more meaningful than indistinguishability obfuscation (IO). In fact, for some circuit families of interest VGB is equivalent to full-fledged Virtual Black Box obfuscation. We investigate the feasibility of obtaining VGB obfuscation for general circuits. We first formulate a natural strengthening of IO, called {\em strong IO} (SIO). Essentially, $\O$ is SIO for class $\C$ if $\O(C)\approx\O(C')$ whenever the pair $(C,C')$ is taken from a distribution over $\C$ where, for all $x$, $C(x)\neq C'(x)$ only with negligible probability. We then show that an obfuscator is VGB for a class $\C$ if and only if it is SIO for $\C$. This result is unconditional and holds for any $\C$. We also show that, for some circuit collections, SIO implies virtual black-box obfuscation. Finally, we formulate a slightly stronger variant of the semantic security property of graded encoding schemes [Pass-Seth-Telang Crypto 14], and show that existing obfuscators, such as the obfuscator of Barak et al. [Eurocrypt 14], are SIO for all circuits in NC$^1$, assuming that the underlying graded encoding scheme satisfies our variant of semantic security. {\em Put together, we obtain VGB obfuscation for all NC$^1$ circuits under assumptions that are almost the same as those used by Pass et al. to obtain IO for NC$^1$ circuits.} We also show that semantic security is in essence {\em necessary} for showing VGB obfuscation.

In this paper, we present a simpler and more restricted variant of the universally composable security (UC) framework that is suitable for ``standard'' two-party and multiparty computation tasks. Many of the complications of the UC framework exist in order to enable more general tasks than classic secure computation. This generality may be a barrier to entry for those who are used to the stand-alone model of secure computation and wish to work with universally composable security but are overwhelmed by the differences. The variant presented here (called simplified universally composable security, or just SUC) is closer to the definition of security for multiparty computation in the stand-alone setting. The main difference is that a protocol in the SUC framework runs with a \emph{fixed set of parties} who know each other's identities ahead of time, and machines \emph{cannot be added dynamically} to the execution. As a result, the definitions of polynomial time and protocol composition are much simpler. In addition, the SUC framework has authenticated channels built in, as is standard in previous definitions of security, and all communication is done via the adversary in order to enable arbitrary scheduling of messages. Due to these differences, not all cryptographic tasks can be expressed in the SUC framework. Nevertheless, standard secure computation tasks (like secure function evaluation) can be expressed. Importantly, we show a natural security-preserving transformation from protocols in the SUC model to protocols in the full-fledged UC model. Consequently, the UC composition theorem holds in the SUC model, and any protocol that is proven secure under SUC can be transformed to a protocol that is secure in the UC model.

We propose a log signing scheme that enables (a) verification of the integrity of the whole log, and (b) presentation of any record, along with a compact proof that the record has not been altered since the log was signed, without leaking any information about the contents of other records in the log. We give a formal proof of the security of the proposed scheme, discuss practical considerations, and provide an implementation case study.

This paper investigates large linear mappings with very good diffusion and efficient software implementations, that can be used as part of a block cipher design. The mappings are derived from linear codes over a small field (typically $F^{2^4}$) with a high dimension (typically 16) and a high minimum distance. This results in diffusion matrices with equally high dimension and a large branch number. Because we aim for parameters for which no MDS code is known to exist, we propose to use more flexible algebraic-geometry codes. We present two simple yet efficient algorithms for the software implementation of matrix-vector multiplication in this context, and derive conditions on the generator matrices of the codes to yield efficient encoders. We then specify an appropriate code and use its automorphisms as well as random sampling to find good such matrices. We provide concrete examples of parameters and implementations, and the corresponding assembly code. We also give performance figures in an example of application which show the interest of our approach.

Functional encryption supports restricted decryption keys that allow users to learn specific functions of the encrypted messages. Whereas the vast majority of research on functional encryption has so far focused on the privacy of the encrypted messages, in many realistic scenarios it is crucial to offer privacy also for the functions for which decryption keys are provided. Whereas function privacy is inherently limited in the public-key setting, in the private-key setting it has a tremendous potential. Specifically, one can hope to construct schemes where encryptions of messages $m_1, \ldots, m_T$ together with decryption keys corresponding to functions $f_1, \ldots, f_T$, reveal essentially no information other than the values $\{ f_i(m_j)\}_{i,j\in [T]}$. Despite its great potential, the known function-private private-key schemes either support rather limited families of functions (such as inner products), or offer somewhat weak notions of function privacy. We present a generic transformation that yields a function-private functional encryption scheme, starting with any non-function-private scheme for a sufficiently rich function class. Our transformation preserves the message privacy of the underlying scheme, and can be instantiated using a variety of existing schemes. Plugging in known constructions of functional encryption schemes, we obtain function-private schemes based either on obfuscation assumptions, on the Learning with Errors assumption, and even on the existence of any one-way function (offering various trade-offs between security and efficiency).

This paper presents three new attacks on the RSA cryptosystem. The first two attacks work when k RSA public keys (Ni, ei) are such that there exist k relations of the shape eix-yi\phi(Ni)=zi or of the shape eixi-y\phi(Ni)=zi where Ni = piqi, \phi(Ni)=(pi-1)(qi-1) and the parameters x, xi, y, yi, zi are suitably small in terms of the prime factors of the moduli. We show that our attacks enable us to simultaneously factor the k RSA moduli Ni. The third attack works when the prime factors p and q of the modulus N = pq share an amount of their least significant bits (LSBs) in the presence of two decryption exponents d1 and d2 sharing an amount of their most significant bits (MSBs). The three attacks improve the bounds of some former attacks that make RSA insecure.

Let N1 = p1q1 and N2 = p2q2 be two RSA moduli, not necessarily of the same bit-size. In 2009, May and Ritzenhofen proposed a method to factor N1 and N2 given the implicit information that p1 and p2 share an amount of least significant bits. In this paper, we propose a generalization of their attack as follows: suppose that some unknown multiples a1p1 and a2p2 of the prime factors p1 and p2 share an amount of their Most Significant Bits (MSBs) or an amount of their Least Significant Bits (LSBs). Using a method based on the continued fraction algorithm, we propose a method that leads to the factorization of N1 and N2. Using simultaneous diophantine approximations and lattice reduction, we extend the method to factor k >= 3 RSA moduli Ni = piqi, i = 1, . . . , k given the implicit information that there exist unknown multiples a1p1, . . . , akpk sharing an amount of their MSBs or their LSBs. Also, this paper extends many previous works where similar results were obtained when the pi's share their MSBs or their LSBs.

We introduce new constructions of systematic authentication codes over finite fields and Galois rings. One code is built over finite fields using resilient functions and it provides optimal impersonation and substitution probabilities. Other two proposed codes are defined over Galois rings, one is based on resilient maps and it attains optimal probabilities as well, while the other uses maps whose Fourier transforms get higher values. Being the finite fields special cases of Galois rings, the first code introduced for Galois rings apply also at finite fields. For the special case of characteristic $p^2$, the maps used at the second case in Galois rings are bent indeed, and this case is subsumed by our current general construction of characteristic $p^s$, with $s\geq 2$.

We consider reputation systems where users are allowed to rate products that they purchased previously. To obtain trustworthy reputations, they are allowed to rate these products only once. As long as they do so, the users stay anonymous. Everybody is able to detect users deviating from the rate-products-only-once policy and the anonymity of such dishonest users can be revoked by a system manager. In this paper we present formal models for such reputation systems and their security. Based on group signatures we design an efficient reputation system that meets all our requirements.

Given a lattice $L\subset\R^n$ and some target vector, this paper studies the algorithms for approximate closest vector problem (CVP$_\gamma$) by using an approximate shortest independent vectors problem oracle (SIVP$_\gamma$). More precisely, if the distance between the target vector and the lattice is no larger than $\frac{c}{\gamma n}\lambda_1(L)$ for any constant $c>0$, we give randomized and deterministic polynomial time algorithms to find a closest vector, which improves the known result by a factor of $2c$. Moreover, if the distance between the target vector and the lattice is larger than some quantity with respect to $\lambda_n(L)$, using $\SIVP_\gamma$ oracle and Babai's nearest plane algorithm, we can solve $\CVP_{\gamma\sqrt{n}}$ in deterministic polynomial time. Specially, if the approximate factor $\gamma\in(1,2)$ in the $\SIVP_\gamma$ oracle, we obtain a better reduction factor for CVP.

This article presents a secure mutual testing strategy for System-on-Chips (SoCs) that implement cryptographic functionalities. Such approach eliminates the need for an additional trusted component that is used to test security sensitive cores in a SoC, like symmetric and public-key cryptographic modules. We combine two test approaches: Logic Built In Self Test (BIST) and secure scan-chain based testing and develop a strategy that preserves the test quality of the standard test methods, enhancing security of the testing scheme. In order to minimize the area overhead of the presented solution, we re-use the existing modules in different manners: a public-key cryptographic core to build the BIST infrastructure and a symmetric one to authenticate a device under test to a test server, thus preventing an unauthorized user from accessing the test interface. By doing so, we achieve both testability and security at the minimal cost.

Several fault attacks against pairing-based cryptography have been described theoretically in recent years. Interestingly, none of these have been practically evaluated. We accomplished this task and prove that fault attacks against pairing-based cryptography are indeed possible and are even practical — thus posing a serious threat. Moreover, we successfully conducted a second-order fault attack against an open source implementation of the eta pairing on an AVR XMEGA A1. We injected the first fault into the computation of the Miller Algorithm and applied the second fault to skip the final exponentiation completely. We introduce a low-cost setup that allowed us to generate multiple independent faults in one computation. The setup implements these faults by clock glitches which induce instruction skips. With this setup we conducted the first practical fault attack against a complete pairing computation.

In this paper, we propose a novel technique, called multi-output filtering model, to study the non-randomness property of a cryptographic algorithm such as message authentication codes and block ciphers. A multi-output filtering model consists of a linear feedback shift register (LFSR) and a multi-output filtering function. Our contribution in this paper is twofold. First, we propose an attack technique under IND-CPA using the multi-output filtering model. By introducing a distinguishing function, we theoretically determine the success rate of this attack. In particular, we construct a distinguishing function based on the distribution of the linear complexity of component sequences, and apply it on studying $\T$'s $f_1$ algorithm, $\AES$, $\Kasumi$ and $\Present$. We demonstrate that the success rate of the attack on $\Kasumi$ and $\Present$ is non-negligible, but $f_1$ and $\AES$ are resistant to this attack. Second, we study the distribution of the cryptographic properties of component functions of a random primitive in the multi-output filtering model. Our experiments show some non-randomness in the distribution of algebraic degree and nonlinearity for $\Kasumi$.

This paper presents a standard-cell-based semi-automatic design methodology of a new conceptual countermeasure against electromagnetic (EM) analysis and fault-injection attacks. The countermeasure namely EM attack sensor utilizes LC oscillators which detect variations in the EM field around a cryptographic LSI caused by a micro probe brought near the LSI. A dual-coil sensor architecture with an LUT-programming-based digital calibration can prevent a variety of microprobe-based EM attacks that cannot be thwarted by conventional countermeasures. All components of the sensor core are semi-automatically designed by standard EDA tools with a fully-digital standard cell library and hence minimum design cost. This sensor can be therefore scaled together with the cryptographic LSI to be protected. The sensor prototype is designed based on the proposed methodology together with a 128bit-key composite AES processor in 0.18um CMOS with overheads of only 1.9% in area, 7.6% in power, and 0.2% in performance, respectively. The validity against a variety of EM attack scenarios has been verified successfully.

This paper presents a highly optimized architecture for Advanced Encryption Standard (AES) by dividing and merging (combining) different sub operations in AES algorithm. The proposed architecture uses ten levels of pipelining to achieve higher throughput and uses Block-RAM utility to reduce slice utilization which subsequently increases the efficiency. It achieves the data stream of 57 Gbps at 451 MHz working frequency and obtains 36% improvement in efficiency to the best known similar design throughput per area (Throughput/Area) and 35% smaller in slice area. This architecture can easily be embedded with other modules because of significantly reduced slice utilization.

Secure computation on encrypted data stored on untrusted clouds is an important goal. Existing secure arithmetic computation techniques, such as fully homomorphic encryption (FHE) and somewhat homomorphic encryption (SWH), have prohibitive performance and/or storage costs for the majority of practical applications. In this work, we investigate a new secure arithmetic computation primitive called switchable homomorphic encryption (SHE) that securely switches between existing inexpensive partially homomorphic encryption techniques to evaluate arbitrary arithmetic circuits over integers. SHE is suited for use in a two-cloud model that is practical, but which makes stronger assumptions than the standard single-cloud server model. The security of our SHE solution relies on two non-colluding parties, in which security holds as long as one of them is honest. We benchmark SHE directly against existing secure arithmetic computation techniques---FHE and SWH---on real clouds (Amazon and Rackspace) using microbenchmarks involving fundamental operations utilized in many privacy-preserving computation applications. Experimentally, we find that SHE offers a new design point for computing on large data---it has reasonable ciphertext and key sizes, and is consistently faster by several (2--3) orders of magnitude compared to FHE and SWH on circuits involving long chain of multiplications. SHE exhibits slower performance only in certain cases, when batch (or parallel) homomorphic evaluation is possible, only against SWH schemes (which have limited expressiveness and potentially high ciphertext and key storage costs).

Near Field Communication (NFC) is one the most recent technologies in the area of application development and service delivery via mobile phone. NFC enables the mobile phone to act as identification and a credit card for customers. Dynamic relationships of NFC ecosystem players in an NFC transaction process make them partners in a way that sometimes they should share their access permissions on the applications that are running in the service environment. One of the technologies that can be used to ensure secure NFC transactions is cloud computing which offers wide range advantages compare to the use of a Secure Element (SE) as a single entity in an NFC enabled mobile phone. In this paper, we propose a protocol based on the concept of NFC mobile payments. Accordingly, we present an extended version of the NFC cloud Wallet model [14], in which, the Secure Element in the mobile device is used for customer authentication whereas the customer's banking credentials are stored in a cloud under the control of the Mobile Network Operator (MNO). In this circumstance, Mobile Network Operator plays the role of network carrier which is responsible for controlling all the credentials transferred to the end user. The proposed protocol eliminates the requirement of a shared secret between the Point-of-Sale (POS) and the Mobile Network Operator before execution of the protocol, a mandatory requirement in the earlier version of this protocol [16]. This makes it more practicable and user friendly. At the end, we provide a detailed analysis of the protocol where we discuss multiple attack scenarios.

We extend the notion of verifiable random functions (VRF) to constrained VRFs, which generalize the concept of constrained pseudorandom functions, put forward by Boneh and Waters (Asiacrypt'13), and independently by Kiayias et al. (CCS'13) and Boyle et al. (PKC'14), who call them delegatable PRFs and functional PRFs, respectively. In a standard VRF the secret key $\sk$ allows one to evaluate a pseudorandom function at any point of its domain; in addition, it enables computation of a non-interactive proof that the function value was computed correctly. In a constrained VRF from the key $\sk$ one can derive constrained keys $\sk_S$ for subsets $S$ of the domain, which allow computation of function values and proofs only at points in $S$. After formally defining constrained VRFs, we derive instantiations from the multilinear-maps-based constrained PRFs by Boneh and Waters, yielding a VRF with constrained keys for any set that can be decided by a polynomial-size circuit. Our VRFs have the same function values as the Boneh-Waters PRFs and are proved secure under the same hardness assumption, showing that verifiability comes at no cost. Constrained (functional) VRFs were stated as an open problem by Boyle et al.

Nonlinear feedback shift registers (NFSRs) are an important building block for stream ciphers. Given a cascade connection of two NFSRs, say NFSR$(f,g)$, it has been known for decades how to solve the characteristic function of the NFSR which is equivalent to NFSR$(f,g)$. However, the converse problem of decomposing an NFSR into a cascade connection of two smaller NFSRs is not completely solved, and only a special case has been studied recently. In this paper, a complete and feasible solution to the problem is given.

In his seminal paper at STOC 2009, Gentry left it as a future work to investigate (somewhat) homomorphic encryption schemes with IND-CCA1 security. At SAC 2011, Loftus et al. showed an IND-CCA1 attack against the somewhat homomorphic encryption scheme presented by Gentry and Halevi at Eurocrypt 2011. At ISPEC 2012, Zhang, Plantard and Susilo showed an IND-CCA1 attack against the somewhat homomorphic encryption scheme developed by van Dijk et al. at Eurocrypt 2010. In this paper, we continue this line of research and show that most existing somewhat homomorphic encryption schemes are not IND-CCA1 secure. In fact, we show that these schemes suffer from key recovery attacks (stronger than a typical IND-CCA1 attack), which allow an adversary to recover the private keys through a number of decryption oracle queries. The schemes, that we study in detail, include those by Brakerski and Vaikuntanathan at Crypto 2011 and FOCS 2011, and that by Gentry, Sahai and Waters at Crypto 2013. We also develop a key recovery attack that applies to the somewhat homomorphic encryption scheme by van Dijk et al., and our attack is more efficient and conceptually simpler than the one developed by Zhang et al.. Our key recovery attacks also apply to the scheme by Brakerski, Gentry and Vaikuntanathan at ITCS 2012, and we also describe a key recovery attack for the scheme developed by Brakerski at Crypto 2012.

This work presents the first differential power analysis of an implementation of the McEliece cryptosystem. Target of this side-channel attack is a state-of-the-art FPGA implementation of the efficient QC-MDPC McEliece decryption operation as presented at DATE 2014. The presented cryptanalysis succeeds to recover the complete secret key after a few observed decryptions. It consists of a combination of a differential leakage analysis during the syndrome computation followed by an algebraic step that exploits the relation between the public and private key.

The notion of indifferentiability, which is a stronger version of the classic notion of indistinguishability, was introduced by Maurer, Renner, and Holenstein in 2003. Indifferentiability, among other things, gives us a way of ``securely replacing" a random oracle of one type by a random oracle of a different type. Most indifferentiability proofs in the literature are very complicated, which makes them difficult to verify and in some cases, has even resulted in them being erroneous. In this paper, we use a simple yet rigorous proof technique for proving indifferentiability theorems. This technique is a generalization of the indistinguishability proof technique used by Bernstein in to prove the security of the Cipher Block Chaining (CBC) construction. We use this technique to prove the indifferentiability result for a very simple construction which processes just two blocks of input. This construction can be viewed as bearing close resemblance to the so called Sponge construction, on which the winner of SHA-3 competition is based. Also as a warm up, we prove the indistinguishability result for this construction using the coupling argument from probability theory. We also prove the non-indifferentiability result for the CBC construction and some of its standard variants, and survey the indifferentiability and non-indifferentiability results for the Merkle-Damgård (MD) construction, some of its standard variants, and the Feistel construction, from the literature.

Physical Unclonable Functions (PUFs) have emerged as a promising solution for securing resource-constrained embedded devices such as RFID-tokens. PUFs use the inherent physical differences of every chip to either securely authenticate the chip or generate cryptographic keys without the need of non-volatile memory. Securing non-volatile memory and cryptographic algorithms against hardware attacks is very costly and hence PUFs are believed to be a good alternative to traditional cryptographic algorithms and key generation on constrained embedded devices. However, PUFs have shown to be vulnerable to model building attacks if the attacker has access to challenge and response pairs. In these model building attacks, machine learning is used to determine the internal parameters of the PUF to build an accurate software model. Nevertheless, PUFs are still a promising building block and several protocols and designs have been proposed that are believed to be resistant against machine learning attacks. In this paper we take a closer look at a two such protocols, one based on reverse fuzzy extractors[15] and one based on pattern matching [15,17]. We show that it is possible to attack these protocols using machine learning despite the fact that an attacker does not have access to direct challenge and response pairs. The introduced attacks demonstrate that even highly obfuscated responses or helper data can be used to attack PUF protocols. Hence, our work shows that even protocols in which it would be computationally infeasible to compute enough challenge and response pairs for a direct machine learning attack can be attacked using machine learning.

The wide availability of inexpensive positioning systems made it possible to embed them into smartphones and other personal devices. This marked the beginning of location-aware applications, where users request personalized services based on their geographic position. The location of a user is, however, highly sensitive information: the user's privacy can be preserved if only the minimum amount of information needed to provide the service is disclosed at any time. While some applications, such as navigation systems, are based on the users' movements and therefore require constant tracking, others only require knowledge of the user's position in relation to a set of points or areas of interest. In this paper we focus on the latter kind of services, where the location information is essentially used to determine membership in one or more geographic sets. We address this problem using Bloom Filters (BF), a compact data structure for representing sets. In particular, we present an extension of the original bloom filter idea: the Spatial Bloom Filter (SBF). SBF's are designed to manage spatial and geographical information in a space efficient way, and are well-suited for enabling privacy in location-aware applications. We show this by providing two multi-party protocols for privacy-preserving computation of location information, based on the known homomorphic properties of public key encryption schemes. The protocols keep the user's exact position private, but allow the provider of the service to learn when the user is close to specific points of interest, or inside predefined areas. At the same time, the points and areas of interest remain oblivious to the user.

In this article, we propose a new comparison metric, the figure of adversarial merit (FOAM), which combines the inherent security provided by cryptographic structures and components with their implementation properties. To the best of our knowledge, this is the first such metric proposed to ensure a fairer comparison of cryptographic designs. We then apply this new metric to meaningful use cases by studying Substitution-Permutation Network permutations that are suited for hardware implementations, and we provide new results on hardware-friendly cryptographic building blocks. For practical reasons, we considered linear and differential attacks and we restricted ourselves to fully serial and round-based implementations. We explore several design strategies, from the geometry of the internal state to the size of the S-box, the field size of the diffusion layer or even the irreducible polynomial defining the finite field. We finally test all possible strategies to provide designers an exhaustive approach in building hardware-friendly cryptographic primitives (according to area or FOAM metrics), also introducing a model for predicting the hardware performance of round-based or serial-based implementations. In particular, we exhibit new diffusion matrices (circulant or serial) that are surprisingly more efficient than the current best known, such as the ones used in AES, LED and PHOTON.

We investigate new models and constructions which allow leakage-resilient signatures secure against existential forgeries, where the signature is much shorter than the leakage bound. Current models of leakage-resilient signatures against existential forgeries demand that the adversary cannot produce a new valid message/signature pair $(m, \sigma)$ even after receiving some $\lambda$ bits of leakage on the signing key. If $\vert \sigma \vert \le \lambda$, then the adversary can just choose to leak a valid signature $\sigma$, and hence signatures must be larger than the allowed leakage, which is impractical as the goal often is to have large signing keys to allow a lot of leakage. We propose a new notion of leakage-resilient signatures against existential forgeries where we demand that the adversary cannot produce $n = \lfloor \lambda / \vert \sigma \vert \rfloor + 1$ distinct valid message/signature pairs $(m_1, \sigma_1), \ldots, (m_n, \sigma_n)$ after receiving $\lambda$ bits of leakage. If $\lambda = 0$, this is the usual notion of existential unforgeability. If $1 < \lambda < \vert \sigma \vert$, this is essentially the usual notion of existential unforgeability in the presence of leakage. In addition, for $\lambda \ge \vert \sigma \vert$ our new notion still guarantees the best possible, namely that the adversary cannot produce more forgeries than he could have leaked, hence graceful degradation. Besides the game-based notion hinted above, we also consider a variant which is more simulation-based, in that it asks that from the leakage a simulator can ``extract'' a set of $n-1$ messages (to be thought of as the messages corresponding to the leaked signatures), and no adversary can produce forgeries not in this small set. The game-based notion is easier to prove for a concrete instantiation of a signature scheme. The simulation-based notion is easier to use, when leakage-resilient signatures are used as components in larger protocols. We prove that the two notion are equivalent and present a generic construction of signature schemes meeting our new notion and a concrete instantiation under fairly standard assumptions. We further give an application, to leakage-resilient identification.

A presentation of a group with two generators having unsolvable word problem and an explicit countable presentation of Mihailova subgroup of F_2×F_2 with finite number of generators are given. Where Mihailova subgroup of F_2×F_2 enjoys the unsolvable subgroup membership problem.One then can use the presentation to create entities' private key in a public key cryptsystem.

We find mathematically optimal side-channel distinguishers by looking at the side-channel as a communication channel. Our methodology can be adapted to any given scenario (device, signal-to-noise ratio, noise distribution, leakage model, etc.). When the model is known and the noise is Gaussian, the optimal distinguisher outperforms CPA and covariance. However, we show that CPA is optimal when the model is only known on a proportional scale. For non-Gaussian noise, we obtain different optimal distinguishers, one for each noise distribution. When the model is imperfectly known, we consider the scenario of a weighted sum of the sensitive variable bits where the weights are unknown and drawn from a normal law. In this case, our optimal distinguisher performs better than the classical linear regression analysis.

This paper introduces constant-time ARM Cortex-A8 ECDH software that (1) is faster than the fastest ECDH option in the latest version of OpenSSL but (2) achieves a security level above 2^200 using a prime above 2^400. For comparison, this OpenSSL ECDH option is not constant-time and has a security level of only 2^80. The new speeds are achieved in a quite different way from typical prime-field ECC software: they rely on a synergy between Karatsuba's method and choices of radix smaller than the CPU word size.

The lightweight block cipher PRIDE designed by Albrecht et al., appears in CRYPTO 2014. The designers claim that their method of constructing linear layer is good both in security and efficiency. In this paper, we find 16 different 2-round iterative characteristics utilizing the weaknesses of S-box and linear layer, construct several 15-round differentials. Based on one of the differentials, we launch differential attack on 18-round PRIDE. The data, time and memory complexity are $2^{60}$, $2^{66}$ and $2^{64}$, respectively.

Hyper-bent functions as a subclass of bent functions attract much interest and it is elusive to completely characterize hyper-bent functions. Most of known hyper-bent functions are Boolean functions with Dillon exponents and they are often characterized by special values of Kloosterman sums. In this paper, we present a method for characterizing hyper-bent functions with Dillon exponents. A class of hyper-bent functions with Dillon exponents over $\mathbb{F}_{2^{2m}}$ can be characterized by a Boolean function over $\mathbb{F}_{2^m}$, whose Walsh spectrum takes the same value twice. Further, we show several classes of hyper-bent functions with Dillon exponents characterized by Kloosterman sum identities and the Walsh spectra of some common Boolean functions.

In this work we explore new techniques for building short signatures from obfuscation. Our goals are twofold. First, we would like to achieve short signatures with adaptive security proofs. Second, we would like to build signatures with fast signing, ideally significantly faster than comparable signatures that are not based on obfuscation. The goal here is to create an "imbalanced" scheme where signing is fast at the expense of slower verification. We develop new methods for achieving short and fully secure obfuscation-derived signatures. Our base signature scheme is built from punctured programming and makes a novel use of the "prefix technique" to guess a signature. We find that our initial scheme has slower performance than comparable algorithms (e.g. EC-DSA). We find that the underlying reason is that the underlying PRG is called l^2 times for security parameter l. To address this issue we construct a more efficient scheme by adapting the Goldreich-Goldwasser-Micali [GGM86] construction to form the basis for a new puncturable PRF. This puncturable PRF accepts variable-length inputs and has the property that evaluations on all prefixes of a message can be efficiently pipelined. Calls to the puncturable PRF by the signing algorithm therefore make fewer invocations of the underlying PRG, resulting in reduced signing costs. We evaluate our puncturable PRF based signature schemes using a variety of cryptographic candidates for the underlying PRG. We show that the resulting performance on message signing is competitive with that of widely deployed signature schemes.

Constrained pseudorandom functions (introduced independently by Boneh and Waters (CCS 2013), Boyle, Goldwasser, and Ivan (PKC 2014), and Kiayias, Papadopoulos, Triandopoulos, and Zacharias (CCS 2013)), are pseudorandom functions (PRFs) that allow the owner of the secret key $k$ to compute a constrained key $k_f$, such that anyone who possesses $k_f$ can compute the output of the PRF on any input $x$ such that $f(x) = 1$ for some predicate $f$. The security requirement of constrained PRFs state that the PRF output must still look indistinguishable from random for any $x$ such that $f(x) = 0$. Boneh and Waters show how to construct constrained PRFs for the class of bit-fixing as well as circuit predicates. They explicitly left open the question of constructing constrained PRFs that are delegatable - i.e., constrained PRFs where the owner of $k_f$ can compute a constrained key $k_{f'}$ for a further restrictive predicate $f'$. Boyle, Goldwasser, and Ivan left open the question of constructing constrained PRFs that are also verifiable. Verifiable random functions (VRFs), introduced by Micali, Rabin, and Vadhan (FOCS 1999), are PRFs that allow the owner of the secret key $k$ to prove, for any input $x$, that $y$ indeed is the output of the PRF on $x$; the security requirement of VRFs state that the PRF output must still look indistinguishable from random, for any $x$ for which a proof is not given. In this work, we solve both the above open questions by constructing constrained pseudorandom functions that are simultaneously verifiable and delegatable.

We study the adaptive security of constrained PRFs in the standard model. We initiate our exploration with puncturable PRFs. A puncturable PRF family is a special class of constrained PRFs, where the constrained key is associated with an element $x'$ in the input domain. The key allows evaluation at all points $x\neq x'$. We show how to build puncturable PRFs with adaptive security proofs in the standard model that involve only polynomial loss to the underlying assumptions. Prior work had either super-polynomial loss or applied the random oracle heuristic. Our construction uses indistinguishability obfuscation and DDH-hard algebraic groups of composite order.

Given a linear code $C$, one can define the $d$-th power of $C$ as the span of all componentwise products of $d$ elements of $C$. A power of $C$ may quickly fill the whole space. Our purpose is to answer the following question: does the square of a code ``typically'' fill the whole space? We give a positive answer, for codes of dimension $k$ and length roughly $\frac{1}{2}k^2$ or smaller. Moreover, the convergence speed is exponential if the difference $k(k+1)/2-n$ is at least linear in $k$. The proof uses random coding and combinatorial arguments, together with algebraic tools involving the precise computation of the number of quadratic forms of a given rank, and the number of their zeros.

In 2011 Stajano proposed Pico, a secure and easy-to-use alternative for passwords. Among the many proposals in this category, Pico stands out by being creative and convincing. However, the description as published leaves some details unspecified, and to the best of our knowledge the complete system has not yet been tested. This work presents detailed specifications and future-proof security protocols for Pico. Moreover, we present the first robust and efficient Pico implementation. Our implementation allows to further mature the Pico concept and can be used for large scale usability evaluations at negligible cost.

This paper suggests and explores the use of UCE security for the task of turning VIL-ROM schemes into FIL-ROM ones. The benefits we offer over indifferentiability, the current leading method for this task, are the ability to handle multi-stage games and greater efficiency. The paradigm consists of (1) Showing that a VIL UCE function can instantiate the VIL RO in the scheme, and (2) Constructing the VIL UCE function given a FIL random oracle. The main technical contributions of the paper are domain extension transforms that implement the second step. Leveraging known results for the first step we automatically obtain FIL-ROM constructions for several primitives whose security notions are underlain by multi-stage games. Our first domain extender exploits indifferentiability, showing that although the latter does not work directly for multi-stage games it can be used indirectly, through UCE, as a tool for this end. Our second domain extender targets performance. It is parallelizable and shown through implementation to provide significant performance gains over indifferentiable domain extenders.

We revisit the context of leakage-tolerant interactive protocols as defined by Bitanski, Canetti and Halevi (TCC 2012). Our contributions can be summarized as follows: \begin{itemize} \item For the purpose of secure message transmission, any encryption protocol with message space $\cM$ and secret key space $\cSK$ tolerating poly-logarithmic leakage on the secret state of the receiver must satisfy $|\cSK| \ge (1-\epsilon)|\cM|$, for every $0 < \epsilon \le 1$, and if $|\cSK| = |\cM|$, then the scheme must use a fresh key pair to encrypt each message. \item More generally, we show that any $n$ party protocol tolerates leakage of $\approx\poly(\log\spar)$ bits from one party at the end of the protocol execution, \emph{if and only if} the protocol has passive adaptive security against an adaptive corruption of one party at the end of the protocol execution. This shows that as soon as a little leakage is tolerated, one needs full adaptive security. \end{itemize} All our results can be based on the only assumption that collision-resistant function ensembles exist.

Two parties, $P_1$ and $P_2$, wish to jointly compute some function $f(x,y)$ where $P_1$ only knows $x$, whereas $P_2$ only knows $y$. Furthermore, and most importantly, the parties wish to reveal only what the output suggests. Function $f$ is said to be computable with \emph{complete fairness} if there exists a protocol computing $f$ such that whenever one of the parties obtains the correct output, then both of them do. The only protocol known to compute functions with complete fairness is the one of Gordon et al (STOC 2008). The functions in question are finite, Boolean, and the output is shared by both parties. The classification of such functions up to fairness may be a first step towards the classification of all functionalities up to fairness. Recently, Asharov (TCC 2014) identifies two families of functions that are computable with fairness using the protocol of Gordon et al and another family for which the protocol (potentially) falls short. Surprisingly, these families account for almost all finite Boolean functions. In this paper, we expand our understanding of what can be computed fairly with the protocol of Gordon et al. In particular, we fully describe which functions the protocol computes fairly and which it (potentially) does not. Furthermore, we present a new class of functions for which fair computation is outright impossible. Finally, we confirm and expand Asharov's observation regarding the fairness of finite Boolean functions: almost all functions $f:X\times Y\rightarrow \{0,1\}$ for which $|X|\neq |Y|$ are fair, whereas almost all functions for which $|X|= |Y|$ are not.

Ideal Social Secret Sharing Using Birkhoff Interpolation Method

Most lattice-based cryptographic schemes with a security proof suffer from large key sizes and heavy computations. This is also true for the simpler case of authentication protocols which are used on smart cards, as a very-constrained computing environment. Recent progress on ideal lattices has significantly improved the efficiency, and made it possible to implement practical lattice-based cryptography on constrained devices. However, to the best of our knowledge, no previous attempts were made to implement lattice-based schemes on smart cards. In this paper, we provide the results of our implementation of several state-of-the-art lattice-based authentication protocols on smart cards and a microcontroller widely used in smart cards. Our results show that only a few of the proposed lattice-based authentication protocols can be implemented using limited resources of such constrained devices, however, cutting-edge ones are suitably efficient to be used practically on smart cards. Moreover, we have implemented fast Fourier transform (FFT) and discrete Gaussian sampling with different typical parameter sets, as well as versatile lattice-based public-key encryptions. These results have noticeable points which help to design or optimize lattice-based schemes for constrained devices.

We discuss how to recover RSA secret keys from noisy analog data obtained through physical attacks such as cold boot and side channel attacks. Many studies have focused on recovering correct secret keys from noisy binary data. Obtaining noisy binary keys typically involves first observing the analog data and then obtaining the binary data through quantization process that discards much information pertaining to the correct keys. In this paper, we propose two algorithms for recovering correct secret keys from noisy analog data, which are generalized variants of Paterson et al.'s algorithm. Our algorithms fully exploit the analog information. More precisely, consider observed data which follows the Gaussian distribution with mean $(-1)^b$ and variance $\sigma^2$ for a secret key bit $b$. We propose a polynomial time algorithm based on the maximum likelihood approach and show that it can recover secret keys if $\sigma < 1.767$. The first algorithm works only if the noise distribution is explicitly known. The second algorithm does not need to know the explicit form of the noise distribution. We implement the first algorithm and verify its effectiveness.

Secure multi-party computation platforms are becoming more and more practical. This has paved the way for privacy-preserving statistical analysis using secure multi-party computation. Simple statistical analysis functions have been emerging here and there in literature, but no comprehensive system has been compiled. We describe and implement the most used statistical analysis functions in the privacy-preserving setting including simple statistics, t-test, $\chi^{2}$ test, Wilcoxon tests and linear regression. We give descriptions of the privacy-preserving algorithms and benchmark results that show the feasibility of our solution.

We present a new transformation of chosen-plaintext secure predicate encryption schemes with public index into chosen-ciphertext secure schemes. Our construction requires only a universal one-way hash function and is selectively secure in the standard model. The transformation is not generic but can be applied to various existing schemes constructed from bilinear groups. Using common structural properties of these schemes we provide an efficient and simple transformation without overhead in form of one-time signatures or message authentication codes as required in the known generic transformations.

In 2005, Hell, Johansson and Meier submitted a stream cipher proposal named Grain v1 to the estream call for stream cipher proposals and it also became one estream nalists in the hardware category. The output function of Grain v1 connects its 160 bits internal state divided equally between an LFSR and an NFSR, using a non-linear lter function in a complex way. Over the last years many cryptanalyst identied several weaknesses in Grain v1. As a result in 2011 the inventors modied Grain v1 and published a new version of Grain named Grain-128a which has a similar structure as Grain v1 but with a 256 bits internal state with an optional authentication is the latest version of Grain family resisting all known attacks on Grain v1. However both these ciphers are quite resistant against the classical algebraic attack due to the rapid growth of the degree of the key-stream equations in subsequent clockings caused by the NFSR. This paper presents a probabilistic algebraic attack on both these Grain versions. The basic idea of our attack is to develop separate probabilistic equations for the LFSR and the NFSR bits from each key-stream equations. Surprisingly it turns out that in case of Grain-128a our proposed equations hold with all most sure probability, which makes the sure retrieval of the LFSR bits. We also outline a technique to reduce the growth of degree of the equations involving the NFSR bits for Grain v1. Further we high light that the concept of probabilistic algebraic attack as proposed in this paper can be considered as a generic attack strategy against any stream cipher having similar structure of the output function as in case of the Grain family.

In this paper, we address the problem of privacy preserving delegated word search in the cloud. We consider a scenario where a data owner outsources its data to a cloud server and delegates the search capabilities to a set of third party users. In the face of semi-honest cloud servers, the data owner does not want to disclose any information about the outsourced data; yet it still wants to benefit from the highly parallel cloud environment. In addition, the data owner wants to ensure that delegating the search functionality to third parties does not allow these third parties to jeopardize the confidentiality of the outsourced data, neither does it prevent the data owner from efficiently revoking the access of these authorized parties. To these ends, we propose a word search protocol that builds upon techniques of keyed hash functions, oblivious pseudo-random functions and Cuckoo hashing to construct a searchable index for the outsourced data, and uses private information retrieval of short information to guarantee that word search queries do not reveal any information about the data to the cloud server. Moreover, we combine attribute-based encryption and oblivious pseudo-random functions to achieve an efficient revocation of authorized third parties. The proposed scheme is suitable for the cloud as it can be easily parallelized.

A successful detection of the stealthy dopant-level circuit (trojan), proposed by Becker et al. at CHES 2013, is reported. Contrary to an assumption made by Becker et al., dopant types in active region are visible with either scanning electron microscopy (SEM) or focused ion beam (FIB) imaging. The successful measurement is explained by an LSI failure analysis technique called the passive voltage contrast. The experiments are conducted by measuring a dedicated chip. The chip uses the diffusion programmable device: an anti-reverse-engineering technique by the same principle as the stealthy dopant-level trojan. The chip is delayered down to the contact layer, and images are taken with (1) an optical microscope, (2) SEM, and (3) FIB. As a result, the four possible dopant-well combinations, namely (i) p+/n-well, (ii) p+/p-well, (iii) n+/n-well and (iv) n+/p-well are distinguishable in the SEM images. Partial but sufficient detection is also achieved with FIB. Although the stealthy dopant-level circuits are visible, however, they potentially make a detection harder. That is because the contact layer should be measured. We show that imaging the contact layer is at most 16-times expensive than that of a metal layer in terms of the number of images

The random oracle is an idealization that allows us to model a hash function as an oracle that will output a uniformly random string given any input. We introduce the notion of a universal sampler scheme that extends the notion of a random oracle, to a method of sampling securely from arbitrary distributions. We describe several applications that provide a natural motivation for this notion; these include generating the trusted parameters for many schemes from just a single trusted setup. We further demonstrate the versatility of universal samplers by showing how they give rise to simple constructions of identity-based encryption and multiparty key exchange. In particular, we construct adaptively secure non-interactive multiparty key exchange in the random oracle model based on indistinguishability obfuscation; obtaining the first known construction of adaptively secure NIKE without complexity leveraging. We give a solution that shows how to transform any random oracle into a universal sampler scheme, based on indistinguishability obfuscation. At the heart of our construction and proof is a new technique we call “delayed backdoor programming” that we believe will have other applications.

The problem of solving polynomial equations over finite fields has many applications in cryptography and coding theory. In this paper, we consider polynomial equations over a ``large'' finite field with a ``small'' characteristic. We introduce a new algorithm for solving this type of equations, called the \emph{Successive Resultants Algorithm} (SRA) in the sequel. SRA is radically different from previous algorithms for this problem, yet it is conceptually simple. A straightforward implementation using Magma was able to beat the built-in function \emph{Roots} for some parameters. These preliminary results encourage a more detailed study of SRA and its applications. Moreover, we point out that an extension of SRA to the multivariate case would have an importa

Let $\cO$ be a maximal order in a definite quaternion algebra over $\mathbb{Q}$ of prime discriminant $p$, and $\ell$ a small prime. We describe a probabilistic algorithm, which for a given left $\cO$-ideal, computes a representative in its left ideal class of $\ell$-power norm. In practice the algorithm is efficient, and subject to heuristics on expected distributions of primes, runs in expected polynomial time. This breaks the underlying problem for a quaternion analog of the Charles-Goren-Lauter hash function, and has security implications for the original CGL construction in terms of supersingular elliptic curves.

We provide the first provable-security analysis of the Intel Secure Key hardware RNG (ISK-RNG), versions of which have appeared in Intel processors since late 2011. To model the ISK-RNG, we generalize the PRNG-with-inputs primitive, introduced Dodis et al. introduced at CCS'13 for their /dev/[u]random analysis. The concrete security bounds we uncover tell a mixed story. We find that ISK-RNG lacks backward-security altogether, and that the forward-security bound for the ``truly random'' bits fetched by the RDSEED instruction is potentially worrisome. On the other hand, we are able to prove stronger forward-security bounds for the pseudorandom bits fetched by the RDRAND instruction. En route to these results, our main technical efforts focus on the way in which ISK-RNG employs CBCMAC as an entropy extractor.

A Hidden Vector Encryption (HVE) scheme is a special type of anonymous identity-based encryption (IBE) scheme where the attribute string associated with the ciphertext or the user secret key can contain wildcards. In this paper, we introduce two constant-size ciphertext-policy hidden vector encryption (CP-HVE) schemes. Our first scheme is constructed on composite order bilinear groups, while the second one is built on prime order bilinear groups. Both schemes are proven secure in a selective security model which captures plaintext (or payload) and attribute hiding. To the best of our knowledge, our schemes are the first HVE constructions that can achieve constant-size ciphertext among all the existing HVE schemes.

Over the past few years, online service providers have started gathering increasing amounts of personal information to build user profiles and monetize them with advertisers and data brokers. Users have little control of what information is processed and are often left with an all-or-nothing decision between receiving free services or refusing to be profiled. This paper explores an alternative approach where users only disclose an aggregate model -- the ``gist'' -- of their data. We aim to preserve data utility and simultaneously provide user privacy. We show that this approach can be efficiently supported by letting users contribute encrypted and differentially-private data to an aggregator. The aggregator combines encrypted contributions and can only extract an aggregate model of the underlying data. We evaluate our framework on a dataset of 100,000 U.S. users obtained from the U.S. Census Bureau and show that (i) it provides accurate aggregates with as little as 100 users, (ii) it generates revenue for both users and data brokers, and (iii) its overhead is appreciably low.

WHIRLBOB, also known as STRIBOBr2, is an AEAD (Authenticated Encryption with Associated Data) algorithm derived from STRIBOBr1 and the Whirlpool hash algorithm. WHIRLBOB/STRIBOBr2 is a second round candidate in the CAESAR competition. As with STRIBOBr1, the reduced-size Sponge design has a strong provable security link with a standardized hash algorithm. The new design utilizes only the LPS or $\rho$ component of Whirlpool in flexibly domain-separated BLNK Sponge mode. The number of rounds is increased from 10 to 12 as a countermeasure against Rebound Distinguishing attacks. The $8 \times 8$ - bit S-Box used by Whirlpool and WHIRLBOB is constructed from $4 \times 4$ - bit ``MiniBoxes''. We report on fast constant-time Intel SSSE3 and ARM NEON SIMD WHIRLBOB implementations that keep full miniboxes in registers and access them via SIMD shuffles. This is an efficient countermeasure against AES-style cache timing side-channel attacks. Another main advantage of WHIRLBOB over STRIBOBr1 (and most other AEADs) is its greatly reduced implementation footprint on lightweight platforms. On many lower-end microcontrollers the total software footprint of $\pi$+BLNK = WHIRLBOB AEAD is less than half a kilobyte. We also report an FPGA implementation that requires 4,946 logic units for a single round of WHIRLBOB, which compares favorably to 7,972 required for Keccak / Keyak on the same target platform. The relatively small S-Box gate count also enables efficient 64-bit bitsliced straight-line implementations. We finally present some discussion and analysis on the relationships between WHIRLBOB, Whirlpool, the Russian GOST Streebog hash, and the recent draft Russian Encryption Standard Kuznyechik.

Modular exponentiation is one of basic operations among most of current cryptosystems. Under some algebraic assumptions or cryptography assumptions, it can construct outsourcing schemes for modular exponentiations by using two untrusted cloud servers, which cannot resist the collusive attack of two untrusted cloud servers. However, it doesn't exist an efficient outsourcing of modular exponentiations using one untrusted cloud server. In this paper, we present three secure outsourcing schemes using one untrusted cloud server, which can enable user to securely outsource exponentiations to single cloud server. The first one is a secure outsourcing scheme for fixed base-variable exponent modular exponentiations, the second is for variable base-variable exponent modular exponentiations, and the third is a secure outsourcing scheme for simultaneous modular exponentiations. Compared with other proposed schemes, our proposed schemes are superior in both efficiency and checkability. Moreover, our schemes are secure without any cryptographic assumptions. Finally, we give two applications for our outsourcing schemes, one is to construct an outsourcing scheme for Cramer-Shoup encryptions, and the other is to design an outsourcing scheme for Schnorr signatures.

and Patey proposed two cryptographic protocols for the computation of Hamming distance in the two-party setting. Their first scheme uses Oblivious Transfer and provides security in the semi-honest model. The other scheme uses Committed Oblivious Transfer (COT) and is claimed to provide full security in the malicious case. The proposed protocols have direct implications to biometric authentication schemes between a prover and a verifier where the verifier has biometric data of the users in plain form. In this paper, we show that their protocol against malicious adversaries is not actually secure. Namely, we show a generic attack such that a malicious user can compute a Hamming distance which is different from the actual value. For biometric authentication systems, this attack allows a malicious adversary to pass the authentication without knowledge of the honest user's input with at most O(n) complexity instead of O(2^n), where n is the input length. We propose an enhanced version of their protocol where this attack is eliminated. The security of our modified protocol is proved using simulation-based paradigm. Also as for efficiency concerns, the modified protocol utilizes Verifiable Oblivious Transfer (VOT) which excludes the commitments to outputs (as they exist in COT). We show that the use of VOT does not reduce the security of the protocol but improves the efficiency significantly.

The Maximum Distance Separable (MDS) mapping, used in cryptography deploys complex Galois field multiplications, which consume lots of area in hardware, making it a costly primitive for lightweight cryptography. Recently in lightweight hash function: PHOTON, a matrix denoted as ‘Serial’, which required less area for multiplication, has been multiplied 4 times to achieve a lightweight MDS mapping. But no efficient method has been proposed so far to synthesize such a serial matrix or to find the required number of repetitive multiplications needed to be performed for a given MDS mapping. In this paper, first we provide an generic algorithm to find out a low-cost matrix, which can be multiplied k times to obtain a given MDS mapping. Further, we optimize the algorithm for using in cryptography and show an explicit case study on the MDS mapping of the hash function PHOTON to obtain the ‘Serial’. The work also presents quite a few results which may be interesting for lightweight implementation.

Hardware implementations of cryptographic algorithms are vulnerable to natural and malicious faults. Concurrent Error Detection (CED) can be used to detect these faults. We present NREPO, a CED which does not require redundant computational resources in the design. Therefore, one can integrate it when computational resources are scarce or when the redundant resources are difficult to harness for CED. We integrate NREPO in a low-cost Advanced Encryption Standard (AES) implementation with 8-bit datapath. We show that NREPO has 25 and 50 times lower fault miss rate than robust code and parity, respectively. The area, throughput, and power are compared with other CEDs on 45nm ASIC. The hardware overhead of NREPO is 34.9%. The throughput and power are 271.6Mbps and 1579.3&#956;W , respectively. One can also implement NREPO in other cryptographic algorithms.

An identity-based multi-proxy signature is a type of proxy signatures in which the delegation of signing right is distributed among a number of proxy signers. In this type of cryptographic primitive, cooperation of all proxy signers in the proxy group generates the proxy signatures of roughly the same size as that of standard proxy signatures on behalf of the original signer, which is more efficient than transmitting individual proxy signatures. Since identity-based multi-proxy signatures are useful in distributed systems, grid computing, presenting a provably secure identity-based multi-proxy scheme is desired. In 2013, Sahu and Padhye proposed the first provably secure identity-based multi-proxy signature scheme in the random oracle model, and proved that their scheme is existential unforgeable against adaptive chosen message and identity attack. Unfortunately, in this paper, we show that their scheme is insecure. We present two forgery attacks on their scheme. Furthermore, their scheme is not resistant against proxy key exposure attack. As a consequence, there is no provably secure identity-based multi-proxy signature scheme secure against proxy key exposure attack to date.

We present a signature scheme provably secure in the standard model (no random oracles) based on the worst-case complexity of approximating the Shortest Vector Problem in ideal lattices within polynomial factors. The distinguishing feature of our scheme is that it achieves short signatures (consisting of a single lattice vector), and relatively short public keys (consisting of O(log n) vectors.) Previous lattice schemes in the standard model with similarly short signatures, due to Boyen (PKC 2010) and Micciancio and Peikert (Eurocrypt 2012), had substantially longer public keys consisting of &Omega;(n) vectors (even when implemented with ideal lattices). We also present a variant of our scheme that further reduces the public key size to just O(log log n) vectors and allows for a tighther security proof by making the signer stateful.

We introduce the k-LWE problem, a Learning With Errors variant of the k-SIS problem. The Boneh-Freeman reduction from SIS to k-SIS suffers from an exponential loss in k. We improve and extend it to an LWE to k-LWE reduction with a polynomial loss in k, by relying on a new technique involving trapdoors for random integer kernel lattices. Based on this hardness result, we present the first algebraic construction of a traitor tracing scheme whose security relies on the worst-case hardness of standard lattice problems. The proposed LWE traitor tracing is almost as efficient as the LWE encryption. Further, it achieves public traceability, i.e., allows the authority to delegate the tracing capability to "untrusted" parties. To this aim, we introduce the notion of projective sampling family in which each sampling function is keyed and, with a projection of the key on a well chosen space, one can simulate the sampling function in a computationally indistinguishable way. The construction of a projective sampling family from k-LWE allows us to achieve public traceability, by publishing the projected keys of the users. We believe that the new lattice tools and the projective sampling family are quite general that they may have applications in other areas.

A Kummer variety is obtained as the quotient of an abelian variety by the automorphism $(-1)$ acting on it. Kummer varieties can be seen as a higher dimensional generalisation of the $x$-coordinate representation of a point of an elliptic curve given by its Weierstrass model. Although there is no group law on the set of points of a Kummer variety, the multiplication of a point by a scalar still makes sense, since it is compatible with the action of $(-1)$, and can efficiently be computed with a Montgomery ladder. In this paper, we explain that the arithmetic of a Kummer variety is not limited to this scalar multiplication and is much richer than usually thought. We describe a set of composition laws which exhaust this arithmetic and explain how to compute them efficiently in the model of Kummer varieties provided by level $2$ theta functions. Moreover, we present concrete example where these laws turn out to be useful in order to improve certain algorithms. As an application interesting for instance in cryptography, we explain how to recover the full group law of the abelian variety with a representation almost as compact and in many cases as efficient as the level $2$ theta functions model of Kummer varieties.

Several papers have studied fault attacks on computing a pairing value e(P,Q), where P is a public point and Q is a secret point. In this paper, we observe that these attacks are in fact effective only on a small number of pairing-based protocols, and that too only when the protocols are implemented with specific symmetric pairings. We demonstrate the effectiveness of the fault attacks on a public-key encryption scheme, an identity-based encryption scheme, and an oblivious transfer protocol when implemented with a symmetric pairing derived from a supersingular elliptic curve with embedding degree 2.

It has been an open problem for a number of years to construct an identity-based fully homomorphic encryption (IBFHE) scheme (first mentioned by Naccache at CHES/CRYPTO 2010). At CRYPTO 2013, Gentry, Sahai and Waters largely settled the problem by presenting leveled IBFHE constructions based on the Learning With Errors problem. However their constructions are not bootstrappable, and as a result, are not ``pure'' IBFHE schemes. The major challenge with bootstrapping in the identity-based setting is that it must be possible to non-interactively derive from the public parameters an ``encryption'' of the secret key for an arbitrary identity. All presently-known leveled IBFHE schemes only allow bootstrapping if such an ``encryption'' of the secret key is supplied out-of-band. In this work, we present a ``pure'' IBFHE scheme from indistinguishability obfuscation, and extend the result to the attribute-based setting. Our attribute-based scheme is the first to support homomorphic evaluation on ciphertexts with different attributes. Finally, we characterize presently-known leveled IBFHE schemes with a view to developing a ``compiler'' from a leveled IBFHE scheme to a bootstrappable IBFHE scheme, and sufficient conditions are identified.

Trusted Network Connect (TNC) requires both user authentication and integrity validation of an endpoint before it connects to the internet or accesses some web service. However, as the user authentication and integrity validation are usually done via independent protocols, TNC is vulnerable to the Man-in-the-Middle (MitM) attack. This paper analyzes TNC which uses keys with Subject Key Attestation Evidence (SKAE) extension to perform user authentication and the IF-T protocol binding to TLS to carry integrity measurement messages in the Universally Composable (UC) framework. Our analysis result shows that TNC using keys with SKAE extension can resist the MitM attack. In this paper, we introduce two primitive ideal functionalities for TNC: an ideal dual-authentication certification functionality which binds messages and both the user and platform identities, and an ideal platform attestation functionality which formalizes the integrity verification of a platform. We prove that the SKAE extension protocol and the basic TCG platform attestation protocol, both of which are defined by TCG specifications, UC-realizes the two primitive functionalities respectively. In the end, we introduce a general ideal TNC functionality and prove that the complete TNC protocol, combining the IF-T binding to TLS which uses keys with SKAE extension for client authentication and the basic TCG platform attestation platform protocol, securely realizes the TNC functionality in the hybrid model.

In this paper, we propose a genetic algorithm for solving the shortest vector problem (SVP) based on sparse integer representations of short vectors in lattices as chromesomes, which, we prove, can guarantee finding the shortest lattice vector under a Markov chain analysis. Moreover, we also suggest some improvements by introducing heuristic techniques: local search and heuristic pruning. The experimental results show that the genetic algorithm outperforms most enumeration algorithms in running time, and achieves the shortest vectors in larger dimensions under SVP challenge benchmarks.

Related-key attacks (RKAs) concern the security of cryptographic primitives in the situation where the key can be manipulated by the adversary. In the RKA setting, the adversary's power is expressed through the class of related-key deriving (\RKD) functions which the adversary is restricted to using when modifying keys. Bellare and Kohno (Eurocrypt 2003) first formalised RKAs and pin-pointed the foundational problem of constructing RKA-secure pseudorandom functions (RKA-PRFs). To date there are few constructions for RKA-PRFs under standard assumptions, and it is a major open problem to construct RKA-PRFs for larger classes of \RKD functions. We make significant progress on this problem. We first show how to repair the Bellare-Cash framework for constructing RKA-PRFs and extend it to handle the more challenging case of classes of \RKD functions that contain claws. We apply this extension to show that a variant of the Naor-Reingold function already considered by Bellare and Cash is an RKA-PRF for a class of affine \RKD functions under the DDH assumption, albeit with an exponential-time security reduction. We then develop a second extension of the Bellare-Cash framework, and use it to show that the same Naor-Reingold variant is actually an RKA-PRF for a class of degree $d$ polynomial \RKD functions under the stronger decisional $d$-Diffie-Hellman inversion assumption. As a significant technical contribution, our proof of this result avoids the exponential-time security reduction that was inherent in the work of Bellare and Cash and in our first result.

The GGH Graded Encoding Scheme, based on ideal lattices, is the first plausible approximation to a cryptographic multilinear map. Unfortunately, using the security analysis in the original paper, the scheme requires very large parameters to provide security for its underlying encoding re-randomization process. Our main contributions are to formalize, simplify and improve the efficiency and the security analysis of the re-randomization process in the GGH construction. This results in a new construction that we call GGHLite. In particular, we first lower the size of a standard deviation parameter of the re-randomization process of the original scheme from exponential to polynomial in the security parameter. This first improvement is obtained via a finer security analysis of the drowning step of re-randomization, in which we apply the Rényi divergence instead of the conventional statistical distance as a measure of distance between distributions. Our second improvement is to reduce the number of randomizers needed from $\Omega(n \log n)$ to $2$, where $n$ is the dimension of the underlying ideal lattices. These two contributions allow us to decrease the bit size of the public parameters from $O(\lambda^5 \log \lambda)$ for the GGH scheme to $O(\lambda \log^2 \lambda)$ in GGHLite, with respect to the security parameter $\lambda$ (for a constant multilinearity parameter $\kappa$).

Applications of elliptic curve cryptography to anonymity, privacy and censorship circumvention call for methods to represent uniformly random points on elliptic curves as uniformly random bit strings, so that, for example, ECC network traffic can masquerade as random traffic. At ACM CCS 2013, Bernstein et al. proposed an efficient approach, called ``Elligator,'' to solving this problem for arbitrary elliptic curve-based cryptographic protocols, based on the use of efficiently invertible maps to elliptic curves. Unfortunately, such invertible maps are only known to exist for certain classes of curves, excluding in particular curves of prime order and curves over binary fields. A variant of this approach, ``Elligator Squared,'' was later proposed by Tibouchi (FC 2014) supporting not necessarily injective encodings to elliptic curves (and hence a much larger class of curves), but, although some rough efficiency estimates were provided, it was not clear how an actual implementation of that approach would perform in practice. In this paper, we show that Elligator Squared can indeed be implemented very efficiently with a suitable choice of curve encodings. More precisely, we consider the binary curve setting (which was not discussed in Tibouchi's paper), and implement the Elligator Squared bit string representation algorithm based on a suitably optimized version of the Shallue--van de Woestijne characteristic 2 encoding, which we show can be computed using only multiplications, trace and half-trace computations, and a few inversions. On the fast binary curve of Oliveira et al. (CHES 2013), our implementation runs in an average of only 22850 Haswell cycles, making uniform bit string representations possible for a very reasonable overhead---much smaller even than Elligator on Edwards curves. As a side contribution, we also compare implementations of Elligator and Elligator Squared on a curve supported by Elligator, namely Curve25519. We find that generating a random point and its uniform bitstring representation is around 35-40% faster with Elligator for protocols using a fixed base point (such as static ECDH), but 30-35% faster with Elligator Squared in the case of a variable base point (such as ElGamal encryption). Both are significantly slower than our binary curve implementation.

KLEIN is a family of lightweight block ciphers which proposed at RFIDSec 2011 by Gong et al. It has a 64-bit state and 64, 80 or 96-bit key size which introduce its version. It uses 16 same 4-bit Sboxes combined with two AES's MixColumn transformations for each round. This approach allows compact implementations of KLEIN in both low-end software and hardware. Such an innovative combination attracts the attention of cryptanalysts, and several security analyses have been published. The most successful one was represented in FSE'15 which was a truncated differential attack. They could attack up to 12, 13 and 14 rounds out of total number of 12, 16 and 20 rounds for KLEIN-64, -80 and -96, respectively. In this paper, by finding more efficient truncated differential paths and a slight improving in key recovery method we present two new truncated differential attacks on KLEIN, which recover the full secret key with better time and data complexities for the previously analyzed number of rounds. Also by using these truncated differential paths we are able to attack up to 14 and 15 rounds for KLEIN-80 and -96, respectively, which are the highest rounds ever analyzed.

Initial attempts to obtain lattice based signatures were closely related to reducing a vector modulo the fundamental parallelepiped of a secret basis (like GGH \cite{GGH97}, or \texttt{NTRUSign} \cite{HHPSW02}). This approach leaked some information on the secret, namely the shape of the parallelepiped, which has been exploited on practical attacks \cite{NR06}. \texttt{NTRUSign} was an extremely efficient scheme, and thus there has been a noticeable interest on developing countermeasures to the attacks, but with little success \cite{DN12}. In \cite{GPV08} Gentry, Peikert and Vaikuntanathan proposed a randomized version of Babai's nearest plane algorithm such that the distribution of a reduced vector modulo a secret parallelepiped only depended on the size of the base used. Using this algorithm and generating large, close to uniform, public keys they managed to get provably secure GGH-like lattice-based signatures. Recently, Stehlé and Steinfeld obtained a provably secure scheme very close to \texttt{NTRUSign} \cite{SS13} (from a theoretical point of view). In this paper we present an alternative approach to seal the leak of \texttt{NTRUSign}. Instead of modifying the lattices and algorithms used, we do a classic leaky \texttt{NTRUSign} signature and hide it with gaussian noise using techniques present in Lyubashevky's signatures. Our main contributions are thus a set of strong \texttt{NTRUSign} parameters, obtained by taking into account latest known attacks against the scheme, a statistical way to hide the leaky \texttt{NTRU} signature so that this particular instantiation of CVP-based signature scheme becomes zero-knowledge and secure against forgeries, based on the worst-case hardness of the $\mathcal{\tilde{O}}(N^{1.5})$-Shortest Independent Vector Problem over \texttt{NTRU} lattices. Finally, we give a set of concrete parameters to gauge the efficiency of the obtained signature scheme.

Hash Proof Systems were first introduced by Cramer and Shoup (Eurocrypt'02) as a tool to construct efficient chosen-ciphertext-secure encryption schemes. Since then, they have found many other applications, including password authenticated key exchange, oblivious transfer, and zero-knowledge arguments. One of the aspects that makes hash proof systems so interesting and powerful is that they can be seen as implicit proofs of membership for certain languages. As a result, by extending the family of languages that they can handle, one often obtains new applications or new ways to understand existing schemes. In this paper, we show how to construct hash proof systems for the disjunction of languages defined generically over cyclic, bilinear, and multilinear groups. Among other applications, this enables us to construct the most efficient one-time simulation-sound (quasi-adaptive) non-interactive zero-knowledge arguments for linear languages over cyclic groups, the first one-round group password-authenticated key exchange without random oracles, the most efficient threshold structure-preserving chosen-ciphertext-secure encryption scheme, and the most efficient one-round password authenticated key exchange in the UC framework.

Computing aggregate statistics about user data is of vital importance for a variety of services and systems, but this practice has been shown to seriously undermine the privacy of users. Differential privacy has proved to be an effective tool to sanitize queries over a database, and various cryptographic protocols have been recently proposed to enforce differential privacy in a distributed setting, e.g., statical queries on sensitive data stored on the user’s side. The widespread deployment of differential privacy techniques in real-life settings is, however, undermined by several limitations that existing constructions suffer from: they support only a limited class of queries, they pose a trade-off between privacy and utility of the query result, they are affected by the answer pollution problem, or they are inefficient. This paper presents PrivaDA, a novel design architecture for distributed differential privacy that leverages recent advances in SMPCs on fixed and floating point arithmetics to overcome the previously mentioned limitations. In particular, PrivaDA supports a variety of perturbation mechanisms (e.g., the Laplace, discrete Laplace, and exponential mechanisms) and it constitutes the first generic technique to generate noise in a fully distributed manner while maintaining the optimal utility. Furthermore, PrivaDA does not suffer from the answer pollution problem. We demonstrate the efficiency of PrivaDA with a performance evaluation, and its expressiveness and flexibility by illustrating a variety of application scenarios such as privacy-preserving web analytics.

We consider the notion of a non-interactive key exchange (NIKE). A NIKE scheme allows a party \(A\) to compute a common shared key with another party \(B\) from \(B\)'s public key and \(A\)'s secret key alone. This computation requires no interaction between \(A\) and \(B\), a feature which distinguishes NIKE from regular (i.e., interactive) key exchange not only quantitatively, but also qualitatively. Our first contribution is a formalization of NIKE protocols as ideal functionalities in the Universal Composability (UC) framework. As we will argue, existing NIKE definitions (all of which are game-based) do not support a modular analysis either of NIKE schemes themselves, or of the use of NIKE schemes. We provide a simple and natural UC-based NIKE definition that allows for a modular analysis both of NIKE schemes and their use in larger protocols. We proceed to investigate the properties of our new definition, and in particular its relation to existing game-based NIKE definitions. We find that (a) game-based NIKE security is equivalent to UC-based NIKE security against \emph{static} corruptions, and (b) UC-NIKE security against adaptive corruptions cannot be achieved without additional assumptions (but \emph{can} be achieved in the random oracle model). Our results suggest that our UC-based NIKE definition is a useful and simple abstraction of non-interactive key exchange.

We provide a new framework of cryptographic agents that unifies various modern ``cryptographic objects'' --- identity-based encryption, fully-homomorphic encryption, functional encryption, and various forms of obfuscation -- similar to how the Universal Composition framework unifies various multi-party computation tasks like commitment, coin-tossing and zero-knowledge proofs. These cryptographic objects can all be cleanly modeled as ``schemata'' in our framework. Highlights of our framework include the following: - We use a new `indistinguishability preserving' (INDPRE) definition of security that interpolates indistinguishability and simulation style definitions, which (often) sidesteps the known impossibilities for the latter. INDPRE-security is parameterized by the choice of the ``test'' family, such that by choosing different test families, one can obtain different levels of security for the same primitive (including various standard definitions in the literature). - We present a notion of `reduction' from one schema to another and a powerful `composition theorem' with respect to INDPRE security. We show that obfuscation is a ``complete'' schema under this notion, under standard cryptographic assumptions. We also provide a stricter notion of reduction that composes even when security is only with respect to certain restricted test families of importance. - Last but not the least, our framework can be used to model abstractions like the generic group model and the random oracle model, letting one translate a general class of constructions in these heuristic models to constructions based on `standard model assumptions'. We also illustrate how our framework can be applied to specific primitives like obfuscation and functional encryption. We relate our definitions to existing definitions and also give new constructions and reductions between different primitives.

Computer log files constitute a precious resource for system administrators for discovering and comprehending security breaches. A prerequisite of any meaningful log analysis is that attempts of intruders to cover their traces by modifying log entries are thwarted by storing them in a tamper-resistant manner. Some solutions employ cryptographic authentication when storing log entries locally, and let the authentication scheme's property of forward security ensure that the cryptographic keys in place at the time of intrusion cannot be used to manipulate past log entries without detection. This strong notion of security is typically achieved through frequent updates of the authentication keys via hash chains. However, as security demands that key updates take place rather often (ideally, at a resolution of milliseconds), in many settings this method quickly reaches the limits of practicality. Indeed, a log auditor aiming at verifying a specific log record might have to compute millions of hash iterations before recovering the correct verification key. This problem was addressed only recently by the introduction of seekable sequential key generators (SSKG). Every instance of this cryptographic primitive produces a forward-secure sequence of symmetric (authentication) keys, but also offers an explicit fast-forward functionality. The only currently known SSKG construction replaces traditional hash chains by the iterated evaluation of a shortcut one-way permutation, a factoring-based and hence in practice not too efficient building block. In this paper we revisit the challenge of marrying forward-secure key generation with seekability and show that symmetric primitives like PRGs, block ciphers, and hash functions suffice for obtaining secure SSKGs. Our scheme is not only considerably more efficient than the prior number-theoretic construction, but also extends the seeking functionality in a way that we believe is important in practice. Our construction is provably (forward-)secure in the standard model.

In a related-key attack (RKA) an adversary attempts to break a cryptographic primitive by invoking the primitive with several secret keys which satisfy some known relation. The task of constructing provably RKA secure PRFs (for non-trivial relations) under a standard assumption has turned to be challenging. Currently, the only known provably-secure construction is due to Bellare and Cash (Crypto 2010). This important feasibility result is restricted, however, to linear relations over relatively complicated groups (e.g., $\Z^*_q$ where $q$ is a large prime) that arise from the algebraic structure of the underlying cryptographic assumption (DDH/DLIN). In contrast, applications typically require RKA-security with respect to simple additive relations such as XOR or addition modulo a power-of-two. In this paper, we partially fill this gap by showing that it is possible to deal with simple additive relations at the expense of relaxing the model of the attack. We introduce several natural relaxations of RKA-security, study the relations between these notions, and describe efficient constructions either under lattice assumptions or under general assumptions. Our results enrich the landscape of RKA security and suggest useful trade-offs between the attack model and the family of possible relations.

A two-to-one recoding (TOR) scheme is a new cryptographic primitive, proposed in the recent work of Gorbunov, Vaikuntanathan, and Wee (GVW), as a means to construct attribute-based encryption (ABE) schemes for all boolean circuits. GVW show that TOR schemes can be constructed assuming the hardness of the learning-with-errors (LWE) problem. We propose a slightly weaker variant of TOR schemes called correlation-relaxed two-to-one recoding (CR-TOR). Unlike the TOR schemes, our weaker variant does not require an encoding function to be pseudorandom on correlated inputs. We instead replace it with an indistinguishability property that states a ciphertext is hard to decrypt without access to a certain encoding. The primary benefit of this relaxation is that it allows the construction of ABE for circuits using the TOR paradigm from a broader class of cryptographic assumptions. We show how to construct a CR-TOR scheme from the noisy cryptographic multilinear maps of Garg, Gentry, and Halevi as well as those of Coron, Lepoint, and Tibouchi. Our framework leads to an instantiation of ABE for circuits that is conceptually different from the existing constructions.

Simon mentions in his seminal result separating collision-resistant hash functions from one-way permutations (EUROCRYPT '98), that the wrong strategy to sample collisions can be exploited to invert the permutation. He, however, does not spell out a concrete circuit that demonstrates this. In this short note, we describe and analyze one such circuit.

One of the interesting types of RFID application is RFID searching which aims to hear a specific RFID tag from a large group of tags, i.e. ability of detecting whether a target RFID tag is nearby. Very recently, a lightweight protocol using error-correcting codes has been proposed by Chen et al. to provide a solution to needs in this field. The authors give a detailed analysis of their protocol in terms of security, privacy, communication overhead, hardware cost and they claim that it is a realizable scheme with fulfilling security and privacy requirements. In this study, however, we investigate security of this protocol and clearly demonstrate its security flaws that completely allow an adversary to exploit the system. In particular, by using linear properties of error correcting coding we firstly describe a tag tracing attack that undermines untraceability property which is one its design objectives. Then along with its implementation details we present a key recovery attack that reduces dramatically search space of a tag's secret key and show that an adversary can compromise it in practical time by only querying this tag for several times. As an illustrative example we retrieve the secret key of the protocol in two hours for the adopted linear block code C(47,24,11) which is one of the suggested codes.

In this paper we pick up an old challenge to design public key or white-box construction from symmetric cipher components. We design several encryption schemes based on the \textsf{ASASA} structure ranging from fast and generic symmetric ciphers to compact public key and white-box constructions based on generic affine transformations combined with specially designed low degree non-linear layers. While explaining our design process we show several instructive attacks on the weaker variants of our schemes.

Identity-based encryption (IBE) eliminates the necessity of having a costly certificate verification process. However, revocation remains as a daunting task in terms of ciphertext update and key update phases as due to the lack of a certificate revocation list in this infrastructure. In this paper, we provide an affirmative solution to solve the efficiency problem incurred by revocation. We propose the first cloud-based revocable identity-based proxy re-encryption (CR-IB-PRE) scheme that supports user revocation but also delegation of decryption rights. No matter a user is revoked or not, at the end of a given time period the cloud acting as a proxy will re-encrypt all ciphertexts of the user under the current time period to the next time period. If the user is revoked in the forthcoming time period, he cannot decrypt the ciphertexts by using the expired private key anymore. We state that this primitive is applicable to many practical network applications, such as subscription-based cloud storage services. Comparing to some naive solutions which require a private key generator (PKG) to interact with non-revoked users in each time period, the new scheme provides definite advantages in terms of communication and computation efficiency. Our scheme only requires the PKG to publish a constant-size public string for each time period and meanwhile, the workload of ciphertexts update is off-loaded to the cloud server. More importantly, the scheme can be proven secure in the standard model.

We introduce a notion of watermarking for cryptographic functions and propose a concrete scheme for watermarking cryptographic functions. Informally speaking, a digital watermarking scheme for cryptographic functions embeds information, called a \textit{mark}, into functions such as one-way functions and decryption functions of public-key encryption. There are two basic requirements for watermarking schemes. (1) A mark-embedded function must be functionally equivalent to the original function. (2) It must be difficult for adversaries to remove the embedded mark without damaging the original functionality. In spite of its importance and usefulness, there have only been a few theoretical works on watermarking for functions (or programs). Furthermore, we do not have rigorous definitions of watermarking for cryptographic functions and concrete constructions. To solve the above problem, we introduce a notion of watermarking for cryptographic functions and define its security. Furthermore, we present a lossy trapdoor function (LTF) based on the decisional linear (DLIN) problem and a watermarking scheme for the LTF. Our watermarking scheme is secure under the DLIN assumption in the standard model. We use techniques of dual system encryption and dual pairing vector spaces (DPVS) to construct our watermarking scheme. This is a new application of DPVS. Our watermarking for cryptographic functions is a generalized notion of copyrighted functions introduced by Naccache, Shamir, and Stern (PKC 1999) and our scheme is based on an identity-based encryption scheme whose private keys for identities (i.e., decryption functions) are marked, so our technique can be used to construct black-box traitor tracing schemes.

A Ciphertext-Policy Attribute-Based Encryption (CP-ABE) system extracts the decryption keys over attributes shared by multiple users. It brings plenty of advantages in ABE applications. CP-ABE enables fine-grained access control to the encrypted data for commercial applications. There has been significant progress in CP-ABE over the recent years because of two properties called traceability and large universe, greatly enriching the commercial applications of CP-ABE. Traceability is the ability of ABE to track the malicious users or traitors who intentionally leak the partial or modified decryption keys to others for profits. Nevertheless, due to the nature of CP-ABE, it is difficult to identify the original key owner from an exposed key since the decryption privilege is shared by multiple users who have the same attributes. On the other hand, the property of large universe in ABE proposed by Lewko and Waters enlarges the practical applications by supporting flexible number of attributes. Several systems have been proposed to obtain either of the above properties. However, none of them achieve the two properties simultaneously in practice, which limits the commercial applications of CP-ABE to a certain extent. In this paper, we propose a practical large universe CP-ABE system supporting white-box traceability, which is suitable for commercial applications. Compared to existing systems, our new system has three advantages: (1) The number of attributes is not polynomially bounded; (2) Malicious users who leak their decryption keys could be traced; and, (3) The storage overhead for traitor tracing is constant. We also prove the selective security of our new system in the standard model under "$q$-type" assumption.