Score:0

What are the fastest algorithms that sample from the uniform distribution?

ru flag

Lots of cryptography algorithms rely on pseudorandom number generators. Sometimes, given a plaintext, you need to generate a pseudorandom number from it. What are some fast algorithms that do so?

I've seen one that uses SHA256 and other that uses AES, but I couldn't find any literature about them or some implementation that I can use. They should be fast because processors nowadays have hardware support for them.

on page 8 of this paper: dl.acm.org/doi/10.1145/2808425.2808431 it says

enter image description here

cn flag
The title and body of the question do not seem to match.
ru flag
@Maeher aren't pseudorandom number generators used for sampling from the uniform distribution?
Paul Uszak avatar
cn flag
I think that you're going to have to expand upon _"Sometimes, given a plaintext, you need to generate a pseudorandom number from it."_ A plain text is an unencrypted messaged with semantic content. What's the pseudorandom number for?
ru flag
@PaulUszak on page 8 of this paper: https://dl.acm.org/doi/10.1145/2808425.2808431 it says https://imgur.com/a/NhDoBlu
kodlu avatar
sa flag
please edit your question to make it clear and self contained
cn flag
PRFs are not random sampling. And distributions can be uniform over something, e.g. a certain number of bits or a finite field, there is no general 'uniform distribution'.
cn flag
Hmm, there are 2 close votes, and then a bounty was added (so no one can vote to close anymore). Adding a bounty instead of fixing the problems ... this doesn't make anyone want to help you.
Geoffroy Couteau avatar
cn flag
I should dig a bit to find a pointer, but to my knowledge, the fastest PRNGs out there are based on the AES permutation with a fixed-key schedule. A good starting point might be [this paper](https://eprint.iacr.org/2019/074.pdf)
Score:1
in flag

Converting an arbitrary message into a pseudo random number is essentially computing a cryptographic hash.

So this question seems to be asking what is the fastest secure cryptographic hash?

It is unclear what are the security requirements you have for this hash, some algorithms are very simple and have are not cryptographically secure but still provide useful digest when there is no adversary. e.g CRC can be very fast.

Other algorithms will provide pre-image and second pre image resistance but not collision resistance, e.g MD5 or SHA1

Some algorithms are considered today to be generally secure and provide also collision resistance and are often modeled as a pseudo random function. E.g SHA-3.

Here are some benchmarks comparing cryptographic primitives https://www.cryptopp.com/benchmarks.html And a different comparison(different setup and different metric): https://medium.com/logos-network/benchmarking-hash-and-signature-algorithms-6079735ce05

The latter chose blake2 as the fastest hash function and it is considered secure for any purpose requiring a secure hash function, even though it isn't as widely used the standardized SHA2 or SHA3 families.(Note Blake2 has several variants). enter image description here

The first link has MD5 pretty fast at 6.8 cpu cycles / byte which is very very fast. And still secure for many purposes but some would be uncomfortable using a "Broken" Hash function.

For most puprposes you don't need the fastest hash algorithm, you need a plenty fast enough hash, and a good implementation of anything standard should be fast enough. No one was ever fired for choosing SHA-3.

Score:0
in flag

Warning: I'm a newbie

TL;DR. The fastest pre-shared key encryption algorithm, contains the fastest CSPRNG (it just adds that it XORs input against it). You may want to only modify one such that it ignores the input (e.g. doesn't XOR against the input because we don't want to encrypt).


Assuming you ask about cryptographically secure PRNGs:

  • If you want practically unlimited cycle, then pick fastest pre-shared encryption algorithm. I think it is their fundamental design goal: find fastest seeded CSPRNG, then XOR cleartext against it. After all, perfect secrecy comes when clear text is XORed against some uniformly distributed data (i.e. the one-time pad). Pre-shared encryption algorithm simply aim to generate this pad using a seeded method (seed being the key, and CSPRNG's state being the nonce).

  • If you're OK with a limited cycle, then you need to modify the fastest pre-shared encryption algorithm to make it do less work (e.g. smaller block size).

  • Ignore hashing functions for this purpose, as they are designed to solve a bigger problem: compression, which makes them a lot slower.

    Compression means that input could be much larger than output, yet the hashing function is supposed to make sure that every bit of the input is represented in every bit of the output. This forces the function to work a lot harder to ensure such dependency.

    I even think that, if one could magically use a secure hashing function, to, somehow, walk back to its input, then an $n$ bit string of that hash would beat the best lossy data compression for an $n$ bits output.

    On the other hand, a pre-shared encryption algorithm doesn't face this harder challenge, as output is guaranteed to be at least as large as the input.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.