waashk/dblp huggingface dataset:
towards fast correlation attacks on irregularly clocked shift registers. a theoretical framework for fast correlation attacks on irregularly clocked linear feedback shift registers (lfsrs) based on a recently established linear statistical weakness of decimated lfsr sequences is developed. when the lfsr feedback polynomial is not known, methods for the statistical weakness detection and the feedback polynomial reconstruction are proposed. when the lfsr feedback polynomial is known, an iterative procedure for fast lfsr initial state reconstruction given an observed keystream sequence is introduced. the procedure is based on appropriately defmed parity-check sums and consists in iterative recomputation of the posterior probabilities for unknown elements of the decimation sequence. a convergence condition in terms of the numbers of the parity-check sums needed for successful reconstruction and the required polynomial computational complexity indicate that the proposed fast correlation attack may be realistic, especially in the constrained clocking case. the number of the feedback polynomial multiples of relatively low weight and not too large degree thus proves to be critical for the security of irregularly clocked lfsrs.
fast low order approximation of cryptographic functions. a fast and efficient procedure for finding low order approximations to large boolean functions, if such approximations exist, is developed. the procedure uses iterative error-correction algorithms for fast correlation attacks on certain stream ciphers and is based on representing low order boolean functions by appropriate linear recurring sequences generated by binary filter generators. applications and significance of the proposed method in thc analysis and design of block and stream ciphers are also discussed.
a generalized correlation attack with a probabilistic constrained edit distance. for a noisy clock-controlled shift register statistically optimal probabilistic constrained edit distance a recursive algorithm for its efficient computation are derived. corresponding generalized correlation attack is proposed.
are big s-boxes best? various probabilities of accidental linearities occurring in a random, reversible substitution lookup table (s-box) with m address and m contents bits are calculated. these probabilities decrease very dramatically with increasing m. it is conjectured that good s-boxes may be built by choosing a random, reversible table of sufficient size.
the maximum order complexity of sequence ensembles. in this paper we extend the theory of maximum order complexity from a single sequence to an ensemble of sequences. in particular, the maximum order complexity of an ensemble of sequences is defined and its properties discussed. also, an algorithm is given to determine the maximum order complexity of an ensemble of sequences linear in time and memory. it is also shown how to determine the maximum order feedback shift register equivalent of a given ensmble of sequences, i.e. including a feedback function. hence, the problem of finding the absolutely shortest (possibly nonlinear) feedback shift register, that can generate two or more given sequences with characters from some arbitrary finite alphabet, is solved. finally, the consequences for sequence prediction based on the minimum number of observations are discussed.
adaptively secure threshold cryptography: introducing concurrency, removing erasures. we put forward two new measures of security for threshold schemes secure in the adaptive adversary model: security under concurrent composition; and security without the assumption of reliable erasure. using novel constructions and analytical tools, in both these settings, we exhibit efficient secure threshold protocols for a variety of cryptographic applications. in particular, based on the recent scheme by cramer-shoup, we construct adaptively secure threshold cryptosystems secure against adaptive chosen ciphertext attack under the ddh intractability assumption. our techniques are also applicable to other cryptosystems and signature schemes, like rsa, dss, and elgamal. our techniques include the first efficient implementation, for a wide but special class of protocols, of secure channels in erasure-free adaptive model. of independent interest, we present the notion of a committed proof.
a chosen messages attack on the iso/iec 9796-1 signature scheme. we introduce an attack against the iso/iec 9796-1 digital signature scheme using redundancy, taking advantage of the multiplicative property of the rsa and rabin cryptosystems. the forged signature of 1 message is obtained from the signature of 3 others for any public exponent v. for even v, the modulus is factored from the signature of 4 messages, or just 2 for v = 2. the attacker must select the above messages from a particular message subset, which size grows exponentialy with the public modulus bit size. the attack is computationally inexpensive, and works for any modulus of 16z, 16z ± 1, or 16z ± 2 bits. this prompts the need to revise iso/iec 9796-1, or avoid its use in situations where an adversary could obtain the signature of even a few mostly chosen messages.
bucket hashing with a small key size. in this paper we consider very fast evaluation of strongly universal hash functions, or equivalently, authentication codes. we show how it is possible to modify some known families of hash functions into a form such that the evaluation is similar to "bucket hashing", a technique for very fast hashing introduced by rogaway. rogaway's bucket, hash family has a huge key size, which for common parameter choices can be more than a hundred thousand bits. the proposed hash families have a key size that is close to the key size of the theoretically best known constructions, typically a few hundred bits, and the evaluation has a time complexity that is similar to bucket hashing.
improved fast correlation attacks on stream ciphers via convolutional codes. this paper describes new methods for fast correlation attacks, based on the theory of convolutional codes. they can be applied to arbitrary lfsr feedback polynomials, in opposite to the previous methods, which mainly focus on feedback polynomials of low weight. the results improve significantly the few previous results for this general case, and are in many cases comparable with corresponding results for low weight feedback polynomials.
alternating step generators controlled by de bruijn sequences. the alternating step generator (asg) is a new generator of pseudo-random sequences which is closely related t o the stop-and-go generator. it shares all the good properties of this latter generator without posessing its weaknesses. the asg consists of three subgenerators k, m, and m. the main characteristic of its structure is that the output of one of the subgenerators, k, controls the clock of the two others, m and m. in the present contribution, we determine the period, the distribution of short patterns and a lower bound for the linear complexity of the sequences generated by an asg. the proof of the lower bound is greatly simplified by assuming that k generates a de bruijn sequence. under this and other not very restrictive assumptions the period and the linear complexity are found to be proportional to the period of the de bruijn sequence. furthermore the frequency of all short patterns as well as the autocorrelations turn out to be ideal. this means that the sequences generated by the asg are provably secure against the standard attacks.
cryptanalysis of the emd mode of operation. in this paper, we study the security of the encrypt-mask-decrypt mode of operation, also called emd, which was recently proposed for applications such as disk-sector encryption. the emd mode transforms an ordinary block cipher operating on n-bit blocks into a tweakable block cipher operating on large blocks of size nm bits. we first show that emd is not a secure tweakable block cipher and then describe efficient attacks in the context of disk-sector encryption. we note that the parallelizable variant of emd, called eme that was proposed at the same time is also subject to these attacks. in the course of developing one of the attacks, we revisit wagner's generalized birthday algorithm and show that in some special cases it performs much more efficiently than in the general case. due to the large scope of applicability of this algorithm, even when restricted to these special cases, we believe that this result is of independent interest.
analysis of multiple access channel using multiple level fsk. for multiple level fsk system of multiple user communication a model is considered containing independent parallel noisy or channels. the error probability is calculated if a random block code and a majority type decoding rule is applied.
a secret key cryptosystem by iterating a chaotic map. chaos is introduced to cryptology. as an example of the applications, a secret key cryptosystem by iterating a one dimensional chaotic map is proposed. this system is based on the characteristics of chaos, which are sensitivity of parameters, sensitivity of initial points, and randomness of sequences obtained by iterating a chaotic map. a ciphertext is obtained by the iteration of a inverse chaotic map from an initial point, which denotes a plaintext. if the times of the iteration is large enough, the randomness of the encryption and the decryption function is so large that attackers cannot break this cryptosystem by statistic characteristics. in addition to the security of the statistical point, even if the cryptosystem is composed by a tent map, which is one of the simplest chaotic maps, setting a finite computation size avoids a ciphertext only attack. the most attractive point of the cryptosystem is that the cryptosystem is composed by only iterating a simple calculations though the information rate of the cryptosystem is about 0.5.
on the optimality of linear, differential, and sequential distinguishers. in this paper, we consider the statistical decision processes behind a linear and a differential cryptanalysis. by applying techniques and concepts of statistical hypothesis testing, we describe precisely the shape of optimal linear and differential distinguishers and we improve known results of vaudenay concerning their asymptotic behaviour. furthermore, we formalize the concept of "sequential distinguisher" and we illustrate potential applications of such tools in various statistical attacks.
comparing the mov and fr reductions in elliptic curve cryptography. this paper addresses the discrete logarithm problem in elliptic curve cryptography. in particular, we generalize the menezes, okamoto, and vanstone (mov) reduction so that it can be applied to some non-supersingular elliptic curves (ecs); decrypt frey and rück (fr)'s idea to describe the detail of the fr reduction and to implement it for actual elliptic curves with finite fields on a practical scale; and based on them compare the (extended) mov and fr reductions from an algorithmic point of view. (this paper has primarily an expository role.)
encryption modes with almost free message integrity. we define a new mode of operation for block ciphers which, in addition to providing confidentiality, also ensures message integrity. in contrast, previously for message integrity a separate pass was required to compute a cryptographic message authentication code (mac). the new mode of operation, called integrity aware parallelizable mode (iapm), requires a total of m+1 block cipher evaluations on a plain-text of length m blocks. for comparison, the well-known cbc (cipher block chaining) encryption mode requires m block cipher evaluations, and the second pass of computing the cbc-mac essentially requires additional m+1 block cipher evaluations. as the name suggests, the new mode is also highly parallelizable.
public-key cryptosystems with very small key length. in some applications of public-key cryptography it is desirable, and perhaps even necessary, that the key size be as small as possible. moreover, the cryptosystem just needs to be secure enough so that breaking it is not cost-effective. the purpose of this paper is to hivestigate the security and practicality of elliptic curve cryptosystems with small key sizes of about 100 bits.
a generalization of linear cryptanalysis and the applicability of matsui's piling-up lemma. matsui's linear cryptanalysis for iterated block ciphers is generalized by replacing his linear expressions with i/o sums. for a single round, an i/o sum is the xor of a balanced binary-valued function of the round input and a balanced binary-valued function of the round output. the basic attack is described and conditions for it to be successful are given. a procedure for finding effective i/o sums, i.e., i/o sums yielding successful attacks, is given. a cipher contrived to be secure against linear cryptanalysis but vulnerable to this generalization of linear cryptanalysis is given. finally, it is argued that the ciphers idea and safer k-64 are secure against this generalization.
nearly one-sided tests and the goldreich-levin predicate. we study statistical tests with binary output that rarely outputs one, which we call nearly one-sided statistical tests. we provide an efficient reduction establishing improved security for the goldreich-levin hard-core bit against nearly one-sided tests. the analysis is extended to prove the security of the blum-micali pseudo-random generator combined with the goldreich-levin bit. furthermore, applications where nearly one-sided tests naturally occur are discussed. this includes cryptographic constructions that replace real randomness with pseudo-randomness and where the adversary's success easily can be verified. in particular, this applies to signature schemes that utilize a pseudo-random generator as a provider of randomness.
efficient and non-malleable proofs of plaintext knowledge and applications. we describe efficient protocols for non-malleable (interactive) proofs of plaintext knowledge for the rsa, rabin, paillier, and el gamal encryption schemes. we also highlight some important applications of these protocols: - chosen-ciphertext-secure, interactive encryption. in settings where both parties are on-line, an interactive encryption protocol may be used. we construct chosen-ciphertext-secure interactive encryption schemes based on any of the schemes above. in each case, the improved scheme requires only a small overhead beyond the original, semantically-secure scheme. - password-based authenticated key exchange. we derive efficient protocols for password-based key exchange in the public-key model [28, 5] whose security may be based on any of the cryptosystems mentioned above. - deniable authentication. our techniques give the first efficient constructions of deniable authentication protocols based on, e.g., the rsa or computational diffie-hellman assumption. of independent interest, we consider the concurrent composition of proofs of knowledge; this is essential to prove security of our protocols when run in an asynchronous, concurrent environment.
xor and non-xor differential probabilities. differential cryptanalysis is a well-known attack on iterated ciphers whose success is determined by the probability of predicting sequences of differences from one round of the cipher to the next. the notion of difference is typically defined with respect to the group operation (s) used to combine the subkey in the round function f. for a given round operation π of f, such as an s-box, let dp⊗(π) denote the probability of the most likely non-trivial difference for π when differences are defined with respect to ⊗. in this paper we investigate how the distribution of dp⊗(π) varies as the group operation ⊗ is varied when π is a uniformly selected permutation. we prove that dp⊗(π) is maximised with high probability when differences are defined with respect to xor.
round efficiency of multi-party computation with a dishonest majority. we consider the round complexity of multi-party computation in the presence of a static adversary who controls a majority of the parties. here, n players wish to securely compute some functionality and up to n - 1 of these players may be arbitrarily malicious. previous protocols for this setting (when a broadcast channel is available) require o(n) rounds. we present two protocols with improved round complexity: the first assumes only the existence of trapdoor permutations and dense cryptosystems, and achieves round complexity o(log n) based on a proof scheduling technique of chor and rabin [13]; the second requires a stronger hardness assumption (along with the non-black-box techniques of barak [2]) and achieves o(1) round complexity.
secure audio teleconferencing: a practical solution. secure audio teleconferencing is a multi-point communication service which uses encryption to prevent eavesdroppers from listening to the speech signals. its greatest vulnerability is the audio bridge - that component which combines the conferees' speech signals and returns the result to them. a new secure teleconferencing system is proposed here. it fits the public telephone network by eliminating the need for the conferees to share their secrete with the bridge. it combines a simplified ('instantaneous') bridging technique with secure bridging ideas previously suggested in the literature, overcoming their main practical disadvantages. in particular, it is not restricting the audio signals to be coded by linear pcm, a technique which is wasteful in terms of bit-rate. rather, it enables the use of conventional µ-law and a-law pcm, as well as vector quantized pcm, thus can be used with a conventional 64kb/s digital channel.
a note on discrete logorithms with special structure. many cryptographic systems assume the computational difficulty of the discrete logarithm (dl) problem. in order to accelerate such practical systems, it was proposed to use logarithms of special structure, such as small hamming weight. how difficult is the underlying restricted dl problem? by rephrasing shanks' method we provide a close to square-root algorithm for such problems.
on using prime polynomials in crypto generators. in this note a primality test for polynomials over a finite field is analyzed. it is particularly well suited to achieve fast computations in the binary case. lots of prime polynomials which do not have to possess the maximum length property can be easily accessed by means of the best. examples of binary polynomials generated through the use of the test are given for degrees from 35 up to 55. the computational requirements are compared with a related test for maximum length and also with some common factorization procedures. as main application the use of prime polynomials in certain crypto geenrators is considered. the acm portal is published by the association for computing machinery. copyright © 2010 acm, inc. terms of usage privacy policy code of ethics contact us useful downloads: adobe acrobat quicktime windows media player real player
cox-rower architecture for fast parallel montgomery multiplication. this paper proposes a fast parallel montgomery multiplication algorithm based on residue number systems (rns). it is easy to construct a fast modular exponentiation by applying the algorithm repeatedly. to realize an efficient rns montgomery multiplication, the main contribution of this paper is to provide a new rns base extension algorithm. cox-rower architecture described in this paper is a hardware suitable for the rns montgomery multiplication. in this architecture, a base extension algorithm is executed in parallel by plural rower units controlled by a cox unit. each rower unit is a single-precision modular multiplier-and-accumulator, whereas cox unit is typically a 7 bit adder. although the main body of the algorithm processes numbers in an rns form, efficient procedures to transform rns to or from a radix representation are also provided. the exponentiation algorithm can, thus, be adapted to an existing standard radix interface of rsa cryptosystem.
the ghs attack revisited. we generalize the weil descent construction of the ghs attack to arbitrary artin-schreier extensions. we give a formula for the characteristic polynomial of frobenius of the obtained curves and prove that the large cyclic factor of the input elliptic curve is not contained in the kernel of the composition of the conorm and norm maps. as an application we almost square the number of elliptic curves which succumb to the basic ghs attack, thereby weakening curves over f2155 further. we also discuss other possible extensions or variations of the ghs attack and conclude that they are not likely to yield further improvements.
how to make efficient fail-stop signatures. fail-stop signatures (introduced in [wp89]) have the very nice property that the signer is secure against unlimited powerful forgers. however, the known fail-stap signatures require very long keys, and they are quite inefficient, because messages are signed bit-wise. this paper presents a fail-stop signature scheme, in which signing a message block requires two modular multiplications and verification requires less than two modular exponentiations. furthermore a construction is shown of an undeniable signature scheme, which is unconditionally secure for the signer, and which allows the signer to convert undeniable signatures into fail-stop signatures. this is the first published undeniable signature having this property.
efficient receipt-free voting based on homomorphic encryption. voting schemes that provide receipt-freeness prevent voters from proving their cast vote, and hence thwart vote-buying and coercion. we analyze the security of the multi-authority voting protocol of benaloh and tuinstra and demonstrate that this protocol is not receiptfree, opposed to what was claimed in the paper and was believed before. furthermore, we propose the first practicable receipt-free voting scheme. its only physical assumption is the existence of secret one-way communication channels from the authorities to the voters, and due to the public verifiability of the tally, voters only join a single stage of the protocol, realizing the "vote-and-go" concept. the protocol combines the advantages of the receipt-free protocol of sako and kilian and of the very efficient protocol of cramer, gennaro, and schoenmakers, with help of designated-verifier proofs of jakobsson, sako, and impagliazzo. compared to the receipt-free protocol of sako and kilian for security parameter l (the number of repetitions in the non-interactive cut-andchoose proofs), the protocol described in this paper realizes an improvement of the total bit complexity by a factor l.
new modular multiplication algorithms for fast modular exponentiation. a modular exponentiation is one of the most important operations in public-key cryptography. however, it takes much time because the modular exponentiation deals with very large operands as 512-bit integers. the modular exponentiation is composed of repetition of modular multiplications. therefore, we can rcducc the execution time of it by reducing thc execution time of each modular multiplication. in this paper, we propose two fast modular multiplication algorithms. one is for modular multiplications between different integers, and the other is for modular squarings. these proposed algorithms require single-precision multiplications fewer than those of montgomery modular multiplication algorithms by 1/2 and 1/3 times, respectively. implementing on pc, proposed algorithms reduce execution times by 50% and 30% compared with montgomery algorithms, respectively.