waashk/dblp huggingface dataset:
on the power of cascade ciphers. the unicity distance of a cascade of random ciphers, with respect to known plaintext attack, is shown to be the sum of the key lengths. a time-space trade-off for the exhaustive cracking of a cascade of ciphers is shown. the structure of the set of permutations realized by a cascade is studied; it is shown that only l.2k exhaustive experiments are necessary to determine the behavior of a cascade of l stages, each having k key bits. it is concluded that the cascade of random ciphers is not a random cipher. yet, it is shown that, with high probability, the number of permutations realizable by a cascade of l random ciphers, each having k key bits, is 2lk. next, it is shown that two stages are not worse than one, by a simple reduction of the cracking problem of any of the stages to the cracking problem of the cascade. finally, it is shown that proving a nonpolynomial lower bound on the cracking problem of long cascades is a hard task, since such a bound implies that p &nap; np.
public-key cryptosystems from lattice reduction problems. we present a new proposal for a trapdoor one-way function, from which we derive public-key encryption and digital signatures. the security of the new construction is based on the conjectured computational difficulty of lattice-reduction problems, providing a possible alternative to existing public-key encryption algorithms and digital signatures such as rsa and dss.
on the existence of pseudorandom generators. pseudorandom generators are known to exist, assuming the existence of functions that cannot be efficiently inverted on the distributions induced by applying the function iteratively polynomially many times. this sufficient condition is also necessary, but it is difficult to check whether particular functions, assumed to be one-way, are also one-way on their iterates. this raises the fundamental question of whether the mere existence of one-way functions suffices for the construction of pseudorandom generators. progress toward resolving this question is presented. regular functions in which every image of a k-bit string has the same number of preimages of length k are considered. it is shown that if a regular function is one-way, then pseudorandom generators do exist. in particular, assuming the intractability of general factoring, it can be proved that the pseudorandom generators do exist. another application is the construction of a pseudorandom generator based on the assumed intractability of decoding random linear codes.
session-key generation using human passwords only. we present session-key generation protocols in a model where the legitimate parties share only a human-memorizable password. the security guarantee holds with respect to probabilistic polynomial-time adversaries that control the communication channel (between the parties), and may omit, insert and modify messages at their choice. loosely speaking, the effect of such an adversary that controls m instances of the protocol is comparable to an on-line attack in which an adversary is only allowed to makes o(m) queries of the form ``is w the password of party&#x00a0;a''''. we stress that the result holds also in case the passwords are selected at random from a small dictionary so that it is feasible (for the adversary) to scan the entire directory.
can statistical zero knowledge be made non-interactive? or on the relationship of szk and niszk. we further extend the study, recently initiated by de-santis et. al (icalp98) of non-interactive statistical zero-knowledge proofs. our main focus is to compare the class niszk of problems possessing such non-interactive proofs to the class szk of problems possessing interactive statistical zero-knowledge proofs. along these lines, we first show that if statistical zero-knowledge is non-trivial then so is non-interactive statistical zero-knowledge, where by non-trivial we mean that the class includes problems which are not solvable in probabilistic polynomial-time. (the hypothesis holds under various assumptions, such as the intractability of the discrete logarithm problem.) furthermore, we show that if niszk is closed under complementation, then in fact szk=niszk, i.e. all statistical zero-knowledge proofs can be made non-interactive. the main tools in our analysis are two promise problems that are natural restrictions of promise problems known to be complete for szk. we show that these restricted problems are in fact complete for niszk, and using this relationship we derive our results comparing the two classes. the two problems refer to the statistical difference, and difference in entropy, respectively, of a given distribution from the uniform one. we also consider a weak form of niszk, in which only requires that for every inverse polynomial 1/p(n), there exists a simulator which achieves simulator deviation 1/p(n), and show that this weak form of niszk actually equals niszk.
public protection of software. one of the overwhelming problems that software producers must contend with is the unauthorized use and distribution of their products. copyright laws concerning software are rarely enforced, thereby causing major losses to the software companies. technical means of protecting software from illegal duplication are required, but the available means are imperfect. we present protocols that enable software protection, without causing substantial overhead in distribution and maintenance. the protocols may be implemented by a conventional cryptosystem, such as the des, or by a public key cryptosystem, such as the rsa. both implementations are proved to satisfy required security criteria.
limits on the provable consequences of one-way permutations. we present strong evidence that the implication, &ldquo;if one-way permutations exist, then secure secret key agreement is possible&rdquo;, is not provable by standard techniques. since both sides of this implication are widely believed true in real life, to show that the implication is false requires a new model. we consider a world where all parties have access to a black box for a randomly selected permutation. being totally random, this permutation will be strongly one-way in a provable, information-theoretic way. we show that, if p = n p, no protocol for secret key agreement is secure in such a setting. thus, to prove that a secret key agreement protocol which uses a one-way permutation as a black box is secure is as hard as proving p &ne; n p. we also obtain, as a corollary, that there is an oracle relative to which the implication is false, i.e., there is a one-way permutation, yet secret-exchange is impossible. thus, no technique which relativizes can prove that secret exchange can be based on any one-way permutation. our results present a general framework for proving statements of the form, &ldquo;cryptographic application x is not likely possible based solely on complexity assumption y.&rdquo;
identity escrow. we introduce the notion of {\em escrowed identity}, an application of key-escrow ideas to the problem of identification. in escrowed identity, one party $a$ does {\em 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 give protocols for escrowed identity based on the el-gamal (signature and encryption) schemes and on the rsa function. a useful feature of our protocol is that after setting up $a$ to use the system, $e$ is only involved when it is actually needed to determine $a$''s identity.
scalable protocols for authenticated group key exchange. we consider the problem of authenticated group key exchange among n parties communicating over an insecure public network. a number of solutions to this problem have been proposed; however, all prior provably secure solutions do not scale well and, in particular, require o(n) rounds. our main contribution is the first scalable protocol for this problem along with a rigorous proof of security in the standard model under the ddh assumption; our protocol uses a constant number of rounds and requires only o(1) "full" modular exponentiations per user. toward this goal (and adapting work of bellare, canetti, and krawczyk), we first present an efficient compiler that transforms any group key-exchange protocol secure against a passive eavesdropper to an authenticated protocol which is secure against an active adversary who controls all communication in the network. this compiler adds only one round and o(1) communication (per user) to the original scheme. we then prove secure&#x2014;against a passive adversary&#x2014;a variant of the two-round group key-exchange protocol of burmester and desmedt. applying our compiler to this protocol results in a provably secure three-round protocol for authenticated group key exchange which also achieves forward secrecy.
a randomnesss-rounds tradeoff in private computation. we study the role of randomness in multiparty private computations. in particular, we give several results that prove the existence of a randomness-rounds tradeoff in multiparty private computation of $\fxor$. we show that with a single random bit, $\theta(n)$ rounds are necessary and sufficient to privately compute $\fxor$ of n input bits. with $d\ge 2$ random bits, $\omega(\log n/ d)$ rounds are necessary, and $o(\log n/ \log d)$ are sufficient. more generally, we show that the private computation of a boolean function f, using $d\ge 2 $ random bits, requires $\omega(\log s(f)/ d)$ rounds, where s(f) is the sensitivity of f. using a single random bit, $\omega(s(f))$ rounds are necessary.
a randomized protocol for signing contracts. randomized protocols for signing contracts, certified mail, and flipping a coin are presented. the protocols use a 1-out-of-2 oblivious transfer subprotocol which is axiomatically defined.the 1-out-of-2 oblivious transfer allows one party to transfer exactly one secret, out of two recognizable secrets, to his counterpart. the first (second) secret is received with probability one half, while the sender is ignorant of which secret has been received.an implementation of the 1-out-of-2 oblivious transfer, using any public key cryptosystem, is presented.
non-interactive timestamping in the bounded storage model. a timestamping scheme is non-interactive if a stamper can stamp a document without communicating with any other player. the only communication done is at validation time. non-interactive timestamping has many advantages, such as information theoretic privacy and enhanced robustness. non-interactive timestamping, however, is not possible against polynomial-time adversaries that have unbounded storage at their disposal. as a result, no non-interactive timestamping schemes were constructed up to date. in this paper we show that non-interactive timestamping is possible in the bounded-storage model, i.e., if the adversary has bounded storage, and a long random string is broadcast to all players. to the best of our knowledge, this is the first example of a cryptographic task that is possible in the bounded-storage model but is impossible in the &#x201c;standard cryptographic setting,&#x201d; even when assuming &#x201c;standard&#x201d; cryptographic assumptions. we give an explicit construction that is secure against all bounded storage adversaries and a significantly more efficient construction secure against all bounded storage adversaries that run in polynomial time.
two-party generation of dsa signatures. we describe a means of sharing the dsa signature function, so that two parties can efficiently generate a dsa signature with respect to a given public key but neither can alone. we focus on a certain instantiation that allows a proof of security for concurrent execution in the random oracle model and that is very practical. we also briefly outline a variation that requires more rounds of communication but that allows a proof of security for sequential execution without random oracles.
threshold password-authenticated key exchange. in most password-authenticated key exchange systems there is a single server storing password verification data. to provide some resilience against server compromise, this data typically takes the form of a one-way function of the password (and possibly a salt, or other public values) rather than the password itself. however, if the server is compromised, this password verification data can be used to perform an off-line dictionary attack on the user's password. in this paper we propose an efficient password-authenticated key exchange system involving a set of servers with known public keys, in which a certain threshold of servers must participate in the authentication of a user, and in which the compromise of any fewer than that threshold of servers does not allow an attacker to perform an off-line dictionary attack. we prove our system is secure in the random oracle model under the decision diffie-hellman assumption against an attacker that may eavesdrop on, insert, delete, or modify messages between the user and servers, and that compromises fewer than that threshold of servers.
digital signature scheme for computer communication networks. this paper introduces four new digital signature schemes for computer communication networks. these involve one or more arbitrators who validate and authenticate messages and signatures without having access to the actual contents of the messages.
private searching on streaming data. in this paper we consider the problem of private searching on streaming data, where we can efficiently implement searching for documents that satisfy a secret criteria (such as the presence or absence of a hidden combination of hidden keywords) under various cryptographic assumptions. our results can be viewed in a variety of ways: as a generalization of the notion of private information retrieval (to more general queries and to a streaming environment); as positive results on privacy-preserving datamining; and as a delegation of hidden program computation to other machines.
a polynomial time algorithm for breaking the basic merkle-hellman cryptosystem. the cryptographic security of the merkle-hellman cryptosystem has been a major open problem since 1976. in this paper we show that the basic variant of this cryptosystem, in which the elements of the public key are modular multiples of a superincreasing sequence, is breakable in polynomial time.
efficient and secure pseudo-random number generation. cryptographically secure pseudo-random number generators known so far suffer from the handicap of being inefficient; the most efficient ones can generate only one bit on each modular multiplication (n/sup 2/ steps). blum, blum and shub ask the open problem of outputting even two bits securely. we state a simple condition, the xor-condition, and show that any generator satisfying this condition can output logn bits on each multiplication. we also show that the logn least significant bits of rsa, rabin's scheme, and the x/sup 2/ mod n generator satisfy boolean predicates of these bits are secure. furthermore, we strengthen the security of the x/sup 2/ mod n generator, which being a trapdoor generator, has several applications, by proving it as hard as factoring.
secure hybrid encryption from weakened key encapsulation. we put forward a new paradigm for building hybrid encryption schemes from constrained chosen-ciphertext secure (ccca) key-encapsulation mechanisms (kems) plus authenticated symmetric encryption. constrained chosen-ciphertext security is a new security notion for kems that we propose. it has less demanding security requirements than standard ccca security (since it requires the adversary to have a certain plaintext-knowledge when making a decapsulation query) yet we can prove that it is ccca sufficient for secure hybrid encryption. our notion is not only useful to express the kurosawa-desmedt public-key encryption scheme and its generalizations to hash-proof systems in an abstract kem/dem security framework. it also has a very constructive appeal, which we demonstrate with a new encryption scheme whose security relies on a class of intractability assumptions that we show (in the generic group model) strictly weaker than the decision diffie-hellman (ddh) assumption. this appears to be the first practical public-key encryption scheme in the literature from an algebraic assumption strictly weaker than ddh.
information security economics - and beyond. the economics of information security has recently become a thriving and fast-moving discipline. as distributed systems are assembled from machines belonging to principals with divergent interests, incentives are becoming as important to dependability as technical design. the new field provides valuable insights not just into 'security' topics such as privacy, bugs, spam, and phishing, but into more general areas such as system dependability (the design of peer-to-peer systems and the optimal balance of effort by programmers and testers), and policy (particularly digital rights management). this research program has been starting to spill over into more general security questions (such as law-enforcement strategy), and into the interface between security and sociology. most recently it has started to interact with psychology, both through the psychology-and-economics tradition and in response to phishing. the promise of this research program is a novel framework for analyzing information security problems - one that is both principled and effective.
deterministic and efficiently searchable encryption. we present as-strong-as-possible definitions of privacy, and constructions achieving them, for public-key encryption schemes where the encryption algorithm is deterministic. we obtain as a consequence database encryption methods that permit fast (i.e. sub-linear, and in fact logarithmic, time) search while provably providing privacy that is as strong as possible subject to this fast search constraint. one of our constructs, called rsa-doaep, has the added feature of being length preserving, so that it is the first example of a public-key cipher. we generalize this to obtain a notion of efficiently-searchable encryption schemes which permit more flexible privacy to search-time trade-offs via a technique called bucketization. our results answer much-asked questions in the database community and provide foundations for work done there.
amplifying collision resistance: a complexity-theoretic treatment. we initiate a complexity-theoretic treatment of hardness amplification for collision-resistant hash functions, namely the transformation of weakly collision-resistant hash functions into strongly collision-resistant ones in the standard model of computation. we measure the level of collision resistance by the maximum probability, over the choice of the key, for which an efficient adversary can find a collision. the goal is to obtain constructions with short output, short keys, small loss in adversarial complexity tolerated, and a good trade-off between compression ratio and computational complexity. we provide an analysis of several simple constructions, and show that many of the parameters achieved by our constructions are almost optimal in some sense.
efficient constructions of composable commitments and zero-knowledge proofs. canetti et al. [7] recently proposed a new framework -- termed generalized universal composability (guc) -- for properly analyzing concurrent execution of cryptographic protocols in the presence of a global setup, and constructed the first known guc-secure implementations of commitment (gucc) and zero-knowledge (guc zk), which suffice to implement any two-party or multi-party functionality under several natural and relatively mild setup assumptions. unfortunately, the feasibility results of [7] used rather inefficient constructions.in this paper, we dramatically improve the efficiency of (adaptively-secure) gucc and guc zk assuming data erasures are allowed. namely, using the same minimal setup assumptions as those used by [7], we build a direct and efficient constant-round guc zk for r from any "dense" ¿-protocol [21] for r. as a corollary, we get a semi-efficient construction from any σ-protocol for r (without doing the cook-levin reduction), and a very efficient guc zk for proving knowledge of a discrete log representation. the first constant-rate (and constant-round) gucc scheme. additionally, we show how to properly model a random oracle in the guc framework without losing deniability, which is one of the attractive features of the guc framework. in particular, by adding the random oracle to the setup assumptions used by [7], we build the first two-round (which we show is optimal), deniable, straight-line extractable and simulatable zk proof for any np relation r.
founding cryptography on oblivious transfer - efficiently. we present a simple and efficient compiler for transforming secure multi-party computation (mpc) protocols that enjoy security only with an honest majority into mpc protocols that guarantee security with no honest majority, in the oblivious-transfer (ot) hybrid model. our technique works by combining a secure protocol in the honest majority setting with a protocol achieving only security against semi-honest parties in the setting of no honest majority.applying our compiler to variants of protocols from the literature, we get several applications for secure two-party computation and for mpc with no honest majority. these include: constant-rate two-party computation in the ot-hybrid model. we obtain a statistically uc-secure two-party protocol in the ot-hybrid model that can evaluate a general circuit c of size s and depth d with a total communication complexity of o(s) + poly(k, d, log s) and o(d) rounds. the above result generalizes to a constant number of parties. extending ots in the malicious model. we obtain a computationally efficient protocol for generating many string ots from few string ots with only a constant amortized communication overhead compared to the total length of the string ots. black-box constructions for constant-round mpc with no honest majority. we obtain general computationally uc-secure mpc protocols in the ot-hybrid model that use only a constant number of rounds, and only make a black-box access to a pseudorandom generator. this gives the first constant-round protocols for three or more parties that only make a black-box use of cryptographic primitives (and avoid expensive zero-knowledge proofs).
deterministic encryption: definitional equivalences and constructions without random oracles. we strengthen the foundations of deterministic public-key encryption via definitional equivalences and standard-model constructs based on general assumptions. specifically we consider seven notions of privacy for deterministic encryption, including six forms of semantic security and an indistinguishability notion, and show them all equivalent. we then present a deterministic scheme for the secure encryption of uniformly and independently distributed messages based solely on the existence of trapdoor one-way permutations. we show a generalization of the construction that allows secure deterministic encryption of independent high-entropy messages. finally we show relations between deterministic and standard (randomized) encryption.
security-amplifying combiners for collision-resistant hash functions. the classical combiner combh0, h1class (m) = h0(m)||h1(m) for hash functions h0, h1 provides collision-resistance as long as at least one of the two underlying hash functions is secure. this statement is complemented by the multi-collision attack of joux (crypto 2004) for iterated hash functions h0,h1 with n-bit outputs. he shows that one can break the classical combiner in n/2 ċ t0 + t1 steps if one can find collisions for h0 and h1 in time t0 and t1, respectively. here we address the question if there are security-amplifying combiners where the security of the building blocks increases the security of the combined hash function, thus beating the bound of joux. we discuss that one can indeed have such combiners and, somewhat surprisingly in light of results of nandi and stinson (eprint 2004) and of hoch and shamir (fse 2006), our solution is essentially as efficient as the classical combiner.