A broadcast protocol allows a sender to distribute a message through a point-to-point network to a set of parties, such that (i) all parties receive the same message, even if the sender is corrupted, and (ii) this is the sender's message, if he is honest. Broadcast protocols satisfying these properties are known to exist if and only if $t<n/3$, where $n$ denotes the total number of parties, and $t$ denotes the maximal number of corruptions. When a setup allowing signatures is available to the parties, then such protocols exist even for $t<n$. Broadcast is the probably most fundamental primitive in distributed cryptography, and is used in almost any cryptographic (multi-party) protocol. However, a broadcast protocol ``only'' satisfying the above properties might be insecure when being used in the context of another protocol. In order to be safely usable within other protocols, a broadcast protocol must satisfy a simulation-based security notion, which is secure under composition. In this work, we show that most broadcast protocols in the literature do not satisfy a (natural) simulation-based security notion. We do not know of any broadcast protocol which could be securely invoked in a multi-party computation protocol in the secure-channels model. The problem is that existing protocols for broadcast do not preserve the secrecy of the message while being broadcasted, and in particular allow the adversary to corrupt the sender (and change the message), depending on the message being broadcasted. For example, when every party should broadcast a random bit, the adversary could corrupt those parties that want to broadcast 0, and make them broadcast 1. More concretely, we show that simulatable broadcast in a model with secure channels is possible if and only if $t<n/3$, respectively $t \le n/2$ when a signature setup is available. The positive results are proven by constructing secure broadcast protocols.

Hash functions are widely used in Cryptography, and hardware implementations of hash functions are of interest in a variety of contexts such as speeding up the computations of a network server or providing authentication in small electronic devices such as RFID tags. Provably secure hash functions, the security of which relies on the hardness of a mathematical problem, are particularly appealing for security, but they used to be too inefficient in practice. In this paper, we study the efficiency in hardware of ZT', a provably secure hash function based on the Zémor-Tillich hash function. We consider three kinds of implementations targeting a high throughput and a low area in different ways. We first present a high-speed implementation of ZT' on FPGA that is nearly half as efficient as state-of-the-art SHA implementations in terms of throughput per area. We then focus on area reduction and present an ASIC implementation of ZT' with much smaller area costs than SHA-1 and even than SQUASH, which was specially designed for low-cost RFID tags. Between these two extreme implementations, we show that the throughput and area can be traded with a lot of flexibility. Finally, we show that the inherent parallelism of ZT' makes it particularly suitable for applications requiring high speed hashing of very long messages. Our work, together with existing reasonably efficient software implementations, shows that this variant of the Zémor-Tillich hash function is in fact very practical for a wide range of applications, while having a security related to the hardness of a mathematical problem and significant additional advantages such as scalability and parallelism.

Security devices are vulnerable to side-channel attacks that perform statistical analysis on data leaked from cryptographic computations. Higher-order (HO) attacks are a powerful approach to break protected implementations. They inherently demand multivariate statistics because multiple aspects of signals have to be analyzed jointly. However, all published works on HO attacks follow the approach to first apply a pre-processing function to map the multivariate problem to a univariate problem and then to apply established $1^{st}$ order techniques. We propose a novel and different approach to HO attacks, Multivariate Mutual Information Analysis (MMIA), that allows to directly evaluate joint statistics without pre-processing. While this approach can benefit from a good power model, it also works without an assumption. A thorough empirical evaluation of MMIA and established HO attacks confirms the overwhelming advantage of the new approach: MMIA is more efficient and less affected by noise. Most important and opposed to all published approaches, MMIA's measurement cost grows sub-exponentially with the attack order. As a consequence, the security provided by the masking countermeasure needs to be reconsidered as $3^{rd}$ and higher order attacks become very practical.

We analyze the relation between induction, co-induction and the presence of encryption cycles in the context of computationally sound symbolic equivalence of cryptographic expressions. Our main finding is that the use of co-induction in the symbolic definition of the adversarial knowledge allows to prove unconditional soundness results that do not require syntactic restrictions, like the absence of encryption cycles. Encryption cycles are relevant only to the extent that the key recovery function associated to acyclic expressions can be shown to have a unique fix-point. So, when a cryptographic expression has no encryption cycles, the inductive (least fix-point) and co-inductive (greatest fix-point) security definitions produce the same results, and the computational soundness of the inductive definitions for acyclic expressions follows as a special case of the soundness of the co-inductive definition.

We describe a new explicit function that given an elliptic curve $E$ defined over $\FF_{p^n}$, maps elements of $\FF_{p^n}$ into $E$ in \emph{deterministic} polynomial time and in a constant number of operations over $\FF_{p^n}$. The function requires to compute a cube root. As an application we show how to hash \emph{deterministically} into an elliptic curve.

In this paper, we give a security proof for Abreast-DM in terms of collision resistance and preimage resistance. As old as Tandem-DM, the compression function Abreast-DM is one of the most well-known constructions for double block length compression functions. The bounds on the number of queries for collision resistance and preimage resistance are given by O(2^n). Based on a novel technique using query-response cycles, our security proof is simpler than those for MDC-2 and Tandem-DM. We also present a wide class of Abreast-DM variants that enjoy a birthday-type security guarantee with a simple proof.

In this paper, we present the pseudo-collision, pseudo-second-preimage and pseudo-preimage attacks on the SHA-3 candidate algorithm Luffa. The pseudo-collisions and pseudo-second-preimages can be found easily by computing the inverse of the message injection function at the beginning of Luffa. We explain in details the pseudo-preimage attacks. For Luffa-224/256, given the hash value, only 2 iteration computations are needed to get a pseudo-preimage. For Luffa-384, finding a pseudo-preimage needs about $2^{64}$ iteration computations with $2^{67}$ bytes memory by the extended generalized birthday attack. For Luffa-512, the complexity is $2^{128}$ iteration computations with $2^{132}$ bytes memory. It is noted that, we can find the pseudo-collision pairs and the pseudo-second images only changing a few different bits of initial values. That is directly converted to the forgery attack on NMAC in related key cases.

Since the first feasible collision differential was given for MD5 in 2004 by Wang et al, a lot of work has been concentrated on how to improve it, but the researches on how to select weak input differences for MD5 collision attack are only sporadically scattered in literature. This paper focuses on a reasonable selection of weak input differences for MD5 collision attack, tries to answer some questions such as, what techniques can be applied satisfying bit conditions? which step in the second round can be the latest to apply a search on free bits without violating previously satisfied conditions? what is the optimal characterization of feasible collision differential propagation for MD5, by which we can find more weak input differences? is there any collision differentials that exceed Wang et al's by some practical criteria? In this paper, a divide-and-conquer strategy is introduced with an optimal scheme of grouping the 64 steps of operation into five stages of independent condition fulfillment, and a feasible collision differential propagation is optimally characterized as a guide to select those 1~3-bit weak input differences, with their computational costs estimated. As a result, hundreds of thousands of weak input differences have been found, quite a number of which are superior to Wang et al's, for example, a 2-bit collision differential is able to find a collision within 2^10 MD5 compressions, a 1-MSB differential collision attack on MD5 is developed with a time complexity of 2^20.96 MD5 compressions, and a practical 1-block collision attack on MD5 is found to be possible. This paper also provides a rich resource of colliding messages with different weak input differences, therefore much greatly increase the probability of finding a second MD5 pre-image for an arbitrarily given message.

In [Solving Multiple Right Hand Sides linear equations. Designs, Codes and Cryptography, 49:147–160, 2008] Raddum and Semaev propose a technique to solve systems of polynomial equations over GF(2) as occurring in algebraic attacks on block ciphers. This approach is known as MRHS, and we present a special purpose architecture to implement MRHS in a dedicated hardware device. Our preliminary performance analysis of this Parallel Elimination Technique Supporting Nice Algebraic Key Elimination shows that the use of ASICs seems to enable significant performance gains over a software implementation of MRHS. The main parts of the proposed architecture are scalable, the limiting factor being mainly the available bandwidth for interchip communication. Our focus is on a design choice that can be implemented within the limits of available fab technology. The proposed design can be expected to offer a running time improvement in the order of several magnitudes over a software implementation. We do not make any claims about the practical feasibility of an attack against AES-128 with our design, as we do not see the necessary theoretical tools to be available: deriving reliable running time estimates for an algebraic attack with MRHS when being applied to a full-round version of AES-128 is still an open problem.

The Boneh-Boyen signature scheme is a pairing based short signature scheme which is provably secure in the standard model under the $q$-Strong Diffie-Hellman assumption. In this paper, we prove the converse of this statement, and show that forging Boneh-Boyen signatures is actually equivalent to solving the $q$-Strong Diffie-Hellman problem. Using this equivalence, we exhibit an algorithm which, on the vast majority of pairing-friendly curves, recovers Boneh-Boyen private keys in $O(p^{\frac{2}{5}+\varepsilon})$ time, using $O(p^{\frac{1}{5}+\varepsilon})$ signature queries. We present implementation results comparing the performance of our algorithm and traditional discrete logarithm algorithms such as Pollard's lambda algorithm and Pollard's rho algorithm. We also discuss some possible countermeasures and strategies for mitigating the impact of these findings.

A leakage-resilient cryptosystem remains secure even if arbitrary, but bounded, information about the secret key (or possibly other internal state information) is leaked to an adversary. Denote the length of the secret key by $n$. We show a signature scheme tolerating (optimal) leakage of up to $n-n^\epsilon$ bits of information about the secret key, and a more efficient one-time signature scheme that tolerates leakage of $(\frac{1}{4}-\epsilon) \cdot n$ bits of information about the signer's entire state. The latter construction extends to give a leakage-resilient $t$-time signature scheme. All these constructions are in the standard model under general assumptions.

We introduce a formal model for certificateless authenticated key exchange (CL-AKE) protocols. Contrary to what might be expected, we show that the natural combination of an ID-based AKE protocol with a public key based AKE protocol cannot provide strong security. We provide the first one-round CL-AKE scheme proven secure in the random oracle model. We introduce two variants of the Diffie-Hellman trapdoor introduced by \cite{DBLP:conf/eurocrypt/CashKS08}. The proposed key agreement scheme is secure as long as each party has at least one uncompromised secret. Thus, our scheme is secure even if the key generation centre learns the ephemeral secrets of both parties.

Cube testers are a generic class of methods for building disstinguishers, based on cube attacks and on algebraic property-testers. In this paper, we report on an efficient FPGA implementation of cube testers on the stream cipher Grain-128. Our best result (a distinguisher on Grain-128 reduced to 237 rounds, out of 256) was achieved after a computation involving 2^54 clockings of Grain-128, with a 256×32 parallelization. An extrapolation of our results with standard methods suggests the possibility of a distinguishing attack on the full Grain-128 in time 2^83, which is well below the 2^128 complexity of exhaustive search. We also describe the method used for finding good cubes (a simple evolutionary algorithm), and report preliminary results on Grain-v1 obtained with a bitsliced C implementation.

This paper considers the construction and analysis of pseudo-random functions (PRFs) with specific reference to modes of operations of a block cipher. In the context of message authentication codes (MACs), earlier independent work by Bernstein and Vaudenay show how to reduce the analysis of relevant PRFs to some probability calculations. In the first part of the paper, we revisit this result and use it to prove a general result on constructions which use a PRF with a ``small'' domain to build a PRF with a ``large'' domain. This result is used to analyse two new parallelizable PRFs which are suitable for use as MAC schemes. The first scheme, called {\iPMAC}, is based on a block cipher and improves upon the well-known PMAC algorithm. The improvements consist in faster masking operations and the removal of a design stage discrete logarithm computation. The second scheme, called {\VPMAC}, uses a keyed compression function rather than a block cipher. The only previously known compression function based parallelizable PRF is called the protected counter sum (PCS) and is due to Bernstein. {\VPMAC} improves upon PCS by requiring lesser number of calls to the compression function. The second part of the paper takes a new look at the construction and analysis of modes of operations for authenticated encryption (AE) and for authenticated encryption with associated data (AEAD). Usually, the most complicated part in the security analysis of such modes is the analysis of authentication security. Previous work by Liskov, Rivest and Wagner and later Rogaway had suggested that this analysis is simplified by using a primitive called a tweakable block cipher (TBC). In contrast, we take a direct approach. We prove a general result which shows that the authentication security of an AE scheme can be proved from the privacy of the scheme and by showing a certain associated function to be a PRF. Two new AE schemes \sym{PAE} and \sym{PAE}-1 are described and analysed using this approach. In particular, it is shown that the authentication security of \sym{PAE} follows easily from the security of {\iPMAC}. As a result, no separate extensive analysis of the authentication security of \sym{PAE} is required. An AEAD scheme can be obtained by combining an AE scheme and an authentication scheme and it has been suggested earlier that a TBC based approach simplifies the analysis. Again, in contrast to the TBC based approach, we take a direct approach based on a simple masking strategy. Our idea uses double encryption of a fixed string and achieves the same effect of mask separation as in the TBC based approach. Using this idea, two new AEAD schemes \sym{PAEAD} and \sym{PAEAD}-1 are described. An important application of AEAD schemes is in the encryption of IP packets. The new schemes offer certain advantages over previously well known schemes such as the offset codebook (OCB) mode. These improvements include providing a wider variety of easily reconfigurable family of schemes, a small speed-up, a smaller size decryption algorithm for hardware implementation and uniform processing of only full-block messages.

A new construction of block cipher based tweakable enciphering schemes (TES) is described. The major improvement over existing TES is that the construction uses only the encryption function of the underlying block cipher. Consequently, this leads to substantial savings in the size of hardware implementation of TES applications such as disk encryption. This improvement is achieved without loss in efficiency of encryption and decryption compared to the best previously known schemes.

We revisit the problem of constructing a protocol for performing authenticated encryption with associated data (AEAD). A technique is described which combines a collision resistant hash function with a protocol for authenticated encryption (AE). The technique is both simple and generic and does not require any additional key material beyond that of the AE protocol. Concrete instantiations are shown where a 256-bit hash function is combined with some known single-pass AE protocols employing either 128-bit or 256-bit block ciphers. This results in possible efficiency improvement in the processing of the header.

We address one of the foundational problems in cryptography: the bias of coin-flipping protocols. Coin-flipping protocols allow mutually distrustful parties to generate a common unbiased random bit, guaranteeing that even if one of the parties is malicious, it cannot significantly bias the output of the honest party. A classical result by Cleve [STOC '86] showed that for any two-party $r$-round coin-flipping protocol there exists an efficient adversary that can bias the output of the honest party by $\Omega(1/r)$. However, the best previously known protocol only guarantees $O(1/\sqrt{r})$ bias, and the question of whether Cleve's bound is tight has remained open for more than twenty years. In this paper we establish the optimal trade-off between the round complexity and the bias of two-party coin-flipping protocols. Under standard assumptions (the existence of oblivious transfer), we show that Cleve's lower bound is tight: we construct an $r$-round protocol with bias $O(1/r)$.

In this note we first characterize the class of Montgomery curves with B=1 by the simplicity of their transformation into short Weierstrass form and explicitly determine their torsion points of order 2 and 4. We then consider two ``verifiably random'' elliptic curves in the SECG standards and show that they are B=1 Montgomery curves that can also be simply transformed into Edwards form over their ground fields.

We propose a lightweight RFID authentication protocol that supports forward and backward security. The only cryptographic mechanism that this protocol uses is a pseudo-random number generator (PRNG) that is shared with the backend Server. Authentication is achieved by exchanging a few numbers (3 or 5) drawn from the PRNG. The protocol is optimistic with constant lookup time, and can be easily adapted to prevent online man-in-the-middle relay attacks. Security is proven in the UC security framework.

Efficient zero-knowledge proofs of knowledge (ZK-PoK) are basic building blocks of many practical cryptographic applications such as identification schemes, group signatures, and secure multiparty computation. Currently, first applications that critically rely on ZK-PoKs are being deployed in the real world. The most prominent example is Direct Anonymous Attestation (DAA), which was adopted by the Trusted Computing Group (TCG) and implemented as one of the functionalities of the cryptographic Trusted Platform Module (TPM) chip. Implementing systems using ZK-PoK turns out to be challenging, since ZK-PoK are, loosely speaking, significantly more complex than standard crypto primitives, such as encryption and signature schemes. As a result, implementation cycles of ZK-PoK are time-consuming and error-prone, in particular for developers with minor or no cryptographic skills. In this paper we report on our ongoing and future research vision with the goal to bring ZK-PoK to practice by making them accessible to crypto and security engineers. To this end we are developing compilers and related tools that support and partially automate the design, implementation, verification and secure implementation of ZK-PoK protocols.

Hash functions are usually composed of a mode of operation on top of a concrete primitive with fixed input-length and fixed output-length, such as a block cipher or a permutation. In practice, the mode is often sequential, although parallel (or tree) hashing modes are also possible. The former requires less memory, while the latter has several advantages such as its inherent parallelism and a lower cost of hash value re-computation when only a small part of the input changes. In this paper, we consider the general case of (tree or sequential) hashing modes that make use of an underlying hash function, which may in turn be sequential. We formulate a set of three simple conditions for such a (tree or sequential) hashing mode to be sound. By sound, we mean that the advantage in differentiating a hash function obtained by applying a tree hashing mode to an ideal underlying hash function from an ideal monolithic hash function is upper bounded by $q^2/2^{n+1}$ with $q$ the number of queries to the underlying hash function and $n$ the length of the chaining values. We provide a proof of soundness in the indifferentiability framework. The conditions we formulate are easy to implement and to verify, and can be used by the practitioner to build a tree hashing mode on top of an existing hash function. We show how to apply tree hashing modes to sequential hash functions in an optimal way, demonstrate the applicability of our conditions with two efficient and simple tree hashing modes and provide a simple method to take the union of tree hashing modes that preserves soundness. It turns out that sequential hashing modes using a compression function (i.e., a hash function with fixed input-length) can be considered as particular cases and, as a by-product, our results also apply to them. We discuss the different techniques for satisfying the three conditions, thereby shedding a new light on several published modes.

In early 2000's, Rivest~\cite{CambridgeTalk-Rivest,TSS-Micali} and Micali~\cite{TSS-Micali} introduced the notion of \emph{transitive signature}, which allows a third party to generate a valid signature for a composed edge $(v_i, v_k)$, from the signatures for two edges $(v_i, v_j)$ and $(v_j, v_k)$, and using the public key only. Since then, a number of works, including \cite{TSS-Micali,transig-fac-rsa-Bellare,hohenberger-masters,TSS-BilinearGroup-Shahandashti,transig-Bellare}, have been devoted on transitive signatures. Most of them address the undirected transitive signature problem, and the directed transitive signature is still an open problem. S.~Hohenberger~\cite{hohenberger-masters} even showed that a directed transitive signature implies a complex mathmatical group, whose existence is still unkown. Recently, a few directed transitive signature schemes~\cite{DirectedTSS-Yi,dtts-Neven} on directed trees are proposed. The drawbacks of these schemes include: the size of composed signature increases linearly with the number of recursive applications of composition and the creating history of composed edge is not hidden properly. This paper presents {\DTTS}---a \emph{Directed}-Tree-Transitive Signature scheme, to address these issues. Like previous works~\cite{DirectedTSS-Yi,dtts-Neven}, {\DTTS} is designed only for directed trees, however, it features with constant (composed) signature size and privacy preserving property. %oblivious composition history G.~Neven~\cite{dtts-Neven} pointed out constant signature size is an essential requirement of the original directed transitive signature problem raised by Rivest and Micali. In this sense, our scheme {\DTTS} is the \emph{first} transitive signature scheme on a directed tree. We also prove that {\DTTS} is transitively unforgeable under adaptive chosen message attack in the standard model.

In this paper we propose an efficient multivariate public key cryptosystem based on permutation p-polynomials over finite fields. We first characterize a class of permutation p-polynomials over finite fields $F_{q^{m}}$ and then construct a trapdoor function using this class of permutation p-polynomials. The complexity of encryption in our public key cryptosystem is $O(m^{3})$ multiplication which is equivalent to other multivariate public key cryptosystems. However the decryption is much faster than other multivariate public key cryptosystems. In decryption we need $O(m^{2})$ left cyclic shifts and $O(m^{2})$ xor operations.

We introduce the notion of a Social Secret Sharing Scheme, in which shares are allocated based on a player's reliability and the way he interacts with other participants. During the share refresh phase, weights of participants are adjusted in a way that participants who cooperate will end up with more shares than those who defect. On the other hand, corrupted players will be disenrolled immediately for the computation safety. Our motivation is that, in real world applications, components of a secure multiparty computation framework may have different levels of importance as well as credibility. Therefore, a robust construction should balance these two factors respectively, that is adjusting the responsibility based on the reliability. The proposed construction has a variety of desirable properties. It is an unconditionally verifiable scheme in the sense that it can detect malicious participants without relying on any computational assumptions. The scheme proactively renews shares at each cycle without changing the secret, and allows trusted participants to gain more authority in the scheme, i.e., a dynamic access structure. The other prominent property of the scheme is that, it gradually reduces the influence of irresponsible players due to the self-reinforcement property of social interactions among players.

The National Institute of Standards and Technology (NIST) has started a competition for a new secure hash standard. In this context third party implementations of all proposed hash functions are regarded as an important part of the competition. We chose to implement the Groestl hash function for FPGAs, for its resemblance to AES. More precisely we developed two optimized versions, one optimized for throughput, the other one for area. Both implementations improve the results and estimates presented in the original submission to the competition. The performance of both implementations may be improved further, thus Groestl seems to be a good candidate for implementations on medium sized FPGAs. Besides that, it is shown that Groestl needs a significant amount of resources, which will hinder its use for automotive applications.

Consider a scenario in which an adversary, attacking a certain public key encryption scheme, gains knowledge of several ciphertexts which underlying plaintext are meaningfully related with a given target ciphertext. This kind of related message attack has been proved successful against several public key encryption schemes; widely known is the Franklin-Reiter attack to RSA with low exponent and its subsequent improvement by Coppersmith. However, to the best of our knowledge no formal treatment of these type of attacks has to date been done, and as a result, it has not been rigorously studied which of the ``standard'' security notions imply resilience to them. We give formal definitions of several security notions capturing the resistance to this kind of attacks. For passive adversaries we prove that, for the case of indistinguishability, security against related message attacks is equivalent to standard CPA security. On the other hand, one-wayness robust schemes in this sense can be seen as strictly between OW-CPA and IND-CPA secure schemes. Furthermore, we prove that the same holds for active (CCA) adversaries.

Secure Join-operator computation in distributed relational databases is one of important problems in the field of secure multiparty computation with valuable applications. We propose a gerneral construction for 2-party Join computation based-on anonymous IBE scheme and its user private-keys blind generation techniques. The construction is GUC(Generalized Universally Composable) secure in standard model. For this goal a new notion of non-malleable zero-knowledge proofs of knowledge and its efficient general construction is also presented.

In 1999, Coron, Naccache and Stern discovered an existential signature forgery for two popular RSA signature standards, ISO/IEC 9796-1 and 2. Following this attack ISO/IEC 9796-1 was withdrawn. ISO/IEC 9796-2 was amended by increasing the message digest to at least 160 bits. Attacking this amended version required at least 2^61 operations. In this paper, we exhibit algorithmic refinements allowing to attack the amended (currently valid) version of ISO/IEC 9796-2 for all modulus sizes. A practical forgery was computed in only two days using 19 servers on the Amazon EC2 grid for a total cost of roughly $800. The forgery was implemented for e=2 but attacking odd exponents will not take longer. The forgery was computed for the RSA-2048 challenge modulus, whose factorization is still unknown. The new attack blends several theoretical tools. These do not change the asymptotic complexity of Coron et al. technique but significantly accelerate it for parameter values previously considered beyond reach. While less efficient ($45,000), the acceleration also extends to EMV signatures. EMV is an ISO/IEC 9796-2-compliant format with extra redundancy. Luckily, this attack does not threaten any of the 730 million EMV payment cards in circulation for operational reasons. Costs are per modulus: after a first forgery for a given modulus, obtaining more forgeries is virtually immediate.

Crisp Commitment schemes are very useful building blocks in the design of high-level cryptographic protocols. They are used as a mean of flipping fair coins between two players and others. In this paper an attempt has been made to give a generalized framework for Crisp Commitment schemes is called an Ordinary Crisp Commitment Scheme (OCCS). The Hiding and Binding properties of OCCS are well defined. We also review some the existing of different Crisp Commitment schemes and we show how it is follow our presenting framework.

In this paper, we present an enhanced cryptanalysis of the Substitution Cipher Chaining mode (SCC)~\cite{scc}. In~\cite{scc_attack}, SCC-128 (SCC which uses AES with 128-bit key) was broken using 5 attacks, where the authors used an active attack model (where the attacker can force the disk encryption application to re-encrypt a sector for her), the complexity of these attacks are at most 2$^{40}$ cipher executions. In this paper, we enhance the main attack on SCC-128, this enhancement decrease the complexity of SCC-128 attacks to be at most 2$^{14}$ cipher executions. We also cryptanalze SCC-128 in a less restrictive attack model, our attacks are upper bounded with 2$^{40}$ cipher executions.

ePassports are biometric identification documents that contain RFID Tags and are primarily used for border security. The embedded RFID Tags are capable of storing data, performing low cost computations and cryptography, and communicating wirelessly. Since 2004, we have witnessed the development and widespread deployment of three generations of electronic passports - The ICAO First Generation ePassport (2004), Extended Access Control (EAC v1.0) ePassports (2006), and Extended Access Control with Password Authentication and Connection Establishment (EAC v2.1) ePassports (2008). Currently, over thirty million ePassports have been issued around the world. In this paper, we provide an introductory study of the technologies implemented in ePassports - Biometrics, RFID, and Public Key Infrastructures; and then go on to analyze the protocols implemented in each of the three generations of ePassports, finally we point out their shortcomings and scope for future related research.

Shabal is based on a new provably secure mode of operation. Some related-key distinguishers for the underlying keyed permutation have been exhibited recently by Aumasson et al. and Knudsen et al., but with no visible impact on the security of Shabal. This paper then aims at extensively studying such distinguishers for the keyed permutation used in Shabal, and at clarifying the impact that they exert on the security of the full hash function. Most interestingly, a new security proof for Shabal's mode of operation is provided where the keyed permutation is not assumed to be an ideal cipher anymore, but observes a distinguishing property i.e., an explicit relation verified by all its inputs and outputs. As a consequence of this extended proof, all known distinguishers for the keyed permutation are proven not to weaken the security of Shabal. In our study, we provide the foundation of a generalization of the indifferentiability framework to biased random primitives, this part being of independent interest

Previously we presented a pairing based DAA protocol in the asymmetric setting, along with a ``security proof''. Jiangtao Li has pointed out to us an attack against this published protocol, thus our prior work should not be considered sound. In this paper we give a repaired version, along with a highly detailed security proof. A full paper will be made available shortly. However in the meantime we present this paper for the community to check and comment on.

In this paper we analyse the security of the SHA-3 candidate ARIRANG. We show that bitwise complementation of whole registers turns out to be very useful for constructing high-probability differential characteristics in the function. We use this approach to find near-collisions with Hamming weight 32 for the full compression function as well as collisions for the compression function of ARIRANG reduced to 26 rounds, both with complexity close to $2^0$ and memory requirements of only a few words. We use near collisions for the compression function to construct pseudo-collisions for the complete hash functions ARIRANG-224 and ARIRANG-384 with complexity $2^{23}$ and close to $2^0$, respectively. We implemented the attacks and provide examples of appropriate pairs of $H,M$ values. We also provide possible configurations which may give collisions for step-reduced and full ARIRANG.

A. Kent proposed a quantum bit string commitment protocol in 2003. Not using the standard two conjugate states $|0\rangle$, $|1\rangle $, $|+\rangle $ and $|-\rangle $, the protocol uses $\psi_0=|0\rangle$ and $\psi_1=\sin \theta|0\rangle+\cos \theta |1\rangle $, where $\theta\neq 0$. In this paper, we show that the protocol can not guarantee security to the receiver. $(1-\frac{\sin^2 \theta}{2})n $ bits are definitely exposed to the receiver, where $n$ is the length of the committed string.

Diagnostic and classification algorithms play an important role in data analysis, with applications in areas such as health care, fault diagnostics, or benchmarking. Branching programs (BP) is a popular representation model for describing the underlying classification/diagnostics algorithms. Typical application scenarios involve a client who provides data and a service provider (server) whose diagnostic program is run on client's data. Both parties need to keep their inputs private. We present new, more efficient privacy-protecting protocols for remote evaluation of such classification/diagnostic programs. In addition to efficiency improvements, we generalize previous solutions -- we securely evaluate private linear branching programs (LBP), a useful generalization of BP that we introduce. We show practicality of our solutions: we apply our protocols to the privacy-preserving classification of medical ElectroCardioGram (ECG) signals and present implementation results. Finally, we discover and fix a subtle security weakness of the most recent remote diagnostic proposal, which allowed malicious clients to learn partial information about the program.

Ring signcryption, a cryptographic primitive to protect security and privacy, is an encryption and authentication scheme in a single logical step which allows a user to anonymously signcrypt a plaintext on behalf of a group of users that decrypter cannot know who is the actual signcrypter. In 2009, Zhang, Gao, Chen and Geng proposed a novel anonymous signcryption scheme(denoted as the ZGCG scheme) which is more efficient in computational cost and ciphertext length than the related schemes. In this paper, however, we show that the ZGCG scheme has not anonymity secure for the receiver, and then we propose an improved anonymous signcryption scheme that remedies the weakness of the ZGCG scheme. Our proposed scheme satisfies the semantic security, unforgeability, signcrypter identity's ambiguity, and public authenticity. We also give the formal security proof in the random oracle model.

This paper presents an efficient and provable secure identity based generalized signcryption scheme based on [1] which can work as signcryption scheme, encryption scheme and signature scheme as per need. Its security is proved under the difficulty of q-BDHIP. A generalized signcryption scheme in multiple PKGs environment is also proposed.

Blindness and unforgeability are two essential security requirements of a secure blind signature scheme. Blindness means that after interacting with various users, the signer can never be able to link a valid message pair. Blindness is meaningless if after interacting with various users, the signer is able to link a valid message signature pair. This security vulnerability is known as linkability attack. Recently, Verma proposed two blind signature schemes over braid groups. Verma claimed that the proposed schemes are secure against all possible security vulnerabilities and also satisfy all essential securities properties.This paper reviews Verma’s proposed blind signature schemes and found that these scheme do not withstand against the linkability vulnerability.

A new technique for combinational circuit optimization is described in the context of S-boxes. The technique is a two-step process. In the first step, the non-linearity of the circuit -- as measured by the number of non-linear gates it contains -- is reduced. The second step reduces the number of gates in the linear components of the already reduced circuit. The technique can be applied to arbitrary circuits, and seems to yield improvements even on circuits that have already been optimized by standard methods. We apply our technique to the S-box of the Advanced Encryption Standard (AES). The result is, as far as we know, the smallest circuit yet constructed for this function.

The discrete logarithm problem is one of the backbones in public key cryptography. In this paper we study the discrete logarithm problem in the group of circulant matrices over a finite field. This gives rise to secure and fast public key cryptosystems.

Proxy re-encryption (PRE) allows a semi-trusted proxy to convert a ciphertext originally intended for Alice into one encrypting the same plaintext for Bob. The proxy only needs a re-encryption key given by Alice, and cannot learn anything about the plaintext encrypted. This adds flexibility in various applications, such as confidential email, digital right management and distributed storage. In this paper, we study unidirectional PRE, which the re-encryption key only enables delegation in one direction but not the opposite. In PKC 2009, Shao and Cao proposed a unidirectional PRE assuming the random oracle. However, we show that it is vulnerable to chosen-ciphertext attack (CCA). We then propose an efficient unidirectional PRE scheme (without resorting to pairings). We gain high efficiency and CCA-security using the ``token-controlled encryption'' technique, under the computational Diffie-Hellman assumption, in the random oracle model and a relaxed but reasonable definition.

Group Inside Signature (GIS) is a signature scheme that allows the signer to designate his signature to be verified by a group of people, so that members other than the designated group cannot verify the signature generated by him. In Broadcast Group Oriented Signature (BGOS), an user from one group can designate his signature to be verified by members of other group. The GIS and BGOS schemes \cite{MaAoHe05}, \cite{CJ09} and \cite{MaHeAo05} which we consider are certificateless schemes. An Adaptable Designated Group Signature (ADGS), is one in which an user can designate his signature to be verified by a selected set of members who are from different groups. The ADGS scheme \cite{MaL06} which we consider here is an identity based scheme. In this paper, we present the cryptanalysis of four schemes that appeared in \cite{MaAoHe05}, \cite{CJ09}, \cite{MaHeAo05} and \cite{MaL06}. We show that, both GIS schemes \cite{MaAoHe05}, \cite{CJ09} and BGOS scheme \cite{MaHeAo05} suffers from Type-I and Type-II vulnerabilities and ADGS \cite{MaL06} is universally forgeable. We also present a new scheme for ADGS (N-ADGS) and proved its security in the random oracle model. The existing model for ADGS did not consider unlinkability which is one of the key properties required for ADGS. We provide security model for unlinkability and also prove our scheme is unlinkable.

The classical McEliece cryptosystem is built upon the class of Goppa codes, which remains secure to this date in contrast to many other families of codes but leads to very large public keys. Previous proposals to obtain short McEliece keys have primarily centered around replacing that class by other families of codes, most of which were shown to contain weaknesses, and at the cost of reducing in half the capability of error correction. In this paper we describe a simple way to reduce significantly the key size in McEliece and related cryptosystems using a subclass of Goppa codes, while also improving the efficiency of cryptographic operations to $\tilde{O}(n)$ time, and keeping the capability of correcting the full designed number of errors in the binary case.

A block cipher is intended to be computationally indistinguishable from a random permutation of appropriate domain and range. But what are the properties of a random permutation? By the aid of exponential and ordinary generating functions, we derive a series of collolaries of interest to the cryptographic community. These follow from the Strong Cycle Structure Theorem of permutations, and are useful in rendering rigorous two attacks on Keeloq, a block cipher in wide-spread use. These attacks formerly had heuristic approximations of their probability of success. Moreover, we delineate an attack against the (roughly) millionth-fold iteration of a random permutation. In particular, we create a distinguishing attack, whereby the iteration of a cipher a number of times equal to a particularly chosen highly-composite number is breakable, but merely one fewer round is considerably more secure. We then extend this to a key-recovery attack in a “Triple-DES” style construction, but using AES-256 and iterating the middle cipher (roughly) a million-fold. This attack is $2^{119.237}$ times faster than brute-force search. It is hoped that these results will showcase the utility of exponential and ordinary generating functions and will encourage their use in cryptanalytic research.

All-or-Nothing Encryption was introduced by Rivest as a countermeasure to brute force key search attacks. This work identifies a new application for All-or-Nothing Transforms, as a protocol-level countermeasure to Differential Side-Channel Analysis (DSCA). We describe an extension to the All-or-Nothing protocol, that strengthens the DCSA resistance of the cryptosystem. The resultant scheme is a practical alternative to Boolean and arithmetic masking, used to protect implementations of encryption and decryption operations on electronic devices.

In this paper, we analyze the hash functions Dynamic SHA and Dynamic SHA2, which have been selected as &#64257;rst round candidates in the NIST hash function competition. These hash functions rely heavily on data-dependent rotations, similar to certain block ciphers, e.g., RC5. Our analysis suggests that in the case of hash functions, where the attacker has more control over the rotations, this approach is less favorable than in block ciphers. We present practical, or close to practical, collision attacks on both Dynamic SHA and Dynamic SHA2. Moreover, we present a preimage attack on Dynamic SHA that is faster than exhaustive search.

In~\cite{DT07} Damgard and Thorbek proposed the linear integer secret sharing (LISS) scheme. In this note we show that the LISS scheme can be made proactive.

In this paper, we present a new tweakable narrow-block mode of operation, the Extended Substitution Cipher Chaining mode (ESCC), that can be efficiently deployed in disk encryption applications. ESCC is an extention of Substitution Cipher Chaining mode (SCC)~\cite{scc}. Unlike SCC, ESCC is resistant to the attacks in~\cite{scc_attack,scc_attack2}.

RFID can be used for a variety of applications, e.g., to conveniently pay for public transportation. However, achieving security and privacy of payment is challenging due to the extreme resource restrictions of RFID tags. In this paper, we propose PSP -- a secure, RFID-based protocol for privacy-preserving payment. Similar to traditional electronic cash, the user of a tag can pay access to a metro using his tag and so called {coins} of a virtual currency. With PSP, tags do not need to store valid coins, but generate them on the fly. Using Bloom filters, readers can verify the validity of generated coins offline. PSP guarantees privacy such that neither the metro nor an adversary can reveal the identity of a user or link subsequent payments. PSP is secure against {invention} and {overspending} of coins, and can reveal the identity of users trying to {doublespend} coins. Still, PSP is lightweight: it requires only a hash-function and few bytes of non-volatile memory on the tag.

Combining and analyzing data collected at multiple locations is critical for a wide variety of applications, such as detecting and diagnosing malicious attacks or computing an accurate estimate of the popularity of Web sites. However, legitimate concerns about privacy often inhibit participation in collaborative data-analysis systems. In this paper, we design, implement, and evaluate a practical solution for privacy-preserving collaboration among a large number of participants. Scalability is achieved through a ``semi-centralized'' architecture that divides responsibility between a proxy that obliviously blinds the client inputs and a database that identifies the (blinded) keywords that have values satisfying some evaluation function. Our solution leverages a novel cryptographic protocol that provably protects the privacy of both the participants and the keywords. For example, if web servers collaborate to detect source IP addresses responsible for denial-of-service attacks, our protocol would not reveal the traffic mix of the Web servers or the identity of the ``good'' IP addresses. We implemented a prototype of our design, including an amortized oblivious transfer protocol that substantially improves the efficiency of client-proxy interactions. Our experiments show that the performance of our system scales linearly with computing resources, making it easy to improve performance by adding more cores or machines. For collaborative diagnosis of denial-of-service attacks, our system can handle millions of suspect IP addresses per hour when the proxy and the database each run on two quad-core machines.

In this paper, we present a near-collision attack on the compression functions of Dynamic SHA2 for all the output sizes. For the Dynamic SHA2-224/256, the complexity is about $2^{45}$ operations and for the Dynamic SHA2-384/512, the complexity is about $2^{75}$.

In this paper, we study GF-NLFSR, a Generalized Unbalanced Feis- tel Network (GUFN) which can be considered as an extension of the outer function FO of the KASUMI block cipher. We show that the differential and linear probabilities of any n + 1 rounds of an n-cell GF-NLFSR are both bounded by p^2, where the corresponding probability of the round function is p. Besides analyzing security against differential and linear cryptanalysis, we provide a frequency distribution for upper bounds on the true differential and linear hull probabilities. From the frequency distribution, we deduce that the proportion of input-output differences/mask values with probability bounded by p^n is close to 1 whereas only a negligible proportion has probability bounded by p^2. We also recall an n^2-round integral attack distinguisher and (n^2+n-2)-round impossible impossible differential distinguisher on the n-cell GF-NLFSR by Li et al. and Wu et al. As an application, we design a new 30-round block cipher Four-Cell+ based on a 4-cell GF-NLFSR. We prove the security of Four-Cell+ against differential, linear, and boomerang attack. Four-Cell+ also resists existing key recovery attacks based on the 16-round integral attack distinguisher and 18-round impossible differential distinguisher. Furthermore, Four-Cell+ can be shown to be secure against other attacks such as higher order differential attack, cube attack, interpolation attack, XSL attack and slide attack.

Many cryptographic applications of hash functions are analyzed in the random oracle model. Unfortunately, most concrete hash functions, including the SHA family, use the iterative (strengthened) Merkle-Damgard transform applied to a corresponding compression function. Moreover, it is well known that the resulting ``structured'' hash function cannot be generically used as a random oracle, even if the compression function is assumed to be ideal. This leaves a large disconnect between theory and practice: although no attack is known for many concrete applications utilizing existing (Merkle-Damgard-based) hash functions, there is no security guarantee either, even by idealizing the compression function. Motivated by this question, we initiate a rigorous and modular study of finding kinds of (still idealized) hash functions which would be (a) elegant and interesting in their own right; (b) still enough to argue security of important applications; and (c) provably instantiable by the (strengthened) Merkle-Damgard transform, applied to a "strong enough" compression function. We develop two such notions which we believe are natural and interesting in their own right: preimage awareness and being indifferentiable from a public-use random oracle.

Recently, Tsai and Hsiang et al. each proposed a multi-server authentication protocol. They claimed their protocols are secure and can withstand various attacks. However, after our analysis, we found some security loopholes in each protocol. We will first show the attacks on their schemes and then present ours. After the security analysis, we conclude that our scheme is the most secure one among all of the proposed protocols in multi-server environments nowadays.

Entity recognition does not ask whether the message is from some entity X, just whether a message is from the same entity as a previous message. This turns turns out to be very useful for low-end devices. Motivated by an attack against a protocol presented at SAC 2003, the current paper proposes a new protocol -- the ``Jane Doe Protocol'' --, and provides a formal proof of its concrete security. The protocol neither employs asymmetric cryptography, nor a trusted third party, nor any key pre-distribution. It is suitable for light-weight cryptographic devices such as sensor network motes and RFID tags.

This paper presents a new identity based key agreement protocol. In id-based cryptography (introduced by Adi Shamir in \cite{shamir-idb}) each party uses its own identity as public key and receives his secret key from a master Key Generation Center, whose public parameters are publicly known. The novelty of our protocol is that it can be implemented over any cyclic group of prime order, where the Diffie-Hellman problem is supposed to be hard. It does not require the computation of expensive bilinear maps, or additional assumptions such as factoring or RSA. The protocol is extremely efficient, requiring only twice the amount of bandwith and computation of the {\em unauthenticated} basic Diffie-Hellman protocol. The design of our protcol was inspired by MQV (the most efficient authenticated Diffie-Hellman based protocol in the public-key model) and indeed its performance is competitive with respect to MQV (especially when one includes the transmission and verification of certificates in the MQV protocol, which are not required in an id-based scheme). Our protocol requires a single round of communication in which each party sends only 2 group elements: a very short message, especially when the protocol is implemented over elliptic curves. We provide a full proof of security in the Canetti-Krawczyk security model for key exchange, including a proof that our protocol satisfies additional security properties such as perfect forward secrecy, and resistance to reflection and key-compromise impersonation attacks.

Recently, the new Multibase Non-Adjacent Form (mbNAF) method was introduced and shown to speed up the execution of the scalar multiplication with an efficient use of multiple bases to represent the scalar. In this work, we first optimize the previous method using fractional windows, and then introduce further improvements to achieve additional cost reductions. Moreover, we present new improvements in the point operation formulae. Specifically, we reduce further the cost of composite operations such as quintupling and septupling of a point, which are relevant for the speed up of multibase methods in general. Remarkably, our tests show that, in the case of standard elliptic curves, the refined mbNAF method can be as efficient as Window-w NAF using an optimal fractional window size. Thus, this is the first published method that does not require precomputations to achieve comparable efficiency to the standard window-based NAF method using precomputations. On other highly efficient curves as Jacobi quartics and Edwards curves, our tests show that the refined mbNAF currently attains the highest performance for both scenarios using precomputations and those without precomputations.

A new protocol for 1-2 (String) Oblivious Transfer is proposed. The Protocol uses 5 rounds of message exchange.

(Full version of a PKC 2009 paper) We take a step towards a more realistic modeling of personal digital signatures, where a human user, his mobile equipment, his PC and a server are all considered as independent players in the protocol, and where only the human user is assumed incorruptible. We then propose a protocol for issuing digital signatures on behalf of the user. This protocol is proactively UC-secure assuming at most one player is corrupted in every operational phase. In more practical terms, this means that one can securely sign using terminals (PC’s) that are not necessarily trusted, as long as the mobile unit and the PC are not both corrupted at the same time. In other words, our solution cannot be broken by phising or key-logging via the PC. The protocol allows for mobile units with very small computing power by securely outsourcing computation to the PC and also allows usage of any PC that can communicate properly. Finally, we report on the results of a prototype implementation of our solution.

Two of the most recent and powerful multi-property-preserving (MPP) hash domain extension transforms are the Ramdom-Oracle-XOR (ROX) transform and the Enveloped Shoup (ESh) transform. The former was proposed by Andreeva et al. at ASIACRYPT 2007 and the latter was proposed by Bellare and Ristenpart at ICALP 2007. In the existing literature, ten notions of security for hash functions have been considered in analysis of MPP capabilities of domain extension transforms, namely CR, Sec, aSec, eSec (TCR), Pre, aPre, ePre, MAC, PRF, PRO. Andreeva et al. showed that ROX is able to preserve seven properties; namely collision resistance (CR), three flavors of second preimage resistance (Sec, aSec, eSec) and three variants of preimage resistance (Pre, aPre, ePre). Bellare and Ristenpart showed that ESh is capable of preserving five important security notions; namely CR, message authentication code (MAC), pseudorandom function (PRF), pseudorandom oracle (PRO), and target collision resistance (TCR). Nonetheless, there is no further study on these two MPP hash domain extension transforms with regard to the other properties. The aim of this paper is to fill this gap. Firstly, we show that ROX does not preserve two other widely-used and important security notions, namely MAC and PRO. We also show a positive result about ROX, namely that it also preserves PRF. Secondly, we show that ESh does not preserve other four properties, namely Sec, aSec, Pre, and aPre. On the positive side we show that ESh can preserve ePre property. Our results in this paper provide a full picture of the MPP capabilities of both ROX and ESh transforms by completing the property-preservation analysis of these transforms in regard to all ten security notions of interest, namely CR, Sec, aSec, eSec (TCR), Pre, aPre, ePre, MAC, PRF, PRO.

Trivium is a hardware-oriented stream cipher, and one of the finally chosen ciphers by eSTREAM project. Michal Hojsik and Bohuslav Rudolf presented an effective attack to Trivium, named floating fault analysis, at INDOCRYPT 2008. Their attack makes use of the fault injection and the fault float. In this paper, we present an improvement of this attack. Our attack is under following weaker and more practical assumptions.The fault injection can be made for the state at a random time.The positions of the fault bits are from random one of 3 NFSRs, and from a random area within 8 neighboring bits.We present a checking method, by which either the injecting time and fault positions can be determined, or the state differential at a known time can be determined. Each of these two determinations is enough for floating attack. After the determination, the attacker can averagely obtain 67.167 additional linear equations from 82 original quadratic equations, and obtain 66 additional quadratic equations from 66 original cubic equations.

We present a second pre-image attack on ECOH. Our attack requires $2^{143}$ time for ECOH-224 and ECOH-256, $2^{206}$ time for ECOH-384, and $2^{287}$ time for ECOH-512. The attack sets the checksum block to a fixed value and uses a collision search on the elliptic curve points.

The Feedback with Carry Shift Registers (FCSRs) have been proposed as an alternative to Linear Feedback Shift Registers (LFSRs) for the design of stream ciphers. FCSRs have good statistical properties and they provide a built-in non-linearity. However, two attacks have shown that the current representations of FCSRs can introduce weaknesses in the cipher. We propose a new ``ring'' representation of FCSRs based upon matrix definition which generalizes the Galois and Fibonacci representations. Our approach preserves the statistical properties and circumvents the weaknesses of the Fibonacci and Galois representations. Moreover, the ring representation leads to automata with a quicker diffusion characteristic and better implementation results. As an application, we describe a new version of F-FCSR stream ciphers.

\begin{abstract} In this paper, we explain the encryption algorithm used by the Queen of France, Marie-Antoinette, to send letters to Axel von Fersen during the French Revolution. We give the complete deciphering of some letters for which we found differences with the text taken from historical books. We also provide the deciphering of one letter that seems to be unknown so far. The results we get bring new proofs on Marie-Antoinette's deep affection for Fersen. Finally, we mention some open questions about Marie-Antoinette's correspondence with Axel von Fersen.

Fault Analysis is a powerful cryptanalytic technique that enables to break cryptographic implementations embedded in portable devices more efficiently than any other technique. For an RSA implemented with the Chinese Remainder Theorem method, one faulty execution suffices to factorize the public modulus and fully recover the private key. It is therefore mandatory to protect embedded implementations of RSA against fault analysis. This paper provides a new countermeasure against fault analysis for exponentiation and RSA. It consists in a {\em self-secure} exponentiation algorithm, namely an exponentiation algorithm that provides a direct way to check the result coherence. An RSA implemented with our solution hence avoids the use of an extended modulus (which slows down the computation) as in several other countermeasures. Moreover, our exponentiation algorithm involves $1.65$ multiplications per bit of the exponent which is significantly less than the $2$ required by other self-secure exponentiations.

In a proxy re-encryption scheme, a semi-trusted proxy can transform a ciphertext under Alice's public key into another ciphertext that Bob can decrypt. However, the proxy cannot access the plaintext. Due to its transformation property, proxy re-encryption can be used in many applications, such as encrypted email forwarding. In this paper, by using signature of knowledge and Fijisaki-Okamoto conversion, we propose a proxy re-encryption scheme \emph{without} pairings, in which the proxy can only transform the ciphertext in one direction. The proposal is secure against chosen ciphertext attack (CCA) and collusion attack in the \emph{random oracle model} based on Decisional Diffie-Hellman (DDH) assumption over $\mathbb{Z}_{N^2}^*$ and integer factorization assumption, respectively. To the best of our knowledge, it is the \emph{first} unidirectional PRE scheme with CCA security and collusion-resistance.

A new 4-pass Key-Agreement-Protocol is presented. The security of the protocol mainly relies on the existence of a (polynomial-time computable) One-Way-Function and the supposed hardness of solving a specific system of equations

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

Correlation power analysis (CPA) is a well-known attack against cryptographic modules with which an attacker evaluates the correlation between the power consumption and the sensitive data candidate calculated from a guessed sub-key and known data (plaintext or ciphertext). This paper enhances CPA to propose a new general power analysis, \textit{build-in determined sub-key CPA} (BS-CPA), that finds a new sub-key by using the previously determined sub-keys recursively to compute the sensitive data candidate and to increase the signal-to-noise ratio in its analysis. BS-CPA is powerful and effective when the multiple sbox outputs (or corresponding data) are processed simultaneously as in the hardware implementation. We apply BS-CPA to the power consumption traces provided at the DPA contest and succeed in finding DES key less than the original CPA does.

We study the design of cryptographic primitives resilient to key leakage attacks, where an attacker can repeatedly and adaptively learn information about the secret key, subject only to the constraint that the overall amount of such information is bounded by some parameter $\ell$. We construct a variety of leakage-resilient public-key systems including the first known identification schemes (ID), signature schemes and authenticated key agreement protocols (AKA). Our main result is an efficient three-round leakage-resilient AKA in the Random Oracle model. This protocol ensures that session-keys are private and authentic even if (1) the adversary leaks a large fraction of the long-term secret keys of both users prior to the protocol execution and (2) the adversary completely learns the long-term secret keys after the protocol execution. In particular, our AKA protocol provides qualitatively stronger privacy guarantees than leakage-resilient public-encryption schemes (constructed in prior and concurrent works), since such schemes necessarily become insecure if the adversary can perform leakage attacks after seing a ciphertext. Moreover, our schemes can be flexibly extended to the Bounded-Retrieval Model, allowing us to tolerate very large absolute amount of adversarial leakage $\ell$ (potentially many gigabytes of information), only by increasing the size of the secret key and without any other loss of efficiency in communication or computation. Concretely, given any leakage parameter $\ell$, security parameter $\lambda$, and any desired fraction $0< \delta \leq 1$, our schemes have the following properties: (1) Secret key size is $\ell(1+\delta)+O(\lambda)$. In particular, the attacker can learn an approximately $(1-\delta)$ fraction of the secret key. (2) Public key size is $O(\lambda)$, and independent of $\ell$. (3) Communication complexity is $O(\lambda/\delta)$, and independent of $\ell$. (4) All computation reads at most $O(\lambda/\delta^2)$ locations of the secret key, independently of $\ell$. Lastly, we show that our schemes allow for repeated ``invisible updates'' of the secret key, allowing us to tolerate up to $\ell$ bits of leakage in between any two updates, and an unlimited amount of leakage overall. These updates require that the parties can securely store a short ``master update key'' (e.g. on a separate secure device protected against leakage), which is only used for updates and not during protocol execution. The updates are invisible in the sense that a party can update its secret key at any point in time, without modifying the public key or notifying the other users.

Skein is a submission to the NIST SHA-3 hash function competition which has been optimized towards implementation in modern 64-bit processor architectures. This paper investigates the performance characteristics of a high-speed hardware implementation of Skein with a 0.18\,\textmu}m standard-cell library and on different modern FPGAs. The results allow a first comparison of the hardware performance figures of full Skein with other SHA-3 candidates.

Delegation of powers is a common practice in the real world. To realized the delegation of powers electronically, Mambo,Usuda and Okamoto proposed the first proxy signature scheme in 1996. Since then a number of new schemes and their improvements have been proposed. In 2008, Verma proposed a proxy signature scheme over braid groups. This paper analyzes Vermas scheme and found that this scheme suffers with the serious security flaws. In this scheme,the proxy signer is able to misuse his delegated signing capabilities and the original signer can not restrict the proxy signer for misuse her delegation power. As a result, the proposed scheme does not satisfy some essential security requirements. Vermas proposed scheme is also not secure against the original signer and proxy singer changing attacks. Thus, the proposed scheme is not only insecure against the attacks by original signer and proxy signer but also has pitfalls against the forgery attacks mounted by any antagonist.

In this article, we deal with fast arithmetic in the Picard group of hyperelliptic curves of genus 3 over binary fields. We investigate both the optimal performance curves, where $h(x)=1$, and the more general curves where the degree of $h(x)$ is 1, 2 or 3. For the optimal performance curves, we provide explicit halving and doubling formulas; not only for the most frequent case but also for all possible special cases that may occur when performing arithmetic on the proposed curves. In this situation, we show that halving offers equivalent performance to that of doubling when computing scalar multiples (by means of an halve-and-add algorithm) in the divisor class group. For the other types of curves where halving may give performance gains (when the group order is twice an odd number), we give explicit halving formulas which outperform the corresponding doubling formulas by about 10 to 20 field multiplications per halving. These savings more than justify the use of halvings for these curves, making them significantly more efficient than previously thought. For halving on genus 3 curves there is no previous work published so far.

Transversal Design is a well known combinatorial design that has been used in deterministic key predistribution scheme. Merging of blocks in a design sometimes helps to obtain a key predistribution scheme with better performance. A deterministic merging strategy to merge the blocks has been discussed. Also, a simple key establishment method for transversal design based key predistribution scheme has been discussed.

This paper proposes new explicit formulas for the doubling and addition steps in Miller's algorithm to compute the Tate pairing on elliptic curves in Weierstrass and in Edwards form. For Edwards curves the formulas come from a new way of seeing the arithmetic. We state the first geometric interpretation of the group law on Edwards curves by presenting the functions which arise in addition and doubling. The Tate pairing on Edwards curves can be computed by using these functions in Miller's algorithm. Computing the sum of two points or the double of a point and the coefficients of the corresponding functions is faster with our formulas than with all previ ously proposed formulas for pairings on Edwards curves. They are even competitive with all published formulas for pairing computation on Weierstrass curves. We also improve the formulas for Tate pairing computation on Weierstrass curve s in Jacobian coordinates. Finally, we present several examples of pairing-friendly Edwards curves.

It is well known that the problem to solve a set of randomly chosen multivariate quadratic equations over a finite field is NP-hard. However, when the number of variables is much larger than the number of equations, it is not necessarily difficult to solve equations. In fact, when n>m(m+1) (n,m are the numbers of variables and equations respectively) and the field is of even characteristic, there is an algorithm to solve equations in polynomial time (see [Kipnis et al, Eurocrypt'99] and also [Courtois et al, PKC'02]). In the present paper, we give two algorithms to solve quadratic equations; one is for the case of n>(about)m^2-2m^{3/2}+2m and the other is for the case of n>m(m+1)/2+1. The first algorithm solves equations over any finite field in polynomial time. The second algorithm requires exponential time operations. However, the number of required variables is much smaller than that in the first one, and the complexity is much less than the exhaustive search.

Using the pigeon-hole principle, we derive a new bound for the key length in a t-wise almost universal hash function where the multicollision or t-collision probability is bounded above by epsilon in the range [0,1]. The important features of this bound are (1) it decreases very slowly as t increases, and (2) the key length grows at least linearly with the logarithm of the message length. To our knowledge, this is the first almost universal hash bound for any integer t > 1. This work arises from the use of t-wise almost universal hash functions in manual authentication protocols.

Despite the large volume of societal interactions taking place on the Internet, it is still hard to assess the credibility of statements made by online users. The digital credentials issued by trustworthy certificate authorities partially address this problem, but a tedious registration and verification process as well as its high cost hinder the wide adoption of this solution. This paper presents FaceTrust, a system that leverages online social networks to provide lightweight, flexible and relaxed credentials that enable users to assess the credibility of others and their assertions.

It is known that Euclid's algorithm, Guass' elimination and Buchberger's algorithm play important roles in algorithmic number theory, symbolic computation and cryptography, and even in science and engineering. The aim of this paper is to reveal again the relations of these three algorithms, and, simplify Buchberger's algorithm without using multivariate division algorithm. We obtain an algorithm for computing the greatest common divisor of several positive integers, which can be regarded as the generalization of Euclid's algorithm. This enables us to re-find the Guass' elimination and further simplify Buchberger's algorithm for computing Gröbner bases of polynomial ideals in modern Computational Algebraic Geometry.

We re-examine the needs of computer security in pervasive computing from first principles, specifically the problem of bootstrapping secure networks. We consider the case of systems that may have no shared secret information, and where there is no structure such as a PKI available. We propose several protocols which achieve a high degree of security based on a combination of human-mediated communication and an ordinary Dolev-Yao communication medium. In particular they resist combinatorial attacks on the hash or digest values that have to be compared by human users, seemingly optimising the amount of security they can achieve for a given amount of human effort. We compare our protocols with recent pairwise protocols proposed by, for example, Hoepman and Vaudenay.

The increased functionality of EPC Class1 Gen2 (EPCGen2) is making this standard a de facto specification for inexpensive tags in the RFID industry. Recently three EPCGen2 compliant protocols that address security issues were proposed in the literature. In this paper we analyze these protocols and show that they are not secure and subject to replay/impersonation and statistical analysis attacks. We then propose an EPCGen2 compliant RFID protocol that uses the numbers drawn from synchronized pseudorandom number generators (RNG) to provide secure tag identification and session unlinkability. This protocol is optimistic and its security reduces to the (cryptographic) pseudorandomness of the RNGs supported by EPCGen2.

Secret handshake allows two members in the same group to authenticate each other secretly. In previous works of secret handshake schemes, two types of anonymities against the group authority (GA) of a group G are discussed: 1)Even GA cannot identify members, namely nobody can identify them (No-Traceability), 2)Only GA can identify members (Traceability). In this paper, first the necessity of tracing of the identification is shown. Second, we classify abilities of GA into the ability of identifying players and that of issuing the certificate to members. We introduce two anonymities Co-Traceability and Strong Detector Resistance. When a more strict anonymity is required ever for GA, the case 2) is unfavorable for members. Then, we introduce Co-Traceability where even if A has GAs ability of identifying members or issuing the certificate, A cannot trace members identification. However, if a scheme satisfies Co-Traceability, GA may be able to judge whether handshake players belong to the own group. Then, we introduce Strong Detector Resistance where even if an adversary A has GAs ability of identifying members, A cannot make judgments whether a handshaking player belongs to G. Additionally, we propose a secret handshake scheme which satisfies previous security requirements and our proposed anonymity requirements by using group signature scheme with message recovery.

The hash function ARIRANG is one of the 1st round SHA-3 candidates. In this paper, we present preimage attacks on ARIRANG with step-reduced compression functions. We consider two step-reduced variants of the compression function. First one uses the same feedforward$_1$ as the original algorithm, and the other one has the feedforward$_1$ working at the output of the half steps. Our attack finds a preimage of the 33-step OFF(Original FeedForward$_1$)-variants of ARIRANG-256 and ARIRANG-512 from Step 1 to Step 33, and a preimage of the 31-step MFF(Middle FeedForward$_1$)-variants of ARIRANG-256 and ARIRANG-512 from Step 3 to Step 33.

We propose an efficient blind certification protocol with interesting properties. It falls in the Groth-Sahai framework for witness-indistinguishable proofs, thus extended to a certified signature it immediately yields non-frameable group signatures. We use blind certification to build an efficient (offline) e-cash system that guarantees user anonymity and transferability of coins without increasing their size. As required for fair e-cash, in case of fraud, anonymity can be revoked by an authority, which is also crucial to deter from double spending.

In this paper, we study security of a certain class of permutation-based compression functions. Denoted lp 231 by Rogaway and Steinberger, they are 2n-to-n-bit compression functions using three calls to a single $n$-bit random permutation. We prove that lp 231 is asymptotically preimage resistant up to 2^{2n/3}/n query complexity and collision resistant up to 2^{n/2}/n^{1+e} query complexity for any e>0. Based on a single permutation, lp 231 provides both efficiency and almost optimal collision security.

Signcryption is a cryptographic primitive which offers authentication and confidentiality simultaneously with a cost lower than signing and encrypting the message independently. Ring signcryption enables a user to signcrypt a message along with the identities of a set of potential senders (that includes him) without revealing which user in the set has actually produced the signcryption. Thus a ring signcrypted message has anonymity in addition to authentication and confidentiality. Ring signcryption schemes have no group managers, no setup procedures, no revocation procedures and no coordination: any user can choose any set of users (ring), that includes himself and signcrypt any message by using his private and public key as well as other users (in the ring) public keys, without getting any approval or assistance from them. Ring Signcryption is useful for leaking trustworthy secrets in an anonymous, authenticated and confidential way. \medskip To the best of our knowledge, seven identity based ring signcryption schemes are reported in the literature. Two of them were already proved to be insecure in \cite{ZBSW08} and \cite{SSP09}. In this paper, we show that four among the remaining five schemes do not provide confidentiality, to be specific, two schemes are not secure against chosen plaintext attack and other two schemes do not provide adaptive chosen ciphertext security. We then propose a new scheme and formally prove the security of the new scheme in the random oracle model. A comparison of our scheme with the only existing correct scheme by Huang et al. shows that our scheme is much more efficient than the scheme by Huang et al.

We newly propose a multiple and unlinkable identity-based public key encryption scheme. Unlike the traditional public key encryption and identity-based encryption schemes, our scheme allows the use of a various number of identity-based public keys in different groups or applications while keeping a single decryption key so that the decryption key can decrypt every ciphertexts encrypted with those public keys. Also our scheme removes the use of certificates as well as the key escrow problem so it is functional and practical. Since our public keys are unlinkable, the user's privacy can be protected from attackers who collect and trace the user information and behavior using the known public keys. Furthermore, we suggest a decryption key renewal protocol to strengthen the security of the single decryption key. Finally, we prove the security of our scheme against the adaptive chosen-ciphertext attack under the random oracle model.

We put forward the new abstract framework of "hard algebraic set systems" that allows to construct efficient chosen-ciphertext secure encryption schemes under computational (rather than decisional) intractability assumptions. Our framework can be instantiated with both RSA and Diffie-Hellman type assumptions, but in itself is completely abstract.

Hierarchical secret sharing is among the most natural generalizations of threshold secret sharing, and it has attracted a lot of attention since the invention of secret sharing until nowadays. Several constructions of ideal hierarchical secret sharing schemes have been proposed, but it was not known what access structures admit such a scheme. We solve this problem by providing a natural definition for the family of the hierarchical access structures and, more importantly, by presenting a complete characterization of the ideal hierarchical access structures, that is, the ones admitting an ideal secret sharing scheme. Our characterization is based on the well known connection between ideal secret sharing schemes and matroids and, more specifically, on the connection between ideal multipartite secret sharing schemes and integer polymatroids. In particular, we prove that every hierarchical matroid port admits an ideal linear secret sharing scheme over every large enough finite field. Finally, we use our results to present a new proof for the existing characterization of the ideal weighted threshold access structures.

In~\cite{gscm}, GSCM mode of operation for authenticated encryption was presented. GSCM is based on the Galois/Counter Mode (GCM). GSCM is an enhancement of GCM, which is characterized by its high throughput and low memory consumption in network applications. In this paper, we propose some enhancements to GSCM and compare it with the different implementations of GCM. We present stability, performance, memory and security analyses of different implementations of GSCM and GCM.

Since Al-Riyami and Paterson presented certificateless cryptography, many certificateless schemes have been proposed for different purposes. In this paper, we present a certificateless group oriented signature scheme based on bilinear pairing. In our scheme, only the members in the same group with the signer can independently verify the signature. We prove the signature scheme is existential unforgeability under adaptive chosen message attack in random oracle model.

We study the problem how to construct an RFID mutual authentication protocol between tags and readers. Juels (in Journal on Selected Areas in Communications, 2006) proposed an open question which asks whether there exists a fully privacy-preserving RFID authentication protocol in which the time complexity of a successful authentication phase can be done in sub-linear time $o(n)$ where $n$ is the number of tags participating in the RFID system. In this work, we answer this question positively in an amortized view. Precisely, we design a fully privacy-preserving protocol in which the amortized cost of a successful authentication phase only requires time $O(n^{3/4})$. In addition, our protocol is a hybrid from the randomized hash lock scheme of Weis et. al., the hash chain scheme of Ohkubo et. al., and the efficient identification scheme of Dimitriou. We combine them delicately to obtain the desired authentication protocol.

MiFare Classic is the most popular contactless smart card with about 200 millions copies in circulation worldwide. At Esorics 2008 Dutch researchers showed that the underlying cipher Crypto-1 can be cracked in as little as 0.1 seconds if the attacker can access or eavesdrop the RF communications with the (genuine) reader. We discovered that a MiFare classic card can be cloned in a much more practical card-only scenario, where the attacker only needs to be in the proximity of the card for a number of minutes, therefore making usurpation of identity through pass cloning feasible at any moment and under any circumstances. For example, anybody sitting next to the victim on a train or on a plane is now be able to clone his/her pass. Other researchers have also (independently from us) discovered this vulnerability, however our attack requires less queries to the card and does not require any precomputation. In addition, we discovered that certain versions or clones of MiFare Classic are even weaker, and can be cloned in 1 second. The main security vulnerability that we need to address with regard to MiFare Classic is not about cryptography, RFID protocols and software vulnerabilities. It is a systemic one: we need to understand how much our economy is vulnerable to sophisticated forms of electronic subversion where potentially one smart card developer can intentionally (or not), but quite easily in fact, compromise the security of governments, businesses and financial institutions worldwide.

We examine the use of randomness extraction and expansion in key agreement (KA) protocols to generate uniformly random keys in the standard model. Although existing works provide the basic theorems necessary, they lack details or examples of appropriate cryptographic primitives and/or parameter sizes. This has lead to the large amount of min-entropy needed in the (non-uniform) shared secret being overlooked in proposals and efficiency comparisons of KA protocols. We therefore summarize existing work in the area and examine the security levels achieved with the use of various extractors and expanders for particular parameter sizes. The tables presented herein show that the shared secret needs a min-entropy of at least 292 bits (and even more with more realistic assumptions) to achieve an overall security level of 80 bits using the extractors and expanders we consider. The tables may be used to find the min-entropy required for various security levels and assumptions. We also find that when using the short exponent theorems of Gennaro et al., the short exponents may need to be much longer than they suggested.

Edon-R is one of the fastest SHA-3 candidate. In this paper we study the security of Edon-R, and we show that using Edon-R as a MAC with the secret prefix construction is unsafe. We present a practical attack in the case of Edon-R256, which requires 32 queries, 2^30 computations, negligible memory, and a precomputation of 2^50 . This does not directly contradict the security claims of Edon-R or the NIST requirements for SHA-3, but we believe it shows a strong weakness in the design.

This paper proposed a first order recursive construction of Boolean function with optimum algebraic immunity. We also show that the Boolean functions are balanced and have good algebraic degrees.

A leakage-resilient cryptosystem remains secure even if arbitrary information about the secret key (or possibly other internal state information) is leaked to an adversary. We demonstrate the first constructions of leakage-resilient signature schemes that remain secure as long as a bounded amount of information, depending on the length $n$ of the secret key, is leaked. We show efficient schemes in the random oracle model that handle leakage of up to $(1/2-\epsilon) n$ bits of information about the signer's entire internal state. In the standard model, we show an inefficient scheme that can handle leakage of up to $(1-\epsilon) n$ bits of information about the secret key, and a one-time signature scheme tolerating arbitrary leakage of $n^{1-\epsilon}$ bits.

In PKC 2009, Alexander May and Maike Ritzenhofen\cite{MR} proposed an ingenious lattice-based method to factor the RSA moduli $N_1=p_1q_1$ with the help of the oracle which outputs $N_2=p_2q_2$, where $p_1$ and $p_2$ share the $t$ least significant bits and $t$ is large enough when we query it with $N_1$. They also showed that when asking $k-1$ queries for RSA moduli with $\alpha$-bit $q_i$, they can improve the bound on $t$ to $t\geq\frac{k}{k-1}\alpha$. In this paper, we propose a new lattice for implicit factoring in polynomial time, and $t$ can be a little smaller than in \cite{MR}. Moreover, we also give a method in which the bound on $t$ can also be improved to $t\geq\frac{k}{k-1}(\alpha-1+\frac{1}{2}\log{\frac{k+3}{k}})$ but with just only one query. Moreover we can show that our method reduces the running time of the implicit factoring for balanced RSA moduli much efficiently and makes it practical.

A Sensor Node in Wireless Sensor Network has very limited resources such as processing capability, memory capacity, battery power, and communication capability. When the communication between any two sensor nodes are required to be secured, the symmetric key cryptography technique is used for its advantage over public key cryptography in terms of requirement of less resources. Keys are pre-distributed to each sensor node from a set of keys called key pool before deployment of sensors nodes. Combinatorial design helps in a great way to determine the way keys are drawn from the key pool for distributing to individual sensor nodes. We study various deterministic key predistribution techniques that are based on combinatorial design.