waashk/dblp huggingface dataset:
smashing squash-0. at the rfid security workshop 2007, adi shamir presented a new challenge-response protocol well suited for rfids, although based on the rabin public-key cryptosystem. this protocol, which we call squash-0, was using a linear mixing function which was subsequently withdrawn. essentially, we mount an attack against squash-0 with full window which could be used as a "known random coins attack" against rabin-saep. we then extend it for squash-0 with arbitrary window. we apply it with the proposed modulus 21 277¿ 1 to run a key recovery attack using 1 024 chosen challenges. since the security arguments equally apply to the final version of squash and to squash-0, we challenge the blame-game argument for the security of squash. nevertheless, our attacks are inefficient when using non-linear mixing so the security of squash remains open.
conditional computational entropy, or toward separating pseudoentropy from compressibility. we study conditional computational entropy: the amount of randomness a distribution appears to have to a computationally bounded observer who is given some correlated information. by considering conditional versions of hill entropy (based on indistinguishability from truly random distributions) and yao entropy (based on incompressibility), we obtain: a separation between conditional hill and yao entropies (which can be viewed as a separation between the traditional hill and yao entropies in the shared random string model, improving on wee's 2004 separation in the random oracle model); the first demonstration of a distribution from which extraction techniques based on yao entropy produce more pseudorandom bits than appears possible by the traditional hill-entropy-based techniques; a new, natural notion of unpredictability entropy, which implies conditional yao entropy and thus allows for known extraction and hardcore bit results to be stated and used more generally.
revisiting the efficiency of malicious two-party computation. in a recent paper mohassel and franklin study the efficiency of secure two-party computation in the presence of malicious behavior. their aim is to make classical solutions to this problem, such as zero-knowledge compilation, more efficient. the authors provide several schemes which are the most efficient to date. we propose a modification to their main scheme using expanders. our modification asymptotically improves at least one measure of efficiency of all known schemes. we also point out an error, and improve the analysis of one of their schemes.
a new mode of operation for block ciphers and length-preserving macs. we propose a new mode of operation, enciphered cbc, for domain extension of length-preserving functions (like block ciphers), which is a variation on the popular cbc mode of operation. our new mode is twice slower than cbc, but has many (property-preserving) properties not enjoyed by cbc and other known modes. most notably, it yields the first constant-rate variable input length (vil) mac from any length preserving fixed input length (fil) mac. this answers the question of dodis and puniya from eurocrypt 2007. further, our mode is a secure domain extender for prfs (with basically the same security as encrypted cbc). this provides a hedge against the security of the block cipher: if the block cipher is pseudorandom, one gets a vil-prf, while if it is "only" unpredictable, one "at least" gets a vil-mac. additionally, our mode yields a vil random oracle (and, hence, a collision-resistant hash function) when instantiated with length-preserving random functions, or even random permutations (which can be queried from both sides). this means that one does not have to re-key the block cipher during the computation, which was critically used in most previous constructions (analyzed in the ideal cipher model).
cryptanalysis of the sidelnikov cryptosystem. we present a structural attack against the sidelnikov cryptosystem [8]. the attack creates a private key from a given public key. its running time is subexponential and is effective if the parameters of the reed-muller code allow for efficient sampling of minimum weight codewords. for example, the length 2048, 3rd-order reed-muller code as proposed in [8] takes roughly an hour to break on a stock pc using the presented method.
simulation without the artificial abort: simplified proof and improved concrete security for waters' ibe scheme. waters' variant of the boneh-boyen ibe scheme is attractive because of its efficency, applications, and security attributes, but suffers from a relatively complex proof with poor concrete security. this is due in part to the proof's "artificial abort" step, which has then been inherited by numerous derivative works. it has often been asked whether this step is necessary.we show that it is not, providing a new proof that eliminates this step. the new proof is not only simpler than the original one but offers better concrete security for important ranges of the parameters. as a result, one can securely use smaller groups, resulting in significant efficiency improvements.
instance-dependent verifiable random functions and their application to simultaneous resettability. we introduce a notion of instance-dependent verifiable random functions (instd-vrfs for short). informally, an instd-vrf is, in some sense, a verifiable random function [23] with a special public key, which is generated via a (possibly)interactive protocol and contains an instance y ¿ l ¿ {0,1}* for a specific np language l, but the security requirements on such a function are relaxed: we only require the pseudorandomness property when y ¿ l and only require the uniqueness property when y ¿ l, instead of requiring both pseudorandomness and uniqueness to hold simultaneously. we show that this notion can be realized under standard assumption.our motivation is the conjecture posed by barak et al.[2], which states there exist resettably-sound resettable zero knowledge arguments for np. the instance-dependent verifiable random functions is a powerful tool to tackle this problem. we first use them to obtain two interesting instance-dependent argument systems from the barak's public-coin bounded concurrent zero knowledge argument [1], and then, we 1 construct the first (constant round) zero knowledge arguments for np enjoying a certain simultaneous resettability under standard hardness assumptions in the plain model, which we call bounded-class resettable zk arguments with weak resettable-soundness though the malicious party (prover or verifier) in such system is limited to a kind of bounded resetting attack, we put no restrictions on the number of the total resets made by malicious party. 1 show that, under standard assumptions, if there exist public-coin concurrent zero knowledge arguments for np, there exist the resettably-sound resetable zero knowledge arguments for np.
a public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks. recently, at crypto 2008, boneh, halevi, hamburg, and ostrovsky (bhho) solved the long-standing open problem of "circular encryption," by presenting a public key encryption scheme and proving that it is semantically secure against key dependent chosen plaintext attack (kdm-cpa security) under standard assumptions (and without resorting to random oracles). however, they left as an open problem that of designing an encryption scheme that simultaneously provides security against both key dependent chosen plaintext and adaptive chosen ciphertext attack (kdm-cca2 security). in this paper, we solve this problem. first, we show that by applying the naor-yung "double encryption" paradigm, one can combine any kdm-cpa secure scheme with any (ordinary) cca2 secure scheme, along with an appropriate non-interactive zero-knowledge proof, to obtain a kdm-cca2 secure scheme. second, we give a concrete instantiation that makes use the above kdm-cpa secure scheme of bhho, along with a generalization of the cramer-shoup cca2 secure encryption scheme, and recently developed pairing-based nizk proof systems. this instantiation increases the complexity of the bhho scheme by just a small constant factor.
toward a rigorous variation of coppersmith's algorithm on three variables. in 1996, coppersmith introduced two lattice reduction based techniques to find small roots in polynomial equations. one technique works for modular univariate polynomials, the other for bivariate polynomials over the integers. since then, these methods have been used in a huge variety of cryptanalytic applications. some applications also use extensions of coppersmith's techniques on more variables. however, these extensions are heuristic methods. in the present paper, we present and analyze a new variation of coppersmith's algorithm on three variables over the integers. we also study the applicability of our method to short rsa exponents attacks. in addition to lattice reduction techniques, our method also uses gröbner bases computations. moreover, at least in principle, it can be generalized to four or more variables.
a new randomness extraction paradigm for hybrid encryption. we present a new approach to the design of ind-cca2 secure hybrid encryption schemes in the standard model. our approach provides an efficient generic transformation from 1-universal to 2-universal hash proof systems. the transformation involves a randomness extractor based on a 4-wise independent hash function as the key derivation function. our methodology can be instantiated with efficient schemes based on standard intractability assumptions such as decisional diffie-hellman, quadratic residuosity, and paillier's decisional composite residuosity. interestingly, our framework also allows to prove ind-cca2 security of a hybrid version of 1991's damgård's elgamal public-key encryption scheme under the ddh assumption.
mesh signatures. we define the mesh signature primitive as an anonymous signature similar in spirit to ring signatures, but with a much richer language for expressing signer ambiguity. the language can represent complex access structures, and in particular allows individual signature components to be replaced with complete certificate chains. because withholding one's public key from view is no longer a shield against being named as a possible cosignatory, mesh signatures may be used as a ring signature with compulsory enrollment.we give an efficient construction based on bilinear maps in the common random string model. our signatures have linear size, achieve everlasting perfect anonymity, and reduce to very efficient ring signatures without random oracles as a special case. we prove non-repudiation from a mild extension of the sdh assumption, which we introduce and justify meticulously.
on the portability of generalized schnorr proofs. the notion of zero knowledge proofs (of knowledge) [zkp] is central to cryptography; it provides a set of security properties that proved indispensable in concrete protocol design. these properties are defined for any given input and also for any auxiliary verifier private state, as they are aimed at any use of the protocol as a subroutine in a bigger application. many times, however, moving the theoretical notion to practical designs has been quite problematic. this is due to the fact that the most efficient protocols fail to provide the above zkp properties for all possible inputs and verifier states. this situation has created various problems to protocol designers who have often either introduced imperfect protocols with mistakes or with lack of security arguments, or they have been forced to use much less efficient protocols in order to achieve the required properties. in this work we address this issue by introducing the notion of "protocol portability," a property that identifies input and verifier state distributions under which a protocol becomes a zkp when called as a subroutine in a sequential execution of a larger application. we then concentrate on the very efficient and heavily employed "generalized schnorr proofs" (gsp) and identify the portability of such protocols. we also point to previous protocol weaknesses and errors that have been made in numerous applications throughout the years, due to employment of gsp instances while lacking the notion of portability (primarily in the case of unknown order groups). this demonstrates that cryptographic application designers who care about efficiency need to consider our notion carefully. we provide a compact specification language for gsp protocols that protocol designers can employ. our specification language is consistent with the ad-hoc notation that is currently widely used and it offers automatic derivation of the proof protocol while dictating its portability (i.e., the proper initial state and inputs) and its security guarantees. finally, as a second alternative to designers wishing to use gsps, we present a modification of gsp protocols that is unconditionally portable (i.e., zkp) and is still quite efficient. our constructions are the first such protocols proven secure in the standard model (as opposed to the random oracle model).
general encryption from exponent inversion ibe. among the three broad classes of identity-based encryption schemes built from pairings, the exponent inversion paradigm tends to be the most efficient, but also the least extensible: currently there are no hierarchical or other known extension of ibe based on those schemes. in this work, we show that such extensions can be realized from ibe systems that conform to a certain abstraction of the exponent inversion paradigm. our method requires no random oracles, and is simple and efficient.
a double-piped mode of operation for macs, prfs and pros: security beyond the birthday barrier. we revisit the double-pipe construction introduced by lucks at asiacrypt 2005. lucks originally studied the construction for iterated hash functions and showed that the approach is effective in improving security against various types of collision and (second-)preimage attacks. instead, in this paper we apply the construction to the secret-key setting, where the underlying fil (fixed-input-length) compression function is equipped with a dedicated key input. we make some adjustments to lucks' original design so that now the new mode works with a single key and operates as a multi-property-preserving domain extension of macs (message authentication codes), prfs (pseudo-random functions) and pros (pseudo-random oracles). though more than twice as slow as the merkle-damgård construction, the double-piped mode enjoys security strengthened beyond the birthday bound, most notably, high mac security. more specifically, when iterating an fil-mac whose output size is n-bit, the new double-piped mode yields an ail-(arbitrary-input-length-)mac with security up to $o\bigl(2^{5n/6}\bigr)$ query complexity. this bound contrasts sharply with the birthday bound of $o\bigl(2^{n/2}\bigr)$, which has been the best mac security accomplished by earlier constructions.
batch verification of short signatures. with computer networks spreading into a variety of new environments, the need to authenticate and secure communication grows. many of these new environments have particular requirements on the applicable cryptographic primitives. for instance, several applications require that communication overhead be small and that many messages be processed at the same time. in this paper we consider the suitability of public key signatures in the latter scenario. that is, we consider signatures that are 1) short and 2) where many signatures from (possibly) different signers on (possibly) different messages can be verified quickly.we propose the first batch verifier for messages from many (certified) signers without random oracles and with a verification time where the dominant operation is independent of the number of signatures to verify. we further propose a new signature scheme with very short signatures, for which batch verification for many signers is also highly efficient. prior work focused almost exclusively on batching signatures from the same signer. combining our new signatures with the best known techniques for batching certificates from the same authority, we get a fast batch verifier for certificates and messages combined. although our new signature scheme has some restrictions, it is the only solution, to our knowledge, that is a candidate for some pervasive communication applications.
traitors collaborating in public: pirates 2.0. this work introduces a new concept of attack against traitor tracing schemes. we call attacks of this type pirates 2.0 attacks as they result from traitors collaborating together in a public way. in other words, traitors do not secretly collude but display part of their secret keys in a public place; pirate decoders are then built from this public information. the distinguishing property of pirates 2.0 attacks is that traitors only contribute partial information about their secret key material which suffices to produce (possibly imperfect) pirate decoders while allowing them to remain anonymous. the side-effect is that traitors can publish their contributed information without the risk of being traced; giving such strong incentives to some of the legitimate users to become traitors allows coalitions to attain very large sizes that were deemed unrealistic in some previously considered models of coalitions.this paper proposes a generic model for this new threat, that we use to assess the security of some of the most famous traitor tracing schemes. we exhibit several pirates 2.0 attacks against these schemes, providing new theoretical insights with respect to their security. we also describe practical attacks against various instances of these schemes. eventually, we discuss possible variations on the pirates 2.0 theme.
simulatable adaptive oblivious transfer. we study an adaptive variant of oblivious transfer in which a sender has n messages, of which a receiver can adaptively choose to receive k one-after-the-other, in such a way that (a) the sender learns nothing about the receiver's selections, and (b) the receiver only learns about the k requested messages. we propose two practical protocols for this primitive that achieve a stronger security notion than previous schemes with comparable efficiency. in particular, by requiring full simulatability for both sender and receiver security, our notion prohibits a subtle selective-failure attack not addressed by the security notions achieved by previous practical schemes.our first protocol is a very efficient generic construction from unique blind signatures in the random oracle model. the second construction does not assume random oracles, but achieves remarkable efficiency with only a constant number of group elements sent during each transfer. this second construction uses novel techniques for building efficient simulatable protocols.
truly efficient 2-round perfectly secure message transmission scheme. in themodel of perfectly securemessage transmission schemes (psmts), there are n channels between a sender and a receiver. an infinitely powerful adversary a may corrupt (observe and forge) the messages sent through t out of n channels. the sender wishes to send a secret s to the receiver perfectly privately and perfectly reliably without sharing any key with the receiver. in this paper, we show the first 2-round psmt for n = 2t + 1 such that not only the transmission rate is o(n) but also the computational costs of the sender and the receiver are both polynomial in n. this means that we solve the open problem raised by agarwal, cramer and de haan at crypto 2006.
on randomizing hash functions to strengthen the security of digital signatures. halevi and krawczyk proposed a message randomization algorithm called rmx as a front-end tool to the hash-then-sign digital signature schemes such as dss and rsa in order to free their reliance on the collision resistance property of the hash functions. they have shown that to forge a rmx-hash-then-sign signature scheme, one has to solve a cryptanalytical task which is related to finding second preimages for the hash function. in this article, we will show how to use dean's method of finding expandable messages for finding a second preimage in the merkle-damgård hash function to existentially forge a signature scheme based on a t-bit rmx-hash function which uses the davies-meyer compression functions (e.g., md4, md5, sha family) in 2 t/2 chosen messages plus 2 t/2 + 1 off-line operations of the compression function and similar amount of memory. this forgery attack also works on the signature schemes that use davies-meyer schemes and a variant of rmx published by nist in its draft special publication (sp) 800-106. we discuss some important applications of our attack.
practical chosen ciphertext secure encryption from factoring. we propose a practical public-key encryption scheme whose security against chosen-ciphertext attacks can be reduced in the standard model to the assumption that factoring is intractable.
key agreement from close secrets over unsecured channels. we consider information-theoretic key agreement between two parties sharing somewhat different versions of a secret w that has relatively little entropy. such key agreement, also known as information reconciliation and privacy amplification over unsecured channels, was shown to be theoretically feasible by renner and wolf (eurocrypt 2004), although no protocol that runs in polynomial time was described. we propose a protocol that is not only polynomial-time, but actually practical, requiring only a few seconds on consumer-grade computers.our protocol can be seen as an interactive version of robust fuzzy extractors (dodis et al., crypto 2006). while robust fuzzy extractors, due to their noninteractive nature, require w to have entropy at least half its length, we have no such constraint. in fact, unlike in prior solutions, in our solution the entropy loss is essentially unrelated to the length or the entropy of w, and depends only on the security parameter.
generating genus two hyperelliptic curves over large characteristic finite fields. in hyperelliptic curve cryptography, finding a suitable hyperelliptic curve is an important fundamental problem. one of necessary conditions is that the order of its jacobian is a product of a large prime number and a small number. in the paper, we give a probabilistic polynomial time algorithm to test whether the jacobian of the given hyperelliptic curve of the form y 2 = x 5 + u x 3 + v x satisfies the condition and, if so, to give the largest prime factor. our algorithm enables us to generate random curves of the form until the order of its jacobian is almost prime in the above sense. a key idea is to obtain candidates of its zeta function over the base field from its zeta function over the extension field where the jacobian splits.
verifiable random functions from identity-based key encapsulation. we propose a methodology to construct verifiable random functions from a class of identity based key encapsulation mechanisms (ib-kem) that we call vrf suitable. informally, an ib-kem is vrf suitable if it provides what we call unique decryption (i.e. given a ciphertext c produced with respect to an identity ${\it{id}}$, all the secret keys corresponding to identity ${\it{id}}'$, decrypt to the same value, even if ${\it{id}}\neq {\it{id}}'$) and it satisfies an additional property that we call pseudorandom decapsulation. in a nutshell, pseudorandom decapsulation means that if one decrypts a ciphertext c, produced with respect to an identity ${\it{id}}$, using the decryption key corresponding to any other identity ${\it{id}}'$ the resulting value looks random to a polynomially bounded observer. interestingly, we show that most known ib-kems already achieve pseudorandom decapsulation. our construction is of interest both from a theoretical and a practical perspective. indeed, apart from establishing a connection between two seemingly unrelated primitives, our methodology is direct in the sense that, in contrast to most previous constructions, it avoids the inefficient goldreich-levin hardcore bit transformation.