Deniable encryption, introduced in 1997 by Canetti, Dwork, Naor, and Ostrovsky, guarantees that the sender or the receiver of a secret message is able to "fake" the message encrypted in a specific ciphertext in the presence of a coercing adversary, without the adversary detecting that he was not given the real message. To date, constructions are only known either for weakened variants with separate "honest" and "dishonest" encryption algorithms, or for single-algorithm schemes with non-negligible detection probability. We propose a sender-deniable public key encryption system with a single encryption algorithm. We describe a generic interactive construction based on a public key bit encryption scheme that has certain properties, and we give two examples of encryption schemes with these properties, one based on the quadratic residuosity assumption and the other on trapdoor permutations. Subsequent to the publication of this work in EUROCRYPT 2011, it was shown by Peikert and Waters that, contrary to our initial claim, the proposed scheme does not have negligible detection probability. In this updated version we describe the attack of Peikert and Waters and the error in our original proof. We include the previous version of the paper with the construction and the (incorrect) security theorem.

We propose a coin-flip protocol which yields a string of strong, random coins and is fully simulatable against poly-sized quantum adversaries on both sides. It can be implemented with quantum-computational security without any set-up assumptions, since our construction only assumes mixed commitment schemes which we show how to construct in the given setting. We then show that the interactive generation of random coins at the beginning or during outer protocols allows for quantum-secure realizations of classical schemes, again without any set-up assumptions. As example applications we discuss quantum zero-knowledge proofs of knowledge and quantum-secure two-party function evaluation. Both applications assume only fully simulatable coin-flipping and mixed commitments. Since our framework allows to construct fully simulatable coin-flipping from mixed commitments, this in particular shows that mixed commitments are complete for quantum-secure two-party function evaluation. This seems to be the first completeness result for quantum-secure two-party function evaluation from a generic assumption.

The publication of private data in user profiles in a both secure and private way is a rising problem and of special interest in, e.g., online social networks that become more and more popular. Current approaches, especially for decentralized networks, often do not address this issue or impose large storage overhead. In this paper, we present a cryptographic approach to \emph{private profile management} that is seen as a building block for applications in which users maintain their own profiles, publish and retrieve data, and authorize other users to access different portions of data in their profiles. In this course, we provide: (i) formalization of \emph{confidentiality} and \empf{unlinkability} as two main security and privacy goals for the data which is kept in profiles and users who are authorized to retrieve this data, and (ii) specification, analysis, and comparison of two private profile management schemes based on different encryption techniques.

We study the problem of unconditionally secure Secret Key Establishment (SKE) when Alice and Bob are connected by two noisy channels in opposite directions, and the channels are eavesdropped by Eve. We consider the case that Alice and Bob do not have any sources of initial randomness at their disposal. We start by discussing special cases of interest where SKE is impossible, and then provide a simple SKE construction over a binary symmetric channel that achieves some rates of secret key. We next focus on the Secret Key (SK) capacity, i.e., the highest rate of secure and reliable key establishment (in bits per channel use) that the parties can achieve. Relying on the existence of capacity-achieving coding schemes, we propose a multi-round SKE protocol, called the \emph{main protocol}, that proves a lower bound on the SK capacity. The main protocol consists of an initialization round, followed by repeated use of a two-round SKE protocol, called the \emph{basic protocol}. We also provide an upper bound on the SK capacity and show that the two bounds coincide when channels do not leak information to the adversary. We apply the results to the case that communicants are connected by binary symmetric channels.

In this work we consider two protocols for performing cryptanalysis and security enhancement. The first one by Song, is a password authentication scheme based on smart cards. We note that this scheme has already been shown vulnerable to the off-line password guessing attack by Tapiador et al. We perform a further cryptanalysis on this protocol and observe that it is prone to the clogging attack, a kind of denial of service (DOS) attack. We observe that all smart card based authentication protocols which precede the one by Song, and require the server to compute the computationally intensive modular exponentiation, like the one by Xu et al., or Lee at al., are prone to the clogging attack. We then suggest an improvement on the protocol to prevent the clogging attack. The other protocol we consider is a two-party identity-based authenticated key agreement protocol by Hölbl et al. They have devised two such protocols in their work. They call them Protocol 1 and Protocol 2. Both the protocols have already been shown vulnerable to the insider attack in a recent work by Chen et al. Here we consider Protocol 2 and show its vulnerability to a simple man-in-the-middle attack where the adversary does not know or calculate either party's private key, or the session key. Protocol 2 by Hölbl et al is an improvement over a previous work by Tseng. This makes the Tseng's protocol vulnerable to the attack we illustrate. We further suggest an additional step for these protocols to make them immune against the man-in-the-middle attack.

In this paper we analyze the security of the mutual authentication and ownership transfer protocols which have been recently proposed by Kulseng \textit{et al.} Our analysis demonstrates a variety of attacks against these protocols. We present a secret parameters disclosure attack which discloses any secret parameter between the tag and the reader. Our disclosure attack can be easily used as an impersonation attack against the mutual authentication protocol. In addition, we present an attack that retrieves the $PIN$-value in the ownership transfer protocol, where the $PIN$-value is a parameter that must be kept secret from any party including the owner of the tag. All the attacks presented in this work are passive, have low complexity and have the success probability of 1.

Group signature schemes allow users to sign messages on behalf of a group while (1) maintaining anonymity (within that group) with respect to an observer, yet (2) ensuring traceability of a signer (by the group manager) when needed. In this work we give the first construction of a group signature scheme based on lattices (more precisely, the learning with errors assumption), in the random oracle model. Toward our goal, we construct a new algorithm for sampling a random superlattice of a given modular lattice together with a short basis, that may be of independent interest.

Recently, a non-abelian factorization problem together with an associated asymmetric encryption scheme were introduced in [1]. We show how a classical baby-step giant-step algorithm for discrete logarithm can be extended to this problem. This contradicts the claims regarding the complexity of the proposed problem.

We describe and analyze the password-based key establishment protocol PACE v2 Integrated Mapping (IM), an evolution of PACE v1 jointly proposed by Gemalto and Sagem Sécurité. PACE v2 IM enjoys the following properties: patent-freeness3 (to the best of current knowledge in the field); full resistance to dictionary attacks, secrecy and forward secrecy in the security model agreed upon by the CEN TC224 WG16 group; optimal performances. The PACE v2 IM protocol is intended to provide an alternative to the German PACE v1 protocol, which is also the German PACE v2 Generic Mapping (GM) protocol, proposed by the German Federal Office for Information Security (BSI). In this document, we provide a description of PACE v2 IM, a description of the security requirements one expects from a password-based key establishment protocol in order to support secure applications, and a security proof of PACE v2 IM in the so-called Bellare-Pointcheval-Rogaway (BPR) security model.

Affine-padding {\sc rsa} signatures consist in signing $\omega\cdot m+\alpha$ instead of the message $m$ for some fixed constants $\omega,\alpha$. A thread of publications progressively reduced the size of $m$ for which affine signatures can be forged in polynomial time. The current bound is $\log m \sim \frac{N}{3}$ where $N$ is the {\sc rsa} modulus' bit-size. Improving this bound to $\frac{N}{4}$ has been an elusive open problem for the past decade.\smallskip In this invited talk we consider a slightly different problem: instead of minimizing $m$'s size we try to minimize its {\sl entropy}. We show that affine-padding signatures on $\frac{N}{4}$ entropy-bit messages can be forged in polynomial time. This problem has no direct cryptographic impact but allows to better understand how malleable the {\sc rsa} function is. In addition, the techniques presented in this talk might constitute some progress towards a solution to the longstanding $\frac{N}{4}$ forgery open problem.\smallskip\smallskip We also exhibit a sub-exponential time technique (faster than factoring) for creating affine modular relations between strings containing three messages of size $\frac{N}{4}$ and a fourth message of size $\frac{3N}{8}$.\smallskip Finally, we show than $\frac{N}{4}$-relations can be obtained in specific scenarios, {\sl e.g.} when one can pad messages with two independent patterns or when the modulus' most significant bits can be chosen by the opponent.\smallskip

This paper introduces a new family of distinguishers for side channel analysis, based on the spectral coherence between leakage traces. Its main goal is to allow adversaries and evaluators of cryptographic devices to take advantage of both time domain and frequency domain intuitions, while also allowing to keep a generic attack in case such intuitions are not available. Compared to previous side channel analysis tools working in the frequency domain, Spectral Coherence Analysis has the significant advantage of directly capturing the degree of similarity between different time domain traces, rather than comparing them with an hypothetical (e.g. Hamming distance) leakage model. In other words, we exploit leakage models to build partitions of the leakage, but not to correlate with an estimated spectrum. As a result, we obtain a more generic and remarkably robust distinguisher. First experiments performed against an unprotected DES implementation suggest that we also gain an improved efficiency in certain meaningful application contexts.

The Isomorphism of Polynomials (IP) is one of the most fundamental problems in multivariate public key cryptography (MPKC). In this paper, we introduce a new framework to study the counting problem associated {to} IP. Namely, we present tools of finite geometry allowing to investigate the counting problem associated to IP. Precisely, we focus on enumerating or estimating the number of isomorphism equivalence classes of homogeneous quadratic polynomial systems. These problems are equivalent to finding the scale of the key space of a multivariate cryptosystem and the total number of different multivariate cryptographic schemes respectively, which might impact the security and the potential capability of MPKC. We also consider their applications in the analysis of a specific multivariate public key cryptosystem. Our results not only answer how many cryptographic schemes can be derived from monomials and how big the key space is for a fixed scheme, but also show that quite many HFE cryptosystems are equivalent to a Matsumoto-Imai scheme.

A computational group is pseudo-free if an adversary cannot find solutions in this group for equations that are not trivially solvable in the free group. This notion was put forth by Rivest as a unifying abstraction of multiple group-related hardness assumptions commonly used in cryptography. Rivest's conjecture that the RSA group is pseudo-free had been settled by Micciancio for the case of RSA moduli that are the product of two safe primes. This result holds for a static setting where the adversary is only given the description of the group (together with a set of randomly chosen generators) and has to come up with the equation and the solution. In this paper we explore a powerful extension of the notion of pseudo-freeness. We identify, motivate, and study pseudo-freeness in face of adaptive adversaries who may learn solutions to other non-trivial equations before having to solve a new non-trivial equation. Our first contribution is a carefully crafted definition of adaptive pseudo-freeness that walks a fine line between being too weak and being unsatisfiable. We give generic constructions that show how any group that satisfies our definition can be used to construct digital signatures and network signature schemes. Next, we prove that the RSA group meets our more stringent notion of pseudo-freeness and as a consequence we obtain different results. First, we obtain a new network (homomorphic) signature scheme in the standard model. Secondly, we demonstrate the generality of our framework for signatures by showing that all existing strong RSA-based signature schemes are instantiations of our generic construction in the RSA group.

An attribute-based signature with respect to a signing policy, chosen ad-hoc by the signer, convinces the verifier that the signer holds a subset of attributes satisfying that signing policy. Ideally, the verifier must obtain no other information about the identity of the signer or the attributes he holds. This primitive has many applications in real scenarios requiring both authentication and anonymity/privacy properties. We propose in this paper the first attribute-based signature scheme satisfying at the same time the following properties: (1) it admits general signing policies, (2) it is proved secure against fully adaptive adversaries, in the standard model, and (3) the number of elements in a signature depends only on the size of the signing policy. Furthermore, our scheme enjoys the additional property of revocability: an external judge can break the anonymity of a signature, when necessary. This property may be very interesting in real applications where authorities are unwilling to allow full anonymity of users.

In this work, we present HIBE and ABE schemes which are ``unbounded" in the sense that the public parameters do not impose additional limitations on the functionality of the systems. In all previous constructions of HIBE in the standard model, a maximum hierarchy depth had to be fixed at setup. In all previous constructions of ABE in the standard model, either a small universe size or a bound on the size of attribute sets had to be fixed at setup. Our constructions avoid these limitations. We use a nested dual system encryption argument to prove full security for our HIBE scheme and selective security for our ABE scheme, both in the standard model and relying on static assumptions. Our ABE scheme supports LSSS matrices as access structures and also provides delegation capabilities to users.

In this note, we define a cryptosystem based on non-commutative properties of groups. The cryptosystem is based on the hardness of the problem of factoring over these groups. This problem, interestingly, boils down to discrete logarithm problem on some Abelian groups. Further, we illustrate this method in three different non-Abelian groups GL$_n({{\mathbb{F}}_q})$, UT$_n({{\mathbb{F}}_q})$ and the Braid Groups.

It is observed that exchanging two values of a function over ${\mathbb F}_{2^n}$, its differential uniformity and nonlinearity change only a little. Using this idea, we find permutations of differential $4$-uniform over ${\mathbb F}_{2^6}$ whose number of the pairs of input and output differences with differential $4$-uniform is $54$, less than $63$, which provides a solution for an open problem proposed by Berger et al. \cite{ber}. Moreover, for the inverse function over $\mathbb{F}_{2^n}$ ($n$ even), various possible differential uniformities are completely determined after its two values are exchanged. As a consequence, we get some highly nonlinear permutations with differential uniformity $4$ which are CCZ-inequivalent to the inverse function on $\mathbb{F}_{2^n}$.

A deniable cryptosystem allows a sender and a receiver to communicate over an insecure channel in such a way that the communication is still secure even if the adversary can threaten the parties into revealing their internal states after the execution of the protocol. This is done by allowing the parties to change their internal state to make it look like a given ciphertext decrypts to a message different from what it really decrypts to. Deniable encryption was in this way introduced to allow to deny a message exchange and hence combat coercion. Depending on which parties can be coerced, the security level, the flavor and the number of rounds of the cryptosystem, it is possible to define a number of notions of deniable encryption. In this paper we prove that there does not exist any non-interactive receiver-deniable cryptosystem with better than polynomial security. This also shows that it is impossible to construct a non-interactive bi-deniable public-key encryption scheme with better than polynomial security. Specifically, we give an explicit bound relating the security of the scheme to how efficient the scheme is in terms of key size. Our impossibility result establishes a lower bound on the security. As a final contribution we give constructions of deniable public-key encryption schemes which establishes upper bounds on the security in terms of key length. There is a gap between our lower and upper bounds, which leaves the interesting open problem of finding the tight bounds.

Identification, authentication and key agreement protocol of UMTS networks with security mode setup has some weaknesses in the case of mutual freshness of key agreement, DoS-attack resistance, and efficient bandwidth consumption. In this article we consider UMTS AKA and some other proposed schemes. Then we explain the known weaknesses of the previous frameworks suggested for the UMTS AKA protocol. After that we propose a new protocol called private identification, authentication, and key agreement protocol (PIAKAP), for UMTS mobile network. Our suggested protocol combines identification and AKA stages of UMTS AKA protocol while eliminates disadvantages of related works and brings some new features to improve the UMTS AKA mechanism. These features consist of reducing the interactive rounds of the UMTS AKA with security mode setup and user privacy establishment.

As a generalization of double base chains, multibase number system is very suitable for efficient computation of scalar multiplication of a point of elliptic curve because of shorter representation length and hamming weight. In this paper combined with the given formulas for computing the 7- Fold of an elliptic curve point P an efficient scalar multiplication algorithm of elliptic curve is proposed using 2,3 and 7 as basis of the multi based number system . The algorithms cost less compared with Shamirs trick and interleaving with NAFs method.

A proxy blind signature scheme is a special form of blind signature which allowed a designated person called proxy signer to sign on behalf of two or more original signers without knowing the content of the message or document. It combines the advantages of proxy signature, blind signature and multi-signature scheme. This paper describes an e±cient proxy blind multi-signature scheme. The security of the proposed schemes is based on the di±culty of breaking the one-way hash function and the elliptic curve discrete logarithm problem (ECDLP). This can be implemented in low power and small processor handheld devices such as smart card, PDA etc which work in low power and small processor. This scheme utilizes a trusted third party called certificate authority to ensure that signatures can only be generated during valid delegation period. It satisfies the security properties of both proxy and blind signature scheme.

We design a probabilistic algorithm for computing endomorphism rings of ordinary elliptic curves defined over finite fields that we prove has a subexponential runtime in the size of the base field, assuming solely the generalized Riemann hypothesis. Additionally, we improve the asymptotic complexity of previously known, heuristic, subexponential methods by describing a faster isogeny-computing routine.

The scope of mobile phones has skyrocketed in recent years to such an extent that smartphone sales are expected to surpass those of PCs by the end of 2011. Equipped with relatively powerful processors and fairly large memory and storage capabilities, smartphones can accommodate increasingly complex interactive applications. As a result, the growing amount of sensitive information shared by smartphone users raises serious privacy concerns and motivates the need for appropriate privacy-preserving mechanisms. In this paper, we present a novel architecture geared for privacy-sensitive applications where personal information is shared among users and decisions are made based on given optimization criteria. Specifically, we focus on two application scenarios: (i) privacy-preserving interest sharing, i.e., discovering shared interests without leaking users' private information, and (ii) private scheduling, i.e., determining common availabilities and location preferences that minimize associate costs, without exposing any sensitive information. We propose efficient yet provably-private solutions, and conduct an extensive experimental analysis that attests to the practicality of the attained privacy features.

We provide a simple and exact formula for the minimum Miller loop length in Ate_i pairing based on Brezing-Weng curves, in terms of the involved parameters, under a mild condition on the parameters. It will be also shown that almost all cryptographically useful parameters satisfy the mild condition. Hence the simple and exact formula is valid for them. It will also turn out that the formula depends only on two parameters, providing freedom to choose the other parameters to address the design issues other than minimizing the loop length.

Ciet et al.(2006) proposed an elegant method for trading inversions for multiplications when computing [2] P+Q from two given points P and Q on elliptic curves of Weierstrass form. Motivated by their work, this paper proposes a fast algorithm for computing [4] P with only one inversion in affine coordinates. Our algorithm that requires 1I+ 8S+ 8M, is faster than two repeated doublings whenever the cost of one field inversion is more expensive than the cost of four field multiplications plus four field squarings (ie I> 4M+ 4S). It saves one field multiplication and one field squaring in comparison with the Sakai-Sakurai method (2001). Even better, for special curves that allow" a= 0"(or" b= 0") speedup, we obtain [4] P in affine coordinates using just 1I+ 5S+ 9M (or 1I+ 5S+ 6M, respectively).

A method for extracting cryptographic key material from DRAM used in modern computers has been recently proposed in [9]; the technique was called Cold Boot attacks. When considering block ciphers, such as the AES and DES, simple algorithms were also proposed in [9] to recover the cryptographic key from the observed set of round subkeys in memory (computed via the cipher’s key schedule operation), which were however subject to errors due to memory bits decay. In this work we extend this analysis to consider key recovery for other ciphers used in Full Disk Encryption (FDE) products. Our algorithms are also based on closest code word decoding methods, however apply a novel method for solving a set of non-linear algebraic equations with noise based on Integer Programming. This method should have further applications in cryptology, and is likely to be of independent interest. We demonstrate the viability of the Integer Programming method by applying it against the Serpent block cipher, which has a much more complex key schedule than AES. Furthermore, we also consider the Twofish key schedule, to which we apply a dedicated method of recovery.

In this work, we study the application of higher-order differential attacks on hash functions. We show a second-order differential attack on the SHA-256 compression function reduced to 46 out of 64 steps. We implemented the attack and give the result in Table 1. The best attack so far (in a different attack model) with practical complexity was for 33 steps of the compression function.

Cryptography algorithm standards play a key role both to the practice of information security and to cryptography theory research. Among them, the MQV and HMQV protocols ((H)MQV, in short) are a family of implicitly authenticated Diffie-Hellman key-exchange (DHKE) protocols that are among the most efficient and are widely standardized. In this work, from some new perspectives and under some new design rationales, and also inspired by the security analysis of HMQV, we develop a new family of practical implicitly authenticated DHKE (IA-DHKE) protocols, which enjoy notable performance among security, efficiency, privacy, fairness and easy deployment. We make detailed comparisons between our new protocols and (H)MQV, showing that the newly developed protocols outperform HMQV in most aspects. Very briefly speaking, we achieve: 1. The most efficient provably secure IA-DHKE protocol to date, and the first online-optimal provably secure IA-DHKE protocols. 2. The first IA-DHKE protocol that is provably secure, resilience to the leakage of DH components and exponents, under merely standard assumptions without additionally relying on the knowledge-of-exponent assumption (KEA). 3. The first provably secure privacy-preserving and computationally fair IA-DHKE protocol, with privacy-preserving properties of reasonable deniability and post-ID computability and the property of session-key computational fairness. Guided by our new design rationales, in this work we also formalize and introduce some new concept, say session-key computational fairness (as a complement to session-key security), to the literature.

We study the problem of authentication based on a weak key in the information-theoretic setting. A key is weak if its min-entropy is an arbitrary small fraction of its bit length. This problem has recently received considerable attention, with different solutions optimizing different parameters. We study the problem in an extended setting, where the weak key is as a one-time session key that is derived from a public source of randomness with the help of a (potentially also weak) long-term key. Our goal now is to authenticate a message by means of the weak session key in such a way that (nearly) no information on the long-term key is leaked. Ensuring privacy of the long-term key is vital for the long-term key to be re-usable. Previous work has not considered such a privacy issue, and previous solutions do not seem to satisfy this requirement. We show the existence of a practical four-round protocol that provides message authentication from a weak session key and that avoids non-negligible leakage on the long-term key. The security of our scheme also holds in the quantum setting where the adversary may have limited quantum side information on the weak session key. As an application of our scheme, we show the existence of an identification scheme in the bounded quantum storage model that is secure against a man-in-the-middle attack and that is truly password-based: it does not need any high entropy key, in contrast to the scheme proposed by Damgaard et al..

We show how the study of the geometry of the nine flex tangents to a cubic produces many pseudo-parameterizations, including the ones given by Icart, Kammerer, Lercier, Renault and Farashahi.

In 2008 I. Dinur and A. Shamir presented a new type of algebraic attack on symmetric ciphers named cube attack. The method has been applied to reduced variants of stream ciphers Trivium and Grain- 128, reduced variants of the block ciphers Serpent and CTC and to a reduced version of the keyed hash function MD6. Independently a very similar attack named AIDA was introduced by M. Vielhaber. In this paper we develop quadraticity tests within the cube attack and apply them to a variant of stream cipher Trivium reduced to 709 initialization rounds. Using this method we obtain the full 80-bit secret key. In this way it eliminates the stage of brute force search of some secret key bits which occured in previous cube attacks. In this corrigendum to our previous paper the indexing of cubes and key bits was reversed making it consistent with other papers.

We present an efficient and optimally resilient Asynchronous Byzantine Agreement (ABA) protocol involving n = 3t+1 parties over a completely asynchronous network, tolerating a computationally unbounded Byzantine adversary, who can control at most t parties out of the n parties. The amortized communication complexity of our ABA protocol is O(n^{3} \log \frac{1}{\epsilon}) bits for attaining agreement on a single bit, where \epsilon (\epsilon > 0) denotes the probability of non-termination. We compare our protocol with the best known optimally resilient ABA protocols of Canetti et al.(STOC 1993) and Abraham et al.~(PODC 2008) and show that our protocol gains by a factor of O(n^{8} \log \frac{1}{\epsilon}^{3}) over the ABA protocol of Canetti et al. and by a factor of O(n^{5} \frac{\log{n}}{\log \frac{1}{\epsilon}}) over the ABA protocol of Abraham et al. in terms of the communication complexity. To design our protocol, we first present a new, optimally resilient statistical asynchronous verifiable secret sharing (AVSS) protocol with n = 3t+1, which significantly improves the communication complexity of the only known optimally resilient statistical AVSS protocol of Canetti et al. Our AVSS protocol shares multiple secrets simultaneously and incurs lower communication complexity than executing multiple instances of an AVSS protocol sharing a single secret. To design our AVSS protocol, we further present a new asynchronous primitive called asynchronous weak commitment (AWC), which acts as a substitute for asynchronous weak secret sharing (AWSS), which was used as a primitive for designing AVSS by Canetti et al. We observe that AWC has weaker requirements than the AWSS and hence can be designed more efficiently. The common coin primitive is one of the most important building blocks for the construction of an ABA protocol. The best known common coin protocol of Feldman et al. requires multiple instances of an AVSS protocol sharing a single secret as a black-box. Unfortunately, this common coin protocol does not achieve its goal when the multiple invocations of AVSS sharing a single secret is replaced by a single invocation of an AVSS protocol sharing multiple secrets simultaneously. Therefore in this paper, we extend the existing common coin protocol to make it compatible with our new AVSS protocol (sharing multiple secrets). As a byproduct, our new common coin protocol is much more communication efficient than the existing common coin protocol.

In this work, we propose an algorithm to produce the double-base chains that optimize the time used for computing an elliptic curve cryptosystem. The double-base chains is the representation that combining the binary and ternary representation. By this method, we can reduce the Hamming weight of the expansion, and reduce the time for computing the scalar point multiplication (Q = rS), that is the bottleneck operation of the elliptic curve cryptosystem. This representation is very redundant, i.e. we can present a number by many expansions. Then, we can select the way that makes the operation fastest. However, the previous works on double-bases chain have used a greedy algorithm, and their solutions are not optimized. We propose the algorithm based on the dynamic programming scheme that outputs the optimized the double-bases chain. The experiments show that we have reduced the time for computing the scalar multiplication by 3.88-3.95%, the multi-scalar multiplication by 2.55-4.37%, and the multi-scalar multiplication on the larger digit set by 3.5-12%.

In 2007, the E.U. FP6 SecurIST called for trustworthy international identity management (IdM) that was user-centric. In 2009, the U.S. Department of Homeland Security (DHS) called for trustworthy global-scale IdM and the U.S. National Institute of Standards and Technology (NIST) called for new cryptographic key management (CKM) designs. In this paper we outline the core architecture for (apparently) the first globally scalable, post quantum secure, symmetric key based platform for provisioning IdM, key distribution/agreement and inter-enterprise CKM services. Our proposal employs a decentralised trust model that exploits compartmentalisation, redundancy and diversification simultaneously across service provider, software developer, hardware vendor, class of cryptographic primitive, and protocol axis. It employs behavioural analysis techniques and supports the collaborative management of international name spaces, management of client transactions using public identifiers and supports user-centric cross-cutting control mechanisms. Our proposal is suitable for use with commercial off the shelf hardware and is designed to wrap-around and protect the output of existing security deployments. The platform addresses the U.S. Networking and Information Technology Research and Development Program (NITRD) call to create a digital immune system (multi-layered protection, decentralised control, diversity, pattern recognition), the DHS call for combating insider attacks and malware, achieving survivability and availability, and NIST managers' call for a CKM design supporting billions of users without the use of public key technologies. This proposal has been designed as part of our Trustworthy Resilient Universal Secure Infrastructure Platform project.

Sponge functions were introduced by Bertoni et al. as an alternative to the classical Merkle-Damgaard design. Many hash function submissions to the SHA-3 competition launched by NIST in 2007, such as CubeHash, Fugue, Hamsi, JH, Keccak and Luffa, derive from the original sponge design, and security guarantees from some of these constructions are typically based on indifferentiability results. Although indifferentiability proofs for these designs often bear significant similarities, these have so far been obtained independently for each construction. In this work, we introduce the parazoa family of hash functions as a generalization of ``sponge-like'' functions. Similarly to the sponge design, the parazoa family consists of compression and extraction phases. The parazoa hash functions, however, extend the sponge construction by enabling the use of a wider class of compression and extraction functions that need to satisfy certain properties. More importantly, we prove that the parazoa functions satisfy the indifferentiability notion of Maurer et al. under the assumption that the underlying permutation is ideal. Not surprisingly, our indifferentiability result confirms the bound on the original sponge function, but it also carries over to a wider spectrum of hash functions and eliminates the need for a separate indifferentiability analysis.

Patra et al. gave a necessary and sufficient condition for the possibility of almost perfectly secure message transmission protocols tolerating general, non-threshold Q^2 adversary structure. However, their protocol requires at least three rounds and performs exponential (exponential in the size of the adversary structure) computation and communication. Moreover, they have left it as an open problem to design efficient protocol for almost perfectly secure message transmission, tolerating Q^2 adversary structure. In this paper, we show the first single round almost perfectly secure message transmission protocol tolerating Q^2 adversary structure. The computation and communication complexities of the protocol are both polynomial} in the size of underlying linear secret sharing scheme (LSSS) and adversary structure. This solves the open problem raised by Patra et al.. When we restrict our general protocol to threshold adversary with n=2t+1, we obtain a single round, communication optimal almost secure message transmission protocol tolerating threshold adversary, which is much more computationally efficient and relatively simpler than the previous communication optimal protocol of Srinathan et al.

The increasing use of computing devices for social interactions fuels the proliferation of online social applications, yet prompts a number of privacy concerns. One common problem occurs when two unfamiliar users, in the process of establishing social relationships, want to assess their social proximity by discovering mutual social contacts. In this paper, we introduce \emph{Private Contact Discovery}, a novel cryptographic primitive that lets two users, on input their respective contact lists, learn their common contacts (if any), and nothing else. We present an efficient and provably secure construction, that (i) prevents arbitrary list manipulation by means of contact certification, and (ii) guarantees user authentication and revocability. Following a rigorous cryptographic treatment of the problem, we define \emph{contact-hiding} security and prove it for our solution, under the RSA assumption in the Random Oracle Model (ROM). We also show that other related cryptographic techniques are unsuitable in this context. Experimental analysis on various types of devices attests to the practicality of our technique, which achieves computational and communication overhead almost linear in the number of contacts.

The publish/subscribe model offers a loosely-coupled communication paradigm where applications interact indirectly and asynchronously. Publisher applications generate events that are sent to interested applications through a network of brokers. Subscriber applications express their interest by specifying filters that brokers can use for routing the events. Supporting confidentiality of messages being exchanged is still challenging. First of all, it is desirable that any scheme used for protecting the confidentiality of both the events and filters should not require the publishers and subscribers to share secret keys. In fact, such a restriction is against the loose-coupling of the model. Moreover, such a scheme should not restrict the expressiveness of filters and should allow the broker to perform event filtering to route the events to the interested parties. Existing solutions do not fully address these issues. In this paper, we provide a novel scheme that supports (i) confidentiality for events and filters; (ii) filters can express very complex constraints on events even if brokers are not able to access any information on both events and filters; (iii) and finally it does not require publishers and subscribers to share keys.

Method of secure evaluation of polynomial y=F(x_1, …, x_k) over some rings on untrusted computer is proposed. Two models of untrusted computer are considered: passive and active. In passive model untrusted computer correctly computes polynomial F and tries to know secret input (x_1, …, x_k) and output y. In active model untrusted computer tries to know input and output and tries to change correct output y so that this change cannot be determined. Secure computation is proposed by using one-time privacy ring homomorphism Z/nZ -> Z/nZ[z]/(f(z)), n = pq, generated by trusted computer. In the case of active model secret check point v = F(u_1, …, u_k) is used. Trusted computer generates polynomial f(z)=(z-t)(z+t), t in Z/nZ, and input X_i(z) in Z/nZ[z]/(f(z)) such that X_i(t)=x_i (mod n) for passive model, and f(z)=(z-t_1)(z-t_2)(z-t_3), t_i in Z/nZ and input X_i(z) in Z/nZ[z]/(f(z)) such that X_i(t_1)=x_i (mod n), X_i(t_2)= u_i (mod n) for active model. Untrusted computer computes function Y(z) = F(X_1(z), …, X_k(z)) in the ring Z/nZ[z]/(f(z)). For passive model trusted computer determines secret output y=Y(t) (mod n). For active model trusted computer checks that Y(t_2)=v (mod n), then determines correct output y=Y(t_1) (mod n).

K$\textsc{eccak}$ is one of the five hash functions selected for the final round of the SHA-3 competition and its inner primitive is a permutation called K$\textsc{eccak}$-$f$. In this paper, we find that for the inverse of the only one nonlinear transformation of K$\textsc{eccak}$-$f$, the algebraic degrees of any output coordinate and of the product of any two output coordinates are both 3 and also 2 less than its size 5. Combining the observation with a proposition from an upper bound on the degree of iterated permutations, we improve the zero-sum distinguisher of full 24 rounds K$\textsc{eccak}$-$f$ permutation by lowering the size of the zero-sum partition from $2^{1590}$ to $2^{1579}$.

Signed difference approach was first introduced by Wang for finding collision in MD5. In this paper we introduce ternary difference approach and present it in 3 symbols. To show its application we combine ternary difference approach with conventional differential cryptanalysis and apply that to cryptanalysis the reduced round PRESENT. We also use ant colony technique to obtain the best differential characteristic. To illustrate the privilege in the result of experiment, we calculate advantage of the attack.

Efficient and privacy-preserving constructions for search functionality on encrypted data is important issues for data outsourcing, and data retrieval, etc. Fully secure anonymous Hierarchical ID-Based Encryption (HIBE) schemes is useful primitives that can be applicable to searchable encryptions [4], such as ID-based searchable encryption, temporary searchable encryption [1], and anonymous forward secure HIBE [9]. We propose a fully secure anonymous HIBE scheme with constant size ciphertexts.

We present a new variant of cover and decomposition attacks on the elliptic curve discrete logarithm problem, that combines Weil descent and decomposition-based index calculus into a single discrete logarithm algorithm. This variant applies, at least theoretically, to all composite degree extension fields, and is particularly well-suited for curves defined over $\F_{p^6}$. We give a real-size example of discrete logarithm computations on a seemingly secure curve defined over a 130$-bit degree $6$ extension field.

In this paper, we analyze collision resistance of the JH hash function in the ideal primitive model. The JH hash function is one of the five SHA-3 candidates accepted for the final round of evaluation. The JH hash function uses a mode of operation based on a permutation, while its security has been elusive even in the random permutation model. One can find a collision for the JH compression function only with two backward queries to the basing primitive. However, the security is significantly enhanced in iteration. For $c\leq n/2$, we prove that the JH hash function using an ideal $n$-bit permutation and producing $c$-bit outputs by truncation is collision resistant up to $O(2^{c/2})$ queries. This bound implies that the JH hash function provides the optimal collision resistance in the random permutation model.

We construct the first homomorphic signature scheme that is capable of evaluating multivariate polynomials on signed data. Given the public key and a signed data set, there is an efficient algorithm to produce a signature on the mean, standard deviation, and other statistics of the signed data. Previous systems for computing on signed data could only handle linear operations. For polynomials of constant degree, the length of a derived signature only depends logarithmically on the size of the data set. Our system uses ideal lattices in a way that is a ``signature analogue'' of Gentry's fully homomorphic encryption. Security is based on hard problems on ideal lattices similar to those in Gentry's system.

Camellia is a block cipher selected as a standard by ISO/IEC, which has been analyzed by a number of cryptanalysts. In this paper, we propose several 6-round impossible differential paths of Camellia with the $FL/FL^{-1}$ layer in the middle of them. With the impossible differential and a well-organized precomputational table, impossible differential attacks on 10-round Camellia-192 and 11-round Camellia-256 are given, and the time complexity are $2^{175}$ and $2^{206.8}$ respectively. An impossible differential attack on 15-round Camellia-256 without $FL/FL^{-1}$ layers and whitening is also be given, which needs about $2^{236.1}$ encryptions. To the best of our knowledge, these are the best cryptanalytic results of Camellia-192/-256 with $FL/FL^{-1}$ layers and Camellia-256 without $FL/FL^{-1}$ layers to date.

As medical records are converted to electronic form, risks of compromise of patients' privacy increase dramatically. The electronic format makes misuse of many patients' data much easier, so we must be extremely careful with who has access to this data. At the same time, this move to an electronic approach also gives us opportunities to improve patient privacy by leveraging recent cryptographic techniques, and in some ways to improve upon the traditional system. Here we look in particular at those parties, such as insurers and pharmacies, that are not actively involved in patient care. Currently patients who are insured are required to share the entire record of their medical treatment with their insurer in order to receive benefits, and a pharmacy may store all prescriptions filled for each patient. However, there is no medical reason for these parties to see this information --- they only need enough information to be able to prevent fraud and verify that the provided treatment should be covered under the patient's policy, or that the patient has a valid prescription for the medication being dispensed. We argue that, using recent developments in cryptography, we can allow this verification without revealing any additional information about the patient's record, thus obtaining optimal privacy guarantees.

The problem of unconditionally reliable message transmission (URMT) is to design a protocol which when run by players in a network enables a sender S to deliver a message to a receiver R with high probability, even when some players in the network are under the control of an unbounded adversary. Renault and Tomala [JoC2008] gave a characterization of undirected neighbour networks over which URMT tolerating Byzantine adversary is possible. In this paper, we generalize their result to the case of directed networks.

We study the problem of information-theoretically secure message transmission (SMT) in asynchronous directed networks. In line with the literature, the distrust and failures of the network is captured via a computationally unbounded Byzantine adversary that may corrupt some subset of nodes. We give a characterization of networks over which SMT from sender S to receiver R is possible in both the well-known settings, namely perfect SMT (PSMT) and unconditional SMT (USMT). We distinguish between two variants of USMT: one in which R can output an incorrect message (with small probability) and another in which R never outputs a wrong message, but may choose to abort (with small probability). We also provide efficient protocols for an important class of networks.

A non-interactive zero-knowledge proof can be used to demonstrate the truth of a statement without revealing anything else. It has been shown under standard cryptographic assumptions that non-interactive zero-knowledge proofs of membership exist for all languages in NP. However, known non-interactive zero-knowledge proofs of membership of NP-languages yield proofs that are larger than the corresponding membership witnesses. We investigate the question of minimizing the communication overhead involved in making non-interactive zero-knowledge proofs and show that if fully homomorphic encryption exists then it is possible to minimize the size of non-interactive zero-knowledge proofs and get proofs that are of the same size as the witnesses. Our technique is applicable to many types of non-interactive zero-knowledge proofs. We apply it to both standard non-interactive zero-knowledge proofs and to universally composable non-interactive zero-knowledge proofs. The technique can also be applied outside the realm of non-interactive zero-knowledge proofs, for instance to get witness-size interactive zero-knowledge proofs in the plain model without any setup.

What does it mean for an encryption scheme to be leakage-resilient Prior formulations require that the scheme remains semantically secure even in the presence of leakage, but only considered leakage that occurs \emph{before the challenge ciphertext is generated}. Although seemingly necessary, this restriction severely limits the usefulness of the resulting notion. In this work we study after-the-fact leakage, namely leakage that the adversary obtains after seeing the challenge ciphertext. We seek a ``natural'' and realizable notion of security, which is usable in higher-level protocols and applications. To this end, we formulate \emph{entropic leakage-resilient PKE}. This notion captures the intuition that as long as the entropy of the encrypted message is higher than the amount of leakage, the message still has some (pseudo) entropy left. We show that this notion is realized by the Naor-Segev constructions (using hash proof systems). We demonstrate that entropic leakage-resilience is useful by showing a simple construction that uses it to get semantic security in the presence of after-the-fact leakage, in a model of bounded memory leakage from a split state.

We consider the problem of encrypting structured data (e.g., a web graph or a social network) in such a way that it can be efficiently and privately queried. For this purpose, we introduce the notion of structured encryption which generalizes previous work on symmetric searchable encryption (SSE) to the setting of arbitrarily-structured data. In the context of cloud storage, structured encryption allows a client to encrypt data without losing the ability to query and retrieve it efficiently. Another application, which we introduce in this work, is to the problem of controlled disclosure, where a data owner wishes to grant access to only part of a massive dataset. We propose a model for structured encryption, a formal security definition and several efficient constructions. We present schemes for performing queries on two simple types of structured data, specifically lookup queries on matrix-structured data, and search queries on labeled data. We then show how these can be used to construct efficient schemes for encrypting graph data while allowing for efficient neighbor and adjacency queries. Finally, we consider data that exhibits a more complex structure such as labeled graph data (e.g., web graphs). We show how to encrypt this type of data in order to perform focused subgraph queries, which are used in several web search algorithms. Our construction is based on our labeled data and basic graph encryption schemes and provides insight into how several simpler algorithms can be combined to generate an efficient scheme for more complex queries.

In 2010, Groth constructed the only previously known sublinear-communication NIZK circuit satisfiability argument in the common reference string model. We optimize Groth's argument by, in particular, reducing both the CRS length and the prover's computational complexity from quadratic to quasilinear in the circuit size. We also use a (presumably) weaker security assumption, and have tighter security reductions. Our main contribution is to show that the complexity of Groth's basic arguments is dominated by the quadratic number of monomials in certain polynomials. We collapse the number of monomials to quasilinear by using a recent construction of progression-free sets.

It is clear that the negation map can be used to speed up the computation of elliptic curve discrete logarithms with the Pollard rho method. However, the random walks defined on elliptic curve points equivalence class $\{\pm P\}$ used by Pollard rho will always get trapped in fruitless cycles. We propose an efficient alternative approach to resolve fruitless cycles. Besides the theoretical analysis, we also examine the performance of the new algorithm in experiments with elliptic curve groups. The experiment results show that we can achieve the speedup by a factor extremely close to $\sqrt{2}$, which is the best performance one can achieve in theory, using the new algorithm with the negation map.

KISS (`Keep it Simple Stupid') is an efficient pseudo-random number generator specified by G. Marsaglia and A. Zaman in 1993. G. Marsaglia in 1998 posted a C version to various USENET newsgroups, including \texttt{sci.crypt}. Marsaglia himself has never claimed cryptographic security for the KISS generator, but many others have made the intellectual leap and claimed that it is of cryptographic quality. In this paper we show a number of reasons why the generator does not meet the KISS authors' claims, why it is not suitable for use as a stream cipher, and that it is not cryptographically secure. Our best attack requires about 70 words of generated output and a few hours of computation to recover the initial state.

In 2-party secure computation, access to common, trusted randomness is a fundamental primitive. It is widely employed in the setting of computationally bounded players (under various complexity assumptions) to great advantage. In this work we seek to understand the power of trusted randomness, primarily in the computationally unbounded (or information theoretic) setting. We show that a source of common randomness does not add any additional power for secure evaluation of deterministic functions, even when one of the parties has arbitrary influence over the distribution of the common randomness. Further, common randomness helps only in a trivial sense for realizing randomized functions too (namely, it only allows for sampling from publicly fixed distributions), if UC security is required. To obtain these impossibility results, we employ a recently developed protocol analysis technique, which we call the {\em frontier analysis}. This involves analyzing carefully defined ``frontiers'' in a weighted tree induced by the protocol's execution (or executions, with various inputs), and establishing various properties regarding one or more such frontiers. We demonstrate the versatility of this technique by employing carefully chosen frontiers to derive the different results. To analyze randomized functionalities we introduce a frontier argument that involves a geometric analysis of the space of probability distributions. Finally, we relate our results to computational intractability questions. We give an equivalent formulation of the ``cryptomania assumption'' (that there is a semi-honest or standalone secure oblivious transfer protocol) in terms of UC-secure reduction among randomized functionalities. Also, we provide an {\em unconditional result} on the uselessness of common randomness, even in the computationally bounded setting. Our results make significant progress towards understanding the exact power of shared randomness in cryptography. To the best of our knowledge, our results are the first to comprehensively characterize the power of large classes of randomized functionalities.

In the area of privacy-preserving data mining, a differentially private mechanism intuitively encourages people to share their data because they are at little risk of revealing their own information. However, we argue that this interpretation is incomplete because external incentives are necessary for people to participate in databases, and so data release mechanisms should not only be differentially private but also compatible with incentives, otherwise the data collected may be false. We apply the notion of \emph{truthfulness} from game theory to this problem. In certain settings, it turns out that existing differentially private mechanisms do not encourage participants to report their information truthfully. On the positive side, we exhibit a transformation that takes truthful mechanisms and transforms them into differentially private mechanisms that remain truthful. Our transformation applies to games where the type space is small and the goal is to optimize an insensitive quantity such as social welfare. Our transformation incurs only a small additive loss in optimality, and it is computationally efficient. Combined with the VCG mechanism, our transformation implies that there exists a differentially private, truthful, and approximately efficient mechanism for any social welfare game with small type space. We also study a model where an explicit numerical cost is assigned to the information leaked by a mechanism. We show that in this case, even differential privacy may not be strong enough of a notion to motivate people to participate truthfully. We show that mechanisms that release a perturbed histogram of the database may reveal too much information. We also show that, in general, any mechanism that outputs a synopsis that resembles the original database (such as the mechanism of Blum et al. (STOC '08)) may reveal too much information.

We describe a space-efficient algorithm for solving a generalization of the subset sum problem in a finite group G, using a Pollard-rho approach. Given an element z and a sequence of elements S, our algorithm attempts to find a subsequence of S whose product in G is equal to z. For a random sequence S of length d*log2(n), where n=#G and d>=2 is a constant, we find that its expected running time is O(sqrt(n)*log(n)) group operations (we give a rigorous proof for d>4), and it only needs to store O(1) group elements. We consider applications to class groups of imaginary quadratic fields, and to finding isogenies between elliptic curves over a finite field.

Bos, Kaihara, Kleinjung, Lenstra, and Montgomery recently showed that ECDLPs on the 112-bit secp112r1 curve can be solved in an expected time of 65 years on a PlayStation 3. This paper shows how to solve the same ECDLPs at almost twice the speed on the same hardware. The improvement comes primarily from a new variant of Pollard's rho method that fully exploits the negation map without branching, and secondarily from improved techniques for modular arithmetic.

There are protocols to privately evaluate any function in the honest-but-curious setting assuming that the honest nodes are in majority. For some specific functions, protocols are known which remain secure even without an honest majority. The seminal work by Chor and Kushilevitz [CK91] gave a complete characterization of Boolean functions, showing that each Boolean function either requires an honest majority, or is such that it can be privately evaluated regardless of the number of colluding nodes. The problem of discovering the threshold for secure evaluation of more general functions remains an open problem. Towards a resolution, we provide a complete characterization of the security threshold for functions with three different outputs. Surprisingly, the zero-one law for Boolean functions extends to Z_3, meaning that each function with range Z_3 either requires honest majority or tolerates up to $n$ colluding nodes.

We present two practical frameworks for $h$-out-of-$n$ oblivious transfer ($OT^{n}_{h}$). The first one is secure against covert adversaries who are not always willing to cheat at any price. The security is proven under the ideal/real simulation paradigm (call such security fully simulatable security). The second one is secure against malicious adversaries who are always willing to cheat. It provides fully simulatable security and privacy respectively for the sender and the receiver (call such security one-sided simulatable security). The two frameworks can be implemented from the decisional Diffie-Hellman (DDH) assumption, the decisional $N$-th residuosity assumption, the decisional quadratic residuosity assumption and so on. The DDH-based instantiation of our first framework costs the minimum communication rounds and the minimum computational overhead, compared with existing practical protocols for oblivious transfer with fully simulatable security against covert adversaries or malicious adversaries. Though our second framework is not efficient, compared with existing practical protocols with one-sided simulatable security against malicious adversaries. However, it first provides a way to deal with general $OT^{n}_{h}$ on this security level. What is more, its DDH-based instantiation is more efficient than the existing practical protocols for oblivious transfer with fully simulatable security against malicious adversaries.