topN using a heap

[Ivan Kazmenko via Digitalmars-d]

On Tuesday, 19 January 2016 at 13:52:08 UTC, Andrei Alexandrescu 
wrote:
> On 01/18/2016 09:21 PM, Ivan Kazmenko wrote:
> Do you think sort and topN would be attackable if they used a 
> per-process-seeded RNG as per Xinok's idea? -- Andrei

Yes, but with a little interactivity (not generating the input in 
advance) and more labor (finding the state of RNG).

Suppose the adversary has the means to generate an input for 
sort/topN, inspect the output, and then generate a bad input.  
With the current (not-secure) RNGs, from the first two actions, 
they can learn the current state of RNG: with sort, the order of 
elements which compare as equal depends on the choice of pivot, 
and therefore exposes the random bits involved; with topN, the 
order of everything except what topN guarantees does the same 
thing.

After that, generating a bad input is definitely possible, since 
everything is known and deterministic at this point.  The 
previously discussed method can be used, or something more clever 
if they want to make it fast.

Ivan Kazmenko.