Pseudorandom functions (PRFs) are the building blocks of symmetric-key cryptography. Almost all central goals of symmetric cryptography (e.g., encryption, authentication, identification) have simple solutions that make efficient use of a PRF. Most existing constructions of these objects are either (a) extremely fast in practice but without provable security guarantees based on hard mathematical problems [AES, Blowfish etc.], or (b) provably secure under assumptions like the hardness of factoring, but extremely inefficient in practice. Lattice-based constructions enjoy strong security guarantees based on natural mathematical problems, are asymptotically and practically efficient, and have thus far even withstood attacks by quantum algorithms. However, most recent lattice-based constructions are of public-key objects, and it's natural to ask whether these advantages can be brought to the world of symmetric-key constructions. In this thesis, we construct asymptotically fast and parallel pseudorandom functions basing their security on a well known hard lattice problem called the learning with errors problem. We provide several types of constructions that have their respective efficiency and security advantages. In addition to this, we also provide improved constructions of key-homomorphic PRFs that achieve almost optimal quasi-linear magnitudes of public parameters, key sizes and incremental run times. We also propose a new cryptographic primitive, constrained key-homomorphic PRFs, provide secure candidate constructions and applications. Lastly, we detail an implementation in software of a candidate PRF and analyze its efficiency and security.

International Telemetering Conference Proceedings / October 29-November 02, 1990 / Riviera Hotel and Convention Center, Las Vegas, Nevada / An innovative digital approach to analog noise synthesis is described. This method can be used to test bit synchronizers and other communications equipment over a wide range of data rates. A generator has been built which has a constant RMS output voltage and a well-defined, closely Gaussian amplitude distribution. Its frequency spectrum is flat within 0.3 dB from dc to an upper limit which can be varied from 1 Hz to over 100 MHz. Both simulation and practical measurement have confirmed that this generator can verify the performance of bit synchronizers with respect to the standard error rate curve.

In this thesis our goal is to study pseudorandom numbers. We  will investigate how to produce pseudorandom samples from the uniform distribution with a method called the linear congruential method. Another method we will look at is the inverse sampling method which gives us the possibility to generate samples from other distributions that are not the uniform distribution. When generating pseudorandom samples quality is an important aspect, therefore we are going to take a look at a discrepancy which is a tool to determine quality of uniformly distributed samples. We implement the methods in Python and perform numerical experiments to test some quality aspects of the output.

We study two deterministic analogues of random walks. The first is the chip-firing game, a single player game played by moving chips around a directed graph, popularised by Björner and Lovász. We find an efficient simulation of boolean circuits and Turing machines using instances of the chip-firing game - after assigning a fixed strategy to the player. The second is the Propp machine, or the rotor router model, a quasirandom model intro- duced by Priezzhev. We improve results of Kijima et al. and show a bound of O(m) on the discrepancy of this process from a random walk on d-regular graphs with m edges. 1

International Telemetering Conference Proceedings / October 21, 2002 / Town & Country Hotel and Conference Center, San Diego, California / It is need to design acquisition and tracking for code loop and carrier loop to detect the high dynamic Global Position System (GPS) signal. Acquiring signal quickly and shortening acquisition time in the cold case are key technology of a high dynamic GPS receiver. Moreover, fast acquisition of C/A code is the base of code tracking and carrier acquisition and tracking. This paper describes elements and implementation of a new parallel-sequential search Algorithm to acquire C/A code of the high dynamic GPS signal. And combined with a 12-channel correlator named GP2021 produced by GEC Co., the arithmetic implementation to acquire C/A code of the high dynamic GPS signal used sequential search based on DSP technology is also given.

<p>This thesis is related to varies statistical test of pseudorandom number generator. In thisthesis I have tried to discuss some aspects of selecting and testing Pseudorandom numbergenerators. The outputs of such generators may be used in many cryptographic applications,such as the generation of key material. After statistical test I have tried to compairethe test value of every generator and have discussed which one is producing good sequencesand which one is a good generator.</p>

Generators of pseudorandom sequences are widely used objects, not in the least place because of their application in stream ciphers. One of the ways to improve resistance to different types of attack is to use compression on the generated sequence in order to remove redundant information, that might lead to an attack against the generator. In this work we try to explore from a wider perspective the theoretical foundations for compressing pseudorandom sequences created thus far. Using this general view we will examine some known attacks against the PRN generators and look for a way to resist such attacks.

Maximum linear feedback shift registers (LFSRs) based on primitive polynomials are commonly used to generate maximum length sequences (m-sequences). An m-sequence is a pseudorandom sequence that exhibits ideal randomness properties like balance, run and autocorrelation but has low linear complexity. One-dimensional Cellular Automata (1D CA) have been used to generate m-sequences and pseudorandom sequences that have high linear complexity and good randomness. This thesis considers the use of two-dimensional Cellular Automata (2D CA) to generate m-sequences and psuedorandom sequences that have high linear complexity and good randomness. The properties of these sequences are compared with those of the corresponding m-sequences and the best sequences generated by 1D CAs. / Graduate

This thesis is related to varies statistical test of pseudorandom number generator. In thisthesis I have tried to discuss some aspects of selecting and testing Pseudorandom numbergenerators. The outputs of such generators may be used in many cryptographic applications,such as the generation of key material. After statistical test I have tried to compairethe test value of every generator and have discussed which one is producing good sequencesand which one is a good generator.

Constructing advanced cryptographic applications often requires the ability of privately embedding messages or functions in the code of a program. As an example, consider the task of building a searchable encryption scheme, which allows the users to search over the encrypted data and learn nothing other than the search result. Such a task is achievable if it is possible to embed the secret key of an encryption scheme into the code of a program that performs the "decrypt-then-search" functionality, and guarantee that the code hides everything except its functionality. This thesis studies two cryptographic primitives that facilitate the capability of hiding secrets in the program of random functions. 1. We first study the notion of a private constrained pseudorandom function (PCPRF). A PCPRF allows the PRF master secret key holder to derive a public constrained key that changes the functionality of the original key without revealing the constraint description. Such a notion closely captures the goal of privately embedding functions in the code of a random function. Our main contribution is in constructing single-key secure PCPRFs for NC^1 circuit constraints based on the learning with errors assumption. Single-key secure PCPRFs were known to support a wide range of cryptographic applications, such as private-key deniable encryption and watermarking. In addition, we build reusable garbled circuits from PCPRFs. 2. We then study how to construct cryptographic hash functions that satisfy strong random oracle-like properties. In particular, we focus on the notion of correlation intractability, which requires that given the description of a function, it should be hard to find an input-output pair that satisfies any sparse relations. Correlation intractability captures the security properties required for, e.g., the soundness of the Fiat-Shamir heuristic, where the Fiat-Shamir transformation is a practical method of building signature schemes from interactive proof protocols. However, correlation intractability was shown to be impossible to achieve for certain length parameters, and was widely considered to be unobtainable. Our contribution is in building correlation intractable functions from various cryptographic assumptions. The security analyses of the constructions use the techniques of secretly embedding constraints in the code of random functions.