waashk/dblp huggingface dataset:
solving hidden number problem with one bit oracle and advice. in the hidden number problem (hnp), the goal is to find a hidden number s, when given p, g and access to an oracle that on query a returns the k most significant bits of $s\cdot g^a \bmod p$.we present an algorithm solving hnp, when given an advice depending only on p and g; the running time and advice length are polynomial in logp. this algorithm improves over prior hnp algorithms in achieving: (1) optimal number of bits k ¿ 1 (compared with k ¿ ¿(loglogp)); (2) robustness to random noise; and (3) handling a wide family of predicates on top of the most significant bit.as a central tool we present an algorithm that, given oracle access to a function f over ${\mathbb z}_n$, outputs all the significant fourier coefficients of f (i.e., those occupying, say, at least 1% of the energy). this algorithm improves over prior works in being: local. its running time is polynomial in logn and $l_1(\widehat f)$ (for $l_1(\widehat f)$ the sum of f's fourier coefficients, in absolute value). universal. for any n,t, the same oracle queries are asked for all functions f over ${\mathbb z}_n$ s.t. $l_1(\widehat f)\le t$. robust. the algorithm succeeds with high probability even if the oracle to f is corrupted by random noise. the acm portal is published by the association for computing machinery. copyright © 2010 acm, inc. terms of usage privacy policy code of ethics contact us useful downloads: adobe acrobat quicktime windows media player real player
public-key cryptosystems resilient to key leakage. most of the work in the analysis of cryptographic schemes is concentrated in abstract adversarial models that do not capture side-channel attacks. such attacks exploit various forms of unintended information leakage, which is inherent to almost all physical implementations. inspired by recent side-channel attacks, especially the "cold boot attacks", akavia, goldwasser and vaikuntanathan (tcc '09) formalized a realistic framework for modeling the security of encryption schemes against a wide class of side-channel attacks in which adversarially chosen functions of the secret key are leaked. in the setting of public-key encryption, akavia et al. showed that regev's lattice-based scheme (stoc '05) is resilient to any leakage of l / polylog(l) bits, where l is the length of the secret key.in this paper we revisit the above-mentioned framework and our main results are as follows: we present a generic construction of a public-key encryption scheme that is resilient to key leakage from any universal hash proof system. the construction does not rely on additional computational assumptions, and the resulting scheme is as efficient as the underlying proof system. existing constructions of such proof systems imply that our construction can be based on a variety of number-theoretic assumptions, including the decisional diffie-hellman assumption (and its progressively weaker d-linear variants), the quadratic residuosity assumption, and paillier's composite residuosity assumption. we construct a new hash proof system based on the decisional diffie-hellman assumption (and its d-linear variants), and show that the resulting scheme is resilient to any leakage of l(1 ¿ o(1)) bits. in addition, we prove that the recent scheme of boneh et al. (crypto '08), constructed to be a "circular-secure" encryption scheme, is resilient to any leakage of l(1 ¿ o(1)) bits. these two proposed schemes complement each other in terms of efficiency. we extend the framework of key leakage to the setting of chosen-ciphertext attacks. on the theoretical side, we prove that the naor-yung paradigm is applicable in this setting as well, and obtain as a corollary encryption schemes that are cca2-secure with any leakage of l(1 ¿ o(1)) bits. on the practical side, we prove that variants of the cramer-shoup cryptosystem (along the lines of our generic construction) are cca1-secure with any leakage of l/4 bits, and cca2-secure with any leakage of l/6 bits.
computational indistinguishability amplification: tight product theorems for system composition. computational indistinguishability amplification is the problem of strengthening cryptographic primitives whose security is defined by bounding the distinguishing advantage of an efficient distinguisher. examples include pseudorandom generators (prgs), pseudorandom functions (prfs), and pseudorandom permutations (prps).the literature on computational indistinguishability amplification consists only of few isolated results. yao's xor-lemma implies, by a hybrid argument, that no efficient distinguisher has advantage better than (roughly) n2 m ¿ 1 ¿ m in distinguishing the xor of m independent n-bit prg outputs s 1,...,s m from uniform randomness if no efficient distinguisher has advantage more than ¿ in distinguishing s i from a uniform n-bit string. the factor 2 m ¿ 1 allows for security amplification only if $\delta: for the case of prfs, a random-offset xor-construction of myers was the first result to achieve strong security amplification, i.e., also for $\frac{1}{2} \le \delta .this paper proposes a systematic treatment of computational indistinguishability amplification. we generalize and improve the above product theorem for the xor of prgs along five axes. first, we prove the tight information-theoretic bound 2 m ¿ 1 ¿ m (without factor n) also for the computational setting. second, we prove results for interactive systems (e.g. prfs or prps). third, we consider the general class of neutralizing combination constructions, not just xor. as an application, this yields the first indistinguishability amplification results for the cascade of prps (i.e., block ciphers) converting a weak prp into an arbitrarily strong prp, both for single-sided and two-sided queries. fourth, strong security amplification is achieved for a subclass of neutralizing constructions which includes as a special case the construction of myers. as an application we obtain highly practical optimal security amplification for block ciphers, simply by adding random offsets at the input and output of the cascade. fifth, we show strong security amplification also for weakened assumptions like security against random-input (as opposed to chosen-input) attacks.a key technique is a generalization of yao's xor-lemma to (interactive) systems which is of independent interest.
distinguisher and related-key attack on the full aes-256. in this paper we construct a chosen-key distinguisher and a related-key attack on the full 256-bit key aes. we define a notion of differential q -multicollision and show that for aes-256 q-multicollisions can be constructed in time q·267 and with negligible memory, while we prove that the same task for an ideal cipher of the same block size would require at least $o(q\cdot 2^{\frac{q-1}{q+1}128})$ time. using similar approach and with the same complexity we can also construct q-pseudo collisions for aes-256 in davies-meyer mode, a scheme which is provably secure in the ideal-cipher model. we have also computed partial q-multicollisions in time q·237 on a pc to verify our results. these results show that aes-256 can not model an ideal cipher in theoretical constructions. finally we extend our results to find the first publicly known attack on the full 14-round aes-256: a related-key distinguisher which works for one out of every 235 keys with 2120 data and time complexity and negligible memory. this distinguisher is translated into a key-recovery attack with total complexity of 2131 time and 265 memory.
the group of signed quadratic residues and applications. we consider the cryptographic group of signed quadratic residues. this group is particularly useful for cryptography since it is a "gap-group," in which the computational problem (i.e., computing square roots) is as hard as factoring, while the corresponding decisional problem (i.e., recognizing signed quadratic residues) is easy. we are able to show that under the factoring assumption, the strong diffie-hellman assumption over the signed quadratic residues holds. that is, in this group the diffie-hellman problem is hard, even in the presence of a decisional diffie-hellman oracle.we demonstrate the usefulness of our results by applying them to the hybrid elgamal encryption scheme (aka diffie-hellman integrated encryption scheme - dhies). concretely, we consider the security of the scheme when instantiated over the group of signed quadratic residues. it is known that, in the random oracle model, the scheme is chosenciphertext (cca) secure under the strong diffie-hellman assumption and hence, by our results, under the standard factoring assumption. we show that furthermore, in the standard model, hybrid elgamal is cca secure under the higher residuosity assumption, given that the used hash function is four-wise independent. the latter result is obtained using the recent "randomness extraction framework" for hash proof systems.
cryptanalysis of c2. we present several attacks on the block cipher c2, which is used for encrypting dvd audio discs and secure digital cards. c2 has a 56 bit key and a secret 8 to 8 bit s-box. we show that if the attacker is allowed to choose the key, the s-box can be recovered in 224 c2 encryptions. attacking the 56 bit key for a known s-box can be done in complexity 248. finally, a c2 implementation with a 8 to 8 bit secret s-box (equivalent to 2048 secret bits) and a 56 bit secret key can be attacked in 253.5 c2 encryptions on average.
private mutual authentication and conditional oblivious transfer. a bi-directional private authentication, or unlinkable secret handshake, allows two parties to authenticate each other as certified by given certification authorities (i.e. affiliated with given groups), in a mutually private way, in the sense that the protocol leaks no information about either participant to a party which does not satisfy that participant's authentication policy. in particular, the protocol hides what group this participant belongs to, and protocol instances involving the same participant are unlinkable. we construct the first realization of such private authentication using o(1) exponentiations and bilinear maps, secure under strong diffie-hellman and decisional linear assumptions.our protocols rely on a novel technical tool, a family of efficient private conditional oblivious transfer (cot) protocols, secure under ddh, for languages defined by modular arithmetic constraints (e.g. equality, inequality, sums, products) on discrete-log representations of some group elements. (recall that (w 1,...,w n ) is a representation of c in bases (g 1,...,g n ) if $c=g_1^{w_1}...g_n^{w_n}$.) a cot protocol for language l allows sender s to encrypt message m "under" statement x so that receiver r gets m only if r holds a witness for membership of x in l, while s learns nothing. a private cot for l hides not only message m but also statement x from any r that does not know a witness for x in l.
practical cryptanalysis of iso/iec 9796-2 and emv signatures. in 1999, coron, naccache and stern discovered an existential signature forgery for two popular rsa signature standards, iso/iec 9796-1 and 2. following this attack iso/iec 9796-1 was withdrawn. iso/iec 9796-2 was amended by increasing the message digest to at least 160 bits. attacking this amended version required at least 261 operations.in this paper, we exhibit algorithmic refinements allowing to attack the amended (currently valid) version of iso/iec 9796-2 for all modulus sizes. a practical forgery was computed in only two days using 19 servers on the amazon ec2 grid for a total cost of $\simeq\mbox{{\sc us\$800}}$. the forgery was implemented for e = 2 but attacking odd exponents will not take longer. the forgery was computed for the rsa-2048 challenge modulus, whose factorization is still unknown.the new attack blends several theoretical tools. these do not change the asymptotic complexity of coron et al.'s technique but significantly accelerate it for parameter values previously considered beyond reach.while less efficient (us$45,000), the acceleration also extends to emv signatures. emv is an iso/iec 9796-2-compliant format with extra redundancy. luckily, this attack does not threaten any of the 730 million emv payment cards in circulation for operational reasons.costs are per modulus: after a first forgery for a given modulus, obtaining more forgeries is virtually immediate.
meet-in-the-middle preimage attacks against reduced sha-0 and sha-1. preimage resistance of several hash functions has already been broken by the meet-in-the-middle attacks and they utilize a property that their message schedules consist of only permutations of message words. it is unclear whether this type of attacks is applicable to a hash function whose message schedule does not consist of permutations of message words. this paper proposes new attacks against reduced sha-0 and sha-1 hash functions by analyzing a message schedule that does not consist of permutations but linear combinations of message words. the newly developed cryptanalytic techniques enable the meet-in-the-middle attack to be applied to reduced sha-0 and sha-1 hash functions. the attacks find preimages of sha-0 and sha-1 in 2156.6 and 2159.3 compression function computations up to 52 and 48 steps, respectively, compared to the brute-force attack, which requires 2160 compression function computations. the previous best attacks find preimages up to 49 and 44 steps, respectively.
linear algebra with sub-linear zero-knowledge arguments. we suggest practical sub-linear size zero-knowledge arguments for statements involving linear algebra. given commitments to matrices over a finite field, we give a sub-linear size zero-knowledge argument that one committed matrix is the product of two other committed matrices. we also offer a sub-linear size zero-knowledge argument for a committed matrix being equal to the hadamard product of two other committed matrices. armed with these tools we can give many other sub-linear size zero-knowledge arguments, for instance for a committed matrix being upper or lower triangular, a committed matrix being the inverse of another committed matrix, or a committed matrix being a permutation of another committed matrix.a special case of what can be proved using our techniques is the satisfiability of an arithmetic circuit with n gates. our arithmetic circuit zero-knowledge argument has a communication complexity of $o(\sqrt{n})$ group elements. we give both a constant round variant and an o(logn) round variant of our zero-knowledge argument; the latter has a computation complexity of o(n/logn) exponentiations for the prover and o(n) multiplications for the verifier making it efficient for the prover and very efficient for the verifier. in the case of a binary circuit consisting of nand-gates we give a zero-knowledge argument of circuit satisfiability with a communication complexity of $o(\sqrt{n})$ group elements and a computation complexity of o(n) multiplications for both the prover and the verifier.
privacy-enhancing auctions using rational cryptography. we consider enhancing with privacy concerns a large class of auctions, which include sealed-bid single-item auctions but also general multi-item multi-winner auctions, our assumption being that bidders primarily care about monetary payoff and secondarily worry about exposing information about their type to other players and learning information about other players' types, that is, bidders are greedy then paranoid. to treat privacy explicitly within the game theoretic context, we put forward a novel hybrid utility model that considers both monetary and privacy components in players' payoffs.we show how to use rational cryptography to approximately implement any given ex interim individually strictly rational equilibrium of such an auction without a trusted mediator through a cryptographic protocol that uses only point-to-point authenticated channels between the players. by "ex interim individually strictly rational" we mean that, given its type and before making its move, each player has a strictly positive expected utility. by "approximately implement" we mean that, under cryptographic assumptions, running the protocol is a computational nash equilibrium with a payoff profile negligibly close to the original equilibrium.
on the amortized complexity of zero-knowledge protocols. we propose a general technique that allows improving the complexity of zero-knowledge protocols for a large class of problems where previously the best known solution was a simple cut-and-choose style protocol, i.e., where the size of a proof for problem instance x and error probability 2¿ n was o(|x| n) bits. by using our technique to prove n instances simultaneously, we can bring down the proof size per instance to o(|x| + n) bits for the same error probability while using no computational assumptions. examples where our technique applies include proofs for quadratic residuosity, proofs of subgroup membership and knowledge of discrete logarithms in groups of unknown order, and proofs of plaintext knowledge for various types of homomorphic encryptions schemes. the generality of our method stems from a somewhat surprising application of black-box secret sharing schemes.
message authentication codes from unpredictable block ciphers. we design an efficient mode of operation on block ciphers, ss-nmac. our mode has the following properties, when instantiated with a block cipher f to yield a variable-length, keyed hash function h: (1) mac preservation. h is a secure message authentication code (mac) with birthday security, as long as f is unpredictable. (2) prf preservation. h is a secure pseudorandom function (prf) with birthday security, as long as f is pseudorandom. (3) security against side-channels. as long as the block cipher f does not leak side-channel information about its internals to the attacker, properties (1) and (2) hold even if the remaining implementation of h is completely leaky. in particular, if the attacker can learn the transcript of all block cipher calls and other auxiliary information needed to implement our mode of operation. our mode is the first to satisfy the mac preservation property (1) with birthday security, solving the main open problem of dodis et al. [7] from eurocrypt 2008. combined with the prf preservation (2), our mode provides a hedge against the case when the block cipher f is more secure as a mac than as a prf: if it is false, as we hope, we get a secure variable-length prf; however, even if true, we still "salvage" a secure mac, which might be enough for a given application.we also remark that no prior mode of operation offered birthday security against side channel attacks, even if the block cipher was assumed pseudorandom.although very efficient, our mode is three times slower than many of the prior modes, such as cbc, which do not enjoy properties (1) and (3). thus, our work motivates further research to understand the gap between unpredictability and pseudorandomness of the existing block ciphers, such as aes.
how to hash into elliptic curves. we describe a new explicit function that given an elliptic curve e defined over $\mathbb f_{p^n}$, maps elements of $\mathbb f_{p^n}$ into e in deterministic polynomial time and in a constant number of operations over $\mathbb f_{p^n}$. the function requires to compute a cube root. as an application we show how to hash deterministically into an elliptic curve.
position based cryptography. we consider what constitutes identities in cryptography. typical examples include your name and your social-security number, or your fingerprint/iris-scan, or your address, or your (non-revoked) public-key coming from some trusted public-key infrastructure. in many situations, however, where you are defines your identity. for example, we know the role of a bank-teller behind a bullet-proof bank window not because she shows us her credentials but by merely knowing her location. in this paper, we initiate the study of cryptographic protocols where the identity (or other credentials and inputs) of a party are derived from its geographic location.we start by considering the central task in this setting, i.e., securely verifying the position of a device. despite much work in this area, we show that in the vanilla (or standard) model, the above task (i.e., of secure positioning) is impossible to achieve. in light of the above impossibility result, we then turn to the bounded storage model and formalize and construct information theoretically secure protocols for two fundamental tasks: secure positioning; and position based key exchange. we then show that these tasks are in fact universal in this setting --- we show how we can use them to realize secure multi-party computation.our main contribution in this paper is threefold: to place the problem of secure positioning on a sound theoretical footing; to prove a strong impossibility result that simultaneously shows the insecurity of previous attempts at the problem; and to present positive results by showing that the bounded-storage framework is, in fact, one of the "right" frameworks (there may be others) to study the foundations of position-based cryptography.
fast cryptographic primitives and circular-secure encryption based on hard learning problems. the well-studied task of learning a linear function with errors is a seemingly hard problem and the basis for several cryptographic schemes. here we demonstrate additional applications that enjoy strong security properties and a high level of efficiency. namely, we construct: 1 public-key and symmetric-key cryptosystems that provide security for key-dependent messages and enjoy circular security. our schemes are highly efficient: in both cases the ciphertext is only a constant factor larger than the plaintext, and the cost of encryption and decryption is only n·polylog(n) bit operations per message symbol in the public-key case, and polylog(n) bit operations in the symmetric-case. 1 two efficient pseudorandom objects: a "weak randomized pseudorandom function" -- a relaxation of standard prf -- that can be computed obliviously via a simple protocol, and a length-doubling pseudorandom generator that can be computed by a circuit of n ·polylog(n) size. the complexity of our pseudorandom generator almost matches the complexity of the fastest known construction (applebaum et al., random 2006), which runs in linear time at the expense of relying on a nonstandard intractability assumption. our constructions and security proofs are simple and natural, and involve new techniques that may be of independent interest. in addition, by combining our constructions with prior ones, we get fast implementations of several other primitives and protocols.
collusion-free multiparty computation in the mediated model. collusion-free protocols prevent subliminal communication (i.e., covert channels) between parties running the protocol. in the standard communication model, if one-way functions exist, then protocols satisfying any reasonable degree of privacy cannot be collusion-free. to circumvent this impossibility, alwen, shelat and visconti (crypto 2008) recently suggested the mediated model where all communication passes through a mediator. the goal is to design protocols where collusion-freeness is guaranteed as long as the mediator is honest, while standard security guarantees hold if the mediator is dishonest. in this model, they gave constructions of collusion-free protocols for commitments and zero-knowledge proofs in the two-party setting.we strengthen the definition of alwen et al., and resolve the main open questions in this area by showing a collusion-free protocol (in the mediated model) for computing any multi-party functionality.