waashk/dblp huggingface dataset:
enhancing secrecy by data compression: theoretical and practical aspects. it was recognised by shannon that data compression increases the strength of secrecy systems when applied prior to encryption. compression techniques have advanced considerably in recent years. this paper considers the extent to which these techniques can increase security. estimates are obtained for how far practical compression schemes can increase unicity distance of symmetric ciphers. it is noted that there are other good reasons for using data compression prior to encryption. comparison is made with homophonic coding and it is suggested that data compression is more worthwhile for practical sources such as natural language.
provably secure password-authenticated key exchange using diffie-hellman. when designing password-authenticated key exchange protocols (as opposed to key exchange protocols authenticated using cryptographically secure keys), one must not allow any information to be leaked that would allow verification of the password (a weak shared key), since an attacker who obtains this information may be able to run an off-line dictionary attack to determine the correct password. we present a new protocol called pak which is the first diffie-hellman-based password-authenticated key exchange protocol to provide a formal proof of security (in the random oracle model) against both passive and active adversaries. in addition to the pak protocol that provides mutual explicit authentication, we also show a more efficient protocol called ppk that is provably secure in the implicit -authentication model. we then extend pak to a protocol called pak-x, in which one side (the client) stores a plaintext version of the password, while the other side (the server) only stores a verifier for the password. we formally prove security of pak-x, even when the server is compromised. our formal model for password-authenticated key exchange is new, and may be of independent interest.
restrictive blinding of secret-key certificates. many signature transporting mechanisms require a signer to issue triples, consisting of a secret key, a matching public key, and a certificate of the signer on the public key. of particular interest are so-called restrictive blind signature issuing protocols, in which the receiver can blind the issued public key and the certificate but not a certain predicate of the secret key. this paper describes the first generally applicable techniquc for designing efficient such issuing protocols, based on the recently introduced notion of secret-key certificates. the resulting three-move issuing protocols require the receiver to perform merely a single on-line multiplication, and the property of restrictive blinding can be proved with respect to a plausible intractability assumption. application of the new issuing protocols results in the most efficient and versatile off-line electronic cash systems known to date, without using the blind signature technique developed by chaum.
rapid demonstration of linear relations connected by boolean operators. consider a polynomial-time prover holding a set of secrets. we describe how the prover can rapidly demonstrate any satisfiable boolean formula for which the atomic propositions are relations that are linear in the secrets, without revealing more information about the secrets than what is conveyed by the formula itself. our protocols support many proof modes, and are as secure as the discrete logarithm assumption or the rsa/factoring assumption.
blinding for unanticipated signatures. previously known blind signature systems require an amount of computation at least proportional to the number of signature types, and also that the number of such types be fixed in advance. these requirements are not practical in some applications. here, a new blind signature technique is introduced that allows an unlimited number of signature types with only a (modest) constant amount of computation.
some weaknesses of "weaknesses of undeniable signatures". the weaknesses that are the subject of [dy 91] have already been addressed in the published literature [c 90 & cva 89]. the main class of these weaknesses consists of ways of cheating undeniable signatures; but these ways are shown here to themselves be "weak." specifically, a cheater using them can double-cross the other cheaters, to the extent that the original ways of cheating are rendered useless. the remaining cited weaknesses are re-statements of, or variations on, some previously observed blinding techniques [cva 89]. these techniques allow advantages in some applications when desired, but are also easily excluded when not desired.
oblivious transfers and privacy amplification. assume a owns two secret k-bit strings. she is willing to disclose one of them to b, at his choosing, provided he does not learn anything about the other string. conversely, b does not want a to learn which secret he chose to learn. a protocol for the above task is said to implement one-out-of-two string oblivious transfer, denoted (2 1)-otk. this primitive is particularly useful in a variety of cryptographic settings. an apparently simpler task corresponds to the case k = 1 of two one-bit secrets: this is known as one-out-of-two bit oblivious transfer, denoted (2 1)-ot. we address the question of reducing (2 1)-otk to (2 1)-ot. this question is not new: it was introduced in 1986. however, most solutions until now have implicitly or explicitly depended on the notion of self-intersecting codes. it can be proved that this restriction makes it asymptotically impossible to implement (2 1)-otk with fewer than about 3.5277k instances of (2 1)-ot. the current paper introduces the idea of using privacy amplification as underlying technique to reduce (2 1)-otk to (2 1)-ot. this allows for more efficient solutions at the cost of an exponentially small probability of failure: it is sufficient to use slightly more than 2k instances of (2 1)-ot in order to implement (2 1)-otk. moreover, we show that privacy amplification allows for the efficient implementation of (2 1)-otk from generalized versions of (2 1)-ot that would not have been suitable for the earlier techniques based on self-intersecting codes. an application of this more general reduction is given.
security aspects of practical quantum cryptography. the use of quantum bits (qubits) in cryptography holds the promise of secure cryptographic quantum key distribution schemes. unfortunately, the implemented schemes are often operated in a regime which excludes unconditional security. we provide a thorough investigation of security issues for practical quantum key distribution, taking into account channel losses, a realistic detection process, and modifications of the "qubits" sent from the sender to the receiver. we first show that even quantum key distribution with perfect qubits might not be achievable over long distances when fixed channel losses and fixed dark count errors are taken into account. then we show that existing experimental schemes (based on weak pulses) currently do not offer unconditional security for the reported distances and signal strength. finally we show that parametric downconversion offers enhanced performance compared to its weak coherent pulse counterpart.
an improved protocol for demonstrating possession of discrete logarithms and some generalizations. a new protocol is presented that allows a to convince b that she knows a solution to the discrete log problem--i.e. that she knows an x such that αx ≡ β (mod n) holds-- without revealing anything about x to b. protocols are given both for n prime and for n composite. we also give protocols for extensions of the discrete log problem allowing a to show possession of: - multiple discrete logarithms to the same base at the same time, i.e. knowing x1,....,xk such that αx1 ≡ β1,..., αxk βk - several discrete logarithms to different bases at the same time, i.e. knowing x1,..., xk such that the product α1x1 α2x2... αkxk ≡ β - a discrete logarithm that is the simultaneous solution of several different instances, i.e. knowing x such that α1x ≡ β1,..., αkx ≡ βk. we can prove that the sequential versions of these protocols do not reveal any "knowledge" about the discrete logarithm(s) in a well-defined sense, provided that a knows (a multiple of) the order of α.
group signatures. in this paper we present a new type of signature for a group of persons, called a group signature, which has the following properties: (i) only members of the group can sign messages; (ii) the receiver can verify that it is a valid group signature, but cannot discover which group member made it; (iii) if necessary, the signature can be "opened", so that the person who signed the message is revealed. the group signatures are a "generalization" of the credential/ membership authentication schemes, in which one person proves that he belongs to a certain group. we present four schemes that satisfy the properties above. not all these schemes arc based on the same cryptographic assumption. in some of the schemes a trusted centre is only needed during the setup; and in other schemes, each pason can create the group he belongs to.
transferred cash grows in size. all known methods for transferring electronic money have the disadvantages that the number of bits needed to represent the money after each payment increases, and that a payer can recognize his money if he sees it later in the chain of payments (forward traceability). this paper shows that it is impossible to construct an electronic money system providing transferability without the property that the money grows when transferred. furthermore it is argued that an unlimited powerful user can always recognize his money later. finally, the lower bounds on the size of transferred electronic money are discussed in terms of secret sharing schemes.
on the efficiency of group signatures providing information-theoretic anonymity. group signatures, introduced by chaum and van heijst at eurocrypt'91, allow members of a group to make signatures on behalf of the group while remaining anonymous. furthermore, in case of disputes a designated group authority, who is given some auxiliary information, can identify the signer. chaum and van heijst presented four schemes, one of which protects the anonymity of the signer information-theoretically. however, this scheme as well as subsequent schemes with this property requires that the signer basically needs a new secret key for each signature and that the group authority secretly stores a very long string. this paper analyses such group signature schemes and obtains lower bounds on the length of both the secret keys of the group members and the auxiliary information of the authority depending on the number of signatures each is allowed to make and the number of group members. these bounds are optimal as they are met by the scheme suggested by chaum and van heijst.
s-boxes with controllable nonlinearity. in this paper, we give some relationship between the nonlinearity of rational functions over f2n and the number of points of associated hyperelliptic curve. using this, we get a lower bound on nonlinearity of rational-typed vector boolean functions over f2n. while the previous works give us a lower bound on nonlinearity only for special-typed monomials, our result gives us general bound applicable for all rational fuctions defined over f2n. as an application of our results, we get a lower bound on nonlinearity of n × kn s-boxes.
on a fast correlation attack on certain stream ciphers. in this paper we present a new algorithm for the recovery of the initial state of a linear feedback shift register when a noisy output sequence is given. our work is focussed on the investigation of the asymptotical behaviour of the recovery process rather than on the construction of an optimal recovery procedure. our results show the importance of low-weight checks and show also that the complexity of the recovery problem grows less than exponentially with the length of the shift register, even if the number of taps grows linearly with the register length. our procedure works for shift register with arbitrary feedback polynomial.
the information leakage through a randomly generated function. if a randomly filled memory is used to combine some ml-shift registers then the obtained mutual information between the output and a set of inputs will be a random variable. its distribution is demonstrated to be approximately proportional to a χ2-distribution.
improved algorithms for efficient arithmetic on elliptic curves using fast endomorphisms. in most algorithms involving elliptic curves, the most expensive part consists in computing multiples of points. this paper investigates how to extend the τ -adic expansion from koblitz curves to a larger class of curves defined over a prime field having an efficiently-computable endomorphism φ in order to perform an efficient point multiplication with efficiency similar to solinas' approach presented at crypto '97. furthermore, many elliptic curve cryptosystems require the computation of k0p + k1q. following the work of solinas on the joint sparse form, we introduce the notion of φ-joint sparse form which combines the advantages of a φ-expansion with the additional speedup of the joint sparse form. we also present an efficient algorithm to obtain the φ-joint sparse form. then, the double exponentiation can be done using the φ endomorphism instead of doubling, resulting in an average of l applications of φ and l/2 additions, where l is the size of the ki's. this results in an important speed-up when the computation of φ is particularly effective, as in the case of koblitz curves.
physical protection of cryptographic devices. with the growth of user awareness for the need to protect sensitive computer data by cryptographic means, this paper explains the need to protect critical cryptographic variables (particularly keys, and in some cases algorithms) in a secure environment within cryptographic equipment, particularly those used in the area of high value funds transfer transactions. design principles are outlined, leading to the concept of tamper resistant and not tamper proof devices to protect key data, whether the data be retained within physically large devices or on small portable tokens. criteria for the detection of attempts to gain access to sensitive data rather than attack prevention are outlined, together with two types of attack scenario - invasive and non-invasive. the risks of attack on cryptographic devices are surveyed and intruder attack objectives are outlined, together with some typical scenarios. the available counter-measures are discussed. several discreet mechanisms are described. typical detection mechanisms and sensor systems are discussed plus the design trade-offs that must be made in implementation, in particular manufacturing and maintenance costs versus scope of attack protection. once an attack is detected, various data destruction mechanisms may be employed. the desirability of active data destruction by "intelligent" means is proposed, together with a discussion of alternative techniques with particular reference to the data storage device characteristics. some experiences of tamper resistant research and development highlight the potential manufacturing problems - particularly in respect of quality assurance, product fault analysis and life-testing. the desirability of tamper resistant standards and independent assessment facilities is expressed, the applicability of such standards and large scale protection methods on intelligent tokens, in particular smart cards and personal authenticators, is discussed.
homomorphisms of secret sharing schemes: a tool for verifiable signature sharing. franklin and reiter introduced at eurocrypt '95 verifiable signature sharing, a primitive for a fault tolerant distribution of signature verification. they proposed various practical protocols. for rsa signatures with exponent e = 3 and n processors their protocol allows for up to (n - 1)/5 faulty processors (in general (n - 1)/(2 + e)). we consider a new unifying approach which uses homomorphisms of secret sharing schemes, and present a verifiable signature sharing scheme for which as many as (n - 1)/3 processors can be faulty (for any value of e), and for which the number of interactions is reduced.
factorization of a 512-bit rsa modulus. this paper reports on the factorization of the 512-bit number rsa-155 by the number field sieve factoring method (nfs) and discusses the implications for rsa.
finding a small root of a univariate modular equation. we show how to solve a polynomial equation (mod n) of degree k in a single variable x, as long as there is a solution smaller than n1/k. we give two applications to rsa encryption with exponent 3. first, knowledge of all the ciphertext and 2/3 of the plaintext bits for a single message reveals that message. second, if messages are padded with truly random padding and then encrypted with an exponent 3, then two encryptions of the same message (with different padding) will reveal the message, as long as the padding is less than 1/9 of the length of n. with several encryptions, another technique can (heuristically) tolerate padding up to about 1/6 of the length of n.
lattice attacks on ntru. ntru is a new public key cryptosystem proposed at crypto 96 by hoffstein, pipher and silverman from the mathematics department of brown university. it attracted considerable attention, and is being advertised over the internet by ntru cryptosystems. its security is based on the difficulty of analyzing the result of polynomial arithmetic modulo two unrelated moduli, and its correctness is based on clustering properties of the sums of random variables. in this paper, we apply new lattice basis reduction techniques to cryptanalyze the scheme, to discover either the original secret key, or an alternative secret key which is equally useful in decoding the ciphertexts.
finding a small root of a bivariate integer equation; factoring with high bits known. we present a method to solve integer polynomial equations in two variables, provided that the solution is suitably bounded. as an application, we show how to find the factors of n = pq if we are given the high order ((1/4) log2 n) bits of p. this compares with rivest and shamit's requirement of ((1/3) log2 n) bits.
computationally private information retrieval with polylogarithmic communication. we present a single-database computationally private information retrieval scheme with polylogarithmic communication complexity. our construction is based on a new, but reasonable intractability assumption, which we call the φ-hiding assumption (φha): essentially the difficulty of deciding whether a small prime divides φ(m), where m is a composite integer of unknown factorization.
low-exponent rsa with related messages. in this paper we present a new class of attacks against rsa with low encrypting exponent. the attacks enable the recovery of plaintext messages from their ciphertexts and a known polynomial relationship among the messages, provided that the ciphertexts were created using the same rsa public key with low encrypting exponent.
efficient and generalized group signatures. the concept of group signatures was introduced by chaum et al. at eurocrypt '91. it allows a member of a group to sign messages anonymously on behalf of the group. in case of a later dispute a designated group manager can revoke the anonymity and identify the originator of a signature. in this paper we propose a new efficient group signature scheme. furthermore we present a model and the first realization of generalized group signatures. such a scheme allows to define coalitions of group members that are able to sign on the group's behalf.
new attacks on pkcs#1 v1.5 encryption. this paper introduces two new attacks on pkcs#1 v1.5, an rsa-based encryption standard proposed by rsa laboratories. as opposed to bleichenbacher's attack, our attacks are chosen-plaintext only, i.e. they do not make use of a decryption oracle. the first attack applies to small public exponents and shows that a plaintext ending by sufficiently many zeroes can be recovered efficiently when two or more ciphertexts c orresponding to the same plaintext are available. we believe the technique we employ to be of independent interest, as it extends coppersmith's low-exponent attack to certain length parameters. our second attack is applicable to arbitrary public exponents, provided that most message bits are zeroes. it seems to constitute the first chosen-plaintext attack on an rsa-based encryption standard that yields to practical results for any public exponent.
confirmer signature schemes secure against adaptive adversaries. the main difference between confirmer signatures and ordinary digital signatures is that a confirmer signature can be verified only with the assistance of a semitrusted third party, the confirmer. additionally, the confirmer can selectively convert single confirmer signatures into ordinary signatures. this paper points out that previous models for confirmer signature schemes are too restricted to address the case where several signers share the same confirmer. more seriously, we show that various proposed schemes (some of which are provably secure in these restricted models) are vulnerable to an adaptive signature-transformation attack. we define a new stronger model that covers this kind of attack and provide a generic solution based on any secure ordinary signature scheme and public key encryption scheme. we also exhibit a concrete instance thereof.
security analysis of the gennaro-halevi-rabin signature scheme. we exhibit an attack against a signature scheme recently proposed by gennaro, halevi and rabin [9]. the scheme's security is based on two assumptions namely the strong rsa assumption and the existence of a division-intractable hash-function. for the latter, the authors conjectured a security level exponential in the hash-function's digest size whereas our attack is sub-exponential with respect to the digest size. moreover, since the new attack is optimal, the length of the hash function can now be rigorously fixed. in particular, to get a security level equivalent to 1024-bit rsa, one should use a digest size of approximately 1024 bits instead of the 512 bits suggested in [9].
proving in zero-knowledge that a number is the product of two safe primes. we present the first efficient statistical zero-knowledge protocols to prove statements such as: - a committed number is a prime. - a committed (or revealed) number is the product of two safe primes, i.e., primes p and q such that (p - 1)=2 and (q - 1)=2 are prime. - a given integer has large multiplicative order modulo a composite number that consists of two safe prime factors. the main building blocks of our protocols are statistical zero-knowledge proofs of knowledge that are of independent interest. we show how to prove the correct computation of a modular addition, a modular multiplication, and a modular exponentiation, where all values including the modulus are committed to but not publicly known. apart from the validity of the equations, no other information about the modulus (e.g., a generator whose order equals the modulus) or any other operand is exposed. our techniques can be generalized to prove that any multivariate modular polynomial equation is satisfied, where only commitments to the variables of the polynomial and to the modulus need to be known. this improves previous results, where the modulus is publicly known. we show how these building blocks allow to prove statements such as those listed earlier.