We study the problem of securely extending the domain of a collision resistant compression function. A new construction based on directed acyclic graphs is described. This generalizes the usual iterated hashing constructions. Our main contribution is to introduce a new technique for hashing arbitrary length strings. Combined with DAG based hashing, this technique gives a new hashing algorithm. The amount of padding and the number of invocations of the compression function required by the new algorithm is smaller than the general \MD algorithm. Lastly, we describe the design of a new parallel hash algorithm.

Almost resilient function is the generalization of resilient function and have important applications in multiple authenticate codes and almost security cryptographic Boolean functions.In this paper,some secondary constructions are provided.In particular, the theorem $3$ in {\cite {ke}} is improved. As $\varepsilon $-almost$(n,1,k)$-CI functions plays an important role in the secondary constructions, we concluded some properties and constructions. Specially we presented a spectrum characterization of balanced almost CI function, which can be used to identify a balanced almost CI function by computing its walsh spectra.

In the presence of economic globalization joint venture is one of the most common and effective means of conducting business internationally. By building joint ventures companies form strategic alliances that help them to enter new economic markets and further their business goals in a cooperative effort without loosing own independence. Upon building a joint venture company, two or more "parent" companies agree to share capital, technology, human ressources, risks and rewards in a formation of a new entity under shared control by a "board of directors", which consists of representatives of "parent" companies. The establishment of such shared control is tricky and relies generally on the "trust, but verify" relationship, i.e., companies trust the information they receive from prospective partners, but it is a good business practice to verify the facts. In this paper we focus on the issue of the shared financial control in a joint venture. We consider the mostly preferred form of the control where every member of the board is able to issue payment orders on behalf of the joint venture, but at the same time representatives of other companies, should be able to monitor the accounting to achieve fairness in the spending of shared funds. For this form of the shared control we propose a new secure group-oriented signature scheme, called a {\it democratic group signature} scheme, which results from the modification of the standard notion of group signatures by eliminating the role of the group manager. We also show that existing schemes, e.g., ring and group signatures, cannot be used to realize the required shared control based on the "trust, but verify" relationship.

Given a corrupted word $\w = (w_1, \ldots, w_n)$ from a Reed-Solomon code of distance $d$, there are many ways to efficiently find and correct its errors. But what if we are instead given $(g^{w_1}, \ldots, g^{w_n})$ where $g$ generates some large cyclic group --- can the errors still be corrected efficiently? This problem is called \emph{error correction in the exponent}, and though it arises naturally in many areas of cryptography, it has received little attention. We first show that \emph{unique decoding} and \emph{list decoding} in the exponent are no harder than the computational Diffie-Hellman (CDH) problem in the same group. The remainder of our results are negative: * Under mild assumptions on the parameters, we show that \emph{bounded-distance decoding} in the exponent, under $e=d-k^{1-\epsilon}$ errors for any $\epsilon > 0$, is as hard as the discrete logarithm problem in the same group. * For \emph{generic} algorithms (as defined by Shoup, Eurocrypt 1997) that treat the group as a ``black-box,'' we show lower bounds for decoding that exactly match known algorithms. Our generic lower bounds also extend to decisional variants of the decoding problem, and to groups in which the decisional Diffie-Hellman (DDH) problem is easy. This suggests that hardness of decoding in the exponent is a qualitatively new assumption that lies ``between'' the DDH and CDH assumptions.

Mercurial commitments were introduced by Chase et al. (Eurocrypt 2005) and form a key building block for constructing zero-knowledge sets (introduced by Micali, Rabin and Kilian (FOCS'03)}). Unlike regular commitments, which are strictly binding, mercurial commitments allow for certain amount of (limited) freedom. The notion of Chase et al. also required that mercurial commitments should be equivocable given a certain trapdoor, although the notion is interesting even without this condition. While trivially implying regular (trapdoor) commitments, it was not clear from the prior work if the converse was true: Chase et al. gave several constructions of mercurial commitments from various incompatible assumptions, leaving open if they can be built from any (trapdoor) commitment scheme, and, in particular, from any one-way function. We give an affirmative answer to this question, by giving two simple constructions of mercurial commitments from any trapdoor bit commitment scheme. By plugging in various (trapdoor) bit commitment schemes, we get *all* the efficient constructions from Chase et al. and Micali et al., as well as several immediate new constructions. Our results imply that (a) ** mercurial commitments can be viewed as surprisingly simple variations of regular (trapdoor) commitments ** (and, thus, can be built from one-way functions and, more efficiently, from a variety of other assumptions); and (b) ** the existence of zero-knowledge sets is equivalent to the existence of collision-resistant hash functions ** (moreover, the former can be efficiently built from the latter and trapdoor commitments). Of independent interest, we also give a stronger and yet much simpler definition of mercurial commitments than that of Chase et al. (which is also met by our constructions). Overall, we believe that our results eludicate the notion of mercurial commitments, and better explain the rational following the previous constructions of mercurial commitments.

This work is motivated by the observation that the function $\F{m}$ to $\F{m}$ defined by $x^d+(x+1)^d+a$ for some $a\in \F{m}$ can be used to construct difference sets. A desired condition is, that the function $\varphi _d(x):=x^d+(x+1)^d$ is a $2^s$-to-1 mapping. If $s=1$, then the function $x^d$ has to be APN. If $s>1$, then there is up to equivalence only one function known: The function $\varphi _d$ is a $2^s$-to-1 mapping if $d$ is the Gold parameter $d=2^k+1$ with $\gcd (k,m)=s$. We show in this paper, that $\varphi _d$ is also a $2^s$-to-1 mapping if $d$ is the Kasami parameter $d=2^{2k}-2^k+1$ with $\gcd (k,m)=s$ and $m/s$ odd. We hope, that this observation can be used to construct more difference sets.

In the context of Universal Composability, we introduce the concept of universal environments and simulators. Then, Universal Composability is equivalent to Universal Composability wrt. universal environments and simulators. We prove the existence of universal environments and simulators and investigate their computational complexity. From this, we get a number of consequences: First, we see that for polynomial-time protocols, exponential adversarial entities are as powerful as unlimited ones. Further, for a large class of protocols (those with bounded communication-complexity) we can show that UC and specialised-simulator UC coincide in the case of statistical security, i.e., that it is does not matter whether the simulator is chosen in dependence of the environment or not. This also implies that for the Universal Composition Theorem for polynomial-time protocols specialised-simulator UC is sufficient. This result is the last piece needed to find all implications and non-implications between the notions of UC, specialised-simulator UC, O(1)-bounded and polynomially-bounded general composability for polynomial-time protocols in the cases of perfect, statistical and polynomial security. Finally, we introduce the notion of bounded-risk UC, which allows to give explicit security guarantees for concrete security parameters and show that in the above case also this variant coincides with UC.

One-way hash algorithms are an indispensable tool in data security. Over the last decade or so a number of one-way hash algorithms have been designed and many of them have been used in numerous applications. Recent progress in cryptanalytic attacks on one-way hash algorithms by Wang and co-workers, however, has brought up the urgency of research into new and more secure algorithms. The goal of this paper is two-folded. On one hand we propose a simple technique to affix authentication tags to messages prior to being hashed by an iterative one-way hash algorithm with the aim of increasing the overall security of the algorithm against cryptanalytic attacks. One the other hand we advocate the importance of a system oriented approach towards the design and deployment of new families of one-way hash algorithms that support greater scalability and facilitate migration to newer member algorithms upon the compromise of deployed ones. We base our observations on a common sense premise that there is no specific one-way hash algorithm can remain secure forever and it will eventually be broken by a cryptanalytic attack faster than exhaustive research.

Non-Adjacent Form (NAF) is a canonical form of signed binary representation of integers. We present some explicit formulae of NAF and its left-to-right analogue (FAN) for randomly chosen n-bit integers. Interestingly, we prove that the zero-run length appeared in FAN is asymptotically 16/7, which is longer than that of the standard NAF. We also apply the proposed formulae to the speed estimation of elliptic curve cryptosystems.

By walsh transform, autocorrelation function, decomposition, derivation and modification of truth table, some new invariants are obtained. Based on invariant theory, we get two results: first a general algorithm which can be used to judge if two boolean functions are affinely equivalent and to obtain the affine equivalence relationship if they are equivalent. For example, all 8-variable homogenous bent functions of degree 3 are classified into 2 classes; second, the classification of the Reed-Muller code $R(4,6)/R(1,6),R(3,7)/R(1,7),$ which can be used to almost enumeration of 8-variable bent functions.

We exhibit an infinite class of almost perfect nonlinear quadratic polynomials from $\mathbb{F}_{2^n}$ to $\mathbb{F}_{2^n}$ ($n\geq 12$, $n$ divisible by 3 but not by 9). We prove that these functions are EA-inequivalent to any power function. In the forthcoming version of the present paper we will proof that these functions are CCZ-inequivalent to any Gold function and to any Kasami function, in particular for $n=12$, they are therefore CCZ-inequivalent to power functions.

We give two applications of Nisan--Wigderson-type ("non-cryptographic") pseudorandom generators in cryptography. Specifically, assuming the existence of an appropriate NW-type generator, we construct: A one-message witness-indistinguishable proof system for every language in NP, based on any trapdoor permutation. This proof system does not assume a shared random string or any setup assumption, so it is actually an "NP proof system." A noninteractive bit commitment scheme based on any one-way function. The specific NW-type generator we need is a hitting set generator fooling nondeterministic circuits. It is known how to construct such a generator if ETIME = DTIME(2^O(n)) has a function of nondeterministic circuit complexity 2^\Omega(n) (Miltersen and Vinodchandran, FOCS `99). Our witness-indistinguishable proofs are obtained by using the NW-type generator to derandomize the ZAPs of Dwork and Naor (FOCS `00). To our knowledge, this is the first construction of an NP proof system achieving a secrecy property. Our commitment scheme is obtained by derandomizing the interactive commitment scheme of Naor (J. Cryptology, 1991). Previous constructions of noninteractive commitment schemes were only known under incomparable assumptions.

In this paper we propose a definition and construction of a new family of one-way candidate functions ${\cal R}_N:Q^N \rightarrow Q^N$, where $Q=\{0,1,\ldots,s-1\}$ is an alphabet with $s$ elements. Special instances of these functions can have the additional property to be permutations (i.e. one-way permutations). These one-way functions have the property that for achieving the security level of $2^n$ computations in order to invert them, only $n$ bits of input are needed. The construction is based on quasigroup string transformations. Since quasigroups in general do not have algebraic properties such as associativity, commutativity, neutral elements, inverting these functions seems to require exponentially many readings from the lookup table that defines them (a Latin Square) in order to check the satisfiability for the initial conditions, thus making them natural candidates for one-way functions.

In order to design bent functions, evolutionary algorithm based on truth table, algebraic normal form or Walsh spectra are already known. Evolutionary algorithm based on trace function form is not known to authors' knowledge. In this paper, we give an evolutionary algorithm based on the trace representation of boolean function. With the algorithm, we constructed many bent functions and made some analysis work. First we observe that all 4 affinely inequivalent bent classes in 6-variable can be written as the linear sum of 2 or 3 monomial trace functions. We make a conclusion that affine transform can be used to change the linear span, which lead to a method constructing perfect nonlinear s-box of non-Niho type; Second, we find that some exponents take more chances to construct bent functions while some exponents take less. By this observation, we give each exponent a cost function, which make our algorithm more efficient than exhaustive searching algorithm or random algorithm. This is also the advantage over the algorithms based on the algebraic normal form, truth table, or Walsh spectra because we don't know what kinds of algebraic normal form, truth table, Walsh spectra are more possible to be used to construct bent functions; Third, we classify the obtained bent functions into affinely inequivalent classes and the number of classes is reported.

A fundamental result in cryptography is that a digital signature scheme can be constructed from an arbitrary one-way function. A proof of this somewhat surprising statement follows from two results: first, Naor and Yung defined the notion of universal one-way hash functions and showed that the existence of such hash functions implies the existence of secure digital signature schemes. Subsequently, Rompel showed that universal one-way hash functions could be constructed from arbitrary one-way functions. Unfortunately, despite the importance of the result, a complete proof of the latter claim has never been published. In fact, a careful reading of Rompel's original conference publication reveals a number of errors in many of his arguments which have (seemingly) never been addressed. We provide here what is --- as far as we know --- the first complete write-up of Rompel's proof that universal one-way hash functions can be constructed from arbitrary one-way functions.

Identity Based Encryption (IBE) has attracted a lot of attention since the publication of the scheme by Boneh and Franklin. So far, only indistinguishability based security notions have been considered in the literature, and it has not been investigated whether these definitions are appropriate. For this purpose, we define the goals of semantic security and non-malleability for IBE. We then compare the security notions resulting from combining those goals with the attacks previously considered in the literature (full and selective-identity attacks), providing either an implication or a separation. Remarkably, we show that the strongest security levels with respect to selective-identity attacks (i.e. chosen-ciphertext security) do not imply the weakest full-identity security level (i.e. one-wayness). With the aim of comprehensiveness, notions of security for IBE in the context of encryption of multiple messages and/or to multiple receivers are finally presented, as well as their relationship with the standard IBE security notion. The results obtained substantiate indistinguishability against full-identity chosen ciphertext attacks as the appropriate security notion for IBE.

Non-interactive zero-knowledge (NIZK) systems are fundamental cryptographic primitives used in many constructions, including CCA2-secure cryptosystems, digital signatures, and various cryptographic protocols. What makes them especially attractive, is that they work equally well in a concurrent setting, which is notoriously hard for interactive zero-knowledge protocols. However, while for interactive zero-knowledge we know how to construct statistical zero-knowledge argument systems for all NP languages, for non-interactive zero-knowledge, this problem remained open since the inception of NIZK in the late 1980's. Here we resolve two problems regarding NIZK: - we construct the first perfect NIZK argument system for any NP language. - we construct the first UC-secure NIZK protocols for any NP language in the presence of a dynamic/adaptive adversary. While it was already known how to construct efficient prover computational NIZK proofs for any NP language, the known techniques yield large common reference strings and large NIZK proofs. As an additional implication of our techniques, we considerably reduce both the size of the common reference string and the size of the proofs.

We provide unconditional constructions of concurrent statistical zero-knowledge proofs for a variety of non-trivial problems (not known to have probabilistic polynomial-time algorithms). The problems include Graph Isomorphism, Graph Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a restricted version of Statistical Difference, and approximate versions of the (coNP forms of the) Shortest Vector Problem and Closest Vector Problem in lattices. For some of the problems, such as Graph Isomorphism and Quadratic Residuosity, the proof systems have provers that can be implemented in polynomial time (given an NP witness) and have \tilde{O}(log n) rounds, which is known to be essentially optimal for black-box simulation. To our best of knowledge, these are the first constructions of concurrent zero-knowledge protocols in the asynchronous model (without timing assumptions) that do not require complexity assumptions (such as the existence of one-way functions).

Identity based encryption (IBE) schemes have been flourishing since the very beginning of this century. In IBE it is widely believed that proving the security of a scheme in the sense of IND-ID-CCA2 is sufficient to claim the scheme is also secure in the senses of both SS-ID-CCA2 and NM-ID-CCA2. The justification for this belief is the relations among indistinguishability (IND), semantic security (SS) and non-malleability (NM). But these relations are proved only for conventional public key encryption (PKE) schemes in historical works. The fact is that between IBE and PKE, there exists a difference of special importance, i.e. only in IBE the adversaries can perform a particular attack, namely the chosen identity attack. This paper shows that security proved in the sense of IND-ID-CCA2 is validly sufficient for implying security in any other sense in IBE. This is to say the security notion, IND-ID-CCA2, captures the essence of security for all IBE schemes. To achieve this intention, we first describe formal definitions of the notions of security for IBE, and then present the relations among IND, SS and NM in IBE, along with rigorous proofs. All of these results are proposed with the consideration of the chosen identity attack.

The abstraction of cryptographic operations by term algebras, called Dolev-Yao models, is essential in almost all tool-supported methods for proving security protocols. Recently significant progress was made in proving that such abstractions can be sound with respect to actual cryptographic realizations and security definitions. The strongest results show this in the sense of reactive simulatability/UC, a notion that essentially means retention of arbitrary security properties under arbitrary active attacks and in arbitrary protocol environments, with only small changes to both abstractions and natural implementations. However, these results are so far restricted to cryptographic systems like encryption and signatures which essentially only have constructors and destructors, but no further algebraic properties. Typical modern tools and complexity results around Dolev-Yao models also allow more algebraic operations. The first such operation considered is typically XOR because of its clear structure and cryptographic usefulness. We show that it is impossible to extend the strong soundness results to XOR, at least not with remotely the same generality and naturalness as for the core cryptographic systems. On the positive side, we show the soundness of an XOR model and realization under passive attacks.

The Ideal-Cipher Model of a blockcipher is a well-known and widely-used model dating back to Shannon and has seen frequent use in proving the security of various cryptographic objects and protocols. But very little discussion has transpired regarding the meaning of proofs conducted in this model or regarding the model's validity. In this paper, we briefly discuss the implications of proofs done in the ideal-cipher model, then show some limitations of the model analogous to recent work regarding the Random-Oracle Model. In particular, we extend work by Canetti, Goldreich and Halevi, and a recent simplification by Maurer, Renner, and Holenstein, to exhibit a blockcipher-based hash function that is provably-secure in the ideal-cipher model but trivially insecure when instantiated by any blockcipher.

To protect copyrighted digital data against piracy, codes with different secure properties such as frameproof codes, secure frameproof codes, codes with identifiable parent property (IPP codes), traceability codes (TA codes) are introduced. In this paper, we study these codes together with related combinatorial objects called separating and perfect hash families. We introduce for the first time the notion of difference function families and use these difference function families to give generalized recursive techniques that can be used for any kind of secure codes and hash families. We show that some previous recursive techniques are special cases of these new techniques.

We prove that for $d>1$ the information rate of the perfect secret sharing scheme based on the edge set of the $d$-dimensional cube is exactly $2/d$. Using the technique developed, we also prove that the information rate of the infinite $d$-dimensional lattice is $1/d$.

We study pseudorandom generator (PRG) constructions G^f : {0,1}^l -> {0,1}^{l+s} from one-way functions f : {0,1}^n \to {0,1}^m. We consider PRG constructions of the form G^f(x) = C(f(q_{1}) ... f(q_{poly(n)})) where C is a polynomial-size constant depth circuit (i.e. AC^0) and C and the q's are generated from x arbitrarily. We show that every black-box PRG construction of this form must have stretch s bounded as s < l ( log^{O(1)} n)/ m + O(1) = o(l). This holds even if the PRG construction starts from a one-to-one function f : {0,1}^n \to {0,1}^m where m < 5n. This shows that either adaptive queries or sequential computation are necessary for black-box PRG constructions with constant factor stretch (i.e. s = \Omega(l)) from one-way functions, even if the functions are one-to-one. On the positive side we show that if there is a one-way function f : {0,1}^n \to {0,1}^m that is regular (i.e. the number of preimages of f(x) depends on |x| but not on x) and computable by polynomial-size constant depth circuits then there is a PRG : {0,1}^l \to {0,1}^{l+1} computable by polynomial-size constant depth circuits. This complements our negative result above because one-to-one functions are regular. We also study constructions of average-case hard functions starting from worst-case hard ones, i.e. hardness amplifications. We show that if there is an oracle procedure Amp^f in the polynomial time hierarchy (PH) such that Amp^f is average-case hard for every worst-case hard f, then there is an average-case hard function in PH \emph{unconditionally}. Bogdanov and Trevisan (FOCS '03) and Viola (CCC'03) show related but incomparable negative results.

In this paper we propose a new class of cryptosystems that utilizes metric continuity. The geometric cryptosystem considered in this paper as the main example of metric cryptosystems has a number of interesting properties such as resistance to several basic cryptographic attacks, efficiency and detection of transmission errors.

A secure sketch is a set of published data that can help to recover the original biometric data after they are corrupted by permissible noises, and by itself does not reveal much information about the original. Several constructions have been proposed for different metrics, and in particular, set difference. We observe that in many promising applications, set difference alone is insufficient to model the noises. We propose to look into point-set difference, which measures noises that not only remove/introduce new feature points in the biometric objects, but may also perturb the points. In this paper, we first give an improvement for set difference construction that can be extended to multi-sets, where the sketch is small and there is an efficient decoding algorithm. We next give a sketch for point-set difference in both one and two-dimensional spaces. By using results in almost k-wise independence, the size of the sketch is reduced to near-optimal.

In this paper we will extend the Benes and Luby-Rackoff constructions to design various pseudo-random functions and pseudo-random permutations with near optimal information-theoretic properties. An example of application is when Alice wants to transmit to Bob some messages against Charlie, an adversary with unlimited computing power, when Charlie can receive only a percentage $\tau$ of the transmitted bits. By using Benes, Luby-Rackoff iterations, concatenations and fixing at 0 some values, we will show in this paper how to design near optimal pseudo-random functions for all values of $\tau$. Moreover we will show how to design near optimal pseudo-random permutations when $\tau$ can have any value such that the number of bits obtained by Charlie is smaller than the square root of all the transmitted bits.

In this paper we discuss the example of APN permutation introduced in the paper ``On the Generalized Linear Equivalence of Functions over Finite Fields'', presented at Asiacrypt 2004. We show that the permutation given there is indeed classically linearly equivalent to a power monomial. More in general, we show that no new class of APN functions can be discovered starting from permutation polynomials of the type used in the paper, and applied on the APN monomial $x^3$.

We prove a general domain extension theorem for pseudo-random functions (PRFs). Given a PRF $F$ from $n$ bits to $n$ bits, it is well known that employing $F$ in a chaining mode (CBC-MAC) yields a PRF on the bigger domain. Viewing each application of $F$ in this chaining mode to be a node in a graph, and the chaining as the edges between the nodes, the resulting graph is just a line graph. In this paper, we show that the underlying graph can be an arbitrary directed acyclic graph (DAG), and the resulting function on the larger domain is still a PRF. The only requirement on the graph is that it have unique source and sink nodes, and no two nodes have the same set of incident nodes. A new highly parallelizable MAC construction follows which has a critical path of only $3+\log ^{*} n $ applications of $F$.\\ \hspace*{0.1in} If we allow Galois field arithmetic, we can consider edge colored DAGs, where the colors represent multiplication in the field by the color number. We prove an even more general theorem, where the only restriction on the colored DAGs is that if two nodes ($u$ and $v$) have the same set of incident nodes $W$, then at least one $w$ in $W$ is incident on $u$ and $v$ with a different colored edge. PMAC (parallelizable message authentication \cite{black}) is a simple example of such graphs. The general thoerem allows one to have further optimizations over PMAC, and many modes which deal with variable lengths.

We present a new primitive--Append-only Signatures (AOS)--with the property that any party given an AOS signature aossig[M_1] on message M_1 can compute aossig[M_1||M_2] for any message M_2, where M_1||M_2 is the concatenation of M_1 and M_2. We define the security of AOS, present concrete AOS schemes, and prove their security under standard assumptions. In addition, we find that despite its simple definition, AOS is equivalent to Hierarchical Identity-based Signatures (HIBS) through efficient and security-preserving reductions. Finally, we show direct applications of AOS to problems in network security. Our investigations indicate that AOS is both useful in practical applications and worthy of further study as a cryptographic primitive.

Providing anonymity support for peer-to-peer (P2P) overlay networks is critical. Otherwise, potential privacy attacks (e.g., network address traceback) may deter a storage source from providing the needed data. In this paper we use this practical application scenario to verify our observation that network-based anonymity can be modeled as a complexity based cryptographic problem. We show that, if the routing process between senders and recipients can be modeled as abstract entities, network-based anonymity becomes an analogy of cryptography. In particular, perfect anonymity facing an unbounded traffic analyst corresponds to Shannon's perfect secrecy facing an unbounded cryptanalyst. More importantly, in this paper we propose Probabilistic Polynomial Route (PPR) model, which is a new polynomially-bounded anonymity model corresponding to the Probabilistic Polynomial Time (PPT) model in cryptography. Afterwards, network-based anonymity attacks are with no exception in BPP. This phenomenon has not been discovered in previous anonymity research.

Currently, many industrial initiatives focus on web-based applications. In this context an important requirement is that the user should only rely on a standard web browser. Hence the underlying security services also rely solely on a browser for interaction with the user. Browser-based identity federation is a prominent example of such a protocol. Unfortunately, very little is still known about the security of browser-based protocols, and they seem at least as error-prone as standard security protocols. In particular, standard web browsers have limited cryptographic capabilities and thus new protocols are used. Furthermore, these protocols require certain care by the user in person, which must be modeled. In addition, browsers, unlike normal protocol principals, cannot be assumed to do nothing but execute the given security protocol. In this paper, we lay the theoretical basis for the rigorous analysis and security proofs of browser-based security protocols. We formally model web browsers, secure browser channels, and the security-relevant browsing behavior of a user as automata. As a first rigorous security proof of a browser-based protocol we prove the security of password-based user authentication in our model. This is not only the most common stand-alone type of browser authentication, but also a fundamental building block for more complex protocols like identity federation.

Elliptic Curves over finite field have found application in many areas including cryptography. In the current article we define a metric on the set of elliptic curves defined over a prime field ${\mathbf F}_p, p>3$.

We consider expansions of the Abadi-Rogaway logic of indistinguishability of formal cryptographic expressions. The formal language of this logic uses a box as notation for indecipherable strings, through which formal equivalence is defined. We expand the logic by considering different kinds of boxes corresponding to equivalence classes of formal ciphers. We consider not only computational, but also purely probabilistic, information-theoretic interpretations. We present a general, systematic treatment of the expansions of the logic for symmetric encryption. We establish general soundness and completeness theorems for the interpretations. We also present applications to specific settings not covered in earlier works: a purely probabilistic one that interprets formal expressions in One-Time Pad, and computational settings of the so-called type 2 (which-key revealing) cryptosystems based on computational complexity.

Determining the minimal assumptions needed to construct various cryptographic building blocks has been a focal point of research in theoretical cryptography. For most --- but not all! --- cryptographic primitives, complexity assumptions both necessary and sufficient for their existence are known. Here, we revisit the following, decade-old question: what are the minimal assumptions needed to construct a statistically-hiding bit commitment scheme? Previously, it was known how to construct such schemes based on any one-way permutation. In this work, we show that regular one-way functions suffice. We show two constructions of statistically-hiding commitment schemes from regular one-way functions. Our first construction is more direct, and serves as a ``stepping-stone'' for our second construction which has improved round complexity. Of independent interest, as part of our work we show a compiler transforming any commitment scheme which is statistically-hiding against an honest-but-curious receiver to one which is statistically-hiding against a malicious receiver. This demonstrates the equivalence of these two formulations of the problem. Our results also improve the complexity assumptions needed for statistical zero-knowledge arguments.

Fix a small, non-empty set of blockcipher keys K. We say a blockcipher-based hash function is "highly-efficient" if it makes exactly one blockcipher call for each message block hashed, and all blockcipher calls use a key from K. Although a few highly-efficient constructions have been proposed, no one has been able to prove their security. In this paper we prove, in the ideal-cipher model, that it is impossible to construct a highly-efficient iterated blockcipher-based hash function that is provably secure. Our result implies, in particular, that the Tweakable Chain Hash (TCH) construction suggested by Liskov, Rivest, and Wagner is not correct under an instantiation suggested for this construction, nor can TCH be correctly instantiated by any other efficient means.

Given a graph $G$, a perfect secret sharing scheme based on $G$ is a method to distribute a secret data among the vertices of $G$, the participants, so that a subset of participants can recover the secret if they contain an edge of $G$, otherwise they can obtain no information regarding the secret. The average information rate is the ratio of the size of the secret and the average size of the share a participant must remember. The information rate of $G$ is the supremum of the information rates realizable by perfect secret sharing schemes. We construct a graph on $n$ vertices with average information rate below $4/\log n$. We obtain this result by determining, up to a constant factor, the average information rate of the $d$/dimensional cube.

It's well known that Shor[1] proposed a polynomial time algorithm for prime factorization by using quantum computers. For a given number $n$, he gave an algorithm for finding the order $r$ of an element $x$ (mod $n$) instead of giving an algorithm for factoring $n$ directly. The indirect algorithm is feasible because factorization can be reduced to finding the order of an element by using randomization[2]. But a point should be stressed that the order of the number must be even. Actually, the restriction can be removed in a particular case. In this paper, we show that factoring RSA modulus (a product of two primes) only needs to find the order of $2$, whether it is even or not.

SHA-0 employs a primitive polynomnial of degree 16 over GF(2) in its message schedule. There are 2048 primitive polynomials of degree 16 over GF(2). For each primitive polynomial, a SHA-0 variant can be constructed. In this paper, the security of 2048 variants is analyzed against the Chabaud-Joux attack proposed in CRYPTO'98. The analysis shows that all the variants could be collision-attacked by using near-collisions as a tool and thus the replacement of the primitive polynomial is not a proper way to make SHA-0 secure. However, it is shown that the selection of the variants highly affects the complexity of the attack. Furthermore, a collision in the most vulnerable variant is presented. It is obtained by the original Chabaud-Joux attack without any improvements.

We prove that security in the Universal Composability framework (UC) is equivalent to security in the probabilistic polynomial time calculus ppc. Security is defined under active and adaptive adversaries with synchronous and authenticated communication. In detail, we define an encoding from machines in UC to processes in ppc and show it is fully abstract with respect to UC-security and ppc-security, i.e., we show a protocol is UC-secure iff its encoding is ppc-secure. However, we restrict security in ppc to be quantified not over all possible contexts, but over those induced by UC-environments under encoding. This result is not overly-simplifying security in ppc, since the threat and communication models we assume are meaningful in both practice and theory.

Hash chains are widely used in various cryptographic systems such as electronic micropayments and one-time passwords etc. However, hash chains suffer from the limitation that they have a finite number of links which when used up requires the system to re-initialize new hash chains. So system design has to reduce the overhead when hash chains are re-initialized. Recently, Vipul Goyal proposed an elegant one-time-signature-based method to re-initialize hash chains, in this efficient method an infinite number of finite length hash chains can be tied together so that hash chains can be securely re-initialized in a non-repudiable manner. Vipul Goyal¡¯s method is improved in this paper to reach a little more efficient method, which, more importantly, is a natural extension of the concept of conventional hash chains.

This paper introduces new notions of asymptotic proofs, PT(polynomial-time)-extensions, PTM(polynomial-time Turing machine)-$\omega$-consistency, etc. on formal theories of arithmetic including PA (Peano Arithmetic). An asymptotic proof is a set of infinitely many formal proofs, which is introduced to define and characterize a property, PTM-$\omega$-consistency, of a formal theory. Informally speaking, PTM-$\omega$-consistency is a {\it polynomial-time bounded} version (in asymptotic proofs) of $\omega$-consistency, and characterized in two manners: (1) (in the light of the {\it extension of PTM to TM}) the resource {\it unbounded} version of PTM-$\omega$-consistency is equivalent to $\omega$-consistency, and (2) (in the light of {\it asymptotic proofs by PTM}) a PTM-$\omega$-{\it inconsistent} theory includes an axiom that only a super-polynomial-time Turing machine can prove asymptotically over PA, under some assumptions. This paper shows that {\it P$\not=$NP (more generally, any super-polynomial-time lower bound in PSPACE) is unprovable in a PTM-$\omega$-consistent theory $T$}, where $T$ is a consistent PT-extension of PA (although this paper does not show that P$\not=$NP is unprovable in PA, since PA has not been proven to be PTM-$\omega$-consistent). This result implies that to prove P$\not=$NP by any technique requires a PTM-$\omega$-{\it inconsistent} theory, which should include an axiom that only a super-polynomial-time machine can prove asymptotically over PA (or implies a super-polynomial-time computational upper bound) under some assumptions. This result is a kind of generalization of the result of ``Natural Proofs'' by Razborov and Rudich, who showed that to prove ``P$\not=$NP'' by a class of techniques called ``Natural Proofs'' implies a super-polynomial-time (e.g., sub-exponential-time) algorithm that can break a typical cryptographic primitive, a pseudo-random generator. Our result also implies that any relativizable proof of P$\not=$NP requires the {\it resource unbounded version} of \PTM-$\omega$-{\it inconsistent} theory, $\omega$-{\it inconsistent} theory, which suggests another negative result by Baker, Gill and Solovay that no relativizable proof can prove ``P$\not=$NP'' in PA, which is a $\omega$-consistent theory. Therefore, our result gives a unified view to the existing two major negative results on proving P$\not=$NP, Natural Proofs and relativizable proofs, through the two manners of characterization of PTM-$\omega$-consistency. We also show that the PTM-$\omega$-consistency of $T$ cannot be proven in any PTM-$\omega$-consistent theory $S$, where $S$ is a consistent PT-extension of $T$. That is, to prove the independence of P vs NP from $T$ by proving the PTM-$\omega$-consistency of $T$ requires a PTM-$\omega$-{\it inconsistent} theory, or implies a super-polynomial-time computational upper bound under some assumptions. This seems to be related to the results of Ben-David and Halevi and Kurz, O'Donnell and Royer, who showed that to prove the independence of P vs NP from PA using any currently known mathematical paradigm implies an extremely-close-to-polynomial-time (but still super-polynomial-time) algorithm that can solve NP-complete problems. Based on this result, we show that {\it the security of any computational cryptographic scheme is unprovable} in the setting where adversaries and provers are modeled as polynomial-time Turing machines and only a PTM-$\omega$-consistent theory is allowed to prove the security.

We study the problem of obfuscation in the context of point functions (also known as delta functions). A point function is a Boolean function that assumes the value 1 at exactly one point. Our main results are as follows: - We provide a simple construction of efficient obfuscators for point functions for a slightly relaxed notion of obfuscation - wherein the size of the simulator has an inverse polynomial dependency on the distinguishing probability - which is nonetheless impossible for general circuits. This is the first known construction of obfuscators for a non-trivial family of functions under general computational assumptions. Our obfuscator is based on a probabilistic hash function constructed from a very strong one-way permutation, and does not require any set-up assumptions. Our construction also yields an obfuscator for point functions with multi-bit output. - We show that such a strong one-way permutation - wherein any polynomial-sized circuit inverts the permutation on at most a polynomial number of inputs - can be realized using a random permutation oracle. We prove the result by improving on the counting argument used in [GT00]; this result may be of independent interest. It follows that our construction yields obfuscators for point functions in the non-programmable random permutation oracle model (in the sense of [N02]). Furthermore, we prove that an assumption like the one we used is necessary for our obfuscator construction. - Finally, we establish two impossibility results on obfuscating point functions which indicate that the limitations on our construction (in simulating only adversaries with single-bit output and in using non-uniform advice in our simulator) are in some sense inherent. The first of the two results is a consequence of a simple characterization of functions that can be obfuscated against general adversaries with multi-bit output as the class of functions that are efficiently and exactly learnable using membership queries. We stress that prior to this work, what is known about obfuscation are negative results for the general class of circuits [BGI01] and positive results in the random oracle model [LPS04] or under non-standard number-theoretic assumptions [C97]. This work represents the first effort to bridge the gap between the two for a natural class of functionalities.

We show that a number of recent definitions and constructions of fuzzy extractors are not adequate for multiple uses of the same fuzzy secret---a major shortcoming in the case of biometric applications. We propose two particularly stringent security models that specifically address the case of fuzzy secret reuse, respectively from an outsider and an insider perspective, in what we call a chosen perturbation attack. We characterize the conditions that fuzzy extractors need to satisfy to be secure, and present generic constructions from ordinary building blocks. As an illustration, we demonstrate how to use a biometric secret in a remote error tolerant authentication protocol that does not require any storage on the client's side.

Joux and Wang's multicollision attack has yielded collisions for several one-way hash algorithms. Of these, MD5 is the most problematic due to its heavy deployment, but there exists a perception that the flaws identified have no applied implications. We show that the appendability of Merkle-Damgard allows us to add any payload to the proof-of-concept hashes released by Wang et al. We then demonstrate a tool, Stripwire, that uses this capability to create two files -- one which executes an arbitrary sequence of commands, the other which hides those commands with the strength of AES -- both with the same MD5 hash. We show how this affects file-oriented system auditors such as Tripwire, but point out that the failure is nowhere near as catastrophic as it appears at first glance. We examine how this failure affects HMAC and Digital Signatures within Digital Rights Management (DRM) systems, and how the full attack expands into an unusual pseudo-steganographic strikeback methodology against peer to peer networks.

Construction methods of Boolean functions with cryptographically significant properties is an important and difficult problem. In this work we investigate the class of rotation symmetric Boolean functions (RSBFs). These functions are invariant under circular translation of indices and were mainly introduced for efficient implementation purposes. First, we derive general results on these functions. Afterwards, we concentrate on plateaued RSBFs on odd number of variables, which have three valued Walsh Spectra ($0, \pm \lambda$), and can have maximum nonlinearity. We consider both cases when the number of variables $n$ is composite and prime. % When $n$ is odd and prime, we derive the constructive relation between {\it balanced/unbalanced} plateaued RSBFs and show how from one given such function the complete sub class can be generated. As long as search for one plateaued RSBF is of high complexity, our proposed manipulation technique with Walsh spectra imediately give us the way to construct many such functions without time consuming. Since the most important properties of a function are determined via the values of Walsh spectra, then such transformation technique is important to create new function with, possible, better properties. The application of our transformation technique construct a class of $\left((2^{\frac{n-1}{2}}+1)/n\right)!\cdot \left(2^{\frac{n-1}{2}}-1\right)$ balanced/unbalanced plateaued RSBFs. % In our practical implementation of this technique, given one balanced PRSBF on $n=11$ variables we could construct 185 new such functions. To find the first function took us several days, whereas to construct new 185 functions took us just a second. However, this technique can be applied only when the Legendre symbol $(2/n)$ is $-1$, and the first such $n$'s are $3, 5, 7, 11, 13, 19, 29, 37, 43, \ldots$.

Let $r,s,n$ be integers satisfying $0 \leq r < s < n$, $s \geq n^{\alpha}$, $\alpha > 1/4$, and $\gcd(r,s)=1$. Lenstra showed that the number of integer divisors of $n$ equivalent to $r \pmod s$ is upper bounded by $O((\alpha-1/4)^{-2})$. We re-examine this problem; showing how to explicitly construct all such divisors and incidentally improve this bound to $O((\alpha-1/4)^{-3/2})$.

Is it harder to solve many puzzles than it is to solve just one? This question has different answers, depending on how you define puzzles. For the case of inverting one-way functions it was shown by Yao that solving many independent instances simultaneously is indeed harder than solving a single instance (cf. the transformation from weak to strong one-way functions). The known proofs of that result, however, use in an essential way the fact that for one-way functions, verifying candidate solutions to a given puzzle is easy. We extend this result to the case where solutions are efficiently verifiable only by the party that generated the puzzle. We call such puzzles weakly verifiable. That is, for weakly verifiable puzzles we show that if no efficient algorithm can solve a single puzzle with probability more than $\eps$, then no efficient algorithm can solve $n$ independent puzzles simultaneously with probability more than $\eps^n$. We also demonstrate that when the puzzles are not even weakly verifiable, solving many puzzles may be no harder than solving a single one. Hardness amplification of weakly verifiable puzzles turns out to be closely related to the reduction of soundness error under parallel repetition in computationally sound arguments. Indeed, the proof of Bellare, Impagliazzo and Naor that parallel repetition reduces soundness error in three-round argument systems implies a result similar to our first result, albeit with considerably worse parameters. Also, our second result is an adaptation of their proof that parallel repetition of four-round systems may not reduce the soundness error.

In this paper we focus on the three basic security requirements for a cryptographic hash function, commonly referred as preimage, second preimage and collision resistance. We examine these security requirements in the case of attacks which do not take advantage on how the hash function is computed, expressing them as success probabilities of suitable randomized algorithms. We give exact mathematical expressions for such resistance indices, and obtain their functional behaviour in relation to the amount of uniformity in the hash function outcomes. Our work provides a mathematical framework for the study of cryptographic hash functions, which enable us to give proofs for some prevailing beliefs.

Adaptively-secure encryption schemes ensure secrecy even in the presence of an adversary who can corrupt parties in an adaptive manner based on public keys, ciphertexts, and secret data of already-corrupted parties. Ideally, an adaptively-secure encryption scheme should, like standard public-key encryption, allow arbitrarily-many parties to use a single encryption key to securely encrypt arbitrarily-many messages to a given receiver who maintains only a single short decryption key. However, it is known that these requirements are impossible to achieve: no non-interactive encryption scheme that supports encryption of an unbounded number of messages and uses a single, unchanging decryption key can be adaptively secure. Impossibility holds even if secure data erasure is possible. We show that this limitation can be overcome by updating the decryption key over time and making some mild assumptions about the frequency of communication between parties. Using this approach, we construct adaptively-secure, completely non-interactive encryption schemes supporting secure encryption of arbitrarily-many messages from arbitrarily-many senders. Our schemes additionally provide forward security and security against chosen-ciphertext attacks.

Cryptographic applications using an elliptic curve over a finite field filter curves for suitability using their order as the primary criterion: e.g. checking that their order has a large prime divisor before accepting it. It is therefore natural to ask whether the discrete log problem (DLOG) has the same difficulty for all curves with the same order; if so it would justify the above practice. We prove that this is essentially true by showing random reducibility of dlog among such curves, assuming the Generalized Riemann Hypothesis (GRH). Our reduction proof works for curves with (nearly) the same endomorphism rings, but it is unclear if such a reduction exists in general. This suggests that in addition to the order, the conductor of its endomorphism ring may play a role. The random self-reducibility for dlog over finite fields is well known; the non-trivial part here is that one must relate non-isomorphic algebraic groups of two isogenous curves. We construct certain expander graphs with elliptic curves as nodes and low degree isogenies as edges, and utilize the rapid mixing of random walks on this graph. We also briefly look at some recommended curves, compare “random” type NIST FIPS 186-2 curves to other special curves from this standpoint, and suggest a parameter to measure how generic a given curve is.

We investigate the relation between symbolic and cryptographic secrecy properties for cryptographic protocols. Symbolic secrecy of payload messages or exchanged keys is arguably the most important notion of secrecy shown with automated proof tools. It means that an adversary restricted to symbolic operations on terms can never get the entire considered object into its knowledge set. Cryptographic secrecy essentially means computational indistinguishability between the real object and a random one, given the view of a much more general adversary. In spite of recent advances in linking symbolic and computational models of cryptography, no relation for secrecy under active attacks is known yet. For exchanged keys, we show that a certain strict symbolic secrecy definition over a specific Dolev-Yao-style cryptographic library implies cryptographic key secrecy for a real implementation of this cryptographic library. For payload messages, we present the first general cryptographic secrecy definition for a reactive scenario. The main challenge is to separate secrecy violations by the protocol under consideration from secrecy violations by the protocol users in a general way. For this definition we show a general secrecy preservation theorem under reactive simulatability, the cryptographic notion of secure implementation. This theorem is of independent cryptographic interest. We then show that symbolic secrecy implies cryptographic payload secrecy for the same cryptographic library as used in key secrecy. Our results thus enable existing formal proof techniques to establish cryptographically sound proofs of secrecy for payload messages and exchanged keys.

We investigate the average case complexity of a generalization of the compact knapsack problem to arbitrary rings: given $m$ (random) ring elements a_1,...,a_m in R and a (random) target value b in R, find coefficients x_1,...,x_m in S (where S is an appropriately chosen subset of R) such that a_1*x_1 + ... + a_m*x_m = b. We consider compact versions of the generalized knapsack where the set S is large and the number of weights m is small. Most variants of this problem considered in the past (e.g., when R = Z is the ring of the integers) can be easily solved in polynomial time even in the worst case. We propose a new choice of the ring R and subset S that yields generalized compact knapsacks that are seemingly very hard to solve on the average, even for very small values of m. Namely, we prove that for any unbounded function m = omega(1) with arbitrarily slow growth rate, solving our generalized compact knapsack problems on the average is at least as hard as the worst-case instance of various approximation problems over cyclic lattices. Specific worst-case lattice problems considered in this paper are the shortest independent vector problem SIVP and the guaranteed distance decoding problem GDD (a variant of the closest vector problem, CVP) for approximation factors n^{1+epsilon} almost linear in the dimension of the lattice. Our results yield very efficient and provably secure one-way functions (based on worst-case complexity assumptions) with key size and time complexity almost linear in the security parameter n. Previous constructions with similar security guarantees required quadratic key size and computation time. Our results can also be formulated as a connection between the worst-case and average-case complexity of various lattice problems over cyclic and quasi-cyclic lattices.

By the relationship between the Walsh spectra at partial points and the Walsh spectra of its sub-functions, by the action of general linear group on the set of Boolean functions, and by the Reed-Muller transform, a novel method is developed, which can theoretically construct all bent functions. With this method, we enumerate all bent functions in 6 variables; in 8-variable case, our method is more efficient than the method presented by Clark though we still can not enumerate all bent functions; enumeration of all homogeneous bent functions of degree 3 in eight variables can be done in one minute by a P4 1.7G HZ computer; construction of homogenous bent function of degree 3 in 10 variables is efficient too; the nonexistence of homogeneous bent functions in 10 variables of degree 4 is proved

A new method for digital true random number generation based on asynchronous logic circuits with feedback is introduced. In particular, a concrete technique using the so-called Fibonacci and Galois ring oscillators is developed and experimentally tested in FPGA technology. The generated random binary sequences inherently have a high speed and a very high and robust entropy rate in comparison with previous proposals for digital random number generators. A new method for digital post-processing of random data based on non-autonomous synchronous logic circuits with feedback is also introduced and a concrete technique using a self-clock-controlled linear feedback shift register is proposed. The post-processing can provide both randomness extraction and computationally secure speed increase of input random data.

We put forward the first secret-key steganographic construction that is both black-box (i.e., the sender need not have knowledge of the channel beyond the ability to sample from it) and stateless (i.e., the sender and the recipient need not maintain synchronized state when sending multiple bits). Both of these properties are important: the first because in many settings it is unrealistic to assume detailed knowledge of the underlying channel distribution, and the second because maintaining synchronized state between the sender and the recipient is particularly problematic in steganography, where communication to resynchronize will alert the adversary. For channels of sufficient entropy, our construction is more efficient than previous black-box constructions. Moreover, it is the first one to provide a tradeoff between the number of samples the encoder needs and the rate at which hiddentext is transmitted.

A first step toward establishing foundations for group signatures was taken by Bellare, Micciancio and Warinschi (Eurocrypt 2003) with a treatment of the case where the group is static. However the bulk of existing practical schemes and applications are for dynamic groups, and these involve important new elements and security issues. This paper treats this case, providing foundations for dynamic group signatures, in the form of a model, strong formal definitions of security, and a construction proven secure under general assumptions. We believe this is an important and useful step because it helps bridge the gap between Bellare Micciancio and Warinschi and the previous practical work, and delivers a basis on which existing practical schemes may in future be evaluated or proven secure.

The distribution of r-patterns is an important aspect of pseudorandomness for periodic sequences over finite field.The aim of this work is to study the distribution of r-patterns in the Kerdock-code binary sequences and the highest level sequences of primitive sequences over $Z_{2^l}$.By combining the local Weil bound with spectral analysis,we derive the upper bound of the deviation to uniform distribution.As a consequence,the recent result on the quantity is improved.

We show new lower bounds and impossibility results for general (possibly *non-black-box*) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions: 1. There does not exist a two-round zero-knowledge *proof* system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero knowledge, by Goldreich and Oren (J. Cryptology, 1994) was only for the case of *auxiliary-input* zero-knowledge proofs and arguments. 2. There does not exist a constant-round zero-knowledge *strong* proof or argument of knowledge (as defined by Goldreich (2001)) for a nontrivial language. 3. There does not exist a constant-round public-coin *proof* system for a nontrivial language that is *resettable zero knowledge*. This result also extends to "bounded-resettable" zero knowledge, in which the number of resets is a priori bounded by a polynomial in the input length and prover-to-verifier communication. In contrast, we show that under reasonable assumptions, there does exist such a (computationally sound) *argument* system that is bounded-resettable zero knowledge. The complexity assumptions we use are not commonly used in cryptography. However, in all cases, we show that assumptions similar to ours are necessary for the above results. Most previously known lower bounds, such as those of Goldreich and Krawczyk (SIAM J. Computing, 1996), were only for *black-box* zero knowledge. However, a result of Barak (FOCS 2001) shows that many (or even most) of these black-box lower bounds do *not* extend to the case of general zero knowledge.

A general mathematical framework behind algebraic cryptanalytic attacks is developed. The framework relates to finding algebraic equations induced by vectorial Boolean functions and, in particular, equations of low algebraic degree. The equations may involve only a subset of input variables and may or may not be conditioned on the values of output variables. In addition, the equations may have a special form interesting for the so-called fast algebraic attacks. A possible divide-and-conquer effect is pointed out and the notion of algebraic immunity order, naturally extending the notion of correlation immunity order, is introduced. An application of general results to stream ciphers known as combiners with or without memory, with possibly multiple outputs, is studied in particular detail. Special properties of combiners with finite input memory, such as nonlinear filter generators, are established. Finally, finding induced algebraic equations for divide-and-conquer algebraic attacks on combiners with or without memory is also considered.

We consider the problem of defining and achieving plaintext-aware encryption without random oracles in the classical public-key model. We provide definitions for a hierarchy of notions of increasing strength: PA0, PA1 and PA2, chosen so that PA1+IND-CPA => IND-CCA1 and PA2+IND-CPA => IND-CCA2. Towards achieving the new notions of plaintext awareness, we show that a scheme due to Damgard, denoted DEG, and the ``lite'' version of the Cramer-Shoup scheme, denoted CSL, are both PA0 under the KEA0 assumption of Damgard, and PA1 under an extension of this assumption called KEA1. As a result, DEG is the most efficient proven IND-CCA1 scheme known.

Russell and Wang (Eurocrypt 2002) recently introduced an elegant, information-theoretic notion called entropic security of encryption: they required that the cipher text leak no predicate of the plaintext (similar to semantic security (Goldwasser and Micali, JCSS 1984)) but only as long as the distribution on messages has high entropy from the adversary's point of view. They show that this notion of security can be achieved with very short keys for entropically rich message spaces. Canetti, Miccianci and Reingold (STOC, 1998) had previously constructed hash functions which satisfy a similar entropic security condition. The output of such hash function leaks no partial information about the input, provided the input has sufficiently high entropy. This paper studies entropic security in general, and its application to the encryption of high-entropy messages. (1) We elucidate the notion of entropic security. Our results apply to all entropically-secure primitives, including both encryption and hash functions. We strengthen the formulation of Canetti and Russell and Wang: we require that an entropically-secure primitive leak no function whasoever of its input, while the previous works focus only on predicates. This stronger formulation is much closer to the original notion of semantic security. We also show that entropic security is equivalent to indistinguishability on pairs of input distributions of sufficiently high entropy. This equivalence generalizes the conventional equivalence between indistinguishability and semantic security. Indistinguishability, in turn, is related to randomness extraction from non-uniform distributions. The proof of the equivalence of hiding predicates to hiding all functions is quite involved, and requires very different techniques from those of Goldwasser and Micali. (2) We use the equivalence above, and the connection to randomness extraction, to prove several new results on entropically-secure encryption. We obtain: (a) Two general frameworks for constructing entropically secure encryption schemes, one based on expander graphs and the other on XOR-universal hash functions. These schemes generalize the schemes of Russell and Wang, yielding simpler constructions and proofs as well as improved parameters. The best scheme uses a key of length k=n-t+2log(1/eps)+O(1), where eps is a measure of leakage and t is the initial min-entropy of the message. (b) Lower bounds on the key length k for entropic security and indistinguishability. In particular, we show near tightness of Russell-Wang constructions: k > n-t. (In fact, for a large class of schemes k >= n-t + log(1/eps).)

A complexity-theoretic model for public-key steganography with active attacks is introduced. The notion of steganographic security against adaptive chosen-covertext attacks (SS-CCA) and a relaxation called steganographic security against publicly-detectable replayable adaptive chosen-covertext attacks (SS-PDR-CCA) are formalized. These notions are closely related to CCA-security and PDR-CCA-security for public-key cryptosystems. In particular, it is shown that any SS-(PDR-)CCA stegosystem is a (PDR-)CCA-secure public-key cryptosystem and that an SS-PDR-CCA stegosystem can be realized from any PDR-CCA-secure public-key cryptosystem with pseudorandom ciphertexts.

Recently some efforts were made towards capturing the security requirements from digital signature schemes as an ideal functionality within a composable security framework. This modeling of digital signatures potentially has some significant analytical advantages (such as enabling component-wise analysis of complex systems that use signature schemes, as well as symbolic and automatable analysis of such systems). However, it turns out that formulating ideal functionalities that capture the properties expected from signature schemes in a way that is both sound and enjoys the above advantages is not a trivial task. This work has several contributions. We first correct some flaws in the definition of the ideal signature functionality of Canetti, 2001, andsubsequent formulations. Next we provide a minimal formalization of ``ideal certification authorities'' and show how authenticated communication can be obtained using ideal signatures and an ideal certification authority. This is done while guaranteeing full modularity (i.e., each component is analyzed as stand-alone), and in an unconditional and errorless way. This opens the door to symbolic and automated analysis of protocols for these tasks, in a way that is both modular and cryptographically sound.

The most common method for computing exponentiation of random elements in Abelian groups are sliding window schemes, which enhance the efficiency of the binary method at the expense of some precomputation. In groups where inversion is easy (e.g. elliptic curves), signed representations of the exponent are meaningful because they decrease the amount of required precomputation. The asymptotic best signed method is wNAF, because it minimizes the precomputation effort whilst the non-zero density is nearly optimal. Unfortunately, wNAF can be computed only from the least significant bit, i.e. right-to-left. However, in connection with memory constraint devices left-to-right recoding schemes are by far more valuable. In this paper we define the MOF (Mutual Opposite Form), a new canonical representation of signed binary strings, which can be computed in any order. Therefore we obtain the first left-to-right signed exponent-recoding scheme for general width w by applying the width w sliding window conversion on MOF left-to-right. Moreover, the analogue right-to-left conversion on MOF yields wNAF, which indicates that the new class is the natural left-to-right analogue to the useful wNAF. Indeed, the new class inherits the outstanding properties of wNAF, namely the required precomputation and the achieved non-zero density are exactly the same.

In this paper we present a general framework for password-based authenticated key exchange protocols, in the common reference string model. Our protocol is actually an abstraction of the key exchange protocol of Katz et al.\ and is based on the recently introduced notion of smooth projective hashing by Cramer and Shoup. We gain a number of benefits from this abstraction. First, we obtain a modular protocol that can be described using just three high-level cryptographic tools. This allows a simple and intuitive understanding of its security. Second, our proof of security is significantly simpler and more modular. Third, we are able to derive analogues to the Katz et al.\ protocol under additional cryptographic assumptions. Specifically, in addition to the DDH assumption used by Katz et al., we obtain protocols under both the Quadratic and $N$-Residuosity assumptions. In order to achieve this, we construct new smooth projective hash functions.

We propose a modification to the framework of Universally Composable (UC) security [Canetti'01]. Our new notion, involves comparing the protocol executions with an ideal execution involving ideal functionalities (just as in UC-security), but allowing the environment and adversary access to some super-polynomial computational power. We argue the meaningfulness of the new notion, which in particular subsumes many of the traditional notions of security. We generalize the Universal Composition theorem of [Canetti'01] to the new setting. Then under new computational assumptions, we realize secure multi-party computation (for static adversaries) without a common reference string or any other set-up assumptions, in the new framework. This is known to be impossible under the UC framework.

K. Kedlaya proposed an method to count the number of ${\mathbb F}_q$-rational points in a hyper-elliptic curve, using the Leschetz fixed points formula in Monsky-Washinitzer Cohomology. The method has been extended to super-elliptic curves (Gaudry and Gürel) immediately, to characteristic two hyper-elliptic curves, and to $C_{ab}$ curves (J. Denef, F. Vercauteren). Based on Miura theory, which is associated with how a curve is expressed as an affine variety, this paper applies Kedlaya's method to so-called strongly telescopic curves which are no longer plane curves and contain super-elliptic curves as special cases.

Complexity-theoretic cryptography considers only abstract notions of computation, and hence cannot protect against attacks that exploit the information leakage (via electromagnetic fields, power consumption, etc.) inherent in the physical execution of any cryptographic algorithm. Such "physical observation attacks" bypass the impressive barrier of mathematical security erected so far, and successfully break mathematically impregnable systems. The great practicality and the inherent availability of physical attacks threaten the very relevance of complexity-theoretic security. To respond to the present crisis, we put forward physically observable cryptography: a powerful, comprehensive, and precise model for defining and delivering cryptographic security against an adversary that has access to information leaked from the physical execution of cryptographic algorithms. Our general model allows for a variety of adversaries. In this paper, however, we focus on the strongest possible adversary, so as to capture what is cryptographically possible in the worst possible, physically observable setting. In particular, we -- consider an adversary that has full (and indeed adaptive) access to any leaked information; -- show that some of the basic theorems and intuitions of traditional cryptography no longer hold in a physically observable setting; and -- construct pseudorandom generators that are provably secure against all physical-observation attacks. Our model makes it easy to meaningfully restrict the power of our general physically observing adversary. Such restrictions may enable schemes that are more efficient or rely on weaker assumptions, while retaining security against meaningful physical observations attacks.

Until recently, most research on the topic of secure computation focused on the stand-alone model, where a single protocol execution takes place. In this paper, we construct protocols for the setting of {\em bounded-concurrent self composition}, where a (single) secure protocol is run many times concurrently, and there is a predetermined bound on the number of concurrent executions. In short, we show that {\em any} two-party functionality can be securely computed under bounded-concurrent self composition, in the {\sf plain model} (where the only setup assumption made is that the parties communicate via authenticated channels). Our protocol provides the first feasibility result for general two-party computation in the plain model, {\em for any model of concurrency}. All previous protocols assumed a trusted setup phase in order to obtain a common reference string. On the downside, the number of rounds of communication in our protocol is super-linear in the bound on the number of concurrent executions. However, we believe that our constructions will lead to more efficient protocols for this task.

We clarify a relation between the XL algorithm and Groebner bases algorithms. The XL algorithm was proposed to be a more efficient algorithm to solve a system of equations with a special assumption without trying to calculate a whole Groebner basis. But in our result, it is shown that the XL algorithm is also a Groebner bases algorithm which can be represented as a redundant version of a Groebner bases algorithm F4 under the assumption in XL.

Sequences with almost perfect linear complexity profile are defined by H.~Niederreiter[4]. C.P. Xing and K.Y. Lam[5, 6] extended this concept from the case of single sequences to the case of multi-sequences and furthermore proposed the concept of d-perfect. In this paper, based on the technique of m-continued fractions due to Dai et al, we investigate the property of d-perfect multi-sequences and obtain the sufficient and necessary condition on d-perfect property. We show that multi-sequences with d-perfect property are not always strongly d-perfect. In particular, we give one example to disprove the conjecture on d-perfect property of multi-sequences proposed by C.P. Xing in [6].

An information-theoretic model for steganography with a passive adversary is proposed. The adversary's task of distinguishing between an innocent cover message $C$ and a modified message $S$ containing hidden information is interpreted as a hypothesis testing problem. The security of a steganographic system is quantified in terms of the relative entropy (or discrimination) between the distributions of $C$ and $S$, which yields bounds on the detection capability of any adversary. It is shown that secure steganographic schemes exist in this model provided the covertext distribution satisfies certain conditions. A universal stegosystem is presented in this model that needs no knowledge of the covertext distribution, except that it is generated from independently repeated experiments.

In~\cite{B02} it was proved that 20 out of 64 PGV-hash functions~\cite{P94} based on block cipher are collision resistant and one-way-secure in black-box model of the underlying block cipher. Here, we generalize the definition of PGV-hash function into a hash family and we will prove that besides the previous 20 hash functions we have 22 more collision resistant and one-way secure hash families. As all these 42 families are keyed hash family, these become target collision resistant also. All these 42 hash families have tight upper and lower bounds on (target) collision resistant and one-way-ness.

In this paper we propose three refinements to Miller's algorithm for computing Weil/Tate Pairing.The first one is an overall improvement and achieves its optimal behavior if the binary expansion of the involved integer has more zeros. If more ones are presented in the binary expansion, second improvement is suggested. The third one is especially efficient in the case base three. We also have some performance analysis.

Recently we solved the long-standing open problem of justifying a Dolev-Yao type model of cryptography as used in virtually all automated protocol provers under active attacks. The justification was done by defining an ideal system handling Dolev-Yao-style terms and a cryptographic realization with the same user interface, and by showing that the realization is as secure as the ideal system in the sense of reactive simulatability. This definition encompasses arbitrary active attacks and enjoys general composition and property-preservation properties. Security holds in the standard model of cryptography and under standard assumptions of adaptively secure primitives. A major primitive missing in that library so far is symmetric encryption. We show why symmetric encryption is harder to idealize in a way that allows general composition than existing primitives in this library. We discuss several approaches to overcome these problems. For our favorite approach we provide a detailed provably secure idealization of symmetric encryption within the given framework for constructing nested terms.

For the last two decades the notion and implementations of proxy signatures have been used to allow transfer of digital signing power within some context (in order to enable flexibility of signers within organizations and among entities). On the other hand, various notions of the key-evolving signature paradigms (forward-secure, key-insulated, and intrusion-resilient signatures) have been suggested in the last few years for protecting the security of signature schemes, localizing the damage of secret key exposure. In this work we relate the various notions via direct and concrete security reductions that are tight. We start by developing the first formal model for fully hierarchical proxy signatures, which, as we point out, also addresses vulnerabilities of previous schemes when self-delegation is used. Next, we prove that proxy signatures are, in fact, equivalent to key-insulated signatures. We then use this fact and other results to establish a tight hierarchy among the key-evolving notions, showing that intrusion-resilient signatures and key-insulated signatures are equivalent, and imply forward-secure signatures. We also introduce other relations among extended notions. Besides the importance of understanding the relationships among the various notions that were originally designed with different goals or with different system configuration in mind, our findings imply new designs of schemes. For example, many proxy signatures have been presented without formal model and proofs, whereas using our results we can employ the work on key-insulated schemes to suggest new provably secure designs of proxy signatures schemes.

This paper considers a weak variant on the notion of zero-knowledge. The weak notion is compatible with the chosen ciphertext security. In fact, arguments of knowledge based on IND-CCA encryption schemes are shown to be statistical zero-knowledge in that sense.

Every integer n > 0 º N defines an increasing monotonic series of integers: n1, n2, ...nk, such that nk = nk +k(k-1)/2. We define as s(m) the number of such series that an integer m belongs to. We prove that there are infinite number of integers with s=1, all of the form 2^t (they belong only to the series that they generate, not to any series generated by a smaller integer). We designate them as s-prime integers. All integers with a factor other than 2 are not s-prime (s>1), but are s-composite. However, the arithmetic s function shows great variability, lack of apparent pattern, and it is conjectured that s(n) is unbound. Two integers, n and m, are defined as s-congruent if they have a common s-series. Every arithmetic equation can be seen as an expression without explicit unknowns -- provided every integer variable can be replaced by any s-congruent number. To validate the equation one must find a proper match of such members. This defines a special arithmetic, which appears well disposed towards certain cryptographic applications.

In 1986, Fiat and Shamir suggested a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The significant contribution of this method is a means for designing efficient digital signatures, while hopefully achieving security against chosen message attacks. All other known constructions which achieve such security are substantially more inefficient and complicated in design. In 1996, Pointcheval and Stern proved that the signature schemes obtained by the Fiat-Shamir transformation are secure in the so called `Random Oracle Model'. The question is: does the proof of the security of the Fiat-Shamir transformation in the Random Oracle Model, imply that the transformation yields secure signature schemes in the ``real-world"? In this paper we answer this question negatively. We show that there exist secure 3-round public-coin identification schemes for which the Fiat-Shamir methodology produces {\bf insecure} digital signature schemes for {\bf any} implementation of the `Random Oracle Model' in the `real-world' by a function ensemble.

Given an ordinary elliptic curve on Hesse form over a finite field of characteristic three, we give a sequence of elliptic curves which leads to an effective construction of the canonical lift, and obtain an algorithm for computing the number of points. Our methods are based on the study of an explicitly and naturally given $3$-isogeny between elliptic curves on Hesse form.

Encryption is often conceived as a committing process, in the sense that the ciphertext may serve as a commitment to the plaintext. But this does not follow from the standard definitions of secure encryption. We define and construct symmetric and asymmetric committing encryption schemes, enabling publicly verifiable non-repudiation. Committing encryption eliminates key-spoofing attacks and has also the robustness to be signed afterwards. Our constructions are very efficient and practical. In particular, we show that most popular asymmetric encryption schemes, e.g. RSA, are committing encryption schemes; we also have an (efficient) construction given an arbitrary asymmetric encryption scheme. Our construction of symmetric committing encryption retains the efficiency of the symmetric encryption for real-time operations, although it uses few public key signatures in the setup phase. Finally, we investigate how to achieve both confidentiality and non-repudiation, and present a publicly verifiable signcryption scheme. Contrary to previous signcryption schemes, which are not publicly verifiable, our publicly verifiable signcryption supports non-repudiation. We construct a simple and efficient publicly verifiable signcryption scheme based on a new composition method which we call “commit-encrypt-then-sign” (CEtS) that preserves security properties of both committing encryption and digital signature schemes.

Cryptographic systems often involve running multiple concurrent instances of some protocol, where the instances have some amount of joint state and randomness. (Examples include systems where multiple protocol instances use the same public-key infrastructure, or the same common reference string.) Rather than attempting to analyze the entire system as a single unit, we would like to be able to analyze each such protocol instance as stand-alone, and then use a general composition theorem to deduce the security of the entire system. However, no known composition theorem applies in this setting, since they all assume that the composed protocol instances have disjoint internal states, and that the internal random choices in the various instances are independent. We propose a new composition operation that can handle the case where different components have some amount of joint state and randomness, and demonstrate sufficient conditions for when the new operation preserves security. The new operation, which is called {\em universal composition with joint state} (and is based on the recently proposed universal composition operation), turns out to be very useful in a number of quite different scenarios such as those mentioned above.

This paper studies the relation among simulator-based and comparison-based definitions of semantic security. The definitions are considered in a more general framework than the ordinal one; namely, an adversary is assumed to have access to prior information of a plaintext. If the framework is restricted to the ordinal one, then all the security notions considered in this paper, including indistinguishability, are shown to be equivalent. On the other hand, the equivalence is not necessarily valid in the general framework. In fact, it is shown that no encryption scheme is secure in the sense of comparison-based semantic security in the strongest forms. Furthermore, a sufficient condition for the equivalence between semantic security and indistinguishability is derived.

The VMPC function is a combination of two basic operations: permutation composition and integer addition. The function resulting from this combination shows to have very high resistance to inverting. Computational effort of about 2^260 operations is estimated to be required to invert the VMPC function. The value of the function can be computed with 3 elementary computer processor instructions per byte. An open question is whether the function's simplicity raises a realistic chance that the lower bound on the complexity of inverting it might be proved.

Informally, a public-key steganography protocol allows two parties, who have never met or exchanged a secret, to send hidden messages over a public channel so that an adversary cannot even detect that these hidden messages are being sent. Unlike previous settings in which provable security has been applied to steganography, public-key steganography is information-theoretically impossible. In this work we introduce computational security conditions for public-key steganography similar to those introduced by Hopper, Langford and von Ahn for the private-key setting. We also give the first protocols for public-key steganography and steganographic key exchange that are provably secure under standard cryptographic assumptions. Additionally, in the random oracle model, we present a protocol that is secure against adversaries that have access to a decoding oracle (the steganographic equivalent of CCA-2 adversaries).

We give the exact number and representatives of the isomorphism, which preserves infinity, classes of hyperelliptic curves of genus $2$ over finite fields with characteristic $2 $ in most cases. These results have applications to hyperelliptic curve cryptography.

In this paper, we generalize the composition construction of Khoo et al. for highly nonlinear Boolean functions. We utilize general quadratic forms instead of the trace map in the construction. The construction composes an n-variable Boolean function and an m-variable quadratic form over field with characteristic 2 to get an nm-variable Boolean function with beautiful spectrum property and a doubled algebraic degree. Especially, the method is suitable to construct functions with 3-valued spectra (bent-like functions) or ones with better spectra (near-bent functions). Our proof technique is based on classification of quadratic forms over finite fields and enumeration of solutions of quadratic equations. We also prove the p-ary analogy of these results for odd prime p.

In a practical system, a message is often encrypted more than once by different encryptions, here called multiple encryption, to enhance its security. Additionally, new features may be achieved by multiple encrypting a message for a scheme, such as the key-insulated cryptosystems \cite{DKXY02} and anonymous channels \cite{Cha81}. Intuitively, a multiple encryption should remain ``secure'', whenever there is one component cipher unbreakable in it. In NESSIE's latest Portfolio of recommended cryptographic primitives (Feb. 2003), it is suggested to use multiple encryption with component ciphers based on different assumptions to acquire long term security. However, in this paper we show this needs careful discussion. Especially, this may \emph{not} be true according to (adaptive) chosen ciphertext attack ({\sf CCA}), even with all component ciphers {\sf CCA} secure. We define an extended version of {\sf CCA} called \emph{chosen ciphertext attack for multiple encryption} ({\sf ME-CCA}) to emulate real world partial breaking of assumptions, and give constructions of multiple encryption satisfying {\sf ME-CCA} security. Since {\sf CCA} security seems so stringent, we further relax it by introducing \emph{weak} {\sf ME-CCA} ({\sf ME-wCCA}), and prove {\sf IND-ME-wCCA} secure multiple encryption can be acquired from {\sf IND-gCCA} secure component ciphers. We also study the relation of various security notions for multiple encryption. We then apply these results to key-insulated cryptosystem. It is only previously known in \cite{DKXY02} that a generic construction exists provably secure against {\sf CPA} attack, however, we prove that this generic construction is in fact secure against {\sf ME-wCCA} by choosing all components {\sf IND-CCA} secure. We also give an efficient generic construction of key-insulated cryptosystem, which is so far the \emph{first} generic construction provably secure against {\sf CCA} (in the random oracle model).

In extension of the bit commitment task and following work initiated by Crepeau and Kilian, we introduce and solve the problem of characterising the optimal rate at which a discrete memoryless channel can be used for bit commitment. It turns out that the answer is very intuitive: it is the maximum equivocation of the channel (after removing trivial redundancy), even when unlimited noiseless bidirectional side communication is allowed. By a well-known reduction, this result provides a lower bound on the channel's capacity for implementing coin tossing, which we conjecture to be an equality. The method of proving this relates the problem to Wyner's wire--tap channel in an amusing way. We also discuss extensions to quantum channels.

The goals of this paper are three-fold. First we introduce and motivate a generalization of the fundamental concept of the indistinguishability of two systems, called indifferentiability. This immediately leads to a generalization of the related notion of reducibility of one system to another. Second, we prove that indifferentiability is the necessary and sufficient condition on two systems S and T such that the security of any cryptosystem using T as a component is not affected when T is substituted by S. In contrast to indistinguishability, indifferentiability is applicable in settings where a possible adversary is assumed to have access to additional information about the internal state of the involved systems, for instance the public parameter selecting a member from a family of hash functions. Third, we state an easily verifiable criterion for a system U not to be reducible (according to our generalized definition) to another system V and, as an application, prove that a random oracle is not reducible to a weaker primitive, called asynchronous beacon, and also that an asynchronous beacon is not reducible to a finite-length random string. Each of these irreducibility results alone implies the main theorem of Canetti, Goldreich and Halevi stating that there exist cryptosystems that are secure in the random oracle model but for which replacing the random oracle by any implementation leads to an insecure cryptosystem.

We take a critical look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes that result from implementing the random oracle by so called "cryptographic hash functions". The main result of this paper is a negative one: There exist signature and encryption schemes that are secure in the Random Oracle Model, but for which any implementation of the random oracle results in insecure schemes. In the process of devising the above schemes, we consider possible definitions for the notion of a "good implementation" of a random oracle, pointing out limitations and challenges.

In earlier work, we described a ``pathological'' example of a signature scheme that is secure in the random-oracle model, but for which no secure implementation exists. For that example, however, it was crucial that the scheme is able to sign "long messages" (i.e., messages whose length is not a-priori bounded). This left open the possibility that the Random Oracle Methodology is sound with respect to signature schemes that sign only "short" messages (i.e., messages of a-priori bounded length, smaller than the length of the keys in use), and are "memoryless" (i.e., the only thing kept between different signature generations is the initial signing-key). In this work, we extend our negative result to address such signature schemes. A key ingredient in our proof is a new type of interactive proof systems, which may be of independent interest.

Proofs of security protocols typically employ simple abstractions of cryptographic operations, so that large parts of such proofs are independent of cryptographic details. The typical abstraction is the Dolev-Yao model, which treats cryptographic operations as a specific term algebra. However, there is no cryptographic semantics, i.e., no theorem that says what a proof with the Dolev-Yao abstraction implies for the real protocol, even if provably secure cryptographic primitives are used. Recently we introduced an extension to the Dolev-Yao model for which such a cryptographic semantics exists, i.e., where security is preserved if the abstractions are instantiated with provably secure cryptographic primitives. Only asymmetric operations (digital signatures and public-key encryption) are considered so far. Here we extend this model to include a first symmetric primitive, message authentication, and prove that the extended model still has all desired properties. The proof is a combination of a probabilistic, imperfect bisimulation with cryptographic reductions and static information-flow analysis. Considering symmetric primitives adds a major complication to the original model: we must deal with the exchange of secret keys, which might happen any time before or after the keys have been used for the first time. Without symmetric primitives only public keys need to be exchanged.

A permutation $P\in S_N$ is a \emph{fast forward permutation} if for each $m$ the computational complexity of evaluating $P^m(x)$ is small independently of $m$ and $x$. Naor and Reingold constructed fast forward pseudorandom cycluses and involutions. By studying the evolution of permutation graphs, we prove that the number of queries needed to distinguish a random cyclus from a random permutation in $S_N$ is $\Theta(N)$ if one does not use queries of the form $P^m(x)$, but is only $\Theta(1)$ if one is allowed to make such queries. We construct fast forward permutations which are indistinguishable from random permutations even when queries of the form $P^m(x)$ are allowed. This is done by introducing an efficient method to sample the cycle structure of a random permutation, which in turn solves an open problem of Naor and Reingold.

A birthday surprise is the event that, given $k$ uniformly random samples from a sample space of size $n$, at least two of them are identical. We show that Bernoulli numbers can be used to derive arbitrarily exact bounds on the probability of a birthday surprise. This result can be used in arbitrary precision calculators, and it can be applied to better understand some questions in communication security and pseudorandom number generation.

We introduce and analyze an efficient family of linear feedback shift registers (LFSR's) with maximal period. This family is word-oriented and is suitable for implementation in software, thus provides a solution to a recent challenge \cite{FSE94}. The classical theory of LFSR's is extended to provide efficient algorithms for generation of irreducible and primitive LFSR's of this new type.

We show how to securely realize any two-party and multi-party functionality in a {\em universally composable} way, regardless of the number of corrupted participants. That is, we consider an asynchronous multi-party network with open communication and an adversary that can adaptively corrupt as many parties as it wishes. In this setting, our protocols allow any subset of the parties (with pairs of parties being a special case) to securely realize any desired functionality of their local inputs, and be guaranteed that security is preserved regardless of the activity in the rest of the network. This implies that security is preserved under concurrent composition of an unbounded number of protocol executions, it implies non-malleability with respect to arbitrary protocols, and more. Our constructions are in the common reference string model and rely on standard intractability assumptions.

We present the first cryptographically sound security proof of the well-known Needham-Schroeder-Lowe public-key protocol. More precisely, we show that the protocol is secure against arbitrary active attacks if it is implemented using provably secure cryptographic primitives. Although we achieve security under cryptographic definitions, our proof does not have to deal with probabilistic aspects of cryptography and is hence in the scope of current proof tools. The reason is that we exploit a recently proposed ideal cryptographic library, which has a provably secure cryptographic implementation. Besides establishing the cryptographic security of the Needham-Schroeder-Lowe protocol, our result also exemplifies the potential of this cryptographic library and paves the way for cryptographically sound verification of security protocols by means of formal proof tools.

The cryptographic concept of simulatability has become a salient technique for faithfully analyzing and proving security properties of arbitrary cryptographic protocols. We investigate the relationship between simulatability in synchronous and asynchronous frameworks by means of the formal models of Pfitzmann et. al., which are seminal in using this concept in order to bridge the gap between the formal-methods and the cryptographic community. We show that the synchronous model can be seen as a special case of the asynchronous one with respect to simulatability, i.e., we present an embedding between both models that we show to preserve simulatability. We show that this result allows for carrying over lemmas and theorems that rely on simulatability from the asynchronous model to its synchronous counterpart without any additional work. Hence future work can concentrate on the more general asynchronous case, without having to neglect the analysis of synchronous protocols.