waashk/dblp huggingface dataset:
extracting group signatures from traitor tracing schemes. digital signatures emerge naturally from public-key encryption based on trapdoor permutations, and the "duality" of the two primitives was noted as early as diffie-hellman's seminal work. the present work is centered around the crucial observation that two well known cryptographic primitives whose connection has not been noticed so far in the literature enjoy an analogous "duality." the primitives are group signature schemes and public-key traitor tracing. based on the observed "duality," we introduce new design methodologies for group signatures that convert a traitor tracing scheme into its "dual" group signature scheme. our first methodology applies to generic public-key traitor tracing schemes. we demonstrate its power by applying it to the boneh-franklin scheme, and obtaining its "dual" group signature. this scheme is the first provably secure group signature scheme whose signature size is not proportional to the size of the group and is based only on ddh and a random oracle. the existence of such schemes was open. our second methodology introduces a generic way of turning any group signature scheme with signature size linear in the group size into a group signature scheme with only logarithmic dependency on the group size. to this end it employs the notion of traceability codes (a central component of combinatorial traitor tracing schemes already used in the first such scheme by chor, fiat and naor). we note that our signatures, obtained by generic transformations, are proportional to a bound on the anticipated maximum malicious coalition size. without the random oracle assumption our schemes give rise to provably secure and efficient identity escrow schemes.
unbalanced oil and vinegar signature schemes. in [16], j. patarin designed a new scheme, called "oil and vinegar", for computing asymmetric signatures. it is very simple, can be computed very fast (both in secret and public key) and requires very little ram in smartcard implementations. the idea consists in hiding quadratic equations in n unknowns called "oil" and v = n unknowns called "vinegar" over a finite field k, with linear secret functions. this original scheme was broken in [10] by a. kipnis and a. shamir. in this paper, we study some very simple variations of the original scheme where v > n (instead of v = n). these schemes are called "unbalanced oil and vinegar" (uov), since we have more "vinegar" unknowns than "oil" unknowns. we show that, when v ≃ n, the attack of [10] can be extended, but when v ≥ 2n for example, the security of the scheme is still an open problem. moreover, when v ≃ n2/2, the security of the scheme is exactly equivalent (if we accept a very natural but not proved property) to the problem of solving a random set of n quadratic equations in n2/2 unknowns (with no trapdoor). however, we show that (in characteristic 2) when v ≥ n2, finding a solution is generally easy. then we will see that it is very easy to combine the oil and vinegar idea and the hfe schemes of [14]. the resulting scheme, called hfev, looks at the present also very interesting both from a practical and theoretical point of view. the length of a uov signature can be as short as 192 bits and for hfev it can be as short as 80 bits.
discrete logarithm based protocols. the exponential security system (tess) developed at the european institute for system security is the result of an attempt to increase the security in heterogenous computer networks. in this paper we present the cryptographic protocols in the kernel of tess. we show how they can be used to implement access control, authentication, confidentiality protection, key exchange, digital signatures and distributed network security management. we also look at the compatibility of tess with existing standards, like the x.509 directory authentication framework, and compare it to established systems like kerberos. a comparison of tess with the non-electronic "paper"-world of authentication and data exchange shows strong parallels. finally we give a short overview of the current state of development and availability of different tess components.
large periods nearly de bruijn fcsr sequences. recently, a new class of feedback shift registers (fcsrs) was introduced, based on algebra over the 2-adic numbers. the sequences generated by these registers have many algebraic properties similar to those generated by linear feedback shift registers. however, it appears to be significantly more difficult to find maximal period fcsr sequences. in this paper we exhibit a technique for easily finding fcsrs that generate nearly maximal period sequences. we further show that these sequence have excellent distributional properties. they are balanced, and nearly have the debruijn property for distributions of subsequences.
some considerations concerning the selection of rsa moduli. in this contribution two conditions are stated which safe rsa moduli n = pċq must fulfill. otherwise the factors of n can be found. first we consider the cycle-lengths of the recursion c ← cφv;(n)-1 +1 mod n which leads to a condition in terms of fibonacci numbers. the second condition involves a property of euler's function. we introduce a number-theoretic distance measure - the power-of-two distance (ptd) - which may be useful for evaluating the security of rsa moduli against 'number-theoretic integration'. the ptd of an rsa prime p must not be too small.
cryptanalysis of an identification scheme based on the permuted perceptron problem. this paper describes an attack on an identification scheme based on the permuted perceptron problem (ppp) as suggested by point-cheval. the attack finds the secret key, a vector of n binary elements, in time much faster than estimated by its designer. the basic idea in the attack is to use several applications of a simulated annealing algorithm and combine the outcomes into an improved search. it is left as an open problem to what extent the methods developed in this paper are useful also in other combinatorial problems.
a new algorithm for the solution of the knapsack problem. a new algorithm for the solution of the knapsack problem is described. the algorithm is based upon successive reductions modulo suitably chosen integers. thus the original knapsack problem is transformed into a system of modified knapsack problems. very often a partial solution to the system can be found. the system and the original knapsack can then be reduced to a lower dimensionality and the algorithm repeated. so far we have not been able to characterize the class of knapsack problems for which the algorithm is effective. there are indications, however, that most knapsack problems for which we know that there is one and only one solution may be solved fast by the use of the new algorithm.
on the difficulty of software key escrow. at eurocrypt'95, desmedt suggested a scheme which allows individuals to encrypt in such a way that the receiver can be traced by an authority having additional information. this paper shows that the proposed scheme does not have the required properties, by devising three non-specified protocols misleading the authority. we also discuss how to repair desmedt's scheme, such that our attacks are no longer possible. however, by allowing slightly more general, but absolutely realistic attacks also this improved system can be broken. in fact, we argue that software key escrow as proposed by desmedt will be very hard to implement as it requires that the distributed public key can only be used in few, well-defincd systems. furthermore, even if this is achieved, most applications to key distribution can be broken.
non-linear approximations in linear cryptoanalysis. by considering the role of non-linear approximatioris in linear cryptanalysis we obtain a generalization of matsui's linear cryptanalytic techniques. this approach allows ihe cryptanalyst greater flexibility in mounting a linear cryptanalytic attack and we demonstrate the effectiveness of our non-linear techniques with some simple attacks on lok191. these attacks potentially allow for the recovery of seven additional bits of key information with less than 1/4 of the plaintext that is required using current linear cryptanalytic methods.
cryptoanalysis of mceliece's public-key cryptosystem. an approach is proposed for the cryptanalysis of the well-known version of mceliece's public-key cryptosystem that is based on a new iterative optimization algorithm for decoding an arbitrary linear code. the algorithm provides guaranteed correction of all error patterns with hamming weight less than d/2, where d is the minimum distance of the code, and has time complexity about o(n3) where n is the block length. the approach is illustrated by the cryptanalysis of mceliece's system when a (63, 36) binary code with d = 11 is the underlying linear code.
fast elliptic curve algorithm combining frobenius map and table reference to adapt to higher characteristic. a new elliptic curve scalar multiplication algorithm is proposed. the algorithm offers about twice the troughput of some conventional oef-base algorithms because it combines the frobenius map with the table reference method based on base-φ expansion. furthermore, since this algorithm suits conventional computational units such as 16, 32 and 64 bits, its base field fpm is expected to enhance elliptic curve operation efficiency more than fq (q is a prime) or f2n.
high-speed implementation methods for rsa scheme. this paper proposes two novel implementation methods for the rsa cryptographic scheme. (1) the most efficient rsa implementation known to the present authors. this implementation achieves 50 kbps at about 25 kgates for a 512-bit exponent e and a 512-bit modulus n. thus the efficiency is 2.0 bps/gate. (2) a systolic architecture useful for high-speed and efficient and flexible chip implementation of the rsa scheme.
secure conference key distribution schemes for conspiracy attack. at the eurocrypt'88 meeting, we proposed three identity-based conference key distribution schemes. at the asiacrypt'91 meeting, shimbo and kawamura presented a conspiracy attacking method which worked against our schemes to disclose a user's secret information. this paper proposes an improved identity-based conference key distribution scheme to counter this attack.
ripping coins for a fair exchange. a fair exchange of payments for goods and services is a barter where one of the parties cannot obtain the item desired without handing over the item he offered. we introduce the concept of ripping digital coins to solve fairness problems in payment transactions. we demonstrate how to implement coin ripping for a recently proposed payment scheme [9, 8], giving a practical and transparent coin ripping scheme. we then give a general solution that can be used in any payment scheme with a challenge. we also indicate how fairness can be obtained by building a contract into the coin.
new hash functions for message authentication. we show that toeplitz matrices generated by sequences drawn from small biased distributions provide hashing schemes applicable to secure message authentication. this work extends our previous results from crypto'94 [4] where an authentication scheme based on toeplitz matrices generated by linear feedback shift registers was presented. our new results have as special case the lfsr-based construction but extend to a much wider and general family of sequences, including several simple and efficient constructions with close to optimal security. examples of the new constructions include toeplitz matrices generated by the legendre symbols of consecutive integers modulo a prime (of size significantly shorter than required by public-key modular arithmetic) as well as other algebraic constructions. the interest of these schemes extends beyond the proposed cryptographic applications to other uses of universal hashing (including other cryptographic applications).
designated verifier proofs and their applications. for many proofs of knowledge it is important that only the verifier designated by the confirmer can obtain any conviction of the correctness of the proof. a good example of such a situation is for undeniable signatures, where the confirmer of a signature wants to make sure that only the intended verifier(s) in fact can be convinced about the validity or invalidity of the signature. generally, authentication of messages and off-the-record messages are in conflict with each other. we show how, using designation of verifiers, these notions can be combined, allowing authenticated but private conversations to take place. our solution guarantees that only the specified verifier can be convinced by t,he proof, even if he shares all his secret information with entities that want to get convinced. our solution is based on trap-door conim.itments [4], allowing the designated verifier to open up commitments in any way he wants. we demonstrate how a trap-door commitment scheme can be uscd to construct designated verifier proofs, both interactive and non-interactive. we examplify the verifier designation method for the confirmation protocol for undeniable signatures.
distributed "magic ink" signatures. the physical analog of "blind signatures" of chaum is a document and a carbon paper put into an envelope, allowing the signer to transfer his signature onto the document by signing on the envelope, and without opening it. only the receiver can present the signed document while the signer cannot "unblind" its signature and get the document signed. when an authority signs "access tokens", "electronic coins", "credentials" or "passports", it makes sense to assume that whereas the users can typically enjoy the disassociation of the blindly signed token and the token itself (i.e. anonymity and privacy), there may be cases which require "unblinding" of a signature by the signing authority itself (to establish what is known as "audit trail" and to "revoke anonymity" in case of criminal activity). this leads us to consider a new notion of signature with the following physical parallel: the signer places a piece of paper with a carbon paper on top in an envelope as before (but the document on the paper is not yet written). the receiver then writes the document on the envelope using magic ink, e.g., ink that is only visible after being "developed". due to the carbon copy, this results in the document being written in visible ink on the internal paper. then, the signer signs the envelope (so its signature on the document is made available). the receiver gets the internal paper and the signer retains the envelope with the magic ink copy. should the signer need to unblind the document, he can develop the magic ink and get the document copy on the envelope. note that the signing is not blinded forever to the signer. we call this new type of signature a magic ink signature. we present an efficient method for distributively generating magic ink signatures, requiring a quorum of servers to produce a signature and a (possibly different) quorum to unblind a signature. the scheme is robust, and the unblinding is guaranteed to work even if a set of up to a threshold of signers refuses to cooperate, or actively cheats during either the signing or the unblinding protocol. we base our specific implementation on the dss algorithm. our construction demonstrates the extended power of distributed signing.
almost k-wise independent sample spaces and their cryptologic applications. an almost k-wise independent sample space is a small subset of m bit sequences in which any k bits are "almost independent". we show that this idea has close relationships with useful cryptologic notions such as multiple authentication codes (multiple a-codes), almost strongly universal hash families and almost k-resilient functions. we use almost k-wise independent sample spaces to construct new efficient multiple a-codes such that the number of key bits grows linearly as a function of k (here k is the number of messages to be authenticated with a single key). this improves on the construction of atici and stinson [2], in which the number of key bits is ω(k2). we also introduce the concept of ɛ-almost k-resilient functions and give a construction that has parameters superior to k-resilient functions. finally, new bounds (necessary conditions) are derived for almost k-wise independent sample spaces, multiple a-codes and balanced ɛ-almost k- resilient functions.
combinatorial bounds for authentication codes with arbitration. unconditionally secure authentication codes with arbitration (a2-codes) protect against deceptions from the transmitter and the receiver as well as that from the opponent. in this paper, we present combinatorial lower bounds on the cheating probabilities for a2-codes in terms of the number of source states, that of the whole messages and that of messages which the receiver accepts as authentic for each source state. previously, only entropy based lower bounds were known. our bounds for the model without secrecy are tight because the a2-codes given by johansson meet our bounds with equality.
design of sac/pc(l) of order k boolean functions and three other cryptographic criteria. a boolean function f satisfies pc(l) of order k if f(x) ⊕ f(x ⊕ α)is balanced for any α such that 1 ≤ w(α) ≤ l even if any k input bits are kept constant, where w(α) denotes the hamming weight of α. this paper shows the first design method of such functions which provides deg(f) ≥ 3. more than that, we show how to design "balanced' such functions. high nonlinearity and large degree are also obtained. further, we present balanced sac(k) functions which achieve the maximum degree. finally, we extend our technique to vector output boolean functions.
one-way trapdoor permutations are sufficient for non-trivial single-server private information retrieval. we show that general one-way trapdoor permutations are sufficient to privately retrieve an entry from a database of size n with total communication complexity strictly less than n. more specifically, we present a protocol in which the user sends o(k2) bits and the server sends n - cn/k bits (for any constant c), where k is the security parameter of the trapdoor permutations. thus, for sufficiently large databases (e.g., when k = nɛ for some small ɛ) our construction breaks the information-theoretic lower-bound (of at least n bits). this demonstrates the feasibility of basing single-server private information retrieval on general complexity assumptions. an important implication of our result is that we can implement a 1-out-of- n oblivious transfer protocol with communication complexity strictly less than n based on any one-way trapdoor permutation.
dealing necessary and sufficient numbers of cards for sharing a one-bit secret key. using a random deal of cards to players and a computationally unlimited eavesdropper, all players wish to share a one-bit secret key which is information-theoretically secure from the eavesdropper. this can be done by a protocol to make several pairs of players share one-bit secret keys so that all these pairs form a spanning tree over players. in this paper we obtain a necessary and sufficient condition on the number of cards for the existence of such a protocol. our condition immediately yields an efficient linear-time algorithm to determine whether there exists a protocol to achieve such a secret key sharing.
hash function based on block ciphers. iterated hash functions based on block ciphers are treated. five attacks on an iterated hash function and on its round function are formulated. the wisdom of strengthening such hash functions by constraining the last block of the message to be hashed is stressed. schemes for constructing m-bit and 2m-bit hash round functions from m-bit block ciphers are studied. a principle is formalized for evaluating the strength of hash round functions, viz., that applying computationally simple (in both directions) invertible transformations to the input and output of a hash round function yields a new hash round function with the same security. by applying this principle, four attacks on three previously proposed 2m-bit hash round functions are formulated. finally, three new hash round functions based on an m-bit block cipher with a 2m-bit key are proposed.
a block lanczos algorithm for finding dependencies over gf(2). some integer factorization algorithms require several vectors in the null space of a sparse m × n matrix over the field gf(2). we modify the lanczos algorithm to produce a sequence of orthogonal subspaces of gf(2)n, each having dimension almost n, where n is the computer word size, by applying the given matrix and its transpose to n binary vectors at once. the resulting algorithm takes about n/(n - 0.76) iterations. it was applied to matrices larger than 106 × 106 during the factorizations of 105-digit and 119-digit numbers via the general number field sieve.
cryptanalysis of the public-key encryption based on braid groups. at crypto 2000, a new public-key encryption based on braid groups was introduced. this paper demonstrates how to solve its underlying problem using the burau representation. by this method, we show that the private-key can be recovered from the public-key for several parameters with significant probability in a reasonable time. our attack can be mounted directly on the revised scheme mentioned at asiacrypt 2001 as well. on the other hand, we give a new requirement for secure parameters against our attack, which more or less conflicts with that against brute force attack.
analysis and optimization of the twinkle factoring device. we describe an enhanced version of the twinkle factoring device and analyse to what extent it can be expected to speed up the sieving step of the quadratic sieve and number field sieve factoring algorithms. the bottom line of our analysis is that the twinkle-assisted factorization of 768-bit numbers is difficult but doable in about 9 months (including the sieving and matrix parts) by a large organization which can use 80,000 standard pentium ii pc's and 5,000 twinkle devices.
counting points on elliptic curves over finite fields of small characteristic in quasi quadratic time. let p be a small prime and q = pn. let e be an elliptic curve over fq. we propose an algorithm which computes without any preprocessing the j-invariant of the canonical lift of e with the cost of o(log n) times the cost needed to compute a power of the lift of the frobenius. let µ be a constant so that the product of two n-bit length integers can be carried out in o(nµ) bit operations, this yields an algorithm to compute the number of points on elliptic curves which reaches, at the expense of a o(n5/2) space complexity, a theoretical time complexity bound equal to o(nmax(1.19,µ)+µ+1/2log n). when the field has got a gaussian normal basis of small type, we obtain furthermore an algorithm with o(log(n)n2µ) time and o(n2) space complexities. from a practical viewpoint, the corresponding algorithm is particularly well suited for implementations. we outline this by a 100002-bit computation.
counting the number of points on elliptic curves over finite fields: strategies and performance. cryptographic schemes using elliptic curves over finite fields require the computation of the cardinality of the curves. dramatic progress have been achieved recently in that field by various authors. the aim of this article is to highlight part of these improvements and to describe an efficient implementation of them in the particular case of the fields gf(2n), for n ≤ 600.
dickson pseudoprimes and primality testing. the paper gives a general definition for the concept of strong dickson pseudoprimes which contains as special cases the carmichael numbers and the strong fibonacci pseudoprimes. furthermore, we give necessary and sufficient conditions for two important classes of strong dickson pseudoprimes and deduce some properties for their elements. a suggestion of how to improve a primality test by baillie&wagstaff concludes the paper.