Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Algorithm No One Knows About (2016)

getkerf.wordpress.com

Post reply on HN
Print view View original

191–200 of 200 posts

Re: Algorithm No One Knows About (2016)

#191

Post by ryacko »

svat wrote: post #190
tripzilch wrote: post #182

Earlier quoted context omitted.

Well the main point of the algorithm is that the output is going to be a sequential, increasing list of int64 "cards". Which may be useful for tape drives, but I'm not sure what else. The big point that the author is missing, is that if you drop that requirement, or rather if you require the output to be shuffled, like you'd expect from dealing cards, then there are super easy algorithms. Just pick a random permutati…

How do you pick a random permutation function over 64-bit integers? On a set of N=2^64 integers, there are N! permutations, so you need lg(N!) ≈ NlgN random bits to generate a uniformly random permutation, and thus at least that much time. This is too much: we want a solution in O(K) time and O(1) additional space (in addition to the space for K integers) — something that's Ω(NlgN) is out of the question. Things like…

https://en.wikipedia.org/wiki/Format-preserving_encryption

It is possible.

Re: Algorithm No One Knows About (2016)

#192

Post by svat »

ryacko wrote: post #191
svat wrote: post #190

Earlier quoted context omitted.

How do you pick a random permutation function over 64-bit integers? On a set of N=2^64 integers, there are N! permutations, so you need lg(N!) ≈ NlgN random bits to generate a uniformly random permutation, and thus at least that much time. This is too much: we want a solution in O(K) time and O(1) additional space (in addition to the space for K integers) — something that's Ω(NlgN) is out of the question. Things like…

https://en.wikipedia.org/wiki/Format-preserving_encryption It is possible.

What “format-preserving encryption” gives you is a hard-to-predict (pseudorandom) permutation on the N elements. The resulting permutation is not guaranteed to be uniformly distributed on the space of all N! permutations; it just comes from some large space that's still much smaller than N! (depending on the number of random bits used), and it's hard to predict which member of that space the permutation will be.

It is simply not possible to sample from a uniform distribution on a set S (here, the set of all N! permutations) in time less than lg|S|. Just think about it: whatever your randomized algorithm, if you only flip a coin M times, there are only 2^M possible outputs of your process. If you want every member of S to be achievable, this requires 2^M ≥ |S|, or M ≥ lg|S|.

Re: Algorithm No One Knows About (2016)

#193

Post by ryacko »

svat wrote: post #192
ryacko wrote: post #191

Earlier quoted context omitted.

https://en.wikipedia.org/wiki/Format-preserving_encryption It is possible.

What “format-preserving encryption” gives you is a hard-to-predict (pseudorandom) permutation on the N elements. The resulting permutation is not guaranteed to be uniformly distributed on the space of all N! permutations; it just comes from some large space that's still much smaller than N! (depending on the number of random bits used), and it's hard to predict which member of that space the permutation will be. It i…

As long as N is factorable into primes, it can be done by Feistel encrypting each prime using modular addition.

There are ways to do it with greater coverage of the space between 4 and 2^64, but I would defer to better judgement before doing so.

Re: Algorithm No One Knows About (2016)

#194

Post by svat »

ryacko wrote: post #193
svat wrote: post #192

Earlier quoted context omitted.

What “format-preserving encryption” gives you is a hard-to-predict (pseudorandom) permutation on the N elements. The resulting permutation is not guaranteed to be uniformly distributed on the space of all N! permutations; it just comes from some large space that's still much smaller than N! (depending on the number of random bits used), and it's hard to predict which member of that space the permutation will be. It i…

As long as N is factorable into primes, it can be done by Feistel encrypting each prime using modular addition. There are ways to do it with greater coverage of the space between 4 and 2^64, but I would defer to better judgement before doing so.

Factoring into primes doesn't really affect the lower bound on complexity.

Note that for N=2^64, the number N! is about 10^(10^20.5), i.e. just the number of digits in N! is itself about 3×10^20. The number of bits in N! is itself over 10^89. Every prime number from 1 to 2^64 (over 10^17 primes) is a prime factor of this number N!; if an algorithm is supposed to work with those many primes, it's clearly no longer O(K) as K could be small relative to N.

An algorithm (like one of the proposed encryption schemes) that produces, say, one of 2^1024 permutations may be “good enough for practical purposes” (as 2^1024 is much larger than the number of atoms in the universe), yet as a fraction of the space of all possible permutations, it is dizzyingly insignificant.

Re: Algorithm No One Knows About (2016)

#195

Post by ryacko »

svat wrote: post #194
ryacko wrote: post #193

Earlier quoted context omitted.

As long as N is factorable into primes, it can be done by Feistel encrypting each prime using modular addition. There are ways to do it with greater coverage of the space between 4 and 2^64, but I would defer to better judgement before doing so.

Factoring into primes doesn't really affect the lower bound on complexity. Note that for N=2^64, the number N! is about 10^(10^20.5), i.e. just the number of digits in N! is itself about 3×10^20. The number of bits in N! is itself over 10^89. Every prime number from 1 to 2^64 (over 10^17 primes) is a prime factor of this number N!; if an algorithm is supposed to work with those many primes, it's clearly no longer O(K…

That is correct.

To achieve full coverage of possible permutations, one needs independent keys and innumerable rounds.

Re: Algorithm No One Knows About (2016)

#196

Post by gliese1337 »

tripzilch wrote: post #182
drfuchs wrote: post #47

A bunch of comments here are missing the main point: Unless you have an Exabyte of memory, you can't use any kind of data structure to remember which cards you've already picked among 2^64 of them. The goal here is an algorithm that generates the selected cards, one by one, in order, as if from a coroutine that only uses a tiny, constant amount of memory. So, no arrays, lists, sets, hash tables, bitmaps, etc., even i…

Well the main point of the algorithm is that the output is going to be a sequential, increasing list of int64 "cards". Which may be useful for tape drives, but I'm not sure what else. The big point that the author is missing, is that if you drop that requirement, or rather if you require the output to be shuffled, like you'd expect from dealing cards, then there are super easy algorithms. Just pick a random permutati…

> Which may be useful for tape drives, but I'm not sure what else.

Partitioning large data sets, or accessing any data store where sequential access is more efficient than random access. Tape drives are merely a canonical and previously-common example of such data stores, but such situations do still exist in the modern world, even if they are not as common. I for one was rather happy to see this, as it addresses a problem I have that I did not know that there was already a solution for!

Suppose you have a huge dataset that you cannot load into memory all at once, but you can request samples of via a paging API. You want to sample a random subset of the records in that dataset. Just generating the indices won't do--you need to turn those indices into actual records. Random access imposes too much overhead--even if you can request arbitrary pages, you don't want to have to request each page more than once, and you don't want to have hold previously-requested pages in memory Just In Case you decide to back up and select another record from them later. Ergo, a non-ordered permutation function doesn't give optimal performance.

With ordered sequential sampling, you can request one page at a time, get all the records you will ever need out of that page, then move on to the next page that would contain an index from your sample.

Now, if your sample size is small enough that you can fit the list of card-indices into memory, rather than just streaming the actual selected records off somewhere else for processing (which in my case, it is), then you could achieve equal data-access performance by selecting the head of a random permutation and then sorting it--but as the article mentions, that kills your asymptotic performance for computing the indices, and means you can no longer perform selection on-line, or parallelize the operations of index selection and data retrieval.

Re: Algorithm No One Knows About (2016)

#197

Post by gliese1337 »

thaumasiotes wrote: post #177
the8472 wrote: post #107

Earlier quoted context omitted.

As a sibling comment mentions the constraints given simply don't allow sampling with rejection due to the memory constraints. You get a stream of uniform samples, you're not allowed to store them. But even if you were allowed to store them the algorithm still has an advantage. It doesn't require random access, only sequential reading and skipping. This was made for tapes, but is also useful for cases where it's simpl…

> even if you were allowed to store them the algorithm still has an advantage. It doesn't require random access, only sequential reading and skipping. This was made for tapes, but is also useful for cases where it's simpler or more efficient to stream your data source instead of doing random access. This is a good point, but its evil twin is the point that this algorithm requires you to read the entire data set, ever…

Not necessarily. If you're using it a tape drive, it requires you to scroll through half of the entire tape on average every time, but fast-forwarding a tape is a faster operation than actually reading the entire tape. Other sequential access data store may have similar behavior--i.e., if you are accessing data from a scrolling/paging API that lets you skip ahead and drop pages, but doesn't let you back up without restarting.

Re: Algorithm No One Knows About (2016)

#198

Post by ZephyrP »

tripzilch wrote: post #180
ZephyrP wrote: post #143

Earlier quoted context omitted.

You can draw the cards in a random order by using the output of an accumulator fed to a block cipher as an index. The fixed output size of a block cipher does entail extra work in filtering numbers outside the range you'd like, just as you would with an LFSR. (as a direct power of 2, you could directly use an LFSR or some ECB-mode block ciphers as if it were format-preserving, but that is "coincidence"). You can prod…

Is that code correct? Why do you overwrite `result` every step of the loop if you only use it at the end?

Good eye, `input` should be replaced with `result` when building the subkeys within the loop.

Here's a working implementation:

  function feistel(ctr, lr, ll) {
      let result = ctr;
      for (var i = 0; i

Re: Algorithm No One Knows About (2016)

#199

Post by dahart »

tripzilch wrote: post #186
dahart wrote: post #173

Earlier quoted context omitted.

This is a good way to pick a few 64 bit numbers without duplicates, if 64 bit numbers is what you need. I didn't see any replies to you mention this part, but Vitter's algorithm works on an unknown number of samples. You can pick a 64-bit number uniformly when you know in advance you have exactly 2^64 choices. But how would you pick samples from a stream with equal probability, without knowing how many items are in t…

Incorrect, you do know this number beforehand. The parameter `N` in the code is the upper bound on the number of values, and the parameter `n` is the number of samples.

I don't know which code you mean, but I was referring to Vitter's basic "Algorithm R", which does not depend on knowing the number of samples or an upper bound in advance. https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_R

Re: Algorithm No One Knows About (2016)

#200

Post by [deleted] »

ZephyrP wrote: post #198
tripzilch wrote: post #180

Earlier quoted context omitted.

Is that code correct? Why do you overwrite `result` every step of the loop if you only use it at the end?

Good eye, `input` should be replaced with `result` when building the subkeys within the loop. Here's a working implementation: function feistel(ctr, lr, ll) { let result = ctr; for (var i = 0; i

[deleted]
Post reply on HN