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

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

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

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

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

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

Verifiable Secret Sharing (VSS) is a fundamental primitive used as a building block in many distributed cryptographic tasks, such as Secure Multiparty Computation (MPC) and Byzantine Agreement (BA). An important variant of VSS is Asynchronous VSS (AVSS) which is designed to work over asynchronous networks. AVSS is a two phase (Sharing, Reconstruction) protocol carried out among $n$ parties in the presence of a computationally unbounded active adversary, who can corrupt up to $t$ parties. We assume that every two parties in the network are directly connected by a pairwise secure channel. In this paper, we present a new statistical AVSS protocol with optimal resilience; i.e. with $n = 3t+1$. Our protocol privately communicates O((\ell n^3 + n^4 \log{\frac{1}{\epsilon}}) \log{\frac{1}{\epsilon}}) bits and A-cast O(n^3 \log(n)) bits to simultaneously share \ell \geq 1 elements from a finite field F, where \epsilon is the error parameter of our protocol. There are only two known statistical AVSS protocols with $n = 3t+1$ reported in [CR93] and [PCR08]. The AVSS protocol of [CR93] requires a private communication of O(n^9 (\log{\frac{1}{\epsilon}})^4) bits and A-cast of O(n^9 (\log{\frac{1}{\epsilon}})^2 \log(n)) bits to share a single element from F. Thus our AVSS protocol shows a significant improvement in communication complexity over the AVSS of [CR93]. The AVSS protocol of [PCR08] requires a private communication and A-cast of O((\ell n^3 + n^4) \log{\frac{1}{\epsilon}}) bits to share \ell \geq 1 elements. However, the shared element(s) may be NULL \not \in F. Thus our AVSS is better than the AVSS of [PCR08] due to the following reasons: 1. The A-cast communication of our AVSS is independent of the number of secrets i.e. \ell; 2. Our AVSS makes sure that the shared value(s) always belong to F. Using our AVSS, we design a new primitive called Asynchronous Complete Secret Sharing (ACSS) which acts as an important building block of asynchronous multiparty computation (AMPC). Using our ACSS scheme, we design a statistical AMPC protocol with optimal resilience; i.e., with $n = 3t+1$, that privately communicates O(n^5 \log{\frac{1}{\epsilon}}) bits per multiplication gate. This significantly improves the communication complexity of only known optimally resilient [BKR93] that privately communicates \Omega(n^{11} (\log{\frac{1}{\epsilon}})^4) bits and A-cast \Omega(n^{11} (\log{\frac{1}{\epsilon}})^2 \log(n)) bits per multiplication gate. Both our ACSS and AVSS employ several new techniques, which are of independent interest.

It is showed that an existence of cubic groups may suggest an existence of one-way function.

The computational soundness of formal encryption is studied extensively following the work of Abadi and Rogaway. Recent work considers the scenario in which secret sharing is needed, and separately, the scenario when key cycles are present. The novel technique is the use of a co-induction definition of the adversarial knowledge. In this paper, we prove a computational soundness theorem of formal encryption in the presence of both key cycles and secret shares at the same time, which is a non-trivial extension of former approaches.

In this paper we find division polynomials for Huff curves, Jacobi quartics, and Jacobi intersections. These curves are alternate models for elliptic curves to the more common Weierstrass curve. Division polynomials for Weierstrass curves are well known, and the division polynomials we find are analogues for these alternate models. Using the division polynomials, we show recursive formulas for the $n$-th multiple of a point on each curve. As an application, we prove a type of mean-value theorem for Huff curves, Jacobi quartics and Jacobi intersections.

Analyzing desired generic properties of hash functions is an important current area in cryptography.For example, in Eurocrypt 2009, Dodis, Ristenpart and Shrimpton [7] introduced the elegant notion of “Preimage Awareness” (PrA) of a hash function HP , and they showed that a PrA hash function followed by an output transformation modeled to be a FIL (fixed input length) random oracle is PRO (pseudorandom oracle) i.e. indifferentiable from a VIL (variable input length) random oracle. We observe that for recent practices in designing hash function (e.g. SHA-3 candidates) most output transformations are based on permutation(s) or blockcipher(s), which are not PRO. Thus, a natural question is how the notion of PrA can be employed directly with these types of more prevalent output transformations? We consider the Davies-Meyer’s type output transformation OT(x) := E(x)xor x where E is an ideal permutation. We prove that OT(HP (·)) is PRO if HP is PrA, preimage resistant and computable message aware (a related but not redundant notion, needed in the analysis that we introduce in the paper). The similar result is also obtained for 12 PGV output transformations. We also observe that some popular double block length output transformations can not be employed as output transformation.

In this work, we study position-based cryptography in the quantum setting. The aim is to use the geographical position of a party as its only credential. On the negative side, we show that if adversaries are allowed to share an arbitrarily large entangled quantum state, no secure position-verification is possible at all. We show a distributed protocol for computing any unitary operation on a state shared between the different users, using local operations and one round of classical communication. Using this surprising result, we break any position-verification scheme of a very general form. On the positive side, we show that if adversaries do not share any entangled quantum state but can compute arbitrary quantum operations, secure position-verification is achievable. Jointly, these results suggest the interesting question whether secure position-verification is possible in case of a bounded amount of entanglement. Our positive result can be interpreted as resolving this question in the simplest case, where the bound is set to zero. In models where secure positioning is achievable, it has a number of interesting applications. For example, it enables secure communication over an insecure channel without having any pre-shared key, with the guarantee that only a party at a specific location can learn the content of the conversation. More generally, we show that in settings where secure position-verification is achievable, other position-based cryptographic schemes are possible as well, such as secure position-based authentication and position-based key agreement.

It is well known that secure computation without an honest majority requires computational assumptions. An interesting question that therefore arises relates to the way such computational assumptions are used. Specifically, can the secure protocol use the underlying primitive (e.g., a one-way trapdoor permutation) in a {\em black-box} way, treating it as an oracle, or must it be {\em nonblack-box} (by referring to the code that computes the primitive)? Despite the fact that many general constructions of cryptographic schemes refer to the underlying primitive in a black-box wayonly, there are some constructions that are inherently nonblack-box. Indeed, all known constructions of protocols for general secure computation that are secure in the presence of a malicious adversary and without an honest majority use the underlying primitive in a nonblack-box way (requiring to prove in zero-knowledge statements that relate to the primitive). In this paper, we study whether such nonblack-box use is essential. We answer this question in the negative. Concretely, we present a \emph{fully black-box reduction} from oblivious transfer with security against malicious parties to oblivious transfer with security against semi-honest parties. As a corollary, we get the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which only make a {\em black-box} use of semi-honest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption.

In recent researches, it is discovered that index calculus is useful for solving the discrete logarithm problems (DLP) of the groups of the Jacobian of curves (including elliptic curve) over finite field, which are widely used to cryptosystems. In these cases, the probability that an element of the group is written by the summation of N elements of large primes and factor bases is O(1) where N is some pre-fixed constant. So the situation is little different to the normal index calculus and it is proposed that it should be called another name, ”decomposition attack”. In decomposition attack, first, some relations are collected and the graph, whose vertexes are the set of large primes and whose edges are the relations, is considered and the elimination of large prime is done by using this graph. However, in the proposed algorithm, the randomness of the graph, which is difficult to define, is needed. In this paper, we first formulate the decomposition attack and next propose a new algorithm, which does not require the randomness of the graph and its worst complexity can be estimated.

Let Z/(pq) be the integer residue ring modulo pq with odd prime numbers p and q. This paper studies the distinctness problem of modulo 2 reductions of two primitive sequences over Z/(pq), which has been studied by H.J. Chen and W.F. Qi in 2009. First, it is shown that almost every element in Z/(pq) occurs in a primitive sequence of order n > 2 over Z/(pq). Then based on this element distribution property of primitive sequences over Z/(pq), previous results are greatly improved and the set of primitive sequences over Z/(pq) that are known to be distinct modulo 2 is further enlarged.

In this paper, we present a new algorithm, such that, for the small integer solution (SIS) problem, if the solution is bounded ( by an integer $\beta$ in $l_\infty$ norm, which we call a bounded SIS (BSIS) problem, {\it and if the difference between the row dimension $n$ and the column dimension $m$ of the corresponding matrix is relatively small with respect the row dimension $m$}, we can solve it easily with a complexity of polynomial in $m$.

In symmetric secure function evaluation (SSFE), Alice has an input $x$, Bob has an input $y$, and both parties wish to securely compute $f(x,y)$. We classify these functions $f$ according to their ``cryptographic complexities,'' and show that the landscape of complexity among these functions is surprisingly rich. We give combinatorial characterizations of the SSFE functions $f$ that have passive-secure protocols, and those which are protocols secure in the standalone setting. With respect to universally composable security (for unbounded parties), we show that there is an infinite hierarchy of increasing complexity for SSFE functions, That is, we describe a family of SSFE functions $f_1, f_2, \ldots$ such that there exists a UC-secure protocol for $f_i$ in the $f_j$-hybrid world if and only if $i \le j$. Our main technical tool for deriving complexity separations is a powerful protocol simulation theorem which states that, even in the strict setting of UC security, the canonical protocol for $f$ is as secure as any other protocol for $f$, as long as $f$ satisfies a certain combinatorial characterization. We can then show intuitively clear impossibility results by establishing the combinatorial properties of $f$ and then describing attacks against the very simple canonical protocols, which by extension are also feasible attacks against {\em any} protocol for the same functionality.

In this note, we provide a formal proof of the fact that any protocol that is a zero-knowledge proof of knowledge for a relation $R$ is also a secure protocol for the zero-knowledge proof of knowledge functionality, where the latter is defined according to the standard framework of stand-alone secure computation. Although this is a well-known fact, to the best of our knowledge, no full proof of this has been published.

The method of concealing a linear relationship between elements of a finite field (LRC method) is described. An LRC method based approach to the secure white-box implementations creating problem is considered. SPN cipher characteristics to create its secure White-Box implementation are revealed.

In a related-key attack (RKA) an adversary attempts to break a cryptographic primitive by invoking the primitive with several secret keys which satisfy some known, or even chosen, relation. We initiate a formal study of RKA security for \emph{randomized encryption} schemes. We begin by providing general definitions for semantic security under passive and active RKAs. We then focus on RKAs in which the keys satisfy known linear relations over some Abelian group. We construct simple and efficient schemes which resist such RKAs even when the adversary can choose the linear relation adaptively during the attack. More concretely, we present two approaches for constructing RKA-secure encryption schemes. The first is based on standard randomized encryption schemes which additionally satisfy a natural ``key-homomorphism'' property. We instantiate this approach under number-theoretic or lattice-based assumptions such as the Decisional Diffie-Hellman (DDH) assumption and the Learning Noisy Linear Equations assumption. Our second approach is based on RKA-secure pseudorandom generators. This approach can yield either {\em deterministic,} {\em one-time use} schemes with optimal ciphertext size or randomized unlimited use schemes. We instantiate this approach by constructing a simple RKA-secure pseurodandom generator under a variant of the DDH assumption. Finally, we present several applications of RKA-secure encryption by showing that previous protocols which made a specialized use of random oracles in the form of \emph{operation respecting synthesizers} (Naor and Pinkas, Crypto 1999) or \emph{correlation-robust hash functions} (Ishai et. al., Crypto 2003) can be instantiated with RKA-secure encryption schemes. This includes the Naor-Pinkas protocol for oblivious transfer (OT) with adaptive queries, the IKNP protocol for batch-OT, the optimized garbled circuit construction of Kolesnikov and Schneider (ICALP 2008), and other results in the area of secure computation. Hence, by plugging in our constructions we get instances of these protocols that are provably secure in the standard model under standard assumptions.

This paper studies the design of cryptographic schemes that are secure even if implemented on untrusted machines, whose internals can be partially observed/controlled by an adversary. For example, this includes machines that are infected with a software virus. We introduce a new cryptographic notion that we call a {\em one-time computable pseudorandom function (PRF)}, which is a PRF $F_K(\cdot)$ that can be evaluated \emph{at most once} on a machine which stores the (long) key $K$, as long as: (1) the adversary cannot retrieve the key $K$ out of the machine completely (this is similar to the assumptions made in the so-called {\em Bounded-Retrieval Model}), and (2) the local read/write memory of the machine is restricted, and not too much larger than the size of $K$. In particular, the \emph{only way} to evaluate $F_K(x)$ on such device, is to overwrite part of the key $K$, preventing all future evaluations of $F_K(\cdot)$ at any other point $x' \neq x$. We show that this primitive can be used to construct schemes for \emph{password protected storage} that are secure against dictionary attacks, even by a virus that infects the machine. Our constructions rely on the random-oracle model, and lower-bounds for {\em graphs pebbling} problems. We show that our techniques can also be used to construct another primitive, that we call {\em uncomputable hash functions}, which are hash funcitons that cannot be computed if the local storage has some restricted size $s$, but {\em can} be computed if they are given slightly more storage than $s$. We show that this tool can be used to improve the communication complexity of {\em proofs-of-erasure} schemes, introduced recently by Perito and Tsudik (ESORICS 2010).

A ``strong'' cryptographic hash function suitable for practical applications should simultaneously satisfy many security properties, like pseudo-randomness, collision resistance and unforgeability. This paper shows how to combine two hash function families each satisfying different security property into one hash function family, which satisfies both properties. In particular, given two hash function families $H_1$ and $H_2$, where $H_1$ is pseudo-random and $H_2$ is collision resistant, we construct a combiner which satisfies pseudo-randomness and collision resistance. We also present a combiner for collision resistance and everywhere preimage resistance. When designing a new hash function family for some particular application, we can use such combiners with existing primitives and thus combine a hash function family satisfying all needed properties.

Since the introduction of the concept of provable security, there has been the steady search for suitable problems that can be used as a foundation for cryptographic schemes. Indeed, identifying such problems is a challenging task. First, it should be open and investigated for a long time to make its hardness assumption plausible. Second, it should be easy to construct hard problem instances. Third, it should allow to build cryptographic applications on top of them. Not surprisingly, only a few problems are known today that satisfy all conditions, e.g., factorization, discrete logarithm, and lattice problems. In this work, we introduce another candidate: the Inhomogeneous Simultaneous Approximation Problem (ISAP), an old problem from the field of analytic number theory that dates back to the 19th century. Although the Simultaneous Approximation Problem (SAP) is already known in cryptography, it has mainly been considered in its homogeneous instantiation for attacking schemes. We take a look at the hardness and applicability of ISAP, i.e., the inhomogeneous variant, for designing schemes. More precisely, we define a decisional problem related to ISAP, called DISAP, and show that it is NP-complete. With respect to its hardness, we review existing approaches for computing a solution and give suggestions for the efficient generation of hard instances. Regarding the applicability, we describe as a proof of concept a bit commitment scheme where the hiding property is directly reducible to DISAP. An implementation confirms its usability in principle (e.g., size of one commitment is slightly more than 6 KB and execution time is in the milliseconds).

In this paper, we propose a class of $2k$-variable Boolean functions which have optimal algebraic degree, very high nonlinearity, and are $1$-resilient. Based on our newly proposed conjecture, it can be shown that the algebraic immunity of our functions is at least suboptimal. Moreover, when $k$ is odd, the algebraic immunity is actually optimal, and for even $k$, we find that the algebraic immunity is optimal at least for $k\leq 28$.

The Universal Composability framework was introduced by Canetti to study the security of protocols which are concurrently executed with other protocols in a network environment. Unfortunately it was shown that in the so called plain model, a large class of functionalities cannot be securely realized. These severe impossibility results motivated the study of other models involving some sort of setup assumptions, where general positive results can be obtained. Until recently, all the setup assumptions which were proposed required some trusted third party (or parties). Katz recently proposed using a \emph{physical setup} to avoid such trusted setup assumptions. In his model, the physical setup phase includes the parties exchanging tamper proof hardware tokens implementing some functionality. The tamper proof hardware is modeled so as to assume that the receiver of the token can do nothing more than observe its input/output characteristics. It is further assumed that the sender \emph{knows} the program code of the hardware token which it distributed. Based on the DDH assumption, Katz gave general positive results for universally composable multi-party computation tolerating any number of dishonest parties making this model quite attractive. In this paper, we present new constructions for UC secure computation using tamper proof hardware (in a stronger model). Our results represent an improvement over the results of Katz in several directions using substantially different techniques. Interestingly, our security proofs do not rely on being able to rewind the hardware tokens created by malicious parties. This means that we are able to relax the assumptions that the parties \emph{know} the code of the hardware token which they distributed. This allows us to model real life attacks where, for example, a party may simply pass on the token obtained from one party to the other without actually knowing its functionality. Furthermore, our construction models the interaction with the tamper-resistant hardware as a simple request-reply protocol. Thus, we show that the hardware tokens used in our construction can be \emph{resettable}. In fact, it suffices to use token which are completely stateless (and thus cannot execute a multi-round protocol). Our protocol is also based on general assumptions (namely enhanced trapdoor permutations).

A function $F$ from \textbf{F}$_{p^n}$ to itself is planar if for any $a\in$\textbf{F}$_{p^n}^*$ the function $F(x+a)-F(x)$ is a permutation. CCZ-equivalence is the most general known equivalence relation of functions preserving planar property. This paper considers two possible extensions of CCZ-equivalence for functions over fields of odd characteristics, one proposed by Coulter and Henderson and the other by Budaghyan and Carlet. We show that the second one in fact coincides with CCZ-equivalence, while using the first one we generalize one of the known families of PN functions. In particular, we prove that, for any odd prime $p$ and any positive integers $n$ and $m$, the indicators of the graphs of functions $F$ and $F'$ from \textbf{F}$_{p^n}$ to \textbf{F}$_{p^m}$ are CCZ-equivalent if and only if $F$ and $F'$ are CCZ-equivalent. We also prove that, for any odd prime $p$, CCZ-equivalence of functions from \textbf{F}$_{p^n}$ to \textbf{F}$_{p^m}$, is strictly more general than EA-equivalence when $n\ge3$ and $m$ is greater or equal to the smallest positive divisor of $n$ different from 1.

We defined a new notion of computational indistinguishability: termination-insensitive computational indistinguishability (tic-indistinguishability). Tic-indistinguishability models indistinguishability with respect to distinguishers that cannot distinguish between termination and non-termination. We sketch how the new notion allows to get computational soundness results of symbolic models for equivalence-based security properties (such as anonymity) for processes that contain loops, solving an open problem.

In this paper, we analyze the complexity of the construction of the $2^k$-diamond structure proposed by Kelsey and Kohno. We point out a flaw in their analysis and show that their construction may not produce the desired diamond structure. We then give a more rigorous and detailed complexity analysis of the construction of a diamond structure. For this, we appeal to random graph theory (in particular, to the theory of random intersection graphs), which allows us to determine sharp necessary and sufficient conditions for the {\it message complexity} (i.e., the number of hash computations required to build the required structure). We also analyze the {\it computational complexity} for constructing a diamond structure, which has not been previously studied in the literature. Finally, we study the impact of our analysis on herding and other attacks that use the diamond structure as a subroutine. Precisely, our results shows the following: \begin{enumerate} \item The message complexity for the construction of a diamond structure is $\sqrt{k}$ times more than the amount previously stated in literature. \item The time complexity is $n$ times the message complexity, where $n$ is the size of hash value. \end{enumerate} Due to the above two results, the herding attack~\cite{KK06} and the second preimage attack~\cite{ABFHKSZ08} on iterated hash functions have increased complexity. We also show that the message complexity of herding and second preimage attacks on ``hash twice'' is $n$ times the complexity claimed by~\cite{ABDK09}, by giving a more detailed analysis of the attack.

Much of the literature on rational cryptography focuses on analyzing the strategic properties of cryptographic protocols. However, due to the presence of computationally-bounded players and the asymptotic nature of cryptographic security, a definition of sequential rationality for this setting has thus far eluded researchers. We propose a new framework for overcoming these obstacles, and provide the first definitions of computational solution concepts that guarantee sequential rationality. We argue that natural computational variants of subgame perfection are too strong for cryptographic protocols. As an alternative, we introduce a weakening called threat free Nash equilibrium that is more permissive but still eliminates the undesirable ``empty threats'' of non-sequential solution concepts. To demonstrate the applicability of our framework, we revisit the problem of implementing a mediator for correlated equilibria (Dodis Halevi-Rabin, Crypto'00), and propose a variant of their protocol that is sequentially rational for a non-trivial class of correlated equilibria. Our treatment provides a better understanding of the conditions under which mediators in a correlated equilibrium can be replaced by a stable protocol.

This paper studies two types of attacks on the hash function Shabal. The first attack is a low-weight pseudo collision attack on Shabal. Since a pseudo collision attack is trivial for Shabal, we focus on a low-weight pseudo collision attack. It means that only low-weight difference in a chaining value is considered. By analyzing the difference propagation in the underlying permutation, we can construct a low-weight (45-bits) pseudo collision attack on the full compression function with complexity of 2^84. The second attack is a preimage attack on variants of Shabal-512. We utilize a guess-and-determine technique, which is originally developed for a cryptanalysis of stream ciphers, and customize the technique for a preimage attack on Shabal-512. As a result, for the weakened variant of Shabal-512 using security parameters (p; r) = (2; 12), a preimage can be found with complexity of 2^497 and memory of 2^400. Moreover, for the Shabal-512 using security parameters (p; r) = (1:5; 8), a preimage can be found with complexity of 2^497 and memory of 2^272. To the best of our knowledge, these are best preimage attacks on Shabal variants and the second result is a first preimage attack on Shabal-512 with reduced security parameters.

Hamsi is one of 14 remaining candidates in NIST's Hash Competition for the future hash standard SHA-3 and Hamsi-256 is one of four kinds of Hamsi. In this paper we present a genetic algorithm to search near collisions for the compress function of Hamsi-256 , give a near collision on (256 − 20) bits and a near collision on (256 − 21) bits with four differences in the chaining value, and obtain a differential path for three rounds of Hamsi-256 with probability 1/2^24, 1/2^23 respectively, which are better than previous work reported about near collisions.

A Binomial Sieve Series (BSS) is an infinite monotonic set of natural numbers, b1, b2, .....bn ( bi < b(i+1) ) generated, ('naturally') from any two natural numbers (x, y <= x) . If one repeatedly counts bi elements over the set X= 1,2,…,x (recycled counting) and eliminates each time the element of X that stops each round of counting, then the surviving element of X is y. Every natural number, per any x, is associated with a certain survivor. We prove that per any x all BSS are infinite and approach an equal size, regardless of the identity of the survivor element y. These infinite series (in count and length) have no simple pattern, their disorder is reminiscent of primes. We suggest some intriguing cryptographic applications based on the poor predictability of the next element in each series, combined with good predictability of the computational load to develop the series (by users and by the cryptanalyst). Using x as a shared secret, and a random, per-session, y, Alice and Bob may mark successive messages between them with the next element of the respective BSS, thereby mutually authenticating themselves throughout their conversation. Other cryptographic possibilities are outlined.

Higher order differential cryptanalysis is based on the property of higher order derivatives of Boolean functions that the degree of a Boolean function can be reduced by at least 1 by taking a derivative on the function at any point. We define \emph{fast point} as the point at which the degree can be reduced by at least 2. In this paper, we show that the fast points of a $n$-variable Boolean function form a linear subspace and its dimension plus the algebraic degree of the function is at most $n$. We also show that non-trivial fast point exists in every $n$-variable Boolean function of degree $n-1$, every symmetric Boolean function of degree $d$ where $n \not\equiv d \pmod{2}$ and every quadratic Boolean function of odd number variables. Moreover we show the property of fast points for $n$-variable Boolean functions of degree $n-2$.

Golić conjecture states that the necessary condition for a function to be perfectly balanced for any choice of a tapping sequence is linearity of a function in the first or in the last essential variable. In the current paper we prove Golić conjecture.

It is proved in this paper that for any point on an elliptic curve, the mean value of $x$-coordinates of its $n$-division points is the same as its $x$-coordinate and the mean value of $y$-coordinates of its $n$-division points is the $n$ times of its $y$-coordinate.

We give a simple example that there is no symbolic theory for exclusive or (XOR) that is computationally sound.

The aim of this paper is to find more Karatsuba-like formulae for a fixed set of moduli polynomials in GF(2)[x]. To this end, a theoretical framework is established. We first generalize the division algorithm, and then present a generalized definition of the remainder of integer division. Finally, a previously generalized Chinese remainder theorem is used to achieve our initial goal. As a by-product of the generalized remainder of integer division, we rediscover Montgomery’s N-residue and present a systematic interpretation of definitions of Montgomery’s multiplication and addition operations.

In this paper, we study approximation of addition by XOR, taking P. Sarkar's publication~\cite{bib:sarkar} as the reference work and starting point. In this work, among various results, it was claimed that explicit formulas seemed difficult to obtain when the number $n$ of summands is more than $5$. In the first part of our work, we show a systematic way to find explicit formulas: the complexity to compute them is $O(n^3)$, which allows large values of $n$. We present some numerical computation and point out a - conjectural - observation on the coefficients. In the second part, we study a generalization of P. Sarkar's work to $q$-ary addition, instead of binary. We show that the mechanics of the addition is essentially the same as in the binary case. In particular, sequence of carries behaves very similarly: it is a Markov chain whose transition matrix can be computed. Running some experiments on small values of $n$ leads us to a conjecture, the first part of which is intuitive and the second part of which reveals an amazing coincidence (and is probably not!). Finally, in a section titled ``very last news'', we refer to a paper published by Holte in 1997, that was brought to us after our first post and that we had missed before. It happens that this paper studies the topic and solves a major part of our open problems. Henceforth, the present post is an updated version of our previous ``Approximating Addition by XOR: how to go (a little) further than P. Sarkar'', taking into account this previous Holte's reference.

This paper describes a method for constructing Barreto-Naehrig (BN) curves and twists of BN curves that are pairing-friendly and have the embedding degree $12$ by using just primality tests without a complex multiplication (CM) method. Specifically, this paper explains that the number of points of elliptic curves $y^2=x^3\pm 16$ and $y^2=x^3 \pm 2$ over $\Fp$ is given by 6 polynomials in $z$, $n_0(z),\cdots, n_5(z)$, two of which are irreducible, classified by the value of $z\bmod{12}$ for a prime $p(z)=36z^4+36z^3+24z^2+6z+1$ with $z$ an integer. For example, elliptic curve $y^2=x^3+2$ over $\Fp$ always becomes a BN curve for any $z$ with $z \equiv 2,11\!\!\!\pmod{12}$. Let $n_i(z)$ be irreducible. Then, to construct a pairing-friendly elliptic curve, it is enough to find an integer $z$ of appropriate size such that $p(z)$ and $n_i(z)$ are primes.

Bellare and Kohno (2004) introduced the notion of balance to quantify the resistance of a hash function $h$ to a generic collision attack. Motivated by their work, we consider the problem of quantifying the resistance of $h$ to a generic multi-collision attack. To this end, we introduce the notion of $r$-balance $\mu_r (h)$ of $h$ and obtain bounds on the success probability of finding an $r$-collision in terms of $\mu_r (h)$. These bounds show that for a hash function with $m$ image points, if the number of trials $q$ is $\Theta(rm^{(r-1)\mu_r(h)/r})$, then it is possible to find $r$-collisions with a significant probability of success. The behaviour of random functions and the expected number of trials to obtain an $r$-collision is studied. These results extend and complete the earlier results obtained by Bellare and Kohno (2004) for collisions (i.e., $r = 2$). Going beyond their work, we provide a new design criteria to provide quantifiable resistance to generic multi- collision attacks. Further, we make a detailed probabilistic investigation of the variation of $r$-balance over the set of all functions and obtain support for the view that most functions have $r$-balance close to one.

For a random-self-reducible function, the evaluation problem is irreducible to the one-more evaluation problem, in the following sense. An irreduction algorithm exists that, given a reduction algorithm from the evaluation to the one-more evaluation problem, solves a separator problem: the evaluation problem itself. Another irreduction shows that if the computational Diffie-Hellman problem is reduced to the gap Diffie-Hellman problem, then the decision Diffie-Hellman problem is easy. Irreductions are primarily of theoretical interest, because they do not actually prove inequivalence between problems. What these irreductions suggest, though, is that one-more variants of the RSA and discrete logarithm problems may be easier than the standard variants, and that the gap Diffie-Hellman problem may be easier than the standard Diffie-Hellman problem.

Cloud computing denotes an architectural shift toward thin clients and conveniently centralized provision of computing resources. Clients’ lack of direct resource control in the cloud prompts concern about the potential for data privacy violations, particularly abuse or leakage of sensitive information by service providers. Cryptography is an oft-touted remedy. Among its most powerful primitives is fully homomorphic encryption (FHE), dubbed by some the field’s “Holy Grail,” and recently realized as a fully functional construct with seeming promise for cloud privacy. We argue that cryptography alone can’t enforce the privacy demanded by common cloud computing services, even with such powerful tools as FHE.We formally define a hierarchy of natural classes of private cloud applications, and show that no cryptographic protocol can implement those classes where data is shared among clients. We posit that users of cloud services will also need to rely on other forms of privacy enforcement, such as tamperproof hardware, distributed computing, and complex trust ecosystems.

This dissertation deals with three most important as well as fundamental problems in secure distributed computing, namely Verifiable Secret Sharing (VSS), Byzantine Agreement (BA) and Multiparty Computation (MPC). VSS is a two phase protocol (Sharing and Reconstruction) carried out among $n$ parties in the presence of a centralized adversary who can corrupt up to $t$ parties. Informally, the goal of the VSS protocol is to share a secret $s$, among the $n$ parties during the sharing phase in a way that would later allow for a unique reconstruction of this secret in the reconstruction phase, while preserving the secrecy of $s$ until the reconstruction phase. VSS is used as a key tool in MPC, BA and many other secure distributed computing problems. It can take many different forms, depending on the underlying network (synchronous or asynchronous), the nature (passive or active) and computing power (bounded or unbounded) of the adversary, type of security (cryptographic or information theoretic) etc. We study VSS in information theoretic setting over both synchronous as well as asynchronous network, considering an active unbounded powerful adversary. Our main contributions for VSS are: \begin{itemize} \item In synchronous network, we carry out in-depth investigation on the round complexity of VSS by allowing a probability of error in computation and show that existing lower bounds for the round complexity of error-free VSS can be circumvented by introducing a negligible probability of error. \item We study the communication and round efficiency of VSS in synchronous network and present a robust VSS protocol that is simultaneously communication efficient and round efficient. In addition, our protocol is the best known communication and round efficient protocol in the literature. \item In asynchronous network, we study the communication complexity of VSS and propose a number of VSS protocols. Our protocols are highly communication efficient and show significant improvement over the existing protocols in terms of communication complexity. \end{itemize} The next problem that we deal with is Byzantine Agreement (BA). BA is considered as one of the most fundamental primitives for fault tolerant distributed computing and cryptographic protocols. BA among a set of $n$ parties, each having a private input value, allows them to reach agreement on a common value even if some of the malicious parties (at most $t$) try to prevent agreement among the parties. Similar to the case of VSS, several models for BA have been proposed during the last three decades, considering various aspects like the underlying network, the nature and computing power of adversary, type of security. One of these models is BA over asynchronous network which is considered to be more realistic network than synchronous in many occasions. Though important, research in BA in asynchronous network has received much less attention in comparison to the BA protocols in synchronous network. Even the existing protocols for asynchronous BA involve high communication complexity and in general are very inefficient in comparison to their synchronous counterparts. We focus on BA in information theoretic setting over asynchronous network tolerating an active adversary having unbounded computing power and mainly work towards the communication efficiency of the problem. Our contributions for BA are as follows: \begin{itemize} \item We propose communication efficient asynchronous BA protocols that show huge improvement over the existing protocols in the same setting. Our protocols for asynchronous BA use our VSS protocols in asynchronous network as their vital building blocks. \item We also construct a communication optimal asynchronous BA protocol for sufficiently long message size. Precisely, our asynchronous BA communicates O(\ell n) bits for \ell bit message, for sufficiently large \ell. \end{itemize} The studies on VSS and BA naturally lead one towards MPC problems. The MPC can model almost any known cryptographic application and uses VSS as well as BA as building blocks. MPC enables a set of $n$ mutually distrusting parties to compute some function of their private inputs, such that the privacy of the inputs of the honest parties is guaranteed (except for what can be derived from the function output) even in the presence of an adversary corrupting up to $t$ of the parties and making them misbehave arbitrarily. Much like VSS and BA, MPC can also be studied in various models. Here, we attempt to solve MPC in information theoretic setting over synchronous as well as asynchronous network, tolerating an active unbounded powerful adversary. As for MPC, our main contributions are: \begin{itemize} \item Using one of our synchronous VSS protocol, we design a synchronous MPC that minimizes the communication and round complexity simultaneously, where existing MPC protocols try to minimize one complexity measure at a time (i.e the existing protocols minimize either communication complexity or round complexity). \item We study the communication complexity of asynchronous MPC protocols and design a number of protocols for the same that show significant gain in communication complexity in comparison to the existing asynchronous MPC protocols. \item We also study a specific instance of MPC problem called Multiparty Set Intersection (MPSI) and provide protocols for the same. \end{itemize} In brief, our work in this thesis has made significant advancement in the state-of-the-art research on VSS, BA and MPC by presenting several inherent lower bounds and efficient/optimal solutions for the problems in terms of their key parameters such as communication complexity and time/round complexity. Thus our work has made a significant contribution to the field of secure distributed computing by carrying out a foundation research on the three most important problems of this field.

We present a family of verifiable random functions which are provably secure for exponentially-large input spaces under a non-interactive complexity assumption. Prior constructions required either an interactive complexity assumption or one that could tolerate a factor 2^n security loss for n-bit inputs. Our construction is practical and inspired by the pseudorandom functions of Naor and Reingold and the verifiable random functions of Lysyanskaya. Set in a bilinear group, where the Decisional Diffie-Hellman problem is easy to solve, we require the Decisional Diffie-Hellman Exponent assumption in the standard model, without a common reference string. Our core idea is to apply a simulation technique where the large space of VRF inputs is collapsed into a small (polynomial-size) input in the view of the reduction algorithm. This view, however, is information-theoretically hidden from the attacker. Since the input space is exponentially large, we can first apply a collision-resistant hash function to handle arbitrarily-large inputs.

We consider the \textit{rational secret sharing problem} introduced by Halpern and Teague\cite{ht04}, where players prefer to get the secret rather than not to get the secret and with lower preference, prefer that as few of the other players get the secret. Some positive results have been derived by Kol and Naor\cite{stoc08} by considering that players only prefer to learn. They have proposed an efficient $m$-out-of-$n$ protocol for rational secret sharing without using cryptographic primitives. Their solution considers that players are of two types; one player is the short player and the rest of the players are long players. But their protocol is susceptible to coalitions if the short player colludes with any of the long players. We extend their protocol, and propose a completely collusion free, $\varepsilon$-Nash equilibrium protocol, when $n \geq 2m -1 $, where $n$ is the number of players and $m$ is the number of shares needed to construct the secret.

With today's dissemination of embedded systems manipulating sensitive data, it has become important to equip low-level programs with strong security guarantees. Unfortunately, security proofs as done by cryptographers are about algorithms, not about concrete implementations running on hardware. In this paper, we show how to extend security proofs to guarantee the security of assembly implementations of cryptographic primitives. Our approach is based on a framework in the Coq proof-assistant that integrates correctness proofs of assembly programs with game-playing proofs of provable security. We demonstrate the usability of our approach using the Blum-Blum-Shub (BBS) pseudorandom number generator, for which a MIPS implementation for smartcards is shown cryptographically secure.

Consider the following problem: a sender S and a receiver R are part of an unreliable, connected, distributed network. The distrust in the network is modelled by an entity called adversary, who has unbounded computing power and who can corrupt some of the nodes of the network (excluding S and R)in a variety of ways. S wishes to send to R a message m that consists of \ell elements, where \ell \geq 1, selected uniformly from a finite field F. The challenge is to design a protocol, such that after interacting with S as per the protocol, R should output m without any error (perfect reliability). Moreover, this hold irrespective of the disruptive actions done by the adversary. This problem is called reliable message transmission or RMT in short. The problem of secure message transmission or SMT in short requires an additional constraint that the adversary should not get any information about the message what so ever in information theoretic sense (perfect secrecy). Security against an adversary with infinite computing power is also known as non-cryptographic or information theoretic or Shannon security and this is the strongest notion of security. Notice that since the adversary has unbounded computing power, we cannot solve RMT and SMT problem by using classical cryptographic primitives such as public key cryptography, digital signatures, authentication schemes, etc as the security of all these primitives holds good only against an adversary having polynomially bounded computing power. RMT and SMT problem can be studied in various network models and adversarial settings. We may use the following parameters to describe different settings/models for studying RMT/SMT: \begin{enumerate} \item Type of Underlying Network --- Undirected Graph, Directed Graph, Hypergraph. \item Type of Communication --- Synchronous, Asynchronous. \item Adversary capacity --- Threshold Static, Threshold Mobile, Non-threshold Static, Non-threshold Mobile. \item Type of Faults --- Fail-stop, Passive, Byzantine, Mixed. \end{enumerate} Irrespective of the settings in which RMT/SMT is studied, the following issues are common: \begin{enumerate} \item Possibility: What are the necessary and sufficient structural conditions to be satisfied by the underlying network for the existence of any RMT/SMT protocol, tolerating a given type of adversary? \item Feasibility: Once the existence of a RMT/SMT protocol in a network is ascertained, the next natural question is, does there exist an efficient protocol on the given network? \item Optimality: Given a message of specific length, what is the minimum communication complexity (lower bound) needed by any RMT/SMT protocol to transmit the message and how to design a polynomial time RMT/SMT protocol whose total communication complexity matches the lower bound on the communication complexity (optimal protocol)? \end{enumerate} In this dissertation, we look into the above issues in several network models and adversarial settings. This thesis reports several new/improved/efficient/optimal solutions, gives affirmative/negative answers to several significant open problems and last but not the least, provides first solutions to several newly formulated problems.

We construct Weil numbers corresponding to genus-2 curves with $p$-rank 1 over the finite field $\F_{p^2}$ of $p^2$ elements. The corresponding curves can be constructed using explicit CM constructions. In one of our algorithms, the group of $\F_{p^2}$-valued points of the Jacobian has prime order, while another allows for a prescribed embedding degree with respect to a subgroup of prescribed order. The curves are defined over $\F_{p^2}$ out of necessity: we show that curves of $p$-rank 1 over $\F_p$ for large $p$ cannot be efficiently constructed using explicit CM constructions.

This note is an exposition of reductions among the q-strong Diffie-Hellman problem and related problems.

Boolean function in even number of variables is called {\it bent} if it is at the maximal possible Hamming distance from the class of all affine Boolean functions. We have proven that every isometric mapping of the set of all Boolean functions into itself that transforms bent functions into bent functions is a combination of an affine transform of coordinates and an affine shift.

Trust Based Collaborative Search is an interactive metasearch engine, presenting the user with clusters of results, based not only on the similarity of content, but also on the similarity of the recommending agents. The theory presented here is broad enough to cover search, browsing, recommendations, demographic profiling, and consumer targeting. We use the term search as an example. We developed a novel general trust theory. In this context, as a special case, we equate trust between agents with the similarity between their search-behaviors. The theory suggests that clusters should be close to maximal similarity within a tolerance dictated by the amount of uncertainty about the vectors of probabilities of attributes representing queries, pages and agents. In addition, we give a new theoretical analysis of clustering tolerances, enabling more judicial decisions about optimal tolerances. Specifically, we show that tolerances should at least be divided by a constant>1 as we descend from one layer in the hierarchical clustering to the next. We also show a promising connection between collaborative search and cryptography: A query plays the role of a cryptogram, the search engine is the cryptanalyst, and the user's intention is the cleartext. Shannon's unicity distance is the length of the search. It is needed to quantify the clustering-tolerance.

We consider the concept of rational secret sharing, which was initially introduced by Halpern and Teague \cite{ht04}, where players' preferences are that they prefer to learn the secret than not, and moreover they prefer that as few others learn the secret as possible. This paper is an attempt to introduce a rational secret sharing scheme which defers from previous RSS schemes in that this scheme does not rely on broadcast to send messages but instead uses point to point transmissions. Not only that, but the protocol will not rely on any cryptographic primitives and is coalition resilient except for when the short player colludes with a long player.

Trust is a central concept in public-key cryptography infrastruc- ture and in security in general. We study its initial quantification and its spread patterns. There is empirical evidence that in trust-based reputation model for virtual communities, it pays to restrict the clusters of agents to small sets with high mutual trust. We propose and motivate a mathematical model, where this phenomenon emerges naturally. In our model, we separate trust values from their weights. We motivate this separation using real examples, and show that in this model, trust converges to the extremes, agreeing with and accentuating the observed phenomenon. Specifically, in our model, cliques of agents of maximal mutual trust are formed, and the trust between any two agents that do not maximally trust each other, converges to zero. We offer initial practical relaxations to the model that preserve some of the theoretical flavor.

The game-based approach to security proofs in cryptography is a widely-used methodology for writing proofs rigorously. However a unifying language for writing games is still missing. In this paper we show how CSLR, a probabilistic lambda-calculus with a type system that guarantees that computations are probabilistic polynomial time, can be equipped with a notion of game indistinguishability. This allows us to dene cryptographic constructions, eective adversaries, security notions, computational assumptions, game transformations, and game-based security proofs in the unied framework provided by CSLR. Our code for cryptographic constructions is close to implementation in the sense that we do not assume primitive uniform distributions but use a realistic algorithm to approximate them. We illustrate our calculus on cryptographic constructions for public-key encryption and pseudorandom bit generation.

At Crypto 2005, Coron et al. introduced a formalism to study the presence or absence of structural flaws in iterated hash functions: If one cannot differentiate a hash function using ideal primitives from a random oracle, it is considered structurally sound, while the ability to differentiate it from a random oracle indicates a structural weakness. This model was devised as a tool to see subtle real world weaknesses while in the random oracle world. In this paper we take in a practical point of view. We show, using well known examples like NMAC and the Mix-Compress-Mix (MCM) construction, how we can prove a hash construction secure and insecure at the same time in the indifferentiability setting. These constructions do not differ in their implementation but only on an abstract level. Naturally, this gives rise to the question what to conclude for the implemented hash function. Our results cast doubts about the notion of “indifferentiability from a random oracle” to be a mandatory, practically relevant criterion (as e.g., proposed by Knudsen [16] for the SHA-3 competition) to separate good hash structures from bad ones.

We study a problem of secure data storage on hardware that may leak information. We introduce a new primitive, that we call {\em leakage-resilient storage} (LRS), which is an (unkeyed) scheme for encoding messages, and can be viewed as a generalization of the {\em All-Or-Nothing Transform} (AONT, Rivest 1997). The standard definition of AONT requires that it should be hard to reconstruct a message $m$ if not all the bits of its encoding $\Encode(m)$ are known. LRS is defined more generally, with respect to a class $\Gamma$ of functions. The security definition of LRS requires that it should be hard to reconstruct $m$ even if some values $g_1(\Encode(m)),\ldots,$ $g_t(\Encode(m))$ are known (where $g_1,\ldots,g_t \in \Gamma$), as long as the total length of $g_1(\Encode(m)),\ldots,g_t(\Encode(m))$ is smaller than some parameter $c$. We construct an LRS scheme that is secure with respect to $\Gamma$ being a set of functions that can depend only on some restricted part of the memory. More precisely: we assume that the memory is divided in $2$ parts, and the functions in $\Gamma$ can be just applied to one of these parts. We also construct a scheme that is secure if the cardinality of $\Gamma$ is restricted (but still it can be exponential in the length of the encoding). This construction implies security in the case when the set $\Gamma$ consists of functions that are computable by Boolean circuits of a small size. We also discuss the connection between the problem of constructing leakage-resilient storage and a theory of the compressibility of NP-instances.

In this paper, we study the complexity of solving hard knapsack problems, i.e., knapsacks with a density close to $1$ where lattice-based low density attacks are not an option. For such knapsacks, the current state-of-the-art is a 31-year old algorithm by Schroeppel and Shamir which is based on birthday paradox techniques and yields a running time of $\TildeOh(2^{n/2})$ for knapsacks of $n$ elements and uses $\TildeOh(2^{n/4})$ storage. We propose here two new algorithms which improve on this bound, finally lowering the running time down to $\TildeOh (2^{0.3113\, n})$ for almost all knapsacks of density $1$. We also demonstrate the practicality of these algorithms with an implementation.

In this paper, based on binary Golay complementary sequences, we propose some methods to construct Golay complementary sequences of length $2^n$ for integer n, over the $M^2$-$QAM$ constellation and $2M$-$Q$-$PAM$ constellations, where $M=2^m$ for integer $m$. A method to judge whether a sequence constructed using the new general offset pairs over the $QAM$ constellation is Golay complementary sequence is proposed. Base on this judging rule, we can construct many new Golay complementary sequences. In particular, we study Golay complementary sequences over $16$-$QAM$ constellation and $64$-$QAM$ constellation,many new Golay complementary sequences over these constellations have been found.

In this paper, we present new constructions for $ M^{2}$ -QAM and $2M$ $Q$-$PAM$ Golay complementary sequences of length $2^n$ for integer $n$, where $M=2^{m}$ for integer $m$. New decision conditions are proposed to judge whether an offset pairs can be used to construct the Golay complementary sequences over constellation, and with the new decision conditions, we prove the conjecture 1 proposed by Ying Li~\cite{16}. We describe a new offset pairs and construct new $64$-$QAM$ Golay sequences based on this new offset pairs. We also study the $128$-$QAM$ Golay complementary sequences, and propose a new decision condition to judge whether the sequences are $128$-$QAM$ Golay complementary.

We initiate the study of one-wayness under {\em correlated products}. We are interested in identifying necessary and sufficient conditions for a function $f$ and a distribution on inputs $(x_1, \ldots, x_k)$, so that the function $(f(x_1), \ldots, f(x_k))$ is one-way. The main motivation of this study is the construction of public-key encryption schemes that are secure against chosen-ciphertext attacks (CCA). We show that any collection of injective trapdoor functions that is secure under a very natural correlated product can be used to construct a CCA-secure public-key encryption scheme. The construction is simple, black-box, and admits a direct proof of security. It can be viewed as a simplification of the seminal work of Dolev, Dwork and Naor (SICOMP '00), while relying on a seemingly incomparable assumption. We provide evidence that security under correlated products is achievable by demonstrating that lossy trapdoor functions (Peikert and Waters, STOC '08) yield injective trapdoor functions that are secure under the above mentioned correlated product. Although we currently base security under correlated products on existing constructions of lossy trapdoor functions, we argue that the former notion is potentially weaker as a general assumption. Specifically, there is no fully-black-box construction of lossy trapdoor functions from trapdoor functions that are secure under correlated products.

R. Feng, and H. Wu recently established a certain mean-value formula for the x-coordinates of the n-division points on an elliptic curve given in Weierstrass form (A mean value formula for elliptic curves, 2010, available at http://eprint.iacr.org/2009/586.pdf ). We prove a similar result for both the x and y-coordinates on a twisted Edwards elliptic curve.

We use two parametrizations of points on elliptic curves in generalized Edwards form x^2 + y^2 = c^2 (1+d x^2 y^2) that omit the x-coordinate. The first parametrization leads to a differential addition formula that can be computed using 6M + 4S, a doubling formula using 1M+4S and a tripling formula using 4M + 7S. The second one yields a differential addition formula that can be computed using 5M+2S and a doubling formula using 5S. All formulas apply also for the case c <> 1 and arbitrary curve parameter d. This generalizes formulas from the literature for the special case c = 1. For both parametrizations the formula for recovering the missing X-coordinate is also provided.

We use security in the Universal Composition framework as a means to study the ``cryptographic complexity'' of 2-party secure computation tasks (functionalities). We say that a functionality $F$ {\em reduces to} another functionality $G$ if there is a UC-secure protocol for $F$ using ideal access to $G$. This reduction is a natural and fine-grained way to compare the relative complexities of cryptographic tasks. There are two natural ``extremes'' of complexity under the reduction: the {\em trivial} functionalities, which can be reduced to any other functionality; and the {\em complete} functionalities, to which any other functionality can be reduced. In this work we show that under a natural computational assumption (the existence of a protocol for oblivious transfer secure against semi-honest adversaries), there is a {\bf zero-one law} for the cryptographic complexity of 2-party deterministic functionalities. Namely, {\em every such functionality is either trivial or complete.} No other qualitative distinctions exist among functionalities, under this computational assumption. While nearly all previous work classifying multi-party computation functionalities has been restricted to the case of secure function evaluation, our results are the first to consider completeness of arbitrary {\em reactive} functionalities, which receive input and give output repeatedly throughout several rounds of interaction. One important technical contribution in this work is to initiate the comprehensive study of the cryptographic properties of reactive functionalities. We model these functionalities as finite automata and develop an automata-theoretic methodology for classifying and studying their cryptographic properties. Consequently, we completely characterize the reactive behaviors that lead to cryptographic non-triviality. Another contribution of independent interest is to optimize the hardness assumption used by Canetti et al.\ (STOC 2002) in showing that the common random string functionality is complete (a result independently obtained by Damgård et al.\ (TCC 2010)).

Motivated by the question of basing cryptographic protocols on stateless tamper-proof hardware tokens, we revisit the question of unconditional two-prover zero-knowledge proofs for $NP$. We show that such protocols exist in the {\em interactive PCP} model of Kalai and Raz (ICALP '08), where one of the provers is replaced by a PCP oracle. This strengthens the feasibility result of Ben-Or, Goldwasser, Kilian, and Wigderson (STOC '88) which requires two stateful provers. In contrast to previous zero-knowledge PCPs of Kilian, Petrank, and Tardos (STOC '97), in our protocol both the prover and the PCP oracle are efficient given an $NP$ witness. Our main technical tool is a new primitive that we call {\em interactive locking}, an efficient realization of an unconditionally secure commitment scheme in the interactive PCP model. We implement interactive locking by adapting previous constructions of {\em interactive hashing} protocols to our setting, and also provide a direct construction which uses a minimal amount of interaction and improves over our interactive hashing based constructions. Finally, we apply the above results towards showing the feasibility of basing unconditional cryptography on {\em stateless} tamper-proof hardware tokens, and obtain the following results: *) We show that if tokens can be used to encapsulate other tokens, then there exist unconditional and statistically secure (in fact, UC secure) protocols for general secure computation. *) Even if token encapsulation is not possible, there are unconditional and statistically secure commitment protocols and zero-knowledge proofs for $NP$. *) Finally, if token encapsulation is not possible, then no protocol can realize statistically secure oblivious transfer.

Knowledge extraction is a fundamental notion, modeling machine possession of values (witnesses) in a computational complexity sense and enabling one to argue about the internal state of a party in a protocol without probing its internal secret state. However, when transactions are concurrent (e.g., over the Internet) with players possessing public-keys (as is common in cryptography), assuring that entities ``know" what they claim to know, where adversaries may be well coordinated across different transactions, turns out to be much more subtle and in need of re-examination. Here, we investigate how to formally treat knowledge possession by parties (with registered public-keys) interacting over the Internet. Stated more technically, we look into the relative power of the notion of ``concurrent knowledge-extraction" (CKE) in the concurrent zero-knowledge (CZK) bare public-key (BPK) model where statements being proven can be dynamically and adaptively chosen by the prover. We show the potential vulnerability of man-in-the-middle (MIM) attacks turn out to be a real security threat to existing natural protocols running concurrently in the public-key model, which motivates us to introduce and formalize the notion of CKE, alone with clarification of various subtleties. Then, both generic (based on standard polynomial assumptions), and efficient (employing complexity leveraging in a novel way) implementations for NP are presented for constant-round (in particular, round-optimal) concurrently knowledge-extractable concurrent zero-knowledge (CZK-CKE) arguments in the BPK model. The efficient implementation can be further practically instantiated for specific number-theoretic language.

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

We show tight connections between several cryptographic primitives, namely encryption with weakly random keys, encryption with key-dependent messages (KDM), and obfuscation of point functions with multi-bit output(which we call multi-bit point functions, or MBPFs, for short). These primitives, which have been studied mostly separately in recent works, bear some apparent similarities, both in the flavor of their security requirements and in the flavor of their constructions and assumptions. Still, rigorous connections have not been drawn. Our results can be interpreted as indicating that MBPF obfuscators imply a very strong form of encryption that simultaneously achieves security for weakly-random keys and key-dependent messages as special cases. Similarly, each one of the other primitives implies a certain restricted form of MBPF obfuscation. Our results carry both constructions and impossibility results from one primitive to others. In particular: - The recent impossibility result for KDM security of Haitner and Holenstein (TCC '09) carries over to MBPF obfuscators. - The Canetti-Dakdouk construction of MBPF obfuscators based on a strong variant of the DDH assumption (EC '08) gives an encryption scheme which is secure w.r.t. any weak key distribution of super-logarithmic min-entropy (and in particular, also has very strong leakage resilient properties). - All the recent constructions of encryption schemes that are secure w.r.t. weak keys imply a weak form of MBPF obfuscators.

Let $\mathbb{F}_{q}$ be a finite field, $\mathbb{F}_{q^s}$ be an extension of $\mathbb{F}_q$, let $f(x)\in \mathbb{F}_q[x]$ be a polynomial of degree $n$ with $\gcd(n,q)=1$. We present a recursive formula for evaluating the exponential sum $\sum_{c\in \mathbb{F}_{q^s}}\chi^{(s)}(f(x))$. Let $a$ and $b$ be two elements in $\mathbb{F}_q$ with $a\neq 0$, $u$ be a positive integer. We obtain an estimate of the exponential sum $\sum_{c\in \mathbb{F}^*_{q^s}}\chi^{(s)}(ac^u+bc^{-1})$, where $\chi^{(s)}$ is the lifting of an additive character $\chi$ of $\mathbb{F}_q$. Some properties of the sequences constructed from these exponential sums are provided also.

In this note, we prove that the order of $x^p-x-1\in \F_p[x]$ is $\frac{p^p-1}{p-1}$, where $p$ is a prime and $\mathbb{F}_p$ is the finite field of size $p$. As a consequence, it is shown that $x^p-x-a\in \mathbb{F}_p[x]$ is primitive if and only if $a$ is a primitive element in $\mathbb{F}_p$.

Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Protocols designed under this assumption provide ``full security'' (and, in particular, guarantee output delivery and fairness) when this assumption holds; unfortunately, these protocols are completely insecure if this assumption is violated. On the other hand, protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a \emph{single} party is dishonest. It is natural to wonder whether it is possible to achieve the ``best of both worlds'': namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) but show some positive results regarding what \emph{can} be achieved.

Verifiable Secret Sharing (VSS) is a fundamental primitive used as a building block in many distributed cryptographic tasks, such as Secure Multiparty Computation (MPC) and Byzantine Agreement (BA). An important variant of VSS is Asynchronous VSS (AVSS) which is designed to work over asynchronous networks. AVSS is a two phase (Sharing, Reconstruction) protocol carried out among n parties in the presence of a computationally unbounded active adversary, who can corrupt up to t parties. We assume that every two parties in the network are directly connected by a pairwise secure channel. In this paper, we present a new statistical AVSS protocol with optimal resilience; i.e. with n = 3t+1. Our protocol privately communicates O((\ell n^3 + n^4 \log{\frac{1}{\epsilon}}) \log{\frac{1}{\epsilon}}) bits and A-casts O(n^3 \log(n)) bits to simultaneously share \ell \geq 1 elements from a finite field F, where \epsilon is the error parameter of our protocol. There are only two known statistical AVSS protocols with n = 3t+1 reported in [CR93] and [PCR09]. The AVSS protocol of [CR93] requires a private communication of O(n^9 (\log{\frac{1}{\epsilon}})^4) bits and A-cast of O(n^9 (\log{\frac{1}{\epsilon}})^2 \log(n)) bits to share a single element from F. Thus our AVSS protocol shows a significant improvement in communication complexity over the AVSS of [CR93]. The AVSS protocol of [PCR09] requires a private communication and A-cast of O((\ell n^3 + n^4) \log{\frac{1}{\epsilon}}) bits to share \ell \geq 1 elements. However, the shared element(s) may be NULL \not \in {\mathbb F}. Thus our AVSS is better than the AVSS of [PCR09] due to the following reasons: 1. The A-cast communication of our AVSS is independent of the number of secrets i.e. \ell; 2. Our AVSS makes sure that the shared value(s) always belong to F. Using our AVSS, we design a new primitive called Asynchronous Complete Secret Sharing (ACSS) which acts as an important building block of asynchronous multiparty computation (AMPC). Using our ACSS scheme, we design a statistical AMPC protocol with optimal resilience; i.e., with n = 3t+1, that privately communicates O(n^5 \log{\frac{1}{\epsilon}}) bits per multiplication gate. This significantly improves the communication complexity of only known optimally resilient statistical AMPC of [BKR93] that privately communicates \Omega(n^{11} (\log{\frac{1}{\epsilon}})^4) bits and A-cast \Omega(n^{11} (\log{\frac{1}{\epsilon}})^2 \log(n)) bits per multiplication gate. Both our ACSS and AVSS employ several new techniques, which are of independent interest.

In this paper, we revisit security notions for dedicated-key hash functions, considering two essential theoretical aspects; namely, formal definitions for security notions, and the relationships among them. Our contribution is twofold. First, we provide a new set of enhanced security notions for dedicated-key hash functions. The provision of this set of enhanced properties has been motivated by the introduction of enhanced target collision resistance (eTCR) property by Halevi and Krawczyk at Crypto 2006. We notice that the eTCR property does not belong to the set of the seven security notions previously investigated by Rogaway and Shrimpton at FSE 2004, namely: Coll, Sec, aSec, eSec, Pre, aPre and ePre. The fact that eTCR, as a new useful property, is the enhanced variant of the well-known TCR (a.k.a. eSec or UOWHF) property motivates one to investigate the possibility of providing enhanced variants for the other properties. We provide such an enhanced set of properties. Interestingly, there are six enhanced variants of security notions available, excluding ``ePre'' which can be demonstrated to be non-enhanceable. As the second and main part of our contribution, we provide a full picture of relationships (i.e. implications and separations) among the (thirteen) security properties including the (six) enhanced properties and the previously considered seven properties. The implications and separations are supported by formal proofs (reductions) and/or counterexamples in the concrete-security framework.

We introduce the notion of “non-malleable codes” which relaxes the notion of error correction and error detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. In contrast to error-correction and error-detection, non malleability can be achieved for very rich classes of modifications. We construct an efficient code that is non-malleable with respect to modifications that effect each bit of the codeword arbitrarily (i.e. leave it untouched, flip it or set it to either 0 or 1), but independently of the value of the other bits of the codeword. Using the probabilistic method, we also show a very strong and general statement: there exists a non-malleable code for every “small enough” family F of functions via which codewords can be modified. Although this probabilistic method argument does not directly yield efficient constructions, it gives us efficient non-malleable codes in the random-oracle model for very general classes of tampering functions-e.g. functions where every bit in the tampered codeword can depend arbitrarily on any 99% of the bits in the original codeword. As an application of non-malleable codes, we show that they provide an elegant algorithmic solution to the task of protecting functionalities implemented in hardware (e.g. signature cards) against “tampering attacks”. In such attacks, the secret state of a physical system is tampered, in the hopes that future interaction with the modified system will reveal some secret information. This problem, was previously studied in the work of Gennaro et al. in 2004 under the name “algorithmic tamper proof security” (ATP). We show that non-malleable codes can be used to achieve important improvements over the prior work. In particular, we show that any functionality can be made secure against a large class of tampering attacks, simply by encoding the secret-state with a non-malleable code while it is stored in memory.

\begin{abstract} Let assume that Alice, Bob, and Charlie, the three classical people of cryptography are not limited anymore to perform a finite number of computations on real computers, but are limited to $\alpha$ computations and to $\alpha$ bits of memory, where $\alpha$ is a fixed infinite cardinal. For example $\alpha = \aleph _0$ (the countable cardinal, i.e. the cardinal of $\mathbb {N}$ the set of integers), or $\alpha = \mathfrak {C}$ (the cardinal of the set $\mathbb {R}$ of real numbers). Is it possible to do secret key cryptography? Public key cryptography? Encryption? Authentication? Signatures? Is it possible to generalize the notion of one way function? The aim of this paper is to give some elements of answers to these questions. We will see for example that for secret key cryptography there are some simple solutions. However for public key cryptography the results are much less clear. \end{abstract}

Efficient characteristic set methods for computing solutions of a polynomial equation system in a finite field are proposed. We introduce the concept of proper triangular sets and prove that proper triangular sets are square-free and have solutions. We present an improved algorithm which can be used to reduce the zero set of an equation system in general form to the union of zero sets of proper triangular sets. Bitsize complexity for the algorithm is given in the case of Boolean polynomials. We also give a characteristic set method for Boolean polynomials, where the size of the polynomials are effectively controlled. The methods are implemented and extensive experiments show that they are quite efficient for solving equations raised in analyzing certain classes of stream ciphers.

In the context of secure point-to-point message transmission in networks with minimal connectivity, previous studies showed that feedbacks from the receiver to the sender can be used to reduce the requirements of network connectivity. We observe that the way how feedbacks were used in previous work does not guarantee perfect privacy to the transmitted message, when the adversary performs a Guessing Attack. In this paper, we shall describe our new Guessing Attack to some existing protocols (in fact, we are the first to point out a flaw in the protocols of Desmedt-Wang's Eurocrypt'02 paper and of Patra-Shankar-Choudhary-Srinathan-Rangan's CANS'07 paper), and propose a scheme defending against a general adversary structure. In addition, we also show how to achieve almost perfectly secure message transmission with feedbacks when perfect reliability or perfect privacy is not strictly required.

We revisit the composability of different forms of zero-knowledge proofs when the honest prover strategy is restricted to be polynomial time (given an appropriate auxiliary input). Our results are: \begin{enumerate} \item When restricted to efficient provers, the original Goldwasser--Micali--Rackoff (GMR) definition of zero knowledge (STOC `85), here called \emph{plain zero knowledge}, is closed under a constant number of sequential compositions (on the same input). This contrasts with the case of unbounded provers, where Goldreich and Krawczyk (ICALP `90, SICOMP `96) exhibited a protocol that is zero knowledge under the GMR definition, but for which the sequential composition of 2 copies is not zero knowledge. \item If we relax the GMR definition to only require that the simulation is indistinguishable from the verifier's view by uniform polynomial-time distinguishers, with no auxiliary input beyond the statement being proven, then again zero knowledge is not closed under sequential composition of 2 copies. \item We show that auxiliary-input zero knowledge with efficient provers is not closed under {\em parallel} composition of 2 copies under the assumption that there is a secure key agreement protocol (in which it is easy to recognize valid transcripts). Feige and Shamir (STOC `90) gave similar results under the seemingly incomparable assumptions that (a) the discrete logarithm problem is hard, or (b) $\UP\not\subseteq \BPP$ and one-way functions exist. \end{enumerate}

In this paper, the twisted Jacobi intersections which contains Jacobi intersections as a special case is introduced. We show that every elliptic curve over the prime field with three points of order $2$ is isomorphic to a twisted Jacobi intersections curve. Some fast explicit formulae for twisted Jacobi intersections curves in projective coordinates are presented. These explicit formulae for addition and doubling are almost as fast as the Jacobi intersections. In addition, the scalar multiplication can be more effective in twisted Jacobi intersections than in Jacobi intersections. Moreover, we propose new addition formulae which are independent of parameters of curves and more effective in reality than the previous formulae in the literature.

We study the necessary and sufficient assumptions for universally composable (UC) computation, both in terms of setup and computational assumptions. We look at the common reference string model, the common random string model and the key-registration authority (KRA) model, and provide new result for all of them. Perhaps most interestingly we show that: - For even the minimal meaningful KRA, where we only assume that the secret key is a value which is hard to compute from the public key, one can UC securely compute any poly-time functionality if there exists a passive secure oblivious-transfer protocol for the stand-alone model. Since a KRA where the secret keys can be computed from the public keys is useless, and some setup assumption is needed for UC secure computation, this establishes the best we could hope for the KRA model: any non-trivial KRA is sufficient for UC computation. - We show that in the KRA model one-way functions are sufficient for UC commitment and UC zero-knowledge. These are the first examples of UC secure protocols for non-trivial tasks which do not assume the existence of public-key primitives. In particular, the protocols show that non-trivial UC computation is possible in Minicrypt.

Enhanced Target Collision Resistance (eTCR) property for a hash function was put forth by Halevi and Krawczyk in Crypto 2006, in conjunction with the randomized hashing mode that is used to realize such a hash function family. eTCR is a strengthened variant of the well-known TCR (or UOWHF) property for a hash function family (i.e. a dedicated-key hash function). The contributions of this paper are twofold. First, we compare the new eTCR property with the well-known collision resistance (CR) property, where both properties are considered for a dedicated-key hash function. We show there is a separation between the two notions, that is, in general, eTCR property cannot be claimed to be weaker (or stronger) than CR property for any arbitrary dedicated-key hash function. Second, we consider the problem of eTCR property preserving domain extension. We study several domain extension methods for this purpose, including (Plain, Strengthened, and Prefix-free) Merkle-Damgård, Randomized Hashing (considered in dedicated-key hash setting), Shoup, Enveloped Shoup, XOR Linear Hash (XLH), and Linear Hash (LH) methods. Interestingly, we show that the only eTCR preserving method is a nested variant of LH which has a drawback of having high key expansion factor. Therefore, it is interesting to design a new and efficient eTCR preserving domain extension in the standard model.

THIS REPORT IS REPLACED BY REPORT 2009/590.

For a prime $p$ with $p\equiv 3\,({\rm mod}\, 4)$ and an odd number $m$, the Bentness of the $p$-ary binomial function $f_{a,b}(x)={\rm Tr}_{1}^n(ax^{p^m-1})+{\rm Tr}_{1}^2(bx^{\frac{p^n-1}{4}})$ is characterized, where $n=2m$, $a\in \bF_{p^n}^*$, and $b\in \bF_{p^2}^*$. The necessary and sufficient conditions of $f_{a,b}(x)$ being Bent are established respectively by an exponential sum and two sequences related to $a$ and $b$. For the special case of $p=3$, we further characterize the Bentness of the ternary function $f_{a,b}(x)$ by the Hamming weight of a sequence.

The Yao's theorem gives an equivalence between the indistinguishability of a pseudorandom generator and the impredictability of the next bit from an asymptotic point of view. We present in this paper, with detailed proofs, some modified versions of the Yao's theorem which can be of interest for the study of practical systems. We study the case of one pseudorandom generator, then the case of a family of pseudorandom generators having the same fixed length and last an asymptotical version of the previous result. We compute in each case the cost of the reduction between the two algorithms.

We show that there is a direct relation between the maximum length of the keys extracted from biometric data and the error rates of the biometric system. The length of the bio-key depends on the amount of distinguishing information that can be extracted from the source data. This information can be used a-priori to evaluate the potential of the biometric data in the context of a speci&#64257;c cryptographic application. We model the biometric data more naturally as a continuous distribution and we give a new de&#64257;nition for fuzzy extractors that works better for this type of data.

Boolean bent functions were introduced by Rothaus (1976) as combinatorial objects related to difference sets, and have since enjoyed a great popularity in symmetric cryptography and low correlation sequence design. In this paper direct links between Boolean bent functions, generalized Boolean bent functions (Schmidt, 2006) and quaternary bent functions (Kumar, Scholtz, Welch, 1985) are explored. We also study Gray images of bent functions and notions of generalized nonlinearity for functions that are relevant to generalized linear cryptanalysis.

We formalize a hierarchy of adversary models for security protocol analysis, ranging from a Dolev-Yao style adversary to more powerful adversaries who can reveal different parts of principals' states during protocol execution. We define our hierarchy by a modular operational semantics describing adversarial capabilities. We use this to formalize various, practically-relevant notions of key and state compromise. Our semantics can be used as a basis for protocol analysis tools. As an example, we extend an existing symbolic protocol-verification tool with our adversary models. The result is the first tool that systematically supports notions such as weak perfect forward secrecy, key compromise impersonation, and adversaries capable of so-called strong corruptions and state-reveal queries. As further applications, we use our model hierarchy to relate different adversarial notions, gaining new insights on their relative strengths, and we use our tool to find new attacks on protocols.

The covering radius problem in any dimension is not known to be solvable in nondeterministic polynomial time, but when in dimension two, we give a deterministic polynomial time algorithm by computing a reduced basis using Gauss' algorithm in this paper.

We present the UC/c framework, a general definition for secure and incoercible multi-party protocols. Our framework allows to model arbitrary reactive protocol tasks (by specifying an ideal functionality) and comes with a universal composition theorem. We show that given natural setup assumptions, we can construct incoercible two-party protocols realising arbitrary functionalities (with respect to static adversaries).

Canetti, Goldreich, Goldwasser, and Micali (STOC 2000) introduced the notion of resettable zero-knowledge proofs, where the protocol must be zero-knowledge even if a cheating verifier can reset the prover and have several interactions in which the prover uses the same random tape. Soon afterwards, Barak, Goldreich, Goldwasser, and Lindell (FOCS 2001) studied the closely related notion of resettable soundness, where the soundness condition of the protocol must hold even if the cheating prover can reset the verifier to have multiple interactions with the same verifier's random tape. The main problem left open by this work was whether it is possible to have a single protocol that is simultaneously resettable zero knowledge and resettably sound. We resolve this question by constructing such a protocol. At the heart of our construction is a new non-black-box simulation strategy, which we believe to be of independent interest. This new strategy allows for simulators which ``marry'' recursive rewinding techniques (common in the context of concurrent simulation) with non-black-box simulation. Previous non-black-box strategies led to exponential blowups in computational complexity in such circumstances, which our new strategy is able to avoid.

Symbolic analysis of cryptographic protocols is dramatically simpler than full-fledged cryptographic analysis. In particular, it is readily amenable to automation. However, symbolic analysis does not a priori carry any cryptographic soundness guarantees. Following recent work on cryptographically sound symbolic analysis, we demonstrate how Dolev-Yao style symbolic analysis can be used to assert the security of cryptographic protocols within the universally composable (UC) security framework. Consequently, our methods enable security analysis that is completely symbolic, and at the same time cryptographically sound with strong composability properties. More specifically, we define a mapping from a class of cryptographic protocols to Dolev-Yao style symbolic protocols. For this mapping, we show that the symbolic protocol satisfies a certain symbolic criterion if and only if the corresponding cryptographic protocol is UC-secure. We concentrate on mutual authentication and key-exchange protocols that use public-key encryption as their only cryptographic primitive. For mutual authentication, our symbolic criterion is similar to the traditional Dolev-Yao criterion. For key exchange, we demonstrate that the traditional Dolev-Yao style symbolic criterion is insufficient, and formulate an adequate symbolic criterion. Finally, to demonstrate the viability of the treatment, we use an existing automated verification tool to assert UC security of some prominent key exchange protocols.

In this paper, we describe an improvement of the Berlekamp algorithm for binomials $x^n - a$ over prime fields $\mathbb{F}_{p}$. We implement the proposed method for various cases and compare the results with the original Berlekamp method. The proposed method can be extended easily to the case where the base field is not a prime field.

In this paper, we re-visit the problem of perfectly secure message transmission (PSMT) in a directed network under the presence of a threshold adaptive Byzantine adversary, having unbounded computing power. Desmedt et.al have given the characterization for three or more phase PSMT protocols over directed networks. Recently, Patra et. al. have given the characterization of two phase PSMT over directed networks. Even though the issue of tradeoff between phase complexity and communication complexity of PSMT protocols has been resolved in undirected networks, nothing is known in the literature regarding directed networks. In this paper, we completely settle down this issue. Specifically, we derive the lower bounds on communication complexity of (a) two phase PSMT protocols and (b) three or more phase PSMT protocols in directed networks. Moreover, we show that our lower bounds are asymptotically tight, by designing communication optimal PSMT protocols in directed networks, which are first of their kind. We re-visit the problem of perfectly reliable message transmission (PRMT) as well. Any PRMT protocol that sends a message containing $\ell$ field elements, has a trivial lower bound of ­O($\ell$) field elements on its communication complexity. Thus any PRMT protocol that sends a message of $\ell$ eld elements by communicating O(\ell) field elements, is referred as communication optimal PRMT or PRMT with constant factor overhead. Here, we characterize the class of directed networks over which communication optimal PRMT or PRMT with constant factor overhead is possible. Moreover, we design a communication optimal PRMT over a directed network that satisfies the conditions stated in our characterization. Our communication optimal PRMT/PSMT protocols employ several new techniques based on coding theory, which are of independent interest.

Zero-knowledge protocols are often studied through specific problems, like Graph-Isomorphism. In many cases this approach prevents an important level of abstraction and leads to limited results, whereas in fact the constructions apply to a wide variety of problems. We propose to address this issue with a formal framework of non-interactive instance-dependent commitment schemes (NIC). We define NIC in both the perfect, statistical, and computational settings, and formally characterize problems admitting NIC in all of these settings. We also prove other useful lemmas such as closure properties. Consequently, results that previously applied only to specific problems are now strengthened by our framework to apply to classes of problems. By providing formal yet intuitive tools, our framework facilitates the construction of zero-knowledge protocols for a wide variety of problems, in various settings, without the need to refer to a specific problem. Our results are unconditional.

Precise concurrent zero-knowledge is a new notion introduced by Pandey et al. \cite{P:P:M:T:V} in Eurocrypt'08 (which generalizes the work on precise zero-knowledge by Micali and Pass \cite{M:P} in STOC'06). This notion captures the idea that the view of any verifier in concurrent interaction can be reconstructed in the almost same time. \cite{P:P:M:T:V} constructed some (private-coin) concurrent zero-knowledge argument systems for $\NP$ which achieve precision in different levels and all these protocols use at least $\omega(\log n)$ rounds. In this paper we investigate the feasibility of reducing the round complexity and still keeping precision simultaneously. Our result is that we construct a public-coin precise bounded-concurrent zero-knowledge argument system for $\NP$ only using almost constant rounds, i.e., $\omega(1)$ rounds. Bounded-concurrency means an a-priori bound on the (polynomial) number of concurrent sessions is specified before the protocol is constructed. Our result doesn't need any setup assumption. We stress that this result cannot be obtained by \cite{P:P:M:T:V} even in bounded-concurrent setting.

In many of the cryptography applications like password or IP address encryption schemes, symmetric cryptography is useful. In these relatively simpler applications of cryptography, asymmetric cryptography is difficult to justify on account of the computational and implementation complexities associated with asymmetric cryptography. Symmetric schemes make use of a single shared key known only between the two communicating hosts. This shared key is used both for the encryption as well as the decryption of data. This key has to be small in size besides being a subset of a potentially large keyspace making it convenient for the communicating hosts while at the same time making cryptanalysis difficult for the potential attackers. In the present work, an abstract Rossler nonlinear dynamical machine has been described first. The Rossler system exhibits chaotic dynamics for certain values of system parameters and initial conditions. The chaotic dynamics of the Rossler system with its apparently erratic and irregular characteristics and extreme sensitivity to the initial conditions has been used for the design of the cryptographic key in an attempt to increase the confusion and the challenge for the potential attackers.

The abstraction of cryptographic operations by term algebras, called Dolev-Yao models, is essential in almost all tool-supported methods for proving security protocols. Recently significant progress was made in proving that Dolev-Yao models offering the core cryptographic operations such as encryption and digital signatures can be sound with respect to actual cryptographic realizations and security definitions. Recent work, however, has started to extend Dolev-Yao models to more sophisticated operations with unique security features. Zero-knowledge proofs arguably constitute the most amazing such extension. In this paper, we first identify which additional properties a cryptographic (non-interactive) zero-knowledge proof needs to fulfill in order to serve as a computationally sound implementation of symbolic (Dolev-Yao style) zero-knowledge proofs; this leads to the novel definition of a symbolically-sound zero-knowledge proof system. We prove that even in the presence of arbitrary active adversaries, such proof systems constitute computationally sound implementations of symbolic zero-knowledge proofs. This yields the first computational soundness result for symbolic zero-knowledge proofs and the first such result against fully active adversaries of Dolev-Yao models that go beyond the core cryptographic operations.

In the present paper we study properties of perfectly balanced Boolean functions. Based on the concept of Boolean function barrier, we propose a novel approach to construct large classes of perfectly balanced Boolean functions.

Traditionally, the definition of zero-knowledge states that an interactive proof of $x\in L$ provides zero (additional) knowledge if the view of any \emph{polynomial-time} verifier can be reconstructed by a \emph{polynomial-time} simulator. Since this definition only requires that the worst-case running-time of the verifier and simulator are polynomials, zero-knowledge becomes a worst-case notion. In STOC'06, Micali and Pass proposed a new notion of precise zero-knowledge, which captures the idea that the view of any verifier in every interaction can be reconstructed in (almost) the same time (i.e., the view can be ``indistinguishably reconstructed''). This is the strongest notion among the known works towards precislization of the definition of zero-knowledge. However, as we know, there are two kinds of computational resources (i.e. time and space) that every algorithm consumes in computation. Although the view of a verifier in the interaction of a precise zero-knowledge protocol can be reconstructed in almost the same time, the simulator may run in very large space while at the same time the verifier only runs in very small space. In this case it is still doubtful to take indifference for the verifier to take part in the interaction or to run the simulator. Thus the notion of precise zero-knowledge may be still insufficient. This shows that precislization of the definition of zero-knowledge needs further investigation. In this paper, we propose a new notion of precise time and space simulatable zero-knowledge (PTSSZK), which captures the idea that the view of any verifier in each interaction can be reconstructed \emph{not only} in the same time, \emph{but also} in the same space. We construct the first PTSSZK proofs and arguments with simultaneous linear time and linear space precisions for all languages in $\NP$. Our protocols do not use noticeably more rounds than the known precise zero-knowledge protocols, and the probability analysis of the successful extraction of the new simulation strategy may be of independent interests.

The definition of IND-CCA disallows an adversary from querying the challenge ciphertext to its decryption oracle. We point out that there are several ways to formalize this. We show that, surprisingly, for public-key encryption the resulting notions are not all equivalent. We then consider the same question for key-encapsulation mechanisms (KEMs) and show that in this case the four notions ARE all equivalent. Our discoveries are another manifestation of the subtleties that make the study of cryptography so attractive and are important towards achieving the definitional clarity and unity required for firm foundations.

Computational indistinguishability amplification is the problem of strengthening cryptographic primitives whose security is defined by bounding the distinguishing advantage of an efficient distinguisher. Examples include pseudorandom generators (PRGs), pseudorandom functions (PRFs), and pseudorandom permutations (PRPs). The literature on computational indistinguishability amplification consists only of few isolated results. Yao's XOR-lemma implies, by a hybrid argument, that no efficient distinguisher has advantage better than (roughly) $n2^{m-1} \delta^m$ in distinguishing the XOR of $m$ independent $n$-bit PRG outputs $S_1,\ldots,S_m$ from uniform randomness if no efficient distinguisher has advantage more than $\delta$ in distinguishing $S_i$ from a uniform $n$-bit string. The factor $2^{m-1}$ allows for security amplification only if $\delta<\frac{1}{2}$: For the case of PRFs, a random-offset XOR-construction of Myers was the first result to achieve {\em strong} security amplification, i.e., also for $\frac{1}{2} \le \delta < 1$. This paper proposes a systematic treatment of computational indistinguishability amplification. We generalize and improve the above product theorem for the XOR of PRGs along five axes. First, we prove the {\em tight} information-theoretic bound $2^{m-1}\delta^m$ (without factor $n$) also for the computational setting. Second, we prove results for {\em interactive} systems (e.g. PRFs or PRPs). Third, we consider the general class of {\em neutralizing combination constructions}, not just XOR. As an application this yields the first indistinguishability amplification results for the cascade of PRPs (i.e., block ciphers) converting a weak PRP into an arbitrarily strong PRP, both for single-sided and two-sided queries. Fourth, {\em strong} security amplification is achieved for a subclass of neutralizing constructions which includes as a special case the construction of Myers. As an application we obtain highly practical optimal security amplification for block ciphers, simply by adding random offsets at the input and output of the cascade. Fifth, we show strong security amplification also for {\em weakened assumptions} like security against random-input (as opposed to chosen-input) attacks. A key technique is a generalization of Yao's XOR-lemma to (interactive) systems, which is of independent interest.