In this paper, we present a new class of semi-bent quadratic Boolean functions of the form $f(x)=\sum_{i=1}^{\lfloor\frac{m-1}{2}\rfloor}Tr^n_1(c_ix^{1+4^{i}})$ $~(c_i\in \mathbb{F}_4$,$n=2m)$. We first characterize the semi-bentness of these quadratic Boolean functions. There exists semi-bent functions only when $m$ is odd. For the case: $m=p^r$, where $p$ is an odd prime with some conditions, we enumerate the semi-bent functions. Further, we give a simple characterization of semi-bentness for these functions with linear properties of $c_i$. In particular, for a special case of $p$, any quadratic Boolean function $f(x)=\sum_{i=1}^{\frac{p-1}{2}}Tr^{2p}_1(c_ix^{1+4^{i}})$ over $\mathbb{F}_{2^{2p}}$ is a semi-bent function.

What is the behavior of an adversary to launch attacks against a communication? The good choice is to eavesdrop the communication such that the communicators can not detect the eavesdropping. The general choice is to disrupt the communication at low cost, say, measuring the transferred quantum signals in the well-known BB84 quantum key distribution protocol. The bad choice is to disrupt it at even high cost, such as severing copper or fiber, if it is necessary. In this note we remark that a quantum communication is very vulnerable to low cost attacks. The plan to build a large quantum photonic network is infeasible.

The aim of this paper is to present a new way of computing short addition-subtraction chains using the generalized continued fractions where subtraction is allowed. We will recover the most used ways of getting addition-subtraction chains. This method is not always optimal but gives minimal chains that are easy to compute.

Most computational soundness theorems deal with a limited number of primitives, thereby limiting their applicability. The notion of deduction soundness of Cortier and Warinschi (CCS'11) aims to facilitate soundness theorems for richer frameworks via composition results: deduction soundness extends, generically, with asymmetric encryption and public data structures. Unfortunately, that paper also hints at rather serious limitations regarding further composition results: composability with digital signatures seems to be precluded. In this paper we provide techniques for bypassing the perceived limitations of deduction soundness and demonstrate that it enjoys vastly improved composition properties. More precisely, we show that a deduction sound implementation can be modularly extended with all of the basic cryptographic primitives (symmetric/asymmetric encryption, message authentication codes, digital signatures, and hash functions). We thus obtain the first soundness framework that allows for the joint use of multiple instances of all of the basic primitives. In addition, we show how to overcome an important restriction of the bare deduction soundness framework which forbids sending encrypted secret keys. In turn, this prevents its use for the analysis of a large class of interesting protocols (e.g. key exchange protocols). We allow for more liberal uses of keys as long as they are hidden in a sense that we also define. All primitives typically used to send secret data (symmetric/asymmetric encryption) satisfy our requirement which we also show to be preserved under composition.

In this paper, we describe a new algorithm for discrete logarithms in small characteristic. This algorithm is based on index calculus and includes two new contributions. The first is a new method for generating multiplicative relations among elements of a small smoothness basis. The second is a new descent strategy that allows us to express the logarithm of an arbitrary finite field element in terms of the logarithm of elements from the smoothness basis. For a small characteristic finite field of size $Q=p^n$, this algorithm achieves heuristic complexity $L_Q(1/4+o(1)).$ For technical reasons, unless $n$ is already a composite with factors of the right size, this is done by embedding $\GF{Q}$ in a small extension $\GF{Q^e}$ with $e\leq 2\lceil \log_p n \rceil$.

We remark that AKS primality testing algorithm needs about 1,000,000,000 G (gigabyte) storage space for a number of 1024 bits. Such storage requirement is hard to meet in practice. To the best of our knowledge, it is impossible for current operating systems to write and read data in so huge storage space. Thus, the running time for AKS algorithm shuould not be simply estimated as usual in terms of the amount of arithmetic operations.

We study various classical secure computation problems in the context of fairness, and relate them with each other. We also systematically study fair sampling problems (i.e., inputless functionalities) and discover three levels of complexity for them. Our results include the following: -Fair exchange cannot be securely reduced to the problem of fair coin-tossing by an r-round protocol, except with an error that is $\Omega(1/r)$. -Finite fair {\em sampling} problems with rational probabilities can all be reduced to fair coin-tossing and unfair 2-party computation (or equivalently, under computational assumptions). Thus, for this class of functionalities, fair coin-tossing is complete. -Only sampling problems which have fair protocols without any fair setup are the trivial ones in which the two parties can sample their outputs independently. Others all have an $\Omega(1/r)$ error, roughly matching an upper bound for fair sampling from Moran et al. (TCC 2009). -We study communication-less protocols for sampling, given another sampling problem as setup, since such protocols are inherently fair. We use spectral graph theoretic tools to show that it is impossible to reduce a sampling problem with {\em common information} (like fair coin-tossing) to a sampling problem without (like 'noisy' coin-tossing, which has a small probability of disagreement). The last result above is a slightly sharper version of a classical result by Witsenhausen from 1975. Our proof reveals the connection between the tool used by Witsenhausen, namely 'maximal correlation', and spectral graph theoretic tools like Cheeger inequality.

We present a new, more constructive proof of von Neumann's Min-Max Theorem for two-player zero-sum game --- specifically, an algorithm that builds a near-optimal mixed strategy for the second player from several best-responses of the second player to mixed strategies of the first player. The algorithm extends previous work of Freund and Schapire (Games and Economic Behavior '99) with the advantage that the algorithm runs in poly(n) time even when a pure strategy for the first player is a distribution chosen from a set of distributions over {0,1}^n. This extension enables a number of additional applications in cryptography and complexity theory, often yielding uniform security versions of results that were previously only proved for nonuniform security (due to use of the non-constructive Min-Max Theorem). We describe several applications, including: a more modular and improved uniform version of Impagliazzo's Hardcore Theorem (FOCS '95); regularity theorems that provide efficient simulation of distributions within any sufficiently nice convex set (extending a result of Trevisan, Tulsiani and Vadhan (CCC '09)); an improved version of the Weak Regularity Lemma of Frieze and Kannan; a Dense Model Theorem for uniform algorithms; and showing impossibility of constructing Succinct Non-Interactive Arguments (SNARGs) via black-box reductions under uniform hardness assumptions (using techniques from Gentry and Wichs (STOC '11) for the nonuniform setting).

This paper explores ways of performing commutative tasks by $N$ parties. Tasks are defined as {\sl commutative} if the order at which parties perform tasks can be freely changed without affecting the final result. It is easy to see that arbitrary $N$-party commutative tasks cannot be completed in less than $N-1$ basic time units. We conjecture that arbitrary $N$-party commutative tasks cannot be performed in $N-1$ time units by exchanging less than $4N-6$ messages and provide computational evidence in favor this conjecture. We also explore the most equitable commutative task protocols.

Yao's garbled circuit construction transforms a boolean circuit $C:\{0,1\}^n\to\{0,1\}^m$ into a ``garbled circuit'' $\hat{C}$ along with $n$ pairs of $k$-bit keys, one for each input bit, such that $\hat{C}$ together with the $n$ keys corresponding to an input $x$ reveal $C(x)$ and no additional information about $x$. The garbled circuit construction is a central tool for constant-round secure computation and has several other applications. Motivated by these applications, we suggest an efficient arithmetic variant of Yao's original construction. Our construction transforms an arithmetic circuit $C : \mathbb{Z}^n\to\mathbb{Z}^m$ over integers from a bounded (but possibly exponential) range into a garbled circuit $\hat{C}$ along with $n$ affine functions $L_i : \mathbb{Z}\to \mathbb{Z}^k$ such that $\hat{C}$ together with the $n$ integer vectors $L_i(x_i)$ reveal $C(x)$ and no additional information about $x$. The security of our construction relies on the intractability of the learning with errors (LWE) problem.

Besides Karatsuba algorithm, optimal Toeplitz matrix-vector product (TMVP) formulae is another approach to design GF(2^n) subquadratic multipliers. However, when GF(2^n) elements are represented using a shifted polynomial basis, this approach is currently appliable only to GF(2^n)s generated by all irreducible trinomials and a special type of irreducible pentanomials, not all general irreducible pentanomials. The reason is that no transformation matrix, which transforms the Mastrovito matrix into a Toeplitz matrix, has been found. In this article, we propose such a transformation matrix and its inverse matrix for an arbitrary irreducible pentanomial. Because there is no known value of n for which either an irreducible trinomial or an irreducible pentanomial does not exist, this transformation matrix makes the TMVP approach a universal tool, i.e., it is applicable to all practical GF(2^n)s.

The ``learning with errors'' (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications. Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. A main open question was whether LWE and its applications could be made truly efficient by exploiting extra algebraic structure, as was done for lattice-based hash functions (and related primitives). We resolve this question in the affirmative by introducing an algebraic variant of LWE called \emph{ring-LWE}, and proving that it too enjoys very strong hardness guarantees. Specifically, we show that the ring-LWE distribution is pseudorandom, assuming that worst-case problems on ideal lattices are hard for polynomial-time quantum algorithms. Applications include the first truly practical lattice-based public-key cryptosystem with an efficient security reduction; moreover, many of the other applications of LWE can be made much more efficient through the use of ring-LWE.

We construct new randomized algorithms to find the exact solution to the shortest and closest vector problems (SVP and CVP) in Euclidean norm (l2) for the integral lattice. Not only the minimal norm of non-zero lattice vectors in SVP and the minimal distance in CVP, but also how many lattice vectors reach those minimums can be simultaneously computed by the algorithms. Our approach is based on some special properties of the generating function of lattice vectors’ (l2-)norms, the lattice-associated theta function, which is used in prior works mainly for hardness analysis on lattice problems but rarely for computational purposes. Such function’s modular properties are exploited to develop our SVP and CVP solvers. In computational complexity perspective and take our SVP solver as an example, for the integral lattice family {Λn} of dimension dimΛn=n and level h=l(Λn) (the minimal positive integer such that the dual lattice Λn* scaled by h1/2 is integral) polynomial in n, the case frequently occurring in applications, this algorithm can find the minimal l2-norm of non-zero lattice vectors and the number of such shortest vectors in Λn with success probability 1-ε in asymptotic space complexity of polynomial in n and asymptotic time complexity of nO(n)log(1/ε). The only contribution to the algorithm’s exponential time complexity nO(n)log(1/ε) comes from independently repeating a randomized lattice vector sampler nO(n)log(1/ε) times. All the rest of operations contribute to the algorithm’s time-complexity only with an additive polynomial in n. Similar situations occur when solving the exact CVP by our algorithm. In other words, our solvers can be easily parallelized to be polynomial in time complexity. In addition, a variant of our CVP solver can solve the closest vector problem with preprocessing (CVPP) in polynomial time and nO(n)log(1/ε) space complexity.

The Fiat-Shamir transformation is a famous technique to turn identification schemes into signature schemes. The derived scheme is provably secure in the random-oracle model against classical adversaries. Still, the technique has also been suggested to be used in connection with quantum-immune identification schemes, in order to get quantum-immune signature schemes. However, a recent paper by Boneh et al. (Asiacrypt 2011) has raised the issue that results in the random-oracle model may not be immediately applicable to quantum adversaries, because such adversaries should be allowed to query the random oracle in superposition. It has been unclear if the Fiat-Shamir technique is still secure in this quantum oracle model (QROM). Here, we discuss that giving proofs for the Fiat-Shamir transformation in the QROM is presumably hard. We show that there cannot be black-box extractors, as long as the underlying quantum-immune identification scheme is secure against active adversaries and the first message of the prover is independent of its witness. Most schemes are of this type. We then discuss that for some schemes one may be able to resurrect the Fiat-Shamir result in the QROM by modifying the underlying protocol first. We discuss in particular a version of the Lyubashevsky scheme which is provably secure in the QROM.

Preneel et al.~(Crypto 1993) assessed 64 possible ways to construct a compression function out of a blockcipher. They conjectured that 12 out of these 64 so-called PGV constructions achieve optimal security bounds for collision resistance and preimage resistance. This was proven by Black et al.~(Journal of Cryptology, 2010), if one assumes that the blockcipher is ideal. This result, however, does not apply to ``non-ideal'' blockciphers such as AES. To alleviate this problem, we revisit the PGV constructions in light of the recently proposed idea of random-oracle reducibility (Baecher and Fischlin, Crypto 2011). We say that the blockcipher in one of the 12 secure PGV constructions reduces to the one in another construction, if \emph{any} secure instantiation of the cipher, ideal or not, for one construction also makes the other secure. This notion allows us to relate the underlying assumptions on blockciphers in different constructions, and show that the requirements on the blockcipher for one case are not more demanding than those for the other. It turns out that this approach divides the 12 secure constructions into two groups of equal size, where within each group a blockcipher making one construction secure also makes all others secure. Across the groups this is provably not the case, showing that the sets of ``good'' blockciphers for each group are qualitatively distinct. We also relate the ideal ciphers in the PGV constructions with those in double-block-length hash functions such as Tandem-DM, Abreast-DM, and Hirose-DM. Here, our results show that, besides achieving better bounds, the double-block-length hash functions rely on weaker assumptions on the blockciphers to achieve collision and everywhere preimage resistance.

We show that public-key bit encryption schemes which support weak (i.e., compact) homomorphic evaluation of any sufficiently "sensitive" collection of functions cannot be proved message indistinguishable beyond AM intersect coAM via general (adaptive) reductions, and beyond statistical zero-knowledge via reductions of constant query complexity. Examples of sensitive collections include parities, majorities, and the class consisting of all AND and OR functions. Our techniques also give a method for converting a strong (i.e., distribution-preserving) homomorphic evaluator for essentially any boolean function (except the trivial ones, the NOT function, and the AND and OR functions) into a rerandomization algorithm: This is a procedure that converts a ciphertext into another ciphertext which is statistically close to being independent and identically distributed with the original one. Our transformation preserves negligible statistical error.

The Advanced Encryption Standard (AES) is the most widely used block cipher. The high level structure of AES can be viewed as a (10-round) key-alternating cipher, where a t-round key-alternating cipher KA_t consists of a small number $t$ of fixed permutations P_i on n bits, separated by key addition: KA_t(K,m)= k_t + P_t(... k_2 + P_2(k_1 + P_1(k_0 + m))...), where (k_0,...,k_t) are obtained from the master key K using some key derivation function. For t=1, KA_1 collapses to the well-known Even-Mansour cipher, which is known to be indistinguishable from a (secret) random permutation, if P_1 is modeled as a (public) random permutation. In this work we seek for stronger security of key-alternating ciphers --- indifferentiability from an ideal cipher --- and ask the question under which conditions on the key derivation function and for how many rounds t is the key-alternating cipher KA_t indifferentiable from the ideal cipher, assuming P_1,...,P_t are (public) random permutations? As our main result, we give an affirmative answer for t=5, showing that the 5-round key-alternating cipher KA_5 is indifferentiable from an ideal cipher, assuming P_1,...,P_5 are five independent random permutations, and the key derivation function sets all rounds keys k_i=f(K), where 0<= i<= 5 and f is modeled as a random oracle. Moreover, when |K|=|m|, we show we can set f(K)=P_0(K)+K, giving an n-bit block cipher with an n-bit key, making only six calls to n-bit permutations P_0,P_1,P_2,P_3,P_4,P_5.

In this paper, we study succinct computationally sound proofs (arguments) for NP, whose communication complexity is polylogarithmic the instance and witness sizes. The seminal works of Kilian '92 and Micali '94 show that such arguments can be constructed under standard cryptographic hardness assumptions with four rounds of interaction, and that they be made non-interactive in the random-oracle model. The latter construction also gives us some evidence that succinct non interactive arguments (SNARGs) may exist in the standard model with a common reference string (CRS), by replacing the oracle with a sufficiently complicated hash function whose description goes in the CRS. However, we currently do not know of any construction of SNARGs with a formal proof of security under any simple cryptographic assumption. In this work, we give a broad black-box separation result, showing that black-box reductions cannot be used to prove the security of any SNARG construction based on any falsifiable cryptographic assumption. This includes essentially all common assumptions used in cryptography (one-way functions, trapdoor permutations, DDH, RSA, LWE etc.). More generally, we say that an assumption is falsifiable if it can be modeled as an interactive game between an adversary and an efficient challenger that can efficiently decide if the adversary won the game. This is similar, in spirit, to the notion of falsifiability of Naor '03, and captures the fact that we can efficiently check if an adversarial strategy breaks the assumption. Our separation result also extends to designated verifier SNARGs, where the verifier needs a trapdoor associated with the CRS to verify arguments, and slightly succinct SNARGs, whose size is only required to be sublinear in the statement and witness size.

Few days ago Grigoriev and Shpilrain have proposed to build a system for transmission of information without a shared secret, or essentially a sort of public key cryptosystem, based on properties of physical systems. In this paper we show that their second scheme based on capacitors is insecure and extremely easy to break in practice.

We consider a class of two-party function evaluation protocols in which the parties are allowed to use ideal functionalities as well as a set of powerful primitives, namely commitments, homomorphic encryption, and certain zero-knowledge proofs. We illustrate that with these it is possible to capture protocols for oblivious transfer, coin-flipping, and generation of multiplication-triple. We show how any protocol in our class can be compiled to a symbolic representation expressed as a process in an abstract process calculus, and prove a general computational soundness theorem implying that if the protocol realises a given ideal functionality in the symbolic setting, then the original version also realises the ideal functionality in the standard computational UC setting. In other words, the theorem allows us to transfer a proof in the abstract symbolic setting to a proof in the standard UC model. Finally, we show that the symbolic interpretation is simple enough in a number of cases for the symbolic proof to be partly automated using the ProVerif tool.

Recent advances in lattice cryptography, mainly stemming from the development of ring-based primitives such as ring-$\lwe$, have made it possible to design cryptographic schemes whose efficiency is competitive with that of more traditional number-theoretic ones, along with entirely new applications like fully homomorphic encryption. Unfortunately, realizing the full potential of ring-based cryptography has so far been hindered by a lack of practical algorithms and analytical tools for working in this context. As a result, most previous works have focused on very special classes of rings such as power-of-two cyclotomics, which significantly restricts the possible applications. We bridge this gap by introducing a toolkit of fast, modular algorithms and analytical techniques that can be used in a wide variety of ring-based cryptographic applications, particularly those built around ring-\lwe. Our techniques yield applications that work in \emph{arbitrary} cyclotomic rings, with \emph{no loss} in their underlying worst-case hardness guarantees, and very little loss in computational efficiency, relative to power-of-two cyclotomics. To demonstrate the toolkit's applicability, we develop two illustrative applications: a public-key cryptosystem and a ``somewhat homomorphic'' symmetric encryption scheme. Both apply to arbitrary cyclotomics, have tight parameters, and very efficient implementations.

Consider two parties Alice and Bob, who hold private inputs x and y, and wish to compute a function f(x,y) privately in the information theoretic sense; that is, each party should learn nothing beyond f(x,y). However, the communication channel available to them is noisy. This means that the channel can introduce errors in the transmission between the two parties. Moreover, the channel is adversarial in the sense that it knows the protocol that Alice and Bob are running, and maliciously introduces errors to disrupt the communication, subject to some bound on the total number of errors. A fundamental question in this setting is to design a protocol that remains private in the presence of large number of errors. If Alice and Bob are only interested in computing f(x,y) correctly, and not privately, then quite robust protocols are known that can tolerate a constant fraction of errors. However, none of these solutions is applicable in the setting of privacy, as they inherently leak information about the parties' inputs. This leads to the question whether we can simultaneously achieve privacy and error-resilience against a constant fraction of errors. We show that privacy and error-resilience are contradictory goals. In particular, we show that for every constant c > 0, there exists a function f which is privately computable in the error-less setting, but for which no private and correct protocol is resilient against a c-fraction of errors.

In this paper we propose a novel method for performing secure two-party computation. By merging together in a suitable way two beautiful ideas of the 80's and the 90's, Yao's garbled circuit construction and Naor and Shamir's visual cryptography, respectively, we enable Alice and Bob to securely evaluate a function $f(\cdot,\cdot)$ of their inputs, $x$ and $y$, through a {\em pure physical} process. Indeed, once Alice has prepared a set of properly constructed transparencies, Bob computes the function value $f(x,y)$ by applying a sequence of simple steps which require the use of a pair of scissors, superposing transparencies, and the human visual system. A crypto-device for the function evaluation process is not needed any more.

We show how to construct an ideal cipher with $n$-bit blocks and $n$-bit keys (\emph{i.e.} a set of $2^n$ public $n$-bit permutations) from a small constant number of $n$-bit random public permutations. The construction that we consider is the \emph{single-key iterated Even-Mansour cipher}, which encrypts a plaintext $x\in\{0,1\}^n$ under a key $k\in\{0,1\}^n$ by alternatively xoring the key $k$ and applying independent random public $n$-bit permutations $P_1,\ldots, P_r$ (this construction is also named a \emph{key-alternating cipher}). We analyze this construction in the plain indifferentiability framework of Maurer, Renner, and Holenstein (TCC 2004), and show that twelve rounds are sufficient to achieve indifferentiability from an ideal cipher. We also show that four rounds are necessary by exhibiting attacks for three rounds or less.

This paper mainly focuses on permutation polynomials over the residue class ring $\mathbb{Z}_{N}$, where $N>3$ is composite. We have proved that for the polynomial $f(x)=a_{1}x^{1}+\cdots +a_{k}x^{k}$ with integral coefficients, $f(x)\bmod N$ permutes $\mathbb{Z}_{N}$ if and only if $f(x)\bmod N$ permutes $S_{\mu}$ for all $\mu \mid N$, where $S_{\mu}=\{0< t <N: \gcd(N,t)=\mu\}$ and $S_{N}=S_{0}=\{0\}$. Based on it, we give a lower bound of the differential uniformities for such permutation polynomials, that is, $\delta (f)\geq \frac{N}{\#S_{a}}$, where $a$ is the biggest nontrivial divisor of $N$. Especially, $f(x)$ can not be APN permutations over the residue class ring \mathbb{Z}_{N}$. It is also proved that $f(x)\bmod N$ and $(f(x)+x)\bmod N$ can not permute $\mathbb{Z}_{N}$ at the same time when $N$ is even.

In this short note, we demonstrate a simple and practical ORAM that enjoys an extremely simple proof of security. Our construction is based on a recent ORAM due to Shi, Chan, Stefanov and Li (Asiacrypt'11), but with some crucial modifications, which significantly simply the analysis.

We argue that it is unnatural and undesirable to use the non-uniform model of complexity for practice-oriented security reductions in cryptography.

In the past few years, cryptographic key management APIs have been shown to be subject to tricky attacks based on the improper use of cryptographic keys. In fact, real APIs provide mechanisms to declare the intended use of keys but they are not strong enough to provide key security. In this paper, we propose a simple imperative programming language for specifying strongly-typed APIs for the management of symmetric, asymmetric and signing keys. The language requires that type information is stored together with the key but it is independent of the actual low-level implementation. We develop a type-based analysis to prove the preservation of integrity and confidentiality of sensitive keys and we show that our abstraction is expressive enough to code realistic key management APIs.

In this paper, we apply results on number systems based on continued fraction expansions to modular arithmetic. We provide two new algorithms in order to compute modular multiplication and modular division. The presented algorithms are based on the Euclidean algorithm and are of quadratic complexity.

We consider the problem of evaluating circuits whose inputs are encrypted with possibly different encryption schemes. Let $\mathcal{C}$ be any circuit with input $x_1, \dots, x_t \in \{0,1\}$, and let $\mathcal{E}_i$, $1 \le i \le t$, be (possibly) different fully homomorphic encryption schemes, whose encryption algorithms are $\Enc_i$. Suppose $x_i$ is encrypted with $\mathcal{E}_i$ under a public key $pk_i$, say $c_i \leftarrow \Enc_i({pk_i}, x_i)$. Is there any algorithm $\Evaluate$ such that $\Evaluate(\mathcal{C}, \langle \mathcal{E}_1, pk_1, c_1\rangle, \dots, \langle \mathcal{E}_t, pk_t, c_t\rangle)$ returns a ciphertext $c$ that, once decrypted, equals $\mathcal{C}(x_1, \dots, x_t)$? We propose a solution to this seemingly impossible problem with the number of different schemes and/or keys limited to a small value. Our result also provides a partial solution to the open problem of converting any FHE scheme to a multikey FHE scheme.

In this paper, we use the theory of theta functions to generalize to all abelian varieties the usual Miller's algorithm to compute a function associated to a principal divisor. We also explain how to use the Frobenius morphism on abelian varieties defined over a finite field in order to shorten the loop of the Weil and Tate pairings algorithms. This extend preceding results about ate and twisted ate pairings to all abelian varieties. Then building upon the two preceding ingredients, we obtain a variant of optimal pairings on abelian varieties. Finally, by introducing new addition formulas, we explain how to compute optimal pairings on Kummer varieties. We compare in term of performance the resulting algorithms to the algorithms already known in the genus one and two case.

How can we encode a communication protocol between two parties to become resilient to adversarial errors on the communication channel? This question dates back to the seminal works of Shannon and Hamming from the 1940's, initiating the study of error-correcting codes (ECC). But, even if we encode each message in the communication protocol with a ``good'' ECC, the error rate of the encoded protocol becomes poor (namely $O(1/m)$ where $m$ is the number of communication rounds). Towards addressing this issue, Schulman (FOCS'92, STOC'93) introduced the notion of \emph{interactive coding}. We argue that whereas the method of separately encoding each message with an ECC ensures that the encoded protocol carries the same amount of information as the original protocol, this may no longer be the case if using interactive coding. In particular, the encoded protocol may completely leak a player's private input, even if it would remain secret in the original protocol. Towards addressing this problem, we introduce the notion of \emph{knowledge-preserving interactive coding}, where the interactive coding protocol is required to preserve the ``knowledge'' transmitted in the original protocol. Our main results are as follows. \begin{itemize} \item The method of separately applying ECCs to each message is essentially optimal: No knowledge-preserving interactive coding scheme can have an error rate of $1/m$, where $m$ is the number of rounds in the original protocol. \item If restricting to computationally-bounded (polynomial-time) adversaries, then assuming the existence of one-way functions (resp. subexponentially-hard one-way functions), for every $\epsilon>0$, there exists a knowledge-preserving interactive coding schemes with constant error rate and information rate $n^{-\epsilon}$ (resp. $1/\polylog(n)$) where $n$ is the security parameter; additionally to achieve an error of even $1/m$ requires the existence of one-way functions. \item Finally, even if we restrict to computationally-bounded adversaries, knowledge-preserving interactive coding schemes with constant error rate can have an information rate of at most $o(1/\log n)$. This results applies even to \emph{non-constructive} interactive coding schemes. \end{itemize}

A major general paradigm in cryptography is the following argument: Whatever an adversary could do in the real world, it could just as well do in the ideal world. The standard interpretation of ``just as well'' is that the translation from the real to the ideal world, usually called a simulator, is achieved by a probabilistic polynomial-time algorithm. This means that a polynomial blow-up of the adversary's time and memory requirements is considered acceptable. In certain contexts this interpretation of ``just as well'' is inadequate, for example if the concrete amount of memory used by the adversary is relevant. The example of Ristenpart et al. (Eurocrypt 2011), for which the original indifferentiability notion introduced by Maurer et al. (Eurocrypt 2004) is shown to be insufficient, turns out to be exactly of this type. It requires a fine-grained statement about the adversary's memory capacity, calling for a generalized treatment of indifferentiability where specific resource requirements can be taken into account by modeling them explicitly. We provide such treatment and employ the new indifferentiability notion to prove lower bounds on the memory required by any simulator in a domain extension construction of a public random function. In particular, for simulators without memory, even domain extension by a single bit turns out to be impossible. Moreover, for the construction of a random oracle from an ideal compression function, memory roughly linear in the length of the longest query is required. This also implies the impossibility of such domain extension in any multi-party setting with potential individual misbehavior by parties (i.e., no central adversary).

We consider session key agreement (SKA) protocols operating in a public key infrastructure, with pre-specified peers, that take no session ID as input, and output only a session key. Despite much work on SKA, we argue that there is no good definition of security for this (very natural) protocol syntax. The difficulty is that in this setting the adversary may not be able to tell which processes share a key, and thus which session keys may be revealed without trivializing the security condition. We consider security against adversaries that control all network traffic, can register arbitrary public keys, and can retrieve session keys. We do not attempt to mitigate damage from hardware failures, such as session-state compromise, as we aim to improve our understanding of this simpler setting. We give two natural but substantially different game based definitions of security and prove that they are equivalent. Such proofs are rare for SKA. The bulk of this proof consists of showing that, for secure protocols, only compatible processes can be made to share a key. This property is very natural but surprisingly subtle. For comparison, we give a version of our definition in which processes output session IDs and we give strong theorems relating these two types of definitions.

In this paper, we prove that finding the approximate shortest vector with length in $[\lambda_{1},\gamma \lambda_{1} ]$ could be reduced to GapSVP. We also prove that shortest vector problem could also be reduced to GapSVP with a small gap. As the complexity of uSVP is not very clear, we improve crurrent complexity results\cite{AD2011} of uSVP, proving uSVP could be reduced from SVP deterministically. What's more, we prove that the search version of uSVP could be reduced to decisional version of uSVP with almost the same gap. At last, based on the results above, we prove a bit-unpredictable property of SVP.

Depending on the application, malleability in cryptography can be viewed as either a flaw or — especially if sufficiently understood and restricted — a feature. In this vein, Chase, Kohlweiss, Lysyanskaya, and Meiklejohn recently defined malleable zero-knowledge proofs, and showed how to control the set of allowable transformations on proofs. As an application, they construct the first compact verifiable shuffle, in which one such controlled-malleable proof suffices to prove the correctness of an entire multi-step shuffle. Despite these initial steps, a number of natural problems remained: (1) their construction of controlled-malleable proofs relies on the inherent malleability of Groth-Sahai proofs and is thus not based on generic primitives; (2) the classes of allowable transformations they can support are somewhat restrictive. In this paper, we address these issues by providing a generic construction of controlled-malleable proofs using succinct non-interactive arguments of knowledge, or SNARGs for short. Our construction can support very general classes of transformations, as we no longer rely on the transformations that Groth-Sahai proofs can support.

Motivated by the goal of controlling the amount of work required to access a shared resource or to solve a cryptographic puzzle, we introduce and study the related notions of {\em lossy chains} and {\em fractional secret sharing}. Fractional secret sharing generalizes traditional secret sharing by allowing a fine-grained control over the amount of uncertainty about the secret. More concretely, a fractional secret sharing scheme realizes a fractional access structure $f:2^{[n]}\to [m]$ by guaranteeing that from the point of view of each set $T\subseteq [n]$ of parties, the secret is {\em uniformly} distributed over a set of $f(T)$ potential secrets. We show that every (monotone) fractional access structure can be realized. For {\em symmetric} structures, in which $f(T)$ depends only on the size of $T$, we give an efficient construction with share size $poly(n,\log m)$. Our construction of fractional secret sharing schemes is based on the new notion of {\em lossy chains} which may be of independent interest. A lossy chain is a Markov chain $(X_0,\ldots,X_n)$ which starts with a random secret $X_0$ and gradually loses information about it at a rate which is specified by a {\em loss function} $g$. Concretely, in every step $t$, the distribution of $X_0$ conditioned on the value of $X_t$ should always be uniformly distributed over a set of size $g(t)$. We show how to construct such lossy chains efficiently for any possible loss function $g$, and prove that our construction achieves an optimal asymptotic information rate.

The learning with rounding (LWR) problem, introduced by Banerjee, Peikert and Rosen [BPR12] at EUROCRYPT '12, is a variant of learning with errors (LWE), where one replaces random errors with deterministic rounding. The LWR problem was shown to be as hard as LWE for a setting of parameters where the modulus and modulus-to-error ratio are super-polynomial. In this work we resolve the main open problem of [BPR12] and give a new reduction that works for a larger range of parameters, allowing for a polynomial modulus and modulus-to-error ratio. In particular, a smaller modulus gives us greater efficiency, and a smaller modulus-to-error ratio gives us greater security, which now follows from the worst-case hardness of GapSVP with polynomial (rather than super-polynomial) approximation factors. As a tool in the reduction, we show that there is a ``lossy mode'' for the LWR problem, in which LWR samples only reveal partial information about the secret. This property gives us several interesting new applications, including a proof that LWR remains secure with weakly random secrets of sufficient min-entropy, and very simple new constructions of deterministic encryption, lossy trapdoor functions and reusable extractors. Our approach is inspired by a technique of Goldwasser et al. [GKPV10] from ICS '10, which implicitly showed the existence of a ``lossy mode'' for LWE. By refining this technique, we also improve on the parameters of that work to only requiring a polynomial (instead of super-polynomial) modulus and modulus-to-error ratio.

Recently there has been a huge emphasis on constructing cryptographic protocols that maintain their security guarantees even in the presence of side channel attacks. Such attacks exploit the physical characteristics of a cryptographic device to learn useful information about the internal state of the device. Designing protocols that deliver meaningful security even in the presence of such leakage attacks is a challenging task. The recent work of Garg, Jain, and Sahai formulates a meaningful notion of zero-knowledge in presence of leakage; and provides a construction which satisfies a weaker variant of this notion called (1+e)-leakage-resilient-zero-knowledge, for every constant e>0. In this weaker variant, roughly speaking, if the verifier learns L bits of leakage during the interaction, then the simulator is allowed to access (1+e).L bits of leakage. The round complexity of their protocol is n/e. In this work, we present the first construction of leakage-resilient zero-knowledge satisfying the ideal requirement of e=0. While our focus is on a feasibility result for e=0, our construction also enjoys a constant number of rounds. At the heart of our construction is a new ``public-coin preamble'' which allows the simulator to recover arbitrary information from a (cheating) verifier in a ``straight line.'' We use non-black-box simulation techniques to accomplish this goal.

We consider the problem of constructing protocols for secure computation that achieve strong concurrent and composable notions of security in the plain model. Unfortunately UC-secure secure computation protocols are impossible in this setting, but the Angel-Based Composable Security notion offers a promising alternative. Until now, however, under standard (polynomial-time) assumptions, only protocols with polynomially many rounds were known to exist. In this work, we give the first $\tilde{O}(\log n)$-round secure computation protocol in the plain model that achieves angel-based composable security in the concurrent setting, under standard assumptions. We do so by constructing the first $\tilde{O}(\log n)$-round CCA-secure commitment protocol. Our CCA-secure commitment protocol is secure based on the minimal assumption that one-way functions exist. A central tool in obtaining our result is a new \emph{robust concurrent extraction lemma} that we introduce and prove, based on the minimal assumptions that one-way functions exist. This robust concurrent extraction lemma shows how to build concurrent extraction procedures that work even in the context of an ``external'' protocol that cannot be rewound by the extractor. We believe this lemma can be used to simplify many existing works on concurrent security, and is of independent interest. In fact, our lemma when used in conjunction with the concurrent-simulation schedule of Pass and Venkitasubramaniam (TCC'08), also yields a constant round construction based additionally on the existence of quasi-polynomial time (\pqt) secure one-way functions.

The simulation paradigm, introduced by Goldwasser, Micali and Rackoff, is of fundamental importance to modern cryptography. In a breakthrough work from 2001, Barak (FOCS'01) introduced a novel non-black-box simulation technique. This technique enabled the construction of new cryptographic primitives, such as resettably-sound zero-knowledge arguments, that cannot be proven secure using just black-box simulation techniques. The work of Barak and its follow-ups, however, all require stronger cryptographic hardness assumptions than the minimal assumption of one-way functions: the work of Barak requires the existence of collision-resistant hash functions, and a very recent result by Bitansky and Paneth (FOCS'12) instead requires the existence of an Oblivious Transfer protocol. In this work, we show how to perform non-black-box simulation assuming just the existence of one-way functions. In particular, we demonstrate the existence of a constant-round resettably-sound zero-knowledge argument based only on the existence of one-way functions. Using this technique, we determine necessary and sufficient assumptions for several other notions of resettable security of zero-knowledge proofs. An additional benefit of our approach is that it seemingly makes practical implementations of non-black-box zero-knowledge viable.

In this short note, we demonstrate that the existence of one-way functions implies the existence of an $\omega(1)$-round simultaneously resettable witness indistinguishable argument.

The central objects of secure multiparty computation are the “multiparty functions” (or functionalities) that it seeks to securely realize. In this article we survey a set of results that constitute a Cryptographic Complexity Theory. This theory classifies and compares multiparty functions according to their secure computability and reducibility to each other. The basic questions studied, under various notions of security and reducibility, include: • Which functionalities are securely realizable (or are “trivial” – i.e., can be reduced to any functionality)? • Which functionalities are “complete” – i.e., those to which any functionality can be reduced? • More generally, which functionalities are reducible to which? Outside of triviality and completeness, this question is relatively less explored. Reductions yield relative measures of complexity among various functionalities. In the information- theoretic setting, absolute complexity measures have also been considered. In particular, we discuss results regarding which functions have t-private protocols (in which security is required against a passive adversary corrupting t out of n players) and how this set changes as t increases from 1 to n. We treat separately the results on two-party functionalities, for which the cryptographic complexity is much better understood. In particular, we present unified combinatorial characterizations of completeness and triviality for secure function evaluation using notions of isomorphism and the common information functionality (called the kernel) of a given functionality. Beyond completeness and triviality, we also discuss results on general reducibility, and, in the computationally bounded setting, the connection between these reductions and computational hardness assumptions. We briefly discuss results on reactive functionalities, which are much less studied than non-reactive (secure function evaluation) functionalities. Finally, we conclude with a selection of open problems.

In this paper, we consider both theoretical and practical aspects of robust NI-PE (non-interactive polynomial evaluation with detection of cheaters). First, we give a necessary condition of adversary structures for which perfectly robust NI-PE with small communication complexity exists. More precisely, we show that for any positive integers $n$, $m$ and $d>1$, an $n$-player access structure $U$, and an $n$-player adversary structure $T$, there exists a $U$-participating NI-PE scheme for $m$-variate polynomials over a finite field $F$ with $T$-private inputs such that (1) perfectly robust (i.e., successful cheating probability $\epsilon=0$), (2) any polynomial of degree $d$ can be evaluated, and (3) the total size of shares of the output for some participating set is $o(m)\times \log |F|$, {\em only if} $T$ is of type $Q_{d+1}$ for $U$, meaning that no $d+1$ sets in $T$ cover any set in $U$. Second, we give constructions of perfectly robust NI-PE schemes against threshold adversary and general adversary, respectively. All the proposed schemes ensure perfect robustness against $Q_{d+1}$ adversary, and computability of arbitrary polynomial of degree $d$. Third, we show that efficient robust NI-PE schemes against general adversary can be constructed by allowing cheaters very small chance of successful cheating. Namely, we construct two robust NI-PE schemes with $\epsilon=1/|F|$ and the total size for shares of the output is only three times larger compared to the perfectly robust NI-PE scheme against threshold adversary.

In this article, we discuss a naive method of randomness reduction for cryptographic schemes, which replaces the required perfect randomness with output distribution of a computationally secure pseudorandom generator (PRG). We propose novel ideas and techniques for evaluating the indistinguishability between the random and pseudorandom cases, even against an adversary with computationally unbounded attack algorithm. Hence the PRG-based randomness reduction can be effective even for information-theoretically secure cryptographic schemes, especially when the amount of information received by the adversary is small. In comparison to a preceding result of Dubrov and Ishai (STOC 2006), our result removes the requirement of generalized notion of ``nb-PRGs'' and is effective for more general kinds of protocols. We give some numerical examples to show the effectiveness of our result in practical situations, and we also propose a further idea for improving the effect of the PRG-based randomness reduction.

In the random oracle model, parties are given oracle access to a random function (i.e., a uniformly chosen function from the set of all functions), and are assumed to have unbounded computational power (though they can only make a bounded number of oracle queries). This model provides powerful properties that allow proving the security of many protocols, even such that cannot be proved secure in the standard model (under any hardness assumption). The random oracle model is also used for showing that a given cryptographic primitive cannot be used in a black-box way to construct another primitive; in their seminal work, Impagliazzo and Rudich [STOC ’89] showed that no key-agreement protocol exists in the random oracle model, yielding that key-agreement cannot be black-box reduced to one-way functions. Their work has a long line of followup works (Simon [EC ’98], Gertner et al. [STOC ’00] and Gennaro et al. [SICOMP ’05], to name a few), showing that given oracle access to a certain type of function family (e.g., the family that “implements” public-key encryption) is not sufficient for building a given cryptographic primitive (e.g., oblivious transfer). Yet, the following question remained open: What is the exact power of the random oracle model? We make progress towards answering the above question, showing that, essentially, any no private input, semi-honest two-party functionality that can be securely implemented in the random oracle model, can be securely implemented information theoretically (where parties are assumed to be all powerful, and no oracle is given). We further generalize the above result to function families that provide some natural combinatorial property. Our result immediately yields essentially that the only no-input functionalities that can be securely realized in the random oracle model (in the sense of secure function evaluation), are the trivial ones (ones that can be securely realized information theoretically). In addition, we use the recent information theoretic impossibility result of McGregor et al. [FOCS ’10], to show the existence of functionalities (e.g., inner product) that cannot be computed both accurately and in a differentially private manner in the random oracle model; yielding that protocols for computing these functionalities cannot be black-box reduced to the existence of one-way functions.

Many index calculus algorithms generate multiplicative relations between smoothness basis elements by using a process called {\it Sieving}. This process allows to filter potential candidate relations very quickly, without spending too much time to consider bad candidates. However, from an asymptotic point of view, there is not much difference between sieving and straightforward testing of candidates. The reason is that even when sieving, some small amount time is spend for each bad candidates. Thus, asymptotically, the total number of candidates contributes to the complexity. In this paper, we introduce a new technique: {\it Pinpointing}, which allows us to construct multiplicate relations much faster, thus reducing the asymptotic complexity of relations' construction. Unfortunately, we only know how to implement this technique for finite fields which contain a medium-sized subfield. When applicable, this method improves the asymptotic complexity of the index calculus algorithm in the cases where the sieving phase dominates. In practice, it gives a very interesting boost to the performance of state-of-the-art algorithms. We illustrate the feasability of the method with a discrete logarithm record in medium prime finite fields of sizes 1175~bits and 1425~bits.

Cryptography relies on the secrecy of keys. Measures of information, and thus secrecy, are called entropy. Previous work does not formally assess the cryptographically appropriate entropy of secret keys. This report defines several new forms of entropy appropriate for cryptographic situations. This report defines statistical inference methods appropriate for assessing cryptographic entropy.

We strengthen the foundations of deterministic public-key encryption via definitional equivalences and standard-model constructs based on general assumptions. Specifically we consider seven notions of privacy for deterministic encryption, including six forms of semantic security and an indistinguishability notion, and show them all equivalent. We then present a deterministic scheme for the secure encryption of uniformly and independently distributed messages based solely on the existence of trapdoor one-way permutations. We show a generalization of the construction that allows secure deterministic encryption of independent high-entropy messages. Finally we show relations between deterministic and standard (randomized) encryption.

The primitive of deniable encryption was first introduced by Canetti et al. (CRYPTO, 1997). Deniable encryption is a regular public key encryption scheme with the added feature that after running the protocol honestly and transmitting a message $m$, both Sender and Receiver may produce random coins showing that the transmitted ciphertext was an encryption of any message $m'$ in the message space. Deniable encryption is a key tool for constructing incoercible protocols, since it allows a party to send one message and later provide apparent evidence to a coercer that a different message was sent. In addition, deniable encryption may be used to obtain \emph{adaptively}-secure multiparty computation (MPC) protocols and is secure under \emph{selective-opening} attacks. Different flavors such as sender-deniable and receiver-deniable encryption, where only the Sender or Receiver can produce fake random coins, have been considered. Recently, several open questions regarding the feasibility of deniable encryption have been resolved (c.f. (O'Neill et al., CRYPTO, 2011), (Bendlin et al., ASIACRYPT, 2011)). A fundamental remaining open question is whether it is possible to construct sender-deniable Encryption Schemes with super-polynomial security, where an adversary has negligible advantage in distinguishing real and fake openings. The primitive of simulatable public key encryption (PKE), introduced by Damgård and Nielsen (CRYPTO, 2000), is a public key encryption scheme with additional properties that allow oblivious sampling of public keys and ciphertexts. It is one of the low-level primitives used to construct adaptively-secure MPC protocols and was used by O'Neill et al. in their construction of bi-deniable encryption in the multi-distributional model (CRYPTO, 2011). Moreover, the original construction of sender-deniable encryption with polynomial security given by Canetti et al. can be instantiated with simulatable PKE. Thus, a natural question to ask is whether it is possible to construct sender-deniable encryption with \emph{super-polynomial security} from simulatable PKE. In this work, we investigate the possibility of constructing sender-deniable public key encryption from the primitive of simulatable PKE in a black-box manner. We show that, in fact, there is no black-box construction of sender-deniable encryption with super-polynomial security from simulatable PKE. This indicates that the original construction of sender-deniable public key encryption given by Canetti et al. is in some sense optimal, since improving on it will require the use of non-black-box techniques, stronger underlying assumptions or interaction.

\emph{Succinct arguments of knowledge} are computationally-sound proofs of knowledge for NP where the verifier's running time is independent of the time complexity $t$ of the nondeterministic NP machine $M$ that decides the given language. Existing succinct argument constructions are, typically, based on techniques that combine cryptographic hashing and probabilistically-checkable proofs (PCPs). Yet, even when instantiating these constructions with state-of-the-art PCPs, the prover needs $\Omega(t)$ space in order to run in quasilinear time (i.e., time $t \poly(k)$), regardless of the space complexity $s$ of the machine $M$. We say that a succinct argument is \emph{complexity preserving} if the prover runs in time $t \poly(k)$ and space $s \poly(k)$ and the verifier runs in time $|x| \poly(k)$ when proving and verifying that a $t$-time $s$-space random-access machine nondeterministically accepts an input $x$. Do complexity-preserving succinct arguments exist? To study this question, we investigate the alternative approach of constructing succinct arguments based on multi-prover interactive proofs (MIPs) and stronger cryptographic techniques: (1) We construct a one-round succinct MIP of knowledge, where each prover runs in time $t \polylog(t)$ and space $s \polylog(t)$ and the verifier runs in time $|x| \polylog(t)$. (2) We show how to transform any one-round MIP protocol to a succinct four-message argument (with a single prover), while preserving the time and space efficiency of the original MIP protocol; using our MIP protocol, this transformation yields a complexity-preserving four-message succinct argument. As a main tool for our transformation, we define and construct a \emph{succinct multi-function commitment} that (a) allows the sender to commit to a vector of functions in time and space complexity that are essentially the same as those needed for a single evaluation of the functions, and (b) ensures that the receiver's running time is essentially independent of the function. The scheme is based on fully-homomorphic encryption (and no additional assumptions are needed for our succinct argument). (3) In addition, we revisit the problem of \emph{non-interactive} succinct arguments of knowledge (SNARKs), where known impossibilities prevent solutions based on black-box reductions to standard assumptions. We formulate a natural (but non-standard) variant of homomorphic encryption having a \emph{homomorphism-extraction property}. We show that this primitive essentially allows to squash our interactive protocol, while again preserving time and space efficiency, thereby obtaining a complexity-preserving SNARK. We further show that this variant is, in fact, implied by the existence of (complexity-preserving) SNARKs.

The Fiat-Shamir heuristic (CRYPTO '86) is used to convert any 3-message public-coin proof or argument system into a non-interactive argument, by hashing the prover's first message to select the verifier's challenge. It is known that this heuristic is sound when the hash function is modeled as a random oracle. On the other hand, the surprising result of Goldwasser and Kalai (FOCS '03) shows that there exists a computationally sound argument on which the Fiat-Shamir heuristic is never sound, when instantiated with any actual efficient hash function. This leaves us with the following interesting possibility: perhaps there exists a hash function that securely instantiates the Fiat-Shamir heuristic for all 3-message public-coin statistically sound proofs, even if it can fail for some computationally sound arguments. Indeed, the existence of such hash functions has been conjectured by Barak, Lindell and Vadhan (FOCS '03), who also gave a seemingly reasonable and sufficient condition under which such hash functions exist. However, we do not have any provably secure construction of such hash functions, under any standard assumption such as the hardness of DDH, RSA, QR, LWE, etc. In this work we give a broad black-box separation result, showing that the security of such hash functions cannot be proved under virtually any standard cryptographic assumption via a black-box reduction.

The Random Oracle Model, introduced by Bellare and Rogaway, provides a method to heuristically argue about the security of cryptographic primitives and protocols. The basis of this heuristic is that secure hash functions are close enough to random functions in their behavior, and so, a primitive that is secure using a random function should continue to remain secure even when the random function is replaced by a real hash function. In the security proof, this setting is realized by modeling the hash function as a random oracle. However, this approach in particular also enables any reduction, reducing a hard problem to the existence of an adversary, to \emph{observe} the queries the adversary makes to its random oracle and to \emph{program} the responses that the oracle provides to these queries. While, the issue of programmability of query responses has received a lot of attention in the literature, to the best of our knowledge, observability of the adversary's queries has not been identified as an artificial artefact of the Random Oracle Model. In this work, we study the security of several popular schemes when the security reduction cannot ``observe'' the adversary's queries to the random oracle, but can (possibly) continue to ``program'' the query responses. We first show that RSA-PFDH and Schnorr's signatures continue to remain secure when the security reduction is non observing (NO reductions), which is not surprising as their proofs in the random oracle model rely on programmability. We also provide two example schemes, namely, Fischlin's NIZK-PoK \cite{Fischlin05} and non interactive extractable commitment scheme, extractor algorithms of which seem to rely on observability in the random oracle model. While we prove that Fischlin's online extractors cannot exist when they are non observing, our extractable commitment scheme continues to be secure even when the extractors are non observing. We also introduce Non Observing Non Programming reductions which we believe are closest to standard model reductions.

This paper studies the distinctness of primitive sequences over Z/(M) modulo 2, where M is an odd integer that is composite and square-free, and Z/(M) is the integer residue ring modulo M. A new sufficient condition is given for ensuring that primitive sequences generated by a primitive polynomial f(x) over Z/(M) are pairwise distinct modulo 2. Such result improves a recent result obtained in our previous paper [27] and consequently the set of primitive sequences over Z/(M) that can be proven to be distinct modulo 2 is greatly enlarged.

We introduce the notion of covert security with public verifiability, building on the covert security model introduced by Aumann and Lindell (TCC 2007). Protocols that satisfy covert security guarantee that the honest parties involved in the protocol will notice any cheating attempt with some constant probability $\epsilon$. The idea behind the model is that the fear of being caught cheating will be enough of a deterrent to prevent any cheating attempt. However, in the basic covert security model, the honest parties are not able to persuade any third party (say, a judge) that a cheating occurred. We propose (and formally define) an extension of the model where, when an honest party detects cheating, it also receives a certificate that can be published and used to persuade other parties, without revealing any information about the honest party's input. In addition, malicious parties cannot create fake certificates in the attempt of framing innocents. Finally, we construct a secure two-party computation protocol for any functionality $f$ that satisfies our definition, and our protocol is almost as efficient as the one of Aumann and Lindell. We believe that the fear of a public humiliation or even legal consequences vastly exceeds the deterrent given by standard covert security. Therefore, even a small value of the deterrent factor $\epsilon$ will suffice in discouraging any cheating attempt. As the overall complexity of covert security and the parameter $\epsilon$ are inversely proportional to each other, we believe that the small price to pay to get the public verifiability property on top of covert security will be dominated by the efficiency gain obtained by using a smaller value $\epsilon$.

There has been much recent progress in constructing cryptosystems that maintain their security without requiring uniform randomness and perfect secrecy. These schemes are motivated by a diverse set of problems such as providing resilience to side-channel leakage, using weak physical sources of randomness as secret keys, and allowing deterministic encryption for high-entropy messages. The study of these problems has significantly deepened our understanding of how randomness is used in cryptographic constructions and proofs. Nevertheless, despite this progress, some basic and seemingly achievable security properties have eluded our reach. For example, we are unable to prove the security of basic tools for manipulating weak/leaky random sources, such as as pseudo-entropy generators and seed-dependent computational condensers. We also do not know how to prove leakage-resilient security of any cryptosystem whose secret key is uniquely determined by its public key. In the context of deterministic encryption we do not have a standard-model constructions achieving the strongest notion of security proposed by Bellare, Boldyreva and O'Neill (CRYPTO '07), that would allow us to encrypt arbitrarily correlated messages of sufficiently large individual entropy. In this work, we provide broad black-box separation results, showing that the security of such primitives cannot be proven under virtually any standard cryptographic hardness assumption via a reduction that treats the adversary as a black box. We do so by formalizing the intuition that ``the only way that a reduction can simulate the correctly distributed view for an attacker is to know all the secrets, in which case it does not learn anything useful from the attack''. Such claims are often misleading and clever way of getting around them allow us to achieve a wealth of positive results with imperfect/leaky randomness. However, in this work we show that this intuition can be formalized and that it indeed presents a real barrier for the examples given above.

We put forward a framework for the modular design and analysis of multi-party protocols. Our framework is called ``GNUC'' (with the recursive meaning ``GNUC's Not UC''), already alluding to the similarity to Canetti's Universal Composability (UC) framework. In particular, like UC, we offer a universal composition theorem, as well as a theorem for composing protocols with joint state. We deviate from UC in several important aspects. Specifically, we have a rather different view than UC on the structuring of protocols, on the notion of polynomial-time protocols and attacks, and on corruptions. We will motivate our definitional choices by explaining why the definitions in the UC framework are problematic, and how we overcome these problems. Our goal is to make offer a framework that is largely compatible with UC, such that previous results formulated in UC carry over to GNUC with minimal changes. We exemplify this by giving explicit formulations for several important protocol tasks, including authenticated and secure communication, as well as commitment and secure function evaluation.

The general number field sieve (GNFS) is the most efficient algorithm known for factoring large integers. It consists of several stages, the first one being polynomial selection. The quality of the chosen polynomials in polynomial selection can be modelled in terms of size and root properties. In this paper, we describe some algorithms for selecting polynomials with very good root properties.

To have “full” entropy has been defined in a draft NIST standard to be to have min-entropy very close, proportionally, to the min-entropy of a uniform distribution. A function is uniform if all its preimages have the same size. This report proves that the output of any uniform compression function can fail to have full entropy, even when the input has full entropy.

The question whether Identity-Based Encryption (IBE) can be based on the Decisional Diffie-Hellman (DDH) assumption is one of the most prominent questions in Cryptography related to DDH. We study limitations on the use of the DDH assumption in cryptographic constructions, and show that it is impossible to construct a secure Identity-Based Encryption system using, in a black box way, only the DDH (or similar) assumption about a group. Our impossibility result is set in the generic groups model, where we describe an attack on any IBE construction that relies on oracle access to the group operation of randomly labelled group elements -- a model that formalizes naturally DDH hardness. The vast majority of existing separation results typically give separation from general primitives, whereas we separate a primitive from a class of number theoretic hardness assumptions. Accordingly, we face challenges in creating an attack algorithm that will work against constructions which leverage the underlying algebraic structure of the group. In fact, we know that this algebraic structure is powerful enough to provide generic constructions for several powerful primitives including oblivious transfer and chosen ciphertext secure public-key cryptosystems (note that an IBE generalizes such systems). Technically, we explore statistical properties of the group algebra associated with a DDH oracle, which can be of independent interest.

The indifferentiability framework of Maurer, Renner, and Holenstein (MRH) has gained immense popularity in recent years and has proved to be a powerful way to argue security of cryptosystems that enjoy proofs in the random oracle model. Recently, however, Ristenpart, Shacham, and Shrimpton (RSS) showed that the composition theorem of MRH has a more limited scope than originally thought, and that extending its scope required the introduction of reset-indifferentiability, a notion which no practical domain extenders satisfy with respect to random oracles. In light of the results of RSS, we set out to rigorously tackle the specifics of indifferentiability and reset-indifferentiability by viewing the notions as special cases of a more general definition. Our contributions are twofold. Firstly, we provide the necessary formalism to refine the notion of indifferentiability regarding composition. By formalizing the definition of stage minimal games we expose new notions lying in between regular indifferentiability (MRH) and reset-indifferentiability (RSS). Secondly, we answer the open problem of RSS by showing that it is impossible to build any domain extender which is reset-indifferentiable from a random oracle. This result formally confirms the intuition that reset-indifferentiability is too strong of a notion to be satisfied by any hash function. As a consequence we look at the weaker notion of single-reset-indifferentiability, yet there as well we demonstrate that there are no ``meaningful'' domain extenders which satisfy this notion. Not all is lost though, as we also view indifferentiability in a more general setting and point out the possibility for different variants of indifferentiability.

SM3~\cite{SM3hf} is the Chinese cryptographic hash standard which was announced in 2010 and designed by Wang $et\ al.$. It is based on the Merkle-Damgård design and its compression function can be seen as a block cipher used in Davies-Meyer mode. It uses message block of length 512 bits and outputs hash value of length 256 bits. This paper studies the security of SM3 hash function against preimage attack and pseudo-collision attack. We propose preimage attacks on 29-step and 30-step SM3, and pseudo-preimage attacks on 31-step and 32-step SM3 out of 64 steps. The complexities of these attacks are $2^{245}$ 29-step operations, $2^{251.1}$ 30-step operations, $2^{245}$ 31-step operations and $2^{251.1}$ 32-step operations, respectively. These (pseudo) preimage attacks are all from the first step of the reduced SM3. Meanwhile, these (pseudo) preimage attacks can be converted into pseudo-collision attacks on SM3 reduced to 29 steps, 30 steps, 31 steps and 32 steps with complexities of $2^{122}$, $2^{125.1}$, $2^{122}$ and $2^{125.1}$ respectively. As far as we know, the previously best known preimage attacks on SM3 cover 28 steps (from the first step) and 30 steps (from the 7-th step), and there is no publicly published result on (pseudo) collision attack on SM3.

We count ]B, C]-grained, k-factor integers which are simultaneously B-rough and C-smooth and have a fixed number k of prime factors. Our aim is to exploit explicit versions of the prime number theorem as much as possible to get good explicit bounds for the count of such integers. This analysis was inspired by certain inner procedures in the general number field sieve. The result should at least provide some insight in what happens there. We estimate the given count in terms of some recursively defined functions. Since they are still difficult to handle, only another approximation step reveals their orders. Finally, we use the obtained bounds to perform numerical experiments that show how good the desired count can be approximated for the parameters of the general number field sieve in the mentioned inspiring application.

This paper presents the Tate pairing computation on generalized Huff curves proposed by Wu and Feng in \cite{Wu}. In fact, we extend the results of the Tate pairing computation on the standard Huff elliptic curves done previously by Joye, Tibouchi and Vergnaud in \cite{Joux}. We show that the addition step of the Miller loop can be performed in $1\mathbf{M}+(k+15)\mathbf{m}+2\mathbf{c}$ and the doubling one in $1\mathbf{M} + 1\mathbf{S} + (k + 12) \mathbf{m} + 5\mathbf{s} + 2\mathbf{c}$ on the generalized Huff curve.

We give easy proofs of some recent results concerning threshold gaps in ramp schemes. We then generalise a construction method for ramp schemes employing error-correcting codes so that it can be applied using nonlinear (as well as linear) codes. Finally, as an immediate consequence of these results, we provide a new explicit bound on the the minimum length of a code having a specified distance and dual distance.

Subset sum or Knapsack problems of dimension $n$ are known to be hardest for knapsacks of density close to 1.These problems are NP-hard for arbitrary $n$. One can solve such problems either by lattice basis reduction or by optimized birthday algorithms. Recently Becker, Coron, Jou } [BCJ10] present a birthday algorithm that follows Schroeppel, Shamir [SS81], and Howgrave-Graham, Joux [HJ10]. This algorithm solves 50 random knapsacks of dimension 80 and density close to 1 in roughly 15 hours on a 2.67 GHz PC. We present an optimized lattice basis reduction algorithm that follows Schnorr, Euchne} [SE03] using pruning of Schnorr, Hörner [SH95] that solves such random knapsacks of dimension 80 on average in less than a minute, and 50 such problems all together about 9.4 times faster and using much less space than [BCJ10] on another 2.67 GHz PC.

There has been considerable recent interest in "cloud storage'' wherein a user asks a server to store a large file. One issue is whether the user can verify that the server is actually storing the file, and typically a challenge-response protocol is employed to convince the user that the file is indeed being stored correctly. The security of these schemes is phrased in terms of an extractor which will recover or retrieve the file given any "proving algorithm'' that has a sufficiently high success probability. This paper treats proof-of-retrievability schemes in the model of unconditional security, where an adversary has unlimited computational power. In this case retrievability of the file can be modelled as error-correction in a certain code. We provide a general analytical framework for such schemes that yields exact (non-asymptotic) reductions that precisely quantify conditions for extraction to succeed as a function of the success probability of a proving algorithm, and we apply this analysis to several archetypal schemes. In addition, we provide a new methodology for the analysis of keyed POR schemes in an unconditionally secure setting, and use it to prove the security of a modified version of a scheme due to Shacham and Waters under a slightly restricted attack model, thus providing the first example of a keyed POR scheme with unconditional security. We also show how classical statistical techniques can be used to evaluate whether the responses of the prover are accurate enough to permit successful extraction. Finally, we prove a new lower bound on storage and communication complexity of POR schemes.

In this paper we show that the recent technique of computationally complete symbolic attackers proposed by Bana and Comon-Lundh for computationally sound verification is powerful enough to verify actual protocols, such as the Needham-Schroeder-Lowe Protocol. In their model, one does not define explicit Dolev-Yao adversarial capabilities but rather the limitations of the adversarial capabilities. In this paper we present a set of axioms sufficient to show that no symbolic adversary compliant with these axioms can successfully violate secrecy or authentication in case of the NSL protocol. Hence all implementations for which these axioms are sound – namely, implementations using CCA2 encryption, and satisfying a minimal parsing requirement for pairing – exclude the possibility of successful computational attacks.

We present a constant-round concurrent zero-knowledge protocol for NP. Our protocol is sound against uniform polynomial-time attackers, and relies on the existence of families of collision-resistant hash functions, and a new (but in our eyes, natural) falsifiable intractability assumption: Roughly speaking, that Micali's non-interactive CS-proofs are sound for languages in P.

In the setting of cryptographic protocols, the corruption of a party has traditionally been viewed as a simple, uniform and atomic operation, where the adversary decides to get control over a party and this party immediately gets corrupted. In this paper, motivated by the fact that different players may require different resources to get corrupted, we put forth the notion of {\em resource-based corruptions}, where the adversary must invest some resources in order to do so. If the adversary has full information about the system configuration then resource-based corruptions would provide no fundamental difference from the standard corruption model. However, in a resource ``anonymous'' setting, in the sense that such configuration is hidden from the adversary, much is to be gained in terms of efficiency and security. We showcase the power of such {\em hidden diversity} in the context of secure multiparty computation (MPC) with resource-based corruptions and prove that it can effectively be used to circumvent known impossibility results. Specifically, if $OPT$ is the corruption budget that violates the completeness of MPC (the case when half or more of the players are corrupted), we show that if hidden diversity is available, the completeness of MPC can be made to hold against an adversary with as much as a $B\cdot OPT$ budget, for any constant $B>1$. This result requires a suitable choice of parameters (in terms of number of players and their hardness to corrupt), which we provide and further prove other tight variants of the result when the said choice is not available. Regarding efficiency gains, we show that hidden diversity can be used to force the corruption threshold to drop from 1/2 to 1/3, in turn allowing the use of much more efficient (information-theoretic) MPC protocols. We achieve the above through a series of technical contributions: o The modeling of the corruption process in the setting of cryptographic protocols through {\em corruption oracles} as well as the introduction of a notion of reduction to relate such oracles; o the abstraction of the corruption game as a combinatorial problem and its analysis; and, importantly, o the formulation of the notion of {\em inversion effort preserving} (IEP) functions which is a type of direct-sum property, and the property of {\em hardness indistinguishability}. While hardness indistinguishability enables the dissociation of parties' identities and the resources needed to corrupt them, IEP enables the discretization of adversarial work into corruption tokens, all of which may be of independent interest.

In this note, we show the existence of \emph{constant-round} computational zero-knowledge \emph{proofs of knowledge} for all $\NP$. The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zero-knowledge \emph{arguments} of knowledge was proven by Feige and Shamir (CRYPTO 1989). However, the existence of constant-round zero-knowledge proofs of knowledge for all $\NP$ is folklore, to the best of our knowledge, since no proof of this fact has been published.

We consider the question of the adequacy of symbolic models versus computational models for the verification of security protocols. We neither try to include properties in the symbolic model that reflect the properties of the computational primitives nor add computational requirements that enforce the soundness of the symbolic model. We propose in this paper a different approach: everything is possible in the symbolic model unless it contradicts a computational assumption. In this way, we obtain unconditional soundness almost by construction. And we do not need to assume the absence of dynamic corruption or the absence of key-cycles, which are examples of hypotheses that are always used in related works. We set the basic framework, for arbitrary cryptographic primitives and arbitrary protocols, however for trace security properties only.

This paper is a tutorial introduction to the present state-of-the-art in the field of security of lattice-based cryptosystems. After a short introduction to lattices, we describe the main hard problems in lattice theory that cryptosystems base their security on, and we present the main methods of attacking these hard problems, based on lattice basis reduction. We show how to find shortest vectors in lattices, which can be used to improve basis reduction algorithms. Finally we give a framework for assessing the security of cryptosystems based on these hard problems.

It is well-known that one-way permutations (and even one-to-one one-way functions) imply the existence of non-interactive commitments. Furthermore the construction is black-box (i.e., the underlying one-way function is used as an oracle to implement the commitment scheme, and an adversary attacking the commitment scheme is used as an oracle in the proof of security). We rule out the possibility of black-box constructions of non interactive commitments from general (possibly not one-to-one) one-way functions. As far as we know, this is the first result showing a natural cryptographic task that can be achieved in a black-box way from one-way permutations but not from one-way functions. We next extend our black-box separation to constructions of non-interactive commitments from a stronger notion of one-way functions, which we refer to as \emph{hitting} one-way functions. Perhaps surprisingly, Barak, Ong, and Vadhan (Siam JoC '07) showed that there does exist a non-black-box construction of non-interactive commitments from hitting one-way functions. As far as we know, this is the first result to establish a ``separation'' between the power of black-box and non-black-box use of a primitive to implement a natural cryptographic task. We finally show that unless the complexity class NP has program checkers, the above separations extend also to non-interactive instance-based commitments, and 3-message public-coin honest-verifier zero-knowledge protocols with O(log n)-bit verifier messages. The well-known classical zero-knowledge proof for NP fall into this category.

Generalizing a method of Sutherland and the author for elliptic curves, we design a subexponential algorithm for computing the endomorphism ring structure of ordinary abelian varieties of dimension two over finite fields. Although its correctness and complexity bound rely on several assumptions, we report on practical computations showing that it performs very well and can easily handle previously intractable cases.

We construct a functional encryption scheme secure against an a priori bounded polynomial number of collusions for the class of all polynomial-size circuits. Our constructions require only semantically secure public-key encryption schemes and pseudo-random generators computable by small-depth circuits (known to be implied by most concrete intractability assumptions). For certain special cases such as predicate encryption schemes with public index, the construction requires only semantically secure encryption schemes, which is clearly the minimal necessary assumption. Our constructions rely heavily on techniques from secure multiparty computation and randomized encodings. All our constructions are secure under a strong, adaptive simulation-based definition of functional encryption.

In this paper, we revisit formalizations of information-theoretic security for symmetric-key encryption and key agreement protocols which are very fundamental primitives in cryptography. In general, we can formalize information-theoretic security in various ways: some of them can be formalized as stand-alone security by extending (or relaxing) Shannon's perfect secrecy; some of them can be done based on composable security. Then, a natural question about this is: what is the gap between the formalizations? To answer the question, we investigate relationships between several formalizations of information-theoretic security for symmetric-key encryption and key agreement protocols. Specifically, for symmetric-key encryption protocols which may have decryption-errors, we deal with the following formalizations of security: formalizations extended (or relaxed) from Shannon's perfect secrecy by using mutual information and statistical distance; information-theoretic analogue of indistinguishability by Goldwasser and Micali; and the ones of composable security by Maurer et al. and Canetti. Then, we explicitly show that those formalizations are essentially equivalent under both one-time and multiple-use models. Under the both models, we also derive lower bounds on the adversary's (or distinguisher's) advantage and secret-key size required under all of the above formalizations. Although some of them may be already known, we can explicitly derive them all at once through our relationships between the formalizations. In addition, we briefly observe impossibility results which easily follow from the lower bounds. The similar results are also shown for key agreement protocols which may have agreement-errors.

A recent work by Nuida and Hanaoka (in ICITS 2009) provided a proof technique for security of information-theoretically secure cryptographic schemes in which the random input tape is implemented by a pseudorandom generator (PRG). In this paper, we revisit their proof technique and generalize it by introducing some trade-off factor, which involves the original proof technique as a special case and provides a room of improvement of the preceding result. Secondly, we consider two issues of the preceding result; one is the requirement of some hardness assumption in their proof; another is the gap between non-uniform and uniform computational models appearing when transferring from the exact security formulation adopted in the preceding result to the usual asymptotic security. We point out that these two issues can be resolved by using a PRG proposed by Impagliazzo, Nisan and Wigderson (in STOC 1994) against memory-bounded distinguishers, instead of usual PRGs against time-bounded distinguishers. We also give a precise formulation of a computational model explained by Impagliazzo et al., and by using this, perform a numerical comparison showing that, despite the significant advantage of removing hardness assumptions, our result is still better than, or at least competitive to, the preceding result from quantitative viewpoints. The results of this paper would suggest a new motivation to use PRGs against distinguishers with computational constraints other than time complexity in practical situations rather than just theoretical works.

We develop a non-interactive proof-system which we call "Metaproof" (mu-NIZK proof system); it provides a proof of "the existence of a proof to a statement". This meta-mathematical notion indeed seems redundant when we deal with proving NP statements, but in the context of zero-knowledge theory and cryptography it has a large variety of applications. Combined with another tool we develop which we call "on-line simulatable NIZK proof system", it is the key tool used to solve the open problem of the existence of a many prover non-interactive zero-knowledge system (MP-NIZK proof system). This problem was presented by Micali when the important notion of non-interactive zero-knowledge proofs (NIZK) was first suggested and implemented for a sole prover. The solution immensely enlarges the domain of applications of the NIZK model. The work also provides a new connection between bounded (single-theorem) non-interactive zero-knowledge proofs and the unbounded (multi-theorem) one. This may help in reducing the complexity assumption upon which to base NIZK systems. Remark: This is a full version (with more details, more material, and with new proofs) of the Crypto 1990 paper on Metaproof. Over the years, the concept has been used and reinvented for specific settings beyond the original ones, by others; (which has made it more useful). Recently, we were asked about this paper and about details, so here they are! For historical reasons, except for this remark, this version is presented as it was in the above mentioned date under the above affiliations, though we did not pursue publication before!

Non-Linear Feedback Shift Registers (NLFSR) are a generalization of Linear Feedback Shift Registers (LFSRs) in which a current state is a non-linear function of the previous state. The interest in NLFSRs is motivated by their ability to generate pseudo-random sequences which are usually hard to break with existing cryptanalytic methods. However, it is still not known how to construct large $n$-stage NLFSRs which generate full cycles of $2^n$ possible states. This paper presents a method for generating full cycles by a composition of NLFSRs. First, we show that an $n*k$-stage register with period $O(2^{2n})$ can be constructed from $k$ $n$-stage NLFSRs by adding to their feedback functions a logic block of size $O(n*k)$. This logic block implements Boolean functions representing the set of pairs of states whose successors have to be exchanged in order to join cycles. Then, we show how to join all cycles into one by using one more logic block of size $O(n*k^2)$ and an extra time step. The presented method is feasible for generating very large full cycles.

The abstraction of cryptographic operations by term algebras, called Dolev-Yao models, is essential in almost all tool-supported methods for verifying security protocols. Recently significant progress was made in establishing computational soundness results: these results prove that Dolev-Yao style models can be sound with respect to actual cryptographic realizations and security definitions. However, these results came at the cost of imposing various constraints on the set of permitted security protocols: e.g., dishonestly generated keys must not be used, key cycles need to be avoided, and many more. In a nutshell, the cryptographic security definitions did not adequately capture these cases, but were considered carved in stone; in contrast, the symbolic abstractions were bent to reflect cryptographic features and idiosyncrasies, thereby requiring adaptations of existing verification tools. In this paper, we pursue the opposite direction: we consider a symbolic abstraction for public-key encryption and identify two cryptographic definitions called PROG-KDM (programmable key-dependent message) security and MKE (malicious-key extractable) security that we jointly prove to be sufficient for obtaining computational soundness without imposing assumptions on the protocols using this abstraction. In particular, dishonestly generated keys obtained from the adversary can be sent, received, and used. The definitions can be met by existing cryptographic schemes in the random oracle model. This yields the first computational soundness result for trace-properties that holds for arbitrary protocols using this abstraction (in particular permitting to send and receive dishonestly generated keys), and that is accessible to all existing tools for reasoning about Dolev-Yao models without further adaptations.

We implement one-out-of-two bit oblivious transfer (OT) based on the assumptions used in the McEliece cryptosystem: the hardness of decoding random binary linear codes, and the difficulty of distinguishing a permuted generating matrix of Goppa codes from a random matrix. To our knowledge this is the first OT reduction to these problems only.

We revisit the problem of building dual-model secure (DMS) hash functions that are simultaneously provably collision resistant (CR) in the standard model and provably pseudorandom oracle (PRO) in an idealized model. Designing a DMS hash function was first investigated by Ristenpart and Shrimpton (ASIACRYPT 2007); they put forth a generic approach, called Mix-Compress-Mix (MCM), and showed the feasibility of the MCM approach with a secure (but inefficient) construction. An improved construction was later presented by Lehmann and Tessaro (ASIACRYPT 2009). The proposed construction by Ristenpart and Shrimpton requires a non-invertible (pseudo-) random injection oracle (PRIO) and the Lehmann-Tessaro construction requires a non-invertible random permutation oracle (NIRP). Despite showing the feasibility of realizing PRIO and NIRP objects in theory–using ideal ciphers and (trapdoor) one-way permutations– these constructions suffer from several efficiency and implementation issues as pointed out by their designers and briefly reviewed in this paper. In contrast to the previous constructions, we show that constructing a DMS hash function does not require any PRIO or NIRP, and hence there is no need for additional (trapdoor) one-way permutations. In fact, Ristenpart and Shrimpton posed the question of whether MCM is secure under easy-to-invert mixing steps as an open problem in their paper.We resolve this question in the affirmative in the fixed-input-length (FIL) hash setting. More precisely, we show that one can sandwich a provably CR function, which is sufficiently compressing, between two random invertible permutations to build a provably DMS compression function. Any multi-property-preserving (MPP) domain extender that preserves CR and PRO can then be used to convert such a DMS compression function to a full-fledged DMS hash function. Interestingly, there are efficient off-the-shelf candidates for all the three ingredients (provably CR compression functions, random invertible permutations, and MPP domain extenders) from which one can choose to implement such a DMS hash function in practice. Further, we also explain the implementation options as well as a concrete instantiation.

Secret sharing schemes usually have perfect information theoretic security. This implies that each share must be as large as the secret. In this work we propose a scheme where the shares are smaller, while the security becomes computational. The computational security assumption is hardness of factorization, which is a simple and rather standard assumption in cryptography. In our scheme, the shared secret can only be a set of prime numbers.

In the past twenty years, the study of the conjunction of chaos and cryptography has attracted much interest but also met with many problems. Today the security of chaos-based encryptions is usually not considered comparable to those based on number theoretic functions. In this paper, instead of making an encryption system, we focus on the more fundamental notion of one-way function, which is a well-defined function that is easy to evaluate but hard to invert. We see that it is more natural to compare chaotic systems with one-way functions, and such a study could possibly give new insights for chaos-based cryptosystems. We propose a function based on Chebyshev polynomials, and we argue it is likely a one-way function.

We investigate how information leakage reduces computational entropy of a random variable X. Recall that HILL and metric computational entropy are parameterized by quality (how distinguishable is X from a variable Z that has true entropy) and quantity (how much true entropy is there in Z). We prove an intuitively natural result: conditioning on an event of probability p reduces the quality of metric entropy by a factor of p and the quantity of metric entropy by log 1/p note that this means that the reduction in quantity and quality is the same, because the quantity of entropy is measured on logarithmic scale). Our result improves previous bounds of Dziembowski and Pietrzak (FOCS 2008), where the loss in the \emph{quantity} of entropy was related to its original quality. The use of metric entropy simplifies the analogous the result of Reingold et. al. (FOCS 2008) for HILL entropy. Further, we simplify dealing with information leakage by investigating conditional metric entropy. We show that, conditioned on leakage of \lambda bits, metric entropy gets reduced by a factor 2^\lambda in quality and \lambda in quantity.

Traditional hush functions map a large number to a small number such that the reverse-hush has an infinity of solutions, and nonetheless a collision is hard to come by. This primitive is so abundantly useful that one is tempted to extend it such that any number large or small may be mapped to any number larger, or smaller while maintaining the above conditions. This extension would increase the flexibility of the commodity hush primitive, expand its current applications, and likely suggest new ones. Additional generality may be achieved by allowing the input to determine the computational burden, and involving Turing’s Entscheidungsproblem. We propose an algorithm where a natural number, X, is mapped to another natural number Y, referring to the mapping as a "Crypto Square", and to the reverse as "Crypto Square Root": Y = X**2|c and X = &#8730;Y|c. While the crypto-square mapping is a proper function, the square root equation has infinite solutions. There exists a deterministic solution algorithm to find any desired number of solutions to a square-root equation. This asymmetry proves itself useful, since the mapping is Z+&#8594;Z+, and hence the chance of collision for any finite size set is negligible. Unlike standard one-way functions, crypto-square shields the identity of the input (X), not by the intractability of the reverse function, but by Vernam-like equivocation per the infinity of X candidates. This prospect suggests further examination of this “square” algorithm for possible useful roles in various crypto protocols, especially protocols concerned with privacy, authentication and deniability.

When Alice and Bob want to securely evaluate a function of their shared inputs, they typically first express the function as a (boolean or arithmetic) circuit and then securely evaluate that circuit, gate-by-gate. In other words, a secure protocol for evaluating $f$ is typically obtained in a {\em non-black-box-way} from $f$ itself. Consequently, secure computation protocols have high overhead (in communication \& computation) that is directly linked to the circuit-description complexity of $f$. In other settings throughout cryptography, black-box constructions invariably lead to better practical efficiency than comparable non-black-box constructions. Could secure computation protocols similarly be made more practical by eliminating their dependence on a circuit representation of the target function? Or, in other words, {\em must one know the code of $f$ to securely evaluate $f$?} In this work we initiate the theoretical study of this question. We show the following: 1. A complete characterization of the 2-party tasks which admit such security against semi-honest adversaries. The characterization is inspired by notions of {\em autoreducibility} from computational complexity theory. From this characterization, we show a class of pseudorandom functions that {\em cannot} be securely evaluated (when one party holds the seed and the other holds the input) without ``knowing'' the code of the function in question. On the positive side, we show a class of functions (related to blind signatures) that can indeed be securely computed without ``knowing'' the code of the function. 2. Sufficient conditions for such security against malicious adversaries, also based on autoreducibility. We show that it is not possible to prove membership in the image of a one-way function in zero-knowledge, without ``knowing'' the code of the one-way function.

In this work we focus on a simple database commitment functionality where besides the standard security properties, one would like to hide the size of the input of the sender. Hiding the size of the input of a player is a critical requirement in some applications, and relatively few works have considered it. Notable exceptions are the work on zero-knowledge sets introduced in~\cite{MRK03}, and recent work on size-hiding private set intersection~\cite{ADT11}. However, neither of these achieves a secure computation (i.e., a reduction of a real-world attack of a malicious adversary into an ideal-world attack) of the proposed functionality. The first result of this submission consists in defining ``secure'' database commitment and in observing that previous constructions do not satisfy this definition. This leaves open the question of whether there is any way this functionality can be achieved. We then provide an affirmative answer to this question by using new techniques that combined together achieve ``secure'' database commitment. Our construction is in particular optimized to require only a constant number of rounds, to provide non-interactive proofs on the content of the database, and to rely only on the existence of a family of CRHFs. This is the first result where input-size hiding secure computation is achieved for an interesting functionality and moreover we obtain this result with standard security (i.e., simulation in expected polynomial time against fully malicious adversaries, without random oracles, non-black-box extraction assumptions, hardness assumptions against super-polynomial time adversaries, or other controversial/strong assumptions). A key building block in our construction is a universal argument enjoying an improved proof of knowledge property, that we call quasi-knowledge. This property is significantly closer to the standard proof of knowledge property than the weak proof of knowledge property satisfied by previous constructions.

Epsilon-biased distribution has many applications in practice, including universal hashing computation. In this paper we will improve an existing epsilon-biased distribution construction due to Alon et al. that requires to uniformly and efficiently sample irreducible polynomials of a large degree, e.g. between 80 and 160. To remove the need for such a sampling which can be computationally expensive, we will replace the irreducible polynomials by random monic polynomials of higher degree, i.e. every degree r monic polynomial whether irreducible or reducible is selected with the same probability 2^{-r}. To analyse the security of the scheme, we need to find the maximum number of degree r polynomials that divide a degree n polynomial where n > r.

The study of probabilistic secret sharing schemes using arbitrary probability spaces and possibly infinite number of participants lets us investigate abstract properties of such schemes. It highlights important properties, explains why certain definitions work better than others, connects this topic to other branches of mathematics, and might yield new design paradigms. A {\em probabilistic secret sharing scheme} is a joint probability distribution of the shares and the secret together with a collection of {\em secret recovery functions} for qualified subsets. The scheme is measurable if the recovery functions are measurable. Depending on how much information an unqualified subset might have, we define four scheme types: {\em perfect}, {\em almost perfect}, {\em ramp}, and {\em almost ramp}. Our main results characterize the access structures which can be realized by schemes of these types. We show that every access structure can be realized by a non-measurable perfect probabilistic scheme. The construction is based on a paradoxical pair of independent random variables which determine each other. For measurable schemes we have the following complete characterization. An access structure can be realized by a (measurable) perfect, or almost perfect scheme if and only if the access structure, as a subset of the Sierpiński space $\{0,1\}^P$, is open, if and only if it can be realized by a span program. The access structure can be realized by a (measurable) ramp or almost ramp scheme if and only if the access structure is a $G_\delta$ set (intersection of countably many open sets) in the Sierpiński topology, if and only if it can be realized by a Hilbert-space program.

The motivation for extending secret sharing schemes to cases when either the set of players is infinite or the domain from which the secret and/or the shares are drawn is infinite or both, is similar to the case when switching to abstract probability spaces from classical combinatorial probability. It might shed new light on old problems, could connect seemingly unrelated problems, and unify diverse phenomena. Definitions equivalent in the finitary case could be very much different when switching to infinity, signifying their difference. The standard requirement that qualified subsets should be able to determine the secret has different interpretations in spite of the fact that, by assumption, all participants have infinite computing power. The requirement that unqualified subsets should have no, or limited information on the secret suggests that we also need some probability distribution. In the infinite case events with zero probability are not necessarily impossible, and we should decide whether bad events with zero probability are allowed or not. In this paper, rather than giving precise definitions, we enlist an abundance of hopefully interesting infinite secret sharing schemes. These schemes touch quite diverse areas of mathematics such as projective geometry, stochastic processes and Hilbert spaces. Nevertheless our main tools are from probability theory. The examples discussed here serve as foundation and illustration to the more theory oriented companion paper ``Probabilistic Infinite Secret Sharing.''

Secure Multi-Party Computation (MPC) providing information theoretic security allows a set of n parties to securely compute an agreed function F over a finite field ${\mathbb F}$, even if t parties are under the control of a computationally unbounded active adversary. Asynchronous MPC (AMPC) is an important variant of MPC, which works over an asynchronous network. It is well known that perfect AMPC is possible if and only if n \geq 4t+1, while statistical AMPC is possible if and only if n \geq 3t+1. In this paper, we study the communication complexity of AMPC protocols (both statistical and perfect) designed with exactly n = 4t+1 parties. Our major contributions in this paper are as follows: 1. Asynchronous Verifiable Secret Sharing (AVSS) is one of the main building blocks for AMPC. In this paper, we design two AVSS protocols with 4t+1 parties: the first one is statistically secure and has non-optimal resilience, while the second one is perfectly secure and has optimal resilience. Both these schemes achieve a common interesting property, which was not achieved by the previous schemes. Specifically, our AVSS schemes allow to share a secret through a polynomial of degree at most d, where t \leq d \leq 2t. In contrast, the existing AVSS schemes can share a secret only through a polynomial of degree at most t. The new property of our AVSS simplifies the degree reduction step for the evaluation of multiplication gates in an AMPC protocol. 2.Using our statistical AVSS, we design a statistical AMPC protocol with n = 4t+1 which communicates O(n^2) field elements per multiplication gate. Though this protocol has non-optimal resilience, it significantly improves the communication complexity of the existing statistical AMPC protocols. 3. We then present a perfect AMPC protocol with n = 4t+1 (using our perfect AVSS scheme), which also communicates O(n^2) field elements per multiplication gate. This protocol improves on our statistical AMPC protocol as it has optimal resilience. To the best of our knowledge, this is the most communication efficient perfect AMPC protocol in the information theoretic setting.

Collision resistance is a fundamental property required for cryptographic hash functions. One way to ensure collision resistance is to use hash functions based on public key cryptography (PKC) which reduces collision resistance to a hard mathematical problem, but such primitives are usually slow. A more practical approach is to use symmetric-key design techniques which lead to faster schemes, but collision resistance can only be heuristically inferred from the best probability of a single differential characteristic path. We propose a new hash function design with variable hash output sizes of 128, 256, and 512 bits, that reduces this gap. Due to its inherent Substitution-Permutation Network (SPN) structure and JH mode of operation, we are able to compute its differential collision probability using the concept of differentials. Namely, for each possible input differences, we take into account all the differential paths leading to a collision and this enables us to prove that our hash function is secure against a differential collision attack using a single input difference. None of the SHA-3 finalists could prove such a resistance. At the same time, our hash function design is secure against pre-image, second pre-image and rebound attacks, and is faster than PKC-based hashes. Part of our design includes a generalization of the optimal diffusion used in the classical wide-trail SPN construction from Daemen and Rijmen, which leads to near-optimal differential bounds when applied to non-square byte arrays. We also found a novel way to use parallel copies of a serial matrix over the finite field GF(2^4), so as to create lightweight and secure byte-based diffusion for our design. Overall, we obtain hash functions that are fast in software, very lightweight in hardware (about 4625 GE for the $256$-bit hash output) and that provide much stronger security proofs regarding collision resistance than any of the SHA-3 finalists.

We consider distributed private data analysis, where $n$ parties each holding some sensitive data wish to compute some aggregate statistics over all parties' data. We prove a tight lower bound for the private distributed summation problem. Our lower bound is strictly stronger than the prior lower-bound result by Beimel, Nissim, and Omri published in CRYPTO 2008. In particular, we show that any $n$-party protocol computing the sum with sparse communication graph must incur an additive error of $\Omega(\sqrt{n})$ with constant probability, in order to defend against potential coalitions of compromised users. Furthermore, we show that in the client-server communication model, where all users communicate solely with an untrusted server, the additive error must be $\Omega(\sqrt{n})$, regardless of the number of messages or rounds. Both of our lower-bounds, for the general setting and the client-to-server communication model, are strictly stronger than those of Beimel, Nissim and Omri, since we remove the assumption on the number of rounds (and also the number of messages in the client-to-server communication model). Our lower bounds generalize to the $(\epsilon, \delta)$ differential privacy notion, for reasonably small values of $\delta$.

Let $\G$ be a group of prime order $q$, and let $g_1,\ldots,g_n$ be random elements of $\G$. We say that a vector $\vecx = (x_1,\ldots,x_n)\in \Z_q^n$ is a {\em discrete log representation} of some some element $y\in\G$ (with respect to $g_1,\ldots,g_n$) if $g_1^{x_1}\cdots g_n^{x_n} = y$. Any element $y$ has many discrete log representations, forming an affine subspace of $\Z_q^n$. We show that these representations have a nice {\em continuous leakage-resilience} property as follows. Assume some attacker $\A(g_1,\ldots,g_n,y)$ can repeatedly learn $L$ bits of information on arbitrarily many random representations of $y$. That is, $\A$ adaptively chooses polynomially many leakage functions $f_i:\Z_q^n\rightarrow \{0,1\}^L$, and learns the value $f_i(\vecx_i)$, where $\vecx_i$ is a {\em fresh and random} discrete log representation of $y$. $\A$ wins the game if it eventually outputs a valid discrete log representation $\vecx^*$ of $y$. We show that if the discrete log assumption holds in $\G$, then no polynomially bounded $\A$ can win this game with non-negligible probability, as long as the leakage on each representation is bounded by $L\approx (n-2)\log q = (1-\frac{2}{n})\cdot |\vecx|$. As direct extensions of this property, we design very simple continuous leakage-resilient (CLR) one-way function (OWF) and public-key encryption (PKE) schemes in the so called ``invisible key update'' model introduced by Alwen et al. at CRYPTO'09. Our CLR-OWF is based on the standard Discrete Log assumption and our CLR-PKE is based on the standard Decisional Diffie-Hellman assumption. Prior to our work, such schemes could only be constructed in groups with a bilinear pairing. As another surprising application, we show how to design the first leakage-resilient {\em traitor tracing} scheme, where no attacker, getting the secret keys of a small subset of decoders (called ``traitors'') {\em and} bounded leakage on the secret keys of all other decoders, can create a valid decryption key which will not be traced back to at least one of the traitors.

Abstract: Consider two parties holding samples from correlated distributions W and W', respectively, where these samples are within distance t of each other in some metric space. The parties wish to agree on a close-to-uniformly distributed secret key R by sending a single message over an insecure channel controlled by an all-powerful adversary who may read and modify anything sent over the channel. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret SK_Ext that they can use to generate a sequence of session keys {R_j} using multiple pairs {(W_j,W'_j)}. The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded-storage model with errors. We show solutions that improve upon previous work in several respects: -- The best prior solution for the keyless case with no errors (i.e., t=0) requires the min-entropy of W to exceed 2n/3, where n is the bit-length of W. Our solution applies whenever the min-entropy of W exceeds the minimal threshold n/2, and yields a longer key. -- Previous solutions for the keyless case in the presence of errors (i.e., t>0) required random oracles. We give the first constructions (for certain metrics) in the standard model. -- Previous solutions for the keyed case were stateful. We give the first stateless solution.

A $(k,l)$ hash-function combiner for property $P$ is a construction that, given access to $l$ hash functions, yields a single cryptographic hash function which has property $P$ as long as at least $k$ out of the $l$ hash functions have that property. Hash function combiners are used to hedge against the failure of one or more of the individual components. One example of the application of hash function combiners are the previous versions of the TLS and SSL protocols \cite{RFC:6101,RFC:5246}. The concatenation combiner which simply concatenates the outputs of all hash functions is an example of a robust combiner for collision resistance. However, its output length is, naturally, significantly longer than each individual hash-function output, while the security bounds are not necessarily stronger than that of the strongest input hash-function. In 2006 Boneh and Boyen asked whether a robust black-box combiner for collision resistance can exist that has an output length which is significantly less than that of the concatenation combiner \cite{C:BonBoy06}. Regrettably, this question has since been answered in the negative for fully black-box constructions (where hash function and adversary access is being treated as black-box), that is, combiners (in this setting) for collision resistance roughly need at least the length of the concatenation combiner to be robust \cite{C:BonBoy06,C:CRSTVW07,EC:Pietrzak07,C:Pietrzak08}. In this paper we examine weaker notions of collision resistance, namely: \emph{second pre-image resistance} and \emph{target collision resistance} \cite{FSE:RogShr04} and \emph{pre-image resistance}. As a generic brute-force attack against any of these would take roughly $2^n$ queries to an $n$-bit hash function, in contrast to only $2^{n/2}$ queries it would take to break collision resistance (due to the birthday bound), this might indicate that combiners for weaker notions of collision resistance can exist which have a significantly shorter output than the concatenation combiner (which is, naturally, also robust for these properties). Regrettably, this is not the case.

In this paper, we construct a class of vectorial Boolean functions over $\mathbb{F}_{2^{n}}$ with high algebraic immunity based on the decomposition of the multiplicative group of $\mathbb{F}_{2^n}$. By viewing $\mathbb{F}_{2^{n}}$ as $G_1G_2\bigcup \{0\} $ (where $G_1$ and $G_2$ are subgroups of $\mathbb{F}_{2^{n}}^{*},~(\#G_1,\#G_2)=1$ and $\#G_1\times \#G_2=2^{2k}-1$), we give a generalized description for constructing vectorial Boolean functions with high algebraic immunity. Moreover, when $n$ is even, we provide two special classes of vectorial Boolean functions with high(sometimes optimal) algebraic immunity, one is hyper-bent, and the other is of balancedness and optimal algebraic degree .

We introduce a new characterization of the NP complexity class, called Quadratic Span Programs (QSPs), which is a natural extension of span programs defined by Karchmer and Wigderson. Our main motivation is the construction of succinct arguments of NP-statements that are quick to construct and verify. QSPs seem well-suited for this task, perhaps even better than Probabilistically Checkable Proofs (PCPs). In 2010, Groth constructed a NIZK argument in the common reference string (CRS) model for Circuit-SAT consisting of only 42 elements in a bilinear group. Interestingly, his argument does not (explicitly) use PCPs. But his scheme has some disadvantages -- namely, the CRS size and prover computation are both quadratic in the circuit size. In 2011, Lipmaa reduced the CRS size to quasi-linear, but with prover computation still quadratic. Using QSPs we construct a NIZK argument in the CRS model for Circuit-SAT consisting of just 7 group elements. The CRS size is linear in the circuit size, and prover computation is quasi-linear, making our scheme seemingly quite practical. (The prover only needs to do a linear number of group operations; the quasi-linear computation is a multipoint evaluation and interpolation.) Our results are complementary to those of Valiant (TCC 2008) and Bitansky et al. (2012), who use "bootstrapping" (recursive composition) of arguments to reduce CRS size and prover and verifier computation. QSPs also provide a crisp mathematical abstraction of some of the techniques underlying Groth's and Lipmaa's constructions.