text:
# Cryptanalysis of dynamic look-up table based chaotic cryptosystems

## 1 Introduction

Since M. S. Baptista proposed in 1998 a new cryptosystem based on the property of *ergodicity* of chaotic systems , a number of new algorithms based on variations of Baptista’s have been published . In  we analyzed the security and cryptographic robustness of Baptista’s seminal algorithm. The first variation of Wong  was cryptanalyzed in . We present in this Letter our results after having thoroughly studied Wong’s second and third algorithms .

The ergodicity property is exploited in these algorithms by using the logistic map

$$y_{n+1}=by_n(1y_n),$$
(1)
where $`y_n[0,1]`$ and the parameter $`b`$ is chosen so that Eq. (1) behaves chaotically. In , the most interesting addition consists of using a dynamic table for looking up the ciphertext and plaintext which is no longer fixed during the whole encryption and decryption processes. Instead, it depends on the plaintext, being continuously updated during the encryption and decryption processes. This makes cryptanalysis more difficult, but not impossible.

When the $`i`$th message block is encrypted, the look-up table is updated dynamically by exchanging the $`i`$th entry $`l_i`$ with another entry $`l_j`$ . The location of the latter entry, i.e., the value of $`j`$, is determined by the current value of $`y`$ using the following formula:

$$\upsilon =\frac{yy_{\mathrm{min}}}{y_{\mathrm{max}}y_{\mathrm{min}}}\times N$$
(2)
$$j=i+\upsilon modN,$$
(3)
where $`y_{\mathrm{min}}`$ and $`y_{\mathrm{max}}`$ are the end points of the chosen interval $`[y_{\mathrm{min}},y_{\mathrm{max}})`$ and $`N`$ is the total number of entries in the table .

In , the previously described chaotic cryptographic scheme is generalized by allowing the swapping of multiple pairs of entries in the look-up table during the encryption of each input block, and by allowing multiple runs of encryption on the whole message continuously. Starting from the current entry $`i`$, $`p`$ pairs of entries ($`p1`$) are swapped according to the following rule: $`i(i+\upsilon modN)`$, $`(i+\upsilon +1modN)(i+2\upsilon +1modN)`$, $`(i+2\upsilon +2modN)(i+3\upsilon +2modN)`$, …, $`(i+(p1)\upsilon +p1modN)(i+p\upsilon +p1modN)`$. Once the message has been encrypted, the whole process is repeated again $`r`$ times, $`r1`$. The final look-up table is the hash of the message .

## 2 Classical types of attacks

When cryptanalyzing a ciphering algorithm, the general assumption made is that the cryptanalist knows exactly the design and working of the cryptosystem under study, i.e., he knows everything about the cryptosystem except the secret key. This is an evident requirement in today’s secure communications networks, usually referred to as Kerchoff’s principle \[9, p. 24\]. According to \[9, p. 25\], it is possible to differentiate between different levels of attacks on cryptosystems. They are enumerated as follows, ordered from the hardest type of attack to the easiest:

1. Ciphertext only: The opponent possesses a string of ciphertext.
2. Known plaintext: The opponent possesses a string of plaintext, $`𝐩`$, and the corresponding ciphertext, $`𝐜`$.
3. Chosen plaintext: The opponent has obtained temporary access to the encryption machinery. Hence he can choose a plaintext string, $`𝐩`$, and construct the corresponding ciphertext string, $`𝐜`$.
4. Chosen ciphertext: The opponent has obtained temporary access to the decryption machinery. Hence he can choose a ciphertext string, $`𝐜`$, and construct the corresponding plaintext string, $`𝐩`$.

In each of these four attacks, the objective is to determine the key that was used. The last two attacks, which might seem unreasonable at first sight, are very common when the cryptographic algorithm, whose key is fixed by the manufacturer and unknown to the attacker, is embedded in a device which the attacker can freely manipulate. Daily life examples of such devices are smartcards, electronic purse cards, GSM phone SIM (Subscriber Identity Module) cards, POST (Point Of Sale Terminals) machines, or web application session token encryption.

## 3 Keystream attacks

Although at first sight the cipher under study might look like a block cipher, in fact it behaves as a stream cipher \[9, p. 20\], a fundamental weakness as is to be seen. The operation of the algorithm as a stream cipher can be explained as follows. Suppose $`K`$ is the key, given by $`y_0`$ and $`b`$, and that $`𝐩=p_1p_2\mathrm{}`$ is the plaintext string. A keystream $`𝐤=k_1k_2\mathrm{}`$ is generated using Eq. (1). This keystream is used to encrypt the plaintext string according to the rule

$$𝐜=e_{k_1}(p_1)e_{k_2}(p_2)\mathrm{}=c_1c_2\mathrm{}$$

Decrypting the ciphertext string $`𝐜`$ can be accomplished by computing the keystream $`𝐤`$ given the knowledge of the key $`K`$ and undoing the operations $`e_{k_i}`$. In  the keystream is the complete orbit followed by iterating Eq. (1) from the initial point $`y_0`$ with parameter near $`b=4.0`$. The unit interval is divided up into $`N`$ equally spaced bins, each corresponding to a symbol of the alphabet in use. However, instead of considering the whole unit interval, only the subinterval $`[0.2,0.8)`$ is used. As a consequence of the natural invariant density of Eq. (1), the orbit will visit frequently the forbidden subintervals $`[0,0.2)`$ and $`[0.8,1]`$.

As an example of how to generate the keystream, let us iterate Eq. (1) starting from $`y_0=0.1777`$ and $`b=3.9999995`$, as in . Let $`s_i`$ be the symbol corresponding to each useful subinterval where $`y_i`$ lands, and let $`x`$ be the iterates which visit the forbidden subintervals. The orbit followed is $`y_i=`${0.5844…, 0.9714…, 0.1109…, 0.3945…, 0.9555…, 0.1698…, 0.5641…, 0.9835…, 0.0647…, 0.2420…, …}, and is transformed into the keystream $`𝐤=s_{165}xxs_{84}xxs_{156}xxs_{18}\mathrm{}`$ Next we show how to recover the keystream using chosen ciphertext, chosen plaintext, and known plaintext attacks. It is important to note that knowing the keystream $`𝐤`$ generated by a certain key $`K`$ ($`y_0`$ and $`b`$) is entirely equivalent to knowing the key. Therefore, our keystream attacks focus on recovering $`𝐤`$.

### 3.1 How to circumvent the look-up table

The election of the look-up table updating method is most unfortunate, since it allows the attacker to easily predict the new positions of the symbols even without the exact knowledge of the value of $`y`$. In order to initially simplify our analysis, we use a variable number $`N`$ of symbols, $`N=2^n,n=1,\mathrm{},8`$. First, we assume that the source emits two different symbols, $`S_2=\{s_1,s_2\}`$. When the orbit lands on the first subinterval $`[0.2,0.5)`$, the table will be updated following Eqs. (2) and (3). Given that $`0.2y<0.5`$, we have that

$$0\upsilon =\frac{yy_{\mathrm{min}}}{y_{\mathrm{max}}y_{\mathrm{min}}}\times 2=\frac{y0.2}{0.6}\times 2<1,$$

and thus $`\upsilon =0`$ and Eq. (3) is equivalent to:

$$j=imod2.$$

When the orbit lands on the second subinterval $`[0.5,0.8)`$, then $`0.5y<0.8`$, and thus $`\upsilon =1`$ and Eq. (3) becomes:

$$j=(i+1)mod2.$$

If the source emits four different symbols, $`S_4=\{s_1,s_2,s_3,s_4\}`$, then $`\upsilon =0`$ if the orbit lands on \[0.2,0.35), $`\upsilon =1`$ if the orbit lands on \[0.35,0.5), $`\upsilon =2`$ if the orbit lands on \[0.5,0.65), and $`\upsilon =3`$ if the orbit lands on \[0.65,0.8).

The generalization for higher order sources is immediate. Even when multiple pairs are swapped at each encryption run, as in , the look-up table evolution is easily predicted. As a consequence, the look-up table plays no significant security role during the encryption process. It is not necessary to know the exact value of $`y`$ to predict the next update. It suffices to know the subinterval where $`y`$ lands. Therefore, the updated table depends solely on the plaintext, and not on the key ($`y_0`$ and $`b`$), to the advantage of the attacker. When encrypting the same plaintext using different keys, the same updating sequence will take place for the look-up table. Likewise, the same message will always yield the same hash value regardless of the key used.

### 3.2 How to obtain the keystream

In this subsection different attacks are described. Each of them aims at the recovery of the keystream.

#### 3.2.1 Chosen ciphertext attack

The chosen ciphertext attack is straightforward. Simply request the plaintext of the one-block ciphertexts $`𝐜=1`$, $`𝐜=2`$, $`𝐜=3`$, …, until the desired length of the keystream is reached. Either the correct symbol (when the iterate lands on a site) or an error (when it lands outside the boundaries) is obtained, one by one. Once the desired length of keystream has been recovered in this way, any message encrypted with the same values of $`y_0`$ and $`b`$ can easily be decrypted. Under this attack, the dynamically updated look-up table has no effect at all. This attack requires as many one-block ciphertexts as the length of the keystream that is to be recovered. This attack does not work on , because the attacker does not know the encrypted values of $`p`$ and $`r`$, the first two blocks of the ciphertext.

#### 3.2.2 Chosen plaintext attack

Let us deal with the chosen plain text attack next. To make things even simpler at first, we assume the fourth order symbol source $`S_4`$ and that $`r_{\mathrm{max}}=1`$ (see ). Although unknown to the cryptanalyst, the system key $`K`$ is given by $`y_0=0.1777`$ and $`b=3.9999995`$, using the interval $`[0.2,0.8)`$, as in .

Our goal is to find out the exact position of all occurrences of $`s_1`$,$`s_2`$,$`s_3`$, and $`s_4`$ in the keystream. But this task is not as easy as requesting the ciphertext of $`𝐩=s_1s_1s_1\mathrm{}`$, then of $`𝐩=s_2s_2s_2\mathrm{}`$, etc., as in . The dynamic look-up table prevents knowing whether a certain symbol corresponds to its original position in the table or has been already changed. But given that the changes produced in the table are known even when the exact value of $`y`$ is unknown, the following attack can be designed.

First, in order to know the exact position of all symbols $`s_1`$ in the keystream $`𝐤`$, we need to construct an adequate plaintext $`𝐩`$. Table 1 represents the final result of the process followed to compute the correct value of $`𝐩`$. We start constructing Table 1 by filling in columns $`i`$ and $`k_i`$, already known in advance. Columns 0, 1, 2, and 3 reflect the current state of the look-up table, i.e., which symbol is at which position at any given moment. Next, we proceed row by row, in the following way:

1. Assign to $`p_i`$ the value of the symbol ($`s_1`$, $`s_2`$, $`s_3`$, or $`s_4`$) in the previous row in the subinterval corresponding to $`k_i`$. At start, the look-up table is not yet altered.
2. Calculate $`j=(i+k_i)mod4`$.
3. Update the look-up table by interchanging the symbols in the subintervals $`i,j`$.
4. Proceed to the next row.

After proceeding in this way, the plaintext that corresponds to all symbols $`s_1`$ in the keystream is worked out: $`𝐩=\mathrm{0\hspace{0.33em}0\hspace{0.33em}0\hspace{0.33em}0\hspace{0.33em}0}\mathrm{}`$ This plaintext is always periodic. The corresponding ciphertext is requested, obtaining: $`𝐜=\mathrm{10\hspace{0.33em}9\hspace{0.33em}6\hspace{0.33em}6\hspace{0.33em}7}\mathrm{}`$. Hence, it is known for sure that there is a true symbol $`s_1`$ at the 10th position, and at the 19th, etc. The partial keystream already obtained is $`𝐤=xxxxxxxxxs_1xxxxxxxxs_1xxxxxs_1xxxxxs_1xxxxxxs_1\mathrm{}`$

Next, we are to obtain the exact position of all symbols $`s_2`$ by constructing Table 2. This table informs us that we have to request the ciphertext of $`𝐩=\mathrm{1\hspace{0.33em}0\hspace{0.33em}2\hspace{0.33em}2\hspace{0.33em}2\hspace{0.33em}0\hspace{0.33em}3\hspace{0.33em}3\hspace{0.33em}3\hspace{0.33em}0\hspace{0.33em}1\hspace{0.33em}1}\mathrm{}`$, obtaining $`𝐜=\mathrm{4\hspace{0.33em}11\hspace{0.33em}14\hspace{0.33em}5}\mathrm{}`$ The improved partial keystream already obtained is $`𝐤=xxxs_2xxxxxs_1xxxxs_2xxxs_1xxxxxs_1xxxs_2xs_1xxs_2xxxs_1\mathrm{}`$

If we repeat this process, generating Table 3 and 4 for symbols $`s_3`$ and $`s_4`$, and requesting the corresponding ciphertexts, we would obtain the following complete keystream:

$$𝐤=s_3xxs_2xxs_3xxs_1s_4s_4s_4xs_2xxxs_1s_4s_4xs_3xs_1s_4s_4xs_2xs_1s_4xs_2xxxs_1\mathrm{}$$
(4)
The generalization for higher order sources is immediate. This attack is very inexpensive too, since it only requires $`N=2^n`$ plaintexts, $`1n8`$.

When $`r_{\mathrm{max}}>1`$, the same procedure must be followed. However, there will be blanks in the recovered keystream, because many valid iterations will be skipped. In many cases, though, it is possible to narrow down the number of possible symbols. Once the partial keystream has been worked out, while trying to decrypt a ciphertext following the decryption method, iterates will land on an $`x`$. The only possible symbols for those $`x`$ are those lying before the $`x`$ at a distance smaller than $`r_{\mathrm{max}}`$. In this way, the possibilities are greatly reduced, in many cases to only one possible value (the correct one). When more than one value is possible, there are two courses of action. If the plaintext is not of random nature, then the gaps can easily be filled selecting by the context one symbol amongst the possible ones. On the other hand, if the plaintext is random, then a new plaintext must be requested, made by all the previous correct symbols plus one of the candidates. If the ciphertext is equal to the expected one, then the guess was correct. Otherwise, new plaintexts must be encrypted until the correct guess is used.

There is still another possible modification presented in . A new parameter, called threshold ($`y_{\mathrm{threshold}}`$), can be introduced along with the key. The current value of $`y`$ can be checked against this threshold, so that the table is updated only when $`y>y_{\mathrm{threshold}}`$. However, although it is assumed that this addition improves security, it is very easy to deduce which is the subinterval to which $`y_{\mathrm{threshold}}`$ belongs. It can be observed in Table 1 that when the plaintext symbol to be encrypted is $`s_1`$, the table is never effectively updated. After the $`N=2^n`$ tables are constructed, if $`y_{\mathrm{threshold}}>y_{\mathrm{min}}`$, then there must occur repeated values in the recovered keystream. Given that the position of $`s_1`$ is always correct in the keystream, we know for sure that symbols $`s_t`$ for $`t>1`$ which coincide with a previous $`s_1`$ symbol must be incorrect. The greatest value of $`t`$ indicates which is the symbol $`y_{\mathrm{threshold}}`$ belongs to. This attack works on  too. The attacker can still predict the evolution of the look-up table with the only knowledge of the plaintext.

#### 3.2.3 Known plaintext attack

Under this attack, each plaintext/ciphertext pair allows for the recovery of a portion of the keystream. For the sake of simplicity and without loss of generality, let us use once again the $`S_4`$ source, $`r_{\mathrm{max}}=1`$, and $`y_{\mathrm{threshold}}=y_{\mathrm{min}}`$. Let us set $`𝐩=\mathrm{1\hspace{0.33em}0\hspace{0.33em}3\hspace{0.33em}0\hspace{0.33em}0}\mathrm{}`$, whose ciphertext is $`𝐜=\mathrm{4\hspace{0.33em}11\hspace{0.33em}5\hspace{0.33em}9\hspace{0.33em}5}\mathrm{}`$ Table 5 can be easily constructed, which allows to recover a correct portion of the keystream: $`𝐤=xxxs_2xxxxxxxxxxs_2xxxxs_4xxxxxxxxs_2xxxxs_2\mathrm{}`$ This process should be repeated with as many known plaintexts as possible, to recover as big a portion of the keystream as possible. Therefore, this attack does not guarantee total recovery of the keystream. It would work in a similar way for .

### 3.3 How to decrypt using the keystream

In the previous subsection, different methods to obtain the complete keystream where introduced. Next, we explain how to recover the plaintext from a ciphertext when the keystream is known.

For simplicity, the fourth order symbol source $`S_4`$ is used. We assume the attacker already knows the keystream given by Eq. (4) and possesses the following ciphertext: $`𝐜=\mathrm{1\hspace{0.33em}10\hspace{0.33em}4\hspace{0.33em}4\hspace{0.33em}4}\mathrm{}`$ In order to decrypt it, Table 6 is constructed in the following way. First, fill all the values of $`k_i`$ with the symbol found in the keystream at the positions indicated by the ciphertext. Next, according to the current state of the look-up table, assign the correct value to $`p_i`$ which corresponds to each $`k_i`$. Calculate the value of $`j`$ and update the look-up table accordingly. Move to the next row and repeat the process until the ciphertext has been exhausted.

## 4 Security of the hash

We have tested that breaking the hash algorithm is possible when $`p=1`$ and $`r=1`$, even without the knowledge of the key ($`y_0`$ and $`b`$). Let us consider for example the following message: “Transfer $10000 to Alvarez’s account.”. If encoded using 4-bit symbols, its hash is $`h=1\mathrm{E}825\mathrm{B}\mathrm{C}0\mathrm{A}36974\mathrm{F}\mathrm{D}`$, expressed in hexadecimal. Changing the message into “Transfer $30005 to Alvarez’s account.” produces exactly the same hash. In order to avoid attacks on the hashing scheme, it is all important that $`r>1`$ and $`p>1`$. In effect, in  two runs and a small value of $`p`$ are suggested. Greater values would increase security, but penalize on speed.

Although in  it is claimed that this hash can be treated as a message authentication code (MAC), in fact it can not. A MAC is a key-dependent one-way hash function. However, as already proved, the look-up table, and hence the hash, does not depend on the key ($`y_0`$ and $`b`$). Therefore, this scheme does not behave as a MAC but as a one-way hash function, even though the knowledge of the key is necessary to verify the hash when both authenticity and secrecy are to be provided.

## 5 Conclusions

In spite of dynamically updating the look-up table, the same fundamental weakness present in Baptista’s algorithm  is reproduced in the chaotic cryptosystems proposed in , as proved by our different attacks. As a consequence of our attacks, an important conclusion is that implementations of these algorithms can never reuse the same key because if so, they are easily broken. Furthermore, the look-up table does not depend on the key, but only on the plaintext, thus facilitating cryptanalysis. After these attacks, we conclude that the lack of security, along with the low encryption speed, discourage the use of these algorithms for secure applications. We are to investigate how the weaknesses outlined in this Letter might affect the security of other Wong’s variants .

This research was supported by Ministerio de Ciencia y Tecnología, Proyecto TIC2001-0586. Our thanks to K. W. Wong for providing his source code.


format: text

text:
# How low is the thermodynamical limit?

## I Introduction

Not only in heavy ion collisions, but also in $`pp`$ and even in $`e^+e^{}`$ collisions exponential transverse mass spectra has been observed besides a power law tail at relatively high transverse momenta. The exponential shape at medium $`p_T`$ was often interpreted as an indication that the source of the observed hadrons can be described by a temperature related to the slope of these spectra. This view is most prominent in the thermal modelsTHERMAL  which assume a thermally equilibrated state, well described by the familiar equilibrium thermodynamics.

The experimental data from CERN SPS and RHIC show an exponential shape in the transverse mass spectrum best fitted by $`\mathrm{exp}((mm_T)/T)`$, where $`m_T=\sqrt{m^2+p_T^2}`$ is the transverse mass of a particle with mass $`m`$EXP . The stiffness of these spectra, $`T`$, has still to be corrected for collective flow effects: for high momenta a relativistic blue-shift factor, for low momenta a mass dependent kinetic flow energy addition occurs in this parameter. The conjectured temperature, $`T_0`$, of a thermally equilibrated state is therefore usually higher than the directly observed slope parameter, $`T`$. Characteristic values at RHIC are $`T140`$ MeV and $`T_0210`$ MeV, so the assumed temperature is well above the color deconfinement temperature predicted by recent lattice QCD calculations.

There is, however, doubt whether a thermally equilibrated state can be formed in such a short time, during which the final state fireball at these high bombarding energies develops. There is no known hadronic process which would lead to a thermal state from a far off-equilibrium initial situation on a time scale of $`12`$ fm/c. It is strongly tempting to consider quark level mechanisms as reason for the observed exponential spectra. Several such mechanisms has already been suggested on a subhadronic level. Ref.Bialas  considered the Schwinger mechanism with a Gaussian fluctuating string tension, which leads to exponential $`m_T`$ spectra. Having color ropes in mind, the effective string tension may have a Gaussian distribution due to a random color chargation process in the limit of high color. Another idea is to consider the fluctuation of temperature, distributed according to a Gamma distributionWilk . In this case the average of exponentials leads to a Tsallis distribution, which is still well approximated by an exponential at soft momenta, while ends in a power-law tail at high momenta. In this paper we shall have a closer look on a recently suggested hadronization mechanism, on the parton recombinationRECOMB , as a possible source of the experimentally observed exponential spectra. In this case we begin with cut power-law minijet distributionsPARTON , having a form of the canonical Tsallis distributionTSALIS , and combine their limiting distribution for many-fold recombinationPLB .

According to this goal first we review how the Gaussian distribution emerges as a limiting distribution and recall the central limit theorem of statistics. Then we consider a simple example not falling under the conditions of this renown theorem, but still leading to a non-trivial limiting distribution. Finally we relate this result to parton recombination and to the canonical Tsallis distribution, which gives an improved quantitative description of experimental findings compared to the naive thermal model.

## II The central limit theorem

In order to demonstrate, how fast a Gaussian limiting distribution may develop, let us first consider the distribution of the scaled sum of uniform random deviates. Let $`x_i`$ be a uniform random deviate in $`(1,1)`$ and $`P_n(x)`$ the distribution of $`x=\sqrt{\frac{3}{n}}_{i=1}^nx_i`$. The statement of the cited theorem is that in the limit of infinite $`n`$ the distribution of the variable $`x`$ exactly becomes the normal distribution.

$$P_{\mathrm{}}(x)=\frac{1}{\sqrt{2\pi }}e^{x^2/2}.$$
(1)
Before we review how and why this happens it is educating to make some guesses how large $`n`$ actually should be in order to mistake such a distribution for a Gaussian. The answer is surprisingly low (cf. Fig.1). The $`n=1`$ case is the uniform distribution, the $`n=2`$ has a triangular shape. The finiteness of the sample ($`m=200000`$) smoothes the differences out, it is therefore not easy to distinguish already the $`n=3`$ or $`n=4`$ case from the Gaussian in a numerical experiment.

Now we turn to the proof of the limiting distribution being a Gaussian. Consider the Fourier transform of $`P_n(x)`$:

$$\stackrel{~}{P}_n(k)=_{\mathrm{}}^{\mathrm{}}𝑑xe^{ikx}\underset{i=1}{\overset{n}{}}\left(\frac{1}{2}_1^1𝑑x_i\right)\delta (x\sqrt{\frac{3}{n}}\underset{j=1}{\overset{n}{}}x_j).$$
(2)
After x-integration it turns to be a product of $`n`$ equal factors:

$$\stackrel{~}{P}_n(k)=\left(\frac{\mathrm{sin}(k\sqrt{3/n})}{k\sqrt{3/n}}\right)^n.$$
(3)
The large $`n`$ limit of this expression is a Gaussian:

$$\stackrel{~}{P}_{\mathrm{}}(k)=\underset{n\mathrm{}}{lim}\left(1\frac{k^2}{2n}+\mathrm{}\right)^ne^{k^2/2}.$$
(4)
Fourier transforming back to x-space gives the required statement. The phenomenon is more general. Let $`x`$ be a weighted sum of $`n`$ independent random variables:

$$P_n(x)=(\underset{i=1}{\overset{n}{}}w(x_i)dx_i)\delta (xa_n\underset{j=1}{\overset{n}{}}x_j).$$
(5)
each distributed according to the same probability density $`w(x)`$. Then the so called central moments, which describe correlations,

$$c_j(n)=\left(\frac{}{ik}\right)^j\mathrm{log}\stackrel{~}{P}_n(k)|_{k=0},$$
(6)
can be obtained easily from the central moments $`c_j(1)`$ of the $`P_1(x)=w(x)`$ distributions using $`\mathrm{log}\stackrel{~}{P}_n(k)=n\mathrm{log}\stackrel{~}{w}(ka_n)`$: $`c_j(n)=na_n^jc_j(1)`$. Whenever $`a_n1/\sqrt{n}`$, $`c_j(n)n^{1j/2}c_j(1)0\mathrm{as}n\mathrm{}`$ for $`j>2`$. This completes the proff of the Central Limit Theorem.

There are exemptions to this theorem. Whenever $`\mathrm{log}\stackrel{~}{P}_{\mathrm{}}(k)`$ is not differentiable arbirary times in the vicinity of $`k=0`$, or not the proper scaling factor $`a_n`$ is used, or the base distribution $`w(x)`$ has a long tail not approaching zero fast enough. In the last case there can be a limiting distribution, it is just not Gaussian. As an interesting example we study the convolution of normalized Lorentzians

$$w(x)=\frac{R}{\pi }\frac{1}{x^2+R^2}$$
(7)
The logarithm of the Fourier transform is not differentiable at $`k=0`$: $`\mathrm{log}\stackrel{~}{w}(k)=|k|R`$. The n-fold convolution’s Fourier transform also has a non-differentiable logarithm, $`\mathrm{log}\stackrel{~}{P}_n(k)=nR|k|a_n`$. It can, however, be found a finite limiting distribution for ($`n\mathrm{}`$) if $`a_n=1/n`$. In this case the Lorentzian is a fixed point of the convolution and scaling. The limiting Lorentzian distribution is also long-tailed, so the central moments diverge. Aiming at physical applications we have to regularize. We use a small parameter, $`m`$, for this purpose and at the end take the nontrivial double limit $`m0`$ and $`n\mathrm{}.`$ Starting with regularized Lorentzians, the Fourier transform has the form of the experimentally observed $`mm_T`$ exponential,

$$\stackrel{~}{w}(k)=\mathrm{exp}(\frac{m\sqrt{k^2+m^2}}{T})$$
(8)
with $`T=1/R`$. Now $`\mathrm{log}\stackrel{~}{w}(k)=R(m\sqrt{k^2+m^2})`$ with vanishing odd central moments, and with regular even central moments, $`c_{2j}(1)\frac{R}{m^{2j1}}`$. The limiting distribution is obtained by keeping $`M=nm`$ constant and scaling with $`a_n=1/n`$ again. It has the following Fourier spectrum

$$\stackrel{~}{P}_{\mathrm{}}(k)=e^{(M\sqrt{k^2+M^2})/T}.$$
(9)
This resembles the original regularized distribution, but with an eventually finite mass $`M`$. The low and high momentum limits are Gaussian and pure exponential, respectively.

## III Parton dressing to exponential spectra

Combining hadrons from many partons also results in a limiting distribution, which is not Gaussian. We consider an additive quark model where the hadron mass is made of $`n`$ approximatevly equal partons: $`M=E_i=nm.`$ The variable, $`x=\frac{{\scriptscriptstyle E_ix_i}}{{\scriptscriptstyle E_i}}=\frac{1}{n}x_i`$ is the center of energy coordinate. Its limiting distribution, $`P_{\mathrm{}}(x)`$ can be viewed as the hadron wave function squared. Its Fourier transform, $`\stackrel{~}{P}(k)`$ is proportional to the hadron spectrum.

While constructing from ”equal-right” partons, we have $`\stackrel{~}{P}_n(k)=\stackrel{~}{w}(k/n)^n`$. The particular cases $`n=2`$ and $`n=3`$ of this formula have been used in parton recombination models of hadronization recently. The partons before hadronization show a cut power law transverse momentum distribution, as fitted to minijets obtained in the framework of pQCD based calculations:

$$\stackrel{~}{w}(k)=a\left(1+\sqrt{k^2+m^2}/b\right)^c$$
(10)
Here $`b`$ and $`c`$ are parameters of the parton distribution, in no way connected to a thermal state, $`m`$ is the transverse mass at zero rapidity, and finally $`a`$ can be obtained from the normalization condition, $`\stackrel{~}{w}(0)=1`$. Note that this distribution is a power law for large transverse momenta $`lim_{|k|m,b}\stackrel{~}{w}(k)=ab^c|k|^c`$.

We construct a constituent quark and eventually hadrons from $`n`$ such partons, keeping the total mass $`M=nm`$ fixed. We arrive at

$$\stackrel{~}{P}_n(k)=a^n\left(1+\frac{1}{nb}\sqrt{k^2+M^2}\right)^{nc}$$
(11)
In the $`n\mathrm{}`$ limit this gives the exponential distribution in the transverse mass

$$\stackrel{~}{P}_{\mathrm{}}(k)=\mathrm{exp}\left(\frac{M\sqrt{k^2+M^2}}{b/c}\right).$$
(12)
This is exponential of the reduced transverse mass $`M_TM=\sqrt{k^2+M^2}M`$ has a slope $`T=b/c`$. This is not a temperature, it is not related to any energy exchange with a heat reservoir. The large parameter by which one approaches the limiting distribution is the foldness of the recombination; in the present model the number of independent primordial partons dressing to a hadron constituent.

## IV Tsallis distribution and thermal model

The cut power law used in minijet fits and modified as a function of energy in the hadronization model presented above accidentally coincides with the canonical Tsallis distribution. This distribution can be derived from a generalization of the Boltzmann entropy formula first suggested by Tsallis:

$$S_q=\frac{1}{1q}\underset{i}{}(w_i^qw_i)$$
(13)
In order to relate to our model we use $`q=11/n`$. We get

$$S_q=n\underset{i}{}w_i(w_i^{1/n}1)\underset{i}{}w_i\mathrm{ln}w_i.$$
(14)
The canonical distribution maximizes the entropy with the following constraints: $`_iw_i=1`$ and $`_iw_i\epsilon _i=E`$. The use of a lagrange multipliers $`\beta `$ leads to the following distribution which minimizes $`S_q\beta E`$:

$$w_i=\frac{1}{Z}\left(1+\frac{\beta \epsilon _i}{n}\right)^n$$
(15)
with $`Z=_i(1+\beta \epsilon _i/n)^n`$ for the proper normalization.

Based on this distribution the free energy can be derived as well as relations reminding to rhe familiar thermodynamical relations. The Tsallis distribution can hence be regarded as a generalization of equilibrium thermodynamics. Among its physical realizations it is particularly interesting the case of finite heat reservoirs.

In view of this formalism we interpret the one parton distribution as a canonical Tsallis distribution,

$$w_1=(1+\frac{E}{b})^c=w_{\mathrm{Tsallis}}(E;T,11/c)$$
(16)
with $`T=b/c`$. Recombination of $`n`$ such partons leads to another Tsallis distribution with the same ”temperature”, but closer to the equilibrium case $`q=1`$:

$$w_n=w_1(E/n)^n=(1+\frac{E}{nb})^{nc}=w_{\mathrm{Tsallis}}(E;T,11/(nc)).$$
(17)
Arriving at the finally observed hadrons with $`c8`$ and $`n=2\mathrm{}6`$ one gets really close to the limiting exponential

$$w_{\mathrm{}}=w_{\mathrm{Tsallis}}(E;T,1)=e^{E/T}.$$
(18)
This property may explain the relative, and so far unexplained, success of the thermal model.

Finally it is interesting to explore the potential of the Tsallis distribution with respect to particle numbers and the energy per particle, since these are the most profound predictions of the thermal model. For the sake of simplicity we consider here the analytically solvable case of massless particles.

The number of a particle in a volume $`V`$ with internal degeneracy factor $`d`$ is given by the integral of the canonical Tsallis distribution,

$$N=\frac{d}{2\pi ^2}V_0^{\mathrm{}}p^2𝑑p\left(1+\frac{E}{b}\right)^c.$$
(19)
In the massless case, $`E=|p|`$, and we get

$$N=\frac{d}{2\pi ^2}Vb^3\frac{2}{(c1)(c2)(c3)}.$$
(20)
In general this is a bigger number for finite $`c`$ than for the Boltzmann distribution at $`nc\mathrm{}`$: $`N(c)/N(\mathrm{})>1`$. This ratio is $`2.4,1.5,1.3`$ for $`c=8,16,24.`$

The energy is given by another integral,

$$E=\frac{d}{2\pi ^2}V_0^{\mathrm{}}p^2𝑑pE\left(1+\frac{E}{b}\right)^c$$
(21)
which can as well be calculated in a closed form for massless particles, $`E=|p|`$:

$$E=\frac{d}{2\pi ^2}Vb^4\frac{6}{(c1)(c2)(c3)(c4)}$$
(22)
The energy per particle becomes $`E/N=\frac{3b}{c4}`$ resulting in $`E/N1.07`$ GeV for $`b=1.39`$ GeV and $`c=7.9`$, and at the same time predicting a slope $`T176`$ MeV for the $`m_T`$ exponential at low momenta $`p_Tbc10`$ GeV.

## V  Conclusion

We reviewed limiting distributions of familiar short tailed and exceptional long tailed distributions. We have seen, that already a few, $`n=34`$ independent random comopnents may lead to a distribution which is hard to distinguish from the limiting case on finite, fluctuating data samples.

Non Gaussian limiting distributions exist with altered (non $`1/\sqrt{n}`$) scaling laws. For the high energy hadronization process it is particularly interesting to consider cut power law distributions, which in the limiting case combine to exponential spectra. This happens with the $`1/n`$ scaling, pointing out a possible interpretation as hadron spectra showing the Fourier transform of the distribution of the center of energy of the recombining partons.

Minijet partons obtained using pQCD processes, and actually also experimentally observed spectra in $`pp`$ collisions are Tsallis distributed at $`T170200`$ MeV, and with $`E/N1`$ GeV. These two numbers can be simultanously described by a Tsallis distribution with the parameters $`b=1.39`$ GeV and $`c=7.9`$, when considering massless particles. The same simple consideration fails for the familiar Boltzmann distribution of the thermal equilibrium with a factor of $`2`$. At finite mass these integrals can be calculated only numerically. Considering massive particles with a mass around the pion mass, our results do not change dramatically. At the mass of 1 GeV, however, the Boltzmann distribution reaches $`E/N1`$ GeV and the Tsallis distribution overshoots with a factor of 2.

###### Acknowledgements.

This work has been supported by the Goethe University, Frankfurt and by the Hungarian National Research Fund OTKA (T034269). Special thanks to Professor Walter Greiner for organizing this NATO Advanced Study Institute meeting at Kemer, Turkey, which location created a perfectly relaxing and inspiring atmosphere.


text:
# The Satellite-substructure Connection

## 1. Introduction

When numerical simulations of cold dark matter (CDM) halo formation reached sufficient resolution a few years ago, they revealed that a wealth of dense substructure, the undigested remains of ancient hierarchical merging, should still survive in these systems at the present day (Klypin et al. 1999; Okamoto & Habe 1999; Moore et al. 1999). The properties of halo substructure will be a sensitive test of the nature of dark matter if we can manage to quantify them observationally, for instance in strong gravitational lens systems (cf. talks by P. Schneider and N. Dalal in these proceedings). Halo substructure must also be linked to satellite galaxies, such as the dozen dwarf satellites of the Milky Way, although the exact nature of the connection remains problematic, given the huge discrepancy between the number of subhalos predicted by simulations and the number of luminous satellites observed locally.

Before we can reach firm conclusions on the properties of halo substructure or the nature of the satellite-substructure connection, however, we should first confirm that current simulations of substructure have converged to a definite and accurate prediction of its properties. For many years, N-body simulations suffered from ‘overmerging’, the artificial disruption of substructure due to numerical effects. It is still not clear that all the properties of simulated halo substructure have converged to level required for applications such as lens modeling. To test for the possibly of residual overmerging, we will compare purely numerical results with semi-analytic (SA) predictions, using a recently developed SA model of halo formation.

## 2. Is Overmerging Over Yet?

The SA model of Taylor & Babul (2003, TB03 hereafter) provides an alternative to direct numerical simulation of halo formation. It combines extended Press-Schechter merger histories, which predict when subhalos merge, with an analytic description of orbital evolution and mass loss, which determines how they evolve subsequently. While the model is approximate in many ways, it also avoids some of the strongest biases in the purely numerical studies, and thus provides an interesting point of comparison.

Fig. 1a shows the mass spectrum of subhalos in simulations by Moore et al. (1998, 1999) and Ghigna et al. (2000) (dotted lines), compared with the SA model of TB03 (thick solid lines, with thin solid lines showing the 1-$`\sigma `$ variance). In the outer part of the halo, the two techniques agree to within 10–20%. In the inner regions, where higher densities and longer evolution times would enhance numerical overmerging, the SA model predicts up to twice as much substructure at a given mass. In Fig. 1b, we compare the spatial distribution of subhalos in simulations of increasing resolution (panels from right to left). While the amount of central substructure increases slowly with resolution, there is no obvious sign of convergence – simulations at even higher resolution might find yet more subhalos in the central regions, as predicted by the SA model (solid lines).

## 3. Implications for Lensing Measurements of Substructure

By examining flux-ratio anomalies in multiply imaged quasars, strong lensing studies can constrain the amount of substructure along lines of sight through the center of galactic halos. Robust predictions of the amount of central substructure are essential to take full advantage of this work. Fig. 2a compares predictions for the number of subhalos and the mass fraction in substructure in the highest-resolution simulation and in the SA model. The differences discussed previously produce an order-of-magnitude increase in the predicted mass fraction in the central regions. Interestingly, the level predicted by the SA model is roughly that inferred from observations (e.g. N. Dalal, these proceedings). The SA model also predicts a large scatter in the mass fraction, however. Fig. 2b shows that the amount of substructure decreases as systems age. Dynamically young systems (those whose halos have formed recently) have 3–4 times more mass in substructure then more relaxed systems. This large scatter implies that sample selection will be an important factor in lensing studies.

## 4. The Satellite-substructure Connection

Many explanations have been proposed to account for the apparent discrepancy between the large numbers of subhalos predicted in CDM models and the few luminous satellites seen around galaxies like the Milky Way. Two generic solutions are that early photoionization heated gas in low-mass halos, halting star formation in all but the oldest of these systems (e.g. Bullock et al. 2000; Benson et al. 2002), or alternatively that strong feedback suppresses star formation in all low-mass halos, and that observed dwarf galaxies actually reside in the central parts of much larger CDM subhalos (Stoehr et al. 2003, Hayashi et al. 2003). To distinguish between these models, we can ask more generally: are local satellites associated with the most massive subhalos, or with the oldest subhalos? Fig. 3 shows the cumulative radial distribution of satellites around the Milky Way, (assuming a virial radius of 310 kpc) compared with the average distribution of the dozen most massive subhalos found in each of several hundred merger trees. The satellites are clearly more clustered than the most massive subhalos. Two-thirds of them are within roughly 100 kpc of the Milky Way, for instance, whereas fewer than 1 tree in 100 shows this degree of clustering for its most massive substructure. More detailed analysis (Taylor, Babul & Silk, in preparation) strengthens the conclusion that the luminous satellites of the Milky Way must correspond to the oldest substructures in its halo, rather than the most massive ones.

## References

Benson A. J., Lacey C. G., Baugh C. M., Cole S., Frenk C. S., 2002, MNRAS, 333, 156

Bullock J. S., Kravtsov A. V., Weinberg D. H., 2000, ApJ, 539, 517

Ghigna S., Moore B., Governato F., Lake G., Quinn T., Stadel J., 2000, ApJ, 544, 616

Hayashi, E., Navarro, J. F., Taylor, J. E., Stadel, J., & Quinn, T. 2003, ApJ, 584, 541

Klypin A., Gottlöber S., Kravtsov A. V., Khokhlov A. M., 1999, ApJ, 516, 530

Moore B., Governato F., Quinn T., Stadel J., Lake G., 1998, ApJ, 499, L5

Moore B., Ghigna S., Governato F., Lake G., Quinn T., Stadel J., Tozzi P., 1999, ApJ, 524, L19

Okamoto T., Habe A., 1999, ApJ, 516, 591

Stoehr F., White S. D. M., Tormen G., Springel V., 2002, MNRAS, 335, L84

Taylor J. E., Babul A., 2003, MNRAS, submitted (astro-ph/0301612)


text:
# Low work function of the (1000) Ca2N surface

## Abstract

Polymer diodes require cathodes that do not corrode the polymer but do have low work function to minimize the electron injection barrier. First-principles calculations demonstrate that the work function of the (1000) surface of the compound Ca2N is half an eV lower than that of the elemental metal Ca (2.35 vs. 2.87 eV). Moreover its reactivity is expected to be smaller. This makes Ca2N an interesting candidate to replace calcium as cathode material for polymer light emitting diode devices. \[PACS: 73.30 +y\]

One of the great challenges for polymer light emitting diodes is the electron injection barrier as well as the performance degradation caused by chemical reactions of the cathode with the polymer. State-of-the-art devices use PPV (poly phenylene vinylene) as electro luminescence material. Often the cathode is made out of calcium, because of its low work function (2.87 eV) and the presumed alignment of its Fermi level with the lowest unoccupied molecular orbital of PPV (electron affinity 2.73-2.8 eV). Biases actually used are much higher than the optical band gap of PPV (2.4 eV) namely in the order of 10 V, which suggests that there is some barrier formation between the cathode and the polymer. This is further confirmed by the observation that the decrease of performance is much less for devices in which the cathode is formed at a small residual oxygen pressure. In such a device some oxidation prevents reaction of the cathode with the polymer.

It would be a major breakthrough when stable, low work function metals are found. Sub-nitrides are fascinating candidates because, as in the case of cesium sub-oxides, it is expected that through quantum confinement their work functions are lower than those of the elemental metals while at the same time ionic bonding reduces reactivity.

The Ca2N crystal and electronic structure (bulk and single slab) are known. It is an ionic compound, built out of slabs of alternating (Ca-N-Ca) hexagonal layers. The interslab distance between Ca layers is 3.81 Å and Ca layers inside a slab are only 2.45 Å apart. This is much smaller than the ordinary fcc Ca (111) layer distance (3.18 Å) and can be attributed to the ionic binding. The band structure shows fully occupied N 2s and N 2p states and a quasi 2D free-electron state in the space between the slabs which further confirms the idea that this is an ionic compound.

In this paper the Ca2N work function ($`\mathrm{\Phi }`$) and surface energy ($`E_\mathrm{S}`$) are determined for both the (0001) and the (1000) surface. An indication of the materials stability is obtained from its binding energy and degree of surface relaxation.

First-principles calculations were carried out based on density functional theory in the local density approximation with generalized gradient corrections. The total energy and molecular dynamics program VASP (Vienna *Ab-initio* Simulation Package) was used which has the projector augmented wave method implemented. Non-linear core corrections were applied for calcium. The unit cells contained 18 and 42 atoms for the (0001) and the (1000) surfaces respectively. The Kohn-Sham orbitals were expanded in plane waves with cutoffs of 37 Ry. $`12121`$ and $`1124`$ Monkhorst-Pack k-point grids respectively were used to sample the Brillouin zones resulting in 74 and 26 k-points respectively in their irreducible parts.

$`\mathrm{\Phi }`$ is defined as the minimum amount of energy it costs to extract an electron from a metal. The fact that it depends on the type of surface, is somewhat counter intuitive, it seems to contradict the conservation of energy. However, the differences in work function are compensated by differences in kinetic energy of the electron at large distances.

In order to determine $`\mathrm{\Phi }`$, two numbers are needed: the maximum energy of an electron inside the material, defined to be the Fermi level ($`E_\text{F}`$), and the minimum energy outside the material, the vacuum potential. Because in a finite slab calculation $`E_\text{F}`$ cannot be accurately determined, this number is first obtained from a bulk calculation. Then for the finite slab the average potential of the middle layers (which *is* an accurate quantity) must be aligned with that of the bulk. In this way the work function for the (0001) surface is determined using 6 slabs of Ca-N-Ca and 19 Å of vacuum. It can be extracted from Fig. 1 and equals 3.43 eV.

Another unit cell was made to find $`\mathrm{\Phi }`$ for the (1000) surface of Ca2N. It contained 14 layers and 20 Å of vacuum. At this surface several bonds are severed and it is necessary to relax the atomic positions. The result is shown in Fig. 2 where the view is along the displacement vector from one slab to the next. The nitrogen atoms at the surface are displaced a little (0.24 Å) inwards, the nitrogens in the second layer a little (0.17 Å) outwards, while the surface calciums tend to move in the direction of the surface nitrogens. This can be understood from an ionic point of view. Nitrogen favors an environment of high electron density while calcium shows the opposite trend. Although the structure has changed very little, the effect of the relaxation on $`\mathrm{\Phi }`$ is substantial (Fig. 3). Before relaxation we find a work function of 2.56 eV, already lower than that of pure calcium, but after relaxation it has even decreased to 2.35 eV. Not only is this comparable to the smallest work function for an element (Cs, 2.14 eV), but also the difference of 1.08 eV with the (0001) surface is larger than that between any two surfaces of tungsten, which is known for its large work function anisotropy. Both the drop in $`\mathrm{\Phi }`$ after relaxation and the large surface-anisotropy can be explained by the Smoluchowski model and *not* by quantum confinement as this is a bulk model that does not say anything about anisotropies and/or relaxation. According to Smoluchowski on the other hand, the more “open” a surface is the more the charge density can be smoothed, and this lowers $`\mathrm{\Phi }`$. However more-open surfaces tend to have higher surface energies and this makes them less stable. For the (0001) and (relaxed) (1000) surface we find $`E_\mathrm{S}`$ is 2.7 and 5.3 eV/nm2 respectively which confirms the trend.

Because in Ref. 10 it is suggested Ca2N can also be made with a larger $`c`$ axis (interslab separation), we examined whether this changes the (1000) work function. After enlarging $`c`$ with 2% and subsequent relaxation of the atoms, the structural changes are small and the trends already indicated are a little more pronounced. The slab thickness however has decreased to almost (+0.5%) its former value. The averaged charge density and local potential are plotted in Fig. 4. Before relaxation $`\mathrm{\Phi }`$ is decreased from 2.35 to 2.24 eV, but relaxation increases it again to 2.35 eV. Again this is in accordance with the Smoluchowski trend because a thicker slab makes the surface more open. We conclude that the work function does not (significantly) change when $`c`$ is enlarged.

Finally the reactivity of Ca2N is briefly discussed. Inspection of the binding energy shows that it is 5.6 eV per formula unit (with respect to half a nitrogen molecule and 2 calcium atoms) for a single slab and 0.6 eV more for the bulk. This gives evidence that the reactivity of Ca2N is smaller than that of calcium, of which the binding energy is just 1.9 eV per atom. It was shown earlier that relaxation of the atomic positions after bonds are cut or $`c`$ is enlarged, does not have a substantial effect on the structure. These facts taken together, give a indication that the reactivity of this sub-nitride is less than that of pure calcium, although it is still air sensitive.

In summary, using first-principles calculations, we have shown that the work function of Ca2N has an anisotropy of more than 1 eV, with a minimum of 2.35 eV (cf. Ca, $`\mathrm{\Phi }`$ = 2.87 eV) for the (1000) surface. Its surface energy (5.3 eV/nm2) however is almost the double of that of the (0001) surface. The low work function does not (significantly) depend on the interslab separation and we argued that this material is not as reactive as calcium. The lower work function and reduced reactivity make Ca2N a promising metal to replace Ca in cathodes of polymer light emitting diodes.

The authors wish to thank Dr. C.M. Fang (TUE) and Prof. Dr. R. Coehoorn (Philips) for helpful discussions. This work was part of the research programme of the Stichting voor Fundamenteel Onderzoek der Materie (FOM) with financial support from the Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO).