On not storing the path of a random walk

We describe a novel form of Monte Carlo method with which to study self-avoiding random walks; we do not (in any sense) store the path of the walk being considered. As we show, the problem is related to that of devising a random-number generator which can produce itsnth number on request, without running through its sequence up to this point.     

A new cryptosystem based on chaotic map and operations algebraic

Based on the study of some existing chaotic encryption algorithms, a new block cipher is proposed. The proposed cipher encrypts 128-bit plaintext to 128-bit ciphertext blocks, using a 128-bit key K and the initial value x₀ and the control parameter mu of logistic map. It consists of an initial permutation and eight computationally identical rounds followed by an output transformation. Round r uses a 128-bit roundkey K^(r) to transform a 128-bit input C^(r-1), which is fed to the next round. The output after round 8 enters the output transformation to produce the final ciphertext. All roundkeys are derived from K and a 128-bit random binary sequence generated from a chaotic map. Analysis shows that the proposed block cipher does not suffer from the flaws of pure chaotic cryptosystems and possesses high security.     

On ε‐biased generators in NC0

Cryan and Miltersen (Proceedings of the 26th Mathematical Foundations of Computer Science, 2001, pp. 272–284) recently considered the question of whether there can be a pseudorandom generator in NC⁰, that is, a pseudorandom generator that maps n‐bit strings to m‐bit strings such that every bit of the output depends on a constant number k of bits of the seed. They show that for k = 3, if m ≥ 4n + 1, there is a distinguisher; in fact, they show that in this case it is possible to break the generator with a linear test, that is, there is a subset of bits of the output whose XOR has a noticeable bias. They leave the question open for k ≥ 4. In fact, they ask whether every NC⁰ generator can be broken by a statistical test that simply XORs some bits of the input. Equivalently, is it the case that no NC⁰ generator can sample an ε‐biased space with negligible ε? We give a generator for k = 5 that maps n bits into cn bits, so that every bit of the output depends on 5 bits of the seed, and the XOR of every subset of the bits of the output has bias 2. For large values of k, we construct generators that map n bits to bits such that every XOR of outputs has bias . We also present a polynomial‐time distinguisher for k = 4,m ≥ 24n having constant distinguishing probability. For large values of k we show that a linear distinguisher with a constant distinguishing probability exists once m ≥ Ω(2^kn^?k/2?). Finally, we consider a variant of the problem where each of the output bits is a degree k polynomial in the inputs. We show there exists a degree k = 2 pseudorandom generator for which the XOR of every subset of the outputs has bias 2^?Ω(n) and which maps n bits to Ω(n²) bits. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Construction of universal one-way hash functions: Tree hashing revisited

We present a binary tree based parallel algorithm for extending the domain of a universal one-way hash function (UOWHF). For t?2, our algorithm extends the domain from the set of all n-bit strings to the set of all ((2^t-1)(n-m)+m)-bit strings, where m is the length of the message digest. The associated increase in key length is 2m bits for t=2; m(t+1) bits for 3?t?6 and m×(t+⌊log₂(t-1)⌋) bits for t?7.     

Inversive congruential generator over a Galois ring of dimension <Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">l</Emphasis></Superscript>

We consider the construction of of an inversive congruential generator over a Galois ring of odd dimension p ^l , whichwas proposed by Solé and Zinoviev for p = 2. Using the estimates of trigonometric sums on the sequences of pseudorandom numbers, we obtain the estimates of a discrepant function, a generated sequence of pseudorandom numbers, and the associated sequence of two-dimensional “overlapping” points.     

Improved distinguishers for HC-128

HC-128 is an eSTREAM final portfolio stream cipher. Several authors have investigated its security and, in particular, distinguishing attacks have been considered. Still, no one has been able to provide a distinguisher stronger than the one presented by Wu in the original HC-128 paper. In this paper we first argue that the keystream requirement in Wu’s original attack is underestimated by a factor of almost 2⁸. Our revised analysis shows that the keystream complexity of Wu’s original attack is 2^160.471 32-bit keystream blocks. We then go on to investigate two new types of distinguishers on HC-128. One of them, a distinguisher counting the number of zeros in created blocks of bits, gives a biased distribution that requires 2^143.537 such constructed block samples (2^152.537 32-bit keystream blocks). For fairness, the same metric is used to compare our attack to Wu’s, and our improvement is significant compared to Wu’s original result. Furthermore, the vector-based methodology used is general and can be applied to any cryptographic primitive that reveals a suitable probability distribution.     

Sharpening an upper bound on the adder and comparator depths

The upper bound log₂ n + log₂ log₂ n + const is proved on the depth of the addition and comparison operators on n-bit numbers over the basis {&;, ∨, ～}.     

Machine independent monte carlo evaluation of the performance of dynamic stochastic systems

The familiar subject of Monte Carlo analysis is reviewed, with special emphasis on repro-ducibility of results, regardless of the digital computer employed. A digital pseudo-random number generator is introduced and tested for desirable characteristics. The generator produces 36-bit random numbers and a method of segmenting the modular arithmetic is described which allows for the exact reproduction of the sequence of any binary machine, independent of the word length.     

Analysis and synthesis of Ultra-uniform Pseudorandom Number Generators

The Wichmann–Hill algorithm is a high-performance generatorof uniformly distributed pseudorandom numbers, designed foruse on, and portability between, 8-bit of 16-bit machines. Twoanalyses (one number-theoretic, the other probability-theoretic)are presented in order to explain its superb performance. Itis shown that the original Wichmann–Hill configurationcan be regarded as a single linear congruential generator withunrealizably large multiplier and modulus decomposed into threerealizable subgenerators. This provides an obvious insight intothe source of the generator's high quality, but more importantlypermits, for the first time, the application of the extremelystringent Coveyou-MacPherson spectral test—which is passedwith flying colours. The techniques used for analysis have also been applied to designand test a large family of three-component generalized Wichmann–Hill-typegenerators with substantially the same very high performanceas the original. Over one hundred such generators have beenfound. There is no difficulty in extending the design to configurationssuitable for 32-bit machines, with some improvement in the quality.Increasing the number of subgenerators produces a more dramaticenhancement: this is illustrated by means of an example employingfour components.     

Emission spectrum of bromine excited in the presence of argon—part I

Bromine was excited by an uncondensed transformer discharge in the presence of argon. The spectrum obtained was found to be different from what one gets without the presence of a foreign gas and consists of (1) a short discrete band system in the region 3150–2970 Å, (2) an extensive discrete band system in the region 2950–2670 Å, (3) a short and weak discrete system in the region 2660–2590 Å and a set of diffuse bands in the region 3340–3190 Å. The wavelengths and wave numbers of the band heads of the system 2950–2670 Å, as obtained from the measurements of the plates taken on the first order 21-ft. grating spectrograph, are given along with the vibrational analysis. This system is shown to be due to a transition from an upper electronic state at 51802 cm.^-1 with ω′_e = 150·5 cm.^-1 and ω′_e X′_e = 1·15 cm.^-1 to the well known³ II _α (O₂ ⁺) state at 15918 cm.^-1     

A multiple recursive non-linear congruential pseudo random number generator

On-linear multiple recursive congruential pseudo random number generator with prime modulus p is introduced. Let x, n0, be the sequence generated by a usual linear (r+1)-step recursive congruential generator with prime modulus p and denote by N(n), n0, the sequence of non-negative integers with x_N(n)0 (mod p). The non-linear generator is defined by z_nx_N(n)+1·x _N(n) ^–1 (mod p), n0, where x _N(n) ^–1 denotes the inverse element of x_N(n) in the Galois field GF(p). A condition is given which ensures that the generated sequence is purely periodic with period length p^r and all (p–1)^r r-tupels (y₁,...,y_r) with 1y₁,...,y_rp are generated once per period when r-tupels of consecutive numbers of the generated sequence are formed. For r=1 this generator coincides with the generator introduced by Eichenauer and Lehn [2].     

Better upper bounds on the QOBDD size of integer multiplication

We show that the middle bit of the multiplication of two n-bit integers can be computed by an ordered binary decision diagram (OBDD) of size less than 2.8·2^6n/5. This improves the previously known upper bound of by Woelfel (New Bounds on the OBDD-size of integer multiplication via Universal Hashing, J. Comput. System Sci. 71(4) (2005) 520-534). The experimental results suggest that our exponent of 6n/5 is optimal or at least very close to optimal. A general upper bound of O(2^3n/2) on the OBDD size of each output bit of the multiplication is also presented.     

Growth Estimates for exp(A<Superscript>-1</Superscript>t) on a Hilbert Space

Let A be the infinitesimal generator of an exponentially stable, strongly continuous semigroup on the Hilbert space H. Since A^-1 is a bounded operator, it is the infinitesimal generator of a strongly continuous semigroup. In this paper we show that the growth of this semigroup is bounded by a constant time log(t).     

Weak generators of the algebra of measures and unicellularity of convolution operators

A general scheme which enables us to consider convolution operators with measures acting in a wide class of spaces of distributions on the interval [0, a), 0<a<∞, is represented. It is proved that if a measure μ is a weak generator of the algebra of measures on [0, a), then C_μ (the convolution operator with μ) is unicellular. We give a condition for a measure μ under which the unicellularity of C_μ implies that μ is a weak generator of the algebra of measures. The following statement is also proved. Let , K_θ=H²⊖θH², and let P_θ be the orthogonal projector from H² onto K_θ; in addition, let μ be a weak generator of the algebra of measures on [0, a) and , z ∈ (here is the unit disk and F^-1 is the inverse Fourier transformation). Let ψ∈H^∞ and let p be a polynomial such that p o(ψ−φ)∈θH^∞. Then the operator x→P_θψx, acting in K_θ, is unicellular. Bibliography: 13 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 217, 1994, pp. 36–53.     

A construction of Gray codes inducing complete graphs

A binary Gray code G(n) of length n, is a list of all 2ⁿn-bit codewords such that successive codewords differ in only one bit position. The sequence of bit positions where the single change occurs when going to the next codeword in G(n), denoted by S(n)?s₁,s₂,…,s_2ⁿ-1, is called the transition sequence of the Gray code G(n). The graph G_G(n) induced by a Gray code G(n) has vertex set {1,2,…,n} and edge set {{s_i,s_i+1}:1?i?2ⁿ-2}. If the first and the last codeword differ only in position s_2ⁿ, the code is cyclic and we extend the graph by two more edges {s_2ⁿ-1,s_2ⁿ} and {s_2ⁿ,s₁}. We solve a problem of Wilmer and Ernst [Graphs induced by Gray codes, Discrete Math. 257 (2002) 585-598] about a construction of an n-bit Gray code inducing the complete graph K_n. The technique used to solve this problem is based on a Gray code construction due to Bakos [A. Ádám, Truth Functions and the Problem of their Realization by Two-Terminal Graphs, Akadémiai Kiadó, Budapest, 1968], and which is presented in D.E. Knuth [The Art of Computer Programming, vol. 4, Addison-Wesley as part of “fascicle” 2, USA, 2005].     

Optimal collision security in double block length hashing with single length key

The idea of double block length hashing is to construct a compression function on 2n bits using a block cipher with an n-bit block size. All optimally secure double block length hash functions known in the literature employ a cipher with a key space of double block size, 2n-bit. On the other hand, no optimally secure compression functions built from a cipher with an n-bit key space are known. Our work deals with this problem. Firstly, we prove that for a wide class of compression functions with two calls to its underlying n-bit keyed block cipher collisions can be found in about \(2^{n/2}\) queries. This attack applies, among others, to functions where the output is derived from the block cipher outputs in a linear way. This observation demonstrates that all security results of designs using a cipher with 2n-bit key space crucially rely on the presence of these extra n key bits. The main contribution of this work is a proof that this issue can be resolved by allowing the compression function to make one extra call to the cipher. We propose a family of compression functions making three block cipher calls that asymptotically achieves optimal collision resistance up to \(2^{n(1-\varepsilon )}\) queries and preimage resistance up to \(2^{3n(1-\varepsilon )/2}\) queries, for any \(\varepsilon >0\). To our knowledge, this is the first optimally collision secure double block length construction using a block cipher with single length key space. We additionally prove this class of functions indifferentiable from random functions in about \(2^{n/2}\) queries, and demonstrate that no other function in this direction achieves a bound of similar kind.     

On String Replacement Exponentiation

The string replacement (SR) method was recently proposed as a methodfor exponentiation a ^e in a group G. The canonicalk-SR method operates by replacing a run of i onesin a binary exponent,0k, with i-1 zeroes followedby the single digit b=2 ⁱ -1. After recoding, it was shown in[5] that the expected weight of e tends to n/4 forn-bit exponents. In this paper we show that the canonicalk-SR recoding process can be described as a regular language andthen use generating functions to derive the exact probability distribution ofrecoded exponent weights. We also show that the canonical 2-SR recodingproduces weight distributions very similar to (optimal) signed-digitrecodings, but no group inversions are required.     

Some observations on HC-128

In this paper, we study HC-128 in detail from cryptanalytic point of view. First, we use linear approximation of the addition modulo 2 ⁿ of three n-bit integers to identify linear approximations of g ₁, g ₂, the feedback functions of HC-128. This, in turn, shows that the process of keystream output generation of HC-128 can be well approximated by linear functions. In this direction, we show that the ??least significant bit?? based distinguisher (presented by the designer himself) of HC-128 works for the complete 32-bit word. Using the above linear approximations of g ₁, g ₂, we present a new distinguisher for HC-128 which is slightly weaker than Wu??s distinguisher. Finally, in the line of Dunkelman??s observation, we also study how HC-128 keystream words leak secret state information of the cipher due to the properties of the functions h ₁, h ₂ and present improved results.     

On exit time from balls of jump-type symmetric Markov processes

We obtain upper and lower bounds of the exit times from balls of a jump-type symmetric Markov process. The proofs are delivered separately. The upper bounds are obtained by using the Levy system corresponding to the process, while the precise expression of the （L^2-）generator of the Dirichlet form associated with the process is used to obtain the lower bounds.