\documentclass[10pt,a4paper]{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{hyperref}
\usepackage{epstopdf}
\begin{document}
\title{LFSR based extractor for random number processing}
\author{Shi Yicheng}
\date{\today}
\maketitle
\subsection*{Overview}

%The LFSR(Linear Feedback Shift Register) based randomness extractor was originally designed as an algorithm for randomness extraction of a physical Random Number Generator(RNG). 

Physical random number generators (RNG) \cite{Kanter2009} usually output numbers that are biased and posess correlations between consecutive numbers, and are not considered useful for most cryptographic purposes.
% The source of randomness is a physical process which?
A randomness extractor converts raw random numbers from such a RNG and outputs a number stream that is uncorrelated and bias free. 

%A portion of the output bits are dropped to make sure the process is irreversible as well as to conserve the entropy of the process. 
\begin{figure}[!htb]
	\centering
	%\begin{center}
	\includegraphics[scale=0.2, trim = 0cm 0cm 0cm 0cm, clip = true]{flowchart_edited.pdf}
	\caption{Randomness extraction process. For example, a physical random number generator generates a stream of numbers with a Gaussian distribution (left). The input stream is processed by the extractor to produce an output stream that follows a uniform distribution (right).}
\end{figure}

An example of a real life implementation of a randomness extractor is to use a cryptographic hashing function. Such hashing functions are in general proven to be effective and secure \cite{Kwok2011}, but the complexity of the hashing functions slows down the processing speed and increases the implementation difficulty \cite{Kwok2011}. We propose here a new randomness extractor based on a LFSR (Linear Feedback Shift Register) which has a compact structure simple to implement hardware wise. LFSR -
type constructs are usually used for ciphers but in our case we will abuse it as a randomness extractor. We introduce first the serial extractor and later expand upon it to the parallel version. %with a provision for conserving entropy which improves security. 
\\*

\subsection*{Basic Structure}

Fig 2. shows the basic structure of the serial randomness extractor. The central part is a Fibonacci type LFSR which is essentially a serial XOR operation. One now chooses the desired number of registers in the LFSR which determines the number of clock cycles after which the output bits repeat (given null inputs). In our implementation we input bits from a RNG, and choose the length of the LFSR (63 bits), number and position of the taps to give a maximal period.

%64th bit discarded because 3 taps needed. We expect that even with a perfect random input there is a non-zero probability that the cycle will repeat.  %However, the output bits will repeat after a number of clock cycles depending on the number of bits in the registers. We thus have an  
%To overcome this limitation we modify the LFSR register to have additional number of XOR taps whose positions are chosen to give a maximal period. 

On each clock cycle, the following operations take place:
\\*
1. One bit %(Least significant bit) 
is read from the physical RNG to the input buffer of the LFSR extractor.\\*
2. The input bit is XORed with the bits from the LFSR taps, generating one new bit. The operation can
be expressed as: $X_{output}=X_{1} \oplus X_{2} \oplus X_{input}$\\* where X denotes the random variable and the subscript denotes the LFSR register position.
3. The LFSR shifts, all bits move one position up, the vacated bottom position is occupied by the newly generated bit. The new bit is at the same time sent to the output buffer.\\*
4. A portion of output bits in the buffer are dropped to conserve entropy.\\*

\begin{figure}[!htb]
	\centering
	\begin{center}
	\includegraphics[scale=0.4, trim = 0cm 4cm 0cm 3cm, clip = true]{63bits_scrambler_serial.pdf}
	\caption{Example of a 63-bit, serial-in/out randomness extractor. The input random numbers are grouped in 16-bit words. The addresses of the LFSR registers are labelled from 1 to 63. The LFSR taps are chosen to maximize processing efficiency. }
	\end{center}
\end{figure}
A statistical measurement of the input yields 12.8 bits of Shannon entropy within every 16 bits. We therefore included a final step which drops 4 out of the 16 output bits to conserve entropy. This bit dropping step also renders the process irreversible.
%but not uncrackable if the LFSR register is short enough the number of combinations of taps to make tables for to compare the output bits to is smaller
%position of the 4 bits to be dropped is always the same for every cycle.  The 16 output bits have shannon entropy of 16.
% process becomes irreversible.

The LFSR register is initally populated with bits from the input of the RNG. The exact length of the LFSR is subject to different applications. A longer LFSR will be more suitable if security issues are of concern; a shorter LFSR on the other hand will make the whole processing unit more compact. 

\subsection*{Parallel-Structure Extractor}

The basic structure shown in the last section has a serial input/output. In order to increase the output random bit rate we propose a parallel structure extractor based on the same principle.
  
\begin{figure}[!htb]
	\centering
	\includegraphics[scale=0.4, trim = 0cm 3cm 0cm 3cm, clip = true]{63bits_scrambler.pdf}
	\caption{63 bits parallel extractor. The input is grouped in 63 bits words.}
\end{figure}

Fig 3 shows an example of a 63-bit parallel extractor. The addresses of the shift register are labelled from 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$ registers are needed. Registers $1 \sim 63$ store the state of the LFSR, and are to be sent to output at next clock cycle; registers $64 \sim 126$ are used to store the next 63 bits that are newly generated by the XOR (Exclusive OR) operation.

%Feedback loops are created from cells $1 \sim 64$ to the XOR module, which performs the XOR operations between the feedback bits and the input random bits. To generate 63 scrambled bits in parallel, 63 parallel XOR operations are needed,  
%On each cycle, the extractor takes in 63 bits data generated by the RNG. The bits stored in addresses $1 \sim 64 $ will be read into the XOR module and XORed with the 63 input random bits. The truth table for the XOR module is shown in the figure, which can be interpreted as:

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 buffer of the LFSR register.\\*
2. XOR operations are performed between the input 63 bits and the bits stored in the register. Following the truth table below:\\*

\begin{align*}
X_{64}&=X_{1} \oplus X_{2} \oplus X_{input1},\\
X_{63}&=X_{2} \oplus X_{3} \oplus X_{input2},\\
\vdots\\
X_{126}&=X_{63} \oplus X_{64} \oplus X_{input63}\\
\end{align*}

This step will generate 63 new bits in register addresses 64 to 126. Note here that all these XOR operations are performed in parallel, thus no extra operating time is required compare to the serial extractor.\\* 
3. The parallel LFSR shifts. All bits shift 63 addresses forward: $64 \to 1$, $65 \to 2$, etc. 
Bits originally stored in addresses $1 \sim 63$ are sent to output; the vacated addresses $64 \sim 126$ accommodate the newly generated 63 bits from the XOR operations.\\*
4. A portion of bits are dropped to conserve entropy.\\*

The parallel structured extractor will speed up processing speed at a cost of requiring more memory space and more XOR gates compare to its serial version. To build a parallel extractor using a n-bit LFSR that has k bit parallel output, k must be less or equal to n. The number of registers needed is simply $n + k$.


%Once the XOR operations are done, all bits in the shift register shift one step to right: bits $1 \sim 63$ go to the parallel output, bits $64 \sim 126$ occupies addresses $1 \sim 63$, and addresses $64 \sim 126$ accommodates the 63 newly generated bits from XOR module.
%Fig 1 shows an example of a 63-bit parallel extractor. The addresses of the shift register are labelled in numbers. 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 needed. Cells $1 \sim 63$ store the state of the LFSR, and are to be sent to output at next clock cycle; cells $64 \sim 126$ are used to store the next 63 bits that are newly generated by the XOR(Exclusive OR) module.

%Feedback loops are created from cells $1 \sim 64$ to the XOR module, which performs the XOR operations between the feedback bits and the input random bits. To generate 63 scrambled bits in parallel, 63 parallel XOR operations are needed,  

%On each cycle, the extractor takes in 63 bits data generated by the RNG. The bits stored in addresses $1 \sim 64 $ will be read into the XOR module and XORed with the 63 input random bits. The truth table for the XOR module is shown in the figure, which can be interpreted as:
%\begin{align*}
%X_{64}&=X_{1} \oplus X_{2} \oplus X_{in1},\\
%X_{63}&=X_{2} \oplus X_{3} \oplus X_{in2},\\
%\vdots\\
%X_{126}&=X_{63} \oplus X_{64} \oplus X_{in63}\\
%\end{align*}
%\vspace{-1.2cm}

%Once the XOR operations are done, all bits in the shift register shift one step to right: bits $1 \sim 63$ go to the parallel output, bits $64 \sim 126$ occupies addresses $1 \sim 63$, and addresses $64 \sim 126$ accommodates the 63 newly generated bits from XOR module.

%An attempt has been done using a 128 bit extractor with similar structure to process the random bits generated from a quantum random number generator. Running the randomness test suite has shown no obvious bias and correlations in the output.
\subsection*{Performance}

As a preliminary assessment, the 63-bit parallel extractor was used to process raw bits generated from a physical RNG (homodyne detection of vacuum field fluctuations). The output unbiased stream (50Gb) is sent through a randomness test suite. The processed stream passed the die-Harder tests, no obvious bias and correlations were detected in the output stream (see attached generated report from the test suite). 

\bibliographystyle{plain}
\bibliography{qrng-cit.bib}

\end{document}


%Figure 1 shows the structure of a 63 bit, LFSR based parallel extractor. The entire unit requires 126 cells of memory to store the internal state of the extractor. 