waashk/dblp huggingface dataset:
noninteractive statistical zero-knowledge proofs for lattice problems. we construct noninteractive statistical zero-knowledge (niszk) proof systems for a variety of standard approximation problems on lattices, such as the shortest independent vectors problem and the complement of the shortest vector problem. prior proof systems for lattice problems were either interactive or leaked knowledge (or both).our systems are the first known niszk proofs for any cryptographically useful problems that are not related to integer factorization. in addition, they are proofs of knowledge, have reasonable complexity, and generally admit efficient prover algorithms (given appropriate auxiliary input). in some cases, they even imply the first known interactive statistical zero-knowledge proofs for certain cryptographically important lattice problems.we also construct an niszk proof for a special kind of disjunction (i.e., or gate) related to the shortest vector problem. this may serve as a useful tool in potential constructions of noninteractive (computational) zero knowledge proofs for np based on lattice assumptions.
dynamic threshold public-key encryption. this paper deals with threshold public-key encryption which allows a pool of players to decrypt a ciphertext if a given threshold of authorized players cooperate. we generalize this primitive to the dynamic setting, where any user can dynamically join the system, as a possible recipient; the sender can dynamically choose the authorized set of recipients, for each ciphertext; and the sender can dynamically set the threshold t for decryption capability among the authorized set. we first give a formal security model, which includes strong robustness notions, and then we propose a candidate achieving all the above dynamic properties, that is semantically secure in the standard model, under a new non-interactive assumption, that fits into the general diffie-hellman exponent framework on groups with a bilinear map. it furthermore compares favorably with previous proposals, a.k.a. threshold broadcast encryption, since this is the first threshold public-key encryption, with dynamic authorized set of recipients and dynamic threshold that provides constant-size ciphertexts.
key-recovery attacks on universal hash function based mac algorithms. this paper discusses key recovery and universal forgery attacks on several mac algorithms based on universal hash functions. the attacks use a substantial number of verification queries but eventually allow for universal forgeries instead of existential or multiple forgeries. this means that the security of the algorithms completely collapses once a few forgeries are found. some of these attacks start off by exploiting a weak key property, but turn out to become full-fledged divide and conquer attacks because of the specific structure of the universal hash functions considered. partial information on a secret key can be exploited too, in the sense that it renders some key recovery attacks practical as soon as a few key bits are known. these results show that while universal hash functions offer provable security, high speeds and parallelism, their simple combinatorial properties make them less robust than conventional message authentication primitives.
cryptanalysis of the gost hash function. in this article, we analyze the security of the gost hash function. the gost hash function, defined in the russian standard gost 34.11-94, is an iterated hash function producing a 256-bit hash value. as opposed to most commonly used hash functions such as md5 and sha-1, the gost hash function defines, in addition to the common iterative structure, a checksum computed over all input message blocks. this checksum is then part of the final hash value computation.as a result of our security analysis of the gost hash function, we present the first collision attack with a complexity of about 2105 evaluations of the compression function. furthermore, we are able to significantly improve upon the results of mendel et al. with respect to preimage and second preimage attacks. our improved attacks have a complexity of about 2192 evaluations of the compression function.
new state recovery attack on rc4. the stream cipher rc4 was designed by r. rivest in 1987, and it is a widely deployed cipher. in this paper we analyse the class rc4-n of rc4-like stream ciphers, where n is the modulus of operations, as well as the length of internal arrays. our new attack is a state recovery attack which accepts the keystream of a certain length, and recovers the internal state. for the reduced rc4-100, our attack has total complexity of around 293 operations, whereas the best previous attack (from knudsen et al.) needs 2236 of time.the complexity of the attack applied to the original rc4-256 depends on the parameters of specific states (patterns), which are in turn hard to discover. extrapolated parameters from smaller patterns give us the attack of complexity about 2241, and it is much smaller than the complexity of the best known previous attack 2779. the algorithm of the new attack was implemented and verified on small cases.
communication complexity in algebraic two-party protocols. in cryptography, there has been tremendous success in building various two-party protocols with small communication complexity out of homomorphic semantically-secure encryption schemes, using their homomorphic properties in a black-box way. a few notable examples of such primitives include items like single database private information retrieval (pir) schemes (introduced in [15]) and private database update with small communication (introduced in [5]). in this paper, we illustrate a general methodology for determining what types of protocols can and cannot be implemented with small communication by using homomorphic encryption in a black-box way.we hope that this work will provide a simple "litmus test" of feasibility for black-box use of known homomorphic encryption schemes by other cryptographic researchers attempting to develop new protocols with low communication. additionally, a precise mathematical language for reasoning about such problems is developed in this work, which may be of independent interest. we stress that the class of algebraic structures for which we prove communication complexity lower bounds is large, and covers practically all known semantically-secure homomorphic cryptosystems (including those based upon bilinear maps).finally, we show the following equivalence which relates group homomorphic encryption and a major open question of designing a so-called fully-homomorphic cryptosystem: a fully homomorphic encryption scheme (over a non-zero ring) exists if and only if there exists homomorphic encryption over any finite non-abelian simple group. this result somewhat generalizes results of barrington [1] (to any group containing a finite non-abelian simple subgroup) and of maurer and rhodes [18], and in fact gives a constructive proof of the 1974 result werner [28]. (this also answers an open question posed by rappe in [23], who in 2004 proved a special case of this result.)
preimages for reduced sha-0 and sha-1. in this paper, we examine the resistance of the popular hash function sha-1 and its predecessor sha-0 against dedicated preimage attacks. in order to assess the security margin of these hash functions against these attacks, two new cryptanalytic techniques are developed: reversing the inversion problem: the idea is to start with an impossible expanded message that would lead to the required digest, and then to correct this message until it becomes valid without destroying the preimage property. p 3 graphs : an algorithm based on the theory of random graphs that allows the conversion of preimage attacks on the compression function to attacks on the hash function with less effort than traditional meet-in-the-middle approaches. combining these techniques, we obtain preimage-style shortcuts attacks for up to 45 steps of sha-1, and up to 50 steps of sha-0 (out of 80).
improved bounds on security reductions for discrete log based signatures. despite considerable research efforts, no efficient reduction from the discrete log problem to forging a discrete log based signature (e.g. schnorr) is currently known. in fact, negative results are known. paillier and vergnaud [pv05] show that the forgeability of several discrete log based signatures cannot be equivalent to solving the discrete log problem in the standard model, assuming the so-called one-more discrete log assumption and algebraic reductions. they also show, under the same assumptions, that, any security reduction in the random oracle model (rom) from discrete log to forging a schnorr signature must lose a factor of at least $\sqrt{q_h}$ in the success probability. here q h is the number of queries the forger makes to the random oracle. the best known positive result, due to pointcheval and stern [ps00], also in the rom, gives a reduction that loses a factor of q h . in this paper, we improve the negative result from [pv05]. in particular, we show that any algebraic reduction in the rom from discrete log to forging a schnorr signature must lose a factor of at least $q_h^{2/3}$, assuming the one-more discrete log assumption. we also hint at certain circumstances (by way of restrictions on the forger) under which this lower bound may be tight. these negative results indicate that huge loss factors may be inevitable in reductions from discrete log to discrete log based signatures.
circular-secure encryption from decision diffie-hellman. we describe a public-key encryption system that remains secure even encrypting messages that depend on the secret keys in use. in particular, it remains secure under a "key cycle" usage, where we have a cycle of public/secret key-pairs (pk i ,sk i ) for i = 1,...,n, and we encrypt each sk i under ${\rm pk}_{(i \bmod n)+1}$. such usage scenarios sometimes arise in key-management systems and in the context of anonymous credential systems. also, security against key cycles plays a role when relating "axiomatic security" of protocols that use encryption to the "computational security" of concrete instantiations of these protocols.the existence of encryption systems that are secure in the presence of key cycles was wide open until now: on the one hand we had no constructions that provably meet this notion of security (except by relying on the random-oracle heuristic); on the other hand we had no examples of secure encryption systems that become demonstrably insecure in the presence of key-cycles of length greater than one.here we construct an encryption system that is circular-secure against chosen-plaintext attacks under the decision diffie-hellman assumption (without relying on random oracles). our proof of security holds even if the adversary obtains an encryption clique, that is, encryptions of sk i under pk j for all 1 ≤ i,j ≤ n. we also construct a circular counterexample: a one-way secure encryption scheme that breaks completely if an encryption cycle (of any size) is published.
constructing cryptographic hash functions from fixed-key blockciphers. we propose a family of compression functions built from fixed-key blockciphers and investigate their collision and preimage security in the ideal-cipher model. the constructions have security approaching and in many cases equaling the security upper bounds found in previous work of the authors [24]. in particular, we describe a 2n-bit to n-bit compression function using three n-bit permutation calls that has collision security n 0.5, where n = 2 n , and we describe 3n-bit to 2n-bit compression functions using five and six permutation calls and having collision security of at least n 0.55 and n 0.63.
programmable hash functions and their applications. we introduce a new information-theoretic primitive called programmable hash functions (phfs). phfs can be used to program the output of a hash function such that it contains solved or unsolved discrete logarithm instances with a certain probability. this is a technique originally used for security proofs in the random oracle model. we give a variety of standard model realizations of phfs (with different parameters).the programmability of phfs make them a suitable tool to obtain black-box proofs of cryptographic protocols when considering adaptive attacks. we propose generic digital signature schemes from the strong rsa problem and from some hardness assumption on bilinear maps that can be instantiated with any phf. our schemes offer various improvements over known constructions. in particular, for a reasonable choice of parameters, we obtain short standard model digital signatures over bilinear maps.
compression from collisions, or why crhf combiners have a long output. a black-box combiner for collision resistant hash functions (crhf) is a construction which given black-box access to two hash functions is collision resistant if at least one of the components is collision resistant.in this paper we prove a lower bound on the output length of black-box combiners for crhfs. the bound we prove is basically tight as it is achieved by a recent construction of canetti et al [crypto'07]. the best previously known lower bounds only ruled out a very restricted class of combiners having a very strong security reduction: the reduction was required to output collisions for both underlying candidate hash-functions given a single collision for the combiner (canetti et al [crypto'07] building on boneh and boyen [crypto'06] and pietrzak [eurocrypt'07]).our proof uses a lemma similar to the elegant "reconstruction lemma" of gennaro and trevisan [focs'00], which states that any function which is not one-way is compressible (and thus uniformly random function must be one-way). in a similar vein we show that a function which is not collision resistant is compressible. we also borrow ideas from recent work by haitner et al. [focs'07], who show that one can prove the reconstruction lemma even relative to some very powerful oracles (in our case this will be an exponential time collision-finding oracle).
a generalization of ddh with applications to protocol analysis and computational soundness. in this paper we identify the (p,q)-ddh assumption, as an extreme, powerful generalization of the decisional diffie-hellman (ddh) assumption: virtually all previously proposed generalizations of ddh are instances of the (p,q)-ddh problem. we prove that our generalization is no harder than ddh through a concrete reduction that we show to be rather tight in most practical cases. one important consequence of our result is that it yields significantly simpler security proofs for protocols that use extensions of ddh. we exemplify in the case of several group-key exchange protocols (among others we give an elementary, direct proof for the burmester-desmedt protocol). finally, we use our generalization of ddh to extend the celebrated computational soundness result of abadi and rogaway [1] so that it can also handle exponentiation and diffie-hellman-like keys. the extension that we propose crucially relies on our generalization and seems hard to achieve through other means.
finding small roots of bivariate integer polynomial equations: a direct approach. coppersmith described at eurocrypt 96 an algorithm for finding small roots of bivariate integer polynomial equations, based on lattice reduction. a simpler algorithm was later proposed in [9], but it was asymptotically less efficient than coppersmith's algorithm. in this paper, we describe an analogous simplification but with the same asymptotic complexity as coppersmith. we illustrate our new algorithm with the problem of factoring rsa moduli with high-order bits known; in practical experiments our method is several orders of magnitude faster than [9].
new efficient attacks on statistical disclosure control mechanisms. the goal of a statistical database is to provide statistics about a population while simultaneously protecting the privacy of the individual records in the database. the tension between privacy and usability of statistical databases has attracted much attention in statistics, theoretical computer science, security, and database communities in recent years. a line of research initiated by dinur and nissim investigates for a particular type of queries, lower bounds on the distortion needed in order to prevent gross violations of privacy. the first result in the current paper simplifies and sharpens the dinur and nissim result.the dinur-nissim style results are strong because they demonstrate insecurity of all low-distortion privacy mechanisms. the attacks have an all-or-nothing flavor: letting n denote the size of the database, ¿(n) queries are made before anything is learned, at which point ¿(n) secret bits are revealed. restricting attention to a wide and realistic subset of possible low-distortion mechanisms, our second result is a more acute attack, requiring only a fixed number of queries for each bit revealed.
on notions of security for deterministic encryption, and efficient constructions without random oracles. the study of deterministic public-key encryption was initiated by bellare et al. (crypto '07), who provided the "strongest possible" notion of security for this primitive (called priv) and constructions in the random oracle (ro) model. we focus on constructing efficient deterministic encryption schemes without random oracles. to do so, we propose a slightly weaker notion of security, saying that no partial information about encrypted messages should be leaked as long as each message is a-priori hard-to-guess given the others (while priv did not have the latter restriction). nevertheless, we argue that this version seems adequate for many practical applications. we show equivalence of this definition to single-message and indistinguishability-based ones, which are easier to work with. then we give general constructions of both chosen-plaintext (cpa) and chosen-ciphertext-attack (cca) secure deterministic encryption schemes, as well as efficient instantiations of them under standard number-theoretic assumptions. our constructions build on the recently-introduced framework of peikert and waters (stoc '08) for constructing cca-secure probabilistic encryption schemes, extending it to the deterministic-encryption setting as well.
scalable multiparty computation with nearly optimal work and resilience. we present the first general protocol for secure multiparty computation in which the total amount of work required by n players to compute a function f grows only polylogarithmically with n (ignoring an additive term that depends on n but not on the complexity of f). moreover, the protocol is also nearly optimal in terms of resilience, providing computational security against an active, adaptive adversary corrupting a (1/2 ¿ ¿) fraction of the players, for an arbitrary ¿> 0.
cryptographic complexity of multi-party computation problems: classifications and separations. we develop new tools to study the relative complexities of secure multi-party computation tasks in the universal composition framework. when one task can be securely realized using another task as a black-box, we interpret this as a qualitative, complexity-theoretic reduction between the two tasks. virtually all previous characterizations of mpc functionalities, in the uc model or otherwise, focus exclusively on secure function evaluation. in comparison, the tools we develop do not rely on any special internal structure of the functionality, thus applying to functionalities with arbitrary behavior. our tools additionally apply uniformly to both the ppt and unbounded computation models.our first main tool is an exact characterization of realizability in the uc framework with respect to a large class of communication channel functionalities. using this characterization, we can rederive all previously-known impossibility results as immediate and simple corollaries. we also complete the combinatorial characterization of 2-party secure function evaluation initiated by [12] and partially extend the combinatorial conditions to the multi-party setting. our second main tool allows us to translate complexity separations in simpler mpc settings (such as the honest-but-curious corruption model) to the standard (malicious) setting. using this tool, we demonstrate the existence of functionalities which are neither realizable nor complete, in the unbounded computation model.
public-key locally-decodable codes. in this paper we introduce the notion of a public-key encryption scheme that is also a locally-decodable error-correcting code (pkldc). in particular, we allow any polynomial-time adversary to read the entire ciphertext, and corrupt a constant fraction of the bits of the entire ciphertext. nevertheless, the decoding algorithm can recover any bit of the plaintext with all but negligible probability by reading only a sublinear number of bits of the (corrupted) ciphertext.we give a general construction of a pkldc from any semantically-secure public key encryption (ss-pke) and any private information retrieval (pir) protocol. since homomorphic encryption implies pir, we also show a reduction from any homomorphic encryption protocol to pkldc.applying our construction to the best known pir protocol (that of gentry and ramzan), we obtain a pkldc, which for messages of size n and security parameter k achieves ciphertexts of size $\mathcal{o}(n)$, public key of size $\mathcal{o}(n+k)$, and locality of size $\mathcal{o}(k^2)$. this means that for messages of length n = ¿(k 2 + ¿ ), we can decode a bit of the plaintext from a corrupted ciphertext while doing computation sublinear in n.
bits security of the elliptic curve diffie-hellman secret keys. we show that the least significant bits (lsb) of the elliptic curve diffie---hellman secret keys are hardcore. more precisely, we prove that if one can efficiently predict the lsb with non-negligible advantage on a polynomial fraction of all the curves defined over a given finite field $\mathbb{f}_p$, then with polynomial factor overhead, one can compute the entire diffie---hellman secret on a polynomial fraction of all the curves over the same finite field. our approach is based on random self-reducibility (assuming grh) of the diffie---hellman problem among elliptic curves of the same order. as a part of the argument, we prove a refinement of h. w. lenstra's lower bounds on the sizes of the isogeny classes of elliptic curves, which may be of independent interest.