We introduce the notion of quasi-Feistel network, which is generalization of the Feistel network, and contains the Lai-Massey scheme as an instance. We show that some of the works on the Feistel network, including the works of Luby-Rackoff, Patarin, Naor-Reingold and Piret, can be naturally extended to our setting. This gives a new proof for theorems of Vaudenay on the security of the Lai-Massey scheme, and also introduces for Lai-Massey a new construction of pseudorandom permutation, analoguous to the construction of Naor-Reingold using pairwise independent permutations. Also, we prove the birthday security of $(2b-1)$- and $(3b-2)$-round unbalanced quasi-Feistel networks with b branches against CPA and CPCA attacks, respectively. This answers an unsolved problem pointed out by Patarin et al.

We define a new notion of a reduced lattice, based on a quantity introduced in the LLL paper. We show that lattices reduced in this sense are simultaneously reduced in both their primal and dual. We show that the definition applies naturally to blocks, and therefore gives a new hierarchy of polynomial time algorithms for lattice reduction with fixed blocksize. We compare this hierarchy of algorithms to previous ones. We then explore algorithms to provably minimize the associated measure, and also some more efficient heuristics. Finally we comment on the initial investigations of applying our technique to the NTRU family of lattices.

We derive a new entropic quantum uncertainty relation involving min-entropy. The relation is tight and can be applied in various quantum-cryptographic settings. Protocols for quantum 1-out-of-2 Oblivious Transfer and quantum Bit Commitment are presented and the uncertainty relation is used to prove the security of these protocols in the bounded-quantum-storage model according to new strong security definitions. As another application, we consider the realistic setting of Quantum Key Distribution (QKD) against quantum-memory-bounded eavesdroppers. The uncertainty relation allows to prove the security of QKD protocols in this setting while tolerating considerably higher error rates compared to the standard model with unbounded adversaries. For instance, for the six-state protocol with one-way communication, a bit-flip error rate of up to 17% can be tolerated (compared to 13% in the standard model). Our uncertainty relation also yields a lower bound on the min-entropy key uncertainty against known-plaintext attacks when quantum ciphers are composed. Previously, the key uncertainty of these ciphers was only known with respect to Shannon entropy.

Ristenpart and Rogaway defined "mix" functions, which are used to mix inputs from two sets of equal size, and produce outputs from the same two sets, in an optimal way. These functions have a cryptographic application in the context of extending the domain of a block cipher. It was observed that mix functions could be constructed from orthogonal latin squares. In this paper, we give a simple, scalable construction for mix functions. We also consider a generalization of mix functions, in which the two sets need not be of equal size. These generalized mix functions turn out to be equivalent to an interesting type of combinatorial design which has not previously been studied. We term these "orthogonal equitable rectangles" and we construct them for all possible parameter situations, with a small number of exceptions and possible exceptions.

Micciancio defined a generalization of cyclic lattices, called ideal lattices. These lattices can be used in cryptosystems to decrease the number of parameters necessary to describe a lattice by a square root, making them more efficient. He proves that the computational intractability of classic lattice problems for these lattices gives rise to provably secure one-way and collision-resistant hash functions. This provable security relies on the assumption that reducing bases of ideal lattices is similar to reducing bases of random lattices. We give an indication that lattice problems in ideal lattices do not represent the general case by providing a distinguisher, which decides in time $O(n^4)$ whether a given basis of rank $n$ spans an ideal lattice or not. Using this algorithm we perform a statistical analysis for several dimensions and show that randomly generated lattices are practically never ideal.

In this work we re-visit the question of building cryptographic primitives that remain secure even when queried on inputs that depend on the secret key. This was investigated by Black, Rogaway, and Shrimpton in the context of randomized encryption schemes and in the random oracle model. We extend the investigation to deterministic symmetric schemes (such as PRFs and block ciphers) and to the standard model. We term this notion "security against key-dependent-input attack", or KDI-security for short. Our motivation for studying KDI security is the existence of significant real-world implementations of deterministic encryption (in the context of storage encryption) that actually rely on their building blocks to be KDI secure. We consider many natural constructions for PRFs, ciphers, tweakable ciphers and randomized encryption, and examine them with respect to their KDI security. We exhibit inherent limitations of this notion and show many natural constructions that fail to be KDI secure in the standard model, including some schemes that have been proven in the random oracle model. On the positive side, we demonstrate examples where some measure of KDI security can be provably achieved (in particular, we show such examples in the standard model).

Recently, 9-variable Boolean functions having nonlinearity 241, which is strictly greater than the bent concatenation bound of 240, have been discovered in the class of Rotation Symmetric Boolean Functions (RSBFs) by Kavut, Maitra and Yucel. In this paper, we present several 9-variable Boolean functions having nonlinearity of 242, which we obtain by suitably generalizing the classes of RSBFs and Dihedral Symmetric Boolean Functions (DSBFs).

Since Bellare and Ristenpart showed a multi-property preserving domain extension transform, the problem of the construction for multi-property hash functions has been reduced to that of the construction for multi-property compression functions. However, the Davies-Meyer compression function that is widely used for standard hash functions is not a multi-property compression function. That is, in the ideal cipher model, the Davies-Meyer compression function is collision resistant, but it is not indifferentiable from a random oracle. In this paper, we show that the compression function proposed by Lai and Massey is a multi-property compression function. In addition, we show that the simplified version of the Lai-Massey compression function is also a multi-property compression function. The use of these compression functions enables us to construct multi-property hash functions by the multi-property preserving domain extension transform.

We extend the notion of perfect secret sharing scheme for access structures with infinitely many participants. In particular we investigate cases when the participants are the vertices of an (infinite) graph, and the minimal qualified sets are the edges. The (worst case) {\it information ratio} of an access structure is the largest lower bound on the amount of information some participant must remember for each bit in the secret -- just the inverse of the information rate. We determine this value for several infinite graphs: infinite path, two-dimensional square and honeycomb lattices; and give upper and lower bounds on the ratio for the triangular lattice. It is also shown that the information ratio is not necessarily {\em local}, i.e.~all finite spanned subgraphs have strictly smaller ratio than the whole graph. We conclude the paper by posing several open problems.

We devise an abstraction of zero-knowledge protocols that is accessible to a fully mechanized analysis. The abstraction is formalized within the applied pi-calculus using a novel equational theory that abstractly characterizes the cryptographic semantics of zero-knowledge proofs. We present an encoding from the equational theory into a convergent rewriting system that is suitable for the automated protocol verifier ProVerif. The encoding is sound and fully automated. We successfully used ProVerif to obtain the first mechanized analysis of the Direct Anonymous Attestation (DAA) protocol. The analysis in particular required us to devise novel abstractions of sophisticated cryptographic security definitions based on interactive games.

The recent algebraic attacks have received a lot of attention in cryptographic literature. The algebraic immunity of a Boolean function quantifies its resistance to the standard algebraic attacks of the pseudo-random generators using it as a nonlinear filtering or combining function. Very few results have been found concerning its relation with the other cryptographic parameters or with the $r$-th order nonlinearity. As recalled by Carlet at Crypto'06, many papers have illustrated the importance of the $r$th-order nonlinearity profile (which includes the first-order nonlinearity). The role of this parameter relatively to the currently known attacks has been also shown for block ciphers. Recently, two lower bounds involving the algebraic immunity on the $r$th-order nonlinearity have been shown by Carlet et \emph{al}. None of them improves upon the other one in all situations. In this paper, we prove a new lower bound on the $r$th-order nonlinearity profile of Boolean functions, given their algebraic immunity, that improves significantly upon one of these lower bounds for all orders and upon the other one for low orders.

We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from one-way permutations, and even from trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme due to Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). As a corollary, we derive similar tight lower bounds for several other cryptographic protocols, such as single-server private information retrieval, interactive hashing, and oblivious transfer that guarantees statistical security for one of the parties. Our techniques extend the collision-finding oracle due to Simon (EUROCRYPT '98) to the setting of interactive protocols (our extension also implies an alternative proof for the main property of the original oracle). In addition, we substantially extend the reconstruction paradigm of Gennaro and Trevisan (FOCS '00). In both cases, our extensions are quite delicate and may be found useful in proving additional black-box separation results.

Algebraic immunity of Boolean functions is a very important concept in recently introduced algebraic attacks of stream cipher. For a $n$-variable Boolean function $f$, the algebraic immunity $AI_n(f)$ takes values in $\{0,1,\ldots,\lceil\frac{n}{2}\rceil\}$. For every $k$ in this range, denote $B_{n,k}$ the set of all $n$-variable Boolean functions with algebraic immunity $k$, and we know that $B_{n,k}$ is always non-empty. According to the algebraic immunity, we can form a hierarchy of Boolean functions. Trivially, $|B_{n,0}|=2$. In general, about this integer sequence $|B_{n,k}|,\quad k=0,1,\ldots,\lceil\frac{n}{2}\rceil,$ very few results are known. In this paper, we show an explicit formula for $|B_{n,1}|$. That is, we obtain an exact formula for the number of Boolean functions with algebraic immunity one. This is the first exact formula for the terms in the above integer sequence. We also give a tight upper bound for nonlinearity of Boolean functions with algebraic immunity one.

The standard symbolic, deducibility-based notions of secrecy are in general insufficient from a cryptographic point of view, especially in presence of hash functions. In this paper we devise and motivate a more appropriate secrecy criterion which exactly captures a standard cryptographic notion of secrecy for protocols involving public-key enryption and hash functions: protocols that satisfy it are computationally secure while any violation of our criterion directly leads to an attack. Furthermore, we prove that our criterion is decidable via an NP decision procedure. Our results hold for standard security notions for encryption and hash functions modeled as random oracles.

Some cryptographic tasks, such as contract signing and other related tasks, need to ensure complex, branching time security properties. When defining such properties one needs to deal with subtle problems regarding the scheduling of non-deterministic decisions, the delivery of messages sent on resilient (non-adversarially controlled) channels, fair executions (executions where no party, both honest and dishonest, is unreasonably precluded to perform its actions), and defining strategies of adversaries against all possible non-deterministic choices of parties and arbitrary delivery of messages via resilient channels. These problems are typically not addressed in cryptographic models and these models therefore do not suffice to formalize branching time properties, such as those required of contract signing protocols. In this paper, we develop a cryptographic model that deals with all of the above problems. One central feature of our model is a general definition of fair scheduling which not only formalizes fair scheduling of resilient channels but also fair scheduling of actions of honest and dishonest principals. Based on this model and the notion of fair scheduling, we provide a definition of a prominent branching time property of contract signing protocols, namely balance, and give the first \emph{cryptographic} proof that the Asokan-Shoup-Waidner two-party contract signing protocol is balanced.

Randomness extraction is of fundamental importance for information-theoretic cryptography. It allows to transform a raw key about which an attacker has some limited knowledge into a fully secure random key, on which the attacker has essentially no information. We show a new randomness-extraction technique which works also in case where the attacker has quantum information on the raw key. Randomness extraction is done by XORing a so-called delta-biased mask to the raw key. Up to date, only very few techniques are known to work against a quantum attacker, much in contrast to the classical (non-quantum) setting, which is much better understood and for which a vast amount of different techniques for randomness extraction are known. We show two applications of the new result. We first show how to encrypt a long message with a short key, information-theoretically secure against a quantum attacker, provided that the attacker has enough quantum uncertainty on the message. This generalizes the concept of entropically-secure encryption to the case of a quantum attacker. As a second application, we show how the new randomness-extraction technique allows to do error-correction without leaking partial information to a quantum attacker. Such a technique is useful in settings where the raw key may contain errors, since standard error-correction techniques may provide the attacker with information on, say, a secret key that was used to obtain the raw key.

We explore the idea of creating a hash function that produces an $s$-bit digest from a compression function with an $n$-bit output, where $s > n$. % where $s\le 2^{n/2}n$.This is accomplished by truncating a hash function with a digest size of $\ell n$-bits. Our work answers the question of how large $\ell$ can be while creating a digest of $sn$-bits securely. We prove that our construction is secure with respect to preimage resistance and collision resistance for $s \le 2^{n/2}n$.

The abstraction of cryptographic operations by term algebras, called Dolev-Yao models or symbolic cryptography, is essential in almost all tool-supported methods for proving security protocols. Recently significant progress was made -- using two conceptually different approaches -- in proving that Dolev-Yao models can be sound with respect to actual cryptographic realizations and security definitions. One such approach is grounded on the notion of simulatability, which constitutes a salient technique of Modern Cryptography with a longstanding history for a variety of different tasks. The other approach strives for the so-called mapping soundness -- a more recent technique that is tailored to the soundness of specific security properties in Dolev-Yao models, and that can be established using more compact proofs. Typically, both notions of soundness for similar Dolev-Yao models are established separately in independent papers. In this paper, the two approaches are related for the first time. Our main result is that simulatability soundness entails mapping soundness provided that both approaches use the same cryptographic implementation. Interestingly, this result does not dependent on details of the simulator, which translates between cryptographic implementations and their Dolev-Yao abstractions in simulatability soundness. Hence, future research may well concentrate on simulatability soundness whenever applicable, and resort to mapping soundness in those cases where simulatability soundness is too strong a notion.

We introduce a variant of the random oracle model where oracle-dependent auxiliary input is allowed. In this setting, the adversary gets an auxiliary input that can contain information about the random oracle. Using simple examples we show that this model should be preferred over the classical variant where the auxiliary input is independent of the random oracle. In the presence of oracle-dependent auxiliary input, the most important proof technique in the random oracle model - lazy sampling - does not apply directly. We present a theorem and a variant of the lazy sampling technique that allows one to perform proofs in the new model almost as easily as in the old one. As an application of our approach and to illustrate how existing proofs can be adapted, we prove that RSA-OAEP is IND-CCA2 secure in the random oracle model with oracle-dependent auxiliary input.

Statistical zero-knowledge (SZK) properties play an important role in designing cryptographic protocols that enforce honest behavior while maintaining privacy. This paper presents a novel approach for verifying SZK properties, using recently developed techniques based on approximate simulation relations. We formulate statistical indistinguishability as an implementation relation in the Task-PIOA framework, which allows us to express computational restrictions. The implementation relation is then proven using approximate simulation relations. This technique separates proof obligations into two categories: those requiring probabilistic reasoning, as well as those that do not. The latter is a good candidate for mechanization. We illustrate the general method by verifying the SZK property of the well-known identification protocol of Girault, Poupard and Stern.

We present the dynamic cryptographic hash function, a new type of hash function which takes two parameters instead of one. The additional parameter, the security parameter, specifies the internal workings and size of the digest produced. We provide a formal definitions for a dynamic cryptographic hash function and for the traditional security properties, modified for dynamic hash functions. Two additional properties, security parameter collision resistance and digest resistance, are also defined. The additional properties are motivated by scenarios where a dynamic hash functions more cleanly provides a solution to a typical cryptographic problem.

We investigate the security of protocols with logarithmic communication complexity. We show that for the security definitions with environment, i.e., Reactive Simulatability and Universal Composability, computational security of logarithmic protocols implies statistical security. The same holds for advantage-based security definitions as commonly used for individual primitives. While this matches the folklore that logarithmic protocols cannot be computationally secure unless they are already statistically secure, we show that under realistic complexity assumptions, this folklore does surprisingly not hold for the stand-alone model without auxiliary input, i.e., there are logarithmic protocols that are statistically insecure but computationally secure in this model. The proof is conducted by showing how to transform an instance of an NP-complete problem into a protocol with two properties: There exists an adversary such that the protocol is statistically insecure in the stand-alone model, and given such an adversary we can find a witness for the problem instance, hence yielding a computationally secure protocol assuming the hardness of finding a witness. The proof relies on a novel technique that establishes a link between cryptographic definitions and foundations of computational geometry, which we consider of independent interest.

We define \emph{reactive simulatability} for general asynchronous systems. Roughly, simulatability means that a real system implements an ideal system (specification) in a way that preserves security in a general cryptographic sense. Reactive means that the system can interact with its users multiple times, e.g., in many concurrent protocol runs or a multi-round game. In terms of distributed systems, reactive simulatability is a type of refinement that preserves particularly strong properties, in particular confidentiality. A core feature of reactive simulatability is \emph{composability}, i.e., the real system can be plugged in instead of the ideal system within arbitrary larger systems; this is shown in follow-up papers, and so is the preservation of many classes of individual security properties from the ideal to the real systems. A large part of this paper defines a suitable system model. It is based on probabilistic IO automata (PIOA) with two main new features: One is \emph{generic distributed scheduling}. Important special cases are realistic adversarial scheduling, procedure-call-type scheduling among colocated system parts, and special schedulers such as for fairness, also in combinations. The other is the definition of the \emph{reactive runtime} via a realization by Turing machines such that notions like polynomial-time are composable. The simple complexity of the transition functions of the automata is not composable. As specializations of this model we define security-specific concepts, in particular a separation beween honest users and adversaries and several trust models. The benefit of IO automata as the main model, instead of only interactive Turing machines as usual in cryptographic multi-party computation, is that many cryptographic systems can be specified with an ideal system consisting of only one simple, deterministic IO automaton without any cryptographic objects, as many follow-up papers show. This enables the use of classic formal methods and automatic proof tools for proving larger distributed protocols and systems that use these cryptographic systems.

Simulatability has established itself as a salient notion for defining and proving the security of cryptographic protocols since it entails strong security and compositionality guarantees, which are achieved by universally quantifying over all environmental behaviors of the analyzed protocol. As a consequence, however, protocols that are secure except for certain environmental behaviors are not simulatable, even if these behaviors are efficiently identifiable and thus can be prevented by the surrounding protocol. We propose a relaxation of simulatability by conditioning the permitted environmental behaviors, i.e., simulation is only required for environmental behaviors that fulfill explicitly stated constraints. This yields a more fine-grained security definition that is achievable i) for several protocols for which unconditional simulatability is too strict a notion or ii) at lower cost for the underlying cryptographic primitives. Although imposing restrictions on the environment destroys unconditional composability in general, we show that the composition of a large class of conditionally simulatable protocols yields protocols that are again simulatable under suitable conditions. This even holds for the case of cyclic assume-guarantee conditions where protocols only guarantee suitable behavior if they themselves are offered certain guarantees. Furthermore, composing several commonly investigated protocol classes with conditionally simulatable subprotocols yields protocols that are again simulatable in the standard, unconditional sense.

Automated tools such as model checkers and theorem provers for the analysis of security protocols typically abstract from cryptography by Dolev-Yao models, i.e., abstract term algebras replace the real cryptographic operations. Recently it was shown that in essence this approach is cryptographically sound for certain operations like signing and encryption. The strongest results show this in the sense of blackbox reactive simulatability (BRSIM)/UC with only small changes to both Dolev-Yao models and natural implementations. This notion essentially means the preservation of arbitrary security properties under active attacks in arbitrary protocol environments. We show that it is impossible to extend the strong BRSIM/UC results to usual Dolev-Yao models of hash functions in the general case. These models treat hash functions as free operators of the term algebra. In contrast, we show that these models are sound in the same strict sense in the random oracle model of cryptography. For the standard model of cryptography, we also discuss several conceivable restrictions to the Dolev-Yao models and classify them into possible and impossible cases.

We investigate the decoding problem of Reed-Solomon (RS) Codes, also known as the Polynomial Reconstruction Problem (PR), from a cryptographic hardness perspective. Namely, we deal with PR instances with parameter choices for which decoding is not known to be feasibly solvable and where part of the solution polynomial is the hidden input. We put forth a natural decisional intractability assumption that relates to this decoding problem: distinguishing between a single randomly chosen error-location and a single randomly chosen non-error location for a given corrupted RS codeword with random noise. We prove that under this assumption, PR-instances are entirely pseudorandom, i.e., they are indistinguishable from random vectors over the underlying finite field. Moreover, under the same assumption we show that it is hard to extract any partial information related to the hidden input encoded by the corrupted PR-instance, i.e., PR-instances hide their message polynomial solution in the semantic security sense. The above results lay a framework for the exploitation of PR as an intractability assumption for provable security of cryptographic primitives. Based on this framework, we present provably secure cryptographic constructions for (i) a pseudorandom extender, (ii) a semantically secure version of the Oblivious Polynomial Evaluation Protocol, and (iii) a stateful cipher with a set of interesting properties that include: semantic security, forward secrecy, error-correcting decryption and an array of random self-reducibility properties with respect to the plaintext choice, key choice and partial domain choice.

Braid cryptosystem was proposed in CRYPTO 2000 as an alternate public-key cryptosystem. The security of this system is based upon the conjugacy problem in braid groups. Since then, there have been several attempts to break the braid cryptosystem by solving the conjugacy problem in braid groups. In this paper, we first survey all the major attacks on the braid cryptosystem and conclude that the attacks were successful because the current ways of random key generation almost always result in weaker instances of the conjugacy problem. We then propose several alternate ways of generating hard instances of the conjugacy problem for use braid cryptography.

We propose the idea of building a secure hash using quadratic or higher degree multivariate polynomials over a finite field as the compression function, whose security relies on simple hard questions. We analyze some security properties and potential feasibility, where the compression functions are randomly chosen high-degree polynomials. Next, we propose to improve on the efficiency of the system by using some specially designed polynomials using composition of maps and certain sparsity property, where the security of the system would then relies on stronger assumptions.

We introduce a new infinite family of multiterm functions that are APN on $GF(2^{2k})$ for odd $k$.

It is known that string (1,2)-OT and Rabin's OT are equivalent. However, two steps are required to construct a string $(1,2)$-OT from Rabin's OT. The first step is a construction of a bit (1,2)-OT from Rabin's OT, and the second step is a construction of a string $(1,2)$-OT from the bit (1,2)-OT. No direct reduction is known. In this paper, we show a direct reduction of string (1,2)-OT to Rabin's OT by using a deterministic randomness extractor. Our reduction is much more efficient than the previous two-step reduction.

We give a complexity-theoretic characterization of the class of problems in NP having zero-knowledge argument systems. This characterization is symmetric in its treatment of the zero knowledge and the soundness conditions, and thus we deduce that the class of problems in NP intersect coNP having zero-knowledge arguments is closed under complement. Furthermore, we show that a problem in NP has a *statistical* zero-knowledge argument system if and only if its complement has a computational zero-knowledge *proof* system. What is novel about these results is that they are *unconditional*, i.e., do not rely on unproven complexity assumptions such as the existence of one-way functions. Our characterization of zero-knowledge arguments also enables us to prove a variety of other unconditional results about the class of problems in NP having zero-knowledge arguments, such as equivalences between honest-verifier and malicious-verifier zero knowledge, private coins and public coins, inefficient provers and efficient provers, and non-black-box simulation and black-box simulation. Previously, such results were only known unconditionally for zero-knowledge *proof systems*, or under the assumption that one-way functions exist for zero-knowledge argument systems.

In a series of papers, Küsters et al. investigated the relationships between various notions of simulation-based security. Two main factors, the placement of a ``master process'' and the existence of ``forwarder processes'', were found to affect the relationship between different definitions. In this extended abstract, we add a new dimension to the analysis of simulation-based security, namely, the scheduling of concurrent processes. We show that, when we move from sequential scheduling (as used in previous studies) to task-based nondeterministic scheduling, the same syntactic definition of security gives rise to incomparable semantic notions of security. Under task-based scheduling, the hierarchy based on placement of ``master process'' is no longer relevant, because no such designation is necessary to obtain meaningful runs of a system. On the other hand, the existence of ``forwarder processes'' remains an important factor.

Let $p$ be a prime and let $E(\F_p)$ be an elliptic curve defined over the finite field $\F_p$ of $p$ elements. For a given point $G \in E(\F_p)$ the linear congruential genarator on elliptic curves (EC-LCG) is a sequence $(U_n)$ of pseudorandom numbers defined by the relation $$ U_n=U_{n-1}\oplus G=nG\oplus U_0,\quad n=1,2,\ldots,$$ where $\oplus$ denote the group operation in $E(\F_p)$ and $U_0 \in E(\F_p)$ is the initial value or seed. We show that if $G$ and sufficiently many of the most significants bits of two consecutive values $U_n, U_{n+1}$ of the EC-LCG are given, one can recover the seed $U_0$ (even in the case where the elliptic curve is private) provided that the former value $U_n$ does not lie in a certain small subset of exceptional values. We also estimate limits of a heuristic approach for the case where $G$ is also unknown. This suggests that for cryptographic applications EC-LCG should be used with great care. Our results are somewhat similar to those known for the linear and non-linear pseudorandom number congruential generator.

In this paper we present that some statistical properties of points on elliptic curve can be used to form new equivalence classes. This can have an impact on solving discrete logarithm (ECDLP) owing to the reduction of the number of points among which a logarithm is searched to points of particular features. It should lead to an improvement of the Pollard-rho algorithm.

An obfuscation O of a function F should satisfy two requirements: firstly, using O it should be possible to evaluate F; secondly, O should not reveal anything about F that cannot be learnt from oracle access to F. Several definitions for obfuscation exist. However, most of them are either too weak for or incompatible with cryptographic applications, or have been shown impossible to achieve, or both. We give a new definition of obfuscation and argue for its reasonability and usefulness. In particular, we show that it is strong enough for cryptographic applications, yet we show that it has the potential for interesting positive results. We illustrate this with the following two results: - If the encryption algorithm of a secure secret-key encryption scheme can be obfuscated according to our definition, then the result is a secure public-key encryption scheme. - A uniformly random point function can be easily obfuscated according to our definition, by simply applying a one-way permutation. Previous obfuscators for point functions, under varying notions of security, are either probabilistic or in the random oracle model (but work for arbitrary distributions on the point function). On the negative side, we show that - Following Hada and Wee, any family of deterministic functions that can be obfuscated according to our definition must already be ``approximately learnable.'' Thus, many deterministic functions cannot be obfuscated. However, a probabilistic functionality such as a probabilistic secret-key encryption scheme can potentially be obfuscated. In particular, this is possible for a public-key encryption scheme when viewed as a secret-key scheme. - There exists a secure probabilistic secret-key encryption scheme that cannot be obfuscated according to our definition. Thus, we cannot hope for a general-purpose cryptographic obfuscator for encryption schemes.

The black-box field (BBF) extraction problem is, for a given field $\F$, to determine a secret field element hidden in a black-box which allows to add and multiply values in $\F$ in the box and which reports only equalities of elements in the box. This problem is of cryptographic interest for two reasons. First, for $\F=\F_p$ it corresponds to the generic reduction of the discrete logarithm problem to the computational Diffie-Hellman problem in a group of prime order $p$. Second, an efficient solution to the BBF problem proves the inexistence of certain field-homomorphic encryption schemes whose realization is an interesting open problems in algebra-based cryptography. BBFs are also of independent interest in computational algebra. In the previous literature, BBFs had only been considered for the prime field case. In this paper we consider a generalization of the extraction problem to BBFs that are extension fields. More precisely we discuss the representation problem defined as follows: For given generators $g_1,\ldots,g_d$ algebraically generating a BBF and an additional element $x$, all hidden in a black-box, express $x$ algebraically in terms of $g_1,\ldots,g_d$. We give an efficient algorithm for this representation problem and related problems for fields with small characteristic (e.g. $\F=\F_{2^n}$ for some $n$). We also consider extension fields of large characteristic and show how to reduce the representation problem to the extraction problem for the underlying prime field. These results imply the inexistence of field-homomorphic (as opposed to only group-homomorphic, like RSA) one-way permutations for fields of small characteristic.

In this paper we present a new algorithm for finding small roots of a system of multivariate polynomials over the integers based on lattice reduction techniques. Our simpler heuristic method is inspired in algorithms for predicting pseudorandom numbers, and it can be considered as another variant of Coppersmith's method for finding small solutions of integer bivariate polynomials. We also apply the method to the well known problem of factoring an integer when we know the high-order bits of one of the factors.

The problem of computing best low order approximations of Boolean functions is treated in this paper. We focus on the case of best quadratic approximations of a wide class of cubic functions of arbitrary number of variables, and provide formulas for their efficient calculation. Our methodology is developed upon Shannon's expansion formula and properties of best affine approximations of quadratic functions, for which we prove formulas for their direct computation, without use of the Walsh-Hadamard transform. The notion of nonquadricity is introduced, as the minimum distance from all quadratic functions, and cubic functions that achieve the maximum possible nonquadricity are determined, leading to a lower bound for the covering radius of second order Reed-Muller code $\mthf{R}(2,n)$ in $\mthf{R}(3,n)$.

There is a rarely mentioned foundational problem involving collision-resistant hash-functions: common constructions are keyless, but formal definitions are keyed. The discrepancy stems from the fact that a function H:{0,1}^* -> {0,1}^n always admits an efficient collision-finding algorithm, it's just that us human beings might be unable to write the program down. We explain a simple way to sidestep this difficulty that avoids having to key our hash functions. The idea is to state theorems in a way that prescribes an explicitly-given reduction, normally a black-box one. We illustrate this approach using well-known examples involving digital signatures, pseudorandom functions, and the Merkle-Damgard construction.

Bent functions are important cryptographic Boolean functions. In order to enumerate eight-variable bent functions, we solve the following three key problems. Firstly, under the action of $AGL(7,2)$, we almost completely classify $R(4,7)/R(2,7)$. Secondly, we construct all seven-variable \emph{plateaued} functions from the orbits of $R(4,7)/R(2,7)$. Thirdly, we present a fast algorithm to expand \emph{plateaued} function into bent functions. Based on the results above, it is feasible to enumerate eight-variable bent functions in practice.

In this paper, we propose a new method for designing public key cryptosystems based on general non-commutative rings. The key idea of our proposal is that for a given non-commutative ring, we can define polynomials and take them as the underlying work structure. By doing so, it is easy to implement Diffie-Helman-like key exchange protocol. And consequently, ElGamal-like cryptosystems can be derived immediately. Moreover, we show how to extend our method to non-commutative groups (or semi-groups).

The Ate pairing and the twisted Ate pairing for ordinary elliptic curves which are generalizations of the $\eta_T$ pairing for supersingular curves have previously been proposed. It is not necessarily the case that both pairings are faster than the Tate pairing. In this paper we propose optimized versions of the Ate and twisted Ate pairings with the loop reduction method and show that both pairings are always at least as fast as the Tate pairing. We also provide suitable families of elliptic curves that our optimized Ate and optimized twisted Ate pairings can be computed with half the loop length compared to the Tate pairing.

In this paper we present a $p$-adic algorithm to compute the zeta function of a nondegenerate curve over a finite field using Monsky-Washnitzer cohomology. The paper vastly generalizes previous work since all known cases, e.g. hyperelliptic, superelliptic and $C_{ab}$ curves, can be transformed to fit the nondegenerate case. For curves with a fixed Newton polytope, the property of being nondegenerate is generic, so that the algorithm works for almost all curves with given Newton polytope. For a genus $g$ curve over $\FF_{p^n}$, the expected running time is $\widetilde{O}(n^3 g^6 + n^2 g^{6.5})$, whereas the space complexity amounts to $\widetilde{O}(n^3 g^4)$, assuming $p$ is fixed.

In the research of the relationship between the formal and the computational view of cryptography, a recent approach uses static equivalence from cryptographic pi calculi as a notion of formal indistinguishability. Previous work has shown that this yields the soundness of natural interpretations of some interesting equational theories, such as certain cryptographic operations and a theory of XOR. In this paper however, we argue that static equivalence is too coarse for sound interpretations of equational theories in general. We show some explicit examples how static equivalence fails to work in interesting cases. To fix this problem, we propose a notion of formal indistinguishability that is more flexible than static equivalence. We provide a general framework along with general theorems, and then discuss how this new notion works for the explicit examples where static equivalence failed to ensure soundness. We also improve the treatment by using ordered sorts in the formal view, and by allowing arbitrary probability distributions of the interpretations.

Hash Chains are used extensively in various cryptographic systems such as one-time passwords, server supported signatures, secure address resolution, certificate revocation, micropayments etc. However, currently they suffer from the limitation that they have a finite number of links which when exhausted requires the system to be re-initialized. In this paper, we present a new kind of hash chain which we call a Re-initializable Hash Chain (RHC). A RHC has the property that if its links are exhausted, it can be securely re-initialized in a non-repudiable manner to result in another RHC. This process can be continued indefinitely to give rise to an infinite length hash chain, or more precisely, an infinite number of finite length hash chains tied together. Finally we illustrate how a conventional hash chain (CHC) may be profitable replaced with a RHC in cryptographic systems.

This essay relates to a recent article of Koblitz & Menezes (Cryptology ePrint Report 2004/152) that ``criticizes several typical `provable security' results'' and argues that the ``theorem-proof paradigm of theoretical mathematics is often of limited relevance'' to cryptography. Although it feels ridiculous to answer such a claim, we undertake to do so in this essay. In particular, we point out some of the fundamental philosophical flaws that underly the said article and some of its misconceptions regarding theoretical research in Cryptography in the last quarter of a century.

The integer addition is often applied in ciphers as a cryptographic means. In this paper we will present some results about the linear approximating for the integer addition.

A random system is the abstraction of the input-output behavior of any kind of discrete system, in particular cryptographic systems. Many aspects of cryptographic security analyses and proofs can be seen as the proof that a certain random system (e.g. a block cipher) is indistinguishable from an ideal system (e.g. a random permutation), for different types of distinguishers. This paper presents a new generic approach to proving upper bounds on the distinguishing advantage of a combined system, assuming upper bounds of various types on the component systems. For a general type of combination operation of systems (including the combination of functions or the cascade of permutations), we prove two amplification theorems. The first is a direct-product theorem, similar in spirit to the XOR-Lemma: The distinguishing advantage (or security) of the combination of two (possibly stateful) systems is twice the product of the individual distinguishing advantages, which is optimal. The second theorem states that the combination of systems is secure against some strong class of distinguishers, assuming only that the components are secure against some weaker class of attacks. As a corollary we obtain tight bounds on the adaptive security of the cascade and parallel composition of non-adaptively (or only random-query) secure component systems. A key technical tool of the paper is to show a tight two-way correspondence, previously only known to hold in one direction, between the distinguishing advantage of two systems and the probability of provoking an appropriately defined event on one of the systems.

We address the question of whether or not semantically secure public-key encryption primitives imply the existence of chosen ciphertext attack (CCA) secure primitives. We show a black-box separation, using the methodology introduced by Impagliazzo and Rudich, for a large non-trivial class of constructions. In particular, we show that if the proposed CCA construction's decryption algorithm does not query the semantically secure primitive's encryption algorithm, then the proposed construction cannot be CCA secure

We demonstrate an \emph{average-case} problem which is as hard as finding $\gamma(n)$-approximate shortest vectors in certain $n$-dimensional lattices in the \emph{worst case}, where $\gamma(n) = O(\sqrt{\log n})$. The previously best known factor for any class of lattices was $\gamma(n) = \tilde{O}(n)$. To obtain our results, we focus on families of lattices having special algebraic structure. Specifically, we consider lattices that correspond to \emph{ideals} in the ring of integers of an algebraic number field. The worst-case assumption we rely on is that in some $\ell_p$ length, it is hard to find approximate shortest vectors in these lattices, under an appropriate form of preprocessing of the number field. Our results build upon prior works by Micciancio (FOCS 2002), Peikert and Rosen (TCC 2006), and Lyubashevsky and Micciancio (ICALP 2006). For the connection factors $\gamma(n)$ we achieve, the corresponding \emph{decisional} promise problems on ideal lattices are \emph{not} known to be NP-hard; in fact, they are in P. However, the \emph{search} approximation problems still appear to be very hard. Indeed, ideal lattices are well-studied objects in computational number theory, and the best known algorithms for them seem to perform \emph{no better} than the best known algorithms for general lattices. To obtain the best possible connection factor, we instantiate our constructions with infinite families of number fields having constant \emph{root discriminant}. Such families are known to exist and are computable, though no efficient construction is yet known. Our work motivates the search for such constructions. Even constructions of number fields having root discriminant up to $O(n^{2/3-\epsilon})$ would yield connection factors better than the current best of~$\tilde{O}(n)$.

Most cryptographic primitives require randomness (for example, to generate their secret keys). Usually, one assumes that perfect randomness is available, but, conceivably, such primitives might be built under weaker, more realistic assumptions. This is known to be true for many authentication applications, when entropy alone is typically sufficient. In contrast, all known techniques for achieving privacy seem to fundamentally require (nearly) perfect randomness. We ask the question whether this is just a coincidence, or, perhaps, privacy inherently requires true randomness? We completely resolve this question for the case of (information-theoretic) private-key encryption, where parties wish to encrypt a b-bit value using a shared secret key sampled from some imperfect source of randomness S. Our main result shows that if such n-bit source S allows for a secure encryption of b bits, where b>log n, then one can deterministically extract nearly b almost perfect random bits from S. Further, the restriction that b>log n is nearly tight: there exist sources S allowing one to perfectly encrypt (log n - loglog n) bits, but not to deterministically extract even a single slightly unbiased bit. Hence, to a large extent, *true randomness is inherent for encryption*: either the key length must be exponential in the message length b, or one can deterministically extract nearly b almost unbiased random bits from the key. In particular, the *one-time pad scheme is essentially universal*. Our technique also extends to related *computational* primitives which are perfectly-binding, such as perfectly-binding commitment and computationally secure private- or public-key encryption, showing the necessity to efficiently extract almost b *pseudorandom* bits.

In \cite{BCS96}, the concept of zigzag function was introduced in relation with oblivious transfer \cite{R84}. This subject has later been studied in \cite{S99,DS01,CFW01}. The definition of zigzag functions has been generalized to $s$-zigzag functions for $2\leq s\leq n$. It turns out that zigzag functions are also interesting combinatorial objects, thanks to their relation with self-intersecting codes and orthogonal arrays \cite{BCS96,S99}. The aim of this work is to formulate these objects with respect to a new metric following the approach proposed in \cite{BNNP} and to investigate the properties of the generalized zigzag functions and related concepts.

We give a construction of statistically-hiding commitment schemes (ones where the hiding property holds information theoretically), based on the minimal cryptographic assumption that one-way functions exist. Our construction employs two-phase commitment schemes, recently constructed by Nguyen, Ong and Vadhan (FOCS `06), and universal one-way hash functions introduced and constructed by Naor and Yung (STOC `89) and Rompel (STOC `90).

Authentication codes provide message integrity guarantees in an information theoretic sense within a symmetric key setting. Information theoretic bounds on the success probability of an adversary who has access to previously authenticated messages have been derived by Simmons and Rosenbaum, among others. In this paper we consider a strong attack scenario where the adversary is adaptive and has access to authentication and verification oracles. We derive information theoretic bounds on the success probability of the adversary and on the key size of the code. This brings the study of unconditionally secure authentication systems on a par with the study of computationally secure ones. We characterize the codes that meet these bounds and compare our result with the earlier ones.

The common random string model permits the construction of cryptographic protocols that are provably impossible to realize in the standard model. In this model, a trusted party generates a random string and gives it to all parties in the protocol. However, the introduction of such a third party should set alarm bells going off: Who is this trusted party? Why should we trust that the string is random? Even if the string is uniformly random, how do we know it does not leak private information to the trusted party? The very point of doing cryptography in the first place is to prevent us from trusting the wrong people with our secrets. In this paper, we propose the more realistic multi-string model. Instead of having one trusted authority, we have several authorities that generate random strings. We do not trust any single authority, we only assume a majority of them generate the random string honestly. We demonstrate the use of this model for two fundamental cryptographic taks. We define non-interactive zero-knowledge in the multi-string model and construct NIZK proofs in the multi-string model. We also consider multi-party computation and show that any functionality can be securely realized in the multi-string model.

Designing public key encryption schemes withstanding chosen ciphertext attacks, which is the highest security level for such schemes, is generally perceived as a delicate and intricate task, and for good reason. In the standard model, there are essentially three well-known but quite involved approaches. This state of affairs is to be contrasted with the situation for semantically secure encryption schemes, a much weaker security notion that only guarantees security in the absence of active attack but that appears to be much easier to fulfill, both conceptually and practically. Thus, the boundary between passive attack and active attack seems to make up the dividing line between which security levels are relatively easily achieved and which are not. Our contributions are two-fold. First, we show a simple, efficient black-box construction of a public key encryption scheme withstanding chosen ciphertext attack from any given semantically secure one. Our scheme is $q$-bounded in the sense that security is only guaranteed if the adversary makes at most $q$ adaptive chosen ciphertext queries. Here, $q$ is an arbitrary polynomial that is fixed in advance in the key-generation. Our work thus shows that whether or not the number of active, adversarial queries is known in advance is the dividing line, and not passive versus active attack. In recent work, Gertner, Malkin and Myers show that such black-box reductions are impossible if instead $q$ is a polynomial that only depends on the adversary. Thus, in a sense, our result appears to be the best black-box result one can hope for. Second, we give a non-blackbox reduction from bounded chosen ciphertext security to semantic security where the length of the public/secret keys and ciphertexts drops from quadratic to linear in $q$, compared to our black-box construction. This latter scheme, however, is only of theoretical interest as it uses general NP-reductions, and our blackbox construction is in fact much more practical.

There is a vast body of work on {\em implementing} anonymous communication. In this paper, we study the possibility of using anonymous communication as a {\em building block}, and show that one can leverage on anonymity in a variety of cryptographic contexts. Our results go in two directions. \begin{itemize} \item{\bf Feasibility.} We show that anonymous communication over {\em insecure} channels can be used to implement unconditionally secure point-to-point channels, and hence general multi-party protocols with unconditional security in the presence of an honest majority. In contrast, anonymity cannot be generally used to obtain unconditional security when there is no honest majority. \item{\bf Efficiency.} We show that anonymous channels can yield substantial efficiency improvements for several natural secure computation tasks. In particular, we present the first solution to the problem of private information retrieval (PIR) which can handle multiple users while being close to optimal with respect to {\em both} communication and computation. A key observation that underlies these results is that {\em local randomization} of inputs, via secret-sharing, when combined with the {\em global mixing} of the shares, provided by anonymity, allows to carry out useful computations on the inputs while keeping the inputs private. \end{itemize}

Many cryptographic protocols secure against malicious players use specially designed cryptographic tools. Essentially, these special tools function much like less-expensive tools, but give extra `powers' to a reduction or simulation algorithm. Using these powers, cryptographers can construct a proof of security using standard techniques. However, these powers are not available to either the honest parties or the adversary. In a large class of protocols, by replacing the expensive, specially designed cryptographic tool with a corresponding less-expensive tool, we can improve the protocol's efficiency without changing the functionality available to either the adversary or the honest parties. The key motivating question we address in this paper is whether the new, `substituted' protocol is still secure. We introduce a framework for reasoning about this question. Our framework uses translators: special purpose oracles that map outputs of one cryptographic tool to corresponding outputs of a different tool. Translators are similar to, but generally weaker than, the ``angels'' of Prabhakaran and Sahai. We introduce the notion of substitution-friendly protocols and show that such protocols remain secure after substitution in our framework. We also leverage existing proofs of security; there is no need to re-prove security from scratch. We demonstrate our framework with a non-interactive non-malleable bit commitment protocol.

This note points out a gap between two natural formulations of the concept of a proof of knowledge, and shows that in all natural cases (e.g., NP-statements) this gap can be closed. The aforementioned formulations differ by whether they refer to (all possible) probabilistic or deterministic prover strategies. Unlike in the rest of cryptography, in the current context, the obvious transformation of probabilistic strategies to deterministic strategies does not seem to suffice per se.

We provide the first construction of a concurrent and non-malleable zero knowledge argument for every language in NP. We stress that our construction is in the plain model with no common random string, trusted parties, or super-polynomial simulation. That is, we construct a zero knowledge protocol $\Pi$ such that for every polynomial-time adversary that can adaptively and concurrently schedule polynomially many executions of $\Pi$, and corrupt some of the verifiers and some of the provers in these sessions, there is a polynomial-time simulator that can simulate a transcript of the entire execution, along with the witnesses for all statements proven by a corrupt prover to an honest verifier. Our security model is the traditional model for concurrent zero knowledge, where the statements to be proven by the honest provers are fixed in advance and do not depend on the previous history (but can be correlated with each other); corrupted provers, of course, can chose the statements adaptively. We also prove that there exists some functionality F (a combination of zero knowledge and oblivious transfer) such that it is impossible to obtain a concurrent non-malleable protocol for F in this model. Previous impossibility results for composable protocols ruled out existence of protocols for a wider class of functionalities (including zero knowledge!) but only if these protocols were required to remain secure when executed concurrently with arbitrarily chosen different protocols (Lindell, FOCS 2003) or if these protocols were required to remain secure when the honest parties' inputs in each execution are chosen adaptively based on the results of previous executions (Lindell, TCC 2004). We obtain an $\Tilde{O}(n)$-round protocol under the assumption that one-to-one one-way functions exist. This can be improved to $\Tilde{O}(k\log n)$ rounds under the assumption that there exist $k$-round statistically hiding commitment schemes. Our protocol is a black-box zero knowledge protocol.

A $(k,\ell)$-robust combiner for collision-resistant hash-functions is a construction which from $\ell$ hash-functions constructs a hash-function which is collision-resistant if at least $k$ of the components are collision-resistant. One trivially gets a $(k,\ell)$-robust combiner by concatenating the output of any $\ell-k+1$ of the components, unfortunately this is not very practical as the length of the output of the combiner is quite large. We show that this is unavoidable as no black-box $(k,\ell)$-robust combiner whose output is significantly shorter than what can be achieved by concatenation exists. This answers a question of Boneh and Boyen (Crypto'06).

We investigate whether security of multiparty computation in the information-theoretic setting implies their security under concurrent composition. We show that security in the stand-alone model proven using black-box simulators in the information-theoretic setting does not imply security under concurrent composition, not even security under 2-bounded concurrent self-composition with an inefficient simulator and fixed inputs. This in particular refutes recently made claims on the equivalence of security in the stand-alone model and concurrent composition for perfect and statistical security (STOC'06). Our result strongly relies on the question whether every rewinding simulator can be transformed into an equivalent, potentially inefficient non-rewinding (straight-line) simulator. We answer this question in the negative by giving a protocol that can be proven secure using a rewinding simulator, yet that is not secure for any non-rewinding simulator.

We study unconditionally secure 1-out-of-2 Oblivious Transfer (1-2 OT). We first point out that a standard security requirement for 1-2 OT of bits, namely that the receiver only learns one of the bits sent, holds if and only if the receiver has no information on the XOR of the two bits. We then generalize this to 1-2 OT of strings and show that the security can be characterized in terms of binary linear functions. More precisely, we show that the receiver learns only one of the two strings sent if and only if he has no information on the result of applying any binary linear function (which non-trivially depends on both inputs) to the two strings. We then argue that this result not only gives new insight into the nature of 1-2 OT, but it in particular provides a very powerful tool for analyzing 1-2 OT protocols. We demonstrate this by showing that with our characterization at hand, the reduceability of 1-2 OT (of strings) to a wide range of weaker primitives follows by a very simple argument. This is in sharp contrast to previous literature, where reductions of 1-2 OT to weaker flavors have rather complicated and sometimes even incorrect proofs.

Blockwise-adaptive chosen-plaintext and chosen-ciphertext attack are new models for cryptanalytic adversaries, first discovered by Joux, et al [JMV02], and describe a vulnerability in SSH discovered by Bellare, et al [BKN02]. Unlike traditional chosen-plaintext (CPA) or chosen-ciphertext (CCA) adversaries, the blockwise adversary can submit individual blocks for encryption or decryption rather than entire messages. This paper focuses on the search for on-line encryption schemes which are resistant to blockwise-adaptive chosen-plaintext attack. We prove that one oracle query with non-equal inputs is sufficient to win the blockwise-adaptive chosen-plaintext game if the game can be won by any adversary in ppt with non-negligible advantage. In order to uniformly describe such encryption schemes, we define a canonical representation of encryption schemes based on functions believed to be pseudorandom (i.e. Block Ciphers). This Canonical Form is general enough to cover many modes currently in use, including ECB, CBC, CTR, OFB, CFB, ABC, IGE, XCBC, HCBC and HPCBC. An immediate result of the theorems in this paper is that CTR, OFB, CFB, HCBC and HPCBC are proven secure against blockwise-adaptive CPA, as well as S-ABC under certain conditions. Conversely ECB, CBC, IGE, and P-ABC are proven to be blockwise-adaptive CPA insecure. Since CBC, IGE and P-ABC are chosen-plaintext secure, this indicates that the blockwise-adaptive chosen-plaintext model is a non-trivial extension of the traditional chosen-plaintext attack model.

This paper examines methods for formally proving the security of cryptographic schemes. We show that, despite many years of active research, there are fundamental problems which have yet to be solved. We also present a new approach to one of the more controversial aspects of provable security: the random oracle model.

This paper concerns the possibility of developing a coherent theory of security when feasibility is associated with expected probabilistic polynomial-time (expected PPT). The source of difficulty is that the known definitions of expected PPT strategies (i.e., expected PPT interactive machines) do not support natural results of the type presented below. To overcome this difficulty, we suggest new definitions of expected PPT strategies, which are more restrictive than the known definitions (but nevertheless extend the notion of expected PPT non-interactive algorithms). We advocate the conceptual adequacy of these definitions, and point out their technical advantages. Specifically, identifying a natural subclass of black-box simulators, called normal, we prove the following two results: (1) Security proofs that refer to all strict PPT adversaries (and are proven via normal black-box simulators), extend to provide security with respect to all adversaries that satisfy the restricted definitions of expected PPT. (2) Security composition theorems of the type known for strict PPT hold for these restricted definitions of expected PPT, where security means simulation by normal black-box simulators. Specifically, a normal black-box simulator is required to make an expected polynomial number of steps, when given oracle access to any strategy, where each oracle call is counted as a single step. This natural property is satisfies by most known simulators and is easy to verify.

The discrete logarithm problem (DLP) generalizes to the constrained DLP, where the secret exponent $x$ belongs to a set known to the attacker. The complexity of generic algorithms for solving the constrained DLP depends on the choice of the set. Motivated by cryptographic applications, we study sets with succinct representation for which the constrained DLP is hard. We draw on earlier results due to Erdös et~al. and Schnorr, develop geometric tools such as generalized Menelaus' theorem for proving lower bounds on the complexity of the constrained DLP, and construct sets with succinct representation with provable non-trivial lower bounds.

The standard class of adversaries considered in cryptography is that of {\em strict} polynomial-time probabilistic machines. However, {\em expected} polynomial-time machines are often also considered. For example, there are many zero-knowledge protocols for which the only known simulation techniques run in expected (and not strict) polynomial time. In addition, it has been shown that expected polynomial-time simulation is {\em essential} for achieving constant-round black-box zero-knowledge protocols. This reliance on expected polynomial-time simulation introduces a number of conceptual and technical difficulties. In this paper, we develop techniques for dealing with expected polynomial-time adversaries in simulation-based security proofs.

We discuss the general theoretical ideas of the possibility using cryptosystems based on the partial differential equations (PDE) and the role of inverse scattering problem for the cryptanalysis as the possible way to the postquantum cipher scheme. An application of the nonlinear Schrödinger equation and optical fibre technology in cryptology is presented.

For the first time we find Boolean functions on 9 variables having nonlinearity 241, that remained as an open question in literature for almost three decades. Such functions are discovered using a suitably modified steepest-descent based iterative heuristic search in the class of rotation symmetric Boolean functions (RSBFs). This shows that there exist Boolean functions on $n$ (odd) variables having nonlinearity $> 2^{n-1} - 2^{\frac{n-1}{2}}$ if and only if $n > 7$. Using the same search method, we also find several other important functions and we study the autocorrelation, propagation characteristics and resiliency of the RSBFs (using proper affine transformations, if required). The results show that it is possible to get balanced Boolean functions on $n=10$ variables having autocorrelation spectra with maximum absolute value $< 2^{\frac{n}{2}}$, which was not known earlier. In certain cases the functions can be affinely transformed to get first order propagation characteristics. We also obtain 10-variable functions having first order resiliency and nonlinearity 492 which was posed as an open question in Crypto 2000.

We prove the equivalence of two definitions of non-malleable encryption, one based on the simulation approach of Dolev, Dwork and Naor and the other based on the comparison approach of Bellare, Desai, Pointcheval and Rogaway. Our definitions are slightly stronger than the original ones. The equivalence relies on a new characterization of non-malleable encryption in terms of the standard notion of indistinguishability of Goldwasser and Micali. We show that non-malleability is equivalent to indistinguishability under a ``parallel chosen ciphertext attack,'' this being a new kind of chosen ciphertext attack we introduce, in which the adversary's decryption queries are not allowed to depend on answers to previous queries, but must be made all at once. This characterization simplifies both the notion of non-malleable encryption and its usage, and enables one to see more easily how it compares with other notions of encryption. The results here apply to non-malleable encryption under any form of attack, whether chosen-plaintext, chosen-ciphertext, or adaptive chosen-ciphertext.

Recently, Wang proposed a new method to cryptanalyze SHA-1 and found collisions of $58$-round SHA-1. However many details of Wang's attack are still unpublished, especially, 1) How to find differential paths? 2) How to modify messages properly? For the first issue, some results have already been reported. In our article, we clarify the second issue and give a sophisticated method based on Gröbner basis techniques. We propose two algorithm based on the basic and an improved message modification techniques respectively. The complexity of our algorithm to find a collision for 58-round SHA-1 based on the basic message modification is $2^{29}$ message modifications and its implementation is equivalent to $2^{31}$ SHA-1 computation experimentally, whereas Wang's method needs $2^{34}$ SHA-1 computation. We propose an improved message modification and apply it to construct a more sophisticated algorithm to find a collision. The complexity to find a collision for 58-round SHA-1 based on this improved message modification technique is $2^8$ message modifications, but our latest implementation is very slow, equivalent to $2^{31}$ SHA-1 computation experimentally. However we conjecture that our algorithm can be improved by techniques of error correcting code and Gröbner basis. By using our methods, we have found many collisions for $58$-round SHA-1.

We show that every language in NP has a *statistical* zero-knowledge argument system under the (minimal) complexity assumption that one-way functions exist. In such protocols, even a computationally unbounded verifier cannot learn anything other than the fact that the assertion being proven is true, whereas a polynomial-time prover cannot convince the verifier to accept a false assertion except with negligible probability. This resolves an open question posed by Naor, Ostrovsky, Venkatesan, and Yung (CRYPTO `92, J. Cryptology `98). Departing from previous works on this problem, we do not construct standard statistically hiding commitments from any one-way function. Instead, we construct a relaxed variant of commitment schemes called "1-out-of-2-binding commitments," recently introduced by Nguyen and Vadhan (STOC `06).

Let $N(d,d^\perp)$ denote the minimum length $n$ of a linear code $C$ with $d$ and $d^{\bot}$, where $d$ is the minimum Hamming distance of $C$ and $d^{\bot}$ is the minimum Hamming distance of $C^{\bot}$. In this paper, we show a lower bound and an upper bound on $N(d,d^\perp)$. Further, for small values of $d$ and $d^\perp$, we determine $N(d,d^\perp)$ and give a generator matrix of the optimum linear code. This problem is directly related to the design method of cryptographic Boolean functions suggested by Kurosawa et al.

The standard security definition of unconditional secure function evaluation, which is based on the ideal/real model paradigm, has the disadvantage of being overly complicated to work with in practice. On the other hand, simpler ad-hoc definitions tailored to special scenarios have often been flawed. Motivated by this unsatisfactory situation, we give an information-theoretic security definition of secure function evaluation which is very simple yet provably equivalent to the standard, simulation-based definitions.

We introduce a computational problem of distinguishing between two specific quantum states as a new cryptographic problem to design a quantum cryptographic scheme that is ``secure'' against any polynomial-time quantum adversary. Our problem QSCDff is to distinguish between two types of random coset states with a hidden permutation over the symmetric group of finite degree. This naturally generalizes the commonly-used distinction problem between two probability distributions in computational cryptography. As our major contribution, we show three cryptographic properties: (i) QSCDff has the trapdoor property; (ii) the average-case hardness of QSCDff coincides with its worst-case hardness; and (iii) QSCDff is computationally at least as hard in the worst case as the graph automorphism problem. These cryptographic properties enable us to construct a quantum public-key cryptosystem, which is likely to withstand any chosen plaintext attack of a polynomial-time quantum adversary. We further discuss a generalization of QSCDff, called QSCDcyc, and introduce a multi-bit encryption scheme relying on the cryptographic properties of QSCDcyc.

Recent progress on pairing implementation has made certain pairings extremely simple and fast to compute. Hence, it is natural to examine if there are consequences for the security of pairing-based cryptography. This paper gives a method to compute eta pairings in a way which avoids the requirement for a final exponentiation. The method does not lead to any improvement in the speed of pairing implementation. However, it seems appropriate to re-evaluate the security of pairing based cryptography in light of these new ideas. A multivariate attack on the pairing inversion problem is proposed and analysed. Our findings support the belief that pairing inversion is a hard computational problem.

In this note we prove that the controversial Diffie-Hellman Knowledge problem is secure in the generic group model. This appears to be the first paper that presents any evidence as to whether the Diffie-Hellman Knowledge problem is true or false.

We define and construct Independent Zero-Knowledge Sets (ZKS) protocols. In a ZKS protocols, a Prover commits to a set $S$, and for any $x$, proves non-interactively to a Verifier if $x \in S$ or $x \notin S$ without revealing any other information about $S$. In the {\em independent} ZKS protocols we introduce, the adversary is prevented from successfully correlate her set to the one of a honest prover. Our notion of independence in particular implies that the resulting ZKS protocol is non-malleable. On the way to this result we define the notion of {\em independence} for commitment schemes. It is shown that this notion implies non-malleability, and we argue that this new notion has the potential to simplify the design and security proof of non-malleable commitment schemes. Efficient implementations of ZKS protocols are based on the notion of mercurial commitments. Our efficient constructions of independent ZKS protocols requires the design of {\em new} commitment schemes that are simultaneously independent (and thus non-malleable) and mercurial.

Several compositional forms of simulation-based security have been proposed in the literature, including universal composability, black-box simulatability, and variants thereof. These relations between a protocol and an ideal functionality are similar enough that they can be ordered from strongest to weakest according to the logical form of their definitions. However, determining whether two relations are in fact identical depends on some subtle features that have not been brought out in previous studies. We identify the position of a ``master process" in the distributed system, and some limitations on transparent message forwarding within computational complexity bounds, as two main factors. Using a general computational framework, called Sequential Probabilistic Process Calculus (SPPC), we clarify the relationships between the simulation-based security conditions. We also prove general composition theorems in SPPC. Many of the proofs are carried out based on a small set of equivalence principles involving processes and distributed systems. This gives us results that carry over to a variety of computational models.

Recently, there has been much interest in extending models for simulation-based security in such a way that the runtime of protocols may depend on the length of their input. Finding such extensions has turned out to be a non-trivial task. In this work, we propose a simple, yet expressive general computational model for systems of Interactive Turing Machines (ITMs) where the runtime of the ITMs may be polynomial per activation and may depend on the length of the input received. One distinguishing feature of our model is that the systems of ITMs that we consider involve a generic mechanism for addressing dynamically generated copies of ITMs. We study properties of such systems and, in particular, show that systems satisfying a certain acyclicity condition run in polynomial time. Based on our general computational model, we state different notions of simulation-based security in a uniform and concise way, study their relationships, and prove a general composition theorem for composing a polynomial number of copies of protocols, where the polynomial is determined by the environment. The simplicity of our model is demonstrated by the fact that many of our results can be proved by mere equational reasoning based on a few equational principles on systems.

We study an extension of the well-known Abadi-Rogaway logic with hashes. Previously, we have given a sound computational interpretation of this extension using Canetti's oracle hashing. This paper extends Micciancio and Warinschi's completeness result for the original logic to this setting.

We present a rigorous approach to building a secure self-organizing mobile ad hoc network (MANET). In a highly dynamic environment like MANET, it is impossible to ensure absolute security to protect everything. We have to speak of the "infeasibility" of breaking the security system rather than the "impossibility" of breaking the same system. More formally, security is defined on the concept of "negligible", which is asymptotically sub-polynomial with respect to a pre-defined system parameter $n$. Intuitively, the parameter $n$ in modern cryptography is the key length. The crypto-system's security is broken if the adversary's capability is of exponentials of $n$, and the efficiency of all related algorithms is measured in polynomials of $n$. We adopt the same formal security notion in ad hoc network security research. In network security, the network scale (i.e., number of network members) $N$ replaces the role of key length $n$ in cryptography. If a security scheme can be devised to ensure that the probability of security failure is negligible, then the larger the network scale is or the more complex the network system is, the more secure the network is. In other words, given a negligibility-based protection against a specific security attack, larger or more complex systems are favored over smaller or simpler systems. Intuitively, this is consistent with the evolution theory where more complex entities probabilistically emerge from and likely survive longer than their less complex counterparts. In this paper, we use ``rushing attack'' as the exemplary security attack to disrupt mobile ad hoc routing. We show that ``rushing attack'' is a severe attack against on-demand ad hoc routing schemes. Fortunately, ``localized forwarding community area'' is an available countermeasure to ensure that the failure probability of packet forwarding is negligible. This demonstrates the usefulness of our negligibility-based network security model. We expect to augment the pool of negligibility-based protections and explore the general notion in other types of networks.\\ \emph{Keywords}---Net-centric Security = Negligibility + Scalability

In this work, we consider privacy in Radio Frequency IDentification (RFID) systems. Our contribution is threefold: (1) We propose a simple, formal definition of strong privacy useful for basic analysis of RFID systems, as well as a different (weaker) definition applicable to multi-verifier systems; (2) We apply our definition to reveal vulnerabilities in several proposed privacy-enhancing RFID protocols; and (3) We formally analyze and suggest improvements to ``Hash-Locks,'' one of the first privacy-enhancing RFID protocols in the literature.

This paper gives a construction method which can get a large class of Boolean functions with maximum algebraic immunity(AI) from one such giving function. Our constructions get more functions than any previous construction. The cryptographic properties, such as balance, algebraic degree etc, of those functions are studied. It shows that we can construct Boolean functions with better cryptographic properties, which gives the guidance for the design of Boolean functions to resist algebraic attack, and helps to design good cryptographic primitives of cryptosystems. From these constructions, we show that the count of the Boolean functions with maximum AI is bigger than ${2^{2^{n-1}}}$ for $n$ odd, bigger than ${2^{2^{n-1}+\frac{1}{2}\binom{n}{\frac{n}{2}} }}$ for $n$ even, which confirms the computer simulation result that such boolean functions are numerous. As far as we know, this is the first bound about this count.

In this contribution we introduce a low-complexity bit-parallel algorithm for computing square roots over binary extension fields. Our proposed method can be applied for any type of irreducible polynomials. We derive explicit formulae for the space and time complexities associated to the square root operator when working with binary extension fields generated using irreducible trinomials. We show that for those finite fields, it is possible to compute the square root of an arbitrary field element with equal or better hardware efficiency than the one associated to the field squaring operation. Furthermore, a practical application of the square root operator in the domain of field exponentiation computation is presented. It is shown that by using as building blocks squarers, multipliers and square root blocks, a parallel version of the classical square-and-multiply exponentiation algorithm can be obtained. A hardware implementation of that parallel version may provide a speedup of up to 50\% percent when compared with the traditional version.

Resettably-sound proofs and arguments remain sound even when the prover can reset the verifier, and so force it to use the same random coins in repeated executions of the protocol. We show that resettably-sound zero-knowledge {\em arguments} for NP exist if collision-resistant hash functions exist. In contrast, resettably-sound zero-knowledge {\em proofs} are possible only for languages in P/poly. We present two applications of resettably-sound zero-knowledge arguments. First, we construct resettable zero-knowledge arguments of knowledge for NP, using a natural relaxation of the definition of arguments (and proofs) of knowledge. We note that, under the standard definition of proofs of knowledge, it is impossible to obtain resettable zero-knowledge arguments of knowledge for languages outside BPP. Second, we construct a constant-round resettable zero-knowledge argument for NP in the public-key model, under the assumption that collision-resistant hash functions exist. This improves upon the sub-exponential hardness assumption required by previous constructions. We emphasize that our results use non-black-box zero-knowledge simulations. Indeed, we show that some of the results are {\em impossible} to achieve using black-box simulations. In particular, only languages in BPP have resettably-sound arguments that are zero-knowledge with respect to black-box simulation.

Modular arithmetic with prime moduli has been crucial in present day cryptography. The primes of Mersenne, Solinas, Crandall and the so called IKE-MODP have been extensively used in efficient implementations. In this paper we study the density of primes with binary signed representation involving a small number of non-zero $\pm 1$-digits.

In 2006, Blake, Murty and Xu proposed three refinements to Miller's algorithm for computing Weil/Tate Pairings. In this paper we extend their work and propose a generalized algorithm, which integrates their first two algorithms. Our approach is to pre-organize the binary representation of the involved integer to the best cases of Blake's algorithms. Further, our refinement is more suitable for Solinas numbers than theirs. We analyze our algorithm and show that our refinement can perform better than the original algorithms.

A cryptographic primitive or a security mechanism can be specified in a variety of ways, such as a condition involving a game against an attacker, construction of an ideal functionality, or a list of properties that must hold in the face of attack. While game conditions are widely used, an ideal functionality is appealing because a mechanism that is indistinguishable from an ideal functionality is therefore guaranteed secure in any larger system that uses it. We relate ideal functionalities to games by defining the \textit{set} of ideal functionalities associated with a game condition and show that under this definition, which reflects accepted use and known examples, bit commitment, a form of group signatures, and some other cryptographic concepts do not have any realizable ideal functionality.

Suppose you want to store a large file on a remote and unreliable server. You would like to verify that your file has not been corrupted, so you store a small private (randomized)``fingerprint'' of the file on your own computer. This is the setting for the well-studied authentication problem, and the size of the required private fingerprint is well understood. We study the problem of sub-linear authentication: suppose you would like to encode and store your file in a way that allows you to verify that it has not been corrupted, but without reading all of it. If you only want to read t bits of the file, how large does the size s of the fingerprint need to be? We define this problem formally, and show a tight lower bound on the relationship between s and t when the adversary is not computationally bounded, namely: s x t= Omega(n) where n is the file size. This is an easier case of the online memory checking problem, introduced by Blum, Evans, Gemmel, Kannan and Naor in 1991, and hence the same (tight) lower bound applies also to this problem. It was previously shown that when the adversary is not computationally bounded, under the assumption that one-way functions exist, it is possible to construct much better online memory checkers and sub-linear authentication schemes. We show that the existence of one-way functions is also a necessary condition: even slightly breaking the s x t= Omega(n) lower bound in a computational setting implies the existence of one-way functions.

Pseudorandom Functions (PRFs), introduced by Goldreich, Goldwasser and Micali, allow one to efficiently simulate the computation of a function which is indistinguishable from a truly random function. A seemingly stronger primitive is that of a (strong) pseudorandom permutation (PRP), which allows one to efficiently simulate a truly random permutation (and its inverse). The celebrated result of Luby and Rackoff shows that these primitives are, in fact, equivalent: four rounds of the Feistel transform are necessary and sufficient to turn a PRF into a (strong) PRP. In this paper we study a similar conversion for the verifiable analogs of PRFs and PRPs, called Verifiable Random Functions (VRFs) and Verifiable Random Permutations (VRPs). VRFs, introduced by Micali, Rabin and Vadhan, extend the notion of a PRF to allow the owner of the secret key for the VRF to prove to the outside parties that a given VRF value was correctly (and uniquely!) computed. Yet, such proofs do not violate the pseudorandomness of the remaining, yet ``unopened'' values. VRPs, introduced in this paper, similarly extend the notion of PRPs. We notice that the result of Luby and Rackoff no longer applies to converting VRFs into VRPs, since the VRP proofs must reveal the VRF outputs (and proofs) of the intermediate rounds. Indeed, we show that even logarithmic (in the security parameter) number of rounds is not enough for this conversion. Our main result, however, shows that super-logarithmic number of rounds of the Feistel transform suffice to build a VRP out of an arbitrary VRF. As an application, we give a construction of non-interactive zero-knowledge (NIZK) proofs with efficient provers for any NP language from any VRF. The result is obtained from our VRF--->VRP conversion, by noticing that VRPs easily yield ``invariant signatures'' of Goldwasser and Ostrovsky , which are known to imply NIZK. (We also notice that the detour through VRPs seems necessary for this implication, since using VRFs in place of invariant signatures is provably insufficient for the NIZK construction of Goldwasser et al. to go through.)

We propose a new model for key exchange (KE) based on a combination of different types of keys. In our setting, servers exchange keys with clients, who memorize short passwords and carry (stealable) storage cards containing long (cryptographic) keys. Our setting is a generalization of that of Halevi and Krawczyk \cite{HaleviKr99} (HK), where clients have a password and the public key of the server. We point out a subtle flaw in the protocols of HK and demonstrate a practical attack on them, resulting in a full password compromise. We give a definition of security of KE in our (and thus also in the HK) setting and discuss many related subtleties. We define and discuss protection against denial of access (DoA) attacks, which is not possible in any of the previous KE models that use passwords. Finally, we give a very simple and efficient protocol satisfying all our requirements.

We show that oblivious transfer of bits from $A$ to $B$ can be obtained from a single instance of the same primitive from $B$ to $A$. Our reduction is perfect and shows that oblivious transfer is in fact a symmetric functionality. This solves an open problem posed by Crépeau and Sántha in 1991.

A multicollision for a function is a set of inputs whose outputs are all identical. A. Joux showed multicollision attacks on the classical iterated hash function. He also showed how these multicollision attacks can be used to get a collision attack on a concatenated hash function. In this paper, we study multicollision attacks in a more general class of hash functions which we term ``generalized sequential hash functions''. We show that multicollision attacks exist for this class of hash functions provided that every message block is used at most twice in the computation of the message digest.

We describe a faithful embedding of the Dolev-Yao model of Backes, Pfitzmann, and Waidner (CCS 2003) in the theorem prover Isabelle/HOL. This model is cryptographically sound in the strong sense of reactive simulatability/UC, which essentially entails the preservation of arbitrary security properties under active attacks and in arbitrary protocol environments. The main challenge in designing a practical formalization of this model is to cope with the complexity of providing such strong soundness guarantees. We reduce this complexity by abstracting the model into a sound, light-weight formalization that enables both concise property specifications and efficient application of our proof strategies and their supporting proof tools. This yields the first tool-supported framework for symbolically verifying security protocols that enjoys the strong cryptographic soundness guarantees provided by reactive simulatability/UC. As a proof of concept, we have proved the security of the Needham-Schroeder-Lowe protocol using our framework.

Since Diffie-Hellman \cite{DH76}, many secure systems, based on discrete logarithm or Diffie-Hellman assumption in $\mathbb{Z}_p$, were introduced in the literature. In this work, we investigate the possibility to construct efficient primitives from exponentiation techniques over $\mathbb{Z}_p$. Consequently, we propose a new pseudorandom generator, where its security is proven under the decisional Diffie-Hellman assumption. Our generator is the most efficient among all generators from $\mathbb{Z}_p^*$ that are provably secure under standard assumptions. If an appropriate precomputation is allowed, our generator can produce $O(\log\log p)$ bits per modular multiplication. This is the best possible result in the literature (even improved by such a precomputation as well). Interestingly, our generator is the first provably secure under a decisional assumption and might be instructive for discovering potentially more efficient generators in the future. Our second result is a new family of universally collision resistant hash family (CRHF). Our CRHF is provably secure under the discrete log assumption and is more efficient than all previous CRHFs that are provably secure under standard assumptions (especially without a random oracle). This result is important, especially when the unproven hash functions (e.g., MD4, MD5, SHA-1) were broken by Wang et al. \cite{W+05,WY05,WYY05}.

(Revision of Sept. 2004 of a journal submission from Dec. 2000.) Certified mail is the fair exchange of a message for a receipt, i.e., the recipient gets the message if and only if the sender gets a receipt. It is an important primitive for electronic commerce and other atomicity services. Certified-mail protocols are known in the literature, but there was no rigorous definition yet, in particular for optimistic protocols and for many interleaved executions. We provide such a definition via an ideal system and show that a specific real certified-mail protocol is as secure as this ideal system in the sense of reactive simulatability in the standard model of cryptography and under standard assumptions. As certified mail without any third party is not practical, we consider optimistic protocols, which involve a third party only if one party tries to cheat. The real protocol resembles prior protocols, but we had to use a different cryptographic primitive to achieve simulatability. The communication model is synchronous. This proof first demonstrated that a cryptographic multi-step protocol can fulfil a general definition of reactive simulatability enabling concurrent composition. We also first showed how formal-method style reasoning can be applied over the ideal system in a cryptographically sound way. Moreover, the treatment of multiple protocol runs and their modular proof in spite of the use of common cryptographic primitives for all runs can be seen as a first example of what is now known as joint-state composition.

In this contribution, we derive a novel parallel formulation of the standard Itoh-Tsujii algorithm for multiplicative inverse computation over GF($2^m$). The main building blocks used by our algorithm are: field multiplication, field squaring and field square root operators. It achieves its best performance when using a special class of irreducible trinomials, namely, $P(X) = X^m + X^k + 1$, with $m$ and $k$ odd numbers and when implemented in hardware platforms. Under these conditions, our experimental results show that our parallel version of the Itoh-Tsujii algorithm yields a speedup of about 30% when compared with the standard version of it. Implemented in a Virtex 3200E FPGA device, our design is able to compute multiplicative inversion over GF($2^193$) after 20 clock cycles in about $0.94\mu$S.

Low degree annihilators for Boolean functions are of great interest in cryptology because of algebraic attacks on LFSR-based stream ciphers. Several polynomial algorithms for construction of low degree annihilators are introduced in this paper. The existence of such algorithms is studied for the following forms of the function representation: algebraic normal form (ANF), disjunctive normal form (DNF), conjunctive normal form (CNF), and arbitrary formula with the Boolean operations of negation, conjunction, and disjunction. For ANF and DNF of a Boolean function $f$ there exist polynomial algorithms that find the vector space $A_d (f)$ of all annihilators of degree $\leqslant d$. For CNF this problem is NP-hard. Nevertheless author introduces one polynomial algorithm that constructs some subspace of $A_d (f)$ having formula that represents $f$.