Questions tagged [inherently-sequential]

Inherently sequential is In opposition to embarrassingly parallel tasks, the execution of some tasks depends heavily on the results of others. In other words, those tasks are not independent, and thus, cannot be made parallel or concurrent. Furthermore, if we were to try to implement concurrency into those programs, it could cost us more execution time to produce the same results.

Filter by
Sorted by
Tagged with
1
vote
0answers
175 views

How quickly can we compute SHA256?

Disclaimer. I have asked a similar question on Electronics StackExchange: they advised me to try here. The question I am in the process of developing a simple protocol whose security relies on the ...
6
votes
1answer
112 views

Is XOR-and-SUM inherently sequential?

I have been thinking recently about inherently sequential functions. In trying to wrap my head around them, I tried to come to the simplest possible function that looks inherently sequential to me. ...
16
votes
2answers
853 views

Can Grover's algorithm be parallelized?

Grover's algorithm can search an unordered list of length $N$ in time $\sqrt{N}$ on a quantum computer. Applied to cryptography, this means that it can recover n-bit keys and find preimages for n-bit ...
7
votes
1answer
1k views

Are there secure stream ciphers that cannot be parallelized?

Are there any stream ciphers (or a deterministic random number generators, that should work as well I guess?) that cannot be parallelized? For example, if I seed it with a specific value, and then &...