waashk/dblp huggingface dataset:
isogenies and the discrete logarithm problem in jacobians of genus 3 hyperelliptic curves. we describe the use of explicit isogenies to translate instances of the discrete logarithm problem from jacobians of hyperelliptic genus 3 curves to jacobians of non-hyperelliptic genus 3 curves, where they are vulnerable to faster index calculus attacks. we provide explicit formulae for isogenies with kernel isomorphic to (z/2z)3 (over an algebraic closure of the base field) for any hyperelliptic genus 3 curve over a field of characteristic not 2 or 3. these isogenies are rational for a positive fraction of all hyperelliptic genus 3 curves defined over a finite field of characteristic p > 3. subject to reasonable assumptions, our constructions give an explicit and efficient reduction of instances of the dlp from hyperelliptic to non-hyperelliptic jacobians for around 18.57% of all hyperelliptic genus 3 curves over a given finite field.
threshold rsa for dynamic and ad-hoc groups. we consider the use of threshold signatures in ad-hoc and dynamic groups such as manets ("mobile ad-hoc networks"). while the known threshold rsa signature schemes have several properties that make them good candidates for deployment in these scenarios, none of these schemes seems practical enough for realistic use in these highly-constrained environments. in particular, this is the case of the most efficient of these threshold rsa schemes, namely, the one due to shoup. our contribution is in presenting variants of shoup's protocol that overcome the limitations that make the original protocol unsuitable for dynamic groups. the resultant schemes provide the efficiency and flexibility needed in ad-hoc groups, and add the capability of incorporating new members (share-holders) to the group of potential signers without relying on central authorities. namely, any threshold of existing members can cooperate to add a new member. the schemes are efficient, fully non-interactive and do not assume broadcast.
on the security of 3gpp networks. later this year we shall see the release of the third generation partnership project (3gpp) specifications for wcdma - the first third generation standard for mobile communications. this 3g system combines elements of both a radical departure and a timid evolution from the 2g system known as gsm. it is radically different from gsm in having a wide-band cdma system for its air-interface, but it hangs on to the gsm/gprs core switching network with its map based signalling system. in this paper we consider the security features in wcdma, taking a critical look at where they depart from those in gsm, where they are still very much the same and how they may develop as the core switching network is replaced by an ip based infrastructure. 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
the twin diffie-hellman problem and applications. we propose a new computational problem called the twin diffie-hellman problem. this problem is closely related to the usual (computational) diffie-hellman problem and can be used in many of the same cryptographic constructions that are based on the diffie-hellman problem. moreover, the twin diffie-hellman problem is at least as hard as the ordinary diffie-hellman problem. however, we are able to show that the twin diffie-hellman problem remains hard, even in the presence of a decision oracle that recognizes solutions to the problem -- this is a feature not enjoyed by the ordinary diffie-hellman problem. in particular, we show how to build a certain "trapdoor test" which allows us to effectively answer such decision oracle queries, without knowing any of the corresponding discrete logarithms. our new techniques have many applications. as one such application, we present a new variant of elgamal encryption with very short ciphertexts, and with a very simple and tight security proof, in the random oracle model, under the assumption that the ordinary diffie-hellman problem is hard. we present several other applications as well, including: a new variant of diffie and hellman's non-interactive key exchange protocol; a new variant of cramer-shoup encryption, with a very simple proof in the standard model; a new variant of boneh-franklin identity-based encryption, with very short ciphertexts; a more robust version of a password-authenticated key exchange protocol of abdalla and pointcheval.
new constructions for uc secure computation using tamper-proof hardware. the universal composability framework was introduced by canetti to study the security of protocols which are concurrently executed with other protocols in a network environment. unfortunately it was shown that in the so called plain model, a large class of functionalities cannot be securely realized. these severe impossibility results motivated the study of other models involving some sort of setup assumptions, where general positive results can be obtained. until recently, all the setup assumptions which were proposed required some trusted third party (or parties). katz recently proposed using a physical setup to avoid such trusted setup assumptions. in his model, the physical setup phase includes the parties exchanging tamper proof hardware tokens implementing some functionality. the tamper proof hardware is modeled so as to assume that the receiver of the token can do nothing more than observe its input/output characteristics. it is further assumed that the sender knows the program code of the hardware token which it distributed. based on the ddh assumption, katz gave general positive results for universally composable multi-party computation tolerating any number of dishonest parties making this model quite attractive. in this paper, we present new constructions for uc secure computation using tamper proof hardware (in a stronger model). our results represent an improvement over the results of katz in several directions using substantially different techniques. interestingly, our security proofs do not rely on being able to rewind the hardware tokens created by malicious parties. this means that we are able to relax the assumptions that the parties know the code of the hardware token which they distributed. this allows us to model real life attacks where, for example, a party may simply pass on the token obtained from one party to the other without actually knowing its functionality. furthermore, our construction models the interaction with the tamper-resistant hardware as a simple request-reply protocol. thus, we show that the hardware tokens used in our construction can be resettable. in fact, it suffices to use token which are completely stateless (and thus cannot execute a multiround protocol). our protocol is also based on general assumptions (namely enhanced trapdoor permutations).
secure communication in broadcast channels: the answer to franklin and wright's question. problems of secure communication and computation have been studied extensively in network models. goldreich, goldwasser, and linial, franklin and yung, and franklin and wright have initiated the study of secure communication and secure computation in multirecipient (broadcast) models. a "broadcast channel" (such as ethernet) enables one processor to send the same message--simultaneously and privately-- to a fixed subset of processors. in their eurocrypt '98 paper, franklin and wright have shown that if there are n broadcast lines between a sender and a receiver and there are at most t malicious (byzantine style) processors, then the condition n > t is necessary and sufficient for achieving efficient probabilisticly reliable and probabilisticly private communication. they also showed that if n > ⌈3t/2⌉ then there is an efficient protocol to achieve probabilisticly reliable and perfectly private communication. and they left open the question whether there exists an efficient protocol to achieve probabilisticly reliable and perfectly private communication when ⌈3t/2⌉ ≥ n > t. in this paper, by using a different authentication scheme, we will answer this question affirmatively and study related problems.
predicate encryption supporting disjunctions, polynomial equations, and inner products. predicate encryption is a new paradigm generalizing, among other things, identity-based encryption. in a predicate encryption scheme, secret keys correspond to predicates and ciphertexts are associated with attributes; the secret key skf corresponding to a predicate f can be used to decrypt a ciphertext associated with attribute i if and only if f(i) = 1. constructions of such schemes are currently known for relatively few classes of predicates. we construct such a scheme for predicates corresponding to the evaluation of inner products over zn (for some large integer n). this, in turn, enables constructions in which predicates correspond to the evaluation of disjunctions, polynomials, cnf/dnf formulae, or threshold predicates (among others). besides serving as a significant step forward in the theory of predicate encryption, our results lead to a number of applications that are interesting in their own right.
on the matsumoto and imai's human identification scheme. at eurocrypt'91, matsumoto and imai presented a human identification scheme for insecure channels, which is suitable for human ability of memorizing and processing a short secret. it prevents an intruder from peeping user in typing password on terminal connected to the central computer. however, in this paper, we are going to propose a new attack, called the replay challenge attack, where a malicious terminal pretends to be the host and replays the host's challenges to reveal the secret password. a modified scheme will be proposed to avoid this attack.
obfuscating point functions with multibit output. we construct obfuscators of point functions with multibit output and other related functions. a point function with multibit output returns a fixed string on a single input point and zero everywhere else. obfuscation of such functions has a useful application as a strong form of symmetric encryption which guarantees security even when the key has very low entropy: essentially, learning information about the plaintext is paramount to finding the key via exhaustive search on the key space. although the constructions appear to be simple and modular, their analysis turns out to be quite intricate. in particular, we uncover some weaknesses in the current definitions of obfuscation. one weakness is that current definitions do not guarantee security even under very weak forms of composition. we thus define a notion of obfuscation that is preserved under an appropriate composition operation. the constructions can use any obfuscator of point functions under the proposed definition. alternatively, they can use perfect one way (pow) functions with statistical indistinguishability, or with computational indistinguishability at the price of somewhat weaker security.
efficient non-interactive proof systems for bilinear groups. non-interactive zero-knowledge proofs and non-interactive witnessindistinguishable proofs have played a significant role in the theory of cryptography. however, lack of efficiency has prevented them from being used in practice. one of the roots of this inefficiency is that non-interactive zeroknowledge proofs have been constructed for general np-complete languages such as circuit satisfiability, causing an expensive blowup in the size of the statement when reducing it to a circuit. the contribution of this paper is a general methodology for constructing very simple and efficient non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs that work directly for groups with a bilinear map, without needing a reduction to circuit satisfiability. groups with bilinear maps have enjoyed tremendous success in the field of cryptography in recent years and have been used to construct a plethora of protocols. this paper provides non-interactive witness-indistinguishable proofs and non-interactive zero-knowledge proofs that can be used in connection with these protocols. our goal is to spread the use of non-interactive cryptographic proofs from mainly theoretical purposes to the large class of practical cryptographic protocols based on bilinear groups.
almost-everywhere secure computation. secure multi-party computation (mpc) is a central problem in cryptography. unfortunately, it is well known that mpc is possible if and only if the underlying communication network has very large connectivity -- in fact, ω(t), where t is the number of potential corruptions in the network. this impossibility result renders existing mpc results far less applicable in practice, since many deployed networks have in fact a very small degree. in this paper, we show how to circumvent this impossibility result and achieve meaningful security guarantees for graphs with small degree (such as expander graphs and several other topologies). in fact, the notion we introduce, which we call almost-everywhere mpc, building on the notion of almost-everywhere agreement due to dwork, peleg, pippenger and upfal, allows the degree of the network to be much smaller than the total number of allowed corruptions. in essence, our definition allows the adversary to implicitly wiretap some of the good nodes by corrupting sufficiently many nodes in the "neighborhood" of those nodes. we show protocols that satisfy our new definition, retaining both correctness and privacy for most nodes despite small connectivity, no matter how the adversary chooses his corruptions. instrumental in our constructions is a new model and protocol for the secure message transmission (smt) problem, which we call smt by public discussion, and which we use for the establishment of pairwise secure channels in limited connectivity networks.
collisions for the lps expander graph hash function. we analyse the hash function family based on walks in lps ramanujan graphs recently introduced by charles et al. we present an algorithm for finding collisions that runs in quasi-linear time in the length of the hashed value. a concrete instance of the hash function is considered, based on a 100-digit prime. a short collision is given, together with implementation details.
second preimage attacks on dithered hash functions. we develop a new generic long-message second preimage attack, based on combining the techniques in the second preimage attacks of dean [8] and kelsey and schneier [16] with the herding attack of kelsey and kohno [15]. we show that these generic attacks apply to hash functions using the merkle-damgård construction with only slightly more work than the previously known attack, but allow enormously more control of the contents of the second preimage found. additionally, we show that our new attack applies to several hash function constructions which are not vulnerable to the previously known attack, including the dithered hash proposal of rivest [25], shoup's uowhf[26] and the rox hash construction [2].we analyze the properties of the dithering sequence used in [25], and develop a time-memory tradeoff which allows us to apply our second preimage attack to a wide range of dithering sequences, including sequences which are much stronger than those in rivest's proposals. finally, we show that both the existing second preimage attacks [8,16] and our new attack can be applied even more efficiently to multiple target messages; in general, given a set of many target messages with a total of 2r message blocks, these second preimage attacks can find a second preimage for one of those target messages with no more work than would be necessary to find a second preimage for a single target message of 2r message blocks.
an implementation of the general number field sieve to compute discrete logarithms mod p. there are many cryptographic protocols the security of which depends on the difficulty of solving the discrete logarithm problem ([8], [9], [14], etc.). in [10] and [18] it was described how to apply the number field sieve algorithm to the discrete logarithm problem in prime fields. this resulted in the asymptotically fastest known discrete log algorithm for finite fields of p elements. very little is known about the behaviour of this algorithm in practice. in this report we write about our practical experience with our implementation of their algorithm whose first version was completed in october 1994 at the department of computer science at the universität des saarlandes.
a leakage-resilient mode of operation. a weak pseudorandom function (wprf) is a cryptographic primitive similar to --- but weaker than --- a pseudorandom function: for wprfs one only requires that the output is pseudorandom when queried on random inputs. we show that unlike "normal" prfs, wprfs are seed-incompressible, in the sense that the output of a wprf is pseudorandom even if a bounded amount of information about the key is leaked.as an application of this result we construct a simple mode of operation which --- when instantiated with any wprf --- gives a leakage-resilient stream-cipher. the implementation of such a cipher is secure against every side-channel attack, as long as the amount of information leaked per round is bounded, but overall can be arbitrary large. the construction is simpler than the previous one (dziembowski-pietrzak focs'08) as it only uses a single primitive (a wprf) in a straight forward manner.
key recovery on hidden monomial multivariate schemes. in this paper, we study the key recovery problem for the c* scheme and generalisations where the quadratic monomial of c* (the product of two linearized monomials) is replaced by a product of three or more linearized monomials. this problem has been further generalized to any system of multivariate polynomials hidden by two invertible linear maps and named the isomorphism of polynomials (ip) problem by patarin. some cryptosystems have been built on this apparently hard problem such as an authentication protocol proposed by patarin and a traitor tracing scheme proposed by billet and gilbert. here we show that if the hidden multivariate system is the projection of a quadratic monomial on a base finite field, as in c*, or a cubic (or higher) monomial as in the traitor tracing scheme, then it is possible to recover an equivalent secret key in polynomial time o(nd) where n is the number of variables and d is the degree of the public polynomials.
the one-round functions of the des generate the alternating group. in each of the 16 des rounds we have a permutation of 64-bitblocks. according to the corresponding key-block there are 248 possible permutations per round. in this paper we will prove that these permutations generate the alternating group. the main parts of the paper are the proof that the generated group is 3-transitive, and the application of a result from p. j. cameron based on the classification of finite simple groups. a corollary concerning n-round functions generalizes the result.
david and goliath commitments: uc computation for asymmetric parties using tamper-proof hardware. designing secure protocols in the universal composability (uc) framework confers many advantages. in particular, it allows the protocols to be securely used as building blocks in more complex protocols, and assists in understanding their security properties. unfortunately, most existing models in which universally composable computation is possible (for useful functionalities) require a trusted setup stage. recently, katz [eurocrypt '07] proposed an alternative to the trusted setup assumption: tamper-proof hardware. instead of trusting a third party to correctly generate the setup information, each party can create its own hardware tokens, which it sends to the other parties. each party is only required to trust that its own tokens are tamper-proof. katz designed a uc commitment protocol that requires both parties to generate hardware tokens. in addition, his protocol relies on a specific number-theoretic assumption. in this paper, we construct uc commitment protocols for "david" and "goliath": we only require a single party (goliath) to be capable of generating tokens. we construct a version of the protocol that is secure for computationally unbounded parties, and a more efficient version that makes computational assumptions only about david (we require only the existence of a one-way function). our protocols are simple enough to be performed by hand on david's side. these properties may allow such protocols to be used in situations which are inherently asymmetric in real-life, especially those involving individuals versus large organizations. classic examples include voting protocols (voters versus "the government") and protocols involving private medical data (patients versus insurance-agencies or hospitals).
towards key-dependent message security in the standard model. standard security notions for encryption schemes do not guarantee any security if the encrypted messages depend on the secret key. yet it is exactly the stronger notion of security in the presence of key-dependent messages (kdm security) that is required in a number of applications: most prominently, kdm security plays an important role in analyzing cryptographic multi-party protocols in a formal calculus. but although often assumed, the mere existence of kdm secure schemes is an open problem. the only previously known construction was proven secure in the random oracle model. we present symmetric encryption schemes that are kdm secure in the standard model (i.e., without random oracles). the price we pay is that we achieve only a relaxed (but still useful) notion of key-dependent message security. our work answers (at least partially) an open problem posed by black, rogaway, and shrimpton. more concretely, our contributions are as follows: 1. we present a (stateless) symmetric encryption scheme that is information-theoretically secure in face of a bounded number and length of encryptions for which the messages depend in an arbitrary way on the secret key. 2. we present a stateful symmetric encryption scheme that is computationally secure in face of an arbitrary number of encryptions for which the messages depend only on the respective current secret state/key of the scheme. the underlying computational assumption is minimal: we assume the existence of one-way functions. 3. we give evidence that the only previously known kdm secure encryption scheme cannot be proven secure in the standard model (i.e., without random oracles).
security/efficiency tradeoffs for permutation-based hashing. we provide attacks and analysis that capture a tradeoff, in the ideal-permutation model, between the speed of a permutation-based hash function and its potential security. we show that any 2n-bit to n-bit compression function will have unacceptable collision resistance it makes fewer than three n-bit permutation invocations, and any 3n-bit to 2n-bit compression function will have unacceptable security if it makes fewer than five n-bit permutation invocations. any rate-a hash function built from n-bit permutations can be broken, in the sense of finding preimages as well as collisions, in about n1-α queries, where n = 2n. our results provide guidance when trying to design or analyze a permutation-based hash function about the limits of what can possibly be done.