waashk/dblp huggingface dataset:
some remarks on the cross correlation analysis of pseudo random generators. siegenthaler has shown how cross-correlation techniques can be applied to identify pseudo random generators consisting of linear feedback shift registers and a scrambling function [7]. these techniques may allow to attack one register in such a generator at a time. the original algorithm needs o(r2rn) operations to identify one register. (r denotes the length of the register examined, r the number of primitive polynomials of degree r. and n the minimal number of bits one has to observe). employing walsh-hadamard transform this analysis can be done in o(r(r2r+n)) operations [8]. we show that there exists a trade-off between the dimension of the hadamard matrix and the number of bits required to compute the cross correlation coefficients. the complexity of this attack is o(r(r2r-δ+2δn)). the integer δ can be selected so that the cost of the attack is minimized. the msr-generator will serve as an example to demonstrate our algorithm. furthermore we examine the correlation immunity of the s-boxes used in the des.
server (prover/signer)-aided verification of identity proofs and signatures. discrete log based identification and signature schemes are well-suited to identity proof and signature generation, but not suitable for verification, by smart cards, due to their highly asymmetric computational load between the prover/signer and the verifier. in this paper, we present very efficient and practical protocols for fast verification in these schemes, where the verifier with limited computing power performs its computation fast with the aid of the powerful prover/signer. the proposed protocols require very small amounts of computation and communication. the prover/signer only needs to perform a few modular exponentiations in real-time and the two interacting parties only need to communicate a few long numbers. using the proposed prover-aided verification (pav) protocol, the verifier can perform the schnorr-like identification scheme almost as fast as the guillou-quisquater scheme. we generalize the pav protocol into the signer-aided verification (sav) protocol, which can be used for verification of any public function.
a simpler construction of cca2-secure public-key encryption under general assumptions. in this paper we present a simpler construction of a publickey encryption scheme that achieves adaptive chosen ciphertext security (cca2), assuming the existence of trapdoor permutations. we build on previous works of sahai and de santis et al. and construct a scheme that we believe is the easiest to understand to date. in particular, it is only slightly more involved than the naor-yung encryption scheme that is secure against passive chosen-ciphertext attacks (cca1). we stress that the focus of this paper is on simplicity only.
a montgomery-suitable fiat-shamir-like authenication scheme. montgomery's algorithm [2] is a process for computing a b 2-|n| modulo n in o(log(n)) memory space. here we construct a fiat-shamir-like authentication scheme [1] suitable for montgomery environnments without introducing any overhead in the number of modular multiplications requested for the execution of the normal protocol. a very recent result [3] establishes (in a constructive way) that a b 2-|n|) mod n can be computed with the same complexity (timewise and hardwarewise) as a b (not mod n). this theoretical reduction of the problem of modular multiplication. recently applied to the design of today's fastest hardware modular multiplier, is very important since it implies that the protocol presented hereafter can be executed in the same time as a fiat-shamir where all modular multiplications are replaced by standard multiplications. the fact that no constants are to be precalculated beforehand and the small amount of ram requested for software implementation of the new protocol makes it highly convenient for smart-card applications.
a new public-key cryptosystem. this paper describes a new public-key cryptosystem where the ciphertext is obtained by multiplying the public-keys indexed by the message bits and the cleartext is recovered by factoring the ciphertext raised to a secret power. encryption requires four multiplications/byte and decryption is roughly equivalent to the generation of an rsa signature.
the sum of prps is a secure prf. given d independent pseudorandom permutations (prps) πi, ..., πd over {0; 1}n, it appears natural to define a pseudorandom function (prf) by adding (or xoring) the permutation results: sumd(x) = π1(x) ⊕...⊕πd(x). this paper investigates the security of sumd and also considers a variant that only uses one single prp over {0; 1}n.
a comparison of cryptoanalytic principles based on iterative error-correction. a cryptanalytic problem of a linear feedback shift register initial state reconstruction using a noisy output sequence is considered. the main underlying principles of three recently proposed cryptanalytic procedures based on the iterative error-correction are pointed out and compared.
distributed pseudo-random functions and kdcs. this work describes schemes for distributing between n servers the evaluation of a function f which is an approximation to a random function, such that only authorized subsets of servers are able to compute the function. a user who wants to compute f(x) should send x to the members of an authorized subset and receive information which enables him to compute f(x). we require that such a scheme is consistent, i.e. that given an input x all authorized subsets compute the same value f(x). the solutions we present enable the operation of many servers, preventing bottlenecks or single points of failure. there are also no single entities which can compromise the security of the entire network. the solutions can be used to distribute the operation of a key distribution center (kdc). they are far better than the known partitioning to domains or replication solutions to this problem, and are especially suited to handle users of multicast groups.
visual cryptography. in this paper we consider a new type of cryptographic scheme, which can decode concealed images without any cryptographic computations. the scheme is perfectly secure and very easy to implement. we extend it into a visual variant of the k out of n secret sharing problem, in which a dealer provides a transparency to each one of the n users; any k of them can see the image by stacking their transparencies, but any k-1 of them gain no information about it.
universal hash functions & hard core bits. in this paper we consider the bit-security of two types of universal hash functions: linear functions on gf[2n] and linear functions on the integers modulo a prime. we show individual security for all bits in the first case and for the o(log n) least significant bits in the second case. both types of functions are shown to have o(log n) simultaneous secure bits. for the second type of functions, primes of length ω(n) are needed. together with the goldreich-levin theorem, this shows that all the common types of universal hash functions provide so called hard-core bits.
software performance of universal hash functions. this paper compares the parameters sizes and software performance of several recent constructions for universal hash functions: bucket hashing, polynomial hashing, toeplitz hashing, division hashing, evaluation hashing, and mmh hashing. an objective comparison between these widely varying approaches is achieved by defining constructions that offer a comparable security level. it is also demonstrated how the security of these constructions compares favorably to existing mac algorithms, the security of which is less understood.
a new method for known plaintext attack of feal cipher. we propose a new known plaintext attack of feal cipher. our method differs from previous statistical ones in point of deriving the extended key in definite way. as a result, it is possible to break feal-4 with 5 known plaintexts and feal-6 with 100 known plaintexts respectively. moreover, we show a method to break feal-8 with 215 known plaintexts faster than an exhaustive search.
local randomness in candidate one-way functions. we call a distribution on n-bit strings (ɛ, e)-locally random, if for every choice of e ≤ n positions the induced distribution on e-bit strings is in the l1-norm at most ɛ away from the uniform distribution on e-bit strings. we establish local randomness in polynomial random number generators (rng) that are candidate one-way functions. let n be a squarefree integer and let f1, ..., fl be polynomials with coefficients in zn = z/nz. we study the rng that stretches a random x ɛ zn into the sequence of least significant bits of f1(x), ..., fl(x). we show that this rng provides local randomness if for every prime divisor p of n the polynomials f1,...,fl are linearly independent modulo the subspace of polynomials of degree ≤ 1 in zp[x]. we also establish local randomness in polynomial random function generators. this yields candidates for cryptographic hash functions. the concept of local randomness in families of functions extends the concept of universal families of hash functions by carter and wegman (1979). the proofs of our results rely on upper bounds for exponential sums.
new approaches to the design of self-synchronizing stream ciphers. self-synchronizing stream ciphers (sssc) are a commonly used encryption technique for channels with low bit error rate but for which bit synchronization can present a problem. most presently used such ciphers are based on a block cipher (e.g. des) in 1-bit cipher feedback mode. in this paper, several alternative design approaches for ssscs are proposed that are superior to the design based on a block cipher with respect to encryption speed and potentially also with respect to security. a method for combining several ssscs is presented that allows to prove that the combined sssc is at least as secure as any of the component ciphers. the problem of designing ssscs is contrasted with the problem of designing conventional synchronous additive stream ciphers and it is shown that different security criteria must be applied. furthermore, an efficient algorithm is presented for finding a function of low degree that approximates a given boolean function, if such an approximation exists. its significance for the cryptographic security of ssscs and its applications in coding theory are discussed.
a simplified and generalized treatment of luby-rackoff pseudorandom permutation generator. a paper by luby and rackoff on the construction of pseudorandom permutations from pseudorandom functions based on a design principle of the des has recently initiated a burst of research activities on applications and generalizations of these results. this paper presents a strongly simplified treatment of these results and generalizes them by pointing out the relation to locally random functions, thereby providing new insight into the relation between probability-theoretic and complexity-theoretic results in cryptography. the first asymptotically-optimal construction of a locally random function is presented and new design strategies for block ciphers based on these results are proposed.
perfect nonlinear s-boxes. a perfect nonlinear s-box is a substitution transformation with evenly distributed directional derivatives. since the method of differential cryptanalysis presented by e. biham and a. shamir makes use of nonbalanced directional derivatives, the perfect nonlinear s-boxes are immune to this attack. the main result is that for a perfect nonlinear s-box the number of input variables is at least twice the number of output variables. also two different construction methods are given. the first one is based on the maiorana-mcfarland construction of bent functions and is easy and efficient to implement. the second method generalizes dillon's construction of difference sets.
factoring with an oracle. the problem of factoring integers in polynomial time with the help of an (infinitely powerful) oracle who answers arbitrary questions with yes or no is considered. the goal is to minimize the number of oracle questions. let n be a given composite n-bit integer to be factored. the trivial method of asking for the bits of the smallest prime factor of n requires n/2 questions in the worst case. a non-trivial algorithm of rivest and shamir requires only n/3 questions for the special case where n is the product of two n/2-bit primes. in this paper, a polynomial-time oracle factoring algorithm for general integers is presented which, for any ɛ > 0, asks at most ɛn oracle questions for sufficiently large n. based on a conjecture related to lenstra's conjecture on the running time of the elliptic curve factoring algorithm it is shown that the algorithm fails with probability at most n-ɛ/2 for all sufficiently large n.
information-theoretically secure secret-key agreement by not authenticated public discussion. all information-theoretically secure key agreement protocols (e.g. based on quantum cryptography or on noisy channels) described in the literature are secure only against passive adversaries in the sense that they assume the existence of an authenticated public channel. the goal of this paper is to investigate information-theoretic security even against active adversaries with complete control over the communication channel connecting the two parties who want to agree on a secret key. several impossibility results are proved and some scenarios are characterized in which secret-key agreement secure against active adversaries is possible. in particular, when each of the parties, including the adversary, can observe a sequence of random variables that are correlated between the parties, the rate at which key agreement against active adversaries is possible is characterized completely: it is either 0 or equal to the rate achievable against passive adversaries, and the condition for distinguishing between the two cases is given.
the security of many-round luby-rackoff pseudo-random permutations. luby and rackoff showed how to construct a (super-)pseudo-random permutation {0, 1}2n → {0, 1}2n from some number r of pseudo-random functions {0, 1}n → {0, 1}n. their construction, motivated by des, consists of a cascade of r feistel permutations. a feistel permutation 1 for a pseudo-random function f is defined as (l,r) → (r,l⊕f(r)), where l and r are the left and right part of the input and ⊕ denotes bitwise xor or, in this paper, any other group operation on {0, 1}n. the only non-trivial step of the security proof consists of proving that the cascade of r feistel permutations with independent uniform random functions {0, 1}n → {0, 1}n, denoted ψ2nr, is indistinguishable from a uniform random permutation {0, 1}2n → {0, 1}2n by any computationally unbounded adaptive distinguisher making at most o(2cn) combined chosen plaintext/ciphertext queries for any c < α, where α is a security parameter. luby and rackoff proved α = 1/2 for r = 4. a natural problem, proposed by pieprzyk is to improve on α for larger r. the best known result, α = 3/4 for r = 6, is due to patarin. in this paper we prove α = 1- o(1/r), i.e., the trivial upper bound α = 1 can be approached. the proof uses some new techniques that can be of independent interest.
message recovery for signature schemes based on the discrete logarithm problem. the new signature scheme presented by the authors in [13] is the first signature scheme based on the discrete logarithm problem that gives message recovery. the purpose of this paper is to show that the message recovery feature is independent of the choice of the signature equation and that all elgamal-type schemes have variants giving message recovery. for each of the six basic elgamal-type signature equations five variants are presented with different properties regarding message recovery, length of commitment and strong equivalence. moreover, the six basic signature schemes have different properties regarding security and implementation. it turns out that the scheme proposed in [13] is the only inversionless scheme whereas the message recovery variant of the dsa requires computing of inverses in both generation and verification of signatures. in general, message recovery variants can be given for elgamal-type signature schemes over any group with large cyclic subgroup as the multiplicative group of gf(2n) or elliptic curve over a finite field.the present paper also shows how to integrate the dlp-based message recovery schemes with secret session key establishment and elgamal encryption. in particular, it is shown that with dlp-based schemes the same functionality as with rsa can be obtained. however, the schemes are not as elegant as rsa in the sense that the signature (verification) function cannot at the same time be used as the decipherment (encipherment) function.
information-theoretic key agreement: from weak to strong secrecy for free. one of the basic problems in cryptography is the generation of a common secret key between two parties, for instance in order to communicate privately. in this paper we consider information-theoretically secure key agreement. wyner and subsequently csiszár and körner described and analyzed settings for secret-key agreement based on noisy communication channels. maurer as well as ahlswede and csiszár generalized these models to a scenario based on correlated randomness and public discussion. in all these settings, the secrecy capacity and the secret-key rate, respectively, have been defined as the maximal achievable rates at which a highly-secret key can be generated by the legitimate partners. however, the privacy requirements were too weak in all these definitions, requiring only the ratio between the adversary's information and the length of the key to be negligible, but hence tolerating her to obtain a possibly substantial amount of information about the resulting key in an absolute sense. we give natural stronger definitions of secrecy capacity and secret-key rate, requiring that the adversary obtains virtually no information about the entire key. we show that not only secret-key agreement satisfying the strong secrecy condition is possible, but even that the achievable key-generation rates are equal to the previous weak notions of secrecy capacity and secret-key rate. hence the unsatisfactory old definitions can be completely replaced by the new ones. we prove these results by a generic reduction of strong to weak key agreement. the reduction makes use of extractors, which allow to keep the required amount of communication negligible as compared to the length of the resulting key.
enumerating nondegenerate permutations. every cryptosystem with an n-bit block length may be modeled as a system of n-bit boolean equations. the cipher is said to be nondegenerate if the equation fi that describes the output ci is nondegenerate, for 1 ≤ i ≤ n. let nn,n be the set of nondegenerate permutations. we will derive an exact expression for |nn,n|, and show that nn,n|/2n! = 1+o(√2n/22n-1+n).
non-interactive public-key cryptography. an identity-based non-interactive public key distribution system is presented that is based on a novel trapdoor one-way function allowing a trusted authority to compute the discrete logarithm of a given number modulo a publicly known composite number m while this is infeasible for an adversary not knowing the factorization of m. without interaction with a key distribution center or with the recipient of a given message a user can generate a mutual secure cipher key based solely on the recipient's identity and his own secret key and send the message, encrypted with the generated cipher key using a conventional cipher, over an insecure channel to the recipient. unlike in previously proposed identity-based systems, no public keys, certificates for public keys or other information need to be exchanged and thus the system is suitable for many applications such as electronic mail that do not allow for interaction.
convergence in differential distributions. differential cryptanalysis is a general attack based on the notion of differences. the success of the attack is derived from the probability of a differential. while it has been observed that the distribution of differentials can be modeled as a markov chain, there have been few analyses that take advantage of this observation because of the prohibitive computations involved. in this paper we apply the markov approach to the differentially 2-uniform mappings, and show that, they converge exponentially fast with high probability.
an analysis of exponentiation based on formal languages. a recoding rule for exponentiation is a method for reducing the cost of the exponentiation ae by reducing the number of required multiplications. if w(e) is the (hamming) weight of e, and e the result of applying the recoding rule a to e, then the purpose is to reduce wa(e) as compared to w(e). a well-known example of a recoding rule is to convert a binary exponent into a signed-digit representation in terms of the digits { 1;1; 0 } where 1 = -1, by recoding runs of 1's. in this paper we show how three recoding rules can be modelled via regular languages to obtain precise information about the resulting weight distributions. in particular we analyse the recoding rules employed by the 2k-ary, sliding window and optimal signed-digit exponentiation algorithms. we prove that the sliding window method has an expected recoded weight of approximately n/(k +1) for relevant k-bit windows and n-bit exponents, and also that the variance is small. we also prove for the optimal signed digit method that the expected weight is approximately n/3 with a variance of 2n/27. in general the sliding window method provides the best performance, and performs less than 85% of the multiplications required for the other methods for a majority of exponents.
suffix tree and string complexity. let s = (s1, s2, ..., sn) be a sequence of characters where si ɛ zp for 1 ≤ i ≤ n. one measure of the complexity of the sequence s is the length of the shortest feedback shift register that will generate s, which is known as the maximum order complexity of s [17, 18]. we provide a proof that the expected length of the shortest feedback register to generate a sequence of length n is less than 2 logp, n + o(1), and also give several other statistics of interest for distinguishing random strings. the proof is based on relating the maximum order complexity to a data structure known as a suflix tree.
communication security in remote controlled computer systems. nowadays remote controlled computer systems are in widespread use. several systems use the communication facilities offered by the public switched telephone network. in view of the public aspects of the network it is necessary that dial-up systems should have sufficient access security and communication security. in this paper it is proposed that this security be provided by the use of cryptography.
optimum secret sharing scheme secure against cheating. tompa and woll considered a problem of cheaters in (k, n) threshold secret sharing schemes. we first derive a tight lower bound on the size of shares |νi| for this problem: |νi|≥ (|s|-1)/δ+1, where νi denotes the set of shares of participant pi, s denotes thr set of secrets, and δ denotes the cheating probabilily. we next present an optimum scheme which meets the equality of our bound by using "difference sets."