waashk/dblp huggingface dataset:
on the security loss in cryptographic reductions. almost all the important cryptographic protocols we have today base their security on unproven assumptions, which all imply np $\ne$ p, and thus having unconditional proofs of their security seems far beyond our reach. one research effort then is to identify more basic primitives and prove the security of these protocols by reductions to the security of these primitives. however, in doing so, one often observes some security loss in the form that the security of the protocols is measured against weaker adversaries, e.g., adversaries with a smaller running time. is such a security loss avoidable? we study two of the most basic cryptographic reductions: hardness amplification of one-way functions and constructing pseudorandom generators from one-way functions. we show that when they are done in a certain black-box way, such a security loss is in fact unavoidable.
robust threshold dss signatures. we present threshold dss (digital signature standard) signatures where the power to sign is shared by n players such that for a given parameter t < n/2 any subset of 2t + 1 signers can collaborate to produce a valid dss signature on any given message, but no subset of t corrupted players can forge a signature (in particular, cannot learn the signature key). in addition, we present a robust threshold dss scheme that can also tolerate n/3 players who refuse to participate in the signature protocol. we can also endure n/4 maliciously faulty players that generate incorrect partial signatures at the time of signature computation. this results in a highly secure and resilient dss signature system applicable to the protection of the secret signature key, the prevention of forgery, and increased system availability. our results significantly improve over a recent result by langford from crypto'95 that presents threshold dss signatures which can stand much smaller subsets of corrupted players, namely, t ≅ √n, and do not enjoy the robustness property. as in thc case of langford's result, our schemes require no trusted party. our techniques apply to other threshold elgamal-like signatures as well. we prove the security of our schemes solely based on the hardness of forging a regular dss signature.
secure distributed key generation for discrete-log based cryptosystems. distributed key generation is a main component of threshold cryptosystems and distributed cryptographic computing in general. solutions to the distributed generation of private keys for discrete-log based cryptosystems have been known for several years and used in a variety of protocols and in many research papers. however, these solutions fail to provide the full security required and claimed by these works. we show how an active attacker controlling a small number of parties can bias the values of the generated keys, thus violating basic correctness and secrecy requirements of a key generation protocol. in particular, our attacks point out to the places where the proofs of security fail. based on these findings we designed a distributed key generation protocol which we present here together with a rigorous proof of security. our solution, that achieves optimal resiliency, can be used as a drop-in replacement for key generation modules as well as other components of threshold or proactive discrete-log based cryptosystems.
perfectly concealing quantum bit commitment from any quantum one-way permutation. we show that although unconditionally secure quantum bit commitment is impossible, it can be based upon any family of quantum one-way permutations. the resulting scheme is unconditionally concealing and computationally binding. unlike the classical reduction of naor, ostrovski, ventkatesen and young, our protocol is non-interactive and has communication complexity o(n) qubits for n a security parameter.
a framework for password-based authenticated key exchange. in this paper we present a general framework for passwordbased authenticated key exchange protocols, in the common reference string model. our protocol is actually an abstraction of the key exchange protocol of katz et al. and is based on the recently introduced notion of smooth projective hashing by cramer and shoup. we gain a number of benefits from this abstraction. first, we obtain a modular protocol that can be described using just three high-level cryptographic tools. this allows a simple and intuitive understanding of its security. second, our proof of security is significantly simpler and more modular. third, we are able to derive analogues to the katz et al. protocol under additional cryptographic assumptions. specifically, in addition to the ddh assumption used by katz et al., we obtain protocols under both the quadratic and n-residuosity assumptions. in order to achieve this, we construct new smooth projective hash functions.
verifiable secret sharing as secure computation. verifiable secret sharing is a fundamental primitive for secure cryptographic design. we present a stronger nation of verifiable secret sharing and exhibit a protocol implementing it. we show that our new notion is preferable to the old ones whenever verifiable secret sharing is used as a tool within larger protocols, rather than being a goal in itself. indeed our definition, and so our protocol satisfying it, provably guarantees reducibilty. applications of this new notion in the field of secure multiparty computation are also provided.
certificate-based encryption and the certificate revocation problem. we introduce the notion of certificate-based encryption. in this model, a certificate - or, more generally, a signature - acts not only as a certificate but also as a decryption key. to decrypt a message, a keyholder needs both its secret key and an up-to-date certificate from its ca (or a signature from an authorizer). certificate-based encryption combines the best aspects of identity-based encryption (implicit certification) and public key encryption (no escrow). we demonstrate how certificate-based encryption can be used to construct an efficient pki requiring less infrastructure than previous proposals, including micali's novomodo, naor-nissim and aiello-lodha-ostrovsky.
predicting the shrinking generator with fixed connections. we propose a novel distinguishing attack on the shrinking generator with known feedback polynomial for the generating lfsr. the attack can e.g. reliably distinguish a shrinking generator with a weight 4 polynomial of degree as large as 10000, using 232 output bits. as the feedback polynomial of an arbitrary lfsr is known to have a polynomial multiple of low weight, our distinguisher applies to arbitrary shrunken lfsr's of moderate length. the analysis can also be used to predict the distribution of blocks in the generated keystream.
equivalent goppa codes and trapdoors to mceliece's public key cryptosystem. we show that contrary to a published statement, any instance of mceliece's public key cryptosystem always has many trapdoors. our proof leads to a natural equivalence relation on monic polynomials over a finite field f such that any two irreducible goppa codes over f whose goppa polynomials are equivalent under this relation are equivalent as codes.
the security of the gabidulin public key cryptosystem. the gabidulin public key cryptosystem (pkc), like the well known mceliece pkc, is based on error correcting codes, and was introduced as an alternative to the mceliece system with the claim that much smaller codes could be used, resulting in a more practical system. in this paper an attack on the gabidulin pkc is given which breaks it for codes of the size envisaged, destroying much of its advantage over the mceliece system. the attack succeeds in polynomial time for gabidulin's choice of one of his system parameters, but it does show how to choose this parameter more appropriately. it consists of a reduction of the decryption problem for the gabidulin pkc to consideration of a search problem that is easier to describe, and which with luck should be easier to analyse. it therefore provides a possible starting point for a proof that decryption for the gabidulin pkc is an np-complete problem.
a note on the limits of collusion-resistant watermarks. in one proposed use of digital watermarks, the owner of a document d sells slightly different documents, d1;d2;,... to each buyer; if a buyer posts his/her document di to the web, the owner can identify the source of the leak. more general attacks are however possible in which k buyers create some composite document d*; the goal of the owner is to identify at least one of the conspirators. we show, for a reasonable model of digital watermarks, fundamental limits on their efficacy against collusive attacks. in particular, if the effective document length is n, then at most o(√n= ln n) adversaries can defeat any watermarking scheme. our attack is, in the theoretical model, oblivious to the watermarking scheme being used; in practice, it uses very little information about the watermarking scheme. thus, using a proprietary system seems to give only a very weak defense.
which new rsa signatures can be computed from rsa signatures, obtained in a specific interactive protocol? we consider cetain interactive protocols, based on rsa. in these protocols, a signature authority z (which chooses the rsa-modulus n that is kept fixed) issues a fixed number of rsa-signatures to an individual a. these rsa-signatures consist of products of rational powers of residue classes modulo n some of these residue classes are chosen by z and the others can be chosen freely by a thus, a can influence the form of the signatures that be gets from z. a wants to choose his residue classes in such a way that he can use the signatures he gets from z to compute a signature of a type not issued by z. in previous literature, some special cases of our protocols were considered. namely that only a chooses the residue classes ([dav82), [denn84], [do85]) and that only z chooses the residue classes [evh92]. the results in our paper are used under the following assumptiom: • a cannot compute rsa-roots on randomly chosen residue classes modulo n. • in his computations, a uses only multiplications and divisions modulo n. our main result gives a necessary and sufficient condition under which a is able to influence the signatures he gets from z in such a way that he can use these rsa-signatures to compute a signature of a type not issued by z. it turns out that this condition is equivalent to the solvability of a particular quadratic equation in integral matrices. we also study a particular case of this problem in more detail.
self-certified public keys. we introduce the notion, and give two examples, of self-certified public keys, i.e. public keys which need not be accompanied with a separate certificate to be authenticated by other users. the trick is that the public key is computed by both the authority and the user, so that the certificate is "embedded" in the public key itself, and therefore does not take the form of a separate value. self-certified public keys contribute to reduce the amount of storage and computations in public key schemes, while secret keys are still chosen by the user himself and remain unknown to the authority. this makes the difference with identity-based schemes, in which there are no more certificates at all, but at the cost that secret keys are computed (and therefore known to) the authority.
cryptanalysis of countermeasures proposed for repairing iso 9796-1. iso 9796-1, published in 1991, was the first standard specifying a digital signature scheme with message recovery. in [4], coron, naccache and stern described an attack on a slight modification of iso 9796- 1. then, coppersmith, halevi and jutla turned it into an attack against the standard in full [2]. they also proposed five countermeasures for repairing it. in this paper, we show that all these countermeasures can be attacked, either by using already existing techniques (including a very recent one), or by introducing new techniques, one of them based on the decomposition of an integer into sums of two squares.
selective forgery of rsa signatures using redundancy. we show the weakness of several rsa signature schemes using redundancy (i.e. completing the message to be signed with some additional bits which are fixed or message-dependent), by exhibiting chosen-message attacks based on the multiplicative property of rsa signature function. our attacks, which largely extend those of dejonge and chaum [djc], make extensive use of an affine variant of euclid's algorithm, due to okamoto and shiraishi [os]. when the redundancy consists of appending any fixed bits to the message m to be signed (more generally when redundancy takes the form of an affine function of m), then our attack is valid if the redundancy is less than half the length of the public modulus. when the redundancy consists in appending to m the remainder of m modulo some fixed value (or, more generally, any function of this remainder), our attack is valid if the redundancy is less than half the length of the public modulus minus the length of the remainder. we successfully apply our attack to a scheme proposed for discussion inside iso.
an efficient pseudo-random generator provably as secure as syndrome decoding. we show a simple and efficient construction of a pseudo-random generator based on the intractability of an np-complete problem from the area of error-correcting codes. the generalor is proved as secure as a hard instance of the syndrome decoding problem. each application of the scheme generates a linear amount of bits in only quadratic computing time.
incremental cryptography and memory checkers. we introduce the relationship between incremental cryptography and memory checkers. we present an incremental message authentication scheme based on the xor macs which supports insertion, deletion and other single block operations. our scheme takes only a constant number of pseudorandom function evaluations for each update step and produces smaller authentication codes than the tree scheme presented in [bgg95]. furthermore, it is secure against message substitution attacks, where the adversary is allowed to tamper messages before update steps, making it applicable to virus protection. from this scheme we derive memory checkers for data structures based on lists. conversely, we use a lower bound for memory checkers to show that so-called message substitution detecting schemes produce signatures or authentication codes with size proportional to the message length.
pseudorandom function tribe ensembles based on one-way permutations: improvements and applications. pseudorandom function tribe ensembles are pseudorandom function ensembles that have an additional collision resistance property: almost all functions have disjoint ranges.we present an alternative to the construction of pseudorandom function tribe ensembles based on oneway permutations given by canetti, micciancio and reingold [7]. our approach yields two different but related solutions: one construction is somewhat theoretic, but conceptually simple and therefore gives an easier proof that one-way permutations suffice to construct pseudorandom function tribe ensembles. the other, slightly more complicated solution provides a practical construction; it starts with an arbitrary pseudorandom function ensemble and assimilates the one-way permutation to this ensemble. therefore, the second solution inherits important characteristics of the underlying pseudorandom function ensemble: it is almost as efficient and if the starting pseudorandom function ensemble is invertible then so is the derived tribe ensemble. we also show that the latter solution yields so-called committing private-key encryption schemes. i.e., where each ciphertext corresponds to exactly one plaintext -- independently of the choice of the secret key or the random bits used in the encryption process.
stronger security proofs for rsa and rabin bits. the rsa and rabin encryption function are respectively defined as en(x) = xe mod n and en(x) = x2 mod n, where n is a product of two large random primes p, q and e is relatively prime to φv;(n). we present a much simpler and stronger proof of the result of alexi, chor, goldreich and schnorr [acgs88] that the following problems are equivalent by probabilistic polynomial time reductions: (1) given en(x) find x (2) given en(x) predict the least-significant bit of x with success probability 1/2 + 1/poly(n), where n has n bits. the new proof consists of a more efficient algorithm for inverhg the rsa/rabin-function with the help of an oracle that predicts the least-significant bit of x. it yields provable security guarantees for rsa-message bits and for the rsa-random number generator for moduli n of practical size.
a signature scheme as secure as the diffie-hellman problem. we show a signature scheme whose security is tightly related to the computational diffie-hellman (cdh) assumption in the random oracle model. existing discrete-log based signature schemes, such as elgamal, dss, and schnorr signatures, either require non-standard assumptions, or their security is only loosely related to the discrete logarithm (dl) assumption using pointcheval and stern's "forking" lemma. since the hardness of the cdh problem is widely believed to be closely related to the hardness of the dl problem, the signature scheme presented here offers better security guarantees than existing discrete-log based signature schemes. furthermore, the new scheme has comparable efficiency to existing schemes. the signature scheme was previously proposed in the cryptographic literature on at least two occasions. however, no security analysis was done, probably because the scheme was viewed as a slight modification of schnorr signatures. in particular, the scheme's tight security reduction to cdh has remained unnoticed until now. interestingly, this discrete-log based signature scheme is similar to the trapdoor permutation based pss signatures proposed by bellare and rogaway, and has a tight reduction for a similar reason.
two-threshold broadcast and detectable multi-party computation. classical distributed protocols like broadcast or multiparty computation provide security as long as the number of malicious players f is bounded by some given threshold t, i.e., f ≤ t. if f exceeds t then these protocols are completely insecure. we relax this binary concept to the notion of two-threshold security: such protocols guarantee full security as long as f ≤ t for some small threshold t, and still provide some degraded security when t < f ≤ t for a larger threshold t. in particular, we propose the following problems. • broadcast with extended validity: standard broadcast is achieved when f ≤ t. when t < f ≤ t, then either broadcast is achieved, or every player learns that there are too many faults. furthermore, when the sender is honest, then broadcast is always achieved. • broadcast with extended consistency: standard broadcast is achieved when f ≤ t. when t < f ≤ t, then either broadcast is achieved, or every player learns that there are too many faults. furthermore, the players agree on whether or not broadcast is achieved. • detectable multi-party computation: secure computation is achieved when f ≤ t. when t < f ≤ t, then either the computation is secure, or all players detect that there are too many faults and abort. the above protocols for n players exist if and only if t = 0 or t+2t < n.
the automated cryptoanalysis of analog speech scramblers. an automated method of attacking commonly used speech scramblers is presented. the cryptanalysis relies on the availability of the scrambled speech only and makes use of the characteristics of speech. it is shown that some of the currently available time and frequency domain scramblers, based on a fixed permutation. can be cryptanalysed. for systems where the permutation is changed with time, methods for partial recovery of the encrypted speech for several existing systems are given. in the case of the frequency domain scramblers a novel method of attack using a codebook is presented.
linear statistical weakness of alleged rc4 keystream generator. a keystream generator known as rc4 is analyzed by the linear model approach. it is shown that the second binary derivative of the least significant bit output sequence is correlated to 1 with the correlation coefficient close to 15ċ2-3n where n is the variable word size of rc4. the output sequence length required for the linear statistical weakness detection may be realistic in high speed applications if n ≤ 8. the result can be used to distinguish rc4 from other keystream generators and to determine the unknown parameter n, as well as for the plaintext uncertainty reduction if n is small.
cryptanalysis of alleged a5 stream cipher. a binary stream cipher, known as a5, consisting of three short lfsrs of total length 64 that are mutually clocked in the stop/go manner is cryptanalyzed. it is allegedly used in the gsm standard for digital cellular mobile telephones. very short keystream sequences are generated from different initial states obtained by combining a 64-bit secret session key and a known 22-bit public key. a basic divide-and-conquer attack recovering the unknown initial state from a known keystream sequence is first introduced. it exploits the specific clocking rule used and has average computational complexity around 240. a time-memory trade-off attack based on the birthday paradox which yields the unknown internal state at a known time for a known keystream sequence is then pointed out. the attack is successful if t ċ m ≥ 2633.32, where t and m are the required computational time and memory (in 128-bit words), respectively. the precomputation time is o(m) and the required number of known keystream sequences generated from different public keys is about t/102. for example, one can choose t ≅ 227.67 and m ≅ 235.65. to obtain the secret session key from the determined internal state, a so-called internal state reversion attack is proposed and analyzed by the theory of critical and subcritical branching processes.
on the security of rdsa. a variant of schnorr's signature scheme called rdsa has been proposed by i. biehl, j. buchmann, s. hamdy and a. meyer in order to be used in finite abelian groups of unknown order such as the class group of imaginary quadratic orders. we describe in this paper a total break of rdsa under a plain known-message attack for the parameters that were originally proposed. it recovers the secret signature key from the knowledge of less than 10 signatures of known messages, with a very low computational complexity. we also compare a repaired version of rdsa with gps scheme, another schnorr variant with similar properties and we show that gps should be preferred for most of the applications.
the number of output sequences of a binary sequence generator. in this paper, a number of output sequences is proposed as a characteristic of binary sequence generators for cryptographic applications. sufficient conditions for a variable-memory binary sequence generator to produce maximum possible number of output sequences are derived.
correlation via linear sequential circuit approximation of combiners with memory. correlation properties of a general binary combiner with an arbitrary number of memory bits are analyzed. it is shown that there exists a pair of certain linear functions of the output and input, respectively, that produce correlated binary sequences. an efficient procedure, based on a linear sequential circuit approximation, is developed for finding such pairs of linear functions. the result may be a basis for a divide and conquer correlation attack on a stream cipher generator consisting of several linear feedback shift registers combined by a combiner with memory.