# Beyond Statistical Analysis in Chaos-Based CSPRNG Design

Authors: John Prakash Arockiasamy; Lydia Elizabeth Benjamin; Rhymend Uthariaraj Vaidyanathan
Journal: Security and Communication Networks
 (2021)

---

## Abstract

The design of cryptographically secure pseudorandom number generator (CSPRNG) producing unpredictable pseudorandom sequences robustly and credibly has been a nontrivial task. Almost all the chaos-based CSPRNG design approaches invariably depend only on statistical analysis. Such schemes designed to be secure are being proven to be predictable and insecure day by day. This paper proposes a design and instantiation approach to chaos-based CSPRNG using proven generic constructions of modern cryptography. The proposed design approach with proper instantiation of such generic constructions eventually results in providing best of both worlds that is the provable security guarantees of modern cryptography and passing of necessary statistical tests as that of chaos-based schemes. Also, we introduce a new coupled map lattice based on logistic-sine map for the construction of CSPRNG. The proposed pseudorandom number generator is proven using rigorous security analysis as that of modern cryptography and tested using the standard statistical testing suites. It is observed that the generated sequences pass all stringent statistical tests such as NIST, Dieharder, ENT, and TestU01 randomness test suites.


---

## Body

## 1. Introduction

Cryptographically secure pseudorandom number generator (CSPRNG) efficiently generates sequences that cannot be distinguished from random sequences by (computationally) efficient adversaries. The number of hardware and software implementations of CSPRNG based on chaotic maps has increased recently along with chaos-based cryptosystems. Chaotic maps are mathematical functions that exhibit random or chaotic behaviour that is hard to predict. The idea is to use the behaviour of such chaotic maps to produce chaotic sequences that are disordered, unpredictable, and sensitive to the initial conditions. However, the designers of such chaos-based cryptosystems claim security by statistical analysis of the topological properties of disorder as defined by the mathematical theory of chaos. More often, there is no rigorous provable security methodology that bridges the gap between statistical analysis of chaotic maps topological properties and security guarantees unlike modern cryptography. As a result, the use of chaos-based cryptosystems is disputed, especially for cryptographic applications, and they are often shown to be flawed, with such failures often attributed to the use of nonrigorous empirical-only methodology in the design process [1]. Modern cryptography instead creates cryptographic primitives by instantiating tried and tested over time standard generic constructions (such as Goldreich–Levin construction, Feistel structure, SPN, counter mode, and sponge construction) with new computationally efficient mathematical functions. We know that such designs drawing strength and credibility from the foundational generic constructions have been resilient to attacks for over sufficient period of time. However, in chaos-based cryptosystems, more often bespoke generic constructions are designed with standard candidate (mathematical) chaotic functions leading to faulty designs. This is largely due to lack of rigorous analysis treatment to bespoke generic constructions used to design cryptographic primitives unlike new instantiations of time-tested generic construction approach of modern cryptography. Therefore, the need to bridge the gap between such chaos-based cryptosystem designs and modern cryptography to provide credible and robust cryptographic primitive designs is pertinent. This paper attempts to bridge this gap through demonstration of provably secure chaos-based CSPRNG design denoted G. We show in this paper that the sequences generated are computationally indistinguishable and hard to predict in the presence of efficient adversaries using modern cryptography design tools. Also, we show that such sequences pass all necessary statistical analysis tests that are required to a chaos-based cryptosystem design. Therefore, the design approach advocates to consider statistical analysis as a necessary condition and mathematical simulation-based proofs as sufficient condition for credible chaos-based cryptographic primitive designs. Provable CSPRNG constructions instantiated with chaotic maps that they will pass all efficient statistical tests are hardly proposed to the best of our knowledge.Generally, pseudorandom sequences generated from a potential CSPRNGG passes a subset of all statistical tests. The question of whether there exists a mechanism to determine the existence of a potential pseudorandom number generator G passes all efficient statistical tests is provided by the abstract notion of computationally indistinguishable (denoted ≈c) formalized in [2]. The abstract notion of computationally indistinguishable is proven in [2] to be equivalent to the abstract notion of unpredictability (denoted ≈p). The notion of computationally indistinguishable requires nonexistence of efficient (computationally bounded) distinguisher (D) which can distinguish samples taken from two different distributions. In the same way, the notion of unpredictability requires nonexistence of efficient (computationally bounded) predictor (P) which can predict the distribution from which a sample was taken given two sample distributions.Based on the notion of computationally indistinguishable, one-way functions (OWFs) [3, 4] or unpredictable functions (UFs) are designed based on assumptions that P≠NP and intractable problems. Furthermore, based on the assumption that OWFs or UFs exist, generic pseudorandom generator constructions are proposed [5–7]. The generic constructions provide a construction framework when instantiated with provable one-way functions or unpredictable functions can be composed to design pseudorandom number generator G [7]. These abstract notions provides provability that such instantiated constructions will pass all efficient statistical tests and provably unpredictable. The chaotic maps when operated in the region of chaos or sensitive dependence on initial conditions (SDIC) exhibit function solutions or trajectories which are unpredictable and uniformly distributed in the state space. The design of PRNGs using chaotic maps have provided many efficient candidates for G. Moreover, such G using chaotic maps are entropy sources and generate sequences which look random and provide guarantees for conducted experiments but no guarantees for passing of all efficient statistical tests.Yao [2] showed that the notion of unpredictability implies pseudorandomness. It was then shown that unpredictability (≈p) for bit sequences is equivalent to pseudorandomness with the notion of computationally indistinguishable (≈c). It is under the premise that existence of efficient predictor (P) to predict bit sequences from unpredictable functions can be used to construct efficient distinguisher (D) to look apart from uniformly random sequences U. Also, unpredictable functions imply one-way functions from which pseudorandom functions can be constructed. It is known that modern cryptography constructions from one-way functions to PRNGs are provably secure but take a toll on computational efficiency. This fact makes pseudorandom generators constructed from unpredictable functions to PRNGs using chaotic maps as unpredictable functions relatively efficient [8].This kind of modern cryptography design approach in chaos cryptography can lead to credible and robust designs. The proven modern cryptographic constructions such as Merkle–Damgard, sponge construction, and block cipher modes can be used by instantiating such proven constructions with suitable chaos-based functions. Such design approach will reduce the reliance of security assessment methods on statistical analysis. Moreover, statistical analysis is performed only on the produced output of cryptographic algorithms such as on ciphertexts obtained from an encryption mechanism, hash or message digest obtained from a hash algorithm, and pseudorandom bits obtained from a pseudorandom number generator. Also, statistical tests conducted only on the output of cryptographic algorithms generally do not capture the notion of attackers’ potential, attackers’ knowledge of the algorithm (Kerckhoffs’ principle), and attackers’ capabilities to interact or query the algorithm. Cryptographic algorithms are often vulnerable in real-world situations due to such attackers’ characteristics. Therefore, beyond statistical analysis, the design approach for chaos-based cryptographic design should be based more on instantiating proven constructions with chaotic maps as unpredictable functions rather designing new constructions on each proposed chaotic cryptographic algorithm.Considering all the above factors, we demonstrate a design approach by instantiating a proven modern cryptographic PRNG construction with a new chaotic map based on coupled map lattices, prove its security using modern cryptographic attack models, and perform statistical analysis on the output. The proposed design approach can also be used for designing other chaos-based cryptographic primitives with proper instantiation of the chaotic maps. The chaotic maps should satisfy the conditions or properties as required by the choice of construction and security model to prove the security. For example, the choice of construction in this work requires that the instantiated chaotic map to be a unpredictable function, and hence, a map known to be noninvertible is used in the composition. Similarly, other chaotic maps can be used in the proposed approach depending on the choice of construction. PRNGs are required to produce output sequence of bits which are distributed almost uniformly. However, for a CSPRNG, the output sequence is required to have negligible probability to be distinguished by an adversary not knowing the initial seed from random sequence besides passing all polynomial-time (in respect of size of the seed) restricted statistical tests. Such CSPRNG can be used in stream ciphers and block ciphers as a submodule as required by the design. The main contributions of this paper are as follows:(1)
We instantiate Goldreich–Levin generic construction with a new deterministic discrete coupled map lattice (δ)(2)
We prove through theoretical security analysis methodology using modern cryptography tools thatδ is an unpredictable function and subsequently, we prove the pseudorandomness of construction G^ as required by modern cryptography(3)
The sequences generated using the proposedG^ are tested using standard statistical test suites and show that the sequences indeed pass all statistical analysis tests as required by chaos cryptography


### 1.1. Organization

In Section2, we summarize the related works. The preliminaries and definitions are presented in Section 3. The construction and instantiation of the proposed CSPRNG G^ is presented in Section 4. The theoretical security analysis of the proposed construction using computational indistinguishability properties leading to security of the CSPRNG is presented in Section 5. The experimental tests for randomness using various statistical testing suites are given in Section 6. Section 7 discusses about various implementation issues. We conclude with final remarks in Section 8.


## 1.1. Organization

In Section2, we summarize the related works. The preliminaries and definitions are presented in Section 3. The construction and instantiation of the proposed CSPRNG G^ is presented in Section 4. The theoretical security analysis of the proposed construction using computational indistinguishability properties leading to security of the CSPRNG is presented in Section 5. The experimental tests for randomness using various statistical testing suites are given in Section 6. Section 7 discusses about various implementation issues. We conclude with final remarks in Section 8.


## 2. Related Works

Entropy of nondeterministic source is used as input to the true random number generator (TRNG) that induces complex and unpredictability properties. For instance, mouse movements or electrical signal noise and bioelectrical signals can be utilized for TRNG process [9–13]. On the other hand, PRNG computed by a deterministic algorithm makes use of a complex mathematical formula in order to remain deterministic and yet unpredictable [14].In recent years, chaos has been used extensively in computing cryptographically secure PRNGs as it is computationally infeasible to predict the preceding bits despite the visible part of the output dynamics. In spite of the hype surrounding the chaos-based PRNGs, there are many shortcomings of this technique which make them insecure to be used in cryptographic systems. The selection of the chaotic system is a indispensable problem in the generation of the pseudorandom bits. Various single-dimensional chaotic maps such as logistic map, multimodal maps, Tinkerbell map, quantum logistic map, and piecewise logistic map are used in the design of PRNGs [14–17]. García-Martínez and Campos-Cantón [14] employed a unidimensional multimodal discrete map in computing the pseudorandom bits. The positive and negative values of the multimodal map yield a complex sequence with long periods. Furthermore, the complex sequences are tested using the NIST statistical testing suite for its credibility. However, the statistical test showcased a number of weak keys causing improper functioning of the generator [18]. Wang et al. [19] present a PRNG based on a piecewise logistic map. Furthermore, the sequence generated from the map is transformed into PRNGs based on the S-box of AES. The author claims that the generated PRNGs have good statistical properties and no shorter periods. Inspite of the claims, the PRNG was found to be insecure where the auxiliary mechanism used in computing the control parameter of the system is exploited [20].Xu et al. [16] proposed an algorithm to produce binary sequence that has three layers. The top layer consists of linear feedback shift register (LFSR) of 16 cells, the bit-reorganization (BR) at the middle, and a nonlinear function F in the bottom. The two chaotic maps are used as a nonlinear element to avoid the finite precision problem. However, PRNG does not enhance its security since the attacker is able to reconstruct the secret key after six iterations [21]. Hu et al. [11] proposed PRNGs based on quantum logistic map, whose randomness was merely based on the chaotic equation involved. The PRNG is subjected to various statistical tests on randomness using testing suites such as ENT, NIST, Dieharder, and TestU01. Although the author claims sufficient randomness, the PRNG has serious security implications. Degradation of security has emerged due to the poor selection of control parameter and the resulting secret key that leads to nonchaotic behaviour of the quantum logistic map [22]. Sahari and Boukemara proposed a 3D chaotic map by coupling two maps of piecewise and logistic maps in order to overcome the weaknesses of one-dimensional map. The PRNG has cryptographic statistical properties such as the simplicity, ergodicity, and higher sensitivity. Additionally, as generation process involves only multiplications and additions, realization by both hardware and software was made easy [23]. Fractional-order chaotic systems such as [24] are dynamical systems which rely on functional calculus and modelled as fractional differential equations. They have the potential to exhibit chaos with low order as low as 0.3. Montero-Canela et al. [25] proposed a PRNG as part of their cryptosystem design using fractional-order chaotic system specifically designed for Internet of Things. Though the work proves the properties of dynamics supported with standard statistical analysis, formal security proof capturing the attacker and attacks is not provided.Another issue which is profoundly identified in the chaotic PRNG is the implementation of generators with finite precision [21, 26–29]. A number of studies have been conducted to solve the problem of dynamical degradation of the chaotic system caused by the data sequence with shorter period. Thus, the security of the cryptographic applications may become completely insecure. Flores-Vergara et al. [30] proposed a novel chaotic PRNG as an alternative to diminish the dynamical degradation of the chaotic dynamics. This method generates pseudorandom numbers with the double precision specified by the IEEE 754 standard for floating-point arithmetic. Nevertheless, the computational speed of the system is significantly influenced. François et al. [31] proposed a solution with the use of more than one chaotic map in cascade. The PRNG consists of mixing three chaotic maps generated from an input initial vector; however, it increases the overhead cost. Perturbation using a nonlinear element was one of the prospective ideas deployed to weed out the influence of shorter period. Dastgheib and Farhang [32] developed a multiple recursive generator based on a digitized sawtooth map. It is demonstrated that this map in a recursive structure and a tiny perturbation can potentially cause unpredictable longer periods in a finite precision. However, the aforementioned solutions such as combining multiple chaotic maps, holding higher precision, and perturbation methods can improve the average length of the period and short trajectories cannot be avoided indefinitely. It can be inferred from the above discussion that unlike cryptographic system, the chaos-based PRNGs lack instantiations based on mathematically proven constructions guarantee satisfiability of all required cryptographic statistical properties. However, chaos provides many potential functions for proven generic construction instantiations, but only the process of exploiting the right function with right properties has been nontrivial.


## 3. Preliminaries and Notations

The choice of the dynamical system in this paper is limited to discrete dynamical functions as in [33]. A parametric discrete time dynamical system is a tuple denoted by D=X,P,δ where X⊆ℝn is the state space, P⊆ℝm is the parameter space, and δ:X×P⟶X is a function. The orbit or trajectory formed by such a discrete dynamical functions is denoted by O. For δ:X⟶X a map, a forward orbit is defined by the set Ox+=y∈X|y=δnx,n∈ℕ. If δ is invertible, then a backward orbit is defined by the set Ox−=y∈X|y=δ−nx,n∈ℕ. A full orbit is defined by Ox=y∈X|y=δnx,n∈ℕ. For t≥0, the time −t map of a continuous dynamical system is the transformation of state space which takes x0,x1⟵δx0,x2⟵δ2x1,…,xn⟵δtxn−1. The study of qualitative behaviour of the dynamical system is thus the analysis of the orbits formed by δ. The orbits could be periodic, eventually periodic, asymptotic, and more. To get rich complex behaviour, functions such as δ are formed as an array of cells called coupled map lattices (CMLs) similar to cellular automata arrays. The cells or array elements are called lattices. The CML exhibits spatiotemporal dynamics in discrete time in which each lattice executes a δ and x⟵δx is coupled to its nearest lattice neighbours or coupled dynamically based on a configuration, denoted in the form δn+1,i=xn+1i=1−ϵδxi+ϵ/2δxni−1+δxni+1.In such a CML, the lattices are ordered on anl×n grid and each lattice can be considered as a function δ:X×X⟶X. A configuration of the CML denoted as D consists of real assignments to each of its lattices, ϵ and parameters for δ if any. A coupled map lattice (CML) as in [34–37] is denoted by a pair X,δ, where X is a continuous set of states, and δ:X×X⟶X is a transition function. A configuration of a CML, at time t∈ℤ,Dt:ℤ⟶X, is an assignment of a unique state to each lattice, where a lattice is represented by an integer. Di,t is the state of lattice i at time t is defined by Dt=t∈ℤ,x∈X,p∈P,δ, and a configuration at time t uniquely determines a configuration at time t+1 as Dt+1=i,q:q=δDi−1,t,Di,t,Di+1,t,i∈Z represented succinctly as Dt+1=δDt while D0 denotes an initial configuration. The dynamical system D with an initial configuration D0 computes to reach a destination configuration Dt, creating an orbit of points given by x0,x1⟵δx0,x2⟵δ2x1,…,xn⟵δtxt−1, and this notion of computability is formalized using [37] as follows.Definition 1.
Computable: a computation of a CML of lengthn is a sequence of configurations D0,D1,…,Dn−1. If Di and Dj, i≤j are two configurations in a computation, then Di⊢∗Dj or Dj=δtDi represents to say that Di computes Dj. Also, we say that Di⊢tDj when a configuration Di computes Dj in t time steps. The probability that it is computable is then PrDj⟵δtDi=1.
We often for brevity denotext⊢pxt+p, if Dt⊢pDt+p by xa⊢txb in the context when configuration can be inferred and computable. In a complex dynamical system, the problem of determining the preimage is formalized [37] as follows.Definition 2.
Preimage problem: given a fixed dynamical systemD and a configuration substring x determine whether there is a configuration substring x0 such that x0⊢kx where k is the time steps and x0⟵x0:D,k,x,x0⊢kx.
A deterministic dynamical system does not always exhibit deterministic behaviour but rather exhibit chaotic or unpredictable behaviour or sensitive dependence to certain initial conditions or parameters. From [33], a deterministic dynamical system is said to be chaotic if δ has sensitive dependence on initial conditions, δ is topologically transitive, and periodic points are dense. From the multitude of definitions, Devaney [33] formalizes chaos using theory of topology and the qualitative behaviour of orbits in region of chaos for a D given that conditions for chaos exists, such as x0⊢kxt is unpredictable. This implication of chaos is formalized by the notion of approximately probabilistically irrelevant using measure theory defined in [38] is given below.Definition 3.
Approx. probabilistically irrelevant:Xtn is approximately probabilistically irrelevant for predicting Ytm, tm≥tn at level ε>0 iff PrYtm|Xtn−PrYtm<ε.
The intuition behind the above definition under the assumption thatD is operating in its region of chaos, given x0 predicting xt is negligible. The condition for predictability can be defined in terms of Lyapunov stability. A discrete deterministic dynamical system is said to be Lyapunov stable if two different orbits whose initial conditions are sufficiently small and progress in time arbitrarily close to each other towards infinity. The system as in [39] is given by(1)∀εt>0,∃ε0,∀x,x′∈X,∀t≥t0:x0−x0′<ε0⟶xt−xt′<εt,where ε0 is the lower bound on the level of measurement accuracy error of initial conditions and εt is the practical lower bound on the tolerable error in the measurement accuracy of the predicted destination state. Given the preliminaries, the next section describes the constructions of a pseudorandom number generator applying these results or notions of dynamical systems and chaos.


## 4. Construction and Instantiation

A general approach towards construction of efficient encryption mechanism is used to generate a short random keyk and then expand k using a pseudorandom generator Gk, into a longer sequence g that looks random, and use g as the key in one-time pad encryption as c=x⊕k since key generated from a truly random source such that x=k is not practical. The existence of such PRNGs g⟵Gk is a contradiction to Shannon’s theorem [40] assuming a computationally unbounded malicious adversary. However, the probability of a computationally unbounded adversary is almost negligible. Therefore, without contradicting Shannon’s theorem, it is surmised that the adversary is computationally bounded or efficient and also it is conjectured that Gk exists if P≠NP [2]. Assuming P≠NP, the class of hard problems is used in cryptographic applications such as PRNG for generating sufficiently random looking sequences for cryptographic applications.LetG^ be a pseudorandom generator as formalized in [41] that generates pseudorandom sequences which are sufficiently random. Let δ be a unpredictable function and let hc be a hard-core predicate of δ defined as hcx,r:=⊕i=1nxi.ri, where x=x1…xn and r=r1…rn. Then, Gs:=δs‖hcs is a pseudorandom generator with expansion factor ln=n+1. The construction of G^ involves parameter generation and construction which uses a coupled map lattice.


### 4.1. Parameter Generation

The deterministic discrete dynamical systemD=X,P,δ is chosen as follows:(1)
Let the state space beX⟵x:x∈ℝ,x∈0,1.(2)
The functionδ is the proposed one-dimensional coupled map lattice (CML) based on logistic-sine map given by(2)δ1n+1x=αxn1−xn+4−αsinπxn4mod1,δ2n+1x=δ1n+1x,(3)δn+1=δ1xnj+ε2δ2xnj+1+δ2xnj−1−2δ2xnj,whereα∈ℝ is control parameter, x0j is the initial state for lattice j∈ℤ, and ϵ is coupling coefficient. The choice of CML being composed of logistic-sine map lattices is to have a well-known noninvertible map which can be scaled and be able to scale the number of pseudorandom bits.(3)
Lethc denote a hard-core predicate of δj of the jth lattice given by(4)hcxj=⊕i=1nxij.ri,wherex=x1…xn,r=r1…rn,j=1…m and m being the number of lattices in the δ3.(4)
Ifδ is an unpredictable function and hc a hard-core predicate of δ, then a pseudorandom number generator can be constructed for each lattice. We prove in Section 5 that δ is indeed unpredictable.(5)
The choice ofp∈P is given by p=x0,k,α,r which are chosen such that(5)∀t≥tp∀x,x′∈X:x0−x0′<ε0∧xt−xt′≥εt.The values ofp are chosen to be α∈0,4 and ϵ=0.1 based on observation from the experimental results which is shown in Figure 1. The bifurcation diagram, KS entropy diagram, and scatter plot depicted in Figure 1 show chaos and uniform distribution of function values for δ map defined in equation (3). The Lyapunov exponent is often used to quantify the amount of separation of nearby orbits. A positive Lyapunov value indicates that the system is chaotic. A KS entropy density normalizes the amount of chaos in a coupled map lattice where the combined measure of chaos across all lattices is required for assessing the overall chaos. A positive KS entropy value is indicative of δ being unpredictable and in chaos state as a whole or almost all lattices exhibiting a positive Lyapunov value. The higher percentage of lattices exhibiting chaotic behaviour and less periodic windows in bifurcation diagram make it suitable for cryptography. The KS entropy (h) and universality (hu) were determined as in [42] by varying α between 0,4 for 25 lattices and 1000 iterations as shown in Figure 1.Figure 1
δ characteristics. (a) δkx0bifurication diagram. (b) δkxKS entropy. (c) δkx0distribution.
(a)(b)(c)


### 4.2.G^ Construction

We construct pseudorandom generatorG^ with expansion factor l+pl, for some polynomial p. On input p from parameter generation described in Section 4.1, the G^ does the following:(1)
Setδ1n+1x=αxn1−xn+4−αsinπxn/4mod1(2)
Setδ2n+1x=δ1n+1x(3)
Setδn+1=δ1xnj+ε/2δ2xnj+1+δ2xnj−1−2δ2xnj(4)
Sethcxj=⊕i=1nxij.rij(5)
Fori=1,…,k do(a)
∀j,1≤j≤m,x0j=δx0j(6)
SetGxj:=δxj‖hcxj(7)
Setsj:=Gx0j(8)
Sett0j:=s. For i=1,…,pl do(a)
Forj=1,…,m do(i)
Letsi−1j be the first n bits of ti−1j, and let σi−1j denote the remaining i−1 (when i=1,s0j=t0j and σ0j is empty string)(ii)
Settij:=Gsi−1j‖σi−1j(9)
OutputtplFigure2 shows the working of the construction G^ with m lattices and will output m bits. The claim that G^ construction is a cryptographically secure PRNG is proven in Section 5.Figure 2
ConstructionG^ for n>1.


## 4.1. Parameter Generation

The deterministic discrete dynamical systemD=X,P,δ is chosen as follows:(1)
Let the state space beX⟵x:x∈ℝ,x∈0,1.(2)
The functionδ is the proposed one-dimensional coupled map lattice (CML) based on logistic-sine map given by(2)δ1n+1x=αxn1−xn+4−αsinπxn4mod1,δ2n+1x=δ1n+1x,(3)δn+1=δ1xnj+ε2δ2xnj+1+δ2xnj−1−2δ2xnj,whereα∈ℝ is control parameter, x0j is the initial state for lattice j∈ℤ, and ϵ is coupling coefficient. The choice of CML being composed of logistic-sine map lattices is to have a well-known noninvertible map which can be scaled and be able to scale the number of pseudorandom bits.(3)
Lethc denote a hard-core predicate of δj of the jth lattice given by(4)hcxj=⊕i=1nxij.ri,wherex=x1…xn,r=r1…rn,j=1…m and m being the number of lattices in the δ3.(4)
Ifδ is an unpredictable function and hc a hard-core predicate of δ, then a pseudorandom number generator can be constructed for each lattice. We prove in Section 5 that δ is indeed unpredictable.(5)
The choice ofp∈P is given by p=x0,k,α,r which are chosen such that(5)∀t≥tp∀x,x′∈X:x0−x0′<ε0∧xt−xt′≥εt.The values ofp are chosen to be α∈0,4 and ϵ=0.1 based on observation from the experimental results which is shown in Figure 1. The bifurcation diagram, KS entropy diagram, and scatter plot depicted in Figure 1 show chaos and uniform distribution of function values for δ map defined in equation (3). The Lyapunov exponent is often used to quantify the amount of separation of nearby orbits. A positive Lyapunov value indicates that the system is chaotic. A KS entropy density normalizes the amount of chaos in a coupled map lattice where the combined measure of chaos across all lattices is required for assessing the overall chaos. A positive KS entropy value is indicative of δ being unpredictable and in chaos state as a whole or almost all lattices exhibiting a positive Lyapunov value. The higher percentage of lattices exhibiting chaotic behaviour and less periodic windows in bifurcation diagram make it suitable for cryptography. The KS entropy (h) and universality (hu) were determined as in [42] by varying α between 0,4 for 25 lattices and 1000 iterations as shown in Figure 1.Figure 1
δ characteristics. (a) δkx0bifurication diagram. (b) δkxKS entropy. (c) δkx0distribution.
(a)(b)(c)


## 4.2.G^ Construction

We construct pseudorandom generatorG^ with expansion factor l+pl, for some polynomial p. On input p from parameter generation described in Section 4.1, the G^ does the following:(1)
Setδ1n+1x=αxn1−xn+4−αsinπxn/4mod1(2)
Setδ2n+1x=δ1n+1x(3)
Setδn+1=δ1xnj+ε/2δ2xnj+1+δ2xnj−1−2δ2xnj(4)
Sethcxj=⊕i=1nxij.rij(5)
Fori=1,…,k do(a)
∀j,1≤j≤m,x0j=δx0j(6)
SetGxj:=δxj‖hcxj(7)
Setsj:=Gx0j(8)
Sett0j:=s. For i=1,…,pl do(a)
Forj=1,…,m do(i)
Letsi−1j be the first n bits of ti−1j, and let σi−1j denote the remaining i−1 (when i=1,s0j=t0j and σ0j is empty string)(ii)
Settij:=Gsi−1j‖σi−1j(9)
OutputtplFigure2 shows the working of the construction G^ with m lattices and will output m bits. The claim that G^ construction is a cryptographically secure PRNG is proven in Section 5.Figure 2
ConstructionG^ for n>1.


## 5. Theoretical Security Analysis

The constructionG^ is based on the abstract notions of unpredictability. We analyse the security of the construction through a series of theorem using modern cryptography. First, we prove δ’s unpredictability and then its one-way function property. We then show that the construction G^ instantiated with δ is next-bit unpredictable secure PRNG with polynomial expansion factor. We also show that construction G^ is secure against adversaries given adaptive queries. These proof techniques are a design strategy which eventually helps in identification and removal of design weaknesses if not completely but to a large extend.Theorem 1.
Unpredictable function: the functionδ:X×X⟶X is an unpredictable function in the chaotic intervalProof.
The theorem is proven through two claims, namely, the unpredictability of theδ and hardness of preimage problem using the inherent properties of δ and choice of parameters made in the construction. Though the dynamic system is deterministic, it exhibits chaotic behaviour which makes predictions hard when they operate in their region of chaos. Given a deterministic dynamic system with an initial configuration D=δ,α,x0,k,l where x0 is the initial state, δ is the function, k is the number of iterations, and l is the number of bits used for representation, two things are necessary for making predictions:(1)
D0 should be known and particularly x0, and the initial state should be measured with reasonable accuracy such that the errors in the prediction are small say ε(2)
Given the initial statex0 and k time steps, compute x0⊢kxt in polynomial time
Measuring the initial statex0 with the required accuracy to keep the prediction errors small and within ε is difficult even if we consider that the initial configuration D0 is known [39]. Therefore, meeting the two necessary conditions is nontrivial to make predictions in D. Let us assume that the computations are carried out in discrete time and continuous state space which are efficiently made discrete with finite precision arithmetic.Claim 1.
If a systemD=δ,α,x0,k,l with parameters x0∈0,1,α∈a,b as initial conditions chosen uniformly random such that(6)∀t≥tp∀x,x′∈X:x0−x0′<ε0∧xt−xt′≥εt,then the system is pragmatically unpredictable where a,b is the chaotic interval and the following holds:(7)Prxt′:D\α,x0,k,xt−xt′≤εt,x0−x0′<ε0,xt′⟵δkx0′≤negll.Proof.
Consider the deterministic dynamical systemD=δ,α,x0,k, and it is said to be strongly pragmatically predictable if and only if the following holds [39]:(8)∀t≥tp∀x,x′∈X:xt−xt′≥εt⟶x0−x0′≥ε0,where tp represents interested prediction time x,x′ denotes state space, ε0 denotes the smallest measurement accuracy of initial conditions, and εt represents practically tolerable prediction error. The above equation intuitively gives the implication that the inability to predict xt with reasonable accuracy level below εt at all times implies system’s initial conditions could not be measured with accuracy less than ε0. In other words, if the system’s initial conditions cannot be measured with at least the measurement accuracy ε0, the system is not strongly pragmatically predictable. Hence, strong pragmatic predictability condition cannot hold if the initial conditions are kept secret as in construction G^, and therefore, x0−x0′≫ε0. Also, if the systems are carefully chosen such that the system is in chaotic regime, as described in Section 4 (parameter generation Section 4.1), it makes predictability hard even when the measurement of initial conditions is within ε0. If the system satisfies equation (6), then the equation for strong predictability cannot hold. The condition for weak pragmatic predictability is given by(9)∃t≥tp∀x,x′∈X:xt−xt′≥εt⟶x0−x0′≥ε0.
The above condition for weak pragmatic predictability can neither hold for the systemD if x0−x0′≫ε0 holds. The intuitive meaning of the above equation is that for all times and states in the chaotic region, if the initial state prediction error is less than ε0 and final state prediction error is more than εt, then the system is unpredictable. This also means sensitive dependence to initial conditions or chaos. Moreover, it is known that boundedness of the trajectories produces nonlinearity, being nonperiodic, simulates statistical random experiment, and fills the entire state space [39]. The system D when bounded in the interval 0,1 by parameter generation will exhibit the following characteristics consequently:(1)
Nonlinearity due to addition of nonlinear term sine to the linear differential equation(2)
Trajectory divergence or positive Lyapunov implies that the time-independent orbits will oscillate without being periodic in a finite region of the state space periodic making it unpredictable as observed from Figure1(3)
Orbits will contain all possible state values and thus simulate a statistical random experiment(4)
Set of orbits starting from one finite state space will fill the entire state space as observed from Figure1 after some time
Hence, the systemD is unpredictable if equation (6) holds. Moreover, equation (6) holds by assumption and given D\x0,k,α, that is, all the dynamical system parameters except for x0,k,α, an approximation x0′ such that x0−x0′≫ε0 also holds, and then it implies that it is hard to compute x0′⊢kxt′ such that xt−xt′≤εt. Any adversary trying to predict xt′ with practically relevant accuracy εt has to exhaustively search all possible values of initial conditions over X, and then the probability of determining xt′ from x0′ assuming x0 is chosen uniformly random which is given by(10)Prxt′:D,xt−xt′≤εt,x0−x0′<ε0,xt′⟵δkx0′,x0′≤εtX≤εt2l.
The second inequality follows from the fact that the state space is represented in finite arithmetic withl bits. The quantity εtX−1=εt2−l≤negll is negligible, and the above equation can be rewritten as(11)Prxt′:D,xt−xt′≤εt,x0−x0′<ε0,xt′⟵δkx0′,x0′≤negll.
Considering thatsk=p=α,k,x0 being kept secret by design and inference from the above equation that the probability of computing x0⊢kxt such that xt−xt′≥εt given that x0−x0′<ε0 is negligible, the above equation can thus be written as(12)Prxt′:D\α,x0,k,xt−xt′≤εt,x0−x0′<ε0,xt′⟵δkx0′≤negll.
Hence, Claim1 is proven.Claim 2.
LetD be such that Prxt′:D\α,x0,k,xt−xt′≤εt,x0−x0′<ε0,xt′⟵δkx0′≤negll, then it holds that(13)PrOx0′:D\α,x0,k,Ox0+−Ox0′+≤εt,Oxt−−Oxt′−≤ε0≤negll.Proof.
It is given that for the systemD, the following holds:(14)Prxt′:D\α,x0,k,xt−xt′≤εt,x0−x0′<ε0,xt′⟵δkx0′≤negll,and then for all the points in the forward predicted orbit Ox0′+ for x0′ implies that given a x0′ such that x0−x0′<ε0, predicting the points in the forward orbit Ox0′+=xi′:xi′,xi∈δ1kx0,xi−xi′≤εt is negligible, and then it can be written without loss of generality:(15)PrOx0′+:D\α,x0,k,Ox0+−Ox0′+≤εt,x0′≤negll.
Given thatδ is a noninvertible map and probability of computing Ox0′+ is negligible, it implies that given a destination point in an orbit xt and predicting all the points backward towards the initial point x0 in the backward orbit Oxt−=xi′:xi′,xi∈δ1kx0,xi−xi′≤εt,x0−x0′≥ε0,x0′ is also negligible, gives(16)PrOxt′−:D\α,x0,k,Oxt−−Oxt′−≤ε0,xt≤negll.
Combining forward and backward orbit computability probability from equations (15) and (16), we get(17)PrOx0′:D\α,x0,k,Ox0+−Ox0′+≤εt,Oxt−−Oxt′−≤ε0≤negll.
Hence, Claim2 is proven.
It follows from Claims1 and 2 that the function δ is unpredictable.Corollary 1.
Preimageδk problem: let D be a system such that PrOxt′−:D\α,x0,k,Oxt−−Oxt′−≤ε0,xt≤negll, then the following holds in the chaotic interval:(18)Prx0′:D\α,x0,k,x0−xo′≥ε0,xt⟵δkx0,x0′,xt′≤negll.Theorem 2.
Ifδ∈D is unpredictable, then it is a one-way function in the chaotic intervalProof.
A function is one-way if the following two conditions hold [41]:(1)
There exists a polynomial-time algorithmMδ computing δ, that is, Mδ=δkx0,l for all x0∈0,1 and k,l∈polyn(2)
For every probabilistic polynomial-time algorithmA, there is a negligible function negl such that(19)PrInvertA,δxt=1≤negll.
The above equation can be also represented succinctly as(20)Prx0∈R0,1A1n,δkx0=δ−kxt≤negll.
The proof of the theorem is structured by means of proving each condition for one-way function described above holds forδ through claims as given below.Claim 3.
GivenD0 and α,k,x0 with finite precision, the function δ computes x0⊢kxt deterministically in polynomial timeProof.
It is assumed that givenD0 is of finite precision and x0∈0,1. The δk function computes x0⊢kxt at each lattice given by(21)δkx0=δkx0mod1=δk−1δk−2…δ1x0mod1=δk−1xk−2mod1∘…∘δ1x0mod1=xt∈0,1.
We can see the abovementioned way of computing recursively and using modular arithmetic which keeps the complexity of finite arithmetic computing deterministic within polynomial time as long ask is polynomial.Claim 4.
GivenD\α,x0,k, for every probabilistic-time algorithm A, there is a negligible function negl such that PrInvertA,δxt≤negllProof.
We construct the experimentInvertA,δ as follows.Construction 1.
(δ−InvertA,δ)(1)
Choose uniformx0∈0,1, and compute xt=δkx0(2)
A is given 1n and y=xt as input, and outputs x0′(3)
The output of the experiment is defined to be 1 ifδx0′=y, and 0 otherwise
A closer observation of the definition of the experiment will reveal the fact that the experiment Invert is just a conceptual redefinition of the preimage problem defined in Section3 and Definition 2. Rewriting the equation PrInvertA,δxt in terms of the preimage problem, we get(22)PrInvertA,δxt=Prx0∈R0,1A1n,δkx0=δ−kxt=PrOxt′−:D\α,x0,k,Oxt−−Oxt′−≤ε0,xt=Prx0′:D\α,x0,k,x0−xo′≥ε0,xt⟵δkx0′,xt≤negll.
The second and third equality follows from equation (16) and Corollary 1. The fourth inequality proves Claim 4.
Now, from Claims3 and 4, it follows that δ is one way.
From Theorems1, 2, and [41], the corollaries are as follows.Corollary 2.
Ifδ is a one-way function in the chaotic interval and Gx,r=δx,r, then the function hcx,r=⊕i=1nxi.ri where x=x1,…,xn and r=r1,…,rn is a hard-core predicate of G.Corollary 3.
Ifδ is an OWP in the chaotic interval, hc is hard-core bit of δ and G is defined by Gx=δnx∘G′x=δnx∘hδn−1x∘…∘hx, then G is next-bit unpredictable.Corollary 4.
IfG^ is a pseudorandom generator with expansion factor n+1, then for any polynomial denoted poly., then there exists a pseudorandom generator G^ with expansion factor polyn.Theorem 3.
Let predictor be a construction as given below forΔ=δnn∈ℕ, an efficient ℝ⟶ℝ function ensemble, and let c∈ℕ be some constant as follows.Construction 2.
(δ−PredictorA,δ,Ix):(1)
Assume two parties, the predictorT and verifier V(2)
LetD0 denote the private initial configuration generated during parameter generation(3)
Letx0 be the initial state space and iterated k such that xt=δkx0 or x0⊢kxt(4)
The protocol runs inq−1 rounds for q=nc. T sends to V a point xi∈X and in return V sends to T at the ith round of the protocol value yi computed as follows:(a)
xi′=x0+ximod1 where xi takes values in the interval 0,1(b)
yi=δxi′(5)
T outputs a point xq which is not previously queried in x1x2…xq−1 and a string yq which is its guess for δk+qxq at the termination of the protocol
Δ is unpredictable against an adaptive sample and an adaptive challenge if for any polynomial-time machine T and any constant c∈ℕ, then(23)Pryq=δk+qxq|y1…q−1≤negll.Proof.
The initial configuration parameters are generated using parameter generation described in Section4.1 such that for D, the following condition for chaos or unpredictability holds:(24)∀t≥tp∀x,x′∈X:x0−x0′<ε0∧xt−xt′≥εt.
From [38], we know that predicting any point in a orbit at any level of precision ε>0, all sufficiently past points are approximately probabilistically irrelevant. Hence, if the condition for chaos holds, then by Definition 2, we have for tm≤tnat levelϵ>0 where ϵ is a negligible quantity, without loss of generality ϵ can be assumed to be equal to a small quantity negll:(25)PBtm|Atn−PBtm<negll.
Rewriting the above equation, we get(26)Pryq=δαkxq|y1…q−1−Pryq=δαkxq<negll.
Theϵ is negligible function of level of precision by definition and its equivalent to negll. Hence, it can be inferred that the probability conditioned on past observations has negligible effect under unpredictability assumption, and then it can be written as(27)Pryq=δ1kxq|y1…q−1<Pryq=δ1kxq+negll<Prx0′:D\α,x0,k,x0−x0′≥ε0,xq⟵δ1k+qx0′,xq+negll<negll+negll≤negll.
The first inequality is obtained by rewriting equation (26). The second inequality follows from Theorem 2 and its corollary. The third and fourth inequality follows that the predictor’s advantage is negligible. Hence, the adversary or the predictor T has negligible advantage in predicting given adaptive sample query access.Corollary 5.
Letδ be such that PrPredictor=1≤neglk, then from [43], it holds that(28)Prb=gi:x∈R0,1,g=g1…gpk=Gx,b⟵Tg1…gi−1<12+negll.Corollary 6.
FromCorollaries 2–5, it follows that G^ is a secure next-bit unpredictable PRNG with expansion factor polyn.


## 6. Empirical and Statistical Analysis

The central requirement for any PRNG to be practical is pseudorandomness and unpredictability (both forward and backward). A well-designed generator produces sequences that exhibit good statistical properties and are evenly distributed. To test the statistical strength of the designed PRNG, the sequence generated is subjected to rigorous statistical tests against the null hypothesis. The null hypothesis is that the sequence under test is random, and alternate hypothesis that the sequence is nonrandom. The statistical test suite describes the probability of the tested potential pseudorandom sequence, called test sequence, against a priori known truly random source or reference distribution. The intuition is that when the computed statistical value does not exceed the critical value, it means that a low probability event does not occur naturally, and hence, it must be random.There are an infinite number of statistical tests describing a methodology to test the existence of a prescribed pattern to prove that the tested sequence is nonrandom. The presence of an infinite number of statistical tests leads to no finite set of tests to quantify randomness. Therefore, the statistical tests are only a necessary condition and not a sufficient condition, but they are truly an indicator of randomness using probability. In this section, we analyze the statistical strength of the binary sequence generated by generatorsG^ using statistical randomness testing suites, namely, NIST 800-22 randomness test suite [44], Dieharder battery of test [45], ENT [46], and TestU01 [47, 48]. The pseudorandom binary bits are generated using G^ and instantiated with δ with m=100, and pl=106 is used for both proposed generators. All other parameters are chosen as described in Section 4.1.


### 6.1. NIST Test Results

NIST SP800-22 statistical test suite consists of 15 independent statistical tests to investigate the randomness of the arbitrary long binary sequence produced by the generators. For each test, with a fixed significant level (α=0.01), the quality of the sequence is given as p values. If the p value is >0.01, the generated sequence passes the test; otherwise, it fails. The sample size of 100 binary sequences for each test is used with the bit length of the order 106. The interpretation of the empirical results can be done from the proportion of passing of a test, i.e., the pass rate. The minimum pass rate is calculated from the sample size and the significant level as given in [44]. The minimum pass rate for 100 binary sequences with 0.01 significance level is 0.9602. The test is statistically successful if at least 96 sequences out of 100 sequences pass the test and the generator G^ successfully passed all the 15 tests as seen in Table 1 confirming the randomness of the generated sequence.Table 1
NIST test results.
Test name (test no.)G^p valuep-rate≥0.010.9602Frequency (1)0.9780720.9900BlockFrequency (2)0.7597561.0000CumulativeSums-forward (3)0.2492840.9800CumulativeSums-backward (4)0.8513830.9800Runs (5)0.5749030.9900LongestRun (6)0.8165370.9800Rank (7)0.6163051.0000FFT (8)0.3345380.9900NonOverlappingTemplate∗ (9–156)0.4970080.9900OverlappingTemplate (157)0.9780721.0000Universal (158)0.7791880.9900ApproximateEntropy (159)0.5341460.9900RandomExcursions∗ (160–167)0.4735460.9848RandomExcursionsVariant∗ (168–185)0.3273610.9848Serial 1 (186)0.7399180.9800Serial 2 (187)0.9114131.0000LinearComplexity (188)0.4749861.0000Success—15/15∗Mean value.


### 6.2. Dieharder Test Results

The Dieharder test suite developed by Robert G. Brown consists of 31 stringent tests for distinguishability from random. Thep value distribution generated by each test for Dieharder in contrast to NIST test suite is analyzed by a Kuiper–Kolmogorov–Smirnov (KKS) test, which has a higher sensitivity to deviations from an equal distribution. A random sequence with size 106 bit sequence from generators G^ is used as input for the Dieharder test suite. Table 2 shows the result of the Dieharder battery of tests. The number of trials used in each test is given as tsample. The generators passed all the 31 stringent tests, which indicate that there is evidence of randomness at a high confidence level.Table 2
Dieharder test results.
Test name (test no)G^T samplep valueDiehard Birthday (0)1000.623511Diehard OPERMS (1)10000000.892017Diehard 32 × 32 Binary (2)400000.563151Diehard 6 × 8 Binary Rank (3)1000000.925417Diehard Bitstream (4)20971520.851563Diehard OPSO (5)20971520.867954Diehard OQSO (6)20971520.415923Diehard DNA (7)20971520.442299Diehard Count the 1 s (stream) (8)2560000.874544Diehard Count the 1 s (byte) (9)2560000.177324Diehard Parking Lot (10)120000.909532Diehard Min. Distance (2d Circle) (11)80000.362603Diehard 3d Sphere (Min. Distance) (12)40000.616346Diehard Squeez (13)1000000.140148Diehard Sums (14)1000.040395Diehard Runs∗ (15)1000000.562278Diehard Craps∗ (16)2000000.569362Marsaglia and Tsang GCD∗ (17)100000000.931485STS Monobit100000 (100)0.716828STS Runs (101)1000000.801802STS Serial (generalized) (102)1000000.422199RGB Bit Distribution∗ (200)1000000.597944RGB Generalized Min. Distance∗ (201)100000.550842RGB Permutations∗ (202)1000000.497884RGB Lagged Sum∗ (203)10000000.494495RGB Kolmogorov–Smirnov (204)100000.240666Byte Distribution (205)512000000.665759DAB DCT (206)500000.441544DAB Fill Tree∗ (207)150000000.393346DAB Fill Tree 2∗ (208)50000000.385133DAB Monobit 2 (209)650000000.009707Success counts31/31—∗Mean value.


### 6.3. ENT Test Results

The ENT battery of tests consists of 5 tests for randomness. Table3 shows the ENT test results. The information density of the sequence is evaluated using the entropy test expressed as number of bits per byte. Entropy quantifies how much expected information is contained in the generated sequence. G^ shows a maximum level of entropy (ideal value is 8) indicating a good measure of randomness. The chi-square test indicates that the generated sequence is random, and it is extremely sensitive to errors in PRNG. The arithmetic mean is the sum of all the bytes in the generated file divided by the file length. G^ is very close to random, i.e., within the mean range of 127±0.01. The Monte Carlo value converges to π with minimal error 0.01 percent for G^ signifying that the sequence is close to random. The serial correlation coefficient (SCC) test indicates that there is no correlation between each byte with the previous byte in the sequence.Table 3
ENT test results.
Test nameG^Sample size (bytes)246460416Entropy (bits)7.999999Chi-square272.11Arithmetic mean127.4943Monte Carlo value for pi3.141934062SCC−0.000147


### 6.4. TestU01 Results

The results for TestU01 are shown in Table4. TestU01 battery of tests developed by Pierre L’Ecuyer and Richard Simard is one of the most stringent tests for randomness. The binary sequence battery test includes Rabbit (38 tests), Alphabit (17 tests), and Blockalphabit (17 tests) are used to test the randomness of the generators. The test results are shown in Table 4. The generator G^ successfully passed all the tests (p value between [0.001, 0.999]) of the TestU01. This indicates that the generated binary sequence has good randomness and hence unpredictable.Table 4
TestU01 test results.
LengthRabbitAlphabitBlockalphabit10638/3817/1717/17Experimentally through a series of stringent battery of the test, it is seen that generatorG^ has passed all the randomness tests successfully in agreement to the security analysis presented in Section 5. Therefore, it is evident that the generated sequences exhibit good statistical evidence of randomness and can be used confidently in sensitive applications.


## 6.1. NIST Test Results

NIST SP800-22 statistical test suite consists of 15 independent statistical tests to investigate the randomness of the arbitrary long binary sequence produced by the generators. For each test, with a fixed significant level (α=0.01), the quality of the sequence is given as p values. If the p value is >0.01, the generated sequence passes the test; otherwise, it fails. The sample size of 100 binary sequences for each test is used with the bit length of the order 106. The interpretation of the empirical results can be done from the proportion of passing of a test, i.e., the pass rate. The minimum pass rate is calculated from the sample size and the significant level as given in [44]. The minimum pass rate for 100 binary sequences with 0.01 significance level is 0.9602. The test is statistically successful if at least 96 sequences out of 100 sequences pass the test and the generator G^ successfully passed all the 15 tests as seen in Table 1 confirming the randomness of the generated sequence.Table 1
NIST test results.
Test name (test no.)G^p valuep-rate≥0.010.9602Frequency (1)0.9780720.9900BlockFrequency (2)0.7597561.0000CumulativeSums-forward (3)0.2492840.9800CumulativeSums-backward (4)0.8513830.9800Runs (5)0.5749030.9900LongestRun (6)0.8165370.9800Rank (7)0.6163051.0000FFT (8)0.3345380.9900NonOverlappingTemplate∗ (9–156)0.4970080.9900OverlappingTemplate (157)0.9780721.0000Universal (158)0.7791880.9900ApproximateEntropy (159)0.5341460.9900RandomExcursions∗ (160–167)0.4735460.9848RandomExcursionsVariant∗ (168–185)0.3273610.9848Serial 1 (186)0.7399180.9800Serial 2 (187)0.9114131.0000LinearComplexity (188)0.4749861.0000Success—15/15∗Mean value.


## 6.2. Dieharder Test Results

The Dieharder test suite developed by Robert G. Brown consists of 31 stringent tests for distinguishability from random. Thep value distribution generated by each test for Dieharder in contrast to NIST test suite is analyzed by a Kuiper–Kolmogorov–Smirnov (KKS) test, which has a higher sensitivity to deviations from an equal distribution. A random sequence with size 106 bit sequence from generators G^ is used as input for the Dieharder test suite. Table 2 shows the result of the Dieharder battery of tests. The number of trials used in each test is given as tsample. The generators passed all the 31 stringent tests, which indicate that there is evidence of randomness at a high confidence level.Table 2
Dieharder test results.
Test name (test no)G^T samplep valueDiehard Birthday (0)1000.623511Diehard OPERMS (1)10000000.892017Diehard 32 × 32 Binary (2)400000.563151Diehard 6 × 8 Binary Rank (3)1000000.925417Diehard Bitstream (4)20971520.851563Diehard OPSO (5)20971520.867954Diehard OQSO (6)20971520.415923Diehard DNA (7)20971520.442299Diehard Count the 1 s (stream) (8)2560000.874544Diehard Count the 1 s (byte) (9)2560000.177324Diehard Parking Lot (10)120000.909532Diehard Min. Distance (2d Circle) (11)80000.362603Diehard 3d Sphere (Min. Distance) (12)40000.616346Diehard Squeez (13)1000000.140148Diehard Sums (14)1000.040395Diehard Runs∗ (15)1000000.562278Diehard Craps∗ (16)2000000.569362Marsaglia and Tsang GCD∗ (17)100000000.931485STS Monobit100000 (100)0.716828STS Runs (101)1000000.801802STS Serial (generalized) (102)1000000.422199RGB Bit Distribution∗ (200)1000000.597944RGB Generalized Min. Distance∗ (201)100000.550842RGB Permutations∗ (202)1000000.497884RGB Lagged Sum∗ (203)10000000.494495RGB Kolmogorov–Smirnov (204)100000.240666Byte Distribution (205)512000000.665759DAB DCT (206)500000.441544DAB Fill Tree∗ (207)150000000.393346DAB Fill Tree 2∗ (208)50000000.385133DAB Monobit 2 (209)650000000.009707Success counts31/31—∗Mean value.


## 6.3. ENT Test Results

The ENT battery of tests consists of 5 tests for randomness. Table3 shows the ENT test results. The information density of the sequence is evaluated using the entropy test expressed as number of bits per byte. Entropy quantifies how much expected information is contained in the generated sequence. G^ shows a maximum level of entropy (ideal value is 8) indicating a good measure of randomness. The chi-square test indicates that the generated sequence is random, and it is extremely sensitive to errors in PRNG. The arithmetic mean is the sum of all the bytes in the generated file divided by the file length. G^ is very close to random, i.e., within the mean range of 127±0.01. The Monte Carlo value converges to π with minimal error 0.01 percent for G^ signifying that the sequence is close to random. The serial correlation coefficient (SCC) test indicates that there is no correlation between each byte with the previous byte in the sequence.Table 3
ENT test results.
Test nameG^Sample size (bytes)246460416Entropy (bits)7.999999Chi-square272.11Arithmetic mean127.4943Monte Carlo value for pi3.141934062SCC−0.000147


## 6.4. TestU01 Results

The results for TestU01 are shown in Table4. TestU01 battery of tests developed by Pierre L’Ecuyer and Richard Simard is one of the most stringent tests for randomness. The binary sequence battery test includes Rabbit (38 tests), Alphabit (17 tests), and Blockalphabit (17 tests) are used to test the randomness of the generators. The test results are shown in Table 4. The generator G^ successfully passed all the tests (p value between [0.001, 0.999]) of the TestU01. This indicates that the generated binary sequence has good randomness and hence unpredictable.Table 4
TestU01 test results.
LengthRabbitAlphabitBlockalphabit10638/3817/1717/17Experimentally through a series of stringent battery of the test, it is seen that generatorG^ has passed all the randomness tests successfully in agreement to the security analysis presented in Section 5. Therefore, it is evident that the generated sequences exhibit good statistical evidence of randomness and can be used confidently in sensitive applications.


## 7. Discussion

Implementation of cryptographic primitives for practical usage and for memory-constrained devices requires standardization in implementation. Also, the choice of operations involved in the algorithm directly affects the choice of hardware. In this proposal, we have focused to establish a solid approach to create robust and credible chaos cryptographic primitive design methodology. However, it can be observed from the construction that the design uses logistic-sine map-based lattices composed into a CML, and hence, the design only requires implementing mainly logistic-sine map in hardware. Therefore, the performance of the CML and the proposed CSPRNG in hardware or specific suitability to resource constrained devices can be assumed to be on par with the performance similar to that of LS map implementations as in [49, 50]. Furthermore, in future we would like to study the performance of the construction on hardware implementations.As dynamical system with chaotic behaviour, its trajectory will never repeat in theory but due to finite precision limitations in digital implementations may give rise to cycles. The robustness to dynamical degradation is thus captured by measuring the cycle length of symbols or bits produced by a chaotic systems. Since the proposed system passed all NIST tests with 1 million bit length output sequence from the proposed CSPRNG, including the random excursion test which captures the notion of cycle lengths in the output sequence, it can be safely assumed that effect of dynamical degradation is negligible for all practical purposes. Moreover, the experiments are carried out using Python 3.7 which adheres to the IEEE Standard for Floating-Point Arithmetic (IEEE 754), thereby restricting the key space to single and double precision. In this CSPRNG, the only secret is the initial seed or initial vector. Therefore, the key length is proportional to the precision or number of bits used to represent one initial seed in a lattice times the total number of lattices in the CML. For example, if a double precision IEEE 754 representation takes 53 significant and 11 exponent bits, then for 25 lattices, the key length is 275 and the total key space is in the order of2275 without considering the parameters of logistic-sine map which are nondominant factors in the order. Similarly, for a single precision, the total key space is in the order of 2200. In chaos-based cryptography, a key space above 2128 is considered secure to be used for encryption, and hence, for the proposed CSPRNG, the probability of a brute force attack is negligible.Provable security has been demonstrated in chaos cryptography with the Chebyshev chaotic map in a multiparty computation setting using the hardness of computational Diffie–Hellman (CDH) problem’s chaotic equivalent computational chaotic Diffie–Hellman (CCDH) problem in their designs. Such designs use the computational chaotic Diffie–Hellman problem posed by Chebyshev maps to build one-way functions. However, to the best of our knowledge, hardly any provable security is proposed in chaos cryptography for a CSPRNG setting. Some of the works using provable security under multiparty computation setting are [51–53] in which the authors present a formal proof of security in a multiparty computation setting to establish a secret key between parties which do not have a preshared secret key for secure communication. Iwasaki and Umeno [54] improved a vector space cipher by modelling a linear masking attack and proved that the improved algorithm can resist linear masking attack but did not use any standard provable security framework for encryption. The reasoning behind the choice of Chebyshev map used in such designs is due to its inherent property of CCDH which perfectly fits in the provable security framework for multiparty computation setting. Similarly, the proposed CSPRNG uses a CML composed of the LS map which is known to exhibit noninvertible property and fits well in the provable security framework for CSPRNG setting. Hence, any chaotic maps or flows can be used in the provable security framework if it would fit in the choice of provable security framework and setting. The proposed chaos-based CSPRNG design methodology demonstrates such instantiation of construction with a chaotic map for a choice of provable security framework and setting. Moreover, the authors in [55] provide a checklist and the proposed work captures those that are pertinent to a CSPRNG setting. The modern cryptography’s provable security frameworks are indeed designed to capture such notions of attack and attacker capabilities enlisted in [55], and their correlation to this work is as follows:(1)
Cryptographic primitive’s algorithm should be stated explicitly in the form of mathematical model as described in Section4.2(2)
Propositions for algorithms stated and proven explicitly as described from Theorems1 to 3(3)
Specification of domain and range as described in Section4.2 parameter generation(4)
Models capturing attackers’ knowledge of the algorithm and security depending on just secret key as demonstrated through Theorems1 to 3(5)
Proof-driven design approach as demonstrated through in Theorems1 to 3(6)
Discussion on hardness assumptions and dynamic degradation as demonstrated through Theorems1 to 3 and Section 7(7)
Scope of attacks and robustness as captured through the notion of Theorems1 to 3


## 8. Conclusion

The theory that a deterministic system shall produce deterministic output has been proven otherwise with the study of dynamical systems. The constructionG^ is based on the results that deterministic dynamical systems can produce chaos over long range. Moreover, when such systems are made to operate in the region of chaos by choosing system parameters appropriately, they tend to become unpredictable. More precisely, the chosen function δ exhibits unpredictability proving computation of the defined preimage problem as hard or unpredictable making them candidate unpredictable functions according to modern cryptography. It is a proven fact that the pseudorandom number generator constructions satisfying the abstract notions of computational indistinguishability will pass all efficient statistical tests. Such notions to the best of our knowledge hardly have been applied in the design of pseudorandom generator constructions using chaos. This paper presents CSPRNG using the proven Goldreich–Levin generic construction of modern cryptography and then instantiated it with a new CML (δ), namely, G^. The security is proven using the abstract notions of unpredictability, a proven equivalent to computational indistinguishability and modern cryptography primitive design tool. The pseudorandom generator G^ is then proven to be computationally indistinguishable. Pseudorandom sequences generated from such design are then tested using standard statistical randomness test suites used by chaos-based cryptography designers, namely, NIST, Dieharder, ENT, and TestU01. The pseudorandom sequences generated from G^ passed all the tests of NIST, Dieharder, ENT, and TestU01 (tests for bits) test suites proving the claims of abstract notions of unpredictability. Hence, the premise that statistical analysis is used as a necessary condition and rigorous mathematical simulation-based proof is used as sufficient condition is demonstrated to eventually produce better designs. Thus, we believe that the demonstrated design approach will provide new directions beyond statistical analysis in designing chaos-based cryptographic primitives by using modern cryptography design tools. Also, it will motivate chaos-based designers to more often instantiate time-tested proven generic constructions with candidate chaotic functions rather than design generic constructions for new cryptographic primitives. This kind of design approach will lead to robust and credible chaotic cryptographic primitives and prevent depreciating motivation on chaos-based cryptographic primitive design.



---

*Source: 5597720-2021-06-10.xml*