waashk/dblp huggingface dataset:
secure bit commitment function against divertibility. some zero-knowledge interactive proofs (zkips) have divertibility, that is, evidence of proof issued by a genuine prover, a, can be transferred to plural verifiers, b and then c, where the intermediate verifier, b, acts as a, with a's help, to confound the other verifier c without revealing the relation between the a-b interaction and the b-c interaction. this property is a serious problem in practice, e.g. the mafia fraud attack on identification scheme and the multiverifier attack against undeniable signatures. this paper proposes a new concept, security against divertibility, and proves that naor's bit commitment function based on pseudo-random generators is secure against divertibility under the reasonable assumption. usage of this bit commitment in zkip can convert a divertible zkip to a divertible-free-zkip which is secure against the mafia fraud attack and the multi-verifier attack.
analysis of pseudo random sequence generated by cellular automata. the security of cellular automata for stream cipher applications is investigated. a cryptanalytic algorithm is developed for a known plaintext attack where the plaintext is assumed to be known up to the unicity distance. the algorithm is shown to be successful on small computers for key sizes up to n between 300 and 500 bits. for a cellular automaton to be secure against more powerful adversaries it is concluded that the key size n needs to be about 1000 bits. the cryptanalytic algorithm takes advantage of an equivalent description of the cryptosystem in which the keys are not equiprobable. it is shown that key search can be reduced considerably if one is contented to succeed only with a certain success probability. this is established by an information theoretic analysis of arbitrary key saurces with non-uniform probability distribution.
direct zero knowledge proofs of computational power in five rounds. zero-knowledge proofs of computational power have been proposed by yung and others. in this paper, we propose an efficient (direct) and constant round (five round) construction of zero knowledge proofs of computational power. to formulate the classes that can be applied to these efficient protocols, we introduce a class of invulnerable problems, fewpr and fewpru. we show that any invulnerable problem in fewpr and fewpru has an efficient and constant round zero knowledge proof of computational power, assuming the existence of a one-way function. we discuss some applications of these zero-knowledge proofs of computational power.
how intractable is the discrete logarithm for a general finite group? gdl is the discrete logarithm prablem for a general finite group g. this paper gives a characterization for the intractability of gdl from the viewpoint of computational complexity theory. it is shown that gdl ∈ np ∩ co-am, assuming that g is in np ∩ co-np, and that the group law operation of g can be cxecuted in a polynomial time of the element size. furthermore, as a natural probabilistic extension, the complexity of gdl is investigated under the assumption that the group law operation is executed in an expected polynomial time of the element size. in this case, it is shown that gdl ∈ ma ∩ co-am if g ∈ np ∩ co-np. finally, we show that gdl is less intractable than np-complete problems unless the polynomial time hierarchy collapses to the second level.
a public key cryptosystem based on elliptic curves over z/nz equivalent to factoring. elliptic curves over the ring z/nz where n is the product of two large primes have first been proposed for public key cryptosystems in [4]. the security of this system is based on the integer factorization problem, but it is unknown whether breaking the system is equivalent to factoring. in this paper, we present a variant of this cryptosystem for which breaking the system is equivalent to factoring the modulus n. moreover, we extend the ideas to get a signature scheme based on elliptic curves over z/nz.
the rsa group is pseudo-free. we prove, under the strong rsa assumption, that the group of invertible integers modulo the product of two safe primes is pseudo-free. more specifically, no polynomial-time algorithm can output (with non negligible probability) an unsatisfiable system of equations over the free abelian group generated by the symbols g 1,&#x2026;,g n , together with a solution modulo the product of two randomly chosen safe primes when g 1,&#x2026;,g n are instantiated to randomly chosen quadratic residues. ours is the first provably secure construction of pseudo-free abelian groups under a standard cryptographic assumption and resolves a conjecture of rivest (theory of cryptography conference&#x2014;proceedings of tcc 2004, lncs, vol.&#x00a0;2951, pp.&#x00a0;505&#x2013;521, 2004).
simulatable commitments and efficient concurrent zero-knowledge. we define and construct simulatable commitments. these are commitment schemes such that there is an efficient interactive proof system to show that a given string c is a legitimate commitment on a given value v, and furthermore, this proof is efficiently simulatable given any proper pair (c, v). our construction is provably secure based on the decisional diffie-hellman (ddh) assumption. using simulatable commitments, we show how to efficiently transform any public coin honest verifier zero knowledge proof system into a proof system that is concurrent zero-knowledge with respect to any (possibly cheating) verifier via black box simulation. by efficient we mean that our transformation incurs only an additive overhead (both in terms of the number of rounds and the computational and communication complexity of each round), and the additive term is close to optimal (for black box simulation): only ω(log n) additional rounds, and ω(log n) additional public key operations for each round of the original protocol, where n is a security parameter, and ω(log n) can be any superlogarithmic function of n independent of the complexity of the original protocol. the transformation preserves (up to negligible additive terms) the soundness and completeness error probabilities, and the new proof system is proved secure based on the ddh assumption, in the standard model of computation, i.e., no random oracles, shared random strings, or public key infrastructure is assumed.
optimal communication complexity of generic multicast key distribution. we prove a tight lower bound on the communication complexity of secure multicast key distribution protocols in which rekey messages are built using symmetric-key encryption, pseudo-random generators, and secret sharing schemes. our lower bound shows that the amortized cost of updating the group key for each group membership change (as a function of the current group size) is at least log2(n) - o(1) basic rekey messages. this lower bound matches, up to a subconstant additive term, the upper bound due to canetti et al. [proc. infocom 1999], who showed that log2(n) basic rekey messages (each time a user joins and/or leaves the group) are sufficient. our lower bound is, thus, optimal up to a small subconstant additive term. the result of this paper considerably strengthens previous lower bounds by canetti et al. [proc. eurocrypt 1999] and snoeyink et al. [computer networks, 47(3):2005], which allowed for neither the use of pseudorandom generators and secret sharing schemes nor the iterated (nested) application of the encryption function. our model (which allows for arbitrarily nested combinations of encryption, pseudorandom generators and secret sharing schemes) is much more general and, in particular, encompasses essentially all known multicast key distribution protocols of practical interest.
on diffie-hellman key agreement with short exponents. the difficulty of computing discrete logarithms known to be "short" is examined, motivated by recent practical interest in using diffie-hellman key agreement with short exponents (e.g. over zp, with 160-bit exponents and 1024-bit primes p). a new divide-and-conquer algorithm for discrete logarithms is presented, combining pollard's lambda method with a partial pohlig-hellman decomposition. for random diffie-hellman primes p, examination reveals this partial decomposition itself allows recovery of short exponents in many cases, while the new technique dramatically extends the range. use of subgroups of large prime order precludes the attack at essentially no cost, and is the recommended solution. using safe primes also precludes this particular attack and allows improved exponentiation performance, although parameter generation costs are dramatically higher.
security proofs for signature schemes. in this paper, we address the question of providing security proofs for signature schemes in the so-called random oracle model [1]. in particular, we establish the generality of this technique against adaptively chosen message attacks. our main application achieves such a security proof for a slight variant of the el garrial signature schemc [4] where committed values are hashed together with the message. this is a rather surprising result since the original el gamal is, as rsa [11], subject to existential forgery.
convergence of a bayesian iterative error-correction procedure on a noisy shift register sequence. convergence of an algorithm for a linear feedback shift register initial state reconstruction using the noisy output sequence, based on a bitwise bayesian iterative error-correction procedure and different weight parity-checks, is analyzed. it is proved that the self-composition of the bayes error probability converges to zero if and only if the noise probability is less than a critical value expressed in terms of the numbers of parity-checks. an alternative approach to the critical noise estimation based on the residual error-rate after each iterative revision is also discussed.
fast arithmetic architectures for public-key algorithms over galois fields gf((2)). this contribution describes a new class of arithmetic architectures for galois fields gf(2k). the main applications of the architecture are public-key systems which are based on the discrete logarithm problem for elliptic curves. the architectures use a representation of the field gf(2k) as gf((2n)m), where k = nċm. the approach explores bit parallel arithmetic in the subfield gf(2n), and serial processing for the extension field arithmetic. this mixed parallel-serial (hybrid) approach can lead to very fast implementations. the principle of these approach was initially suggested by mastrovito. as the core module, a hybrid multiplier is introduced and several optimizations are discussed. we provide two different approaches to squaring which, in conjunction with the multiplier, yield fast exponentiation architectures. the hybrid architectures are capable of exploring the time-space trade-off paradigm in a flexible manner. in particular, the number of clock cycles for one field multiplication, which is the atomic operation in most public-key schemes, can be reduced by a factor of n compared to all other known realizations. the acceleration is achieved at the cost of an increased computational complexity. we describe a proof-of-concept implementation of an asic for exponentiation in gf((2n)m), m variable.
public-key cryptosystems based on composite degree residuosity classes. this paper investigates a novel computational problem, namely the composite residuosity class problem, and its applications to public-key cryptography. we propose a new trapdoor mechanism and derive from this technique three encryption schemes : a trapdoor permutation and two homomorphic probabilistic encryption schemes computationally comparable to rsa. our cryptosystems, based on usual modular arithmetics, are provably secure under appropriate assumptions in the standard model.
simulation in quasi-polynomial time, and its application to protocol composition. we propose a relaxation of zero-knowledge, by allowing the simulator to run in quasi-polynomial time. we show that protocols satisfying this notion can be constructed in settings where the standard definition is too restrictive. specifically, we construct constant-round straight-line concurrent quasi-polynomial time simulatable arguments and show that such arguments can be used in advanced composition operations without any set-up assumptions. our protocols rely on slightly strong, but standard type assumptions (namely the existence of one-to-one one-way functions secure against subexponential circuits).
how to construct pseudorandom and super pseudorandom permutations from one single pseudorandom function. in this paper we will solve two open problems concerning pseudorandom permutations generators. 1. we will see that it is possible to obtain a pseudorandom permutation generator with only three rounds of des - like permutation and a single pseudorandom function. this will solve an open problem of [6]. 2. we will see that it is possible to obtain a super pseudorandom permutation generator with a single pseudorandom function. this will solve an open problem of [5]. for this we will use only four rounds of des - like permutation. for example, we will see that if ζ denotes the rotation of one bit, ψ(f,f,fo ζ o f) is a pseudorandom function generator. and ψ(f,f,f,f,o ζ o f) is a super pseudorandom function generator. here the number of rounds used is optimal. it should be noted that here we introduce an important new idea in that we do not use a composition of f, i times, but f o ζ o f for the last round, where ζ is a fixed and public function.
hidden fields equations (hfe) and isomorphisms of polynomials (ip): two new families of asymmetric algorithms. in [6] t. matsumoto and h. imai described a new asymmetric algorithm based on multivariate polynomials of degree two over a finite field, which was subsequently broken in [9]. here we present two new families of asymmetric algorithms that so far have resisted all attacks, if properly used: hidden field equations (hfe) and isomorphism of polynomials (ip). these algorithms can be seen as two candidate ways to repair the matsumoto-imai algorithm. hfe can be used to do signatures, encryption or authentication in an asymmetric way, with very short signatures and short encryptions of short messages. ip can be used for signatures and for zero knowledge authenticatinn. an extended version of this paper can be obtained from the author. another way to repair the matsumoto-imai algorithm will be presented in [10].
distributed provers with applications to undeniable signatures. this paper introduces distributed prover protocols. such a protocol is a proof system in which a polynomially bounded prover is replaced by many provers each having partial information about the witness owned by the original prover. as an application of this concept, it is shown how the signer of undeniable signatures can distribute part of his secret key to n agents such that any k of these can verify a signature. this facility is useful in most applications of undeniable signatures, and as the proposed protocols are practical, the results in this paper makes undeniable signatures more useful. the first part of the paper describes a method for verifiable secret sharing, which allows non-interactive verification of the shares and is as secure as the shamir secret sharing scheme in the proposed applications.
coin-based anonymous fingerprinting. fingerprinting schemes are technical means to discourage people from illegally redistributing the digital data they have legally purchased. these schemes enable the original merchant to identify the original buyer of the digital data. in so-called asymmetric fingerprinting schemes the fingerprinted data item is only known to the buyer after a sale and if the merchant finds an illegally redistributed copy, he obtains a proof convincing a third party whom this copy belonged to. all these fingerprinting schemes require the buyers to identify themselves just for the purpose of fingerprinting and thus offer the buyers no privacy. hence anonymous asymmetric fingerprinting schemes were introduced, which preserve the anonymity of the buyers as long as they do not redistribute the data item. in this paper a new anonymous fingerprinting scheme based on the principles of digital coins is introduced. the construction replaces the general zero-knowledge techniques from the known certificate-based construction by explicit protocols, thus bringing anonymous fingerprinting far nearer to practicality.
how to break another provably secure payment system. at euroctypt '94, stefano d'amiano and giovanni di crescenzo presented a protocol for untraceable electronic cash based on non-interactive zero-knowledge proofs of knowledge with preprocessing. it was supposed to be provably secure given this and a few other general cryptographic tools. we show that this protocol nevertheless does not provide any untraceability and has some further weaknesses. we also break another "provably secure" system proposed by di crescenzo at ciac 94. this is the second case of problems with "provably secure" payment systems. moreover, yet another system with this name tacitly solves a much weaker problem than the seminal paper by chaum, fiat, and naor and most other "practical" papers in this field (de santis and persiano, stacs 92). we therefore identify some principal problems with definitions and proofs of such schemes, and sketch better ways to handle them.
attacks on protocols for server-aided rsa computation. on crypto '88, matsumoto, kato, and imai presented protocols to speed up secret computations with insecure auxiliary devices. the two most important protocols enable a smart card to compute the secret rsa operation faster with the help of a server that is not necessarily trusted by the card holder. it was stated that if rsa is secure, the protocols could only be broken by exhaustive scarch in certain spacts. our main attacks show that much smaller search spaces suffice. these attacks are passive and therefore undetectable. it was already known that one of the protocols is vulnerable to active attacks. we show that this holds for the other protocol, too. more importantly, we show that our attack may still work if the smart card checks the correctness of the result; this was previously believed to be can easy measure excluding all active attacks. finally, we discuss attach on related protocols.
anonymous fingerprinting. fingerprinting schemes deter people from illegally redistributing digital data by enabling the original merchant of the data to identify the original buyer of a redistributed copy. recently, asymmetric fingerprinting schemes were introduced. here, only the buyer knows the fingerprinted copy after a sale, and if the merchant finds this copy somewhere, he obtains a proof that it was the copy of this particular buyer. a problem with all previous fingerprinting schemes arises in the context of electronic marketplaces where untraceable electronic cash offers buyers privacy similar to that when buying books or music in normal shops with normal cash. now buyers would have to identify themselves solely for the purpose of fingerprinting. to remedy this, we introduce and construct anonymous asymmetric fingerprinting schemes, where buyers can buy information anonymously, but can nevertheless be identified if they redistribute this information illegally. a subresult of independent interest is an asymmetric fingerprinting protocol with reasonable collusion tolerance and 2-party trials, which have several practical advantages over the previous 3-party trials. our results can also be applied to so-called traitor tracing, the equivalent of fingerprinting for broadcast encryption.
probabilistic analysis of elementary randimizers. in the paper, elementary randomizers based on random functions and the des structure are examined. first, it is proved that the randomizer with three different random functions produces the outputs which are independent and uniformly distributed random variables. next, randomizers based on two different random functions are considered and it is shown that their statistical properties depend upon the order of the functions used in them. finally, it is proved that the randomizer with a single random function gives outputs which are statistically related.
randomized authentication systems. in this work, the application of luby-rackoff randomizers for authentication purposes is examined. first randomized authentication codes are introduced. in these codes, the assignment of a cryptogram to a given message is done in two stages. in the first, the redundancy is introduced and in the second, the concatenation of several luby-rackoff randomizers is used. next, perfect a-codes are defined. the quality of the authentication codes (a-codes) is measured using the concept of distinguishing circuits. three a-codes with different redundancy stages are examined and proven that they are perfect if the suitable number of luby-rackoff randomizers is used in the second stage of the a-code.
fair secure two-party computation. we demonstrate a transformation of yao's protocol for secure two-party computation to a fair protocol in which neither party gains any substantial advantage by terminating the protocol prematurely. the transformation adds additional steps before and after the execution of the original protocol, but does not change it otherwise, and does not use a trusted third party. it is based on the use of gradual release timed commitments, which are a new variant of timed commitments, and on a novel use of blind signatures for verifying that the committed values are correct.
a new identification scheme based on the perceptrons problem. identification is a useful cryptographic tool. since zero-knowledge theory appeared [3], several interactive identification schemes have been proposed (in particular fiat-shamir [2] and its variants [8, 5, 4], schnorr [9]). these identifications are based on number theoretical problems. more recently, new schemes appeared with the peculiarity that they are more efficient from the computational point of view and that their security is based on np-complete problems: pkp (permuted kernels problem) [10], sd (syndrome decoding) [12] and cle (constrained linear equations) [13]. we present a new np-complete linear problem which comes from learning machines: the perceptrons problem. we have some constraints, m vectors xi of (-1, +1}n, and we want to find a vector v of (-1, +1}n such that xi ċ v ≥ 0 for all i. next, we provide some zero-knowledge interactive identification protocols based on this problem, with an evaluation of their security. eventually, those protocols are well suited for smart card applications.
new public key cryptosystems based on the dependent-rsa problems. since the diffie-hellman paper, asymmetric encryption has been a very important topic, and furthermore ever well studied. however, between the efficiency of rsa and the security of some less efficient schemes, no trade-off has ever been provided. in this paper, we propose better than a trade-off: indeed, we first present a new problem, derived from the rsa assumption, the "dependent-rsa problem". a careful study of its difficulty is performed and some variants are proposed, namely the "decisional dependent-rsa problem". they are next used to provide new encryption schemes which are both secure and efficient. more precisely, the main scheme is proven semantically secure in the standard model. then, two variants are derived with improved security properties, namely against adaptive chosen-ciphertext attacks, in the random oracle model. furthermore, all those schemes are more or less as efficient as the original rsa encryption scheme and reach semantic security.