waashk/dblp huggingface dataset:
detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors. consider an abstract storage device σ(g) that can hold a single element x from a fixed, publicly known finite group g. storage is private in the sense that an adversary does not have read access to σ(g) at all. however, σ(g) is non-robust in the sense that the adversary can modify its contents by adding some offset δ ∈ g. due to the privacy of the storage device, the value δ can only depend on an adversary's a priori knowledge of x. we introduce a new primitive called an algebraic manipulation detection (amd) code, which encodes a source s into a value x stored on σ(g) so that any tampering by an adversary will be detected. we give a nearly optimal construction of amd codes, which can flexibly accommodate arbitrary choices for the length of the source s and security level. we use this construction in two applications: - we show how to efficiently convert any linear secret sharing scheme into a robust secret sharing scheme, which ensures that no unqualified subset of players can modify their shares and cause the reconstruction of some value s′ ≠ s. - we show how to build nearly optimal robust fuzzy extractors for several natural metrics. robust fuzzy extractors enable one to reliably extract and later recover random keys from noisy and non-uniform secrets, such as biometrics, by relying only on non-robust public storage. in the past, such constructions were known only in the random oracle model, or required the entropy rate of the secret to be greater than half. our construction relies on a randomly chosen common reference string (crs) available to all parties.
efficient sequential aggregate signed data. we generalize the concept of sequential aggregate signatures (sas), proposed by lysyanskaya, micali, reyzin, and shacham (lmrs) at eurocrypt 2004, to a new primitive called sequential aggregate signed data (sasd) that tries to minimize the total amount of transmitted data, rather than just signature length. we present sas and sasd schemes that offer numerous advantages over the lmrs scheme. most importantly, our schemes can be instantiated with uncertified claw-free permutations, thereby allowing implementations based on low-exponent rsa and factoring, and drastically reducing signing and verification costs. our schemes support aggregation of signatures under keys of different lengths, and the sasd scheme even has as little as 160 bits of bandwidth overhead. finally, we present a multi-signed data scheme that, when compared to the state-of-the-art multi-signature schemes, is the first scheme with non-interactive signature generation not based on pairings. all of our constructions are proved secure in the random oracle model based on families of claw-free permutations.
a practical attack on keeloq. keeloq is a lightweight block cipher with a 32-bit block size and a 64-bit key. despite its short key size, it is widely used in remote keyless entry systems and other wireless authentication applications. for example, authentication protocols based on keeloq are supposedly used by various car manufacturers in anti-theft mechanisms. this paper presents a practical key recovery attack against keeloq that requires 216 known plaintexts and has a time complexity of 244.5 keeloq encryptions. it is based on the slide attack and a novel approach to meet-in-the-middle attacks. the fully implemented attack requires 65 minutes to obtain the required data and 7.8 days of calculations on 64 cpu cores. a variant which requires 216 chosen plaintexts needs only 3.4 days on 64 cpu cores. using only 10 000 euro, an attacker can purchase a cluster of 50 dual core computers that will find the secret key in about two days. we investigated the way keeloq is intended to be used in practice and conclude that our attack can be used to subvert the security of real systems. an attacker can acquire chosen plaintexts in practice, and one of the two suggested key derivation schemes for keeloq allows to recover the master secret from a single key.
proving tight security for rabin-williams signatures. this paper proves "tight security in the random-oracle model relative to factorization" for the lowest-cost signature systems available today: every hash-generic signature-forging attack can be converted, with negligible loss of efficiency and effectiveness, into an algorithm to factor the public key. the most surprising system is the "fixed unstructured b-0 rabin-williams" system, which has a tight security proof despite hashing unrandomized messages.
on the indifferentiability of the sponge construction. in this paper we prove that the sponge construction introduced in [4] is indifferentiable from a random oracle when being used with a random transformation or a random permutation and discuss its implications. to our knowledge, this is the first time indifferentiability has been shown for a construction calling a random permutation (instead of an ideal compression function or ideal block cipher) and for a construction generating outputs of any length (instead of a fixed length).
isolated proofs of knowledge and isolated zero knowledge. we consider proof of knowledge protocols where the cheating prover may communicate with some external adversarial environment during the run of the proof. without additional setup assumptions, no witness hiding protocol can securely ensure that the prover knows a witness in this scenario. this is because the prover may just be forwarding messages between the environment and the verifier while the environment performs all the necessary computation. in this paper we consider an l-isolated prover, which is restricted to exchanging at most l bits of information with its environment. we introduce a new notion called l-isolated proofs of knowledge (l-ipok). these protocols securely ensure that an l-isolated prover knows the witness. to prevent the above-mentioned attack, an l-ipok protocol has to have communication complexity greater than l. we show that for any relation in np and any value l, there is an l-ipok protocol for that relation. in addition, the communication complexity of such a protocol only needs to be larger than l by a constant multiplicative factor.
kleptography: using cryptography against cryptography. the notion of a secretly embedded trapdoor with universal protection (setup) has been recently introduced. in this paper we extend the study of stealing information securely and subliminally from black-box cryptosystems. the setup mechanisms presented here, in contrast with previous ones, leak secret key information without using an explicit subliminal channel. this extends this area of threats, which we call "kleptography". we introduce new definitions of setup attacks (strong, regular, and weak setups) and the notion of m out of n leakage bandwidth. we show a strong attack which is based on the discrete logarithm problem. we then show how to use this setup to compromise the diffie-hellman key exchange protocol. we also strengthen the previous setup against rsa. the strong attacks employ the discrete logarithm as a one-way function (assuring what is called "forward secrecy"), public-key cryptography, and a technique which we call probabilistic bias removal.
new key-recovery attacks on hmac/nmac-md4 and nmac-md5. at crypto '07, fouque, leurent and nguyen presented full key-recovery attacks on hmac/nmac-md4 and nmac-md5, by extending the partial key-recovery attacks of contini and yin from asiacrypt '06. such attacks are based on collision attacks on the underlying hash function, and the most expensive stage is the recovery of the socalled outer key. in this paper, we show that the outer key can be recovered with near-collisions instead of collisions: near-collisions can be easier to find and can disclose more information. this improves the complexity of the fln attack on hmac/nmac-md4: the number of mac queries decreases from 288 to 272, and the number of md4 computations decreases from 295 to 277. we also improved the total complexity of the related-key attack on nmac-md5. moreover, our attack on nmac- md5 can partially recover the outer key without the knowledge of the inner key, which might be of independent interest.
hb: increasing the security and efficiency of hb. the innovative hb+ protocol of juels and weis [10] extends device authentication to low-cost rfid tags. however, despite the very simple on-tag computation there remain some practical problems with hb+ and despite an elegant proof of security against some limited active attacks, there is a simple man-in-the-middle attack due to gilbert et al. [8]. in this paper we consider improvements to hb+ in terms of both security and practicality. we introduce a new protocol that we denote random-hb#. this proposal avoids many practical drawbacks of hb+, remains provably resistant to attacks in the model of juels and weis, and at the same time is provably resistant to a broader class of active attacks that includes the attack of [8]. we then describe an enhanced variant called hb# which offers practical advantages over hb+.
order-preserving symmetric encryption. we initiate the cryptographic study of order-preserving symmetric encryption (ope), a primitive suggested in the database community by agrawal et al. (sigmod '04) for allowing efficient range queries on encrypted data. interestingly, we first show that a straightforward relaxation of standard security notions for encryption such as indistinguishability against chosen-plaintext attack (ind-cpa) is unachievable by a practical ope scheme. instead, we propose a security notion in the spirit of pseudorandom functions (prfs) and related primitives asking that an ope scheme look "as-random-as-possible" subject to the order-preserving constraint. we then design an efficient ope scheme and prove its security under our notion based on pseudorandomness of an underlying blockcipher. our construction is based on a natural relation we uncover between a random order-preserving function and the hypergeometric probability distribution. in particular, it makes black-box use of an efficient sampling algorithm for the latter.
hash functions and graphs with large girths. we propose and analyse an easily computable cryptographic hash function, for the purpose of signing long variable length texts, which is related to the construction of graphs with large girths.
cryptanalysis of mdc-2. we provide a collision attack and preimage attacks on the mdc-2 construction, which is a method (dating back to 1988) of turning an n-bit block cipher into a 2n-bit hash function. the collision attack is the first below the birthday bound to be described for mdc-2 and, with n = 128, it has complexity 2124.5, which is to be compared to the birthday attack having complexity 2128. the preimage attacks constitute new time/memory trade-offs; the most efficient attack requires time and space about 2 n , which is to be compared to the previous best known preimage attack of lai and massey (eurocrypt '92), having time complexity 23n/2 and space complexity 2 n/2, and to a brute force preimage attack having complexity 22n .
ecm on graphics cards. this paper reports record-setting performance for the elliptic-curve method of integer factorization: for example, 926.11 curves/second for ecm stage 1 with b 1 = 8192 for 280-bit integers on a single pc. the state-of-the-art gmp-ecm software handles 124.71 curves/second for ecm stage 1 with b 1 = 8192 for 280-bit integers using all four cores of a 2.4 ghz core 2 quad q6600.the extra speed takes advantage of extra hardware, specifically two nvidia gtx 295 graphics cards, using a new ecm implementation introduced in this paper. our implementation uses edwards curves, relies on new parallel addition formulas, and is carefully tuned for the highly parallel gpu architecture. on a single gtx 295 the implementation performs 41.88 million modular multiplications per second for a general 280-bit modulus. gmp-ecm, using all four cores of a q6600, performs 13.03 million modular multiplications per second.this paper also reports speeds on other graphics processors: for example, 2414 280-bit elliptic-curve scalar multiplications per second on an older nvidia 8800 gts (g80), again for a general 280-bit modulus. for comparison, the ches 2008 paper "exploiting the power of gpus for asymmetric cryptography" reported 1412 elliptic-curve scalar multiplications per second on the same graphics processor despite having fewer bits in the scalar (224 instead of 280), fewer bits in the modulus (224 instead of 280), and a special modulus (2224 ¿ 296 + 1).
auto-correlations and new bounds on the nonlinearity of boolean functions. it is a well known fact that the nonlinearity of a function f on the n-dimensional vector space vn is bounded from above by 2n-1- 21/2n-1. in cryptographic practice, nonlinear functions are usually constructively obtained in such a way that they support certain mathematical or cryptographic requirements. hence an important question is how to calculate the nonlinearity of a function when extra information is available. in this paper we address this question in the context of auto-correlations, and derive four (two upper and two lower) bounds on the nonlinearity of a function (see table 1). strengths and weaknesses of each bound are also examined. in addition, a few examples axe given to demonstrate the usefulness of the bounds in practical applications. we anticipate that these four bounds will be very useful in calculating the nonlinearity of a cryptographic function when certain extra information on the auto-correlations of the function is available.
realizing hash-and-sign signatures under standard assumptions. currently, there are relatively few instances of "hash-and-sign" signatures in the standard model. moreover, most current instances rely on strong and less studied assumptions such as the strong rsa and q-strong diffie-hellman assumptions. in this paper, we present a new approach for realizing hash-and-sign signatures in the standard model. in our approach, a signer associates each signature with an index i that represents how many signatures that signer has issued up to that point. then, to make use of this association, we create simple and efficient techniques that restrict an adversary which makes q signature requests to forge on an index no greater than $2^{\lceil \lg(q) \rceil} . finally, we develop methods for dealing with this restricted adversary. our approach requires that a signer maintains a small amount of state -- a counter of the number of signatures issued. we achieve two new realizations for hash-and-sign signatures respectively based on the rsa assumption and the computational diffie-hellman assumption in bilinear groups.
resettable zero-knowledge in the weak public-key model. a new public-key model for resettable zero-knowledge (rzk) protocols, which is an extension and generalization of the upperbounded public-key (upk) model introduced by micali and reyzin [eurocrypt' 01, pp. 373-393], is introduced and is named weak public-key (wpk) model. the motivations and applications of the wpk model are justified in the distributed smart-card/server setting and it seems more preferable in practice, especially in e-commerce over internet. in this wpk model a 3-round (optimal) black-box resettable zero-knowledge argument with concurrent soundness for np is presented assuming the security of rsa with large exponents against subexponential-time adversaries. our result improves micali and reyzin's result of resettable zero-knowledge argument with concurrent soundness for np in the upk model. note that although micali and reyzin' protocol satisfies concurrent soundness in the upk model, but it does not satisfy even sequential soundness in our wpk model. our protocol works in a somewhat "parallel repetition" manner to reduce the error probability and the black-box zero-knowledge simulator works in strict polynomial time rather than expected polynomial time. the critical tools used are: verifiable random functions introduced by micali, rabin and vadhan [focs'99, pp. 120-130], zap presented by dwork and naor [focs'00, pp. 283-293] and complexity leveraging introduced by canetti, goldreich, goldwasser and micali [stoc'00, pp. 235-244].
resettably secure computation. the notion of resettable zero-knowledge (rzk) was introduced by canetti, goldreich, goldwasser and micali (focs'01) as a strengthening of the classical notion of zero-knowledge. a rzk protocol remains zero-knowledge even if the verifier can reset the prover back to its initial state anytime during the protocol execution and force it to use the same random tape again and again. following this work, various extensions of this notion were considered for the zero-knowledge and witness indistinguishability functionalities.in this paper, we initiate the study of resettability for more general functionalities. we first consider the setting of resettable two-party computation where a party (called the user) can reset the other party (called the smartcard) anytime during the protocol execution. after being reset, the smartcard comes back to its original state and thus the user has the opportunity to start interacting with it again (knowing that the smartcard will use the same set of random coins). in this setting, we show that it is possible to secure realize all ppt computable functionalities under the most natural (simulation based) definition. thus our results show that in cryptographic protocols, the reliance on randomness and the ability to keep state can be made significantly weaker. our simulator for the aforementioned resettable two-party computation protocol (inherently) makes use of non-black box techniques. second, we provide a construction of simultaneous resettable multi-party computation with an honest majority (where the adversary not only controls a minority of parties but is also allowed to reset any number of parties at any point). interestingly, all our results are in the plain model.
asymmetric group key agreement. a group key agreement (gka) protocol allows a set of users to establish a common secret via open networks. observing that a major goal of gkas for most applications is to establish a confidential channel among group members, we revisit the group key agreement definition and distinguish the conventional (symmetric) group key agreement from asymmetric group key agreement (asgka) protocols. instead of a common secret key, only a shared encryption key is negotiated in an asgka protocol. this encryption key is accessible to attackers and corresponds to different decryption keys, each of which is only computable by one group member. we propose a generic construction of one-round asgkas based on a new primitive referred to as aggregatable signature-based broadcast (asbb), in which the public key can be simultaneously used to verify signatures and encrypt messages while any signature can be used to decrypt ciphertexts under this public key. using bilinear pairings, we realize an efficient asbb scheme equipped with useful properties. following the generic construction, we instantiate a one-round asgka protocol tightly reduced to the decision bilinear diffie-hellman exponentiation (bdhe) assumption in the standard model.
adaptive security in broadcast encryption systems (with short ciphertexts). we present new techniques for achieving adaptive security in broadcast encryption systems. previous work on fully collusion resistant broadcast encryption systems with very short ciphertexts was limited to considering only static security.first, we present a new definition of security that we call semi-static security and show a generic "two-key" transformation from semi-statically secure systems to adaptively secure systems that have comparable-size ciphertexts. using bilinear maps, we then construct broadcast encryption systems that are semi-statically secure in the standard model and have constant-size ciphertexts. our semi-static constructions work when the number of indices or identifiers in the system is polynomial in the security parameter.for identity-based broadcast encryption, where the number of potential indices or identifiers may be exponential, we present the first adaptively secure system with sublinear ciphertexts. we prove security in the standard model.
divisible e-cash systems can be truly anonymous. this paper presents an off-line divisible e-cash scheme where a user can withdraw a divisible coin of monetary value 2 l that he can parceled and spend anonymously and unlinkably. we present the construction of a security tag that allows to protect the anonymity of honest users and to revoke anonymity only in case of cheat for protocols based on a binary tree structure without using a trusted third party. this is the first divisible e-cash scheme that provides both full unlinkability and anonymity without requiring a trusted third party.
range extension for weak prfs; the good, the bad, and the ugly. we investigate a general class of (black-box) constructions for range extension of weak pseudorandom functions: a construction based on m independent functions f 1,...,f m is given by a set of strings over {1,...,m}*, where for example $\{\langle{2}\rangle, \langle{1,2}\rangle\}$ corresponds to the function x ¿[f 2(x),f 2(f 1(x))]. all efficient constructions for range expansion of weak pseudorandom functions that we are aware of are of this form.we completely classify such constructions as good, bad or ugly, where the good constructions are those whose security can be proven via a black-box reduction, the bad constructions are those whose insecurity can be proven via a black-box reduction, and the ugly constructions are those which are neither good nor bad.our classification shows that the range expansion from [10] is optimal, in the sense that it achieves the best possible expansion (2 m ¿ 1 when using m keys).along the way we show that for weak quasirandom functions (i.e. in the information theoretic setting), all constructions which are not bad --- in particular all the ugly ones --- are secure.
cryptanalysis on hmac/nmac-md5 and md5-mac. in this paper, we present the first distinguishing attack on hmac and nmac based on md5 without related keys, which distinguishes the hmac/nmac-md5 from hmac/nmac with a random function. the attack needs 297 queries, with a success probability 0.87, while the previous distinguishing attack on hmac-md5 reduced to 33 rounds takes 2126.1 messages with a success rate of 0.92. furthermore, we give distinguishing and partial key recovery attacks on mdx-mac based on md5. the mdx-mac was proposed by preneel and van oorschot in crypto'95 which uses three subkeys derived from the initial key. we are able to recover one 128-bit subkey with 297 queries.