Currently, researchers have focused their attention on proxy re-encryption scheme deployed between two entities. Lots of bidirectional schemes have been proposed and this kind of scheme is suitable for the scenario in which the two entities have already established a relationship of trust. How to construct a unidirectional scheme is an open problem and receiving increasing attention. In this paper, we present a unidirectional proxy re-encryption scheme for group communication. In this scheme, a proxy is only allowed to convert ciphertext for Alice into ciphertext for Bob without revealing any information on plaintext or private key. It is suitable for the environment in which no mutual relationship exists and transitivity is not permitted. We prove the scheme secure against chosen ciphertext attack in standard model.

The recent attack on Apple iTunes Digital Rights Management \cite{SJ05} has brought to light the usefulness of proxy re-encryption schemes for Digital Rights Management. It is known that the use of proxy re-encryption would have prevented the attack in \cite{SJ05}. With this utility in mind and with the added requirement of non-repudiation, we propose the first ever signcryption scheme with proxy re-encryption that does not involve bilinear maps. Our scheme is called RSA-TBOS-PRE and is based on the RSA-TBOS signcryption scheme of Mao and Malone-Lee \cite{MM03}. We adapt various models available in the literature concerning authenticity, unforgeability and non-repudiation and propose a signature non-repudiation model suitable for signcryption schemes with proxy re-encryption. We show the non-repudiability of our scheme in this model. We also introduce and define a new security notion of Weak-IND-CCA2, a slightly weakened adaptation of the IND-CCA2 security model for signcryption schemes and prove that RSA-TBOS-PRE is secure in this model. Our scheme is Weak-IND-CCA2 secure, unidirectional, extensible to multi-use and does not use bilinear maps. This represents significant progress towards solving the open problem of designing an IND-CCA2 secure, unidirectional, multi-use scheme not using bilinear maps proposed in \cite{CH07}\cite{SXC08}.

Proxy signature schemes allow a proxy signer to generate proxy signatures on behalf of an original signer. Mambo et al. first introduced the notion of proxy signature and a lot of research work can be found on this topic nowadays. Recently, many identity based proxy signature schemes were proposed. However, some schemes are vulnerable to proxy key exposure attack. In this paper, we propose a security model for identity based proxy signature schemes. Then an efficient scheme from pairings is presented. The presented scheme is provably secure in the random oracle model. In particular, the new scheme is secure against proxy key exposure attack.

Blind signatures (BS), introduced by Chaum, have become a cornerstone in privacy-oriented cryptography. Using hard lattice problems, such as the shortest vector problem, as the basis of security has advantages over using the factoring or discrete logarithm problems. For instance, lattice operations are more efficient than modular exponentiation and lattice problems remain hard for quantum and subexponential-time adversaries. Generally speaking, BS allow a signer to sign a message without seeing it, while retaining a certain amount of control over the process. In particular, the signer can control the number of issued signatures. For the receiver of the signature, this process provides perfect anonymity, e.g., his spendings remain anonymous when using BS for electronic money. We provide a positive answer to the question of whether it is possible to implement BS based on lattice problems. More precisely, we show how to turn Lyubashevsky's identification scheme into a BS scheme, which has almost the same efficiency and security in the random oracle model. In particular, it offers quasi-linear complexity, statistical blindness, and its unforgeability is based on the hardness of worst-case lattice problems with an approximation factor of $\cOtilde(n^{5})$ in dimension $n$. Moreover, it is the first blind signature scheme that supports leakage-resilience, tolerating leakage of a $(1-o(1))$ fraction of the secret key in a model that is inspired by Katz and Vaikuntanathan.

In this note, we describe a correction to the cryptosystem proposed by the authors in "Efficient and Secure Comparison for On-Line Auctions". Although the correction is small and does not affect the performance of the protocols proposed in that paper, it is necessary as the cryptosystem is not secure without it.

We have designed a new class of public key algorithms based on quasigroup string transformations using a specific class of quasigroups called \emph{multivariate quadratic quasigroups (MQQ)}. Our public key algorithm is a bijective mapping, it does not perform message expansions and can be used both for encryption and signatures. The public key consist of $n$ quadratic polynomials with $n$ variables where $n=140, 160, \ldots$. A particular characteristic of our public key algorithm is that it is very fast and highly parallelizable. More concretely, it has the speed of a typical modern symmetric block cipher -- the reason for the phrase \emph{"A Public Key Block Cipher"} in the title of this paper. Namely the reference C code for the 160--bit variant of the algorithm performs decryption in less than 11,000 cycles (on Intel Core 2 Duo -- using only one processor core), and around 6,000 cycles using two CPU cores and OpenMP 2.0 library. However, implemented in Xilinx Virtex-5 FPGA that is running on 249.4 MHz it achieves decryption throughput of 399 Mbps, and implemented on four Xilinx Virtex-5 chips that are running on 276.7 MHz it achieves encryption throughput of 44.27 Gbps. Compared to fastest RSA implementations on similar FPGA platforms, MQQ algorithm is more than 10,000 times faster.

Distance-bounding protocols have been proposed by Brands and Chaum in 1993 in order to detect \emph{relay attacks}, also known as \emph{mafia fraud}. Although the idea has been introduced fifteen years ago, only recently distance-bounding protocols attracted the attention of the researchers. Several new protocols have been proposed the last five years. In this paper, a new secure distance-bounding protocol is presented. It is self-contained and composable with other protocols for example for authentication or key-negotiation. It allows periodically execution and achieves better use of the communication channels by exchanging authenticated nonces. The proposed protocol becomes suitable for wider class of devices, since the resource requirements to the prover are relaxed.

This paper presents several improvements to Stern's attack on the McEliece cryptosystem and achieves results considerably better than Canteaut et al. This paper shows that the system with the originally proposed parameters can be broken in just 1400 days by a single 2.4GHz Core 2 Quad CPU,or 7 days by a cluster of 200 CPUs. This attack has been implemented and is now in progress. This paper proposes new parameters for the McEliece and Niederreiter cryptosystems achieving standard levels of security against all known attacks. The new parameters take account of the improved attack; the recent introduction of list decoding for binary Goppa codes; and the possibility of choosing code lengths that are not a power of 2. The resulting public-key sizes are considerably smaller than previous parameter choices for the same level of security.

Elliptic curves scalar multiplication over some finite fields, attractive research area, which paid much attention by researchers in the recent years. Researchs still in progress to improve elliptic curves cryptography implementation and reducing its complexity. Elliptic curve point-halving algorithm proposed in and later double-base chain and step multi-base chain are among efficient techniques offered in this field. Our paper proposes new algorithm combining step multi-base number representation and point halving. We extend the work done by K. W. Wong, which combined double base chain with point halving technique. The expriment results show our contribution will enhance elliptic curves scalar multiplication.

Network coding offers increased throughput and improved robustness to random faults in completely decentralized networks. In contrast to traditional routing schemes, however, network coding requires intermediate nodes to modify data packets en route; for this reason, standard signature schemes are inapplicable and it is a challenge to provide resilience to tampering by malicious nodes. Here, we propose two signature schemes that can be used in conjunction with network coding to prevent malicious modification of data. In particular, our schemes can be viewed as signing linear subspaces in the sense that a signature on V authenticates exactly those vectors in V. Our first scheme is homomorphic and has better performance, with both public key size and per-packet overhead being constant. Our second scheme does not rely on random oracles and uses weaker assumptions. We also prove a lower bound on the length of signatures for linear subspaces showing that both of our schemes are essentially optimal in this regard.

We consider RSA with $N = pq$, $q < p < 2q$, public encryption exponent $e$ and private decryption exponent $d$. Boneh and Durfee (Eurocrypt 1999, IEEE-IT 2000) used Coppersmith's method (Journal of Cryptology, 1997) to factorize $N$ using $e$ when $d < N^{0.292}$, the {\sf theoretical bound}. Related works have also been presented by Blömer and May (CaLC 2001). However, the {\sf experimental bound} for $d$ that has been reached so far is only $N^{0.280}$ for 1000 bits $N$ (the upper bound on $d$ less for higher number of bits). The basic idea relied on LLL algorithm, but the experimental bounds were constrained by large lattice dimensions. In this paper we present {\sf theoretical results} as well as {\sf experimental evidences} to {\sf extend the bound of} $d$ for which RSA is weak. This requires the knowledge of a few most significant bits of $p$ (alternatively these bits need to be searched exhaustively). We provide experimental results to highlight that the problem can be solved with low lattice dimensions in practice. Our strategy outperforms the existing experimental results by increasing the bounds of $d$. We provide clear evidence that RSA, with $d$ of the order of $N^{0.3}$ for 1000 bit $N$, can be cryptanalysed in practice from the knowledge of $N, e$.

We present Scratch, Click & Vote voting scheme, which is a modification of the Punchscan and ThreeBallot systems. The scheme is end-to-end veryfiable and allows for voting over the Internet. Security against malicious hardware and software used by a voter %TT is due to the fact that a voter's computer does not get any knowledge about the voter's choice. Moreover, it can change successfully a voter's ballot only with a small probability. As a side result, we present a modification of the ThreeBallot that eliminates Strauss'-like attacks on this scheme.

We show how to change one coordinate function of an almost perfect nonlinear (APN) function in order to obtain new examples. It turns out that this is a very powerful method to construct new APN functions. In particular, we show that the approach can be used to construct ``non-quadratic'' APN functions. This new example is in remarkable contrast to all recently constructed functions which have all been quadratic.

Kiltz proposed a practical key encapsulation mechanism(Kiltz07-KEM) which is secure against adaptive chosen ciphertext attacks(IND-CCA2) under the gap hashed Diffie-Hellman(GHDH) assumption\cite{Kiltz2007}. We show a variant of Kiltz07-KEM which is more efficient than Kiltz07-KEM in encryption. The new scheme can be proved to be IND-CCA2 secure under the same assumption, GHDH.

Time-Memory Tradeoff (TMTO) attacks on stream ciphers are a serious security threat and the resistance to this class of attacks is an important criterion in the design of a modern stream cipher. TMTO attacks are especially effective against stream ciphers where a variant of the TMTO attack can make use of multiple data to reduce the off-line and the on-line time complexities of the attack (given a fixed amount of memory). In this paper we present a new approach to TMTO attacks against stream ciphers using a publicly known initial value (IV): We suggest not to treat the IV as part of the secret key material (as done in current attacks), but rather to choose in advance some IVs and apply a TMTO attack to streams produced using these IVs. We show that while the obtained tradeoff curve is identical to the curve obtained by the current approach, the new technique allows to mount the TMTO attack in a larger variety of settings. For example, if both the secret key and the IV are of length n, it is possible to mount an attack with data, time, and memory complexities of 2^{4n/5}, while in the current approach, either the time complexity or the memory complexity is not less than 2^n. We conclude that if the IV length of a stream cipher is less than 1.5 times the key length, there exists an attack on the cipher with data, time, and memory complexities less than the complexity of exhaustive key search.

This document consists of a collection of attacks upon RFID protocols and is meant to serve as a quick and easy reference. This document will be updated as new attacks are found. Currently the only attacks on protocols shown are the authors' original attacks with references to similar attacks on other protocols. The main security properties considered are authentication, untraceability, and - for stateful protocols - desynchronization resistance.

In this work, we design a method for creating public key broadcast encryption systems. Our main technical innovation is based on a new ``two equation'' technique for revoking users. This technique results in two key contributions: First, our new scheme has ciphertext size overhead $O(r)$, where $r$ is the number of revoked users, and the size of public and private keys is only a \emph{constant} number of group elements from an elliptic-curve group of prime order. In addition, the public key allows us to encrypt to an unbounded number of users. Our system is the first to achieve such parameters. We give two versions of our scheme: a simpler version which we prove to be selectively secure in the standard model under a new, but non-interactive assumption, and another version that employs the new dual system encryption technique of Waters to obtain adaptive security under the d-BDH and decisional Linear assumptions. Second, we show that our techniques can be used to realize Attribute-Based Encryption (ABE) systems with non-monotonic access formulas, where our key storage is significantly more efficient than previous solutions. This result is also proven selectively secure in the standard model under our new non-interactive assumption. We believe that our new technique will be of use elsewhere as well.

Key agreement is a fundamental security functionality by which pairs of nodes agree on shared keys to be used for protecting their pairwise communications. In this work we study key-agreement schemes that are well-suited for the mobile network environment. Specifically, we describe schemes with the following haracteristics: -- Non-interactive: any two nodes can compute a unique shared secret key without interaction; -- Identity-based: to compute the shared secret key, each node only needs its own secret key and the identity of its peer; -- Hierarchical: the scheme is decentralized through a hierarchy where intermediate nodes in the hierarchy can derive the secret keys for each of its children without any limitations or prior knowledge on the number of such children or their identities; -- Resilient: the scheme is fully resilient against compromise of {\em any number of leaves} in the hierarchy, and of a threshold number of nodes in each of the upper levels of the hierarchy. Several schemes in the literature have three of these four properties, but the schemes in this work are the first to possess all four. This makes them well-suited for environments such as MANETs and tactical networks which are very dynamic, have significant bandwidth and energy constraints, and where many nodes are vulnerable to compromise. We provide rigorous analysis of the proposed schemes and discuss implementations aspects.

At EUROCRYPT 2005, Sahai and Waters presented the Fuzzy Identity Based Encryption (Fuzzy-IBE) which could be used for biometrics and attribute-based encryption in the selective-identity model. When a secure Fuzzy-IBE scheme in the selective-identity model is transformed to full identity model it exist an exponential loss of security. In this paper, we use the CPA secure Gentry's IBE (exponent inversion IBE) to construct the first Fuzzy IBE that is fully secure without random oracles. In addition, the same technique is used to the modification of CCA secure Gentry's IBE which introduced by Kiltz and Vahlis to get the CCA secure Fuzzy IBE in the full-identity model.

In this paper, we study batch codes, which were introduced by Ishai, Kushilevitz, Ostrovsky and Sahai. A batch code specifies a method to distribute a database of n items among m devices (servers) in such a way that any k items can be retrieved by reading at most t items from each of the servers. It is of interest to devise batch codes that minimize the total storage, denoted by N, over all m servers. In this paper, we study the special case t=1, under the assumption that every server stores a subset of the items. This is purely a combinatorial problem, so we call this kind of batch code a "combinatorial batch code''. For various parameter situations, we are able to present batch codes that are optimal with respect to the storage requirement, N. We also study uniform codes, where every item is stored in precisely c of the m servers (such a code is said to have rate 1/c). Interesting new results are presented in the cases c = 2, k-2 and k-1. In addition, we obtain improved existence results for arbitrary fixed c using the probabilistic method.

In a directed signature scheme, a verifier can exclusively verify the signatures designated to himself, and shares with the signer the ability to prove correctness of the signature to a third party when necessary. Directed signature schemes are suitable for applications such as bill of tax and bill of health. This paper studies directed signatures in the identity-based setting. We first present the syntax and security notion that includes unforgeability and invisibility, then propose a concrete identity-based directed signature scheme from bilinear pairings. We then prove our scheme existentially unforgeable under the computational Diffie-Hellman assumption, and invisible under the decisional Bilinear Diffie-Hellman assumption, both in the random oracle model.

We present a new approach to the design of IND-CCA2 secure hybrid encryption schemes in the standard model. Our approach provides an efficient generic transformation from 1-universal to 2-universal hash proof systems. The transformation involves a randomness extractor based on a 4-wise independent hash function as the key derivation function. Our methodology can be instantiated with efficient schemes based on standard intractability assumptions such as DDH, QR and Paillier. Interestingly, our framework also allows to prove IND-CCA2 security of a hybrid version of 1991's Damgaard's ElGamal public-key encryption scheme under the DDH assumption.

In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, security properties such as privacy, correctness, and more. One desirable property is fairness which guarantees, informally, that if one party receives its output, then the other party does too. Cleve (STOC 1986) showed that complete fairness cannot be achieved, in general, without an honest majority. Since then, the accepted folklore has been that nothing non-trivial can be computed with complete fairness in the two-party setting, and the problem has been treated as closed since the late '80s. In this paper, we demonstrate that this folklore belief is false by showing completely-fair protocols for various non-trivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an ``embedded XOR''; this class of functions includes boolean AND/OR as well as Yao's ``millionaires' problem''. We also demonstrate feasibility for certain functions that do contain an embedded XOR, and prove a lower bound showing that any completely-fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely-fair secure computation without an honest majority is far from closed.

We propose a new hybrid protocol for cryptographically secure biometric authentication. The main advantages of the proposed protocol over previous solutions can be summarised as follows: (1) potential for much better accuracy using di&#64256;erent types of biometric signals, including behavioural ones; and (2) improved user privacy, since user identities are not transmitted at any point in the protocol execution. The new protocol takes advantage of state-of-the-art identi&#64257;cation classi&#64257;ers, which provide not only better accuracy, but also the possibility to perform authentication without knowing who the user claims to be. Cryptographic security is based on the Paillier public key encryption scheme.

Concurrent signature provided a novel idea for fair exchange protocol without trusted third party. Perfect Concurrent Signature is proposed to strengthen theambiguity of the concurrent signature. Wang et al, pointed out there exist an attack against the fairness of Perfect Concurrent Signature and proposed the improved perfect concurrent signature. This paper find that in proposed (perfect) concurrent signature protocol, no matter two party or multi-party, the signer could bind multiple messages with one keystone set but let the other signers know only one of the messages. This is a new unfair case in the application of concurrent signature. Based on this observation, we propose that accountability should be one of the security properties of (perfect) concurrent signature and we give the definition of accountability of concurrent signature. To illustrate this idea, we give an attack scene against the accountability of improved perfect concurrent signature proposed by Wang et al, and propose an update version of perfect concurrent signature to avoid such attack.

We relate the fixed argument pairing inversion problems (FAPI) and the discrete logarithm problem on an elliptic curve. This is done using the reduction from the DLP to the Diffie-Hellman problem developed by Boneh, Lipton, Maurer and Wolf. This approach fails when only one of the FAPI problems can be solved. In this case we use Cheon's algorithm to get a reduction.

We construct a map injecting the set of infrastructure ideals in a real function field into the class group of the correspoding hyperelliptic curve. This map respects the `group-like' structure of the infrastructure, as a consequence of this construction we show that calculating distances in the set of infrastructure ideals is equivalent to the DLP in the underlying hyperelliptic curve. We also give a precise description of the elements missing in the infrastructure to be a group.

Abstract. The piece in hand (PH) is a general scheme which is applicable to any reasonable type of multivariate public key cryptosystems for the purpose of enhancing their security. In this paper, we propose a new class PH method called NLPHPV (NonLinear Piece in Hand Perturbation Vector) method. Although our NLPHPV uses similar perturbation vectors as is used for the previously known internal perturbation method, this new method can avoid redundant repetitions in decryption process. With properly chosen parameter sizes, NLPHPV achieves an observable gain in security from the original multivariate public key cryptosystem. We demonstrate these by both theoretical analyses and computer simulations against major known attacks and provides the concrete sizes of security parameters, with which we even expect the grater security against potential quantum attacks.

In this paper, we present a universal forgery attack on Kang et al.'s identity-based strong designated verifier signature (IBSDVS) scheme. We show anyone can forge a valid IBSDVS on an arbitrary message without the knowledge of the private key of either the signer or the designated verifier. Moreover, we point out that Kang et al.'s scheme does not satisfy the properties of strongness and non-delegatability. At last, an improved IBSDVS scheme for Kang et al.'s scheme is presented, and it is provably secure and achieves all the requirements for an IBSDVS.

LSBS-RSA denotes an RSA system with modulus primes, p and q, sharing a large number of least significant bits. In ISC 2007, Zhao and Qi analyzed the security of short exponent LSBS-RSA. They claimed that short exponent LSBS-RSA is much more vulnerable to the lattice attack than the standard RSA. In this paper, we point out that there exist some errors in the calculation of Zhao & Qi's attack. After re-calculating, the result shows that their attack is unable for attacking RSA with primes sharing bits. Consequently, we give a revised version to make their attack feasible. We also propose a new method to further extend the security boundary, compared with the revised version. The proposed attack also supports the result of analogue Fermat factoring on LSBS-RSA, which claims that p and q cannot share more than (n/4) least significant bits, where n is the bit-length of pq. In conclusion, it is a trade-off between the number of sharing bits and the security level in LSBS-RSA. One should be more careful when using LSBS-RSA with short exponents.

Group Key Establishment is fundamental for a variety of security mechanisms in group applications. It allows n > 1 principals to agree upon a common secret key. This can further be classified into Group Key Exchange (or Group Key Agreement), where all the principals participate in the construction of the key, and Group Key Transport (or Group Key Distribution), where the key is chosen by a singe principal and is then securely communicated to the others. Both these techniques can be analyzed in the context of either static or dynamic groups. Dynamic Group Key Establishment is better known as Group Key Management (GKM), as it involves not only the initital key establishment, but also efficient key management when group members join or leave the group. Dynamic Group Key Exchange is also known as decentralized or distributed GKM, while Dynamic Group Key Transport is known as centralized GKM. While there has been a lot of recent work in formal security models for Dynamic Group Key Exchange, little, if any, attention has been directed towards building a concrete framework and formal security model for centralized GKM. Many such schemes that have been proposed so far have been broken, as they cite ambiguous arguments and lack formal proofs. In this paper, we take a first step towards addressing this problem by providing firm foundations for centralized Group Key Management. We provide a generalized framework for centralized GKM along with a formal security model and strong definitions for the security properties that dynamic groups demand. We also show a generic construction of a centralized GKM scheme from any given multi-receiver ID-based Key Encapsulation Mechanism (mID-KEM). By doing so, we unify two concepts that are significantly different in terms of what they achieve. Our construction is simple and efficient. We prove that the resulting GKM inherits the security of the underlying mID-KEM up to CCA security. We also illustrate our general conversion using the mID-KEM proposed in 2007 by Delerablée.

We propose a message recognition protocol which is suitable for ad hoc pervasive networks without the use of hash chains. Hence, we no longer require the sensor motes to save values of a hash chain in their memories. This relaxes the memory requirements. Moreover, we do not need to fix the total number of times the protocol can be executed which implies a desired flexibility in this regard. Furthermore, our protocol is secure without having to consider families of assumptions that depend on the number of sessions the protocol is executed. Hence, the security does not weaken as the protocol is executed over time. Last but not least, we provide a practical procedure for resynchronization in case of any adversarial disruption or communication failure.

Some sensor network settings involve disconnected or unattended operation with periodic visits by a mobile sink. An unattended sensor network operating in a hostile environment can collect data that represents a high-value target for the adversary. Since an unattended sensor can not immediately off-load sensed data to a safe external entity (such as a sink), the adversary can easily mount a focused attack aiming to erase or modify target data. To maximize chances of data survival, sensors must collaboratively attempt to mislead the adversary and hide the location, the origin and the contents of collected data. In this paper, we focus on applications of well-known security techniques to maximize chances of data survival in unattended sensor networks, where sensed data can not be off-loaded to a sink in real time. Our investigation yields some interesting insights and surprising results. The highlights of our work are: (1) thorough exploration of the data survival challenge, (2) exploration of the design space for possible solutions, (3) construction of several practical and effective techniques, and (4) their evaluation.

The recent introduction of Edwards curves has significantly reduced the cost of addition on elliptic curves. This paper presents new explicit formulae for pairing implementation in Edwards coordinates. We prove our method gives performances similar to those of Miller's algorithm in Jacobian coordinates and is thus of cryptographic interest when one chooses Edwards curve implementations of protocols in elliptic curve cryptography. The method is faster than the recent proposal of Das and Sarkar for computing pairings on supersingular curves using Edwards coordinates.

Erasing old data and keys is an important tool in cryptographic protocol design. It is useful in many settings, including proactive security, adaptive security, forward security, and intrusion resilience. Protocols for all these settings typically assume the ability to perfectly erase information. Unfortunately, as amply demonstrated in the systems literature, perfect erasures are hard to implement in practice. We propose a model of partial erasures where erasure instructions leave almost all the data erased intact, thus giving the honest players only a limited capability for disposing of old data. Nonetheless, we provide a general compiler that transforms any secure protocol using perfect erasures into one that maintains the same security properties when only partial erasures are available. The key idea is a new redundant representation of secret data which can still be computed on, and yet is rendered useless when partially erased. We prove that any such a compiler must incur a cost in additional storage, and that our compiler is near optimal in terms of its storage overhead.

We present a new methodology for realizing Ciphertext-Policy Attribute Encryption (CP-ABE) under concrete and noninteractive cryptographic assumptions in the standard model. Our solutions allow any encryptor to specify access control in terms of any access formula over the attributes in the system. In our most efficient system, ciphertext size, encryption, and decryption time scales linearly with the complexity of the access formula. The only previous work to achieve these parameters was limited to a proof in the generic group model. We present three constructions within our framework. Our first system is proven selectively secure under a assumption that we call the decisional Parallel Bilinear Diffie-Hellman Exponent (PBDHE) assumption which can be viewed as a generalization of the BDHE assumption. Our next two constructions provide performance tradeoffs to achieve provable security respectively under the (weaker) decisional Bilinear-Diffie-Hellman Exponent and decisional Bilinear Diffie-Hellman assumptions.

Gathering and processing sensitive data is a difficult task. In fact, there is no common recipe for building the necessary information systems. In this paper, we present a provably secure and efficient general-purpose computation system to address this problem. Our solution - SHAREMIND - is a virtual machine for privacy-preserving data processing that relies on share computing techniques. This is a standard way for securely evaluating functions in a multi-party computation environment. The novelty of our solution is in the choice of the secret sharing scheme and the design of the protocol suite. We have made many practical decisions to make large-scale share computing feasible in practice. The protocols of SHAREMIND are information-theoretically secure in the honest-but-curious model with three computing participants. Although the honest-but-curious model does not tolerate malicious participants, it still provides significantly increased privacy preservation when compared to standard centralised databases.

We present a birthday attack against DES. It is entirely based on the relationship $L_{i+1}=R_{i}$ and the simple key schedule in DES. It requires about $2^{16}$ ciphertexts of the same $R_{16}$, encrypted by the same key $K$. We conjecture it has a computational complexity of $2^{48}$. Since the requirement for the birthday attack is more accessible than that for Differential cryptanalysis, Linear cryptanalysis or Davies' attack, it is of more practical significance.

Pease {\em et al.}\/ introduced the problem of Byzantine Generals (BGP) to study the effects of Byzantine faults in distributed protocols for reliable broadcast. It is well known that BGP among $n$ players tolerating up to $t$ faults is (efficiently) possible if and only if $n > 3t$. To overcome this severe limitation, Pease {\em et al.} introduced a variant of BGP, \emph{Authenticated Byzantine General} (ABG). Here players are supplemented with digital signatures (or similar tools) to thwart the challenge posed by Byzantine faults. Subsequently, they proved that with the use of authentication, fault tolerance of protocols for reliable broadcast can be amazingly increased to $n > t$ (which is a huge improvement over the $n > 3t$). Byzantine faults are the most generic form of faults. In a network not {\em all} faults are always malicious. Some faulty nodes may only leak their data while others are malicious. Motivated from this, we study the problem of ABG in ($t_b$,$t_p$)-mixed adversary model where the adversary can corrupt up to any $t_b$ players actively and control up to any other $t_p$ players passively. We prove that in such a setting, ABG over a completely connected synchronous network of $n$ nodes tolerating a ($t_b$,$t_p$)-adversary is possible if and only if $n > 2t_b$+min($t_b,t_p$) when $t_p > 0$. Interestingly, our results can also be seen as an attempt to unify the extant literature on BGP and ABG.

The one-up problem is defined for any group and a function from the group to integers. An instance of problem consists of two points in the group. A solution consists of another point satisfying an equation involving the group and the function. The one-up problem must be hard for the security of (EC)DSA. Heuristic arguments are given for the independence of the discrete log and one-up problems. DSA and ECDSA are conjectured to be secure if the discrete log and one-up problems are hard and the hash is collision resistant.

Multi-exponentiation is a common and time consuming operation in public-key cryptography. Its elliptic curve counterpart, called multi-scalar multiplication is extensively used for digital signature verification. Several algorithms have been proposed to speed-up those critical computations. They are based on simultaneously recoding a set of integers in order to minimize the number of general multiplications or point additions. When signed-digit recoding techniques can be used, as in the world of elliptic curves, Joint Sparse Form (JSF) and interleaving $w$-NAF are the most efficient algorithms. In this paper, a novel recoding algorithm for a pair of integers is proposed, based on a decomposition that mixes powers of 2 and powers of 3. The so-called Hybrid Binary-Ternary Joint Sparse Form require fewer digits and is sparser than the JSF and the interleaving $w$-NAF. Its advantages are illustrated for elliptic curve double-scalar multiplication; the operation counts show a gain of up to 18\%.

Akiyama and Goto have proposed a cryptosystem based on rational points on curves over function fields (stated in the equivalent form of sections of fibrations on surfaces). It is easy to construct a curve passing through a few given points, but finding the points, given only the curve, is hard. We show how to break their original cryptosystem by using algebraic points instead of rational points and discuss possibilities for changing their original system to create a secure one.

Singelee and Preneel have recently proposed a enhancement of Hancke and Kuhn's distance bounding protocol for RFID. The authors claim that their protocol offers substantial reductions in the number of rounds, though preserving its advantages: suitable to be employed in noisy wireless environments, and requiring so few resources to run that it can be implemented on a low-cost device. Subsequently, the same authors have also proposed it as an efficient key establishment protocol in wireless personal area networks. Nevertheless, in this paper we show effective relay attacks on this protocol, which dramatically increase the success probability of an adversary. As a result, the effectiveness of Singelee and Preneel's protocol is seriously questioned.

Group key agreement (GKA) allows a set of players to establish a shared secret and thus bootstrap secure group communication. GKA is very useful in many types of peer group scenarios and applications. Since all GKA protocols involve multiple rounds, robustness to player failures is important and desirable. A robust group key agreement (RGKA) protocol runs to completion even if some players fail during protocol execution. Previous work yielded constant-round RGKA protocols suitable for the LAN setting, assuming players are homogeneous, failure probability is uniform and player failures are independent. However, in a more general widearea network (WAN) environment, heterogeneous hardware/software and communication facilities can cause wide variations in failure probability among players. Moreover, congestion and communication equipment failures can result in correlated failures among subsets of GKA players. In this paper, we construct the first RGKA protocol that supports players with different failure probabilities, spread across any LAN/WAN combination, while also allowing for correlated failures among subgroups of players. The proposed protocol is efficient (2 rounds) and provably secure. We evaluate its robustness and performance both analytically and via simulations.

SMS4 is a 128-bit block cipher with a 128-bit user key and 32 rounds, which is used in WAPI, the Chinese WLAN national standard. In this paper, we present a linear attack and a differential attack on a 22-round reduced SMS4; our 22-round linear attack has a data complexity of 2^{117} known plaintexts, a memory complexity of 2^{109} bytes and a time complexity of 2^{109.86} 22-round SMS4 encryptions and 2^{120.39} arithmetic operations, while our 22-round differential attack requires 2^{118} chosen plaintexts, 2^{123} memory bytes and 2^{125.71} 22-round SMS4 encryptions. Both of our attacks are better than any previously known cryptanalytic results on SMS4 in terms of the number of attacked rounds. Furthermore, we present a boomerang and a rectangle attacks on a 18-round reduced SMS4. These results are better than previously known rectangle attacks on reduced SMS4. The methods presented to attack SMS4 can be applied to other unbalanced Feistel ciphers with incomplete diffusion.

Since their introduction in constructive cryptographic applications, pairings over (hyper)elliptic curves are at the heart of an ever increasing number of protocols. As they rely critically on efficient algorithms and implementations of pairing primitives, the study of hardware accelerators became an active research area. In this paper, we propose two coprocessors for the reduced $\eta_T$ pairing introduced by Barreto {\it et al.} as an alternative means of computing the Tate pairing on supersingular elliptic curves. We prototyped our architectures on FPGAs. According to our place-and-route results, our coprocessors compare favorably with other solutions described in the open literature. We also present the first ASIC implementation of the reduced $\eta_T$ pairing.

In predicate encryption systems, given a capability, one can evaluate one or more predicates on the encrypted data, while all other information about the plaintext remains hidden. We consider the first such systems to permit delegation of capabilities. In a system that supports delegation, a user Alice who has a capability can delegate to Bob a more restrictive capability, which allows him to learn less about encrypted data than she did. We formally define delegation in predicate encryption systems, and propose a new security definition for delegation. In addition, we present an efficient construction supporting conjunctive queries. The security of our construction can be reduced to the general 3-party Bilinear Diffie-Hellman assumption, and the Bilinear Decisional Diffie-Hellman assumption in composite-order bilinear groups.

We consider the problem of building robust fuzzy extractors, which allow two parties holding similar random variables W, W' to agree on a secret key R in the presence of an active adversary. Robust fuzzy extractors were defined by Dodis et al. in Crypto 2006 to be noninteractive, i.e., only one message P, which can be modified by an unbounded adversary, can pass from one party to the other. This allows them to be used by a single party at different points in time (e.g., for key recovery or biometric authentication), but also presents an additional challenge: what if R is used, and thus possibly observed by the adversary, before the adversary has a chance to modify P. Fuzzy extractors secure against such a strong attack are called post-application robust. We construct a fuzzy extractor with post-application robustness that extracts a shared secret key of up to (2m-n)/2 bits (depending on error-tolerance and security parameters), where n is the bit-length and m is the entropy of W. The previously best known result, also of Dodis et al., extracted up to (2m-n)/3 bits (depending on the same parameters).

A successful strategy was identified for any Verifier colluding with any Issuer to distinguish honest Provers issuing DAA signatures. An additional verification equation was introduced for a Prover to detect 'tagged' credentials that may be issued while Join protocol. This verification can be done by the Host and do not affect TPM in any way.

Confidentiality and authenticity are two of the most fundamental problems in cryptography. Many applications require both confidentiality and authenticity, and hence an efficient way to get both together was very desirable. In 1997, Zheng proposed the notion of ``signcryption'', a single primitive which provides both confidentiality and authenticity in a way that's more efficient than signing and encrypting separately. Proxy re-encryption is a primitive that allows a semi-trusted entity called the ``proxy'' to convert ciphertexts addressed to a ``delegator'' to those that can be decrypted by a ``delegatee'', by using some special information given by the delegator, called the ``rekey''. In this work, we propose the notion of signcryption with proxy re-encryption (SCPRE), and motivate the same. We define security models for SCPRE, and also propose a concrete unidirectional, non-interactive identity-based SCPRE construction. We also provide complete proofs of security for the scheme in the security models defined. We finally provide directions for further research in this area.

In this paper, we propose two new certificate-based signature (CBS) schemes with new features and advantages. The first one is very efficient as it does not require any pairing computation and its security can be proven using Discrete Logarithm assumption in the random oracle model. We also propose another scheme whose security can be proven in the standard model without random oracles. To the best of our knowledge, these are the \emph{first} CBS schemes in the literature that have such kind of features.

In this paper we show that the twisted Ate pairing on elliptic curves can be generalized to hyperelliptic curves, we also give a series of variations of the hyperelliptic Ate and twisted Ate pairings. Using the hyperelliptic Ate pairing and twisted Ate pairing, we propose a new approach to speed up the Weil pairing computation, and obtain an interested result: For some hyperelliptic curves with high degree twist, using this approach to compute Weil pairing will be faster than Tate pairing, Ate pairing etc. all known pairings.

A key research question in computer security is whether one can implement software that offers some protection against software attacks from its execution platform. While code obfuscation attempts to hide certain characteristics of a program P, white-box cryptography specifically focusses on software implementations of cryptographic primitives (such as encryption schemes); the goal of a white-box implementation is to offer a certain level of robustness against an adversary who has full access to and control over the implementation of the primitive. Several formal models for obfuscation have been presented before, but it is not clear if any of these definitions can capture the concept of white-box cryptography. In this paper, we discuss the relation between obfuscation and white-box cryptography, and formalize the notion of white-box cryptography by capturing the security requirement using a 'White-Box Property' (WBP). In the second part, we present positive and negative results on white-box cryptography. We show that for interesting programs (such as encryption schemes, and digital signature schemes), there are security notions that cannot be satisfied when adversaries have white-box access, while the notion is satisfied when the adversary has black-box access to its functionality. On the positive side, we show that there exists an obfuscator for a symmetric encryption scheme for which a useful security notion (such as CPA security) remains satisfied when an adversary has access to its white-box implementation.

In this work, we study several properties of the SHA-2 design which have been utilized in recent collision attacks against reduced round SHA-2. Small modifications to the SHA-2 design are suggested to thwart these attacks. The modified round function provides the same resistance to linearization attacks as the original SHA-2 round function, but, provides better resistance to non-linear attacks. Our next contribution is to introduce the general idea of ``multiple feed-forward" for the construction of cryptographic hash functions. This can provide increased resistance to the Chabaud-Joux type ``perturbation-correction'' collision attacks. The idea of feed-forward is taken further by introducing the idea of feed-forward across message blocks leading to resistance against generic multi-collision attacks. The net effect of the suggested changes to the SHA-2 design has insignificant impact on the efficiency of computing the digest.

We perform a combinatorial analysis of SHA-2 compression function. This analysis explains in a unified way the recent attacks against reduced round SHA-2. We start with a general class of local collisions and show that the previously used local collision by Nikolić and Biryukov (NB) and Sanadhya and Sarkar (SS) are special cases. The study also clarifies several advantages of the SS local collision over the NB local collision. Deterministic constructions of up to 22-round SHA-2 collisions are described using the SS local collision and up to 21-round SHA-2 collisions are described using the NB local collision. For 23 and 24-round SHA-2, we describe a general strategy and then apply the SS local collision to this strategy. The resulting attacks are faster than those proposed by Indesteege et al using the NB local collision. We provide colliding message pairs for 22, 23 and 24-round SHA-2. Although these attacks improve upon the existing reduced round SHA-256 attacks, they do not threaten the security of the full SHA-2 family. \footnote{This work builds upon and subsumes previous work done by us. Whereas the previous works focused on obtaining collisions for fixed number of rounds, the current work provides the combinatorial framework for understanding how such collisions arise.}

In this work, we provide new and improved attacks against 22, 23 and 24-step SHA-2 family using a local collision given by Sanadhya and Sarkar (SS) at ACISP '08. The success probability of our 22-step attack is 1 for both SHA-256 and SHA-512. The computational efforts for the 23-step and 24-step SHA-256 attacks are respectively $2^{11.5}$ and $2^{28.5}$ calls to the corresponding step reduced SHA-256. The corresponding values for the 23 and 24-step SHA-512 attack are respectively $2^{16.5}$ and $2^{32.5}$ calls. Using a look-up table having $2^{32}$ (resp. $2^{64}$) entries the computational effort for finding 24-step SHA-256 (resp. SHA-512) collisions can be reduced to $2^{15.5}$ (resp. $2^{22.5}$) calls. We exhibit colliding message pairs for 22, 23 and 24-step SHA-256 and SHA-512. This is the \emph{first} time that a colliding message pair for 24-step SHA-512 is provided. The previous work on 23 and 24-step SHA-2 attacks is due to Indesteege et al. and utilizes the local collision presented by Nikolić and Biryukov NB) at FSE '08. The reported computational efforts are $2^{18}$ and $2^{28.5}$ for 23 and 24-step SHA-256 respectively and $2^{43.9}$ and $2^{53}$ for 23 and 24-step SHA-512. The previous 23 and 24-step attacks first constructed a pseudo-collision and later converted it into a collision for the reduced round SHA-2 family. We show that this two step procedure is unnecessary. Although these attacks improve upon the existing reduced round SHA-2 attacks, they do not threaten the security of the full SHA-2 family.

In this work we revisit the known algorithms for searching for low weight codewords in linear binary codes. We propose some improvements on them and also propose a new efficient heuristic.

We present new techniques for achieving adaptive security in broadcast encryption systems. Previous work on fully-collusion resistant broadcast encryption with short ciphertexts was limited to only considering static security. First, we present a new definition of security that we call semi-static security and show a generic ``two-key" transformation from semi-statically secure systems to adaptively secure ones that have comparable-sized ciphertexts. Using bilinear maps, we then construct broadcast encryption systems that are semi-statically secure in the standard model and have constant size ciphertexts. Our semi-static constructions work when the number of indices or identifiers in the system is polynomial in the security parameter. For identity-based broadcast encryption, where the number of potential indices or identifiers may be exponential, we present the first adaptively secure system with sublinear ciphertexts. We prove security in the standard model.

We strengthen the foundations of deterministic public-key encryption via definitional equivalences and standard-model constructs based on general assumptions. Specifically we consider seven notions of privacy for deterministic encryption, including six forms of semantic security and an indistinguishability notion, and show them all equivalent. We then present a deterministic scheme for the secure encryption of uniformly and independently distributed messages based solely on the existence of trapdoor one-way permutations. We show a generalization of the construction that allows secure deterministic encryption of independent high-entropy messages. Finally we show relations between deterministic and standard (randomized) encryption.

We present three voting protocols with unconditional privacy and information-theoretic correctness, without assuming any bound on the number of corrupt voters or voting authorities. All protocols have polynomial complexity and require private channels and a simultaneous broadcast channel. Our first protocol is a basic voting scheme which allows voters to interact in order to compute the tally. Privacy of the ballot is unconditional, but any voter can cause the protocol to fail, in which case information about the tally may nevertheless transpire. Our second protocol introduces voting authorities which allow the implementation of the first protocol, while reducing the interaction and limiting it to be only between voters and authorities and among the authorities themselves. The simultaneous broadcast is also limited to the authorities. As long as a single authority is honest, the privacy is unconditional, however, a single corrupt authority or a single corrupt voter can cause the protocol to fail. Our final protocol provides a safeguard against corrupt voters by enabling a verification technique to allow the authorities to revoke incorrect votes. We also discuss the implementation of a simultaneous broadcast channel with the use of temporary computational assumptions, yielding versions of our protocols achieving everlasting security.

We discuss arithmetic in the Jacobian of a hyperelliptic curve $C$ of genus $g$. The traditional approach is to fix a point $P_\infty \in C$ and represent divisor classes in the form $E - d(P_\infty)$ where $E$ is effective and $0 \le d \le g$. We propose a different representation which is balanced at infinity. The resulting arithmetic is more efficient than previous approaches when there are 2 points at infinity. This is a corrected and extended version of the article presented in ANTS 2008. We include an appendix with explicit formulae to compute a very efficient `baby step' in genus 2 hyperelliptic curves given by an imaginary model.

It is well known that general secure function evaluation (SFE) with information-theoretical (IT) security is infeasible in presence of a corrupted majority in the standard model. On the other hand, there are SFE protocols (Goldreich et al.~[STOC'87]) that are computationally secure (without fairness) in presence of an actively corrupted majority of the participants. Now, the issue with computational assumptions is not so much that they might be unjustified at the time of protocol execution. Rather, we are usually worried about a potential violation of the privacy of sensitive data by an attacker whose power increases over time (e.g.~due to new technical developments). Therefore, we ask which functions can be computed with long-term security, where we admit computational assumptions for the duration of a computation, but require IT security (privacy) once the computation is concluded. Toward this end we combinatorially characterize the classes of functions that can be computed IT securely in the authenticated channels model in presence of passive, semi-honest, active, and quantum adversaries (our results for quantum adversaries and in part for active adversaries are limited to the 2-party setting). In particular we obtain results on the fair computability of functions in the IT setting along the lines of the work of Gordon et al.~[STOC'08] for the computational setting. Our treatment is constructive in the sense that if a function is computable in a given setting, then we exhibit a protocol. We show that the class of functions computable with long-term security in a very practical setting where the adversary may be active and insecure channels and a public-key infrastructure are provided is precisely the class of functions computable with IT security in the authenticated channels model in presence of a semi-honest adversary. Finally, from our results and the work of Kushilevitz [SIAM Journal on Discrete Mathematics '92] and Kraschewski and Müller-Quade we can derive a complete combinatorial classification of functions, by secure computability and completeness under passive, semi-honest, active, and quantum adversaries.

This paper studies the application of slide attacks to hash functions. Slide attacks have mostly been used for block cipher cryptanalysis. But, as shown in the current paper, they also form a potential threat for hash functions, namely for sponge-function like structures. As it turns out, certain constructions for hash-function-based MACs can be vulnerable to forgery and even to key recovery attacks. In other cases, we can at least distinguish a given hash function from a random oracle. To illustrate our results, we describe attacks against the Grindahl-256 and Grindahl-512 hash functions. To the best of our knowledge, this is the first cryptanalytic result on Grindahl-512. Furthermore, we point out a slide-based distinguisher attack on a slightly modified version of RadioGatun. We finally discuss simple countermeasures as a defense against slide attacks.

Consider the following problem: a sender S and a receiver R are part of a directed synchronous network and connected through intermediate nodes. Specifically, there exists n node disjoint paths, also called as wires, which are directed from S to R and u wires, which are directed from R to S. Moreover, the wires from S to R are disjoint from the wires directed from R to S. There exists a centralized, static adversary who has unbounded computing power and who can control at most t wires between S and R in Byzantine fashion. S has a message m^S, which we wants to send to R. The challenge is to design a protocol, such that after interacting in phases as per the protocol, R should correctly output m^R = m^S, except with error probability 2^{-\Omega(\kappa)}, where \kappa is the error parameter. This problem is called as statistically reliable message transmission (SRMT). The problem of statistically secure message transmission (SSMT) has an additional requirement that at the end of the protocol, m^S should be information theoretically secure. Desmedt et.al have given the necessary and sufficient condition for the existence of SRMT and SSMT protocols in the above settings. They also presented an SSMT protocol, satisfying their characterization. Desmedt et.al claimed that their protocol is efficient and has polynomial computational and communication complexity. However, we show that it is not so. That is, we specify an adversary strategy, which may cause the protocol to have exponential computational and communication complexity. We then present new and efficient SRMT and SSMT protocols, satisfying the characterization of Desmedt et.al Finally we show that the our proposed protocols are communication optimal by deriving lower bound on the communication complexity of SRMT and SSMT protocols. As far our knowledge is concerned, our protocols are the first communication optimal SRMT and SSMT protocols in directed networks.

In this paper we study a novel computational problem called the Hidden Root Problem, which appears naturally when considering fault attacks on pairing based cryptosystems. Furthermore, a variant of this problem is one of the main obstacles for efficient pairing inversion. We present an algorithm to solve this problem over extension fields and investigate for which parameters the algorithm becomes practical.

We show that a generic ring algorithm for breaking RSA in $\mathbb{Z}_N$ can be converted into an algorithm for factoring the corresponding RSA-modulus $N$. Our results imply that any attempt at breaking RSA without factoring $N$ will be non-generic and hence will have to manipulate the particular bit-representation of the input in $\mathbb{Z}_N$. This provides new evidence that breaking RSA may be equivalent to factoring the modulus.

In this paper, we propose a method to get the lower bounds of the 2-adic complexity of a sequence obtained from a periodic sequence over GF(2) by either inserting or deleting k symbols within one period. The results show the variation of the distribution of the 2-adic complexity becomes as k increases. Particularly, we discuss the lower bounds when k respectively.

This study digs out some new algebraic properties of an Osborn loop that will help in the future to unveil the mystery behind the middle inner mappings $T_{(x)}$ of an Osborn loop. These new algebraic properties, will open our eyes more to the study of Osborn loops like CC-loops which has received a tremendious attention in this $21^\textrm{st}$ and VD-loops whose study is yet to be explored. In this study, some algebraic properties of non-WIP Osborn loops have been investigated in a broad manner. Huthnance was able to deduce some algebraic properties of Osborn loops with the WIP i.e universal weak WIPLs. So this work exempts the WIP. Two new loop identities, namely left self inverse property loop(LSIPL) identity and right self inverse property loop(RSLPL) are introduced for the first time and it is shown that in an Osborn loop, they are equivalent. A CC-loop is shown to be power associative if and only if it is a RSLPL or LSIPL. Among the few identities that have been established for Osborn loops, one of them is recognized and recommended for cryptography in a similar spirit in which the cross inverse property has been used by Keedwell following the fact that it was observed that Osborn loops that do not have the LSIP or RSIP or 3-PAPL or weaker forms of inverse property, power associativity and diassociativity to mention a few, will have cycles(even long ones). These identity is called an Osborn cryptographic identity(or just a cryptographic identity).

This study presents a special type of middle isotopism under which $m$-inverse quasigroups are isotopic invariant. A sufficient condition for an $m$-inverse quasigroup that is specially isotopic to a quasigroup to be isomorphic to the quasigroup isotope is established. It is shown that under this special type of middle isotopism, if $n$ is a positive even integer, then, a quasigroup is an $m$-inverse quasigroup with an inverse cycle of length $nm$ if and only if its quasigroup isotope is an $m$-inverse quasigroup with an inverse cycle of length $nm$. But when $n$ is an odd positive integer. Then, if a quasigroup is an $m$-inverse quasigroup with an inverse cycle of length $nm$, its quasigroup isotope is an $m$-inverse quasigroup with an inverse cycle of length $nm$ if and only if the two quasigroups are isomorphic. Hence, they are isomorphic $m$-inverse quasigroups. Explanations and procedures are given on how these results can be used to apply $m$-inverse quasigroups to cryptography, double cryptography and triple cryptography.

This study presents a special type of middle isotopism under which the weak inverse property(WIP) is isotopic invariant in loops. A sufficient condition for a WIPL that is specially isotopic to a loop to be isomorphic to the loop isotope is established. Cross inverse property loops(CIPLs) need not satisfy this sufficient condition. It is shown that under this special type of middle isotopism, if $n$ is a positive even integer, then a WIPL has an inverse cycle of length $n$ if and only if its isotope is a WIPL with an inverse cycle of length $n$. But, when $n$ is an odd positive integer. If a loop or its isotope is a WIPL with only $e$ and inverse cycles of length $n$, its isotope or the loop is a WIPL with only $e$ and inverse cycles of length $n$ if and only if they are isomorphic. So, that both are isomorphic CIPLs. Explanations and procedures are given on how these results can be used to apply CIPLs to cryptography.

In this paper, we present three embedding schemes for extensions of least significant bit overwriting to both of the two lowest bit planes in digital images. Our approaches are inspired by the work of Fridrich et al. [8] who proposed wet paper coding as an efficient method for steganographic schemes. Our new works generalize it to the embedding in two least significant bits, that is to say, combine two novel extensions of least significant bits embedding and the double-layered embedding developed in [16] with wet paper coding, respectively. The proposed schemes improve steganographic security and are less vulnerable to steganalytic attacks compared with original schemes with shared selection channels between the sender and the recipient.

ID-based ring signcryption schemes (IDRSC) are usually derived from bilinear parings, a powerful but computationally expensive primitive. The number of paring computations of all existing ID-based ring signcryption schemes from bilinear pairings grows linearly with the group size, which makes the efficiency of ID-based schemes over traditional schemes questionable. In this paper, we present a new identity-based ring signcryption scheme, which only takes four pairing operations for any group size and the scheme is proven to be indistinguishable against adaptive chosen ciphertext ring attacks (IND-IDRSC-CCA2) and secure against an existential forgery for adaptive chosen messages attacks (EF-IDRSC-ACMA).

Secure group communication is significant for wireless and mobile computing. Overheads can be reduced efficiently when a sender sends multiple messages to multiple recipients using multi-recipient signcryption schemes. In this paper, we proposed the formal definition and security model of multi-recipient signcryption, presented the definition of reproducible signcryption and proposed security theorems for randomness reusing based multi-recipient signcryption schemes. We found that a secure reproducible signcryption scheme can be used to construct an efficient multi-recipient signcryption scheme which has the same security level as the underlying base signcryption scheme. We constructed a multi-recipient scheme which is provable secure in random oracle model assuming that the GDH problem is hard, based on a new BLS-type signcryption scheme. Overheads of the new scheme are only (n+1)/2n times of traditional ways when a sender sends different messages to n distinct recipients. It is more efficient than other known schemes. It creates a possibility for the practice of the public key cryptosystem in ubiquitous computing.

We study security of digital signature schemes in tamper-proof device model. In this model each participant of the protocol has access to a tamper-proof device to encrypt hash values. This substitutes commonly used random oracle. In the tamper-proof device model we demonstrate security of a modified version of the GOST signature scheme.

We present a security analysis of the complete TLS protocol in the Universal Composable security framework. This analysis evaluates the composition of key exchange functionalities realized by the TLS handshake with the message transmission of the TLS record layer to emulate secure communication sessions and is based on the adaption of the secure channel model from Canetti and Krawczyk to the setting where peer identities are not necessarily known prior the protocol invocation and may remain undisclosed. Our analysis shows that TLS, including the Diffie-Hellman and key transport suites in the uni-directional and bi-directional models of authentication, securely emulates secure communication sessions.

We analyse the efficiency of pairing computations on hyperelliptic curves given by a real model using a balanced divisor at infinity. Several optimisations are proposed and analysed. Genus two curves given by a real model arise when considering pairing friendly groups of order dividing $p^{2}-p+1$. We compare the performance of pairings on such groups in both elliptic and hyperelliptic versions. We conclude that pairings can be efficiently computable in real models of hyperelliptic curves.

In this paper, we describe a method to construct (n, m, t) resilient functions which satisfy multiple cryptographic criteria including high nonlinearity, good resiliency, high algebraic degree, and nonexistence of nonzero linear structure. Given a [u, m, t+1] linear code, we show that it is possible to construct (n, m, t) resilient functions with multiple good cryptographic criteria, where 2m &lt; u &lt; n.

Recently, Byun et al. proposed an efficient client-to-client password-authenticated key agreement protocol (EC2C-PAKA), which was provably secure in a formally defined security model. This letter shows that EC2C-PAKA protocol is vulnerable to password compromise impersonate attack and man-in-the-middle attack if the key between servers is compromised.

Broadcast signcryption enables the broadcaster to simultaneously encrypt and sign the content meant for a specific set of users in a single logical step. It provides a very efficient solution to the dual problem of achieving confidentiality and authentication during content distribution. Among other alternatives, ID-based schemes are arguably the best suited for its implementation in wireless ad-hoc networks because of the unique advantage that they provide - any unique, publicly available parameter of a user can be his public key, which eliminates the need for a complex public key infrastructure. In 2004, Bohio et al. [4] proposed an ID-based broadcast signcryption (IBBSC) scheme which achieves constant ciphertext size. They claim that their scheme provides both message authentication and confidentiality, but do not give formal proofs. In this paper, we demonstrate how a legitimate user of the scheme can forge a valid signcrypted ciphertext, as if generated by the broadcaster. Moreover, we show that their scheme is not IND-CCA secure. Following this, we propose a fix for Bohio et al.'s scheme, and formally prove its security under the strongest existing security models for broadcast signcryption (IND-CCA2 and EUF-CMA). While fixing the scheme, we also improve its efficiency by reducing the ciphertext size to two elements compared to three in [4].

The Random Oracle Model and the Ideal Cipher Model are two well known idealised models of computation for proving the security of cryptosystems. At Crypto 2005, Coron et al. showed that security in the random oracle model implies security in the ideal cipher model; namely they showed that a random oracle can be replaced by a block cipher-based construction, and the resulting scheme remains secure in the ideal cipher model. The other direction was left as an open problem, i.e. constructing an ideal cipher from a random oracle. In this paper we solve this open problem and show that the Feistel construction with 6 rounds is enough to obtain an ideal cipher; we also show that 5 rounds are insufficient by providing a simple attack. This contrasts with the classical Luby-Rackoff result that 4 rounds are necessary and sufficient to obtain a (strong) pseudo-random permutation from a pseudo-random function.

An attack on a recently proposed authentication scheme of Shpilrain and Ushakov is presented. The public information allows the derivation of a system of polynomial equations for the secret key bits. Our attack uses simple elimination techniques to distill linear equations. For the proposed parameter choice, the attack often finds secret keys or alternative secret keys within minutes with moderate resources.

We study an infinite class of functions which provably achieve an optimum algebraic immunity, an optimum algebraic degree and a good nonlinearity. We checked that it has also a good behavior against fast algebraic attacks.

We analyze how well forensic systems reduce counterfeiting of soft- ware and content. We make a few idealized assumptions, and show that if the revenues of the producer before the introduction of forensics (Ro) are non-zero then the payoff of forensics is independent of the overall market size, it declines as the ratio between the penalty and the crime (both monetized) goes up, but that this behavior is reversed if Ro = 0. We also show that the payoff goes up as the ratio between success probability with and without forensics grows; however, for typical parameters most of the payoff is already reached when this ratio is 5.

Rotation symmetric functions have been used as components of different cryptosystems. This class of functions are invariant under circular translation of indices. In this paper, we will do some enumeration on homogeneous rotation symmetric functions over GF(p). And we givea formula to count homogeneous rotation symmetric functions when the greatest common divisor of input variable n and the degree d is a power of a prime, which solves the open problem in [7].

HB and HB+ are a shared-key authentication protocol designed for low-cost devices such as RFID tags. It was proposed by Juels and Weis at Crypto 2005. The security of the protocol relies on the ``learning parity with noise'' (LPN) problem, which was proved to be NP-hard. The best known attack on LPN (by Levieil and Fouque, SCN 2006) requires exponential number of samples and exponential number of operations to be performed. This makes this attack impractical because it is infeasible to collect exponentially-many observations of the protocol execution. We present a passive attack on HB protocol which requires only linear (to the length of the secret key) number of samples. Number of performed operations is still exponential, but attack is efficient for some real-life values of the parameters, i.~e.~noise $\frac{1}{8}$ and key length $144$-bits.

We construct a stream-cipher $\SC$ whose \emph{implementation} is secure even if arbitrary (adversely chosen) information on the internal state of $\SC$ is leaked during computation. This captures \emph{all} possible side-channel attacks on $\SC$ where the amount of information leaked in a given period is bounded, but overall can be arbitrary large, in particular much larger than the internal state of $\SC$. The only other assumption we make on the \emph{implementation} of $\SC$ is that only data that is accessed during computation leaks information. The construction can be based on any pseudorandom generator, and the only computational assumption we make is that this PRG is secure against non-uniform adversaries in the classical sense (i.e. when there are no side-channels). The stream-cipher $\SC$ generates its output in chunks $K_1,K_2,\ldots$, and arbitrary but bounded information leakage is modeled by allowing the adversary to adaptively chose a function $f_\ell:\bin^*\rightarrow\bin^\lambda$ before $K_\ell$ is computed, she then gets $f_\ell(\tau_\ell)$ where $\tau_\ell$ is the internal state of $\SC$ that is accessed during the computation of $K_\ell$. One notion of security we prove for $\SC$ is that $K_\ell$ is indistinguishable from random when given $K_1,\ldots,K_{\ell-1}$, $f_1(\tau_1),\ldots, f_{\ell-1}(\tau_{\ell-1})$ and also the complete internal state of $\SC$ after $K_{\ell}$ has been computed (i.e. our cipher is forward-secure). The construction is based on alternating extraction (previously used in the intrusion-resilient secret-sharing scheme from FOCS'07). We move this concept to the computational setting by proving a lemma that states that the output of any PRG has high HILL pseudoentropy (i.e. is indistinguishable from some distribution with high min-entropy) even if arbitrary information about the seed is leaked. The amount of leakage $\leak$ that we can tolerate in each step depends on the strength of the underlying PRG, it is at least logarithmic, but can be as large as a constant fraction of the internal state of $\SC$ if the PRG is exponentially hard.

We examine the problem of message and entity recognition in the context of ad hoc networks. We review the definitions and the security model described in the literature and examine previous recognition protocols described in ABCLMN98, HWGW05, LZWW05, M03, and WW03. We prove that there is a one to one correspondence between non-interactive message recognition protocols and digital signature schemes. Hence, we concentrate on designing interactive recognition protocols. We look at LZWW05 in more detail and suggest a variant to overcome a certain shortcoming. In particular, in case of communication failure or adversarial disruption, this protocol is not equipped with a practical resynchronization process and can fail to resume. We propose a variant of this protocol which is equipped with a resynchronization technique that allows users to resynchronize whenever they wish or when they suspect an intrusion.

In ATC 2007, an identity based signcryption scheme for multiple receivers was proposed by Yu et al. In this paper, we first show that Yu et al.'s signcryption scheme is insecure by demonstrating an universal forgeability attack - anyone can generate a valid signcryption on any message on behalf of any legal user for any set of legal receivers without knowing the secret keys of the legal users. Also, we point out a subtle flaw in the proof of confidentiality given by Yu et al. and show that the scheme does not provide confidentiality. Further, we propose a corrected version of Yu et al.'s scheme and formally prove its security (confidentiality and unforgeability) under the existing security model for signcryption.\\ In another direction, Fagen Li et al. have proposed a pairing based multi-recipient signcryption scheme which works in public key infrastructure (PKI). We show that, the scheme proposed by Fagen Li et al. is not adaptive chosen ciphertext secure. We propose a new PKI based multi-receiver signcryption scheme and formally prove confidentiality and unforgeability of the scheme. Since all the previously reported schemes are shown to have flaws either in this paper or else where, the schemes reported in this paper are the only correct and efficient ones (both identity based and PKI based) for multi-receiver signcryption.

We propose a novel efficient cryptanalytic technique allowing an adversary to recover an initial state of filter generator given its output sequence. The technique is applicable to filter generators possessing local affinity property.

We study the security of the widely deployed Secure Session Layer/Transport Layer Security (TLS) key agreement protocol. Our analysis identifies, justifies, and exploits the modularity present in the design of the protocol: the {\em application keys} offered to higher level applications are obtained from a {\em master key}, which in turn is derived, through interaction, from a {\em pre-master key}. Our first contribution consists of formal models that clarify the security level enjoyed by each of these types of keys. The models that we provide fall under well established paradigms in defining execution, and security notions. We capture the realistic setting where only one of the two parties involved in the execution of the protocol (namely the server) has a certified public key, and where the same master key is used to generate multiple application keys. The main contribution of the paper is a modular and generic proof of security for the application keys established through the TLS protocol. We show that the transformation used by TLS to derive master keys essentially transforms an {\em arbitrary} secure pre-master key agreement protocol into a secure master-key agreement protocol. Similarly, the transformation used to derive application keys works when applied to an arbitrary secure master-key agreement protocol. These results are in the random oracle model. The security of the overall protocol then follows from proofs of security for the basic pre-master key generation protocols employed by TLS.

In this paper we consider commitment schemes that are secure against concurrent poly-time man-in-the-middle (cMiM) attacks. Under such attacks, two possible notions of security for commitment schemes have been proposed in the literature: concurrent non-malleability with respect to commitment and concurrent non-malleability with respect to decommitment (i.e., opening). After the original notion of non-malleability introduced by [Dolev, Dwork and Naor STOC 91] that is based on the independence of the committed and decommitted message, a new and stronger notion of non-malleability has been given in [Pass and Rosen STOC 05] by requiring that for any man-in-the-middle adversary there is a stand-alone adversary that succeeds with the same probability. Under this stronger security notion, a constant-round commitment scheme that is concurrent non-malleable only with respect to commitment has been given in [Pass and Rosen FOCS 05] for the plain model, thus leaving as an open problem the construction of a constant-round concurrent non-malleable commitments with respect to decommitment. In other words, in [Pass and Rosen FOCS 05] security against adversaries that mount concurrent man-in-the-middle attacks is guaranteed only during the commitment phase (under their stronger notion of non-malleability). The main result of this paper is a commitment scheme that is concurrent non-malleable with respect to both commitment and decommitment, under the stronger notion of [Pass and Rosen STOC 05]. This property protects against cMiM attacks mounted during both commitments and decommitments which is a crucial security requirement in several applications, as in some digital auctions, in which players have to perform both commitments and decommitments. Our scheme uses a constant number of rounds of interaction in the plain model and is the first scheme that enjoys all these properties under the definitions of [Pass and Rosen FOCS 05]. We stress that, exactly as in [Pass and Rosen FOCS 05], we assume that commitments and decommitments are performed in two distinct phases that do not overlap in time.

It is known that there exists a reduction from the CCA1-security of Damgård's Elgamal (DEG) cryptosystem to what we call the $\DDH^{\DSDH}$ assumption. We show that $\DDH^{\DSDH}$ is unnecessary for DEG-CCA1, while DDH is insufficient for DEG-CCA1. We also show that CCA1-security of the Elgamal cryptosystem is equivalent to another assumption $\DDH^{\CSDH}$, while we show that $\DDH^{\DSDH}$ is insufficient for Elgamal's CCA1-security. Finally, we prove a generic-group model lower bound $\Omega (\sqrt[3]{q})$ for the hardest considered assumption $\DDH^{\CSDH}$, where $q$ is the largest prime factor of the group order.

We study the simultaneous resettability problem, namely whether resettably-sound resettable ZK arguments for non-trivial languages exist (posed by Barak et al. [BGGL FOCS'01]), in both the plain model and the bare public-key (BPK for short) model. Under general hardness assumptions, we show: 1. in the BPK model, there exist constant-round (full-fledged) resettably-sound resettable ZK arguments for NP. This resolves a main problem in this model that remained open since the Micali and Reyzin's identification of notions of soundness [MR Crypto 2001] in the BPK model. 2.in the plain model, there exist constant-round (unbounded) resettably-sound class-bounded resettable ZK (as defined by Deng and Lin in [DL Eurocrypt 2007]) arguments for NP. This improves the previous result of Deng and Lin [Eurocrypt 2007] in that the DL construction for class-bounded resettable ZK argument achieves only a weak notion of resettable-soundness. The crux of these results is a construction of constant-round instance-dependent (full-fledged) resettably-sound resettable WI argument of knowledge (IDWIAOK for short) for any NP statement of the form x_0\in L_0 or x_1\in L_1, a notion also introduced by Deng and Lin [Eurocrypt 2007], whose construction, however, obtains only weak resettable-soundness when x_0\notin L_0. Our approach to the simultaneous resettability problem in the BPK model is to make a novel use of IDWIAOK, which gives rise to an elegant structure we call \Sigma-puzzles. Given the fact that all previously known resettable ZK arguments in the BPK model can be achieved in the plain model when ignoring round complexity, we believe this approach will shed light on the simultaneous resettability problem in the plain model.

In this paper, we study the issues related to the possibility, feasibility and optimality for perfectly secure message transmission (PSMT) in an undirected synchronous network, under the influence of a mixed adversary having unbounded computing power, who can corrupt some of the nodes in the network in Byzantine, fail-stop and passive fashion respectively. Specifically, we answer the following questions: (a) Possibility: Given a network and a mixed adversary, what are the necessary and sufficient conditions for the existence of any PSMT protocol over the network tolerating the adversary? (b) Feasibility: Once the existence of a protocol is ensured, then does there exist a polynomial time and efficient protocol on the given network? (c) Optimality: Given a message of specific length, what is the minimum communication complexity (lower bound) needed by any PSMT protocol to transmit the message and how to design a polynomial time protocol whose total communication complexity matches the lower bound on the communication complexity? We answer the above questions by considering two different types of mixed adversary, namely static mixed adversary and mobile mixed adversary. Intuitively, it is more difficult to tolerate a mobile mixed adversary (who can corrupt different set of nodes during different stages of the protocol) in comparison to its static counter part (who corrupts the same set of nodes throughout the protocol). However, surprisingly, we show that the connectivity requirement in the network and lower bound on communication complexity of PSMT protocols is same against both static and mobile mixed adversary. To design our protocols against static and mobile mixed adversary, we use several new techniques, which are of independent interest.

We present a very simple probabilistic, passive attack against the protocols HB and HB+. Our attack presents some interesting features: it requires less captured transcripts of protocol executions when com- pared to previous results; It makes possible to trade the amount of required transcripts for computational complexity; the value of noise used in the protocols HB and HB+ need not be known.

Since the first collision differential with its full differential path was presented for MD5 function by Wang et al. in 2004, renewed interests on collision attacks for the MD family of hash functions have surged over the world of cryptology. To date, however, no cryptanalyst can give a second computationally feasible collision differential for MD5 with its full differential path, even no improved differential paths based on Wangs MD5 collision differential have appeared in literature. Firstly in this paper, a new differential cryptanalysis called signed difference is defined, and some principles or recipes on finding collision differentials and designing differential paths are proposed, the signed difference generation or elimination rules which are implicit in the auxiliary functions, are derived. Then, based on these newly found properties and rules, this paper comes up with a new computationally feasible collision differential for MD5 with its full differential path, which is simpler thus more understandable than Wangs, and a set of sufficient conditions considering carries that guarantees a full collision is derived from the full differential path. Finally, a multi-message modification-based fast collision attack algorithm for searching collision messages is specialized for the full differential path, resulting in a computational complexity of 2 to the power of 36 and 2 to the power of 32 MD5 operations, respectively for the first and second blocks. As for examples, two collision message pairs with different first blocks are obtained.

At first glance, privacy and zero-knowledgeness seem to be similar properties. A scheme is private when no information is revealed on the prover and in a zero-knowledge scheme, communications should not leak provers' secrets. Until recently, privacy threats were only partially formalized and some zero-knowledge (ZK) schemes have been proposed so far to ensure privacy. We here explain why the intended goal is not reached. Following the privacy model proposed by Vaudenay at Asiacrypt 2007, we then reconsider the analysis of these schemes and thereafter introduce a general framework to modify identification schemes leading to different levels of privacy. Our new protocols can be useful, for instance, for identity documents, where privacy is a great issue. Furthermore, we propose efficient implementations of zero-knowledge and private identification schemes based on modifications of the GPS scheme. The security and the privacy are based on a new problem: the Short Exponent Strong Diffie-Hellman (SESDH) problem. The hardness of this problem is related to the hardness of the Strong Diffie-Hellman (SDH) problem and to the hardness of the Discrete Logarithm with Short Exponent (DLSE) problem. The security and privacy of these new schemes are proved in the random oracle paradigm.

In this paper we revisit Wiener's method (IEEE-IT 1990) of continued fraction (CF) to find new weaknesses in RSA. We consider RSA with $N = pq$, $q < p < 2q$, public encryption exponent $e$ and private decryption exponent $d$. Our motivation is to find out when RSA is insecure given $d$ is $O(N^\delta)$, where we are mostly interested in the range $0.3 \leq \delta \leq 0.5$. Given $\rho$ $(1 \leq \rho \leq 2)$ is known to the attacker, we show that the RSA keys are weak when $d = N^\delta$ and $\delta < \frac{1}{2} - \frac{\gamma}{2}$, where $|\rho q - p| \leq \frac{N^\gamma}{16}$. This presents additional results over the work of de Weger (AAECC 2002). We also discuss how the lattice based idea of Boneh-Durfee (IEEE-IT 2000) works better to find weak keys beyond the bound $\delta < \frac{1}{2} - \frac{\gamma}{2}$. Further we show that, the RSA keys are weak when $d < \frac{1}{2} N^\delta$ and $e$ is $O(N^{\frac{3}{2}-2\delta})$ for $\delta \leq \frac{1}{2}$. Using similar techniques we also present new results over the work of Blömer and May (PKC 2004).

This paper studies the security of ARIA against impossible differential cryptanalysis. Firstly an algorithm is given to find many new 4-round impossible differentials of ARIA. Followed by such impossible differentials, we improve the previous impossible differential attack on 5/6-round ARIA. We also point out that the existence of such impossible differentials are due to the bad properties of the binary matrix employed in the diffusion layer.

Many practical applications use hybrid encryption mechanism to deal with large plaintext messages or real-time communication since the performance of the public key encryption scheme is poor. The key encapsulation is a crucial part in hybrid encryption mechanism, which allows a sender to generate a random session key and distribute it to recipient. In this paper we present a proxy key re-encapsulation scheme for group communication. The proxy in our scheme is allowed to transform the encapsulated message corresponding to group A's public key into one that can be decapsulated by the member in group B. It can be used in cases when a group users need to perform sensitive operation without holding the necessary secret key.