The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
This paper introduces a new adaptive chosen ciphertext attack against certain protocols based on RSA. We show that an RSA private-key operation can be performed if the attacker has access to an oracle that, for any chosen ciphertext, returns only one bit telling whether the ciphertext corresponds to some unknown block of data encrypted using PKCS #1. An example of a protocol susceptible to our attack...
A new public key cryptosystem is proposed and analyzed. The scheme is quite practical, and is provably secure against adaptive chosen ciphertext attack under standard intractability assumptions. There appears to be no previous cryptosystem in the literature that enjoys both of these properties simultaneously.
We compare the relative strengths of popular notions of security for public key encryption schemes. We consider the goals of privacy and non-malleability, each under chosen plaintext attack and two kinds of chosen ciphertext attack. For each of the resulting pairs of definitions we prove either an implication (every scheme meeting one notion must meet the other) or a separation (there is a scheme...
After many years, cryptography is coming to the Internet. Some protocols are in common use; more are being developed and deployed. The major issue has been one of cryptographic engineering: turning academic papers into a secure, implementable specification. But there is missing science as well, especially when it comes to efficient implementation techniques.
In this paper we present a method for finding collisions in SHA-0 which is related to differential cryptanalysis of block ciphers. Using this method, we obtain a theoretical attack on the compression function SHA-0 with complexity 261, which is thus better than the birthday paradox attack. In the case of SHA-1, this method is unable to find collisions faster than the birthday paradox. This is a strong...
We present a method for efficient conversion of differential (chosen plaintext) attacks into the more practical known plaintext and ciphertext-only attacks. Our observation may save up to a factor of 220 in data over the known methods, assuming that plaintext is ASCII encoded English (or some other types of highly redundant data). We demonstrate the effectiveness of our method by practical attacks...
We present a solution to both the robust threshold RSA and proactive RSA problems. Our solutions are conceptually simple, and allow for an easy design of the system. The signing key, in our solution, is shared at all times in additive form, which allows for simple signing and for a particularly efficient and straightforward refreshing process for proactivization. The key size is (up to a very small...
Verifiable Signature Sharing (VσS) enables the recipient of a digital signature, who is not necessarily the original signer, to share such signature among n proxies so that a subset of them can later reconstruct it. The original RSA and Rabin VσS protocols were subsequently broken and the original DSS VσS lacks a formal proof of security. We present new protocols for RSA, Rabin and DSS VσS...
This paper improves on the classical results in unconditionally secure multi-party computation among a set of n players, by considering a model with three simultaneously occurring types of player corruption: the adversary can actively corrupt (i.e. take full control over) up to ta players and, additionally, can passively corrupt (i.e. read the entire information...
The availability of fast and reliable Digital Identities is an essential ingredient for the successful implementation of the public-key infrastructure of the Internet. All digital identity schemes must include a method for revoking someone's digital identity in the case that this identity is stolen (or canceled) before its expiration date (similar to the cancelation of a credit-cards in the case that...
We introduce delegation schemes wherein a user may delegate certain rights to himself, but may not safely delegate these rights to others. In our motivating application, a user has a primary (long-term) key that receives some personalized access rights, yet the user may reasonably wish to delegate these rights to new secondary (short-term) keys he creates to use on his laptop when traveling, to avoid...
We introduce the concept of escrowed identity, an application of key-escrow ideas to the problem of authentication. In escrowed identity, one party A does not give his identity to another party B, but rather gives him information that would allow an authorized third party E to determine A's identity. However, B receives a guarantee that E can indeed determine A's identity. We consider a number of...
Unbalanced Feistel networks Fk which are used to construct invertible pseudo-random permutations from kn bits to kn bits using d pseudo-random functions from n bits to (k − l)n bits, k ≥ 2 are studied. We show a new generalized birthday attack on Fk, with d ≤ 3k − 3. With 2(k−1)n chosen plaintexts an adversary can distinguish...
In this paper, we derive 7 quadratic relations over GF(2) from the input and output bits of the S-boxes of DES. We apply one of those to an improved linear attack of full round DES. We describe an improved algorithm by combining the non-linear approximation method proposed by Knudsen and Robshaw, and the multiple approximation method proposed by Kaliski and Robshaw. This improvement can reduce the...
Using recent results from coding theory, it is shown how to break block ciphers operating on GF(q) where the ciphertext is expressible as evaluations of an unknown univariate polynomial of low degree m over the plaintext with a typically low but non-negligible, probability Μ. The method employed is essentially Sudan's algorithm for decoding Reed-Solomon codes beyond the error-correction diameter....
Recently, Ajtai discovered a fascinating connection between the worst-case complexity and the average-case complexity of some wellknown lattice problems. Later, Ajtai and Dwork proposed a cryptosystem inspired by Ajtai's work, provably secure if a particular lattice problem is difficult in the worst-case. We present a heuristic attack (to recover the private key) against this celebrated cryptosystem...
Knapsack-based cryptosystems used to be popular in the beginning of public key cryptography before being all broken, all but the Chor-Rivest cryptosystem. In this paper, we show how to break this one with its suggested parameters: GF(p24) and GF(25625). We also give direction on possible extensions of our attack.
Several multivariate algebraic signature schemes had been proposed in recent years, but most of them had been broken by exploiting the fact that their secret trapdoors are low rank algebraic structures. One of the few remaining variants is Patarin's”Oil & Vinegar” scheme, which is based on a system of n quadratic forms in 2n variables of two flavors (n ”oil” variables and n ”vinegar” variables)...
This paper studies the relationship between unpredictable functions (which formalize the concept of a MAC) and pseudo-random functions. We show an efficient transformation of the former to the latter using a unique application of the Goldreich-Levin hard-core bit (taking the inner-product with a random vector r): While in most applications of the GL-bit the random vector r may be public, in our setting...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.