waashk/dblp huggingface dataset:
the gchq protocol and its problems. the uk government is fielding an architecture for secure electronic mail based on the nsa's message security protocol, with a key escrow scheme inspired by diffie-hellman. attempts have been made to have this protocol adopted by other governments and in various domestic applications. the declared policy goal is to entrench commercial key escrow while simultaneously creating a large enough market that software houses will support the protocol as a standard feature rather than charging extra for it. we describe this protocol and show that, like the 'clipper' proposal of a few years ago, it has a number of problems. it provides the worst of both secret and public key systems, without delivering the advantages of either; it does not support nonrepudiation; and there are serious problems with the replacement of compromised keys, the protection of security labels, and the support of complex or dynamic administrative structures.
perfect and essentially perfect authentication schemes. suppose that a wants to send a message m to b. it is important that b receives the message without any alteration. on the other hand, a bad guy x looks for his chance to alter m in his favour. in order t o make the bad guy's life difficult, a authenticates the message m. for this, a and b have to agree on an authentication function f and a secret key k. the function f has m and k as its input, and the authenticator (also called message authentication code) f(m,k) as its output.
a public key encryption scheme based on the polynomial reconstruction problem. the polynomial reconstruction problem (pr) has been introduced in 1999 as a new hard problem. several cryptographic primitives established on this problem have been constructed, for instance naor and pinkas have proposed a protocol for oblivious polynomial evaluation. then it has been studied from the point of view of robustness, and several important properties have been discovered and proved by kiayias and yung. furthermore the same authors constructed a symmetric cipher based on the pr problem. in the present paper, we use the published security results and construct a new public key encryption scheme based on the hardness of the problem of polynomial reconstruction. the scheme presented is the first public key encryption scheme based on this polynomial reconstruction problem. we also present some attacks, discuss their performances and state the size of the parameters required to reach the desired security level. in conclusion, this leads to a cryptosystem where the cost of encryption and decryption per bit is low, and where the public key is kept relatively small.
a² codes from universal hash classes. we describe a general method to construct codes for unconditional authentication with arbitration (a2-codes), which protect not only against outside opponents but also against certain types of frauds from the receiver and transmitter. the constructions are based on orthogonal arrays and universal hash classes. the idea is to construct a2-codes out of pairs of a-codes. the hitherto known examples are special cases of the construction. along the way we also construct new universal hash classes.
uniform results in polynomial-time security. most security results can be established both in the non-uniform and the uniform model of computation. nonetheless, non-uniform results are often much easier to obtain than their uniform version. in this paper we initiate a general framework in which the classical sampling technique can be applied to obtain uniform results. our main theorem gives sufficient conditions under which a non-uniform result can be extended to a uniform one. as a consequence, we derive the uniform version of schrift and shamir's generalization of yao's theorem on the universality of the next-bit test.
tools for proving zero knowledge. we develop general techniques that can be used to prove the zero knowledge property of most of the known zero knowledge protocols. those techniques consist in reducing the circuit indistinguishability of the output distributions of two probabilistic turing machines to the indistinguishability of the output distributions of certain subroutines.
collision-free accumulators and fail-stop signature schemes without trees. one-way accumulators, introduced by benaloh and de mare, can be used to accumulate a large number of values into a single one, which can then be used to authenticate every input value without the need to transmit the others. however, the one-way property does is not sufficient for all applications. in this paper, we generalize the definition of accumulators and define and construct a collision-free subtype. as an application, we construct a fail-stop signature scheme in which many one-time public keys are accumulated into one short public key. in contrast to previous constructions with tree authentication, the length of both this public key and the signatures can be independent of the number of messages that can be signed.
cryptanalysis of patarin's 2-round public key system with s boxes (2r). in a series of papers patarin proposes new efficient public key systems. a very interesting proposal, called 2-round public key system with s boxes, or 2r, is based on the difficulty of decomposing the structure of several rounds of unknown linear transformations and s boxes. this difficulty is due to the difficulty of decomposing compositions of multivariate binary functions. in this paper we present a novel attack which breaks the 64-bit block variant with complexity about 230 steps, and the more secure 128-bit blocks variant with complexity about 260 steps. it is interesting to note that this cryptanalysis uses only the ciphertexts of selected plaintexts, and does not analyze the details of the supplied encryption code.
cryptoanalysis of the chaotic-map cryptosystem suggested at eurocrypt'91. in this conference, habutsu[1] suggested a cryptosystem based on iterating a chaotic map. in this paper several properties of this cryptosystem are studied and two cryptanalytic attacks are described.
cryptology - methods and maxims. this paper gives a survey of classical cryptographic methods and of the maxims to their proper use in order to resist illegitimate decryption, as a basis for an understanding of modern commercial, computer-based cryptographic systems and for a critical analysis of those.
cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. in this paper we present a new cryptanalytic technique, based on impossible differentials, and use it to show that skipjack reduced from 32 to 31 rounds can be broken by an attack which is faster than exhaustive search.
minimal-latency secure function evaluation. sander, young and yung recently exhibited a protocol for computing on encrypted inputs, for functions computable in nc1. in their variant of secure function evaluation, bob (the "cryptocomputer") accepts homomorphically-encrypted inputs (x) from client alice, and then returns a string from which alice can extract f(x; y) (where y is bob's input, or e.g. the function f itself). alice must not learn more about y than what f(x; y) reveals by itself. we extend their result to encompass nlogspace (nondeterministic log-space functions). in the domain of multiparty computations, constant-round protocols have been known for years [bb89,fkn95]. this paper introduces novel parallelization techniques that, coupled with the [syy99] methods, reduce the constant to 1 with preprocessing. this resolves the conjecture that nlogspace subcomputations (including log-slices of circuit computation) can be evaluated with latency 1 (as opposed to just o(1)).
how to break a "secure" oblivious transfer protocol. we show how to break a protocol for oblivious transfer presented at eurocrypt 90 [11]. armed with a new set of definitions for proving the security of interactive computations, we found difficulties in proving the protocol secure. these difficulties led us to a simple attack that breaks the ot protocol in a subtle but fundamental way. the error that we found may be present in a wide variety of secure protocols. it reveals a fundamental flaw in the traditional definition of oblivious transfer itself.
equivocable oblivious transfer. we analyze and enhance oblivious transfer (ot) protocols to accommodate security against adaptive attacks. previous analysis has been static in nature, treating the security of alice and the security of bob as separate cases, determined in advance. it remains unclear whether existing protocols are provably secure against adaptive attacks, but we provide enhancements to make them provably secure against attacks by adaptive 1-adversaries, who can choose at any time whether to corrupt alice or bob. we determine circumstances under which ot can be executed "in the open," without encrypting the messages, thereby giving simple alternatives to encrypting an entire interaction. we isolate equivocation properties that provide enough flexibility for a simulator to handle adaptive attacks. these properties also provide a means for classifying ot protocols and understanding the subtle demands of security against adaptive adversaries, as well as designing protocols that can be proven secure against adaptive attacks.
differential cryptoanalysis of feal and n-hash. in [1,2] we introduced the notion of differential cryptanalysis and described its application to des[8] and several of its variants. in this paper we show the applicability of differential cryptanalysis to the feal family of encryption algorithms and to the n-hash hash function.
cryptographic protocols provably secure against dynamic adversaries. we introduce new techniques for generating and reasoning about protocols. these techniques are based on protocol transformations that depend on the nature of the adversaries under consideration. we propose a set of definitions that, captures and unifies the intuitive notions of correctness, privacy, and robustness, and enables us to give concise and modular proofs that our protocols possess these desirable properties. using these techniques, whose major purpose is to greatly simplify the design and verification of cryptographic protocols, we show how to construct a multiparty cryptographic protocol to compute any given feasible function of the parties' inputs. we prove that our protocol is secure against the malicious actions of any adversary, limited to feasible computation, but with the power to eavesdrop on all messages and to corrupt any dynamically chosen minority of the parties. this is the first proof of security against dynamic adversaries in the "cryptographic" model of multiparty protocols. we assume the existeuce of a one-way function and allow the participants to erase small portions of memory. our result combines the superior resilience of the cryptographic setting of [gmw87] with the stronger (dynamic) fault pattern of the "non-cryptographic" setting of [bgw88, ccd88].
a toolbox for cryptanalysis: linear and affine equivalence algorithms. this paper presents two algorithms for solving the linear and the affine equivalence problem for arbitrary permutations (s-boxes). for a pair of n × n-bit permutations the complexity of the linear equivalence algorithm (le) is o(n32n). the affine equivalence algorithm (ae) has complexity o(n322n). the algorithms are efficient and allow to study linear and affine equivalences for bijective s-boxes of all popular sizes (le is efficient up to n ≤ 32). using these tools new equivalent representations are found for a variety of ciphers: rijndael, des, camellia, serpent, misty, kasumi, khazad, etc. the algorithms are furthermore extended for the case of non-bijective n to m-bit s-boxes with a small value of |n - m| and for the case of almost equivalent s-boxes. the algorithms also provide new attacks on a generalized even-mansour scheme. finally, the paper defines a new problem of s-box decomposition in terms of substitution permutations networks (spn) with layers of smaller s-boxes. simple information-theoretic bounds are proved for such decompositions.
structural cryptanalysis of sasas. in this paper we consider the security of block ciphers which contain alternate layers of invertible s-boxes and affine mappings (there are many popular cryptosystems which use this structure, including the winner of the aes competition, rijndael). we show that a five-layer scheme with 128-bit plaintexts and 8-bit s-boxes is surprisingly weak against what we call a multiset attack, even when all the s-boxes and affine mappings are key dependent (and thus completely unknown to the attacker). we tested the multiset attack with an actual implementation, which required just 216 chosen plaintexts and a few seconds on a single pc to find the 217 bits of information in all the unknown elements of the scheme.
advanced slide attacks. recently a powerful cryptanalytic tool--the slide attack-- was introduced [3]. slide attacks are very successful in breaking iterative ciphers with a high degree of self-similarity and even more surprisingly are independent of the number of rounds of a cipher. in this paper we extend the applicability of slide attacks to a larger class of ciphers. we find very efficient known- and chosen-text attacks on generic feistel ciphers with a periodic key-schedule with four independent subkeys, and consequently we are able to break a des variant proposed in [2] using just 128 chosen texts and negligible time for the analysis (for one out of every 216 keys). we also describe known-plaintext attacks on desx and even-mansour schemes with the same complexity as the best previously known chosen-plaintext attacks on these ciphers. finally, we provide new insight into the design of gost by successfully analyzing a 20-round variant (gost⊕) and demonstrating weak key classes for all 32 rounds.
general short computational secret sharing schemes. a secret sharing scheme permits a secret to be shared among participants in such a way that only qualified subsets of participants can recover the secret. if any non qualified subset has absolutely no information about the secret, then the scheme is called perfect. unfortunately, in this case the size of the shares cannot be less than the size of the secret. krawczyk [9] showed how to improve this bound in the case of computational threshold schemes by using rabin's information dispersal algorithms [14], [15]. we show how to extend the information dispersal algorithm for general access structure (we call access structure, the set of all qualified subsets). we give bounds on the amount of information each participant must have. then we apply this to construct computational schemes for general access structures. the size of shares each participant must have in our schemes is nearly minimal: it is equal to the minimal bound plus a piece of information whose length does not depend on the secret size but just on the security parameter.
on the impossibility of highly-efficient blockcipher-based hash functions. fix a small nonempty set of blockcipher keys . we say a blockcipher-based hash function is highly-efficient if it makes exactly one blockcipher call for each message block hashed, and all blockcipher calls use a key from . although a few highly-efficient constructions have been proposed, no one has been able to prove their security. in this paper we prove, in the ideal-cipher model, that it is impossible to construct a highly-efficient iterated blockcipher-based hash function that is provably secure. our result implies, in particular, that the tweakable chain hash (tch) construction suggested by liskov, rivest, and wagner (advances in cryptologycrypto 02, lecture notes in computer science, vol. 2442, pp. 3146, springer, berlin, 2002) is not correct under an instantiation suggested for this construction, nor can tch be correctly instantiated by any other efficient means.
round-optimal zero-knowledge arguments based on any one-way function. we fill a gap in the theory of zero-knowledge protocols by presenting np-arguments that achieve negligible error probability and computational zero-knowledge in four rounds of interaction, assuming only the existence of a one-way function. this result is optimal in the sense that four rounds and a one-way function are each individually necassary to achieve a negligible error zero-knowledge argument for np.
efficient multiplicative sharing schemes. multiplicative threshold schemes are useful tools in threshold cryptography. for example, such schemes can be used with a wide variety of practical homomorphic cryptosystems (such as the rsa, the el gamal and elliptic curve systems) for threshold decryption, signatures, or proofs. the paper describes a new recursive construction for multiplicative threshold schemes which makes it possible to extend the number of users of such schemes for a relatively small expansion of the share size. we discuss certain properties of the schemes, such as the information rate and zero knowledge aspects. the paper extends the karnin-greene-hellman bound on the parameters of ideal secret sharing schemes to schemes which are not necessarily ideal and then uses this as a yardstick to compare the performance of currently known multiplicative sharing schemes.
a theoretical treatment of related-key attacks: rka-prps, rka-prfs, and applications. we initiate a theoretical investigation of the popular blockcipher design-goal of security against "related-key attacks" (rkas). we begin by introducing definitions for the concepts of prps and prfs secure against classes of rkas, each such class being specified by an associated set of "related-key deriving (rkd) functions." then for some such classes of attacks, we prove impossibility results, showing that no block-cipher can resist these attacks while, for other, related classes of attacks that include popular targets in the block cipher community, we prove possibility results that provide theoretical support for the view that security against them is achievable. finally we prove security of various block-cipher based constructs that use related keys, including a tweakable block cipher given in [14].
noisy polynomial interpolation and noisy chinese remaindering. the noisy polynomial interpolation problem is a new intractability assumption introduced last year in oblivious polynomial evaluation. it also appeared independently in password identification schemes, due to its connection with secret sharing schemes based on lagrange's polynomial interpolation. this paper presents new algorithms to solve the noisy polynomial interpolation problem. in particular, we prove a reduction from noisy polynomial interpolation to the lattice shortest vector problem, when the parameters satisfy a certain condition that we make explicit. standard lattice reduction techniques appear to solve many instances of the problem. it follows that noisy polynomial interpolation is much easier than expected. we therefore suggest simple modifications to several cryptographic schemes recently proposed, in order to change the intractability assumption. we also discuss analogous methods for the related noisy chinese remaindering problem arising from the well-known analogy between polynomials and integers.
a new paradigm for collision-free hashing: incrementality at reduced cost. we present a simple, new paradigm for the design of collision-free hash functions. any function emanating from this paradigm is incremental. (this means that if a message x which i have previously hashed is modified to x′ then rather than having to re-compute the hash of x′ from scratch, i can quickly "update" the old hash value to the new one, in time proportional to the amount of modification made in x to get x′). also any function emanating from this paradigm is parallelizable, useful for hardware implementation. we derive several specific functions from our paradigm. all use a standard hash function, assumed ideal, and some algebraic operations. the first function, muhash, uses one modular multiplication per block of the message, making it reasonably efficient, and significantly faster than previous incremental hash functions. its security is proven, based on the hardness of the discrete logarithm problem. a second function, adhash, is even faster, using additions instead of multiplications, with security proven given either that approximation of the length of shortest lattice vectors is hard or that the weighted subset sum problem is hard. a third function, lthash, is a practical variant of recent lattice based functions, with security proven based, again on the hardness of shortest lattice vector approximation.
generating eigamal signatures without knowing the secret key. we present a new method to forge elgamal signatures if the public parameters of the system are not chosen properly. since the secret key is hereby riot fourid this attack shows that forging elgamal signatures is sometimes easier than the underlying discrete logarithm problem.
foundations of group signatures: formal definitions, simplified requirements, and a construction based on general assumptions. this paper provides theoretical foundations for the group signature primitive. we introduce strong, formal definitions for the core requirements of anonymity and traceability. we then show that these imply the large set of sometimes ambiguous existing informal requirements in the literature, thereby unifying and simplifying the requirements for this primitive. finally we prove the existence of a construct meeting our definitions based only on the sole assumption that trapdoor permutations exist.
authenticated key exchange secure against dictionary attacks. password-based protocols for authenticated key exchange (ake) are designed to work despite the use of passwords drawn from a space so small that an adversary might well enumerate, off line, all possible passwords. while several such protocols have been suggested, the underlying theory has been lagging. we begin by defining a model for this problem, one rich enough to deal with password guessing, forward secrecy, server compromise, and loss of session keys. the one model can be used to define various goals. we take ake (with "implicit" authentication) as the "basic" goal, and we give definitions for it, and for entity-authentication goals as well. then we prove correctness for the idea at the center of the encrypted key-exchange (eke) protocol of bellovin and merritt: we prove security, in an ideal-cipher model, of the two-flow protocol at the core of eke.
sha: a design for parallel architectures? to enhance system performance computer architectures tend to incorporate an increasing number of parallel execution units. this paper shows that the new generation of md4-based customized hash functions (ripemd-128, ripemd-160, sha-1) contains much more software parallelism than any of these computer architectures is currently able to provide. it is conjectured that the parallelism found in sha-1 is a design principle. the critical path of sha-1 is twice as short as that of its closest contender ripemd-160, but realizing it would require a 7-way multiple-issue architecture. it will also be shown that, due to the organization of ripemd-160 in two independent lines, it will probably be easier for future architectures to exploit its software parallelism.
on binary sequences from recursions modulo 2 made non-linear by the bit-by-bit xor function. we consider binary sequences obtained by choosing the the most significant bit of each element in a sequence obtained from a feedback shift register of length n operating over the ring z/2e, that is with arithmetic carried out modulo 2e. the feedback has been made non-linear by using the bit-by-bit exclusive-or function as well as the linear operation of addition. this should increase the cryptologic strength without greatly increasing the computing overheads. the periods and linear equivalences are discussed. provided certain conditions are met it is easy to check that the period achieves its maximal value.