In this article we describe new generic distinguishing and forgery attacks in the related-key scenario (using only a single related-key) for the HMAC construction. When HMAC uses a k-bit key, outputs an n-bit MAC, and is instantiated with an l-bit inner iterative hash function processing m-bit message blocks where m=k, our distinguishing-R attack requires about 2^{n/2} queries which improves over the currently best known generic attack complexity 2^{l/2} as soon as l>n. This means that contrary to the general belief, using wide-pipe hash functions as internal primitive will not increase the overall security of HMAC in the related-key model when the key size is equal to the message block size. We also present generic related-key distinguishing-H, internal state recovery and forgery attacks. Our method is new and elegant, and uses a simple cycle-size detection criterion. The issue in the HMAC construction (not present in the NMAC construction) comes from the non-independence of the two inner hash layers and we provide a simple patch in order to avoid this generic attack. Our work finally shows that the choice of the opad and ipad constants value in HMAC is important.

Cryptanalytic time-memory trade-offs were introduced by Hellman in 1980 in order to perform key-recovery attacks on cryptosystems. A major advance was presented at Crypto 2003 by Oechslin, with the rainbow table variant that outperforms Hellman's seminal work. This paper introduces the fingerprint tables, which drastically reduce the number of false alarms during the attack compared to the rainbow tables. The key point of our technique consists in storing in the tables the fingerprints of the chains instead of their endpoints. The fingerprint tables provide a time-memory trade-off that is about two times faster than the rainbow tables on usual problem sizes. We experimentally illustrate the performance of our technique, and demonstrate that it is faster than Ophcrack, a Windows LM Hash password cracker considered so far to be the fastest one ever implemented.

For data storage outsourcing services, it is important to allow data owners to efficiently and securely verify that the storage sever stores their data correctly. To address this issue, several proof-of-retrievability (POR) schemes have been proposed wherein a storage sever must prove to a verifier that all of a client's data are stored correctly. While existing POR schemes offer decent solutions addressing various practical issues, they either have a non-trivial (linear or quadratic) communication complexity, or only support private verification, i.e., only the data owner can verify the remotely stored data. It remains open to design a POR scheme that achieves both public verifiability and constant communication cost simultaneously. In this paper, we solve this open problem and propose the first POR scheme with public verifiability and constant communication cost: in our proposed scheme, the message exchanged between the prover and verifier is composed of a constant number of group elements; different from existing private POR constructions, our scheme allows public verification and releases the data owners from the burden of staying online. We achieved these by tailoring and uniquely combining techniques such as constant size polynomial commitment and homomorphic linear authenticators. Thorough analysis shows that our proposed scheme is efficient and practical. We prove the security of our scheme based on the Computational Diffie-Hellman Problem, the Strong Diffie-Hellman assumption and the Bilinear Strong Diffie-Hellman assumption.\end{abstract}

The stream cipher WG-7 is a lightweight variant of the well-known Welch-Gong (WG) stream cipher family, targeting for resource-constrained devices like RFID tags, smart cards, and wireless sensor nodes. Recently, a distinguishing attack was discovered against the stream cipher WG-7 by Orumiehchiha, Pieprzyk and Steinfeld. In this paper, we extend their work to a general distinguishing attack and suggest criteria to protect the WG stream cipher family from this attack. Our analysis shows that by properly choosing the minimal polynomial of the linear feedback shift register for a WG stream cipher, the general distinguishing attack can be easily thwarted.

We present new families of access structures that, similarly to the multilevel and compartmented access structures introduced in previous works, are natural generalizations of threshold secret sharing. Namely, they admit an ideal linear secret sharing schemes over every large enough finite field, they can be described by a small number of parameters, and they have useful properties for the applications of secret sharing. The use of integer polymatroids makes it possible to find many new such families and it simplifies in great measure the proofs for the existence of ideal secret sharing schemes for them.

In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their inputs, while preserving properties like privacy, correctness, and independence of inputs. One security property that has typically not been considered in the past relates to the length or size of the parties inputs. This is despite the fact that in many cases the size of a party's input can be confidential. The reason for this omission seems to have been the folklore belief that, as with encryption, it is impossible to carry out non-trivial secure computation while hiding the size of parties' inputs. However some recent results (e.g., Ishai and Paskin at TCC 2007, Ateniese, De Cristofaro and Tsudik at PKC 2011) showed that it is possible to hide the input size of one of the parties for some limited class of functions, including secure two-party set intersection. This suggests that the folklore belief may not be fully accurate. In this work, we initiate a theoretical study of input-size hiding secure computation, and focus on the two-party case. We present definitions for this task, and deal with the subtleties that arise in the setting where there is no a priori polynomial bound on the parties' input sizes. Our definitional study yields a multitude of classes of input-size hiding computation, depending on whether a single party's input size remains hidden or both parties' input sizes remain hidden, and depending on who receives output and if the output size is hidden from a party in the case that it does not receive output. We prove feasibility and impossibility results for input-size hiding secure two-party computation. Some of the highlights are as follows: Under the assumption that fully homomorphic encryption (FHE) exists, there exist non-trivial functions (e.g., the millionaire's problem) that can be securely computed while hiding the input size of both parties. Under the assumption that FHE exists, every function can be securely computed while hiding the input size of one party, when both parties receive output (or when the party not receiving output does learn the size of the output). In the case of functions with fixed output length, this implies that every function can be securely computed while hiding one party's input size. There exist functions that cannot be securely computed while hiding both parties' input sizes. This is the first formal proof that, in general, some information about the size of the parties' inputs must be revealed. Our results are in the semi-honest model. The problem of input-size hiding is already challenging in this scenario. We discuss the additional difficulties that arise in the malicious setting and leave this extension for future work.

Implementation attacks pose a serious threat for the security of cryptographic devices and there are a multitude of countermeasures that are used to prevent them. Two countermeasures used in implementations of block ciphers to increase the complexity of such attacks are the use of dummy rounds and redundant computation with consistency checks to prevent fault attacks. In this paper we present several countermeasures based on the idea of infective computation. Our countermeasures ensure that a fault injected into a cipher, dummy, or redundant round will infect the ciphertext such that an attacker cannot derive any information on the secret key being used. This has one clear advantage: the propagation of faults prevents an attacker from being able to conduct any fault analysis on any corrupted ciphertexts. As a consequence, there is no need for any test at the end of an implementation to determine if a fault has been injected and a ciphertext can always be returned.

Recently, several important block ciphers are considered to be broken by the bruteforce-like cryptanalysis, with a time complexity faster than exhaustive key search by going over the entire key space but performing less than a full encryption for each possible key. Motivated by this observation, we describe a meet-in-the-middle attack that can always be successfully mounted against any practical block ciphers with success probability one. The data complexity of this attack is the smallest according to the unicity distance. The time complexity can be written as $2^k(1-\epsilon)$ where $\epsilon > 0$ for all block ciphers. Previously, the security bound that is commonly accepted is the length k of the given master key. From our result we point out that actually this k-bit security is always overestimated and can never be reached due to the inevitable key bits loss. No amount of clever design can prevent it, but increments of the number of rounds can reduce this key loss as much as possible. We give more insight in the problem of the upper bound of eective key bits in block ciphers, and show a more accurate bound. A suggestion about the relation between the key size and block size is given. That is, when the number of rounds is xed, it is better to take a key size equal to the block size. Moreover, eective key bits of many well-known block ciphers are calculated and analyzed, which also conrm their lower security margin than thought before.

In this paper we present a rather new approach to apply mixed-integer optimization to the cryptanalysis of cryptographic primitives. We focus on the stream cipher Trivium, that has been recommended by the eSTREAM stream cipher project, and the lightweight block cipher Ktantan. Using these examples we explain how the problem of solving a non-linear multivariate Boolean equation system can be formulated as a mixed-integer linear programming problem. Our main focus is the formulation of the mixed-integer programming model (MIP model), which includes amongst others the choice of a conversion method to convert the Boolean equations into equations over the reals, different guessing strategies and the selection of binary variables. We apply the commercial solver Cplex to our problems. The results and further possible features of the approach are discussed.

We investigate a lattice construction method for the Coppersmith technique for finding small solutions of a modular equation. We consider its variant for simultaneous equations and propose a method to construct a lattice by combining lattices for solving single equations. As applications, we consider a new RSA cryptanalyses. Our algorithm can factor an RSA modulus from $\ell \ge 2$ pairs of RSA public exponents with the common modulus corresponding to secret exponents smaller than $N^{(9\ell -5)/(12\ell + 4)}$, which improves on the previously best known result by Sarkar and Maitra. For partial key exposure situation, we also can factor the modulus if $\beta - \delta/2 + 1/4 < (3\ell-1)(3\ell + 1)$, where $\beta$ and $\delta$ are bit-lengths $/ \log N$ of the secret exponent and its exposed LSBs, respectively.

These are basically the lecture notes for the short course "Applications of Combinatorics to Information-Theoretic Cryptography", Central European University, Budapest, May-June 2012. With the objective of covering a full course on secret sharing, additional content will be added in subsequent versions of these lecture notes.

We revisit the notions of robustness introduced by Abdalla, Bellare, and Neven (TCC 2010). One of the main motivations for the introduction of strong robustness for public-key encryption (PKE) by Abdalla et al. to prevent certain types of attack on Sako's auction protocol. We show, perhaps surprisingly, that Sako's protocol is still vulnerable to attacks exploiting robustness problems in the underlying PKE scheme, even when it is instantiated with a \emph{strongly} robust scheme. This demonstrates that current notions of robustness are insufficient even for one of its most natural applications. To address this and other limitations in existing notions, we introduce a series of new robustness notions for PKE and explore their relationships. In particular, we introduce \emph{complete} robustness, our strongest new notion of robustness, and give a number of constructions for completely robust PKE schemes.

On October 2-nd 2012 NIST announced its selection of the Keccak scheme as the new SHA-3 hash standard. In this paper we present the first published collision finding attacks on reduced-round versions of Keccak-384 and Keccak-512, providing actual collisions for 3-round versions, and describing an attack which is $2^{45}$ times faster than birthday attacks for 4-round Keccak-384. For Keccak-256, we increase the number of rounds which can be attacked to 5. All these results are based on a generalized {\it internal differential attack} (introduced by Peyrin at Crypto 2010), and use it to map a large number of Keccak inputs into a relatively small subset of possible outputs with a surprisingly large probability. In such a \textit{squeeze attack} it is easier to find random collisions in the reduced target subset by a standard birthday argument.

In this paper, we present the first inner-product encryption (IPE) schemes that are unbounded in the sense that the public parameters do not impose additional limitations on the predicates and attributes used for encryption and decryption keys. All previous IPE schemes were bounded, or have a bound on the size of predicates and attributes given public parameters fixed at setup. The proposed unbounded IPE schemes are fully (adaptively) secure and fully attribute-hiding in the standard model under a standard assumption, the decisional linear (DLIN) assumption. In our unbounded IPE schemes, the inner-product relation is generalized, where the two vectors of inner-product can be different sizes and it provides a great improvement of efficiency in many applications. We also present the first fully secure unbounded attribute-based encryption (ABE) schemes, and the security is proven under the DLIN assumption in the standard model. To achieve these results, we develop novel techniques, indexing and consistent randomness amplification, on the (extended) dual system encryption technique and the dual pairing vector spaces (DPVS).

In this paper we highlight the benefits of using genus 2 curves in public-key cryptography. Compared to the standardized genus 1 curves, or elliptic curves, arithmetic on genus 2 curves is typically more involved but allows us to work with moduli of half the size. We give a taxonomy of the best known techniques to realize genus 2 based cryptography, which includes fast formulas on the Kummer surface and efficient 4-dimensional GLV decompositions. By studying different modular arithmetic approaches on these curves, we present a range of genus 2 implementations. On a single core of an Intel Core i7-3520M (Ivy Bridge), our implementation on the Kummer surface breaks the 125 thousand cycle barrier which sets a new software speed record at the 128-bit security level for constant-time scalar multiplications compared to all previous genus 1 and genus 2 implementations.

In the context of Ciphertext-Policy Attribute-Based Encryption (CP-ABE), if a decryption device associated with an attribute set $S_{\cal D}$ appears on eBay, and is alleged to be able to decrypt any ciphertexts with policies satisfied by $S_{\cal D}$, no one including the CP-ABE authorities can identify the malicious user(s) who build such a decryption device using their key(s). This has been known as a major practicality concern in CP-ABE applications, for example, providing fine-grained access control on encrypted data. Due to the nature of CP-ABE, users get decryption keys from authorities associated with attribute sets. If there exists two or more users with attribute sets being the supersets of $S_{\cal D}$, existing CP-ABE schemes cannot distinguish which user is the malicious one who builds and sells such a decryption device. In this paper, we extend the notion of CP-ABE to support \emph{Blackbox Traceability} and propose a concrete scheme which is able to identify a user whose key has been used in building a decryption device from multiple users whose keys associated with the attribute sets which are all the supersets of $S_{\cal D}$. The scheme is efficient with sub-linear overhead and when compared with the very recent (non-traceable) CP-ABE scheme due to Lewko and Waters in Crypto 2012, we can consider this new scheme as an extension with the property of \emph{fully collusion-resistant blackbox traceability} added, i.e. an adversary can access an arbitrary number of keys when building a decryption device while the new tracing algorithm can still identify at least one particular key which must have been used for building the underlying decryption device. We show that this new scheme is secure against adaptive adversaries in the standard model, and is highly expressive by supporting any monotonic access structures. Its additional traceability property is also proven against adaptive adversaries in the standard model. As of independent interest, in this paper, we also consider another scenario which we call it ``\emph{found-in-the-wild}". In this scenario, a decryption device is found, for example, from a black market, and reported to an authority (e.g. a law enforcement agency). The decryption device is found to be able to decrypt ciphertexts with certain policy, say $\mathbb{A}$, while the associated attribute set $S_{\cal D}$ is \textbf{missing}. In this found-in-the-wild scenario, we show that the Blackbox Traceable CP-ABE scheme proposed in this paper can still be able to find the malicious users whose keys have been used for building the decryption device, and our scheme can achieve \emph{selective} traceability in the standard model under this scenario.

In this paper, we study differential attacks against ARX schemes. We build upon the generalized characteristics of de Cannière and Rechberger and the multi-bit constraints of Leurent. We describe a more efficient way to propagate multi-bit constraints, that allows us to use the complete set of 2^32 2.5-bit constraints, instead of the reduced sets used by Leurent. As a result, we are able to build complex non-linear differential characteristics for reduced versions of the hash function Skein. We present several characteristics for use in various attack scenarios; this results in attacks with a relatively low complexity, in relatively strong settings. In particular, we show practical free-start and semi-free-start collision attacks for 20 rounds and 12 rounds of Skein-256, respectively. To the best of our knowledge, these are the first examples of complex differential trails are build for pure ARX designs. We believe this is an important work to assess the security of ARX designs against differential cryptanalysis. Our improved tools will be publicly available with the final version of this paper.

Forensic watermarking is the application of digital watermarks for the purpose of tracing unauthorized redistribution of content. The most powerful type of attack on watermarks is the collusion attack, in which multiple users compare their differently watermarked versions of the same content. Collusion-resistant codes have been developed against these attacks. One of the most famous such codes is the Tardos code. It has the asymptotically optimal property that it can resist c attackers with a code of length proportional to c^2. Determining error rates for the Tardos code and its various extensions and generalizations turns out to be a nontrivial problem. In recent work we developed an approach called the Convolution and Series Expansion (CSE) method to accurately compute false positive accusation probabilities. In this paper we extend the CSE method in order to make it possible to compute false negative accusation probabilities as well.

The RSA-768 (270 decimal digits) was factored by Kleinjung et al. on December 12 2009, and the RSA-704 (212 decimal digits) was factored by Bai et al. on July 2, 2012. And the RSA-200 (663 bits) was factored by Bahr et al. on May 9, 2005. Until right now, there is no body successful to break the RSA-210 (696 bits) currently. In this paper, we would discuss an estimation method to approach lower/upper bound of &#934;(n) in the RSA parameters. Our contribution may help researchers lock the &#934;(n) and the challenge RSA shortly.

To have “full” entropy has been defined in a draft NIST standard to be to have min-entropy very close, proportionally, to the min-entropy of a uniform distribution. A function is uniform if all its preimages have the same size. This report proves that the output of any uniform compression function can fail to have full entropy, even when the input has full entropy.

In a proxy re-encryption (PRE) scheme, a proxy is given a re-encryption key and has the ability to translate a ciphertext under one key into a ciphertext of the same message under a different key, without learning anything about the message encrypted under either key. PREs have been widely used in many exciting applications, such as email forwarding and law enforcement. Based on a good observation on the applications of PREs, we find that a PRE receiver needs an ability, just like what is provided by public-key encryption with non-interactive opening, to non-interactively and efficiently convince third parties of what he obtains from a particular (transformed) ciphertext, while still keeping the security of his secret key and other ciphertexts. To meet such a practical requirement, we first introduce proxy re-encryption with non-interactive opening (PRENO), and formally define the notions of security against \textit{chosen ciphertext attacks} (CCA) and \textit{proof soundness}. Our security model is natural and strong since we allow the CCA adversary to adaptively choose public keys for malicious users (i.e., a chosen key model), and a scheme secure in previous models (i.e., knowledge of secret key models) is not necessarily secure in our model. Then, we present an efficient PRENO scheme which satisfies our security notions based on the decisional bilinear Diffie-Hellman (DBDH) assumption in the standard model. Compared with two previous PRE schemes, our scheme is competitive in several aspects. First, its CCA security is proved in a strong security model under a well-studied assumption in the standard model. Second, it has a good overall performance in terms of ciphertext length and computational cost. Third, it first provides non-interactive opening for PRE schemes.

In [eprint.iacr.org/2009/117] method of virtual isomorphisms of ciphers was proposed for cryptanalysis. Cipher is vulnerable to an attack iff isomorphic cipher is vulnerable to this attack. That method is based on conjugation, and it is not practical because all round operations except one become nonlinear. New isomorphism of AES is proposed, its image IAES has only one nonlinear operation IXOR - isomorphic image of XOR of 5 bytes. Maximal probabilities of byte differentials are increased about 10-11 times, maximal biases of linear sums are increased about 3.6 times comparatively to original AES. IAES possesses computable family of differentials of IXOR with two active input bytes, zero output difference and probability 1. Zero output difference decreases the rate of multiplication of active nonlinearities in differential characteristic of IAES.

Physically Unclonable Functions (PUFs) exploit the physical characteristics of silicon and provide an alternative to storing digital encryption keys in non-volatile memory. A PUF maps a unique set of digital inputs to a corresponding set of digital outputs. In this paper, the use of asynchronous logic and design techniques to implement PUFs is advocated for Asynchronous Physically Unclonable Functions (APUFs). A new method of using asynchronous rings to implement PUFs is described called ASYNCPUF which features inherent field programmability. It is both a novel and holistic PUF design compared to the existing state-of-the-art as it naturally addresses the two challenges facing PUFs to-date that prevent wide-spread adoption: robustness and entropy. Results of electrical simulation in a 90 nano-meter lithography process are presented and discussed.

In their paper ``A Quasigroup Based Random Number Generator for Resource Constrained Environments", the authors Matthew Battey and Abhishek Parakh propose the pseudo random number generator LOQG PRNG 256. We show several highly efficient attacks on LOQG PRNG 256.

Image compression and image encryption are pivotal to proper storage and transmission of images over MANET. Simultaneous image compression and encryption aims at achieving enhanced bandwidth utilization and security at the same time. The Number Theory based Image Compression and Quasigroup Encryption (NTICQE) algorithm employs number theoretic paradigm - Chinese Remainder Theorem and Quasigroup Encryption, to solve congruencies and hence realize the twin ideals of compression and encryption simultaneously. Quasigroup encryptor that has very good data-scrambling properties and, therefore, it has potential uses in symmetric cryptography.

At NDSS 2012, Yan et al. analyzed the security of several challenge-response type user authentication protocols against passive observers, and proposed a generic counting based statistical attack to recover the secret of some counting based protocols given a number of observed authentication sessions. Roughly speaking, the attack is based on the fact that secret (pass) objects appear in challenges with a different probability from non-secret (decoy) objects when the responses are taken into account. Although they mentioned that a protocol susceptible to this attack should minimize this difference, they did not give details as to how this can be achieved barring a few suggestions. In this paper, we attempt to fill this gap by generalizing the attack with a much more comprehensive theoretical analysis. Our treatment is more quantitative which enables us to describe a method to theoretically estimate a lower bound on the number of sessions a protocol can be safely used against the attack. Our results include 1) two proposed fixes to make counting protocols practically safe against the attack at the cost of usability, 2) the observation that the attack can be used on non-counting based protocols too as long as challenge generation is contrived, 3) and two main design principles for user authentication protocols which can be considered as extensions of the principles from Yan et al. This detailed theoretical treatment can be used as a guideline during the design of counting based protocols to determine their susceptibility to this attack. The Foxtail protocol, one of the protocols analyzed by Yan et al., is used as a representative to illustrate our theoretical and experimental results.

In a digital signature scheme with message recovery, rather than transmitting the message $m$ and its signature $\sigma$, a single enhanced signature $\tau$ is transmitted. The verifier is able to recover $m$ from $\tau$ and at the same time verify its authenticity. The two most important parameters of such a scheme are its security and overhead $|\tau|-|m|$. A simple argument shows that for any scheme with ``$n$ bits security" $|\tau|-|m|\ge n$, i.e., the overhead is lower bounded by the security parameter $n$. Currently, the best known constructions in the random oracle model are far from this lower bound requiring an overhead of $n+\log q_h$, where $q_h$ is the number of queries to the random oracle. In this paper we give a construction which basically matches the $n$ bit lower bound. We propose a simple digital signature scheme with $n+o(\log q_h)$ bits overhead, where $q_h$ denotes the number of random oracle queries. Our construction works in two steps. First, we propose a signature scheme with message recovery having optimal overhead in a new ideal model, the random invertible function model. Second, we show that a four-round Feistel network with random oracles as round functions is tightly "public-indifferentiable'' from a random invertible function. At the core of our indifferentiability proof is an almost tight upper bound for the expected number of edges of the densest "small'' subgraph of a random Cayley graph, which may be of independent interest.

Let $E$ be an elliptic curve over a finite field ${\mathbb F}_q$ with a power of prime $q$, $r$ a prime dividing $\#E({\mathbb F}_q)$, and $k$ the smallest positive integer satisfying $r | \Phi_k(p)$, called embedding degree. Then a bilinear map $t: E({\mathbb F}_q)[r] \times E({\mathbb F}_{q^k})/rE({\mathbb F}_{q^k}) \rightarrow {\mathbb F}_{q^k}^*$ is defined, called the Tate pairing. And the Ate pairing and other variants are obtained by reducing the domain for each argument and raising it to some power. In this paper we consider the {\em Fixed Argument Pairing Inversion (FAPI)} problem for the Tate pairing and its variants. In 2012, considering FAPI for the Ate$_i$ pairing, Kanayama and Okamoto formulated the {\em Exponentiation Inversion (EI)} problem. However the definition gives a somewhat vague description of the hardness of EI. We point out that the described EI can be easily solved, and hence clarify the description so that the problem does contain the actual hardness connection with the prescribed domain for given pairings. Next we show that inverting the Ate pairing (including other variants of the Tate pairing) defined on the smaller domain is neither easier nor harder than inverting the Tate pairing defined on the lager domain. This is very interesting because it is commonly believed that the structure of the Ate pairing is so simple and good (that is, the Miller length is short, the solution domain is small and has an algebraic structure induced from the Frobenius map) that it may leak some information, thus there would be a chance for attackers to find further approach to solve FAPI for the Ate pairing, differently from the Tate pairing.

Rakaposhi is a synchronous stream cipher, which uses three main components a non-linear feedback shift register (NLFSR), a dynamic linear feedback shift register (DLFSR) and a non-linear filtering function ($NLF$). NLFSR consists of 128 bits and is initialised by the secret key $K$. DLFSR holds 192 bits and is initialised by an initial vector ($IV$). $NLF$ takes 8-bit inputs and returns a single output bit. The work identifies weaknesses and properties of the cipher. The main observation is that the initialisation procedure has the so-called sliding property. The property can be used to launch distinguishing and key recovery attacks. The distinguisher needs four observations of the related $(K,IV)$ pairs. The key recovery algorithm allows to discover the secret key $K$ after observing $2^{9}$ pairs of $(K,IV)$. In the proposed related-key attack, the number of related $(K,IV)$ pairs is $2^{(128+192)/4}$ pairs. The key recovery algorithm allows to discover the secret key $K$ after observing $2^9$ related $(K,IV)$ pairs. Further the cipher is studied when the registers enter short cycles. When NLFSR is set to all ones, then the cipher degenerates to a linear feedback shift register with a non-linear filter. Consequently, the initial state (and Secret Key and $IV$) can be recovered with complexity $2^{63.87}$. If DLFSR is set to all zeros, then $NLF$ reduces to a low non-linearity filter function. As the result, the cipher is insecure allowing the adversary to distinguish it from a random cipher after $2^{17}$ observations of keystream bits. There is also the key recovery algorithm that allows to find the secret key with complexity $2^{54}$.

Predicate encryption (PE) that provides both the access control of ciphertexts and the privacy of ciphertexts is a new paradigm of public-key encryption. An important application of PE is a searchable encryption system in cloud storage, where it enables a client to securely outsource the search of a keyword on encrypted data without revealing the keyword to the cloud server. One practical issue of PE is to devise an efficient revocation method to revoke a user when the secret key of the user is compromised. Privacy preserving revocable PE (RPE) can provide not only revocation, but also the privacy of revoked users. In this paper, we first define two new security models of privacy preserving RPE: the strongly full-hiding security and the weakly full-hiding security. The strongly full-hiding security provides the full privacy of ciphertexts against outside and inside adversaries, but the weakly full-hiding security provides the full privacy of ciphertexts against an outside adversary who cannot decrypt the challenge ciphertext. Next, we propose a general RPE construction from any PE scheme, and prove its security in the weakly full-hiding security model. Our generic RPE scheme is efficient since the number of ciphertext elements is not proportional to the number of users in a receiver set. Additionally, our RPE scheme can support polynomial-size circuits if a recently proposed FE scheme for polynomial-size circuits is used as an underlying PE scheme.

We revisit the concept of public key encryption with delegated keyword search (PKEDS), a concept proposed by Ibraimi et al. A PKEDS scheme allows a receiver to authorize third-party server(s) to search in two ways: either according to a message chosen by the server itself or according to a trapdoor sent by the receiver. We show that the existing formulation has some defects and the proposed scheme is unnecessarily inefficient. Based on our analysis, we present a refined formulation of the primitive with a new security model. We then propose a new PKEDS scheme, which is proven secure and much more efficient than the original scheme by Ibraimi et al.

The question whether Identity-Based Encryption (IBE) can be based on the Decisional Diffie-Hellman (DDH) assumption is one of the most prominent questions in Cryptography related to DDH. We study limitations on the use of the DDH assumption in cryptographic constructions, and show that it is impossible to construct a secure Identity-Based Encryption system using, in a black box way, only the DDH (or similar) assumption about a group. Our impossibility result is set in the generic groups model, where we describe an attack on any IBE construction that relies on oracle access to the group operation of randomly labelled group elements -- a model that formalizes naturally DDH hardness. The vast majority of existing separation results typically give separation from general primitives, whereas we separate a primitive from a class of number theoretic hardness assumptions. Accordingly, we face challenges in creating an attack algorithm that will work against constructions which leverage the underlying algebraic structure of the group. In fact, we know that this algebraic structure is powerful enough to provide generic constructions for several powerful primitives including oblivious transfer and chosen ciphertext secure public-key cryptosystems (note that an IBE generalizes such systems). Technically, we explore statistical properties of the group algebra associated with a DDH oracle, which can be of independent interest.

We consider the problem of constructing protocols for secure computation that achieve strong concurrent and composable notions of security in the plain model. Unfortunately UC-secure secure computation protocols are impossible in this setting, but the Angel-Based Composable Security notion offers a promising alternative. Until now, however, under standard (polynomial-time) assumptions, only protocols with polynomially many rounds were known to exist. In this work, we give the first $\tilde{O}(\log n)$-round secure computation protocol in the plain model that achieves angel-based composable security in the concurrent setting, under standard assumptions. We do so by constructing the first $\tilde{O}(\log n)$-round CCA-secure commitment protocol. Our CCA-secure commitment protocol is secure based on the minimal assumption that one-way functions exist. A central tool in obtaining our result is a new \emph{robust concurrent extraction lemma} that we introduce and prove, based on the minimal assumptions that one-way functions exist. This robust concurrent extraction lemma shows how to build concurrent extraction procedures that work even in the context of an ``external'' protocol that cannot be rewound by the extractor. We believe this lemma can be used to simplify many existing works on concurrent security, and is of independent interest. In fact, our lemma when used in conjunction with the concurrent-simulation schedule of Pass and Venkitasubramaniam (TCC'08), also yields a constant round construction based additionally on the existence of quasi-polynomial time (\pqt) secure one-way functions.

Data access control is an effective way to ensure the data security in the cloud. Due to data outsourcing and untrusted cloud servers, the data access control becomes a challenging issue in cloud storage systems. Ciphertext-Policy Attribute-based Encryption (CP-ABE), as a promising technique for access control of encrypted data, is very suitable for access control in cloud storage systems due to its high efficiency and expressiveness. However, the existing CP-ABE schemes cannot be directly applied to data access control for cloud storage systems because of the attribute revocation problem. In this paper, we consider the problem of attribute revocation in multi-authority cloud storage systems where the users' attributes come from different domains each of which is managed by a different authority. We propose TAAC (Temporal Attribute-based Access Control), an efficient data access control scheme for multi-authority cloud storage systems, where the authorities are independent from each other and no central authority is needed. TAAC can efficiently achieve temporal access control on attribute-level rather than on user-level. Moreover, different from the existing schemes with attribute revocation functionality, TAAC does not require re-encryption of any ciphertext when the attribute revocation happens, which means great improvement on the efficiency of attribute revocation. The analysis results show that TAAC is highly efficient, scalable, and flexible to applications in practice.

This article introduces a definition of privacy for Direct Anonymous Attestation schemes. The definition is expressed as an equivalence property which is suited to automated reasoning using Blanchet's ProVerif. The practicality of the definition is demonstrated by analysing the RSA-based Direct Anonymous Attestation protocol by Brickell, Camenisch & Chen. The analysis discovers a vulnerability in the RSA-based scheme which can be exploited by a passive adversary and, under weaker assumptions, corrupt administrators. A security fix is identified and the revised protocol is shown to satisfy our definition of privacy.

Adding a Schnorr signature to ElGamal encryption is a popular proposal aiming at thwarting chosen-ciphertext attacks by rendering the scheme plaintext-aware. However, there is no known security proof for the resulting scheme, at least not in a weaker model than the one obtained by combining the Random Oracle Model (ROM) and the Generic Group Model (Schnorr and Jakobsson, ASIACRYPT 2000). In this paper, we propose a very simple modification to Schnorr-Signed ElGamal encryption such that the resulting scheme is semantically secure under adaptive chosen-ciphertext attacks (IND-CCA2-secure) in the ROM under the Decisional Diffie-Hellman assumption. In fact, we even prove that our new scheme is plaintext-aware in the ROM as defined by Bellare et al. (CRYPTO'98). Interestingly, we also observe that Schnorr-Signed ElGamal is not plaintext-aware (again, for the definition of Bellare et al.) under the Computational Diffie-Hellman assumption. We show that our new scheme additionally achieves anonymity as well as robustness, a notion formalized by Abdalla et al. (TCC 2010) which captures the fact that it is hard to create a ciphertext that is valid under two different public keys. Finally, we study the hybrid variant of our new proposal, and show that it is IND-CCA2-secure in the ROM under the Computational Diffie-Hellman assumption when used with a symmetric encryption scheme satisfying the weakest security notion, namely ciphertext indistinguishability under one-time attacks (IND-OT-security).

Recently, the concept of Search in Encrypted Data (SED) has become a highlight in cryptography. A SED scheme enables a client to have third-party server(s) to perform certain search functionalities on his encrypted data. In this book chapter, we aim at conducting a systematic study on SED schemes. Firstly, we describe three application scenarios and identify the desirable security requirements. Secondly, we provide two orthogonal categorizations and review the related security models for each category of SED schemes. Thirdly, we analyze the practical issues related to SED schemes and identify some future research directions.

In this work we present a modification of a well-established measure of dependence appropriate for the analysis of stopping times for adversarial processes on cryptographic primitives. We apply this measure to construct generic criteria for the ideal behavior of fixed functions in both the random oracle and ideal permutation setting. More significantly, we provide a nontrivial extension of the notion of hash function indifferentiability, transporting the theory from the status of providing security arguments for protocols utilizing ideal primitives into the more realistic setting of protocol assurance with fixed functions. The methodology this measure introduces to indifferentiability analysis connects the security of a hash function with an indifferentiable mode to the security of the underlying compression function in a quantitative way; thus, we prove that dependence results on cryptographic primitives provide a direct means of determining the practical resistance or vulnerability of protocols employing such primitives.

In Africacrypt 2009, Galindo-Garcia proposed a lightweight identity-based signature (IBS) scheme based on the Schnorr signature. The construction is simple and claimed to be the most efficient IBS till date. The security is based on the discrete-log assumption and the security argument consists of two reductions: B1 and B2, both of which use the multiple-forking lemma to solve the discrete-log problem (DLP). In this work, we revisit the security argument given in. Our contributions are two fold: (i) we identify several problems in the original argument and (ii) we provide a detailed new security argument which allows significantly tighter reductions. In particular, we show that the reduction B1 in fails in the standard security model for IBS, while the reduction B2 is incomplete. To remedy these problems, we adopt a two-pronged approach. First, we sketch ways to fill the gaps by making minimal changes to the structure of the original security argument; then, we provide a new security argument. The new argument consists of three reductions: R1, R2 and R3 and in each of them, solving the DLP is reduced to breaking the IBS. R1 uses the general forking lemma together with the programming of the random oracles and Coron's technique. Reductions R2 and R3, on the other hand, use the multiple-forking lemma along with the programming of the random oracles. We show that the reductions R1 and R2 are significantly tighter than their original counterparts.

Hierarchical Key Assignment Schemes can be used to enforce access control policies by cryptographic means. In this paper, we present a new, enhanced security model for such schemes. We also give simple, efficient, and strongly-secure constructions for Hierarchical Key Assignment Schemes for arbitrary hierarchies using pseudorandom functions and forward-secure pseudorandom generators. We compare instantiations of our constructions with state-of-the-art Hierarchical Key Assignment Schemes, demonstrating that our new schemes possess an attractive trade-off between storage requirements and efficiency of key derivation.

The indifferentiability framework of Maurer, Renner, and Holenstein (MRH) has gained immense popularity in recent years and has proved to be a powerful way to argue security of cryptosystems that enjoy proofs in the random oracle model. Recently, however, Ristenpart, Shacham, and Shrimpton (RSS) showed that the composition theorem of MRH has a more limited scope than originally thought, and that extending its scope required the introduction of reset-indifferentiability, a notion which no practical domain extenders satisfy with respect to random oracles. In light of the results of RSS, we set out to rigorously tackle the specifics of indifferentiability and reset-indifferentiability by viewing the notions as special cases of a more general definition. Our contributions are twofold. Firstly, we provide the necessary formalism to refine the notion of indifferentiability regarding composition. By formalizing the definition of stage minimal games we expose new notions lying in between regular indifferentiability (MRH) and reset-indifferentiability (RSS). Secondly, we answer the open problem of RSS by showing that it is impossible to build any domain extender which is reset-indifferentiable from a random oracle. This result formally confirms the intuition that reset-indifferentiability is too strong of a notion to be satisfied by any hash function. As a consequence we look at the weaker notion of single-reset-indifferentiability, yet there as well we demonstrate that there are no ``meaningful'' domain extenders which satisfy this notion. Not all is lost though, as we also view indifferentiability in a more general setting and point out the possibility for different variants of indifferentiability.

Coin-tossing protocols are protocols that generate a random bit with uniform distribution. These protocols are used as a building block in many cryptographic protocols. Cleve [STOC 1986] has shown that if at least half of the parties can be malicious, then, in any r-round coin-tossing protocol, the malicious parties can cause a bias of Omega(1/r) to the bit that the honest parties output. However, for more than two decades the best known protocols had bias t/\sqrt{r}, where t is the number of corrupted parties. Recently, in a surprising result, Moran, Naor, and Segev [TCC 2009] have shown that there is an r-round two-party coin-tossing protocol with the optimal bias of O(1/r). We extend Moran et al. results to the multiparty model when less than 2/3 of the parties are malicious. The bias of our protocol is proportional to 1/r and depends on the gap between the number of malicious parties and the number of honest parties in the protocol. Specifically, for a constant number of parties or when the number of malicious parties is somewhat larger than half, we present an r-round m-party coin-tossing protocol with optimal bias of O(1/r).

SPDZ (pronounced “Speedz”) is the nickname of the MPC protocol of Damg°ard et al. from Crypto 2012. SPDZ provided various efficiency innovations on both the theoretical and practical sides compared to previous work in the preprocessing model. In this paper we both resolve a number of open problems with SPDZ; and present several theoretical and practical improvements to the protocol. In detail, we start by designing and implementing a covertly secure key generation protocol for distributed BGV secret keys. In prior work this was assumed to be provided by a given setup functionality. Protocols for distributingBGV secret keys are likely to be of wider applicability than to the SPDZ protocol alone. We then construct both a covertly and actively secure preprocessing phase, both of which compare favourably with previous work in terms of efficiency and provable security. We also build a new online phase, which solves a major problem of the SPDZ protocol: namely prior to this work preprocessed data could be used for only one function evaluation and then had to be recomputed from scratch for the next evaluation, while our online phase can support reactive functionalities. This improvement comes mainly from the fact that our construction does not require players to reveal the MAC keys to check correctness of MAC’d values. Since our focus is also on practical instantiations, our implementation offloads as much computation as possible into the preprocessing phase, thus resulting in a faster online phase. Moreover, a better analysis of the parameters of the underlying cryptoscheme and a more specific choice of the field where computation is performed allow us to obtain a better optimized implementation. Improvements are also due to the fact that our construction is in the random oracle model, and the practical implementation is multi-threaded.

Recently, Fang et al. [6] introduced an interactive(bidirectional) conditional proxy re-encryption(C-PRE) scheme such that a proxy can only convert ciphertexts that satisfy access policy set by a delegator. Their scheme supports monotonic access policy expressed by “OR” and “AND” gates. In addition, their scheme is called interactive since generation of re-encryption keys requires interaction between the delegator and delegatee. In this paper, we study the problem of constructing a unidirectional(non-interactive) C-PRE scheme supporting non-monotonic access policy expressed by “NOT”, “OR” and “AND” gates. A security model for unidirectional C-PRE schemes is also proposed in this paper. To yield a unidirectional C-PRE scheme supporting non-monotonic access policy, we extend the unidirectional PRE scheme presented by Libert et al. [8] by using the ideas from the non-monotonic attributed based encryption (ABE) scheme presented by Ostrovsky et al. [9]. Furthermore, the security of our C-PRE scheme is proved under the modified 3-weak Decision Bilinear Diffie-Hellman Inversion assumption in the standard model.

SM3~\cite{SM3hf} is the Chinese cryptographic hash standard which was announced in 2010 and designed by Wang $et\ al.$. It is based on the Merkle-Damgård design and its compression function can be seen as a block cipher used in Davies-Meyer mode. It uses message block of length 512 bits and outputs hash value of length 256 bits. This paper studies the security of SM3 hash function against preimage attack and pseudo-collision attack. We propose preimage attacks on 29-step and 30-step SM3, and pseudo-preimage attacks on 31-step and 32-step SM3 out of 64 steps. The complexities of these attacks are $2^{245}$ 29-step operations, $2^{251.1}$ 30-step operations, $2^{245}$ 31-step operations and $2^{251.1}$ 32-step operations, respectively. These (pseudo) preimage attacks are all from the first step of the reduced SM3. Meanwhile, these (pseudo) preimage attacks can be converted into pseudo-collision attacks on SM3 reduced to 29 steps, 30 steps, 31 steps and 32 steps with complexities of $2^{122}$, $2^{125.1}$, $2^{122}$ and $2^{125.1}$ respectively. As far as we know, the previously best known preimage attacks on SM3 cover 28 steps (from the first step) and 30 steps (from the 7-th step), and there is no publicly published result on (pseudo) collision attack on SM3.

We count ]B, C]-grained, k-factor integers which are simultaneously B-rough and C-smooth and have a fixed number k of prime factors. Our aim is to exploit explicit versions of the prime number theorem as much as possible to get good explicit bounds for the count of such integers. This analysis was inspired by certain inner procedures in the general number field sieve. The result should at least provide some insight in what happens there. We estimate the given count in terms of some recursively defined functions. Since they are still difficult to handle, only another approximation step reveals their orders. Finally, we use the obtained bounds to perform numerical experiments that show how good the desired count can be approximated for the parameters of the general number field sieve in the mentioned inspiring application.

Generalized signcryption (GSC) scheme can adaptively work as an encryption scheme, a signature scheme or a signcryption scheme with only one algorithm. It is very suitable for storage-constrained environments. In this paper, we analyze a multi-receiver GSC scheme, and show that it cannot achieve indistinguishability-adaptive chosen ciphertext attack (IND-CCA2) secure in the pure encryption mode and hybrid encryption mode. We further propose a revised version of the scheme, which resolves the security issues of the original scheme without sacrificing its high efficiency and simple design. Our improved scheme can be proved to be IND-CCA2 secure and existentially unforgeable-adaptive chosen message attack (EUF-CMA) under computational Diffie-Hellman (CDH) assumption.

We present high performance non-deterministic fully-homomorphic methods for practical randomization of data (over commutative ring), and symmetric-key encryption of random mod-N data (over ring of reidues mod-N) well suited for crypto applications. These methods secure, for example, the multivariate input or the coefficients of a polynomial function running in an open untrusted environment. We show that random plaintext is the sufficient condition for proof of security for the homomorphic encryption. The efficient nature of the methods - one large-numbers multiplication per encryption and six for the product of two encrypted values - motivates and enables the use of low cost collaborative security platforms for crypto applications such as keyed-hash or private key derivation algorithms. Such a platform is comprised of a low-cost and low performance security element supported by an untrusted high performance server running the homomorpic algorithms. The methods employed may also provide enhanced protection for some existing crypto algorithms against certain attacks. Specifically, it is shown how to secure OSS public-key signature against Pollard attack. Further, we demonstrate how the homomorphic randomization of data can offer protection for an AES-key against side-channel attacks. Finally, the methods provide both fault detection and verification of computed-data integrity.

This work presents a study of the complexity of the Blum-Kalai-Wasserman (BKW) algorithm when applied to the Learning with Errors (LWE) problem, by providing refined estimates for the data and computational effort requirements for solving concrete instances of the LWE problem. We apply this refined analysis to suggested parameters for various LWE-based cryptographic schemes from the literature and compare with alternative approaches based on lattice reduction. As a result, we provide new upper bounds for the concrete hardness of these LWE-based schemes. Rather surprisingly, it appears that BKW algorithm outperforms known estimates for lattice reduction algorithms starting in dimension n &#8776; 250 when LWE is reduced to SIS. However, this assumes access to an unbounded number of LWE samples.

Attribute-Based Encryption (ABE) is a promising cryptographic primitive which significantly enhances the versatility of access control mechanisms. Due to the high expressiveness of ABE policies, the computational complexities of ABE key-issuing (by Attribute Authorities (AAs)) and decryption (by eligible users) are getting prohibitively high. Despite that the existing Outsourced ABE solutions are able to offload some intensive computing tasks to a third party, for example, a cloud, so to relieve the local burden of eligible users during decryption, the high computational complexity of the key-issuing at the AAs has yet to be addressed, while an ABE system will continue to grow with more users being included, and with the user revocation being considered in practice which will trigger more key (re-)issuing. Aiming at tackling the challenges above, for the first time, we propose a Secure Outsourced ABE system, which not only supports secure outsourced decryption, but also provides secure outsourced key-issuing. Unlike the current outsourced ABE systems, our new method offloads all access policy and attribute related operations in the key-issuing process or decryption to a Key Generation Service Provider (KGSP) and a Decryption Service Provider (DSP), respectively, leaving only a constant number of simple operations for the AAs and eligible users to perform locally. Furthermore, we show that both outsourcing processes (to KGSP and to DSP) are secure, namely, the KGSP and the DSP would not be able to recover the keys or decrypt the ciphertexts, respectively. In addition, we consider the scenario that a KGSP or DSP may be dishonest and could maliciously generate some incorrect returning values rather than following the outsourced operations. Therefore, in this paper, we also propose another ABE construction which allows the AAs and eligible users to check the correctness of outsourced operations in an efficient way. The security of the construction is analyzed under a recently formalized model called Refereed Delegation of Computation (RDoC).

A double-block-length (DBL) hash mode of block ciphers, MJH has been proved to be collision-resistant in the ideal cipher model upto $2^{2n/3- \log n}$ queries. In this paper we provide first cryptanalytic results for MJH. We show that a collision attack on MJH has the time complexity below the birthday bound. When block ciphers with 128-bit blocks are used, it has time complexity around $2^{124}$, which is to be compared to the birthday attack having complexity $2^{128}$. We also give a preimage attack on MJH. It has the time complexity of $2^{3n/2+1}$ with $n$-bit block ciphers, which is to be compared to the brute force attack having complexity $2^{2n}$.

In this paper, we provide some cryptanalytic results for double-block-length (DBL) hash modes of block ciphers, MDC-4. Our preimage attacks follow the framework of Knudsen et al.'s time/memory trade-off preimage attack on MDC-2. We find how to apply it to our objects. When the block length of the underlying block cipher is $n$ bits, the most efficient preimage attack on MDC-4 requires time and space about $2^{3n/2}$, which is to be compared to the previous best known preimage attack having time complexity of $2^{7n/4}$. Additionally, we propose an enhanced version of MDC-4, MDC-4$^*$ based on a simple idea. It is secure against our preimage attack and previous attacks and has the same efficiency as MDC-4.

This paper presents the Tate pairing computation on generalized Huff curves proposed by Wu and Feng in \cite{Wu}. In fact, we extend the results of the Tate pairing computation on the standard Huff elliptic curves done previously by Joye, Tibouchi and Vergnaud in \cite{Joux}. We show that the addition step of the Miller loop can be performed in $1\mathbf{M}+(k+15)\mathbf{m}+2\mathbf{c}$ and the doubling one in $1\mathbf{M} + 1\mathbf{S} + (k + 12) \mathbf{m} + 5\mathbf{s} + 2\mathbf{c}$ on the generalized Huff curve.

We formalize a new cryptographic primitive, Message-Locked Encryption (MLE), where the key under which encryption and decryption are performed is itself derived from the message. MLE provides a way to achieve secure deduplication (space-efficient secure outsourced storage), a goal currently targeted by numerous cloud-storage providers. We provide definitions both for privacy and for a form of integrity that we call tag consistency. Based on this foundation, we make both practical and theoretical contributions. On the practical side, we provide ROM security analyses of a natural family of MLE schemes that includes deployed schemes. On the theoretical side the challenge is standard model solutions, and we make connections with deterministic encryption, hash functions secure on correlated inputs and the sample-then-extract paradigm to deliver schemes under different assumptions and for different classes of message sources. Our work shows that MLE is a primitive of both practical and theoretical interest.

The Transport Layer Security (TLS) protocol is the most widely used security protocol on the Internet. It supports negotiation of a wide variety of cryptographic primitives through different cipher suites, various modes of client authentication, and additional features such as renegotiation. Despite its widespread use, only recently has the full TLS protocol been proven secure, and only the core cryptographic protocol with no additional features. These additional features have been the cause of several practical attacks on TLS. In 2009, Ray and Dispensa demonstrated how TLS renegotiation allows an attacker to splice together its own session with that of a victim, resulting in a man-in-the-middle attack on TLS-reliant applications such as HTTP. TLS was subsequently patched with two defence mechanisms for protection against this attack. We present the first formal treatment of renegotiation in secure channel establishment protocols. We add optional renegotiation to the authenticated and confidential channel establishment model of Jager et al., an adaptation of the Bellare--Rogaway authenticated key exchange model. We describe the attack of Ray and Dispensa on TLS within our model. We show generically that the proposed fixes for TLS offer good protection against renegotiation attacks, and give a simple new countermeasure that provides renegotiation security for TLS even in the face of stronger adversaries.

Secure two-party and multiparty computation has long stood at the center of the foundations of theoretical cryptography. Recently, however, interest has grown regarding the efficiency of such protocols and their application in practice. As a result, there has been significant progress on this problem and it is possible to actually carry out secure computation for non-trivial tasks on reasonably large inputs. Part of this research goal of making secure computation practical has also involved \emph{implementations}. Such implementations are of importance for two reasons: first, they demonstrate the real efficiency of known and new protocols; second, they deepen our understanding regarding where the bottlenecks in efficiency lie. However, it is very hard to compare between implementations by different research groups since they are carried out on different platforms and using different infrastructures. In addition, most implementations have been carried out without the goal of code reuse, and so are not helpful to other researchers. The difficulty of beginning implementation projects is further compounded by the fact that existing cryptographic libraries (like openSSL, Bouncy Castle, and others) are tailored for tasks like encryption, authentication and key-exchange, and not for secure computation. We have developed SCAPI in order to address these problems. SCAPI is an \emph{open-source} general library tailored for secure computation implementations. Our aim in developing SCAPI has been to provide a flexible and efficient infrastructure for secure computation implementations, that is both easy to use and robust. Great care has been taken in the design of the library, in writing clean code, and in documentation. We hope that this library will be useful to the community interested in implementations of secure protocols, and will help to promote the goal of making secure computation practical.

Key management in multicast dynamic groups, where users can leave or join at their ease is one of the most crucial and essential part of secure communication. Various efficient management strategies have been proposed during last decade that aim to decrease encryption costs and transmission overheads. In this report, two different types of key management schemes are proposed. First proposed scheme is based on One-way function tree (OFT). The proposed scheme fulfills the security gaps that have been pointed out in recent years. Second proposed scheme is based on logical key hierarchy (LKH). This proposed scheme provides better performance for, rather inflexible and expensive, LKH scheme.

In a group signature scheme, group members are able to sign on behalf of the group. Since the introduction of this cryptographic authentication mechanism, several schemes have been proposed but only few of them enjoy a security in the standard model. Moreover, those provided in the standard model suffer the recourse to non standard-assumptions, or the expensive cost and bandwidth of the resulting signature. We provide three practical group signature schemes that are provably secure in the standard model under standard assumptions. The three schemes permit dynamic enrollment of new members while keeping a constant size for both keys and group signatures, and they improve the state-of-the art by several orders of magnitude.

We present explicit formulae and complexities of bit-parallel shifted polynomial basis (SPB) squarers in finite field $GF(2^{n})$s generated by general irreducible trinomials $x^{n}+x^{k}+1$ ($0< k <n$) and type-II irreducible pentanomials $x^{n}+x^{k+1}+x^{k}+x^{k-1}+1$ ($3<k<(n-3)/2$). The complexities of the proposed squarers match or slightly outperform the previous best results. These formulae can also be used to design polynomial basis Montgomery squarers without any change. Furthermore, we show by examples that XOR gate numbers of SPB squarers are different when different shift factors in the SPB definition, i.e., parameter $v$ in ${\{}x^{i-v}|0\leq i\leq n-1 {\}}$, are used. This corrects previous misinterpretation.

We further the study of order-preserving symmetric encryption (OPE), a primitive for allowing efficient range queries on encrypted data, recently initiated (from a cryptographic perspective) by Boldyreva et al.~(Eurocrypt '09). First, we address the open problem of characterizing what encryption via a random order-preserving function (ROPF) leaks about underlying data (ROPF being the ``ideal object'' in the security definition, POPF, satisfied by their scheme.) In particular, we show that, for a database of randomly distributed plaintexts and appropriate choice of parameters, ROPF encryption leaks neither the precise value of any plaintext nor the precise distance between any two of them. The analysis here introduces useful new techniques. On the other hand, we show that ROPF encryption leaks approximate value of any plaintext as well as approximate distance between any two plaintexts, each to an accuracy of about square root of the domain size. We then study schemes that are not order-preserving, but which nevertheless allow efficient range queries and achieve security notions stronger than POPF. In a setting where the entire database is known in advance of key-generation (considered in several prior works), we show that recent constructions of ``monotone minimal perfect hash functions'' allow to efficiently achieve (an adaptation of) the notion of IND-O(rdered) CPA also considered by Boldyreva et al., which asks that \emph{only} the order relations among the plaintexts is leaked. Finally, we introduce {\em modular} order-preserving encryption (MOPE), in which the scheme of Boldyreva et al. is prepended with a random shift cipher. MOPE improves the security of OPE in a sense, as it does not leak any information about plaintext location. We clarify that our work should not be interpreted as saying the original scheme of Boldyreva et al., or the variants that we introduce, are ``secure'' or ``insecure.'' Rather, the goal of this line of research is to help practitioners decide whether the options provide a suitable security-functionality tradeoff for a given application.

We initiate the cryptographic study of order-preserving symmetric encryption (OPE), a primitive suggested in the database community by Agrawal et al.~(SIGMOD '04) for allowing efficient range queries on encrypted data. Interestingly, we first show that a straightforward relaxation of standard security notions for encryption such as indistinguishability against chosen-plaintext attack (IND-CPA) is unachievable by a practical OPE scheme. Instead, we propose a security notion in the spirit of pseudorandom functions (PRFs) and related primitives asking that an OPE scheme look ``as-random-as-possible" subject to the order-preserving constraint. We then design an efficient OPE scheme and prove its security under our notion based on pseudorandomness of an underlying blockcipher. Our construction is based on a natural relation we uncover between a random order-preserving function and the hypergeometric probability distribution. In particular, it makes black-box use of an efficient sampling algorithm for the latter.

The block cipher modes of operation that are widely used (CBC, CTR, CFB) are secure up to the birthday bound; that is, if $w2^{w}$ or fewer bits of data are encrypted with a $w$-bit block cipher. However, the detailed security properties close to this bound are not widely appreciated, despite the fact that $64$-bit block ciphers are sometimes used in that domain. This work addresses the issue by analyzing plaintext-recovery attacks that are effective close to that bound. We describe possible-plaintext attacks, which can learn unknown plaintext values that are encrypted with CBC, CFB, or OFB. We also introduce \textit{impossible plaintext} cryptanalysis, which can recover information encrypted with CTR, and can improve attacks against the aforementioned modes as well. These attacks work at the birthday bound, or even slightly below that bound, when the target plaintext values are encrypted under a succession of keys.

The area of proof-based verified computation (outsourced computation built atop probabilistically checkable proofs and cryptographic machinery) has lately seen renewed interest. Although recent work has made great strides in reducing the overhead of naive applications of the theory, these schemes still cannot be considered practical. A core issue is that the work for the prover is immense, in general; it is near-practical only for hand-compiled computations that can be expressed in special forms. This paper addresses that problem. Provided one is willing to batch verification, we develop a protocol that achieves the efficiency of the best manually constructed protocols in the literature yet applies to most computations. Our protocol is built on the observation that the recently-proposed QAPs of Gennaro et al. (ePrint 2012/215) yield a linear PCP that works with the efficient argument protocol of Setty et al. (ePrint 2012/598, Security 2012, NDSS 2012), itself based on the proposal of Ishai et al. (CCC 2007). The consequence is a prover whose total work is not much more than \emph{linear} in the running time of the computation. We implement the protocol in the context of a built system that includes a compiler and a GPU implementation. The result, as indicated by an experimental evaluation, is a system that is {\em almost} usable for real problems---without special-purpose tailoring.

In this paper, we evaluate the security of lightweight block ciphers PRESENT, Piccolo and LED against biclique cryptanalysis. To recover the secret key of PRESENT-80/128, our attacks require $2^{79.76}$ full PRESENT-80 encryptions and $2^{127.91}$ full PRESENT-128 encryptions, respectively. Our attacks on Piccolo-80/128 require computational complexities of $2^{79.13}$ and $2^{127.35}$, respectively. The attack on a $29$-round reduced LED-64 needs $2^{63.58}$ 29-round reduced LED-64 encryptions. In the cases of LED-80/96/128, we propose the attacks on two versions. First, to recover the secret key of $45$-round reduced LED-80/96/128, our attacks require computational complexities of $2^{79.45}, 2^{95.45}$ and $2^{127.45}$, respectively. To attack the full version, we require computational complexities of $2^{79.37}, 2^{95.37}$ and $2^{127.37}$, respectively. However, in these cases, we need the full codebook. These results are superior to known biclique cryptanalytic results on them.

Subset sum or Knapsack problems of dimension $n$ are known to be hardest for knapsacks of density close to 1.These problems are NP-hard for arbitrary $n$. One can solve such problems either by lattice basis reduction or by optimized birthday algorithms. Recently Becker, Coron, Jou } [BCJ10] present a birthday algorithm that follows Schroeppel, Shamir [SS81], and Howgrave-Graham, Joux [HJ10]. This algorithm solves 50 random knapsacks of dimension 80 and density close to 1 in roughly 15 hours on a 2.67 GHz PC. We present an optimized lattice basis reduction algorithm that follows Schnorr, Euchne} [SE03] using pruning of Schnorr, Hörner [SH95] that solves such random knapsacks of dimension 80 on average in less than a minute, and 50 such problems all together about 9.4 times faster and using much less space than [BCJ10] on another 2.67 GHz PC.

Verifiable secret sharing (VSS) is a vital primitive in secure distributed computing. It allows an untrusted dealer to verifiably share a secret among n parties in the presence of an adversary controlling at most t of them. VSS in the synchronous communication model has received tremendous attention in the cryptographic research community. Nevertheless, recent interest in deploying secure distributed computing over the Internet requires going beyond the synchronous communication model and thoroughly investigating VSS in the asynchronous communication model. In this work, we consider the communication complexity of asynchronous VSS in the com- putational setting for the optimal resilience of n = 3t + 1. The best known asynchronous VSS protocol by Cachin et al. has O(n^2) message complexity and O(kn^3) communication complexity, where k is a security parameter corresponding to the size of the secret. We close the linear complexity gap between these two measures for asynchronous VSS by presenting two protocols with O(n^2) message complexity and O(kn^2) communication complexity. Our first protocol satisfies the standard VSS definition, and can be used in stand-alone VSS scenarios as well as in applications such as Byzantine agreement. Our second and more intricate protocol satisfies a stronger VSS definition, and is useful in all VSS applications including multiparty computation and threshold cryptography.

This paper introduces a new key establishment scheme aiming at fully collusion-resistant identity-based symmetric-key agreement. In an identity-based pairwise key agreement scheme, a Trusted Third Party (TTP) manages the system and securely provides any node, e.g., Alice or Bob, with private keying materials. Alice can generate a pairwise key with Bob given her own secret keying material and Bob's identity. The full collusion resistance property would ensure that the scheme remains secure even if arbitrarily many devices collude or are compromised. Our scheme, the HIMMO algorithm, relies on two design concepts: Hiding Information and Mixing Modular Operations. Hiding information is related to the Noisy Interpolation Problem; the Mixing Modular Operations problem seems to be a new hard problem. We describe our scheme, the security of its underlying design principles and give order of magnitude estimations for secure configuration parameters. For these parameters, we show that our prototypic implementation of HIMMO on the 8-bit CPU ATmega128L can generate 128-bit keys in less than 7 ms based on an algorithm fitting in 428 B and with secret keying materials of size 656 B.

An increasing number of embedded security applications---which traditionally have been heavily reliant on secret and/or proprietary solutions---apply the principle of open evaluation. A recent example is the specification of an open security protocol stack for car immobilizer applications by Atmel, which has been presented at ESCAR 2010. This stack is primarily intended to be used in conjunction with automotive transponder chips of this manufacturer, but could in principle be deployed on any suitable type of transponder chip. In this paper we re-evaluate the security of this protocol stack. We were able to uncover a number of security vulnerabilities. We show that an attacker with a cheap standard reader close to such a car key can track it, lock sections of its EEPROM, and even render its immobilizer functionality completely useless. After eavesdropping on a genuine run of the authentication protocol between the car key and the car, an attacker is enabled to read and write the memory of the car key. Furthermore, we point out the threats of relay attacks and session hijacking, which require slightly more elaborate attack setups. For each of the indicated attacks we propose possible fixes and discuss their overhead.

We revisit hardness-preserving constructions of a pseudo-random function (PRF) from any length doubling pseudo-random generator (PRG) when there is a non-trivial upper bound $q$ on the number of queries that the adversary can make to the PRF. Very recently, Jain, Pietrzak, and Tentes (TCC 2012) gave a hardness-preserving construction of a PRF that makes only $O(\log q)$ calls to the underlying PRG when $q = 2^{n^\epsilon}$ and $\epsilon \geq \frac{1}{2}$. This dramatically improves upon the efficiency of the construction of Goldreich, Goldwasser, and Micali (FOCS 1984). However, they explicitly left open the question of whether such constructions exist when $\epsilon < \frac{1}{2}$. In this work, we give constructions of PRFs that make only $O(\log q)$ calls to the underlying PRG when $q = 2^{n^\epsilon}$, for $0<\epsilon<1$; our PRF outputs $O(n^{2\epsilon})$ bits (on every input), as opposed to the construction of Jain {\em et al.} that outputs $n$ bits. That is, our PRF is not length preserving; however it outputs more bits than the PRF of Jain {\em et al.} when $\epsilon>\frac{1}{2}$. We obtain our construction through the use of information-theoretic tools such as {\em almost} $\alpha$-wise independent hash functions coupled with a novel proof strategy.

We introduce the \emph{linear centralizer method}, and use it to devise a provable polynomial time solution of the Commutator Key Exchange Problem, the computational problem on which, in the passive adversary model, the security of the Anshel--Anshel--Goldfeld 1999 \emph{Commutator} key exchange protocol is based. We also apply this method to the computational problem underlying the \emph{Centralizer} key exchange protocol, introduced by Shpilrain and Ushakov in 2006. This is the first provable polynomial time cryptanalysis of the Commutator key exchange protocol, hitherto the most important key exchange protocol in the realm of noncommutative-algebraic cryptography, and the first cryptanalysis (of any kind) of the Centralizer key exchange protocol. Unlike earlier cryptanalyses of the Commutator key exchange protocol, our cryptanalyses cannot be foiled by changing the distributions used in the protocol.

In this paper we prove an explicit formula for an arithmetic intersection number on the Siegel moduli space of abelian surfaces, generalizing the work of Bruinier-Yang and Yang. These intersection numbers allow one to compute the denominators of Igusa class polynomials, which has important applications to the construction of genus 2 curves for use in cryptography. Bruinier and Yang conjectured a formula for intersection numbers on an arithmetic Hilbert modular surface, and as a consequence obtained a conjectural formula for the intersection number relevant to denominators of Igusa class polynomials under strong assumptions on the ramification of the primitive quartic CM field K. Yang later proved this conjecture assuming that the ring of integers is freely generated by one element over the ring of integers of the real quadratic subfield. In this paper, we prove a formula for the intersection number for more general primitive quartic CM fields, and we use a different method of proof than Yang. We prove a tight bound on this intersection number which holds for all primitive quartic CM fields. As a consequence, we obtain a formula for a multiple of the denominators of the Igusa class polynomials for an arbitrary primitive quartic CM field. Our proof entails studying the Embedding Problem posed by Goren and Lauter and counting solutions using our previous article that generalized work of Gross-Zagier and Dorman to arbitrary discriminants.

A major general paradigm in cryptography is the following argument: Whatever an adversary could do in the real world, it could just as well do in the ideal world. The standard interpretation of ``just as well'' is that the translation from the real to the ideal world, usually called a simulator, is achieved by a probabilistic polynomial-time algorithm. This means that a polynomial blow-up of the adversary's time and memory requirements is considered acceptable. In certain contexts this interpretation of ``just as well'' is inadequate, for example if the concrete amount of memory used by the adversary is relevant. The example of Ristenpart et al. (Eurocrypt 2011), for which the original indifferentiability notion introduced by Maurer et al. (Eurocrypt 2004) is shown to be insufficient, turns out to be exactly of this type. It requires a fine-grained statement about the adversary's memory capacity, calling for a generalized treatment of indifferentiability where specific resource requirements can be taken into account by modeling them explicitly. We provide such treatment and employ the new indifferentiability notion to prove lower bounds on the memory required by any simulator in a domain extension construction of a public random function. In particular, for simulators without memory, even domain extension by a single bit turns out to be impossible. Moreover, for the construction of a random oracle from an ideal compression function, memory roughly linear in the length of the longest query is required. This also implies the impossibility of such domain extension in any multi-party setting with potential individual misbehavior by parties (i.e., no central adversary).

Time memory tradeoff algorithms are tools for inverting one-way functions, and they are often used to recover passwords from unsalted password hashes. There are many publicly known tradeoff algorithms, and the rainbow tradeoff is widely believed to be the best algorithm. This work provides an accurate complexity analysis of the non-perfect table version of the fuzzy rainbow tradeoff algorithm, which has not yet received much attention. It is shown that, when the pre-computation cost and the online efficiency are both taken into consideration, the non-perfect fuzzy rainbow tradeoff is preferable to the original rainbow tradeoff in many situations.

There has been considerable recent interest in "cloud storage'' wherein a user asks a server to store a large file. One issue is whether the user can verify that the server is actually storing the file, and typically a challenge-response protocol is employed to convince the user that the file is indeed being stored correctly. The security of these schemes is phrased in terms of an extractor which will recover or retrieve the file given any "proving algorithm'' that has a sufficiently high success probability. This paper treats proof-of-retrievability schemes in the model of unconditional security, where an adversary has unlimited computational power. In this case retrievability of the file can be modelled as error-correction in a certain code. We provide a general analytical framework for such schemes that yields exact (non-asymptotic) reductions that precisely quantify conditions for extraction to succeed as a function of the success probability of a proving algorithm, and we apply this analysis to several archetypal schemes. In addition, we provide a new methodology for the analysis of keyed POR schemes in an unconditionally secure setting, and use it to prove the security of a modified version of a scheme due to Shacham and Waters under a slightly restricted attack model, thus providing the first example of a keyed POR scheme with unconditional security. We also show how classical statistical techniques can be used to evaluate whether the responses of the prover are accurate enough to permit successful extraction. Finally, we prove a new lower bound on storage and communication complexity of POR schemes.

We describe plausible lattice-based constructions with properties that approximate the sought-after multilinear maps in hard-discrete-logarithm groups, and show an example application of such multilinear maps that can be realized using our approximation. The security of our constructions relies on seemingly hard problems in ideal lattices, which can be viewed as extensions of the assumed hardness of the NTRU function.

The discrete logarithm problem with auxiliary inputs is to solve~$\alpha$ for given elements $g, g^\alpha, \ldots, g^{\alpha^d}$ of a cyclic group $G=\langle g \rangle$ of prime order~$p$. The best-known algorithm, proposed by Cheon in 2006, solves $\alpha$ in the case of $d | (p\pm 1)$ with running time of $O\left( \sqrt{p/d} + d^i \right)$ group exponentiations~($i=1$ or $1/2$ depending on the sign). There have been several attempts to generalize this algorithm in the case of $\Phi_k(p)$ for $k \ge 3$, but it has been shown, by Kim, Cheon and Lee, that they cannot have better complexity than the usual square root algorithms. We propose a new algorithm to solve the DLPwAI. The complexity of the algorithm is determined by a chosen polynomial $f \in \F_p[x]$ of degree $d$. We show that the proposed algorithm has a running time of $\widetilde O\left( \sqrt{p / \tau_f} +d \right)$ group exponentiations, where~$\tau_f$ is the number of absolutely irreducible factors of $f(x)-f(y)$. We note that it is always smaller than $\widetilde O(p^{1/2})$. To obtain a better complexity of the algorithm, we investigate an upper bound of $\tau_f$ and try to find polynomials that achieve the upper bound. We can find such polynomials in the case of $d|(p\pm 1)$. In this case, the algorithm has a running time of $\widetilde O\left(\sqrt{p/d} +d \right)$ group operations which corresponds with the lower bound in the generic group model. On the contrary, we show that no polynomial exists that achieves the upper bound in the case of $d \vert\Phi_3(p)=p^2+p+1$. As an independent interest, we present an analysis of a non-uniform birthday problem. Precisely, we show that a collision occurs with a high probability after $O\big( \frac{1}{ \sqrt{\sum_{k} {w_k}^2} } \big)$ samplings of balls, where the probability $w_k$ of assigning balls to the bin $k$ is arbitrary.

Secure sketches and fuzzy extractors enable the use of biometric data in cryptographic applications by correcting errors in noisy biometric readings and producing cryptographic materials suitable for authentication, encryption, and other purposes. Such constructions work by producing a public sketch, which is later used to reproduce the original biometric and all derived information exactly from a noisy biometric reading. It has been previously shown that release of multiple sketches associated with a single biometric presents security problems for certain constructions. We continue the analysis to demonstrate that all other constructions in the literature are also prone to similar problems and cannot be safely reused. To mitigate the problem, we propose for each user to store one short secret string for all possible uses of her biometric, and show that simple constructions in the computational setting have numerous advantageous security and usability properties under standard hardness assumptions. Our constructions are generic in that they can be used with any existing secure sketch as a black box.

We give three new algorithms to solve the ``isomorphism of polynomial'' problem, which was underlying the hardness of recovering the secret-key in some multivariate trapdoor one-way functions. In this problem, the adversary is given two quadratic functions, with the promise that they are equal up to linear changes of coordinates. Her objective is to compute these changes of coordinates, a task which is known to be harder than Graph-Isomorphism. Our new algorithm build on previous work in a novel way. Exploiting the birthday paradox, we break instances of the problem in time $q^{2n/3}$ (rigorously) and $q^{n/2}$ (heuristically), where $q^n$ is the time needed to invert the quadratic trapdoor function by exhaustive search. These results are obtained by turning the algebraic problem into a combinatorial one, namely that of recovering partial information on an isomorphism between two exponentially large graphs. These graphs, derived from the quadratic functions, are new tools in multivariate cryptanalysis.

We construct the first Message Authentication Codes (MACs) that are existentially unforgeable against a quantum chosen message attack. These chosen message attacks model a quantum adversary’s ability to obtain the MAC on a superposition of messages of its choice. We begin by showing that a quantum secure PRF is sufficient for constructing a quantum secure MAC, a fact that is considerably harder to prove than its classical analogue. Next, we show that a variant of Carter-Wegman MACs can be proven to be quantum secure. Unlike the classical settings, we present an attack showing that a pair-wise independent hash family is insufficient to construct a quantum secure one-time MAC, but we prove that a four-wise independent family is sufficient for one-time security.

Attribute-based signature (ABS) is a useful variant of digital signature, which enables users to sign messages over attributes without revealing any information other than the fact that they have attested to the messages. However, heavy computational cost is required during signing in existing work of ABS, which grows linearly with the size of the predicate formula. As a result, this presents a significant challenge for resource-limited users (such as mobile devices) to perform such heavy computation independently. Aiming at tackling the challenge above, we propose and formalize a new paradigm called OABS, in which the computational overhead at user side is greatly reduced through outsourcing such intensive computation to an untrusted signing-cloud service provider (S-CSP). Furthermore, we apply this novel paradigm to existing ABS to reduce complexity and present two schemes, i) in the first OABS scheme, the number of exponentiations involving in signing is reduced from $O(d)$ to $O(1)$ (nearly three), where $d$ is the upper bound of threshold value defined in the predicate; ii) our second scheme is built on Herranz et al's construction with constant-size signatures. The number of exponentiations in signing is reduced from $O(d^2)$ to $O(d)$ and the communication overhead is $O(1)$. Security analysis demonstrates that both OABS schemes are secure in terms of the unforgeability and attribute-signer privacy definitions specified in the proposed security model. Finally, to allow for high efficiency and flexibility, we discuss extensions of OABS and show how to achieve accountability and outsourced verification as well.

We present new constructions of leakage-resilient cryptosystems, which remain provably secure even if the attacker learns some arbitrary partial information about their internal secret key. For any polynomial $\ell$, we can instantiate these schemes so as to tolerate up to $\ell$ bits of leakage. While there has been much prior work constructing such leakage-resilient cryptosystems under concrete number-theoretic and algebraic assumptions, we present the first schemes under general and minimal assumptions. In particular, we construct: - Leakage-resilient public-key encryption from any standard public-key encryption. - Leakage-resilient weak pseudorandom functions, symmetric-key encryption}, and message-authentication codes from any one-way function. These are the first constructions of leakage-resilient symmetric-key primitives that do not rely on public-key assumptions. We also get the first constructions of leakage-resilient public-key encryption from ``search assumptions'', such as the hardness of factoring or CDH. Although our schemes can tolerate arbitrarily large amounts of leakage, the tolerated rate of leakage (defined as the ratio of leakage-amount to key-size) is rather poor in comparison to prior results under specific assumptions. As a building block of independent interest, we study a notion of weak hash-proof systems in the public-key and symmetric-key settings. While these inherit some of the interesting security properties of standard hash-proof systems, we can instantiate them under general assumptions.

Several companies exploit medical data to better understand medication consumption patterns. Their analyses are useful to various health actors in order to enhance health care management. In this article, we focus on a configuration which allows a network of pharmacies to forward medical data to a private company in order to construct a database. Pharmacies must operate in full compliance with legal requirements in terms of confidentiality and privacy. We show that our solution fulfills all the requirements. Our work leads us to introduce the concept of generalized discrete logarithm problem which is proven to be as hard as the discrete logarithm problem.

Imai and Matsumoto introduced a public key cryptosystem based on multivariate quadratic polynomials. In a simplified way, the essence of their cryptosystem can be described in the following way: Start with a central monomial F. The secret key comprises two invertible linear transformations T and L such that TFL is the public key. In order to study equivalent public keys it is natural to ask for the "invariant" secret keys (T,L), i.e. TFL=F. Lin, Faugere, Perret and Wang give a partial answer to this question by considering such L which fulfill FL=F. In this paper we will determine all invariant invertible linear transformations (T,L).

Assuming solely the existence of one-way functions, we show how to construct Garbled RAM Programs (GRAM) where its size only depends on fixed polynomial in the security parameter times the program running time. We stress that we avoid converting the RAM programs into circuits. As an example, our techniques implies the first garbled binary search program (searching over sorted encrypted data stored in a cloud) which is poly-logarithmic in the data size instead of linear. Our result requires the existence of one-way function and enjoys the same non-interactive properties as Yao's original garbled circuits.

We present a new block cipher LED. While dedicated to compact hardware implementation, and offering the smallest silicon footprint among comparable block ciphers, the cipher has been designed to simultaneously tackle three additional goals. First, we explore the role of an ultra-light (in fact non-existent) key schedule. Second, we consider the resistance of ciphers, and LED in particular, to related-key attacks: we are able to derive simple yet interesting AES-like security proofs for LED regarding related- or single-key attacks. And third, while we provide a block cipher that is very compact in hardware, we aim to maintain a reasonable performance profile for software implementation.

Polynomial selection is very important in number field sieve. If the yield of a pair of polynomials is closely correlated with the coefficients of the polynomials, we can select polynomials by checking the coefficients first. This can speed up the selection of good polynomials. In this paper, we aim to study the correlation between the polynomial coefficients and the yield of the polynomials. By theoretical analysis and experiments, we find that a polynomial with the ending coefficient containing more small primes is usually better in yield than the one whose ending coefficient contains less. One advantage of the ending coefficient over the leading coefficient is that the ending coefficient is bigger and can contain more small primes in root optimizing stage. Using the complete discrimination system, we also analyze the condition on coefficients to obtain more real roots.

We describe Ginger, a built system for unconditional, general-purpose, and nearly practical verification of outsourced computation. Ginger is based on Pepper, which uses the PCP theorem and cryptographic techniques to implement an \emph{efficient argument} system (a kind of interactive protocol). Ginger slashes the query size and costs via theoretical refinements that are of independent interest; broadens the computational model to include (primitive) floating-point fractions, inequality comparisons, logical operations, and conditional control flow; and includes a parallel GPU-based implementation that dramatically reduces latency.

The contribution of the paper is two-fold. First, we design a novel permutation-based hash mode of operation FP, and analyze its security. The FP mode is derived by replacing the hard-to-invert primitive of the FWP mode -- designed by Nandi and Paul, Indocrypt 2010 -- with an easy-to-invert permutation; since easy-to-invert permutations with good cryptographic properties are normally easier to design, and are more efficient than the hard-to-invert functions, the FP mode is more suitable in practical applications than the FWP mode. We show that any n-bit hash function that uses the FP mode is indifferentiable from a random oracle up to 2^n/2 queries (up to a constant factor), if the underlying 2n-bit permutation is free from any structural weaknesses. Based on our further analysis and experiments, we conjecture that the FP mode is resistant to all non-trivial generic attacks with work less than the brute force, mainly due to its large internal state. We compare the FP mode with other permutation-based hash modes, and observe that it displays the so-far best security/rate trade-off. To put this into perspective, our second contribution is a proposal for a concrete hash function SAMOSA using the new mode and the $P$-permutations of the SHA-3 finalist Groestl. Based on our analysis we claim that the SAMOSA family cannot be attacked with work significantly less than the brute force. We also provide hardware implementation (FPGA) results for SAMOSA to compare it with the SHA-3 finalists. In our implementations, SAMOSA family consistently beats Groestl, Blake and Skein in the throughput to area ratio. With more efficient underlying permutation, it seems possible to design a hash function based on the FP mode that can achieve even higher performances.

Bitcoin is quickly emerging as a popular digital payment system. However, in spite of its reliance on pseudonyms, Bitcoin raises a number of privacy concerns due to the fact that all of the transactions that take place are publicly announced in the system. In this paper, we investigate the privacy guarantees of Bitcoin in the setting where Bitcoin is used as a primary currency for the daily transactions of individuals. More specifically, we evaluate the privacy that is provided by Bitcoin (i) by analyzing the genuine Bitcoin system and (ii) through a simulator that mimics Bitcoin client’s behavior in the context where Bitcoin is used for all transactions within a university. In this setting, our results show that the profiles of almost 40% of the users can be, to a large extent, recovered even when users adopt privacy measures recommended by Bitcoin. To the best of our knowledge, this is the first work that comprehensively analyzes, and evaluates the privacy implications of Bitcoin. As a by-product, we have designed and implemented the first simulator of Bitcoin; our simulator can be used to model the interaction between Bitcoin users in generic settings.

One important result in secret sharing is the Brickell-Davenport Theorem: every ideal perfect secret sharing scheme defines a matroid that is uniquely determined by the access structure. Even though a few attempts have been made, there is no satisfactory definition of ideal secret sharing scheme for the general case, in which non-perfect schemes are considered as well. Without providing another unsatisfactory definition of ideal non-perfect secret sharing scheme, we present a generalization of the Brickell-Davenport Theorem to the general case. After analyzing that result under a new point of view and identifying its combinatorial nature, we present a characterization of the (not necessarily perfect) secret sharing schemes that are associated to matroids. Some optimality properties of such schemes are discussed.

As an ISO/IEC international standard, Camellia has been used various cryptographic applications. In this paper, we improve previous attacks on Camellia-192/256 with key-dependent layers $FL/FL^{-1}$ by using the intrinsic weakness of keyed functions. Specifically, we present the first impossible differential attack on 13-round Camellia with $2^{121.6}$ chosen ciphertexts and $2^{189.9}$ 13-round encryptions, while the analysis for the biggest number of rounds in previous results on Camellia-192 worked on 12 rounds. Furthermore, we successfully attack 14-round Camellia-256 with $2^{122.1}$ chosen ciphertexts and $2^{229.3}$ 14-round encryptions. Compared with the previously best known attack on 14-round Camellia-256, the time complexity of our attack is reduced by $2^{8.9}$ times and the data complexity is comparable.

The security of pairing-based cryptosystems relies on the hardness of the discrete logarithm problems in elliptic curves and in finite fields related to the curves, namely, their embedding fields. Public keys and ciphertexts in the pairing-based cryptosystems are composed of points on the curves or values of pairings. Although the values of the pairings belong to the embedding fields, the representation of the field is inefficient in size because the size of the embedding fields is usually larger than the size of the elliptic curves. We show factor-4 and 6 compression and decompression for the values of the pairings with the supersingular elliptic curves of embedding degrees 4 and 6, respectively. For compression, we use the fact that the values of the pairings belong to algebraic tori that are multiplicative subgroups of the embedding fields. The algebraic tori can be expressed by the affine representation or the trace representation. Although the affine representation allows decompression maps, decompression maps for the trace representation has not been known. In this paper, we propose a trace representation with decompression maps for the characteristics 2 and 3. We first construct efficient decompression maps for trace maps by adding extra information to the trace representation. Our decompressible trace representation with additional information is as efficient as the affine representation is in terms of the costs of compression, decompression and exponentiation, and the size.

In this work, we provide the first construction of Attribute-Based Encryption (ABE) for general circuits. Our construction is based on the existence of multilinear maps. We prove selective security of our scheme in the standard model under the natural multilinear generalization of the BDDH assumption. Our scheme achieves both Key-Policy and Ciphertext-Policy variants of ABE. Our scheme and its proof of security directly translate to the recent multilinear map framework of Garg, Gentry, and Halevi.

In this paper, we analyze the resistance of the lightweight ciphers PRESENT, LED, and KLEIN to biclique attacks. Primarily, we describe attacks on the full-round versions PRESENT-80, PRESENT-128, LED-64, LED-128, KLEIN-80, and KLEIN-96. Our attacks have time complexities of $2^{79.49}$, $2^{127.32}$, $2^{63.58}$, $2^{127.42}$, $2^{79.00}$, and $2^{95.18}$ encryptions, respectively. In addition, we consider attacks on round-reduced versions of PRESENT and LED, to show the security margin for which an adversary can obtain an advantage of at least a factor of two compared to exhaustive search.

--withdrawn--

--withdrawn--

Not surprisingly, the common use of any public key crypto system involves publishing the public key and keeping the private key secret. There are however a few applications where both the private and public key are kept secret, thereby effectively converting a public key crypto algorithm to a symmetric algorithm. We show that if the RSA cryptosystem is used in such a symmetric application, it is possible to determine the public RSA modulus if the public exponent is known and short, such as 3 or F4=65537, and two or more plaintext/ciphertext (or, if RSA is used for signing, signed value/signature) pairs are known.

In this paper,we give an example of how symbolic computation are used to analyze the block cipher PRESENT,an ultra-lightweight block cipher proposed by Bogdanov et al. at CHES’07.The block size is 64 bits and the key size can be 80 bit or 128 bit.Using Mathematica 7.0,this paper obtains the unexpanded polynomial expressions of the output of round 1-6 of PRESENT-80(80- bit key variant).The time complexity of getting these expressions is 4 minutes on a PC with a 2.6GHz CPU and 8G RAM.Then we expand the expressions of the output of round 1-2 and the LSB(least significant bit) of the output of round 3 and obtain the ANFs(Algebraic Normal Form) of these 129(=2*64+1) expressions. The time complexity of getting these ANFs is 22 minutes.It it known that the time complexity of the classical method of computing the ANF of an n-ary Boolean function from its truth table is O(n*2^n),with total time complexity of obtaining these 129 ANFs O(129*144*2^144) = O(2^158)(each of the 129 ANFs can be viewed as a 144-ary Boolean function,where 144=64+80,the sum of the block size and the key size).As an application,we give a side channel attack on PRESENT-80 under the single bit leakage model proposed by Dinur and Shamir.If the LSB bit of the output of the 3rd round can be obtained without error,then with 200 known plaintexts,we can set up an equation system in terms of the master key bits and can recover 43 bits key by the Gr¨obner Basis method.Compared with the previous side channel attack on PRESENT,such as Yang et al. in CANS 2009,Abdul-Latip et al. in ASIACCS 2011 and Zhao et al. in 2011,each of which needs at least 2^13 chosen plaintexts,the data complexity of our attack is the best.

We introduce two new schemes for securely computing Hamming distance in the two-party setting. Our first scheme is a very efficient protocol, based solely on 1-out-of-2 Oblivious Transfer, that achieves full security in the semi-honest setting and one-sided security in the malicious setting. Moreover we show that this protocol is significantly more efficient than the previous proposals, that are either based on garbled circuits or on homomorphic encryption. Our second scheme achieves full security against malicious adversaries and is based on Committed Oblivious Transfer. These protocols have direct applications to secure biometric identification.

Signcryption is a cryptographic protocol that provides uthentication and confidentiality as a single primitive at a cost lower than the combined cost of sign and encryption. Code-based cryptography, a likely candidate for post-quantum cryptography, provides an exciting alternative to number-theoretic cryptography. Courtois, Finiasz and Sendrier proposed the only practical code-based signature(CFS signature) at Asiacrypt 2001. But that signature scheme currently lacks a formal proof of security due to the existence of the high rate distinguisher proposed by Fauge`re et al. In this paper, we make use of an alternate key-construct for the CFS signature, and thus prove its existential unforgeability under chosen message attacks (EUF-CMA). Also, we propose a code-based signcryption scheme and prove its security. To the best of our knowledge, this is the first code-based, provably secure signature and signcryption scheme in literature.