Specify size of random number to generate

[mds1]

To compute a stealth address for the recipient, the sender must generate a random number. Currently a 32-byte random number is used.

As part of the spec, determine if we should stick with a 32-byte random number or use a different size.

[apbendi]

A 16-byte (or 128 bit) random number should theoretically provide sufficient security, as 128 bit keyspace is considered sufficiently secure for many high stakes usecases, i.e. Bitcoin private keys and seed phrases. That said, I don't feel fully qualified to say for sure that moving from 256 bits to 128 bits is definitely secure.

If we did decrease the size, the gains from a smaller number would primarily be:

1. Smaller payload to put on chain when making an announcement (how much smaller? Does it actually result in gas savings on the EVM, for usage of the param in calldata and event emission, or do we still end up using about the same gas because of EVM peculiarities?)
2. Client side decryption speeds when scanning announcements. The cyphertext would be smaller, so it should be faster. How much does this save? Making this fast is important, since the user has to scan and attempt to decrypt all announcements to find ones for them.
3. Multiplications should be faster because one of the numbers is smaller. This is negligible when generating addresses, since it's done so infrequently, but could be important if calculating the address from the random number is part of the scan and discovery phase.

This leads to another question, which is faster when scanning announcements:

1. Including a prefix in the plaintext, and checking for the presence of that prefix after attempting to decrypt, to see if this was intended for us
2. Decrypting to a number, then doing the multiplication to determine if the address generated from the random number matches.

[seresistvanandras]

Generally speaking, the bit security of ECDSA/ECC with n-bits is considered to be around n/2 due to the Pollard-Rho attack. Therefore, it does not make sense to waste performance and bandwidth to apply larger random numbers than 128 bits, since in that case, the security bottleneck would not be Umbra but Ethereum's applied elliptic-curve cryptography. Even today, after a decade of attacking AES, the best attack against AES-128 requires 2**{126.01} computation, hence AES-128 also provides approximately 128-bit security.

However, since the EVM has a word size of 256 bits, it might be the case that the ciphertext of AES-128 does not give any gas savings when it is logged out in the announcement.

All in all, given that we want a memo to be included in the random number, it would make sense to go with a 256-bit random number, where the first 128 bits is the memo, and the last 128-bits is the actual random number. And then the concatenation of these two parts would be encrypted with either AES or XOR.

[mds1]

given that we want a memo to be included in the random number, it would make sense to go with a 256-bit random number, where the first 128 bits is the memo, and the last 128-bits is the actual random number

Agreed, this is the approach we'll go with