\documentclass[10pt,a4paper]{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{hyperref}
\usepackage{epstopdf}
\usepackage{natbib}
%\begin{CJK}{UTF8}{gkai}
\begin{document}
\title{randomness extractors embedded with physical random number generators}
%\author{Shi Yicheng}
\date{\today}
\maketitle

\section{abstract}

\newpage

\section{drawings}

%figure 1, a flowchart of the process.
\begin{figure}
\includegraphics[trim = 0mm 0mm 0mm 0mm, clip, scale=0.25]{drawings/flowchart.pdf}
\caption{flowchart of the process}
\end{figure}

%figure 2, 63 bit fibonacci type, serial version
\begin{figure}
\includegraphics[trim = 0mm 40mm 0mm 40mm, clip, scale=0.5]{drawings/fibonacci_serial.pdf}
\caption{Example of a Fibonacci-type randomness extractor, serial input/output}
\end{figure}

%figure 3, 63 bit galois type, serial version
\begin{figure}
\includegraphics[trim = 0mm 20mm 0mm 20mm, clip, scale=0.5]{drawings/galois_serial.pdf}
\caption{Example of a Galois-type randomness extractor, serial input/output}
\end{figure}

%figure 4, 63 bit fibonacci type, parallel version
\begin{figure}
\includegraphics[trim = 0mm 30mm 0mm 20mm, clip, scale=0.5]{drawings/fibonacci_parallel.pdf}
\caption{Example of a Fibonacci-type randomness extractor, serial type}
\end{figure}

%figure 5, 63 bit galois type, parallel version
\begin{figure}
\includegraphics[trim = 20mm 10mm 30mm 0mm, clip,angle=270 ,scale=0.55]{drawings/galois_parallel.pdf}
\caption{Example of a Fibonacci-type randomness extractor, serial type}
\end{figure}

\newpage

\section{Invention background}
The present invention is a randomness extraction processes that converts biased random data into unbiased random bits. %which are applicable to communication and encryption processes. 
\subsection{Random number generation}
A range of applications ranging from encryption to numerical modeling require random numbers to be generated at high speed.
In particular, when information security is of concern, the quality of the generated random numbers should have good statistical properties. Ideally, they should possess no bias or correlations. In other words these random numbers should be intrinsically unpredictable.
\\
\\*
Random number generators can be categorized into either pseudo-random number generators or physical random number generators. 
\\*
Pseudo-random number generators are deterministic since they employ complex algorithmic functions to generate their output, thus their output cannot be considered intrinsically random. However, pseudo-random number generators are easy to implement and are often used for computational purposes such as Monte-Carlo Simulations.
\\*
For applications that require a source of high quality random numbers for example cryptographic key generation, a physical random number generator whose output is based on intrinsically unpredictable physical processes is preferable.
%Physical random number should be used for security sensitive cases instead of pseudo-random number generators. Physical random number generators whose output is based on intrinsically unpredictable physical processes are good countermeasures to potential third-party attacks.
\\*
%Different implementations of physical random number generators have been investigated. 
Some typical sources of physical randomness used to generate a source of raw random numbers include the detection of emission from radioactive nuclei, key strokes derived from human input and various types electrical/optical noises. Measurements on sources of physical randomness are often slower than the computation speed of processors, and thus limits the output rate. 
%This physical random process is typically measured repeatedly and the output converted into binary bits. 
\\
\\*
%Typically the unpredictability of physical random number generators are more trusted compare to pseudo-random number generator. 
%However, one drawback of physical random number generators is that they generally have slower output rates. 
\\*
%One fact responsible to the slow output rate is that measurements on physical randomness sources are very often slower than the computation speed of processors, thus limit the output rate.
\\*
The raw random numbers derived from physical sources are also typically biased and cannot be used directly. A post-processing step (also known as randomness extraction) is required to ensure the quality of the output numbers. This post-processing generally involves performing logic operations on the raw random data and will introduce further time delay in the final output stage.  
%cannot be directly treated as good random numbers, as these data usually do not have good statistical properties. 
%need to quote Fig.1 here
\subsection{Randomness extraction}
%Randomness extraction is typically involved in physical random number generators. Raw data generated from measuring physical randomness sources is generally biased and may possess certain correlations. 
%The aim of a randomness extractor is to eliminate these statistical weaknesses and produce an output stream that is indistinguishable from a true random stream.
\\*
From an information-theory point of view, a randomness extractor is a process that converts a statistically weak binary stream into a new stream, with each bit in the output stream possessing one bit of Shannon entropy. The process should be in principle irreversible such that the raw data cannot be recovered from the output.
\\
\\*
One famous example of such an extractor is the so called Von-Neumann extractor. This specific extractor operates by grouping the raw input bit stream into pairs and maps them to individual bits. It has been shown that the Von-Neumann extractor eliminates the bias of the bit stream, but is not effective against correlations. Also, the Von-Neumann extractor is not efficient as the output rate is reduced by more than half of the input rate.
%more intro to the von neumann extractor here? 
\\*
Another typical implementation of a randomness extractor uses a cryptographic hashing function. Such hashing functions are proven to be effective and secure, but the complexity of the hashing functinos slows down the processing speed and increases the implementation difficulty.
%These implementations involves using complex arithmetic functions to process the input raw data, and generate high quality random number output. These methods are generally shown to be effective against almost all kinds of statistical weaknesses, and the output quality is usually satisfactory for information security purposes. 
\\*
%The drawback of using these hashing functions is typically a trade-off between output speed and computational resources. 
A faster output rate generally requires more memory space and faster processing units, thus compact implementations of such algorithms are difficult to realize.
%should I mention linear matrix operations and toeplitz matrix thingys?
\\
\\*
%shift this part below to the actual implementation of LFSR since it has nothing to do with pseudo or other implementations of physical random number generators other than ours
The applicant came to notice, while implementing the randomness extractors, another feature of importance, known as the conservation of entropy.
\\*
\\*
This proposition can be understood as such: Since the randomness extractor is a deterministic function that does not input any additional entropy into the input stream, the entropy of the output stream should be conserved. From an information-theoretic point of view, each bit at the input of the randomness extractor contains less than 1 bit of Shannon entropy. For an ideal randomness extractor we require the output binary stream to possess a Shannon entropy of 1 per bit. One method of conserving entropy is to truncate the length of the output stream.%a bit vague here
\\*
From a cryptographic angle, a shorter output stream requires dropping a certain portion of the output bits, which makes the entire extraction process practically irreversible. Potential attackers are unable to recover the raw random data and hence the security of the system is ensured.
\\*
The applicant observes that implementing such an entropy conversation process improves the output quality of the randomness extractors.
%
\subsection{Prior arts}
Prior arts to be quoted?(saw several other patents did that...)\\*
some possible quotes\\*
US 8219602\\*
US 6581078\\*
US 8364977\\*

\newpage

\section{Summary of the disclosure}

The applicant proposes an %new?%
efficient implementation of a randomness extractor that processes raw random data from a source of physical randomness and produces high quality random numbers at the output.
\\
\\*
The applicant observes that a simple and compact structure commonly known as a Linear Feedback Shift Register (LFSR) is suitable for randomness extraction due to properties such as spectrum whitening and uniformizing the distribution of its output stream.
\\
\\*
The applicant proposes a modification to the LFSR structure such that instead of a deterministic structure %structure or output?%
, the LFSR receives a random serial input from a physical source, performs a series of logic operations and output an extracted random stream. The extracted random stream is at the same time used to update the internal state of the LFSR and prepare for the next round of operation.
\\
\\*
The applicant proposes two different structures of randomness extractors based on the LFSR, namely the serial Fibonacci and serial Galois type.
\\
\\*
The applicant also proposes two %new?% 
additional structures, namely the parallel Fibonacci and Galois type randomness extractors. The two parallel version extractors have much faster output rates compared to their corresponding serial versions, with an acceptable increase in computational resources.
\\
\\*
The applicant employs the entropy conservation process mentioned earlier and applies a bit-dropping step to all the extractors introduced to ensure a shorter output stream and a conserved input/output entropy. The portion of dropped bits is decided by first statistically measuring the entropy of the raw random data, and then truncating the output stream length to match amount of entropy measured. %vague last line, entropy conservation is not a actual theorem..%
\\
\\*
The applicant claims the proposed structure to be a high speed, efficient randomness extraction scheme, and can be implemented in compact and efficient designs. The proposed structures may possibly be implemented in information security systems where the local memory is limited and power consumption is of concern, such as cell-phones, tablets, and other small portable devices.

\newpage

\section{Description of the drawings}
Fig. 1 shows a general flow chart of the random number generation process from a physical randomness source. The process includes a physical randomness source, a measurement/sampling unit, and a randomness extractor unit.
\\*
Fig. 2 shows a more detailed example of the physical randomness generator. The physical randomness source is a measurement of optical noise, and the uniformizing property of the randomness extractor is shown.
\\*
Fig. 3 schematically shows the common structure of a Fibonacci-type Linear Feedback Shift Register.
\\*
Fig. 4 schematically shows the common structure of a Galois-type Linear Feedback Shift Register.
Fig. 5 shows a possible implementation of a serial version, Fibonacci-type randomness extractor
\\*
Fig. 6 shows a possible implementation of a serial version, Galois-type randomness extractor
\\*
Fig. 7 shows a possible implementation of a parallel version, Fibonacci-type randomness extractor
\\*
Fig. 8 shows a possible implementation of a parallel version, Galois-type randomness extractor
\newpage


\section{Description of the invention}
\subsection{Randomness from physical sources}
A physical random number generator (RNG) is based on measurements of a source of physical randomness. Different implementations of physical random number generators have been investigated. Typical sources of physical randomness include radioactive counters, human behaviours(key strokes, mouse movements, etc), electrical/optical noises, etc. A physical randomness source is usually quantum mechanical or chaotic, thus the measurement outcome is  believed to be almost unpredictable. %Typically the output quality of physical random number generators are trusted to be more random compared to pseudo-random number generator due to the intrinsic unpredictability.
\\
\\*
An example of such a randomness source and measuement is shown in Fig.2.
The applicant measures the noise from an optical detector to generate the raw random data. Optical noise is believed to originate from quantum mechanical fluctuations and thus effectively unpredictable. This is advantageous as the measurements can be performed at high speed and the detection unit is compact. %detection or measurement unit
\\
\\*
The outcome of the physical measurement is converted by an analog/digital convertor (ADC) into a binary number of certain bit length, determined by ADC. 
\\*
For a n-bit ADC, there are $2^n$ possible outcomes. The statistically weak raw data from the measurements will be distributed among these possible outcomes with a non-uniform distribution.

\subsection{Shannon entropy of a randomness source}
In this section we introduce the concept of Shannon entropy as an measure of the quality of the randomness source. A higher value of Shannon entropy indicates that the source is more random while a Shannon entropy of zero indicates that the source is perfectly predictable.
%perfectly random is shannon entropy of 1 for one bit
\\
\\*
Before we perform the randomness extraction process, we characterize the amount of entropy of the source of randomness as measured with our n-bit ADC such that one may estimate the amount entropy to be retained later. 
\\
\\*
Each outcome of a measurement with a n-bit ADC can be considered as a random variable X with $2^n$ possible values. The Shannon entropy is defined as for a random variable X as
\\*
$H(X)=-\sum\limits_{x_i}P(X=x_i)\log P(X=x_i)$\\*
where $\sum\limits_{x_i}$ indicates the sum over all possible values of X, and $P(X=x_i)$ is the probability of the variable $X$ with value $x_i$. 
\\*
The probability of each outcome $P(X=x_i)$ can be determined by counting its number of occurances over a large number of measurement outcomes. For a large enough sample size, we this formula is an accurate representation of the Shannon entropy of the source of randomness.
% measurement outcomes and counting the number of occurance of each outcome divided by the t. If the sample size is large enough, the above expression is a statistically estimation of entropy.
\\*
For a n-bit ADC, the value of $H(X)$ is between 0 and n, with 0 being perfectly non-random and n being perfectly random. A perfectly random case corresponds to a uniform distribution among all $2^n$ possibilities.

\subsection{Linear Feedback Shift Register (LFSR)}
A brief introduction of the so called Linear Feedback Shift Register is necessary before introducing the proposed randomness extractors.
\\
\\*
A Linear Feedback Shift Register (LFSR) is an arithmetic structure which consists of a shift register and XOR (Exclusive OR) gates. The shift register is of length n and stores n bits of data at any instant. The length of the shift register is commonly referred as the length of the LFSR. The bit content stored in the shift register at a certain clock cycle is referred as the state of the LFSR within that clock cycle.
\\
\\*
Fig.3 and Fig.4 shows two possible LFSR structures, namely the Fibonacci-type and Galois-type. The LFSR memory cells are labelled with numbers 1 to 63.
\\
\\*
As its name suggests, a LFSR operates by XORing bits inside the shift register with the bit fed to the bottommost cell. %at least 2 bits, bits can be any where in the LFSR, any number of XORs
\\*
The cells in the shift register that take part in the XOR operations are commonly called the LFSR taps.
\\
\\*
Fig.3 is an example of a 63-bit Fibonacci-type LFSR. cells 1 and 2 are chosen as taps. At each clock cycle, the bits stored in cells 1 and 2 are XORed to produce an output bit, which is simultaneously fed back to cell 63 of the shift register. All other bits in the LFSR shift one step upwards in the process. We have chosen here the output to be the XOR of cell 1 and 2.%in general this output can be any bit in the LFSR
\\*
Fig.4 is an example of a 63-bit Galois-type LFSR. cells 1 and 2 are chosen as taps. At each clock cycle, the bit stored in cell 63 is shifted to cell 1. Simultaneously the same bit is XORed with the bit originally stored in cell 1, and its outcome is sent to cell 2. All other bits in the LFSR shift one step downwards in the process. We have chosen here the output to be the bit in cell 63.%in general this output can be any bit in the LFSR
\\*
It is obvious that an LFSR is a deterministic structure. The LFSR state is continually updated at each clock cycle and will eventually it return to its original state at the beginning.
\\*
We note that an LFSR of length n can have a maximum of $2^{n}-1$ possible states. Also, for a LFSR with all bits being zero in the shift register is not considered an operational state since its output will always be zero regardless of length or combination of taps.
%For any LFSR of any length and any combination of taps, the zero state (with all bits being zero in the shift register) is not considered an operational state, since its output will be zero. 
\\
\\*
In general, the taps of an LFSR can be arbitrarily chosen cells. In practice we are interested in certain taps called "maximum period taps" that allow the LFSR (of fixed length) to iterate through all $2^{n}-1$ possible states before repeating itself. This is to avoid repeating patterns in the LFSR output. 
%will the given a LFSR of fixed length, certain sets of taps are of more interest. These are the so called maximum period taps. As the name suggests, some particular sets of taps allow the LFSR to iterate through all the $2^{n}-1$ possible states before repeating itself. 
In the examples in Fig.3 and Fig.4, cells 1 and 2 forms such a set of taps. The example LFSR will go through $2^{63}-1$ different states before repeating outcomes start to occur.
%want to say why we want maximum period length?
\\*
Mathematically, an LFSR can be described by finite Galois field algebra. It can be shown that the solutions for maximimum period taps for both Fibonacci-type and Galois-type LFSRs can be analyzed by such algebra.
%probably need quotes here
\\
\\*
The output binary sequence of a LFSR with maximum period taps possess good statistical properties. The occurances of 0s and 1s are almost identical, as are the two-bit pairs (00,01,10,11) and 3-bit triplets (000,001,010...) and so on. %high quality, truly random numbers
Also, a discrete Fourier transform of the output stream shows a white spectra. Although the stream is deterministic in nature, its repetition period will be sufficiently long even for a moderate length LFSR ($2^{63}-1$ for a 63-bit length LFSR). As such, the output stream of such a LFSR is often used as a pseudo-random number generator.
\\*
However, it should be noted that despite its good statistical properties, such a pseudo-random stream cannot be considered as good random numbers for use in information security as there exist methods to distinguish the pseudo-random stream from a LFSR from a truly random stream.
\\
\\*
The randomness extractor proposed by the applicant can be considered as a combination of a physical randomness source and a LFSR structure. The applicant proposes to utilize the good statistical properties of an LFSR output, and meanwhile also introduces the unpredictablity of a physical randomness source to construct an efficient and reliable randomness extraction scheme.

\subsection{LFSR based randomness extractors}

In this invention, the applicant utilizes the %uniformizing property
statistical properties of the LFSR output, but additionally seeds it with a binary sequence originating from a physical source of randomness to construct a randomness extractor. We describe first the serial version of the Fibonacci type and Galois type randomness extractors and later expand upon them to their corresponding parallel versions which are able to process all the bits in the word provided by the measurement in a single clock step. %Unlike a conventional LFSR, a LFSR based extractor receives an input stream(several streams in parallel case) from measurement of the randomness source, and output a random stream of shorter length depends on the entropy of the source.	
%It should be noted that the parallel version proposed here are not simply achieved by piling up its serial siblings. 

\subsubsection{Serial Fibonacci type randomness extractor}
Fig.5 shows the basic structure of a serial Fibonacci type extractor. The central part is a Fibonacci type 63-bit LFSR, with the its taps chosen to give a maximal period (cells 1 and 2). The extractor has a serial input and output. The length of the LFSR is chosen to be 63 bits because it minimizes the number of tap bits (and hence XOR operations) required. In each clock cycle, the following operations take place:
%CPLD chip input?
\\*
1. One bit is read from the physical RNG to the input.\\*
2. The input bit is XORed with the bits in cells 1 and 2 (labelled tap bits), generating one new bit. The operation can be expressed as: $X_{output}=X_{1} \oplus X_{2} \oplus X_{input}$\\*
3. All bits in the LFSR shift one cell upwards, the vacated bottom cell is occupied by the newly generated bit. The new bit is at the same time sent to output.\\*
\\*
\\
In this example, each measurement outcome from a physical randomness source is a 16-bit number which yields 12 bits of Shannon entropy. We therefore dropped 4 out of the 16 output bits to ensure an entropy of 12 bits per sample in the output stream. The LFSR is inially populated with bits from the input of the physical RNG.
% The bit dropping is interleaved, after 2 bits, one bit is dropped.
\\
\\*
\\*
In general, a longer LFSR adds more complexity to the system but also improves the statistical properties of the output. A LFSR length of $<$ 32 bits significantly reduces the quality of the output random numbers.
\\
\\*
The applicant notes that the structure described is very similar to "scramblers" normally used in telecommunications. However, a scrambler preserves the output word length while in the randomness extractor described above one deliberately drops bits to conserve entropy. %conserve entropy is not a theorem, so..


\subsubsection{Serial Galois type randomness extractor}
Fig.6 shows the basic structure of a serial version, Galois-type extractor. The central part is a Galois type 63-bit LFSR, with its taps chosen to give a maximal period (cells 1 and 2). The extractor has a serial input and output. The length of the LFSR is chosen to be 63 bits because it minimizes the number of tap bits (and hence XOR operations) required. In each clock cycle, the following operations take place:
\\*
1. One bit is read from the physical RNG to the input.\\*
2. The input bit is XORed with the output bit (bit from cell 63) of the LFSR, generating one new bit.\\*
3. All bits in the LFSR shift one cell downwards. The vacated top cell is occupied by the newly generated bit and the bit from cell 63 is sent to the output. The XOR operation can be expressed as: $X_1=X_{input} \oplus X_{63}, X_2=X_1 \oplus X_{63}$\\*
\\*
\\
The Galois-type LFSR is mathematically equivalent to a Fibonacci-type LFSR, both structures can be described by finite Galois field algebra. The applicant notes that the serial Galois-type LFSR extractor presents a significant increase in output bit rate since all the XOR operations simultaneously occur in one clock cycle as compared to at least two clock cycles required in the serial Fibonacci-type LFSR.\\*
\\
%The entropy conservation condition and the LFSR length considerations remains the same as the Fibonacci type.

\subsubsection{Parallel Fibonacci type randomness extractor}
Fig.7 shows the basic structure of a parallel Fibonacci-type extractor. The cells of the shift register are labelled with numbers 1 to 126. The arrows indicate the shift of bits at each clock cycle. To generate an output of 63 bits in parallel, $63 \times 2 = 126$ cells of memory are required. Cells $1 \sim 63$ store the state of the LFSR, and are to be sent to output at the next clock cycle; cells $64 \sim 126$ are used to store the next 63 bits newly generated by the XOR circuit.
\\*
Similar to the serial extractor, the operations in one clock cycle are as following:\\*
1. 63 bits are read from the physical RNG to the input.\\*
2. XOR operations are performed between the input 63 bits and the bits stored in the shift register following the truth table below:\\*

\begin{tabular}{|c|}
\hline
\text{XOR circuit}\\
$X_{64}=X_{1} \oplus X_{2} \oplus X_{\textrm{input}1}$\\
$X_{63}=X_{2} \oplus X_{3} \oplus X_{\textrm{input}2}$\\
\vdots\\
$X_{126}=X_{63} \oplus X_{64} \oplus X_{\textrm{input}63}$\\
\hline
\end{tabular}
\\
\\*
One clock cycle generates 63 new bits by performing a pair of XOR operations in sequence for every new bit. \\*
3. The parallel LFSR shifts. All bits shift 63 cells forward: $64 \to 1$, $65 \to 2$, etc. The bits originally stored in cells $1 \sim 63$ are sent to output; the vacated cells $64 \sim 126$ accommodate the newly generated 63 bits from the XOR circuit.\\*
4. A portion of bits are dropped to conserve entropy.\\* %conserve entropy is not a theorem..

The applicant notes that since all the XOR operations are performed in parallel, the processing speed is 63 times faster than its serial version. This speedup is at a cost of requiring more memory space and more XOR gates. To build a parallel Fibonacci-type extractor using a n-bit LFSR that has k bit parallel output, k must be less or equal to n. The number of memory cells needed is simply $n + k$.\\*
\\
The entropy conservation condition and the LFSR length considerations remains the same.

\subsubsection{Parallel Galois type randomness extractor}
Fig.8 shows the basic structure of a parallel Galois-type extractor. The cells of the shift register are labelled with numbers 1 to 63, 64 to 126 and 64' to 126'. The arrows indicate the shift of bits at each clock cycle. To generate an output of 63 bits in parallel, $63 \times 3 = 189$ memory cells are required. Cells $1 \sim 63$ store the state of the LFSR, and are to be sent to output at next clock cycle; cells $64 \sim 189$ are used to store the 126 bits that will undergo the XOR operations.

Similar to the serial extractor, the operations in one clock cycle are as following:\\*
1. 63 bits are read from the physical RNG to the input.\\*
2. XOR operations are performed between the input 63 bits and the bits stored in the shift register following the truth table below:\\*

\begin{tabular}{|c|c|}
\hline
\text{XOR circuit 1} & \text{XOR circuit 2} \\
 $X_{64'}=X_{1} \oplus X_{\textrm{input}1}$ & $X_{64}=X_{64'} \oplus X_{2}$ \\
 $X_{65'}=X_{2} \oplus X_{\textrm{input}2}$ & $X_{65}=X_{65'} \oplus X_{3}$ \\
 \vdots & \vdots\\
 $X_{126'}=X_{63} \oplus X_{\textrm{input}63}$ & $X_{126}=X_{126'} \oplus X_{64}$ \\
\hline
\end{tabular}
\\
\\*
One clock cycle performs 126 simultaneous XOR operations and generates 63 new bits. % It's worth noting here that all these XOR operations are performed simultaneously in the same clock cycle.\\*
3. The parallel LFSR shifts. All bits shift 63 cells forward: $64' \to 64$, $64 \to 1$, $65' \to 65$, $65 \to 2$, etc. The bits originally stored in cells $1 \sim 63$ are sent to output; the output from XOR circuit 1 occupies cells $64' \sim 126'$; the output from XOR circuit 2 occupies cells $64 \sim 126$\\*
4. A portion of bits are dropped to conserve entropy.\\* %conserve entropy is not a theorem..

The Galois-type parallel extractor will speed up the processing speed at the cost of additional memory space and XOR operations compared to its serial version. To build a parallel Galois-type extractor using a n-bit LFSR that has a k bit parallel output, k must be less or equal to n. The number of memory cells needed would be $n + m \times k$ where m is the number of taps of the chosen LFSR. %The Galois-type parallel extractor presents a slight advantage over the parallel Fibonacci type extractor as it requires the time for one XOR operation less\\*
\\
The entropy conservation condition and the LFSR length considerations remains the same.
\end{document}