waashk/dblp huggingface dataset:
fast authentication in a trapdoor - knapsack public key cryptosystem. public key cryptosystems based on the trapdoor knapsack method proposed by merkle and hellman are not well suited to provide authentication in the sense of public key authentication because only a small fraction of all possible message words of a typical length lead to a binary solution of the knapsack problem. in this paper, a new method is discussed which provides a nonbinary solution for the knapsack problem of a merkle/hellman scheme. the algorithm works for any message word with a comparatively short computation time. thus, the solution can be used as a secure authentication pattern. 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
on the use of interconnection networks in cryptography. cryptosystems can be viewed as sets of permutations from which one permutation is chosen as cryptofunction by specifying a key. interconnection networks have been widely studied in the field of parallel processing. they have one property that makes them very interesting for cryptology, i.e. they give the opportunity to access and perform permutations at the same time. this paper presents two examples of how cryptology can benefit from the use of interconnection networks. one is a new construction of a pseudo-random permutation (generator) from one single pseudo-random function (generator). the search for such constructions has been of major interest since luby and rackoff gave the first construction in 1986. the second example presents a cryptosystem based on interconnection networks and a certain class of boolean functions. some arguments for its security are given. although there is a relation between the two examples they complement each other in using different properties of interconnection networks. this can be regarded as an argument that exploiting the full potential of interconnection networks can establish completely new techniques in cryptology.
fair encryption of rsa keys. cryptography is more and more concerned with elaborate protocols involving many participants. in some cases, it is crucial to be sure that players behave fairly especially when they use public key encryption. accordingly, mechanisms are needed to check the correctness of encrypted data, without compromising secrecy. we consider an optimistic scenario in which users have pairs of public and private keys and give an encryption of their secret key with the public key of a third party. in this setting we wish to provide a publicly verifiable proof that the third party is able to recover the secret key if needed. our emphasis is on size; we believe that the proof should be of the same length as the original key. in this paper, we propose such proofs of fair encryption for el gamal and rsa keys, using the paillier cryptosystem. our proofs are really efficient since in practical terms they are only a few hundred bytes long. as an application, we design a very simple and efficient key recovery system.
is the rsa scheme safe? we present a new factoring algorithm which under reasonable assumptions and for r ≥ 2 will factor about n(r-2)-(r-2) which integers in [1,n] within n1/2r multiplications i n g(-n). here g(-n) is the group of equivalence classes under sl2(z), of primitive, positive forms ax2+bxy+cy2 with discriminant -n = b2 - 4 ac. let h(-n) = |g(- n)| be the class number. then n will be factored within this time bound if (1) the largest prime divisor of h(-n) is ≤ n1/r (2) the second largest prime divisor of h(-n) is ≤ n1/2r. so far it is unpredictable which integers n satisfy these conditions. 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
race integrity primitives evaluation (ripe): a status report. early in 1989, a call for integrity primitives was disseminated within the cryptographic community by the ripe consortium. the goal of this consortium is to put forward an ensemble of techniques to meet the anticipated requirements of the future integrated broadband communication network in the european community. the aim of this paper is to describe the status of the ripe project.
public key encryption and signature schemes based on polynomials over zn. the problem of computing roots of a polynomial over the ring zn, is equivalent to factoring n. starting from this intractable problem we construct a public key encryption scheme where the message blocks are encrypted as roots of a polynomial over zn and a signature scheme where the signature belonging to a message is a (set of) root(s) of a polynomial having the message blocks as coefficients. these schemes can be considered as extensions of rabin's encryption and signature scheme. however, our signature scheme has some new properties: a short signature can be generated for a long message without using a hash function, and the security features of the scheme can be chosen either to be similar to those of the rsa scheme or to be equivalent to those of rabin's scheme.
boolean functions satisfying higher order propagation criteria. boolean functions that satisfy higher order propagation criteria are studied. a complete characterization is given of the autocorrelation function and walsh spectrum of second order functions. the number of second order functions satisfying pc(k) is related to a problem in coding theory and can be computed explicitly for k = 1, n - 1 and n. a new interpretation of the number of balanced second order functions is given and a class of functions showing interesting properties is discussed.
on the security of two mac algorithms. the security of two message authentication code (mac) algorithms is considered: the md5-based envelope method (rfc 1828), and the banking standard maa (iso 8731-2). customization of a general mac forgery attack allows improvements in both cases. for the envelope method, the forgery attack is extended to allow key recovery; for example, a 128-bit key can be recovered using 267 known text-mac pairs and time plus 213 chosen texts. for maa, internal collisions are feud with fewer and shorter messages than previously by exploiting the algorithm's internal structure; consequently, the number of chosen texts (each 256 kbyte long) for a forgery can be reduced by two orders of magnitude, e.g. from 224 to 217. this attack can be extended to one requiring only short messages (224 messages shorter than 1 kbyte) to circumvent the special maa mode for long messages. moreover, certain internal collisions allow key recovery, and weak keys for maa are identified.
provably secure threshold password-authenticated key exchange. we present two protocols for threshold password authenticated key exchange. in this model, the password is not stored in a single authenticating server but rather shared among a set of n servers so that an adversary can learn the password only by breaking into t+1 of them. the protocols require n > 3t servers to work. the goal is to protect the password against hackers attacks that can break into the authenticating server and steal password information. all known centralized password authentication schemes are susceptible to such an attack. ours are the first protocols which are provably secure in the standard model (i.e. no random oracles are used for the proof of security). moreover our protocols are reasonably efficient and implementable in practice. in particular a goal of the design was to avoid costly zero-knowledge proofs to keep interaction to a minimum.
new bounds in secret-key agreement: the gap between formation and secrecy extraction. perfectly secret message transmission can be realized with only partially secret and weakly correlated information shared by the parties as soon as this information allows for the extraction of information-theoretically secret bits. the best known upper bound on the rate s at which such key bits can be generated has been the intrinsic information of the distribution modeling the parties', including the adversary's, knowledge. based on a new property of the secret-key rate s, we introduce a conditional mutual information measure which is a stronger upper bound on s. having thus seen that the intrinsic information of a distribution p is not always suitable for determining the number of secret bits extractable from p, we prove a different significance of it in the same context: it is a lower bound on the number of key bits required to generate p by public communication. taken together, these two results imply that sometimes, (a possibly arbitrarily large fraction of) the correlation contained in distributed information cannot be extracted in the form of secret keys by any protocol.
information-theoretic bounds for authentication frauds. several properties of authentication codes depend on a mathematical structure, called below a fraud scheme, which is much simpler than the one originally given. relying on this fact, we present a powerful lower bound, which is a sort of mould to painlessly derive a whole range of information-theoretic bounds to fraud probabilities in authentication coding.
on the concurrent composition of zero-knowledge proofs. we examine the concurrent composition of zero-knowledge proofs. by concurrent composition, we indicate a single prover that is involved in multiple, simultaneous zero-knowledge proofs with one or multiple verifiers. under this type of composition it is believed that standard zero-knowledge protocols are no longer zero-knowledge. we show that, modulo certain complexity assumptions, any statement in np has kɛ-round proofs and arguments in which one can efficiently simulate any ko(1) concurrent executions of the protocol.
on the security of the schnorr scheme using preprocessing. in this paper, it is shown that the schnorr scheme with preprocessing as proposed in [4] leaks too much information. an attack based on this information leakage is presented that retrieves the secret key. the complexity of this attack is upper bounded by 2k ċ k3(d-2) steps, and the expected required number of signatures is less than 2k ċ (k/2)(d-2), where k is a security parameter. this complexity is significantly lower than the kk(d-2) steps, conjectured in [4]. for example, for the security parameters that are proposed in [4], the secret key can on average be found in 237.5 steps, instead of in 272 steps, this shows that it is inevitable to either modify the preprocessing algorithm, or choose the values of the security paremeters larger than proposed in [4]. finally, we briefly discuar the possibility of averting the proposed attack by modifying the preprocessing algorithm.
on the complexity of hyperelliptic discrete logarithm problem. we give a characterization for the intractability of hyperelliptic discrete logarithm problem from a viewpoint of computational complexity theory. it is shown that the language of which complexity is equivalent to that of the hyperelliptic discrete logarithm problem is in np ∩ co-am, and that especially for elliptic curves, the corresponding language is in np ∩ co-np. it should be noted here that the language of which complexity is equivalent to that of the discrete logarithm problem defined over the multiplicative group of a finite field is also characterized as in np ∩ co-np.
practical threshold signatures. we present an rsa threshold signature scheme. the scheme enjoys the following properties: 1. it is unforgeable and robust in the random oracle model, assuming the rsa problem is hard; 2. signature share generation and verification is completely non-interactive; 3. the size of an individual signature share is bounded by a constant times the size of the rsa modulus.
using hash functions as a hedge against chosen ciphertext attack. the cryptosystem recently proposed by cramer and shoup [cs98] is a practical public key cryptosystem that is secure against adaptive chosen ciphertext attack provided the decisional diffie-hellman assumption is true. although this is a reasonable intractability assumption, it would be preferable to base a security proof on a weaker assumption, such as the computational diffie-hellman assumption. indeed, this cryptosystem in its most basic form is in fact insecure if the decisional diffie-hellman assumption is false. in this paper we present a practical hybrid scheme that is just as efficient as the scheme of of cramer and shoup; indeed, the scheme is slightly more efficient than the one originally presented by cramer and shoup; we prove that the scheme is secure if the decisional diffie-hellman assumption is true; we give strong evidence that the scheme is secure if the weaker, computational diffie-hellman assumption is true by providing a proof of security in the random oracle model.
a composition theorem for universal one-way hash functions. in this paper we present a new scheme for constructing universal one-way hash functions that hash arbitrarily long messages out of universal one-way hash functions that hash fixed-length messages. the new construction is extremely simple and is also very efficient, yielding shorter keys than previously proposed composition constructions.
when shift registers clock themselves. a new class of sequences, which we term [d,k] self-decimated sequences, is investigated. for appropriate choices of [d,k] these sequences possess large periods, balanced k-distributions, large linear complexities, and moderate out-of-phase autocorrelation magnitudes. furthermore, they are easy to generate. these properties suggest that [d,k] self-decimated sequences may have some applications in cryptography and spread spectrum communication.
on the security of a practical identification scheme. we analyze the security of an interactive identification scheme. the scheme is the obvious extension of the original square root scheme of goldwasser, micali and rackoff to 2mth roots. this scheme is quite practical, especially in terms of storage and communication complexity. although this scheme is certainly not new, its security was apparently not fully understood. we prove that this scheme is secure if factoring integers is hard, even against active attacks where the adversary is first allowed to pose as a verifier before attempting impersonation.
lower bounds for discrete logarithms and related problems. this paper considers the computational complexity of the discrete logarithm and related problems in the context of "generic algorithms"--that is, algorithms which do not exploit any special properties of the encodings of group elements, other than the property that each group element is encoded as a unique binary string. lower bounds on the complexity of these problems are proved that match the known upper bounds: any generic algorithm must perform ω(p1/2) group operations, where p is the largest prime dividing the order of the group. also, a new method for correcting a faulty diffie-hellman oracle is presented.
a formal approach to security architectures. we define a formal language whose symbols are security goals and mechanisms. this allows us to express every security architecture as a string. designing a security architecture becomes the task of generating a word in the language. analysing a security architecture becomes the task of parsing a string and determining if it belongs to the language. since not every complete security architecture achieves its goals equally efficient, we associate a complexity parameter to every goal and mechanism. this allows us to identify complexity- reducing and complexity-increasing mechanisms.
session key distribution using smart cards. in this paper, we investigate a method by which smart cards can be used to enhance the security of session key distribution in the third-party setting of needham & schroeder. we extend the security model of bellare & rogaway to take into account both the strengths and weaknesses of smart card technology, we propose a session key distribution protocol, and we prove that it is secure assuming pseudo-random functions exist.
a construction for one way hash functions and pseudorandom bit generators. we prove that if f is a n-bit one-way permutation, i.e., it has some hard bits, a one-way permutation with n - k provably simultaneous hard bits can be constructed with it. we apply this construction to improve the efficiency of blum-micali pseudo-random bit generator. then, we apply the construction to propose a new approach for building universal one-way hash functions. this approach merges damgard's design principle (or merkle's meta-method) and the method proposed by zheng, matsumoto and imai for the construction of hash functions for long messages.
a construction for super pseudorandom permutations from a single pseudorandom function. in this paper, we show how to construct a super pseudorandom permutation generator from a single pseudorandom function generator, based on des-like permutations. first, we show ψ(g, 1, f, g, 1, f), which consists of six rounds of des-like permutations with two different pseudorandom functions and a fixed permutation, is super psuedorandom. then, we show that with replacing a two-fold composition of one of the pseudorandom functions instead of the other one it is possible to construct a super pseudorandom permutation from a single pseudorandom function, where we need six rounds of des-like permutations and six references to the pseudorandom function.
authentication codes in plaintext and chosen-content attacks. we study authentication codes (a-codes) when the enemy has access to the content of the intercepted cryptogram. this is similar to plaintext attack in secrecy systems. enemy's success is defined in two ways. the first is as in simmons' model. we will also consider chosen-content attacks in which the success is by constructing a fraudulent cryptogram with a given content. we will obtain information theoretic bounds, define perfect protection and obtain lower bounds on the number of encoding rules for codes with perfect protection against chosen-content impersonation and chosen-content plaintext substitution. we characterize these a-codes when the number of encoding rules is minimum. we give methods of making an a-code resistant against plaintext and chosen-context plaintext attack.
factoring integers and computing discrete logarithms via diophantine approximations. let n be an integer with at least two distinct prime factors. we reduce the problem of factoring n to the task of finding random integer solutions (e1,..., et) ∈ zzt of the inequalities |σi=1tei log pi - log n|≤ n-c and σi=1t|ei log pi| ≤ (2c-1)log n+o(log pt), where c > 1 is fixed and p1, ..., pt are the first t primes. we show, under the assumption that the smooth integers distribute "uniformly", that there are ne+o(1) many solutions (e1,...,et) if c > 1 and if ɛ := c - 1 - (2c - 1) log log n / log pt > 0. we associate with the primes p1,...,pt a lattice l ⊂ rt+1 of dimension t and we associate with n a point n ∈ rt+1. we reduce the problem of factoring n to the task of finding random lattice vectors z that are sufficiently close to n in both the ∞-norm and thr 1-norm. the dimension t of the lattice l is polynomial in log n. for n ≅ 2512 it is about 6300. we also reduce the problem of computing, for a prime n, discrete logarithms of the units in zz/nzz to a similar diophantiue approximation problem.
message authentication with arbitration of transmitter/receiver disputes. in the most general model of message authentication, there are four essential participants: a transmitter who observes an information source, such as a coin toss, and wishes to communicate these observations to a remotely located receiver over a publicly exposed, noiseless, communications channel; a receiver who wishes to not only learn the state of the source (as observed by the transmitter) but also to assure himself that the communications (messages) he accepts actually were sent by the transmitter and that no alterations have been made to them subsequent to the transmitter having sent them, and two other parties, the opponent and the arbiter. the opponent wishes to deceive the receiver into accepting a message that will misinform him as to the state of the source. we assume, in accordance with kerckhoffs' criteria in cryptography, that the opponent is fully knowledgeable of the authentication system and that in addition he is able to both eavesdrop on legitimate communications in the channel and to introduce fraudulent communications of his own choice. we also assume that he has unlimited computing power, i.e., that any computation which can be done in principal can in fact be done in practice. given this, the opponent can achieve his objective in either of two ways: 1) he can impersonate the transmitter and send a fraudulent message when in fact no message was sent by the transmitter, or 2) he can wait to intercept a legitimate message from the transmitter and substitute in its stead some other message of his own devising.
receipt-free mix-type voting scheme - a practical solution to the implementation of a voting booth. we present a receipt-free voting scheme based on a mixtype anonymous channel[cha81, pik93]. the receipt-freeness property [bt94] enables voters to hide how they have voted even from a powerful adversary who is trying to coerce him. the work of [bt94] gave the first solution using a voting booth, which is a hardware assumption not unlike that in current physical elections. in our proposed scheme, we reduce the physical assumptions required to obtain receipt-freeness. our sole physical assumption is the existence of a private channel through which the center can send the voter a message without fear of eavesdropping.
relationships among the computational powers of breaking discrete log cryptosystems. we investigate the complexity of breaking cryptosystems of which security is based on the discrete logarithm problem. we denote the algorithms of breaking the diffie-hellman's key exchange scheme by dh, the bellare-micali's non-interactive oblivious transfer scheme by bm, the elgamal's public-key cryptosystem by eg, the okamoto's conferencekey sharing scheme by conf, and the shamir's 3-pass key-transmission scheme by 3pass, respectively. we show a relation among these cryptosystems that 3pass ≤mfp conf ≤mfp eg ≡mfp bm ≡mfp dh, where ≤mfp denotes the polynomial-time functionally many-teone reducibility, i.e. a function version of the ≤mp -reducibility. we further give some condition in which these algorithms have equivalent difficulty. namely, 1. if the complete factorization of p - 1 is given, i.e. if the the discrete logarithm problem is a certified one, then these cryptosystems are equivalent w.r.t. expected polynomial-time functionally turing reducibility. 2. if the underlying group is the jacobian of an elliptic curve over zp, with a prime order, then these cryptosystems are equivalent w.r.t. polynomial-time functionally many-to-one reducibility. we also discuss the complexity of several languages related to those computing problems.
construction of nonlinear boolean functions with important cryptographic properties. this paper addresses the problem of obtaining new construction methods for cryptographically significant boolean functions. we show that for each positive integer m, there are infinitely many integers n (both odd and even), such that it is possible to construct n-variable, m-resilient functions having nonlinearity greater than 2n-1 -2[n/2]. also we obtain better results than all published works on the construction of n-variable, m-resilient functions, including cases where the constructed functions have the maximum possible algebraic degree n - m - 1. next we modify the patterson-wiedemann functions to construct balanced boolean functions on n-variables having nonlinearity strictly greater than 2n-1 - 2n-1/2 for all odd n ≥ 15. in addition, we consider the properties strict avalanche criteria and propagation characteristics which are important for design of s-boxes in block ciphers and construct such functions with very high nonlinearity and algebraic degree.