The design of embedded processors demands a careful trade-off between many conflicting objectives such as performance, silicon area and power consumption. Finding such a trade-off can often ignore the issue of security, which can cause, otherwise secure, software to leak information through so-called micro-architectural side channels. In this paper we show that early-terminating integer multipliers found in many embedded processors (e.g., ARM7TDMI) represent an instance of this problem. The early-termination mechanism causes differences in the time taken to compute a multiplication depending on the magnitude of the operands (e.g., up to three clock cycles on an ARM7TDMI processor), which are observable via variations in execution time and power consumption. Exploiting the early-termination mechanism makes Simple Power Analysis (SPA) attacks relatively straightforward to conduct, and may even allow one to attack implementations with integrated countermeasures that would not leak any information when executed on a processor with a constant-latency multiplier. We describe a number of case studies, including both public-key (RSA, ECIES) and secret-key algorithms (RC6, AES), to demonstrate the threat posed by early-terminating multipliers. Furthermore, we describe an implementation of one such attack on an implementation of AES, where we were able the extract the entire key using just eight power traces.

In this paper, we cryptanalyze two knapsack cryptosystems. The first one is proposed by Hwang et al [4], which is based on a new permutation algorithm named Permutation Combination Algorithm. We show that this permutation algorithm is useless to the security of the cryptosystem. Because of the special super increasing structure, we can break this cryptosystem use the method provided by Shamir at Crypto'82. The second one is provided by Su et al [16], which is based on the elliptic curve discrete logarithm and knapsack problem. We show that one can recover the plaintext as long as he solve a knapsack problem.Unfounately, this knapsack problem can be solved by Shamir's method or the low density attack. Finally, we give a improved version of Su's cryptosystem to avoid these attacks.

Most recently, Yang et al proposed an ID-based remote mutual authentication with key agreement scheme for mobile devices on elliptic curve cryptosystem in journal of Computer and Security. In this paper, we find some disadvantages in their scheme and thereafter propose such an improved scheme that overcomes all those disadvantages existing in their scheme while the merits are left unchanged. Our scheme provides more guarantees in security as follows: (1) our scheme combines two factors to protect its authentication mechanism. (2) our scheme can safely provide mutual authentication and key agreement with more desirable properties. (3) our scheme can provide anonymity for the user's identity. And yet, our scheme is simpler and more efficient than Yang et al's scheme. Therefore the end result is more practical for the users of mobile devices.

To guarantee the quality of the growing popular communication services, quite recently, Huang presented a simple and efficient three-party password-based authenticated key exchange protocol in International Journal of Communications and Systems. In this letter, we first show her protocol is still vulnerable to a partition attack (offline dictionary attack), by which the adversary can easily determine the correct password.

Quite recently, Yang et al. presented an efficient three-party authenticated key exchange protocol based upon elliptic curve cryptography for mobile-commerce environments. In this paper, we demonstrate that Yang et al's three-party authenticated protocol is potentially vulnerable to an unknown key-share attack and impersonation attack. Thereafter, we suggest a secure and efficient three-party authenticated key exchange protocol for mobile-commerce environments. Our improved protocol has the following advantages over Yang et al.'s protocol: (1) our scheme combines two factors to strengthen its authentication mechanism; (2) our scheme simply utilizes each user's unique identity to accomplish authentication, eliminating maintenance of a lot of users' keys. Furthermore, our scheme is more efficient than Yang et al's scheme. Therefore, the end result is more suited to be a candidate for implementation in mobile-commerce environments.

We apply the Cocks-Pinch method to obtain pairing-friendly composite order groups with prescribed embedding degree associated to ordinary elliptic curves, and we show that new security issues arise in the composite order setting.

In [BSW06,BW06] Boneh et al. presented the first fully collusion-resistant traitor tracing and trace & revoke schemes. These schemes are based on composite order bilinear groups and their security depends on the hardness of the subgroup decision assumption. In this paper we present new, efficient trace & revoke schemes which are based on prime order bilinear groups, and whose security depend on the hardness of the Decisional Linear Assumption or the External Diffie-Hellman (XDH) assumption. This allows our schemes to be flexible and thus much more efficient than existing schemes in terms a variety of parameters including ciphertext size, encryption time, and decryption time. For example, if encryption time was the major parameter of concern, then for the same level of practical security as [BSW06] our scheme encrypts 6 times faster. Decryption is 10 times faster. The ciphertext size in our scheme is 50% less when compared to [BSW06]. We provide the first implementations of efficient fully collusion-resilient traitor tracing and trace & revoke schemes. The ideas used in this paper can be used to make other cryptographic schemes based on composite order bilinear groups efficient as well.

In this paper, we improve the recent rebound and start-from-the-middle attacks on AES-like permutations. Our new cryptanalysis technique uses the fact that one can view two rounds of such permutations as a layer of big Sboxes preceded and followed by simple affine transformations. The big Sboxes encountered in this alternative representation are named Super-Sboxes. We apply this method to two second-round SHA-3 candidates Grostl and ECHO, and obtain improvements over the previous cryptanalysis results for these two schemes. Moreover, we improve the best distinguisher for the AES block cipher in the known-key setting, reaching 8 rounds for the 128-bit version.

This paper presents a effcient proposal for iterating hash functions to prevent the main of generic attacks such as Multicollisions Attack,Second Preimage Attack and Herding Attack.Based on this proposal,it’s possible that a secure hash function can be built with iterating compression functions . The proposal mainly contains a method called ” Shifting Whole Message”,it regroups the cascaded messages to be new blocks and makes the known results of the pre-computed blocks noneffective .

We present a protocol for anonymous access to a database where the different records have different access control permissions. These permissions could be attributes, roles, or rights that the user needs to have in order to access the record. Our protocol offers maximal security guarantees for both the database and the user, namely (1) only authorized users can access the record; (2) the database provider does not learn which record the user accesses; and (3) the database provider does not learn which attributes or roles the user has when she accesses the database. We prove our protocol secure in the standard model (i.e., without random oracles) under the bilinear Diffie-Hellman exponent and the strong Diffie-Hellman assumptions.

In this report we present a new fault attack that applies to some implementations of elliptic curve scalar multiplication (ECSM). We consider the fault model with 'precise control of time', 'loose control of fault location' and 'random number of faulty bits'. We show that in this fault model the secret key can be revealed with polynomial time complexity and linear number of faults. In addition, we discuss different countermeasures to resist this attack.

It is known that composable secure commitments, that is, concurrent non-malleable commitments exist in the plain model, based only on standard assumptions such as the existence of claw-free permutations or even one-way functions. Since being based on the plain model, the deniability of them is trivially satisfied, and especially the latter scheme satisfies also adaptivity, hence it is adaptive-deniable-concurrent non-malleable. However, those schemes cannot be said to be practically efficient. We show a practically efficient (string) adaptive-deniable-concurrent commitment scheme is possible under a global setup model, called global CRS-KR model.

Hash function Skein is one of the 14 NIST SHA-3 second round candidates. Threefish is a tweakable block cipher as the core of Skein, defined with a 256-, 512-, and 1024-bit block size. The 512-bit block size is the primary proposal of the authors. Skein had been updated after it entered the second round, the only differences between the original and the new version are the rotation constants. In this paper we construct related-key boomerang distinguishers on round-reduced Threefish-512 based on the new rotation constants using the method of \emph{modular differential}. With these distinguishers, we mount related-key boomerang key recovery attacks on Threefish-512 reduced to 32, 33 and 34 rounds. The attack on 32-round Threefish-512 has time complexity $2^{195}$ with memory of $2^{12}$ bytes. The attacks on Threefish-512 reduced to 33 and 34 rounds has time complexity of $2^{325.56}$ and $2^{483}$ encryptions respectively, and both with negligible memory. The best key recovery attack known before is proposed by Aumasson et al. Their attack, which bases on the old rotation constants, is also a related-key boomerang attack. For 32-round Threefish-512, their attack requires $2^{312}$ encryptions and $2^{71}$ bytes of memory.

Bellare and Kohno (2004) introduced the notion of balance to quantify the resistance of a hash function $h$ to a generic collision attack. Motivated by their work, we consider the problem of quantifying the resistance of $h$ to a generic multi-collision attack. To this end, we introduce the notion of $r$-balance $\mu_r (h)$ of $h$ and obtain bounds on the success probability of finding an $r$-collision in terms of $\mu_r (h)$. These bounds show that for a hash function with $m$ image points, if the number of trials $q$ is $\Theta(rm^{(r-1)\mu_r(h)/r})$, then it is possible to find $r$-collisions with a significant probability of success. The behaviour of random functions and the expected number of trials to obtain an $r$-collision is studied. These results extend and complete the earlier results obtained by Bellare and Kohno (2004) for collisions (i.e., $r = 2$). Going beyond their work, we provide a new design criteria to provide quantifiable resistance to generic multi- collision attacks. Further, we make a detailed probabilistic investigation of the variation of $r$-balance over the set of all functions and obtain support for the view that most functions have $r$-balance close to one.

Lossy Trapdoor Functions (LTDFs), introduced by Peikert and Waters (STOC 2008) have been useful for building many cryptographic primitives. In particular, by using an LTDF that loses a (1-1/omega(log n)) fraction of all its input bits, it is possible to achieve CCA security using the LTDF as a black-box. Unfortunately, not all candidate LTDFs achieve such a high level of lossiness. In this paper we drastically improve upon previous results and show that an LTDF that loses only a non-negligible fraction of a single bit can be used in a black-box way to build numerous cryptographic primitives, including one-way injective trapdoor functions, CPA secure public-key encryption (PKE), and CCA-secure PKE. We then describe a novel technique for constructing such slightly-lossy LTDFs and give a construction based on modular squaring.

We use two parametrizations of points on elliptic curves in generalized Edwards form x^2 + y^2 = c^2 (1+d x^2 y^2) that omit the x-coordinate. The first parametrization leads to a differential addition formula that can be computed using 6M + 4S, a doubling formula using 1M+4S and a tripling formula using 4M + 7S. The second one yields a differential addition formula that can be computed using 5M+2S and a doubling formula using 5S. All formulas apply also for the case c <> 1 and arbitrary curve parameter d. This generalizes formulas from the literature for the special case c = 1. For both parametrizations the formula for recovering the missing X-coordinate is also provided.

Isogenies, the mappings of elliptic curves, have become a useful tool in cryptology. These mathematical objects have been proposed for use in computing pairings, constructing hash functions and random number generators, and analyzing the reducibility of the elliptic curve discrete logarithm problem. With such diverse uses, understanding these objects is important for anyone interested in the field of elliptic curve cryptography. This paper, targeted at an audience with a knowledge of the basic theory of elliptic curves, provides an introduction to the necessary theoretical background for understanding what isogenies are and their basic properties. This theoretical background is used to explain some of the basic computational tasks associated with isogenies. Herein, algorithms for computing isogenies are collected and presented with proofs of correctness and complexity analyses. As opposed to the complex analytic approach provided in most texts on the subject, the proofs in this paper are primarily algebraic in nature. This provides alternate explanations that some with a more concrete or computational bias may find more clear.

As traditional oblivious transfer protocols are treated as a cryptographic primitive, they are usually executed without the consideration of possible attacks, e.g., impersonation, replaying, and man-in-the-middle attacks. Therefore, when these protocols are applied in certain applications such as mental poker playing, some necessary mechanism must be executed first to ensure the security of subsequent communications. But doing this way, we found that almost all of the resulting mechanisms are not efficient enough in communicational cost which is a significant concern for commercial transactions. Inspired by these observations, we propose a novel secure oblivious transfer protocol based on bilinear pairing which not only can provide mutual authentication to resist malicious attacks but also is efficient in communicational cost, other than its original functions.

We present the UC/c framework, a general definition for secure and incoercible multi-party protocols. Our framework allows to model arbitrary reactive protocol tasks (by specifying an ideal functionality) and comes with a universal composition theorem. We show that given natural setup assumptions, we can construct incoercible two-party protocols realising arbitrary functionalities (with respect to static adversaries).

In the problem of Secure Message Transmission in the public discussion model (SMT-PD), a Sender wants to send a message to a Receiver privately and reliably. Sender and Receiver are connected by $n$ channels, up to $t<n$ of which may be maliciously controlled by a computationally unbounded adversary, as well as one public channel, which is reliable but not private. The SMT-PD abstraction has been shown instrumental in achieving secure multi-party computation on sparse networks, where a subset of the nodes are able to realize a broadcast functionality, which plays the role of the public channel. However, the {\em implementation} of such public channel in point-to-point networks is highly costly and non-trivial, which makes minimizing the use of this resource an intrinsically compelling issue. In this paper, we present the first SMT-PD protocol with {\em sublinear} (i.e., logarithmic in $m$, the message size) communication on the public channel. In addition, the protocol incurs a private communication complexity of $O(\frac{mn}{n-t})$, which, as we also show, is {\em optimal}. By contrast, the best known bounds in both public and private channels were linear. Furthermore, our protocol has an optimal round complexity of $(3,2)$, meaning three rounds, two of which must invoke the public channel. Finally, we ask the question whether some of the lower bounds on resource use for a single execution of SMT-PD can be beaten \emph{on average} through amortization. In other words, if Sender and Receiver must send several messages back and forth (where later messages depend on earlier ones), can they do better than the naïve solution of repeating an SMT-PD protocol each time? We show that amortization can indeed drastically reduce the use of the public channel: it is possible to limit the total number of uses of the public channel to {\em two}, no matter how many messages are ultimately sent between two nodes. (Since two uses of the public channel are required to send any reliable communication whatsoever, this is best possible.)

Designated verifier signature (DVS) is a cryptographic primitive that allows a signer to convince a verifier the validity of a statement in a way that the verifier is unable to transfer the conviction to a third party. In DVS, signatures are publicly verifiable. The validity of a signature ensures that it is from either the signer or the verifier. Strong DVS (SDVS) enhances the privacy of the signer so that anyone except the designated verifier cannot verify the signer's signatures. In this paper we propose a highly efficient SDVS scheme based on pseudorandom functions, which is proved to be secure in the standard model. Compared with the most efficient SDVS scheme secure in the random oracle model, our scheme has almost the same complexity in terms of both the computational cost of generating a signature and signature size. A signature of our scheme is simply the output of a pseudorandom function. The security of the scheme is tightly reduced to the hardness of DDH problem and the security of the pseudorandom function. Since our scheme is vulnerable to delegatability attacks, the study of which was initiated by Lipmaa, Wang and Bao in ICALP 2005, we then propose another construction of SDVS, which is the \emph{first} one immune to delegatability attacks. The scheme is also very efficient, and has the same signature size with that of Lipmaa-Wang-Bao non-delegatable DVS scheme. We show that it is secure based on discrete logarithm assumption and gap Diffie-Hellman assumption in the random oracle model.

In Undeniable Signature, a signature's validity can only be confirmed or disavowed with the help of an alleged signer via a confirmation or disavowal protocol. A Convertible undeniable signature further allows the signer to release some additional information which can make an undeniable signature become publicly verifiable. In this work we introduce a new kind of attacks, called \emph{claimability attacks}, in which a dishonest/malicious signer both disavows a signature via the disavowal protocol and confirms it via selective conversion. Conventional security requirement does not capture the claimability attacks. We show that some convertible undeniable signature schemes are vulnerable to this kind of attacks. We then propose a new efficient construction of fully functional convertible undeniable signature, which supports both selective conversion and universal conversion, and is immune to the claimability attacks. To the best of our knowledge, it is the most efficient convertible undeniable signature scheme with provable security in the standard model. A signature is comprised of three elements of a bilinear group. Both the selective converter of a signature and the universal converter consist of one group element only. Besides, the confirmation and disavowal protocols are also very simple and efficient. Furthermore, the scheme can be extended to support additional features which include the delegation of conversion and confirmation/disavowal, threshold conversion and etc. We also propose an alternative generic construction of convertible undeniable signature schemes. Unlike the conventional sign-then-encrypt paradigm, the signer encrypts its (standard) signature with an identity-based encryption instead of a public key encryption. It enjoys the advantage of short selective converter, which is simply an identity-based user private key, and security against claimability attacks.

In the near future myriads of low-cost pervasive computing devices will enable the ubiquitous computing era that is widely believed to be the next paradigm in computing. Along with all its benefits come new security and privacy risks, which, given the severe cost constraints, provide a remarkable challenge. The thesis at hand provides an engineering approach to lightweight cryptography, a research field that aims at providing low-cost cryptographic solutions for constrained devices. Trade-offs for lightweight cryptography are discussed and, since this thesis has a strong emphasis on hardware implementations, application specific integrated circuit design is briefly introduced. Several lightweight cryptographic primitives for encryption, hashing and identification schemes are presented and their implementation for software and hardware platforms is discussed in detail. ­

In this paper, we investigate the famous Blake-Wilson, Johnson \& Menezes (BJM) authenticated key exchange protocols. We observe that the Corrupt query in the BJM model is not very reasonable, i.e. it fails to model the adversary's capability well. We modify the BJM model by providing it with a new Corrupt query. By this way, we bring the BJM model further to the practice. Besides, our modification has a significant impact on the security proofs of the BJM protocols. Specifically, the security proofs using CDH assumption will no longer work in the modified BJM model.With slight modification, we show that the BJM protocols are secure in the modified BJM model under the gap Diffie-Hellman assumption (GDH).

Minimizing complexity of group key exchange (GKE) protocols is an important milestone towards their practical deployment. An interesting approach to achieve this goal is to simplify the design of GKE protocols by using generic building blocks. In this paper we investigate the possibility of founding GKE protocols based on a primitive called {\em multi key encapsulation mechanism (mKEM)} and describe advantages and limitations of this approach. In particular, we show how to design a one-round GKE protocol which satisfies the classical requirement of authenticated key exchange (AKE) security, yet without forward secrecy. As a result, we obtain the first one-round GKE protocol secure in the standard model. We also conduct our analysis using recent formal models that take into account both outsider and insider attacks as well as the notion of key compromise impersonation resilience (KCIR). In contrast to previous models we show how to model both outsider and insider KCIR within the definition of mutual authentication. Our analysis additionally implies that the insider security compiler by Katz and Shin from ACM CCS 2005 can be used to achieve more than what is shown in the original work, namely both outsider and insider KCIR.

Selective opening attacks against commitment schemes occur when the commitment scheme is repeated in parallel and an adversary can choose depending on the commit-phase transcript to see the values and openings to some subset of the committed bits. Commitments are secure under such attacks if one can prove that the remaining, unopened commitments stay secret. We prove the following black-box constructions and black-box lower bounds for commitments secure against selective opening attacks for parallel composition: 1. $3$ (resp. $4$) rounds are necessary to build computationally (resp. statistically) binding and computationally hiding commitments. 2. There is a black-box construction of $(t+3)$-round statistically binding commitments secure against selective opening attacks based on $t$-round stand-alone statistically hiding commitments. 3. $O(1)$-round statistically-hiding commitments are equivalent to $O(1)$-round statistically-binding commitments. Our lower bounds improve upon the parameters obtained by the impossibility results of Bellare \etal{} (EUROCRYPT '09), and are proved in a fundamentally different way, by observing that essentially all known impossibility results for black-box zero-knowledge can also be applied to the case of commitments secure against selective opening attacks.

We construct the first public-key encryption scheme in the Bounded-Retrieval Model (BRM), providing security against various forms of adversarial "key leakage" attacks. In this model, the adversary is allowed to learn arbitrary information about the decryption key, subject only to the constraint that the overall amount of "leakage" is bounded by at most L bits. The goal of the BRM is to design cryptographic schemes that can flexibly tolerate arbitrarily leakage bounds L (few bits or many Gigabytes), by only increasing the size of secret key proportionally, but keeping all the other parameters -- including the size of the public key, ciphertext, encryption/decryption time, and the number of secret-key bits accessed during decryption -— small and independent of L. As our main technical tool, we introduce the concept of an Identity-Based Hash Proof System (IB-HPS), which generalizes the notion of hash proof systems of Cramer and Shoup [CS02] to the identity-based setting. We give three different constructions of this primitive based on: (1) bilinear groups, (2) lattices, and (3) quadratic residuosity. As a result of independent interest, we show that an IB-HPS almost immediately yields an Identity-Based Encryption (IBE) scheme which is secure against (small) partial leakage of the target identity’s decryption key. As our main result, we use IB-HPS to construct public-key encryption (and IBE) schemes in the Bounded-Retrieval Model.

We construct the first public-key encryption scheme that is proven secure (in the standard model, under standard assumptions) even when the attacker gets access to encryptions of arbitrary efficient functions of the secret key. Specifically, under either the DDH or LWE assumption, for every polynomials L and N we obtain a public-key encryption scheme that resists key-dependent message (KDM) attacks for up to N(k) public keys and functions of *circuit size* up to L(k), where k denotes the size of the secret key. We call such a scheme *bounded KDM secure*. Moreover, we show that our scheme suffices for one of the important applications of KDM security: ability to securely instantiate symbolic protocols with axiomatic proofs of security. We also observe that any fully homomorphic encryption scheme which additionally enjoys circular security and circuit privacy is *fully KDM secure* in the sense that the encryption and decryption algorithms can be independent of the polynomials L and N as above. Thus, the recent fully homomorphic encryption scheme of Gentry (STOC 2009) is fully KDM secure under certain non-standard hardness assumptions. Previous works obtained either full KDM security in the random oracle model Black et al (SAC 2002), or security with respect to a very restricted class of functions (e.g., clique/circular security and affine functions, Boneh et al, CRYPTO 2008, and Applebaum et al, CRYPTO 2009). Our main result is based on a combination of the circular-secure encryption scheme of either Boneh et al or Applebaum et al with Yao's garbled circuit construction. Finally, we extend the impossibility result of Haitner and Holenstein (TCC 2009), showing that it is impossible to prove KDM security against a family of query functions that contains exponentially hard pseudorandom functions, using only *black-box* access to the query function and the adversary attacking the scheme. This proves that the non-black-box usage of the query function in our proof of security makes to the KDM query function is *inherent*.

In this paper we describe our high-speed hardware implementations of the 14 candidates of the second evalution round of the \mbox{SHA-3} hash function competition. We synthesized all implementations using a uniform tool chain, standard-cell library, target technology, and optimization heuristic. This work provides the fairest comparison of all second-round candidates to date.

The McEliece cryptosystem is a promising alternative to conventional public key encryption systems like RSA and ECC. In particular, it is supposed to resist even attackers equipped with quantum computers. Moreover, the encryption process requires only simple binary operations making it a good candidate for low cost devices like RFID tags. However, McEliece's original scheme has the drawback that the keys are very large. Two promising variants have been proposed to overcome this disadvantage. The rst one is due to Berger et al. presented at AFRICACRYPT 2009 and the second is due to Barreto and Misoczki presented at SAC 2009. In this paper we rst present a general attack framework and apply it to both schemes subsequently. Our framework allows us to recover the private key for most parameters proposed by the authors of both schemes within at most a few days on a single PC

Due to its universality oblivious transfer (OT) is a primitive of great importance in secure multi-party computation. OT is impossible to implement from scratch in an unconditionally secure way, but there are many reductions of OT to other variants of OT, as well as other primitives such as noisy channels. It is important to know how efficient such unconditionally secure reductions can be in principle, i.e., how many instances of a given primitive are at least needed to implement OT. For perfect (error-free) implementations good lower bounds are known, e.g. the bounds by Beaver (STOC '96) or by Dodis and Micali (EUROCRYPT '99). However, in practice one is usually willing to tolerate a small probability of error and it is known that these statistical reductions can in general be much more efficient. Thus, the known bounds have only limited application. In the first part of this work we provide bounds on the efficiency of secure (one-sided) two-party computation of arbitrary finite functions from distributed randomness in the statistical case. From these results we derive bounds on the efficiency of protocols that use (different variants of) OT as a black-box. When applied to implementations of OT, our bounds generalize known results to the statistical case. Our results hold in particular for transformations between a finite number of primitives and for any error. Furthermore, we provide bounds on the efficiency of protocols implementing Rabin OT. In the second part we study the efficiency of quantum protocols implementing OT. Recently, Salvail, Schaffner and Sotakova (ASIACRYPT '09) showed that most classical lower bounds for perfectly secure reductions of OT to distributed randomness still hold in a quantum setting. We present a statistically secure protocol that violates these bounds by an arbitrarily large factor. We then present a weaker lower bound that does hold in the statistical quantum setting. We use this bound to show that even quantum protocols cannot extend OT. Finally, we present two lower bounds for reductions of OT to commitments and a protocol based on string commitments that is optimal with respect to both of these bounds.

Automatic recognition of human faces is becoming increasingly popular in civilian and law enforcement applications that require reliable recognition of humans. However, the rapid improvement and widespread deployment of this technology raises strong concerns regarding the violation of individuals' privacy. A typical application scenario for privacy-preserving face recognition concerns a client who privately searches for a specific face image in the face image database of a server. In this paper we present a privacy-preserving face recognition scheme that substantially improves over previous work in terms of communication- and computation efficiency: the most recent proposal of Erkin et al. (PETS'09) requires $\mathcal{O}(\log M)$ rounds and computationally expensive operations on homomorphically encrypted data to recognize a face in a database of $M$ faces. Our improved scheme requires only $\mathcal{O}(1)$ rounds and has a substantially smaller online communication complexity (by a factor of $15$ for each database entry) and less computation complexity. Our solution is based on known cryptographic building blocks combining homomorphic encryption with garbled circuits. Our implementation results show the practicality of our scheme also for large databases (e.g., for $M = 1000$ we need less than $13$ seconds and less than $4$ MByte online communication on two 2.4GHz PCs connected via Gigabit Ethernet).

We revisit the enhanced target collision resistance (eTCR) property as a newly emerged notion of security for dedicated-key hash functions, which has been put forth by Halevi and Krawczyk at CRYPTO'06, in conjunction with the Randomized Hashing mode to archive this property. Our contribution is twofold. Firstly, we provide a full picture of the relationships between eTCR and each of the seven security properties for a dedicated-key hash function, considered by Rogaway and Shrimpton at FSE'04; namely, collision resistance (CR), the three variants of second-preimage resistance (Sec, aSec, eSec) and the three variants of preimage resistance (Pre, aPre, ePre). The results show that, for an arbitrary dedicated-key hash function, eTCR is not implied by any of these seven properties, and it can only imply three of the properties; namely, eSec (TCR), Sec, Pre. In the second part of the paper, we analyze eTCR preservation capabilities of several domain extension transforms (a.k.a. modes of operation) for hash functions, including (Plain, Strengthened, and Prefix-free) Merkle-Damgård, Randomized Hashing (variant in the dedicated-key hash function setting), Shoup, Enveloped Shoup, XOR Linear Hash (XLH), and Linear Hash (LH) methods. From this analysis it turns out that, with the exception of a nested variant of LH construction, none of the investigated transforms can preserve eTCR property.

In this paper, we investigate the security model for authenticated key exchange protocols. We observe that there is further room to extend the latest enhanced Canetti-Krawczyk (eCK) model. We further enhance the freshness definition for the three-pass authenticated key exchange protocols such that our new definition gives the adversary more capabilities. We point out that the three-pass authenticated key exchange protocols generically transformed from the two-pass authenticated key exchange protocols secure in the eCK model can not be secure in our new security definition. We then introduce a new authenticated key exchange protocol SIG-DH$^+$ and prove that it satisfies our new definition.

Network coding allows the routers to mix the received information before forwarding them to the next nodes. Though this information mixing has been proven to maximize network throughput, it also introduces security challenges such as pollution attacks. A malicious node could insert a malicious packet into the system and this corrupted packet will propagate more quickly than in traditional copy-and-forward networks. Several authors have studied secure network coding from both information theoretic and probabilistic viewpoints. In this paper, we show that there are serious flaws in several of these schemes (the security ``proofs'' for these schemes were presented in these publications).

At CHES 2009, Coron, Joux, Kizhvatov, Naccache and Paillier (CJKNP) exhibited a fault attack against RSA signatures with partially known messages. This attack allows factoring the public modulus N. While the size of the unknown message part (UMP) increases with the number of faulty signatures available, the complexity of CJKNP's attack increases exponentially with the number of faulty signatures. This paper describes a simpler attack, whose complexity is polynomial in the number of faults; consequently, the new attack can handle much larger UMPs. The new technique can factor N in a fraction of a second using ten faulty EMV signatures -- a target beyond CJKNP's reach. We show how to apply the attack even when N is unknown, a frequent situation in real-life attacks.

We study cubic monomial Boolean functions of the form $Tr_1^n(\mu x^{2^i+2^j+1})$ where $\mu \in \mathbb{F}_{2^n}$. We prove that the functions of this form do not have any affine derivative. A lower bound on the second order nonlinearities of these functions is also derived.

This paper presents new software speed records for encryption and decryption using the block cipher AES-128 for different architectures. Target platforms are 8-bit AVR microcontrollers, NVIDIA graphics processing units (GPUs) and the Cell broadband engine. The new AVR implementation requires 124.6 and 181.3 cycles per byte for encryption and decryption with a code size of less than two kilobyte. Compared to the previous AVR records for encryption our code is 38 percent smaller and 1.24 times faster. The byte-sliced implementation for the synergistic processing elements of the Cell architecture achieves speed of 11.7 and 14.4 cycles per byte for encryption and decryption. Similarly, our fastest GPU implementation, running on the GTX 295 and handling many input streams in parallel, delivers throughputs of 0.17 and 0.19 cycles per byte for encryption and decryption respectively. Furthermore, this is the first AES implementation for the GPU which implements both encryption and decryption.

This paper shows a key recovery attack on QuiSci (quick stream cipher), designed by Stefan Müller (FGAN-FHR, a German research institute) in 2001. With one or few know plaintexts it's possible to recover most of the key with negligible time complexity. This paper shows a way how to exploit the weak key setup of QuiSci.

In this paper, we define an underlying computational problem and its decisional problem. As an application of their problems, we propose an efficient designated verifier signature (DVS) scheme without random oracles (related to symmetric pairings). We formally redefine the (Strong) Privacy of Signature's Identity, and prove our DVS scheme satisfying security based on the difficulty of the problems. Also we prove that the difficulty of the computational problem is tightly equivalent to the Strong Unforgeability of our proposed conventional signature scheme (without random oracles) related to asymmetric pairings. We believe that our underlying problems are profitable to propose many efficient cryptographic schemes.

In order to prevent illegal tracking and stealing personal or cargo information, the authentication services should be provided for the tags to identify a Reader. A NTRU based signature scheme is proposed in this paper, which meets the demand for a group of tags to quickly and securely identify a Reader in RFID system. In our scheme, only the tag in specified group can verify the reader’s message. Because of fast operation, easy key generation and limited source occupied, our signature is very suit for the RFID systems.

Abstract. The cube attack has been introduced by Itai Dinur and Adi Shamir [8] as a known plaintext attack on symmetric primitives. The attack has been applied to reduced variants of the stream ciphers Trivium [3, 8] and Grain-128 [2], reduced to three rounds variant of the block cipher Serpent [9] and reduced version of the hash function MD6 [3]. In the special case the attack has appeared in the M. Vielhaber ePrint articles [13, 14], where it has been named AIDA (Algebraic Initial Value Differential Attack ) and applied to the modified versions of Trivium. In this paper, we present the experimental results of application the cube attack to four rounds of the Courtois Toy Cipher (CTC) with the full recovery of 120-bit key. After that we extend the attack to five rounds by applying the meet-in-the-middle principle. Key words: Cube attack, symmetric primitives, Boolean polynomials, CTC, the meet-in-the-middle method

In this paper, we consider the problem of predicate encryption and focus on the predicate for testing whether the hamming distance between the attribute $X$ of a data item and a target $V$ is equal to (or less than) a threshold $t$ where $X$ and $V$ are of length $m$. Existing solutions either do not provide attribute protection or produce a big ciphertext of size $O(m2^m)$. For the equality version of the problem, we provide a scheme which is match-concealing (MC) secure and the sizes of the ciphertext and token are both $O(m)$. For the inequality version of the problem, we give two practical schemes. The first one, also achieving MC security, produces ciphertext with size $O(m^{t_{max}})$ if the maximum value of $t$, $t_{max}$, is known in advance and is a constant. We also show how to update the ciphertext if the user wants to increase $t_{max}$ without constructing the ciphertext from scratch. On the other hand,in many real applications, the security requirement can be lowered from MC to MR (match-revealing). Our second scheme, which is MR secure, produces ciphertext of size $O(m)$ and token of size $O((t+1)m)$ only.

In ICA3PP 2009, Xinglan Zhang proposed two one-round authenticated key exchange protocols and proved their security in the standard model. In this paper, we analyze these two protocols and find that both of them exist some flaws.

A universally composable (UC) blind signature functionality requres users to commit to the message to be blindly signed. It is thereby impossible to realize in the plain model. This paper shows that even non-committing variants of UC blind signature functionality can not be realized in the plain model. We characterize UC non-committing blind signatures in the common reference string model by presenting equivalent stand-alone security notions under static corruption. Usefulness of the characterization is demonstrated by showing that Fischlin's basic stand-alone blind signature scheme can be transformed into a UC non-committing blind signature protocol without using extra cryptographic components. We extend the results to the adaptive corruption model and present analogous notions, theorems, and constructions both in the erasure model and the non-erasure model.

We remark that the schemes [PhysRevLett.98.020503, PhysRevA.74.012315, PhysRevA.71.022321, PhysRevA.72.012304, PhysRevA.69.052307, PhysRevA.59.1829] are not secret sharing schemes as claimed.

Verifiable Secret Sharing (VSS) is a fundamental primitive used as a building block in many distributed cryptographic tasks, such as Secure Multiparty Computation (MPC) and Byzantine Agreement (BA). An important variant of VSS is Asynchronous VSS (AVSS) which is designed to work over asynchronous networks. AVSS is a two phase (Sharing, Reconstruction) protocol carried out among n parties in the presence of a computationally unbounded active adversary, who can corrupt up to t parties. We assume that every two parties in the network are directly connected by a pairwise secure channel. In this paper, we present a new statistical AVSS protocol with optimal resilience; i.e. with n = 3t+1. Our protocol privately communicates O((\ell n^3 + n^4 \log{\frac{1}{\epsilon}}) \log{\frac{1}{\epsilon}}) bits and A-casts O(n^3 \log(n)) bits to simultaneously share \ell \geq 1 elements from a finite field F, where \epsilon is the error parameter of our protocol. There are only two known statistical AVSS protocols with n = 3t+1 reported in [CR93] and [PCR09]. The AVSS protocol of [CR93] requires a private communication of O(n^9 (\log{\frac{1}{\epsilon}})^4) bits and A-cast of O(n^9 (\log{\frac{1}{\epsilon}})^2 \log(n)) bits to share a single element from F. Thus our AVSS protocol shows a significant improvement in communication complexity over the AVSS of [CR93]. The AVSS protocol of [PCR09] requires a private communication and A-cast of O((\ell n^3 + n^4) \log{\frac{1}{\epsilon}}) bits to share \ell \geq 1 elements. However, the shared element(s) may be NULL \not \in {\mathbb F}. Thus our AVSS is better than the AVSS of [PCR09] due to the following reasons: 1. The A-cast communication of our AVSS is independent of the number of secrets i.e. \ell; 2. Our AVSS makes sure that the shared value(s) always belong to F. Using our AVSS, we design a new primitive called Asynchronous Complete Secret Sharing (ACSS) which acts as an important building block of asynchronous multiparty computation (AMPC). Using our ACSS scheme, we design a statistical AMPC protocol with optimal resilience; i.e., with n = 3t+1, that privately communicates O(n^5 \log{\frac{1}{\epsilon}}) bits per multiplication gate. This significantly improves the communication complexity of only known optimally resilient statistical AMPC of [BKR93] that privately communicates \Omega(n^{11} (\log{\frac{1}{\epsilon}})^4) bits and A-cast \Omega(n^{11} (\log{\frac{1}{\epsilon}})^2 \log(n)) bits per multiplication gate. Both our ACSS and AVSS employ several new techniques, which are of independent interest.

Increasing dependence on anytime-anywhere availability of data and the commensurately increasing fear of losing privacy motivate the need for privacy-preserving techniques. One interesting and common problem occurs when two parties need to privately compute an intersection of their respective sets of data. In doing so, one or both parties must obtain the intersection (if one exists), while neither should learn anything about other set. Although prior work has yielded a number of effective and elegant Private Set Intersection (PSI) techniques, the quest for efficiency is still underway. This paper explores some PSI variations and constructs several secure protocols that are appreciably more efficient than the state-of-the-art.

Password-based user-authentication schemes have been widely used when users access a server to avail internet services. Multiserver password-authentication schemes enable remote users to obtain service from multiple servers without separately registering with each server. In 2008, Jia-Lun Tsai proposed an improved and efficient password-authenticated key agreement scheme for a multiserver architecture based on Chang-Lee’s scheme proposed in 2004. However, we found that Tsai’s scheme does not provide forward secrecy and is weak to insider impersonation and denial of service attacks. In this article, we describe the drawbacks of Tsai’s scheme and provide a countermeasure to satisfy the forward secrecy property.

Impossible boomerang attack \cite{lu} (IBA) is a new variant of differential cryptanalysis against block ciphers. Evident from its name, it combines the ideas of both impossible differential cryptanalysis and boomerang attack. Though such an attack might not be the best attack available, its complexity is still less than that of the exhaustive search. In impossible boomerang attack, impossible boomerang distinguishers are used to retrieve some of the subkeys. Thus the security of a block cipher against IBA can be evaluated by impossible boomerang distinguishers. In this paper, we study the impossible boomerang distinguishers for block cipher structures whose round functions are bijective. Inspired by the $\mathcal{U}$-method in \cite{kim}, we provide an algorithm to compute the maximum length of impossible boomerang distinguishers for general block cipher structures, and apply the algorithm to known block cipher structures such as Nyberg's generalized Feistel network, a generalized CAST256-like structure, a generalized MARS-like structure, a generalized RC6-like structure, etc.

In 1998 [8], Patarin proposed an efficient cryptosystem called Little Dragon which was a variant of Matsumoto Imai cryptosystem C¤. However Patarin later found that Little Dragon cryptosystem is not secure [8], [3]. In this paper we propose a public key cryp- tosystem Little Dragon Two which is as e±cient as Little Dragon cryptosystem but secure against all the known attacks. Like little Dragon cryptosystem the public key of Little Dragon Two is of mixed type that is quadratic in plaintext and ciphertext variables. So the public key size of Little Dragon Two is equal to Little Dragon Cryptosystem. Our Public key algorithm is bijective and can be used for both encryption and signatures.

An error decodable secret-sharing scheme is a secret-sharing scheme with the additional property that the secret can be recovered from the set of all shares, even after a coalition of participants corrupts the shares they possess. In this paper we consider schemes that can tolerate corruption by sets of participants belonging to a monotone coalition structure, thus generalising both a related notion studied by Kurosawa, and the well-known error-correction properties of threshold schemes based on Reed-Solomon codes. We deduce a necessary and sufficient condition for the existence of such schemes, and we show how to reduce the storage requirements of a technique of Kurosawa for constructing error-decodable secret-sharing schemes with efficient decoding algorithms. In addition, we explore the connection between one-round perfectly secure message transmission (PSMT) schemes with general adversary structures and secret-sharing schemes, and we exploit this connection to investigate factors affecting the performance of one-round PSMT schemes such as the number of channels required, the communication overhead, and the efficiency of message recovery.

In this paper, we generalize Naor and Reingold's construction of pseudorandom functions under the DDH Assumption to yield a construction of pseudorandom functions under the decisional $k$-Linear Assumption, for each $k\geq 1$. The decisional Linear Assumption was first introduced by Boneh, Boyen, and Shacham as an alternative assumption for settings where the DDH problem is easy, such as bilinear groups. This assumption can be generalized to obtain the decisional $k$-Linear Assumptions. Shacham and Hofheinz and Kiltz showed that the decisional $(k+1)$-Linear problem is hard for generic groups even when the decisional $k$-Linear problem is easy. It is thus desirable to have constructions of cryptographic primitives based on the decisional $k$-Linear Assumption instead of DDH. Not surprisingly, one must pay a small price for added security: as $k$ increases, our constructed functions become slightly less efficient to compute and the key size increases (quadratically in $k$).

We show how to achieve public-key encryption schemes that can securely encrypt nonlinear functions of their own secret key. Specifically, we show that for any constant $d\in\mathbb{N}$, there exists a public-key encryption scheme that can securely encrypt any function $f$ of its own secret key, assuming $f$ can be expressed as a polynomial of total degree~$d$. Such a scheme is said to be key-dependent message (KDM) secure w.r.t.\ degree-$d$ polynomials. We also show that for any constants $c,e$, there exists a public-key encryption scheme that is KDM secure w.r.t.\ all Turing machines with description size $c\log \lambda$ and running time $\lambda^e$, where $\lambda$ is the security parameter. The security of such public-key schemes can be based either on the standard decision Diffie-Hellman (DDH) assumption or on the learning with errors (LWE) assumption (with certain parameters settings). In the case of functions that can be expressed as degree-$d$ polynomials, we show that the resulting schemes are also secure with respect to \emph{key cycles} of any length. Specifically, for any polynomial number $n$ of key pairs, our schemes can securely encrypt a degree-$d$ polynomial whose variables are the collection of coordinates of all $n$ secret keys. Prior to this work, it was not known how to achieve this for nonlinear functions. Our key idea is a general transformation that amplifies KDM security. The transformation takes an encryption scheme that is KDM secure w.r.t.\ \emph{some} functions even when the secret keys are weak (i.e.\ chosen from an arbitrary distribution with entropy~$k$), and outputs a scheme that is KDM secure w.r.t.\ a \emph{richer} class of functions. The resulting scheme may no longer be secure with weak keys. Thus, in some sense, this transformation converts security with weak keys into amplified KDM security.

Hamsi-256 is designed by Özgül Kücük and it has been a candidate Hash function for the second round of SHA-3. The compression function of Hamsi-256 maps a 256-bit chaining value and a 32-bit message to a new 256-bit chaining value. As hashing a message, Hamsi-256 operates 3-round except for the last message it operates 6-round. In this paper, we will give the pseudo-near-collision for 5-round Hamsi-256. By the message modifying, the pseudo-near-collision for 3, 4 and 5 rounds can be found with $2^5$, $2^{32}$ and $2^{125}$ compression function computations respectively.

In this short note, we investigate the security of the Unbalanced Oil and Vinegar Scheme \cite{uov}. To do so, we use a hybrid approach for solving the algebraic systems naturally arising when mounting a signature-forgery attack. The basic idea is to compute Gröbner bases of several modified systems rather than a Gröbner basis of the initial system. It turns out that our approach is efficient in practice. We have obtained a complexity bounded from above by $2^{40.3}$ (or $9$ hours of computation) to forge a signature on a set of parameters proposed by the designers of UOV.

We construct a fully secure HIBE scheme with short ciphertexts. The previous construction of Boneh, Boyen, and Goh was only proven to be secure in the selective model, under a non-static assumption which depended on the depth of the hierarchy. To obtain full security, we apply the dual system encryption concept recently introduced by Waters. A straightforward application of this technique is insufficient to achieve short ciphertexts, since the original instantiation of the technique includes tags that do not compress. To overcome this challenge, we design a new method for realizing dual system encryption. We provide a system in composite order groups (of three primes) and prove the security of our scheme under three static assumptions.

As RFID applications are entering our daily life, many new security and privacy challenges arise. However, current research in RFID security focuses mainly on simple authentication and privacy-preserving identication. In this paper, we discuss the possibility of widening the scope of RFID security and privacy by introducing a new application scenario. The suggested application consists of computing statistics on private properties of individuals stored in RFID tags. The main requirement is to compute global statistics while preserving the privacy of individual readings. PPS assures the privacy of properties stored in each tag through the combination of homomorphic encryption and aggregation at the readers. Re-encryption is used to prevent tracking of users. The readers scan tags and forward the aggregate of their encrypted readings to the back-end server. The back-end server then decrypts the aggregates it receives and updates the global statistics accordingly. PPS is provably privacypreserving. Moreover, tags can be very simple since they are not required to perform any kind of computation, but only to store data.

Asymmetric pairings $e : \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$ for which an efficiently-computable isomorphism $\psi : \mathbb{G}_2 \rightarrow \mathbb{G}_1$ is known are called Type 2 pairings; if such an isomorphism $\psi$ is not known then $e$ is called a Type 3 pairing. Many cryptographic protocols in the asymmetric setting rely on the existence of $\psi$ for their security reduction while some use it in the protocol itself. For these reasons, it is believed that some of these protocols cannot be implemented with Type 3 pairings, while for some the security reductions either cannot be transformed to the Type 3 setting or else require a stronger complexity assumption. Contrary to these widely held beliefs, we argue that Type 2 pairings are merely inefficient implementations of Type 3 pairings, and appear to offer no benefit for protocols based on asymmetric pairings from the point of view of functionality, security, and performance.

In this paper, we propose preimage attacks on 41-step SHA-256 and 46-step SHA-512, which drastically increase the number of attacked steps compared to the best previous preimage attack working for only 24 steps. The time complexity for 41-step SHA-256 is $2^{253.5}$ compression function operations and the memory requirement is $2^{16}\times 10$ words. The time complexity for 46-step SHA-512 is $2^{511.5}$ compression function operations and the memory requirement is $2^{3}\times 10$ words. Our attack is a meet-in-the-middle attack. We first consider the application of previous meet-in-the-middle attack techniques to SHA-2. We then analyze the message expansion of SHA-2 by considering all previous techniques to find a new independent message-word partition. We first explain the attack on 40-step SHA-256 whose complexity is $2^{249}$ to describe the ideas. We then explain how to extend the attack.

The hash function Blue Midnight Wish (BMW) is a candidate in the SHA-3 competition organised by the U.S. National Institute of Standards and Technology (NIST). BMW was selected for the second round of the competition, but the algorithm was tweaked in a number of ways. In this paper we describe cryptanalysis on the original version of BMW, as submitted to the SHA-3 competition in October 2008. When we refer to BMW, we therefore mean the original version of the algorithm. The attacks described are (near-)collision, preimage and second preimage attacks on the BMW compression function. These attacks can also be described as pseudo-attacks on the full hash function, i.e., as attacks in which the adversary is allowed to choose the initial value of the hash function. The complexities of the attacks are about 2^{14} for the near-collision attack, about 2^{3n/8+1} for the pseudo-collision attack, and about 2^{3n/4+1} for the pseudo-(second) preimage attack, where n is the output length of the hash function. Memory requirements are negligible. Moreover, the attacks are not (or only moderately) affected by the choice of security parameter for BMW.

In this paper, we present a preimage attack for 42 step-reduced SHA-256 with time complexity $2^{251.7}$ and memory requirements of order $2^{12}$. The same attack also applies to 42 step-reduced SHA-512 with time complexity $2^{502.3}$ and memory requirements of order $2^{22}$. Our attack is meet-in-the-middle preimage attack.

Recently a new human authentication scheme called PAS (predicate-based authentication service) was proposed, which does not require the assistance of any supplementary device. The main security claim of PAS is to resist passive adversaries who can observe the whole authentication session between the human user and the remote server. In this paper we give a detailed security analysis of PAS and show that PAS is insecure against both brute force attack and a probabilistic attack. In particular we show that the security of PAS against brute force attack was strongly overestimated. Furthermore, we introduce a probabilistic attack, which can break part of the password even with a very small number of observed authentication sessions. Although the proposed attack cannot completely break the password, it can downgrade the PAS system to a much weaker system similar to common OTP (one-time password) systems.

In previous work we showed how to compress certain prime-order subgroups of certain cyclotomic subgroups by a factor of 4. We also showed that single-exponentiation can be efficiently performed using compressed representations. In this paper we show that double-exponentiation can be efficiently performed using factor-4 compressed representation of elements. In addition to giving a considerable speed up to the previously known fastest single-exponentiation algorithm for general bases, double-exponentiation can be used to adapt our compression technique to ElGamal type signature schemes.

Typical security models used for proving security of deployed cryptographic primitives do not allow adversaries to rewind or reset honest parties to an earlier state. Thus, it is common to see cryptographic protocols rely on the assumption that fresh random numbers can be continually generated. In this paper, we argue that because of the growing popularity of virtual machines and, specifically, their state snapshot and revert features, the security of cryptographic protocols proven under these assumptions is called into question. We focus on public-key encryption security in a setting where resetting is possible and random numbers might be reused. We show that existing schemes and security models are insufficient in this setting. We then provide new formal security models and show that making a simple and efficient modification to any existing PKE scheme gives us security under our new models.

We describe an SPA attack on an 8-bit smart card implementation of the Serpent block cipher. Our attack uses measurements taken during an on-the-fly key expansion together with linearity in the cipher's key schedule algorithm to drastically reduce the search time for an initial key. An implementation finds 256-bit keys in 3.736 ms on average. Our work shows that linearity in key schedule design and other cryptographic applications should be carefully evaluated for susceptibility to side-channel attacks and that search algorithm design can greatly speed up side-channel attacks.

At CANS 2008, Mashatan and Stinson suggested a message recognition protocol for ad hoc pervasive networks. The protocol provides a procedure to resynchronize in case of a (possibly adversarial) disruption of communication. We show that this resynchronization process does not provide the functionality intended and in fact enables an adversary to create selective forgeries. The computational effort for the attack is negligible and allows the insertion of arbitrary messages.

In this paper, we describe an improvement of the Berlekamp algorithm for binomials $x^n - a$ over prime fields $\mathbb{F}_{p}$. We implement the proposed method for various cases and compare the results with the original Berlekamp method. The proposed method can be extended easily to the case where the base field is not a prime field.

In this paper, we re-visit the problem of perfectly secure message transmission (PSMT) in a directed network under the presence of a threshold adaptive Byzantine adversary, having unbounded computing power. Desmedt et.al have given the characterization for three or more phase PSMT protocols over directed networks. Recently, Patra et. al. have given the characterization of two phase PSMT over directed networks. Even though the issue of tradeoff between phase complexity and communication complexity of PSMT protocols has been resolved in undirected networks, nothing is known in the literature regarding directed networks. In this paper, we completely settle down this issue. Specifically, we derive the lower bounds on communication complexity of (a) two phase PSMT protocols and (b) three or more phase PSMT protocols in directed networks. Moreover, we show that our lower bounds are asymptotically tight, by designing communication optimal PSMT protocols in directed networks, which are first of their kind. We re-visit the problem of perfectly reliable message transmission (PRMT) as well. Any PRMT protocol that sends a message containing $\ell$ field elements, has a trivial lower bound of ­O($\ell$) field elements on its communication complexity. Thus any PRMT protocol that sends a message of $\ell$ eld elements by communicating O(\ell) field elements, is referred as communication optimal PRMT or PRMT with constant factor overhead. Here, we characterize the class of directed networks over which communication optimal PRMT or PRMT with constant factor overhead is possible. Moreover, we design a communication optimal PRMT over a directed network that satisfies the conditions stated in our characterization. Our communication optimal PRMT/PSMT protocols employ several new techniques based on coding theory, which are of independent interest.

We show how to express an arbitrary integer interval $\II = [0, H]$ as a sumset $\II = \sum_{i=1}^\ell G_i * [0, u - 1] + [0, H']$ of smaller integer intervals for some small values $\ell$, $u$, and $H' < u - 1$, where $b * A = \{b a : a \in A\}$ and $A + B = \{a + b : a \in A \land b \in B\}$. We show how to derive such expression of $\II$ as a sumset for any value of $1 < u < H$, and in particular, how the coefficients $G_i$ can be found by using a nontrivial but efficient algorithm. This result may be interesting by itself in the context of additive combinatorics. Given the sumset-representation of $\II$, we show how to decrease both the communication complexity and the computational complexity of the recent pairing-based range proof of Camenisch, Chaabouni and shelat from ASIACRYPT 2008 by a factor of $2$. Our results are important in applications like e-voting where a voting server has to verify thousands of proofs of e-vote correctness per hour. Therefore, our new result in additive combinatorics has direct relevance in practice.

We here describe a new Password-based Authenticated Key Exchange (PAKE) protocol based on elliptic curve cryptography. We prove it secure in the Bellare-Pointcheval-Rogaway (BPR) model. Our proposal is conceived in a such a way that it ensures that the elliptic curve public parameters remain private. This is important in the context of ID contactless devices as, in this case, it is easy to link these parameters with the nationality of the ID document owners.

This paper investigates the Learning from Parity with Noise (LPN) problem under the scenario that the unknowns (secret keys) are only unpredictable instead of being uniformly random to the adversaries. In practice, this corresponds to the case where an adversary already possesses some additional knowledge about the secret key. In the information-theoretic setting, we show that the problem is robust against arbitrary leakages as long as the unknowns remain some sufficient amount of min-entropy. In the computational setting, we prove Dodis et al.'s [STOC'09] conjecture that the auxiliary-input LPN assumption is implied by the standard LPN assumption, i.e., encryption schemes based on the standard LPN assumption is secure against any exponentially hard-to-invert auxiliary input. \medskip Our setting is more general than the traditional model of auxiliary input which deals with secret keys of sufficient min-entropy, in particular, we allow leakages that information-theoretically determine their secret keys as long as the keys remain a linear amount of unpredictability pseudoentropy. Further, unlike most other schemes, our result is reducible to a well-known hardness problem and does not quantify over all hard-to-invert auxiliary functions.

To encourage research on the hardness of the elliptic-curve discrete-logarithm problem (ECDLP) Certicom has published a series of challenge curves and DLPs. This paper analyzes the costs of breaking the Certicom challenges over the binary fields $\F_{2^{131}}$ and $\F_{2^{163}}$ on a variety of platforms. We describe details of the choice of step function and distinguished points for the Koblitz and non-Koblitz curves. In contrast to the implementations for the previous Certicom challenges we do not restrict ourselves to software and conventional PCs, but branch out to cover the majority of available platforms such as various ASICs, FPGAs, CPUs and the Cell Broadband Engine. For the field arithmetic we investigate polynomial and normal basis arithmetic for these specific fields; in particular for the challenges on Koblitz curves normal bases become more attractive on ASICs and FPGAs.

Recent emergence of RFID tags capable of performing public key operations motivates new RFID applications, including electronic travel documents, identification cards and payment instruments. In such settings, public key certificates form the cornerstone of the overall system security. In this paper, we argue that one of the prominent -and still woefully unaddressed- challenges is how to handle revocation checking of RFID reader certificates. This is an important issue considering that these high-end RFID tags are geared for applications such as e-documents and contactless payment instruments. Furthermore, the problem is unique to public key-based RFID systems, since tags (even those capable of complex cryptographic operations) have no clock and thus cannot use traditional (time-based) off-line revocation checking methods. Whereas, on-line methods require unrealistic connectivity assumptions. In this paper, we address the problem of reader revocation in PKI-Based RFID systems. We begin by observing an important distinguishing feature of personal RFID tags used in authentication, access control or payment applications -the involvement of a human user. We then take advantage of the user's awareness and presence to construct a simple, efficient, secure and (most importantly) feasible solution for reader revocation checking. And finally, we evaluate the usability and practical security our solution via usability studies and discuss its feasibility in a case study of e-Passports. In our approach, the main extra feature is the requirement for a small passive on-tag display. However, as discussed in the paper, modern low-power display technology (e.g., e-paper) is low-cost and appealing for other (e.g., authentication and verification) purposes.

Against such attacks as rubber-hose attack, key authentic degree of cryptosystem is expatiated in detail, and the important significance of key authentic degree of cryptosystem is pointed out. And the key authentic degrees of modern cryptosystem under different conditions are given. Research shows that under most realistic situations, the key authentic degree of modern cryptosystem is high, this means that modern cryptosystem is threatened by such as rubber-hose attack and so on. Feasibility of low key authentic degree reliability is analyzed, and the implementing of low key authentic degree algorithm is studied.

In this paper we present a theoretical framework to quantify the information brought by several linear approximations of a block-cipher without putting any restriction on these approximations. We quantify here the entropy of the key given the plaintext-ciphertext pairs statistics which is a much more accurate measure than the ones studied earlier. The techniques which are developed here apply to various ways of performing the linear attack and can also been used to measure the entropy of the key for other statistical attacks. Moreover, we present a realistic attack on the full DES with a time complexity of $2^{48}$ for $2^{41}$ pairs what is a big improvement comparing to Matsui's algorithm 2 ($2^{51.9}$).

Often authentication and confidentiality are required as simultaneous key requirements in many cryptographic applications. The cryptographic primitive called signcryption effectively implements the same and while most of the public key based systems are appropriate for small messages, hybrid encryption (KEM-DEM) provides an efficient and practical way to securely communicate very large messages. Recently, Lippold et al. \cite{GCJ09} proposed a certificateless KEM in the standard model and the first certificateless hybrid signcryption scheme was proposed by Fagen Li et al. \cite{LST09}. The concept of certificateless hybrid signcryption has evolved by combining the ideas of signcryption based on tag-KEM and certificateless cryptography. In this paper, we show that \cite{GCJ09} is not Type-I CCA secure and \cite{LST09} is existentially forgeable. We also propose an improved certificateless hybrid signcryption scheme and formally prove the security of the improved scheme against both adaptive chosen ciphertext attack and existential forgery in the appropriate security models for certificateless hybrid signcryption.

Zero-knowledge protocols are often studied through specific problems, like Graph-Isomorphism. In many cases this approach prevents an important level of abstraction and leads to limited results, whereas in fact the constructions apply to a wide variety of problems. We propose to address this issue with a formal framework of non-interactive instance-dependent commitment schemes (NIC). We define NIC in both the perfect, statistical, and computational settings, and formally characterize problems admitting NIC in all of these settings. We also prove other useful lemmas such as closure properties. Consequently, results that previously applied only to specific problems are now strengthened by our framework to apply to classes of problems. By providing formal yet intuitive tools, our framework facilitates the construction of zero-knowledge protocols for a wide variety of problems, in various settings, without the need to refer to a specific problem. Our results are unconditional.

A boolean function of n boolean variables is correlation-immune of order k if the function value is uncorrelated with the values of any k of the arguments. Such functions are of considerable interest due to their cryptographic properties, and are also related to the orthogonal arrays of statistics and the balanced hypercube colourings of combinatorics. The weight of a boolean function is the number of argument values that produce a function value of 1. If this is exactly half the argument values, that is, 2^{n-1} values, a correlation-immune function is called resilient. An asymptotic estimate of the number N(n,k) of n-variable correlation-immune boolean functions of order k was obtained in 1992 by Denisov for constant k. Denisov repudiated that estimate in 2000, but we will show that the repudiation was a mistake. The main contribution of this paper is an asymptotic estimate of N(n,k) which holds if k increases with n within generous limits and specialises to functions with a given weight, including the resilient functions. In the case of k=1, our estimates are valid for all weights. ~

The study of secure multiparty computation has yielded powerful feasibility results showing that any efficient functionality can be securely computed in the presence of malicious adversaries. Despite this, there are few problems of specific interest for which we have highly efficient protocols that are secure in the presence of malicious adversaries under full simulation based definitions (following the ideal/real model paradigm). Due to the difficulties of constructing such protocols, many researchers have resorted to weaker definitions of security and weaker adversary models. In this paper, we construct highly efficient protocols for the well-studied problem of oblivious polynomial evaluation. Our protocol is secure under standard cryptographic assumptions for the settings of malicious adversaries, and readily transform to protocols that are secure under universal composability and in the presence of covert adversaries. Our protocol is constant round and requires O(d \cdot s) exponentiations, where $d$ is the degree of the polynomial and s is a statistical security parameter (that should equal about 160 in practice).

The braid groups have attracted much attention as a new platform of constructing cryptosystems. This paper firstly analyzes the security vulnerabilities of existing proxy signature schemes over braid groups and presents feasible attacks. Then a new proxy signature scheme is proposed based on the difficulty of the conjugacy search problem and the multiple conjugacy search problem. Security analysis shows that the proposed scheme satisfies the security requirements of proxy signature.

We consider the computation of cube roots in finite fields. For the computation of square roots in finite fields, there are two typical methods; the Tonelli-Shanks method and the Cipolla-Lehmer method. The former can be extended easily to the case of $r$-th roots, which is called the Adleman-Manders-Miller method, but it seems to be difficult to extend the latter to more general cases. In this paper, we propose two explicit algorithms for realizing the Cipolla-Lehmer method in the case of cube roots for prime fields $\mathbb{F}_{p}$ with $p \equiv 1 \ ({\rm mod} \ {3})$. We implement these methods and compare the results.

In this paper we present a new method of constructing multicollision sets for iterated hash functions. Multicollisions have been studied quite actively since Joux published an attack against iterated hash functions, which works in $O(k2^{\frac{n}{2}} )$ complexity for $2^k$ -multicollisions. Recently Kelsey \& Schneier and Aumasson have published even faster multicollision attacks, which are based on fixed points of the compression function and some assumptions on the attacker's capabilities. Our method has complexity $O(2^{\frac{n}{2}} )$ for arbitrarily large multicollision sets and does not have any additional assumptions on the compression function or attacker's capabilities. The drawback of our method is the extremely long messages generated by the algorithm in the worst case. Our method is based on automata theory and, given a compression function $f$, we construct a finite state transducer, which realizes the iterated hash function based on $f$. The method for generating multicollision sets is based on well known pumping properties of these automata.

Signcryption is a cryptographic primitive that fulfills both the functions of digital signature and public key encryption simultaneously, at a cost significantly lower than that required by the traditional signature-then-encryption approach. In this paper, we address a question whether it is possible to construct a hybrid signcryption scheme in identity-based setting. This question seems to have never been addressed in the literature. We answer the question positively in this paper. In particular, we extend the concept of signcryption key encapsulation mechanism to the identity-based setting. We show that an identity-based signcryption scheme can be constructed by combining an identity-based signcryption key encapsulation mechanism with a data encapsulation mechanism. We also give an example of identity-based signcryption key encapsulation mechanism.

Undeniable signatures, introduced by Chaum and van Antwerpen, require a verifier to interact with the signer to verify a signature, and hence allow the signer to control the verifiability of his signatures. Convertible undeniable signatures, introduced by Boyar, Chaum, Damg\aa{}rd, and Pedersen, furthermore allow the signer to convert signatures to publicly verifiable ones by publicizing a verification token, either for individual signatures or for all signatures universally. In addition, the signer is able to delegate the ability to prove validity and convert signatures to a semi-trusted third party by providing a verification key. While the latter functionality is implemented by the early convertible undeniable signature schemes, most recent schemes do not consider this despite its practical appeal. In this paper we present an updated definition and security model for schemes allowing delegation, and highlight a new essential security property, token soundness, which is not formally treated in the previous security models for convertible undeniable signatures. We then propose a new convertible undeniable signature scheme. The scheme allows delegation of verification and is provably secure in the standard model assuming the computational co-Diffie-Hellman problem, a closely related problem, and the decisional linear problem are hard. Our scheme is, to the best of our knowledge, the currently most efficient convertible undeniable signature scheme which provably fulfills all security requirements in the standard model.

Abstract. BLUE MIDNIGHT WISH hash function is the fastest among 14 algorithms in the second round of SHA-3 competition [1]. At the beginning of this round authors were invited to add some tweaks before September 15th 2009. In this paper we discuss the tweaked version (BMW). The BMW algorithm [3] is of the type AXR, since it uses only operations ADD (sub), XOR and ROT (shift). If we substitute the operation ADD with operation XOR, we get a BMWlin, which is an affine transformation. In this paper we consider only a BMWlin function and its building blocks. These affine transformations can be represented as a linear matrix and a constant vector. We found that all matrices of main blocks of BMWlin have a full rank, or they have a rank very close to full rank. The structure of matrices was examined. Matrices of elementary blocks have an expected non-random structure, while main blocks have a random structure. We will also show matrices for different values of security parameter ExpandRounds1 (values between 0 and 16). We observed that increasing the number of rounds ExpandRounds1 tends to increase randomness as was intended by designers. These observations hold for both BMW256lin and BMW512lin. In this analysis we did not find any useful property, which would help in cryptanalysis, nor did we find any weaknesses of BMW. The study of all building blocks will follow.

A new structural attack on the McEliece/Niederreiter public key cryptosystem based on subcodes of generalized Reed-Solomon codes proposed by Berger and Loidreau is described. It allows the reconstruction of the private key for almost all practical parameter choices in polynomial time with high probability.

We give a direct construction of a certificateless key encapsulation mechanism (KEM) in the standard model that is more efficient than the generic constructions proposed before by Huang and Wong \cite{DBLP:conf/acisp/HuangW07}. We use a direct construction from Kiltz and Galindo's KEM scheme \cite{DBLP:conf/acisp/KiltzG06} to obtain a certificateless KEM in the standard model; our construction is roughly twice as efficient as the generic construction. We also address the security flaw discovered by Selvi et al. \cite{cryptoeprint:2009:462}.

Recently, two novel schemes have been proposed for hierarchical threshold secret sharing, one based on Birkoff interpolation and another based on bivariate Lagrange interpolation. In this short paper, we propose a much simpler solution for this problem.

In this paper, we examine the relationship between and the efficiency of different approaches to standard (univariate) DPA attacks. We first show that, when feeded with the same assumptions about the target device (i.e. with the same leakage model), the most popular approaches such as using a distance-of-means test, correlation analysis, and Bayes attacks are essentially equivalent in this setting. Differences observed in practice are not due to differences in the statistical tests but due to statistical artifacts. Then, we establish a link between the correlation coefficient and the conditional entropy in side-channel attacks. In a first-order attack scenario, this relationship allows linking currently used metrics to evaluate standard DPA attacks (such as the number of power traces needed to perform a key recovery) with an information theoretic metric (the mutual information). Our results show that in the practical scenario defined formally in this paper, both measures are equally suitable to compare devices in respect to their susceptibility to DPA attacks. Together with observations regarding key and algorithm independence we consequently extend theoretical strategies for the sound evaluation of leaking devices towards the practice of side-channel attacks.

Precise concurrent zero-knowledge is a new notion introduced by Pandey et al. \cite{P:P:M:T:V} in Eurocrypt'08 (which generalizes the work on precise zero-knowledge by Micali and Pass \cite{M:P} in STOC'06). This notion captures the idea that the view of any verifier in concurrent interaction can be reconstructed in the almost same time. \cite{P:P:M:T:V} constructed some (private-coin) concurrent zero-knowledge argument systems for $\NP$ which achieve precision in different levels and all these protocols use at least $\omega(\log n)$ rounds. In this paper we investigate the feasibility of reducing the round complexity and still keeping precision simultaneously. Our result is that we construct a public-coin precise bounded-concurrent zero-knowledge argument system for $\NP$ only using almost constant rounds, i.e., $\omega(1)$ rounds. Bounded-concurrency means an a-priori bound on the (polynomial) number of concurrent sessions is specified before the protocol is constructed. Our result doesn't need any setup assumption. We stress that this result cannot be obtained by \cite{P:P:M:T:V} even in bounded-concurrent setting.

In many of the cryptography applications like password or IP address encryption schemes, symmetric cryptography is useful. In these relatively simpler applications of cryptography, asymmetric cryptography is difficult to justify on account of the computational and implementation complexities associated with asymmetric cryptography. Symmetric schemes make use of a single shared key known only between the two communicating hosts. This shared key is used both for the encryption as well as the decryption of data. This key has to be small in size besides being a subset of a potentially large keyspace making it convenient for the communicating hosts while at the same time making cryptanalysis difficult for the potential attackers. In the present work, an abstract Rossler nonlinear dynamical machine has been described first. The Rossler system exhibits chaotic dynamics for certain values of system parameters and initial conditions. The chaotic dynamics of the Rossler system with its apparently erratic and irregular characteristics and extreme sensitivity to the initial conditions has been used for the design of the cryptographic key in an attempt to increase the confusion and the challenge for the potential attackers.

In this paper, we show that the fundamental concepts behind the Ntr¹u cryptosystem can be extended to a broader algebra than Dedekind domains. Also, we present an abstract and generalized algorithm for constructing a Ntr¹u-like cryptosystem such that the underlying algebra can be non-commutative or even non-associative. To prove the main claim, we show that it is possible to generalize Ntr¹u over non-commutative Quaternions (algebra in the sense of Cayley-Dikson, of dimension four over an arbitrary principal ideal domain) as well as non-associative Octonions (a power-associative and alternative algebra of dimension eight over a principal ideal domain). Given the serious challenges ahead of non-commutative/non-associative algebra in quater- nionic or octonionic lattices, the proposed cryptosystems are more resistant to lattice-based attacks when compared to Ntr¹u. Concisely, this paper is making an abstract image of the mathematical base of Ntr¹u in such a way that one can make a similar cryptosystem based on various algebraic structures with the goal of better security against lattice attack and/or more capability for protocol design.

We present a space-efficient algorithm to compute the Hilbert class polynomial H_D(X) modulo a positive integer P, based on an explicit form of the Chinese Remainder Theorem. Under the Generalized Riemann Hypothesis, the algorithm uses O(|D|^(1/2+o(1))log P) space and has an expected running time of O(|D|^(1+o(1)). We describe practical optimizations that allow us to handle larger discriminants than other methods, with |D| as large as 10^13 and h(D) up to 10^6. We apply these results to construct pairing-friendly elliptic curves of prime order, using the CM method.

The simple, computationally efficient LPN-based HB-like entity authentication protocols have attracted a great deal of attention in the past few years due to the broad application prospect in low-cost pervasive devices. At present, the most efficient protocol is HB$^\#$, which is proven to resist the GRS attack under the conjecture that it is secure in the DET-model. In this paper, we introduce an innovative HB-CM$^-$ protocol, which significantly reduces the storage requirement while maintaining the same level of communication cost. We develop the concept of equivalence class, and present HB-CM$^-$ reductionist proof that overcomes an inherent limitation in the HB$^\#$ security proof. In fact, HB$^\#$ is only provably resistant to partial instances of GRS attack, while we prove that HB-CM$^-$ can prevent the full GRS attack except one trivial case. In addition, we propose a new noise mode for all HB-like protocols in order to thwart the latest OOV man-in-the-middle attack, which can effectively compromise all current HB-like protocols with the basic Bernoulli nose mode. The HB-CM$^-$ protocol along with the proposed noise mode constitutes our final protocol: HB-CM.

In this work, we apply the rebound attack to the AES based SHA-3 candidate LANE. The hash function LANE uses a permutation based compression function, consisting of a linear message expansion and 6 parallel lanes. In the rebound attack on LANE, we apply several new techniques to construct a collision for the full compression function of LANE-256 and LANE-512. Using a relatively sparse truncated differential path, we are able to solve for a valid message expansion and colliding lanes independently. Additionally, we are able to apply the inbound phase more than once by exploiting the degrees of freedom in the parallel AES states. This allows us to construct semi-free-start collisions for full LANE-256 with $2^{96}$ compression function evaluations and $2^{88}$ memory, and for full LANE-512 with $2^{224}$ compression function evaluations and $2^{128}$ memory.

The P2PRep algorithm is a reputation-management mechanism in which a peer uses fuzzy techniques to compute local reputations and aggregates these results to compute a global reputation for another peer which has made an offer of service. While this mechanism is known to be extremely effective in the presence of malicious peers, it has one drawback: it does not preserve the anonymity of peers in the network during the voting phase of protocol. This makes it unsuitable for use in networks which associate peers with a routing identifier such as an IP address. We propose in this paper, a solution to this problem - the 3PRep (Privacy Preserving P2PRep) algorithm which implements two protocols to maintain vote privacy in P2PRep without significant additional computation and communications overhead. In doing so, we also provide a method to compute the Ordered Weighted Average (OWA) over distributed datasets while maintaining privacy of these data.

This paper presents an efficient identity-based key exchange protocol based on the difficulty of computing a Elliptic Curve Discrete Lgarithm Problem. As compared with the previously proposed protocols, it has better performance in terms of the computational cost and the communication steps. Key exchange protocols allow two parties communicating over a public network to establish a common secret key called session key to encrypt the communication data. Due to their significance by in building a secure communication channel, a number of key exchange protocols have been suggested over the years for a variety of settings.The proposed key exchange protocol provides implicit key authentication as well as the desired security attributes of an authenticated key exchange protocol.

Multivariate public key cryptography is one of the main approaches to guarantee the security of communication in a post quantum world. One of the major drawbacks in this area is the huge size of the public key. In this paper we present a new idea to create a multivariate signature scheme with an almost cyclic public key. The scheme is very similar to the UOV-Scheme of Kipnis and Patarin but reduces the size of the public key by about 83 \verb!%!.

Abstract. We present a fast and secure mental poker protocol. It is twice as fast as Barnett-Smart's and Castellà-Roca's protocols. This protocol is provably secure under DDH assumption.