AES for Monte-Carlo

In finance, and also in science, the Mersenne-Twister is the de-factor pseudo-random number generator (PRNG) for Monte-Carlo simulations. By the way, there is a recent 64-bit maximally equidistributed version called MEMT19937 with 53-bit double precision floating point numbers in mind.

D.E. Shaw paper Parallel Random Numbers: As easy as 1, 2, 3 makes a bold remark: since specific AES instructions have been available since 2010 in most x86 processors, why not use them?

Historicaly, counter-based PRNGs based on cryptographic standards such as AES were historically slow, which motivated the development of sequential PRNGs with good statistical properties, yet not cryptographically strong like the Mersenne Twister for Monte-Carlo simulations.

The randomness of AES is of vital importance to its security making the use of the AES128 encryption algorithm as PRNG sound (see Hellekalek & Wegenkittl paper). Furthermore, D.E. Shaw study shows that AES can be faster than Mersenne-Twister. In my own simple implementation using the standard library of the Go language, it was around twice slower than Mersenne-Twister to generate random double precision floats, which can result in a 5% performance loss for a local volatility simulation. The relative slowness could be explained by the type of processor used, but it is still competitive for Monte-Carlo use.

The code is extremely simple, with many possible variations around the same idea. Here is mine

type AES2RNG struct {
	counter uint64
	bs      []byte
	block   cipher.Block
}

func New2() (*AES2RNG, error) {
	bs := make([]byte, aes.BlockSize)
	counter := uint64(0)
	key := []byte("AES128_16charkey") //16 bytes
	block, err := aes.NewCipher(key)
	if err != nil {
		return nil, err
	}
	return &AES2RNG{counter, bs, block}, nil
}

func (u *AES2RNG) Uint64() uint64 {
	if u.counter&0x1 == 0 {
		binary.LittleEndian.PutUint64(u.bs, u.counter)
		u.counter++
		binary.LittleEndian.PutUint64(u.bs[8:], u.counter)
		u.block.Encrypt(u.bs, u.bs)
		return binary.LittleEndian.Uint64(u.bs)
	}
	u.counter++
	return binary.LittleEndian.Uint64(u.bs[8:])
}

func (u *AES2RNG) Float64OO() float64 {
	return (float64(u.Uint64()>>12) + 0.5) * (1.0 / 4503599627370496.0)
}

Interestingly, the above code was 40% faster with Go 1.7 compared to Go 1.6, which resulted in a local vol Monte-Carlo simulation performance improvement of around 10%.

The stream cipher Salsa20 is another possible candidate to use as counter-based PRNG. The algorithm has been selected as a Phase 3 design in the 2008 eSTREAM project organised by the European Union ECRYPT network, whose goal is to identify new stream ciphers suitable for widespread adoption. It is faster than AES in the absence of specific AES CPU instructions. Our tests run with a straightforward implementation that does not make use of specific AMD64 instructions and show the resulting PRNG to be faster than MRG63k3a and only 5% slower than MEMT19937 for local volatility Monte-Carlo simulations, that is the same speed as the above Go AES PRNG. While it led to sensible results, there does not seem any study yet of its equidistribution properties.

Counter-based PRNGs are parallelizable by nature: if a counter is used as plaintext, we can generate any point in the sequence at no additional cost by just setting the counter to the point position in the sequence, the generator is not sequential. Furthermore, alternate keys can be used to create independent substreams: the strong cryptographic property will guarantee the statistical independence. A PRNG based on AES will allow \(2^{128}\) substreams of period \(2^{128}\).