waashk/dblp huggingface dataset:
single database private information retrieval implies oblivious transfer. a single-database private information retrieval (pir) is a protocol that allows a user to privately retrieve from a database an entry with as small as possible communication complexity. we call a pir protocol non-trivial if its total communication is strictly less than the size of the database. non-trivial pir is an important cryptographic primitive with many applications. thus, understanding which assumptions are necessary for implementing such a primitive is an important task, although (so far) not a well-understood one. in this paper we show that any non-trivial pir implies oblivious transfer, a far better understood primitive. our result not only significantly clarifies our understanding of any non-trivial pir protocol, but also yields the following consequences: - any non-trivial pir is complete for all two-party and multiparty secure computations. - there exists a communication-efficient reduction from any pir protocol to a 1-out-of-n oblivious transfer protocol (also called spir). - there is strong evidence that the assumption of the existence of a one-way function is necessary but not sufficient for any non-trivial pir protocol.
differential cryptanalysis of the stream ciphers py, py6 and pypy. py and pypy are efficient array-based stream ciphers designed by biham and seberry. both were submitted to the estream competition. this paper shows that py and pypy are practically insecure. if one key is used with about 216 ivs with special differences, with high probability two identical keystreams will appear. this can be exploited in a key recovery attack. for example, for a 16-byte key and a 16-byte iv, 223 chosen ivs can reduce the effective key size to 3 bytes. for a 32-byte key and a 32-byte iv, the effective key size is reduced to 3 bytes with 224 chosen ivs. py6, a variant of py, is more vulnerable to these attacks.
conditional oblivious transfer and timed-release encryption. we consider the problem of sending messages "into the future." previous constructions for this task were either based on heuristic assumptions or did not provide anonymity to the sender of the message. in the public-key setting, we present an efficient and secure timed-release encryption scheme using a "time server" which inputs the current time into the system. the server has to only interact with the receiver and never learns the sender's identity. the scheme's computational and communicational cost per request are only logarithmic in the time parameter. the construction of our scheme is based on a novel cryptographic primitive: a variant of oblivious transfer which we call conditional oblivious transfer. we define this primitive (which may be of independent interest) and show an efficient construction for an instance of this new primitive based on the quadratic residuosity assumption.
anonymous nizk proofs of knowledge with preprocessing. in this extended abstract we present an unpublished result in [6] which extends a result in [4]. we give a non-interactive zero-knowledge proof system of knowledge with preprocessing, whose main property is that, after executing two preprocessing phases and given a transcript of a proof phase, the verifier is not able to relate the transcript to any of the two preprocessing phases significantly better than random guessing. the technique used has motivated the cash scheme in [3]. because of this result, only mentioned but used in [3], the main observation of pfitzmann et al. in [8] against the cash scheme in [3] doesn't hold. we also discuss the other observations of pfitzmann et al. in [8] against the cash schemes in [3, 5] and show that all of them don't hold. as a conclusion, the cash schemes in [3, 5] are not broken at all.
linear complexity of periodically repeated random sequences. on the linear complexity λ(z) of a periodically repeated random bit sequence z, r. rueppel proved that, for two extreme cases of the period t, the expected linear complexity e[λ(z)] is almost equal to t, and suggested that e[λ(z)] would be close to t in general [6, pp. 33- 52] [7, 8]. in this note we obtain bounds of e[λ(z)], as well as bounds of the variance var[λ(z)], both for the general case of t, and we estimate the probability distribution of λ(z). our results on e[λ(z)] quantify the closeness of e[λ(z)] and t, in particular, formally confirm r. rueppel's suggestion.
efficient concurrent zero-knowledge in the auxiliary string model. we show that if any one-way function exists, then 3-round concurrent zero-knowledge arguments for all np problems can be built in a model where a short auxiliary string with a prescribed distribution is available to the players. we also show that a wide range of known efficient proofs of knowledge using specialized assumptions can be modified to work in this model with no essential loss of efficiency. we argue that the assumptions of the model will be satisfied in many practical scenarios where public key cryptography is used, in particular our construction works given any secure public key infrastructure. finally, we point out that in a model with preprocessing (and no auxiliary string) proposed earlier, concurrent zero-knowledge for np can be based on any one-way function.
collision free hash functions and public key signature schemes. in this paper, we present a construction of hash functions. these functions are collision free in the sense that under some cryptographic assumption, it is provably hard for an enemy to find collisions. assumptions that would be sufficient are the hardness of factoring, of discrete log, or the (possibly) more general assumption about the existence of claw free sets of permutations. the ability of a hash function to improve security and speed of a signature scheme is discussed: for example, we can combine the rsa-system with a collision free hash function based on factoring to get a scheme which is more efficient and much more secure. also, the effect of combining the goldwasser-micali-rest signature scheme with one of our functions is studied. in the factoring based implementation of the scheme using a k-bit modulus, the signing process can be speeded up by a factor roughly equal to kċo (log2(k)), while the signature checking process will be faster by a factor of o (log2(k)).
non-interactive circuit based proofs and non-interactive perfect zero-knowledge with proprocessing. in the first part of this paper, we present a noninteractive zero-knowledge proof system for circuit satisfiability. with this protocol, we can prove an arbitrary np-statement non-interactively without using karp-reductions to 3-sat or graph hamiltonicity. the proof system is based on the quadratic residuosity problem and allows processing of xor and not gates at virtually no cost. it is significantly more efficient than previously known non-interactive proof systems. in the second part, we present protocols based on the existence of collision intractable hash functions, leading to a statistical zero-knowledge noninteractive argument with preprocessing for any np-statement. under the certified discrete log assumption, the protocol is perfect zero-knowledge. in the preprocessing, the parties need only exchange messages of length independent of the theorem to be proved later. this is the first protocol with such efficient preprocessing that does not need to assume oblivious transfer. finally we present a perfect zero-knowledge non-interactive protocol based on discrete logarithms that may potentially remove the need for preprocessing.
on the (im)possibility of basing oblivious transfer and bit commitment on weakened security assumptions. we consider the problem of basing oblivious transfer (ot) and bit commitment (bc), with information theoretic security, on seemingly weaker primitives.we introduce a general model for describing such primitives, called weak generic transfer (wgt). this model includes as important special cases weak oblivious transfer (wot), where both the sender and receiver may learn too much about the other party's input, and a new, more realistic model of noisy channels, called unfair noisy channels. an unfair noisy channel has a known range of possible noise levels; protocols must work for any level within this range against adversaries who know the actual noise level. we give a precise characterization for when one can base ot on wot. when the deviation of the wot from the ideal is above a certain threshold, we show that no information-theoretic reductions from ot (even against passive adversaries) and bc exist; when the deviation is below this threshold, we give a reduction from ot (and hence bc) that is information-theoretically secure against active adversaries. for unfair noisy channels we show a similar threshold phenomenon for bit commitment. if the upper bound on the noise is above a threshold (given as a function of the lower bound) then no information-theoretic reduction from ot (even against passive adversaries) or bc exist; when it is below this threshold we give a reduction from bc. as a partial result, we give a reduction from ot to unc for smaller noise intervals.
new convertible undeniable signature schemes. undeniable signatures are like ordinary digital signatures, except that testing validity of a signature requires interaction with the signer. this gives the signer additional control over who will benefit from being convinced by a signature, and is particularly relevant when signing sensitive, non-public data. convertible undeniable signatures offer additional flexibility in that there is a separate verification key that can be used to verify a signature (without interaction). this allows the signer to delegate the ability to verify signatures to one or more participants, and ultimately to convert all signatures to ordinary ones by making the verification key public. while provably secure theoretical solutions exist for convertible schemes, earlier practical schemes proposed have either been broken or their status as far as security is concerned is very unclear. in this paper, we present two new convertible schemes, in which forging signatures is provably equivalent to forging el gamal signatures. the difficulty of verifying signatures without interacting with the signer is based on the factoring problem for one of the schemes and on the diffie-hellman problem for the other scheme.
a public key analog cryptosystem. in this paper we present a public key cryptosystem based on error correcting codes [1, 7, 15]. the new public key system is obtained by extending the public key cryptosystem of mceliece [6, 12]. in this scheme a message m, consisting of a column vector of k elements from a finite field is first scrambled by multiplying it by a non singular matrix q to get m′ = q m this scrambled message has parity check variables added to it, by multiplying it by a generator matrix g and then has all the variables reordered by multipliation by a permutation matrix p. noise is then added to obtain the encrypted message c = p g q m + z the product of the three matrices g′ = p g q is made public, but the factors are not.
an expanded set of s-box design criteria based on information theory and its relation to differential-like attacks. the security of des-like cryptosystems depends heavily on the strength of the substitution boxes (s-boxes) used. the design of new s-boxes is therefore an important concern in the creation of new and more secure cryptosystems. the full set of design criteria for the s-boxes of des has never been released and a complete set has yet to be proposed in the open literature. this paper introduces a unified s-box design framework based on information theory and illustrates how it provides immunity to the differential attack.
how to break a practical mix and design a new one. a mix net takes a list of ciphertexts (c1; ... ; cn) and outputs a permuted list of the plaintexts (m1; ... ;mn) without revealing the relationship between (c1; ... ; cn) and (m1; ... ;mn). this paper first shows that the jakobsson's mix net of eurocrypt'98, which was believed to be resilient and very efficient, is broken. we next propose an efficient t-resilient mix net with o(t2) servers in which the cost of each mix server is o(n). two new concepts are introduced, existential-honesty and limited-open-verification. they will be useful for distributed computation in general.
esign: an efficient digital signature implementation for smard cards. esign is an efficient digital signature algorithm [oks, ok], whose computation speed is more than twenty times faster than that of the rsa scheme, while its key length and signature length are comparable to those of the rsa scheme. this paper presents a software implementation of esign on an 8bit micro-processor smart card. this realizes a computation time for signature generation of about 0.2 seconds. to achieve this remarkable speed for signature generation, appropriate implementation techniques such as pre-computation and table look-up techniques are effectively used. moreover, this software implementation is compact enough for smart cards; the program size and the data size including the work area are at most 3kbytes each. practical identification schemes based on esign are also presented.
interactive bi-proof systems and undeniable signature schemes. this paper proposes a new construction of the minimum knowledge undeniable signature scheme which solves a problem inherent in chaum's scheme. we formulate a new proof system, the minimum knowledge interactive bi-proof system, and a pair of languages, the common witness problem, based on the random self-reducible problem. and we show that any common witness problem has the minimum knowledge interactive bi-proof system. a practical construction for undeniable signature schemes is proposed based on such a proof system. these schemes assure signature confirmation and disavowal with the same protocol (or at the same time).
ideals over a non-commutative ring and thier applications in cryptology. a new modification of the mceliece public-key cryptosystem is proposed that employs the so-called maximum-rank-distance (mrd) codes in place of goppa codes and that hides the generator matrix of the mrd code by addition of a randomly-chosen matrix. a short review of the mathematical background required for the construction of mrd codes is given. the cryptanalytic work function for the modified mceliece system is shown to be much greater than that of the original system. extensions of the rank metric are also considered.
facts and myths of enigma: breaking stereotypes. in spite of a relatively large number of publications about breaking enigma by the allies before and during the world war ii, this subject remains relatively unknown not only to the general public, but also to people professionally involved in cryptological research. for example, the story of enigma is rarely a part of a modern textbook on cryptology or a modern course on cryptography and network security. there exist multiple reasons for this situation. first, there are still a few unresolved issues, resulting from conflicting reports, the lack of reliable sources, and a long period required for declassifying documents related to any cryptological activity during the world war ii. secondly, the issue is highly political, and there is little consensus in weighing the contribution of all involved countries. thirdly, many contemporary cryptologists honestly believe that there is little to learn from the analysis of old cryptosystems, because of the tremendous progress in theory and practice of cryptography and a little similarity between old and modern ciphers. in this paper we confront these opinions by presenting a look at the current state of knowledge about cryptological methods and devices used to break enigma. we introduce all major players involved in these activities, and we make an effort to weigh their original contributions. finally, we show that the story of enigma can still provide contemporary cryptographers with many useful lessons regarding the way of organizing and building any large-scale security system.
massively parallel elliptic curve factorin. we describe our massively parallel implementations of the elliptic curve factoring method. one of our implementations is based on a new systolic version of montgomery multiplication.
concealment and its applications to authenticated encryption. we introduce a new cryptographic primitive we call concealment, which is related, but quite different from the notion of commitment. a concealment is a publicly known randomized transformation, which, on input m, outputs a hider h and a binder b. together, h and b allow one to recover m, but separately, (1) the hider h reveals "no information" about m, while (2) the binder b can be "meaningfully opened" by at most one hider h. while setting b = m, h = φ is a trivial concealment, the challenge is to make |b| ≪ |m|, which we call a "non-trivial" concealment. we show that non-trivial concealments are equivalent to the existence of collision-resistant hash functions. moreover, our construction of concealments is extremely simple, optimal, and yet very general, giving rise to a multitude of efficient implementations. we show that concealments have natural and important applications in the area of authenticated encryption. specifically, let ae be an authenticated encryption scheme (either public- or symmetric-key) designed to work on short messages. we show that concealments are exactly the right abstraction allowing one to use ae for encrypting long messages. namely, to encrypt "long" m, one uses a concealment scheme to get h and b, and outputs authenticated ciphertext 〈ae(b),h〉. more surprisingly, the above paradigm leads to a very simple and general solution to the problem of remotely keyed (authenticated) encryption (rkae) [12,13]. in this problem, one wishes to split the task of high-bandwidth authenticated encryption between a secure, but low-bandwidth/computationally limited device, and an insecure, but computationally powerful host. we give formal definitions for rkae, which we believe are simpler and more natural than all the previous definitions. we then show that our composition paradigm satisfies our (very strong) definition. namely, for authenticated encryption, the host simply sends a short value b to the device (which stores the actual secret key for ae), gets back ae(b), and outputs 〈ae(b), h〉 (authenticated decryption is similar). finally, we also observe that the particular schemes of [13,17] are all special examples of our general paradigm.
strengthening zero-knowledge protocols using signatures. recently there has been an interest in zero-knowledge protocols with stronger properties, such as concurrency, unbounded simulation soundness, non-malleability, and universal composability. in this paper, we show a novel technique to convert a large class of existing honest-verifier zero-knowledge protocols into ones with these stronger properties in the common reference string model. more precisely, our technique utilizes a signature scheme existentially unforgeable against adaptive chosen-message attacks, and transforms any σ-protocol (which is honest-verifier zero-knowledge) into an unbounded simulation sound concurrent zero-knowledge protocol. we also introduce ω-protocols, a variant of σ-protocols for which our technique further achieves the properties of non-malleability and/or universal composability. in addition to its conceptual simplicity, a main advantage of this new technique over previous ones is that it avoids the cook-levin theorem, which tends to be rather inefficient. indeed, our technique allows for very efficient instantiation based on the security of some efficient signature schemes and standard number-theoretic assumptions. for instance, one instantiation of our technique yields a universally composable zero-knowledge protocol under the strong rsa assumption, incurring an overhead of a small constant number of exponentiations, plus the generation of two signatures.
an algorithm for solving the discrete log problem on hyperelliptic curves. we present an index-calculus algorithm for the computation of discrete logarithms in the jacobian of hyperelliptic curves defined over finite fields. the complexity predicts that it is faster than the rho method for genus greater than 4. to demonstrate the efficiency of our approach, we describe our breaking of a cryptosystem based on a curve of genus 6 recently proposed by koblitz.
lower bounds for oblivious transfer reductions. we prove the first general and non-trivial lower bound for the number of times a 1-out-of-n oblivious transfer of strings of length l should be invoked so as to obtain, by an information-theoretically secure reduction, a 1-out-of-n oblivious transfer of strings of length l. our bound is tight in many significant cases. we also prove the first non-trivial lower bound for the number of random bits needed to implement such a reduction whenever the receiver sends no messages to the sender. this bound is also tight in many significant cases.
secure multiround authentication protocols. gemmell and naor proposed a new protocol for unconditionally secure authentication of long messages. however gehrmann showed that the proof of the security of the protocol was incorrect. here we generalize the multiround protocol model. we prove the security of a 3-round protocol and give for this case a new easy implementable construction which has a key size close to the fundamental lower bound for even extremely long messages. furthermore, we give a proof of a secure multiround protocol for an arbitrary number of rounds.
secure hash-and-sign signatures without the random oracle. we present a new signature scheme which is existentially unforgeable under chosen message attacks, assuming some variant of the rsa conjecture. this scheme is not based on "signature trees", and instead it uses the so called "hash-and-sign" paradigm. it is unique in that the assumptions made on the cryptographic hash function in use are well defined and reasonable (although non-standard). in particular, we do not model this function as a random oracle. we construct our proof of security in steps. first we describe and prove a construction which operates in the random oracle model. then we show that the random oracle in this construction can be replaced by a hash function which satisfies some strong (but well defined!) computational assumptions. finally, we demonstrate that these assumptions are reasonable, by proving that a function satisfying them exists under standard intractability assumptions.
verifiable signature sharing. we introduce verifiable signature sharing (vσs), a cryptographic primitive for protecting digital signatures. vσs enables the holder of a digitally signed document, who may or may not be the original signer, to share the signature among a set of proxies so that the honest proxies can later reconstruct it. we present efficient vσs schemes for exponentiation based signatures (e.g., rsa, rabin) and discrete log based signatures (e.g., elgamal, schnorr, dsa) that can tolerate the malicious (byzantine) failure of the sharer and a constant fraction of the proxies. we also describe our implementation of these schemes and evaluate their performance. among the applications of vσs is the incorporation of digital cash into multiparty protocols, e.g., to enable cash escrow and secure distributed auctions.