@SEJPM Hmm, must have been the NSA :)

@mikeazo I'm slightly disappointed that I apparently can't star removed messages. :)

@SEJPM Well, there's always en.wikipedia.org/wiki/Index_of_cryptography_articles, but I doubt that would really make a good community ad.

From this paper - "It has been proved that approximate SVP within a quasipolynomial factor is NP-hard under the randomized reduction." So is that, approximating the approximate SVP?

When will we find out if approximating the approximation of approximate SVP is NP-hard (under the randomized reduction, of course)?

Gotta love Computer Science.

I wonder if this is on-topic here or not...

One one hand, it's not really a crypto question -- it could equally well be about any C API that deals with dynamic memory allocation. On the other hand, the API is from a crypto standard.

I'm kind of thinking no... let's see how others feel.

Anyone able to discuss pseudorandom distribution here? The definition on wikipedia's prg theorem page doesn't make sense to me.

@user474632 There seem to be a few quantifiers missing from the introduction there. I'd phrase it something like: A family of distributions $D_n$ is pseudorandom if, for any non-zero polynomial function $p$, there exists an $n_0$ such that $n \ge n_0 \implies | Pr[C(x)=1 | x∈U] − Pr[C(x)=1 | x∈D_n] | ≤ |1/p(n)|$.

...where $x∈D_n$ denotes that $x$ is a random variable (or maybe a sequence of variables?) sampled from the distribution $D_n$ (and should probably be written $x \sim D_n$, to be correct), and $U$ is the uniform distribution.

Yeah, the | Pr[C(x)=1 | x∈U] − Pr[C(x)=1 | x∈D_n] | ≤ |1/p(n)|$ part I've been over already, trying to piece together n>n_0 atm

It's just 'there exists a lower limit for which the following expression is true'?

Yes.

It means that, whatever polynomial we pick for $p$, if we choose $n$ big enough then the following expression holds.

The only change in the latter part is D_n, does it have to be x from a family of distributions or can it be a specific one?

Sorry, I kind of used $D_n$ for two things there. What I meant is that $D_n$ is, for each $n$, a probability distribution -- and the collection $D = \langle D_n \rangle_n$ of these distributions is pseudorandom if it satisfies this property.

I think I'm following then.

Basically, you can think of $n$ as something like the length of the possible keys used to generate the pseudorandom values; the larger the keyspace, the harder it is (or should be) to distinguish the distribution from random.

I know it shouldn't work but my question was if for a given f(x∈U)=(x,b) the latter expression would easily have C(x)>1/p(n)

My notation is probably sloppy but I mean D has a given generator using the uniform distribution to make one bit.

C(x) would just test f(x∈U)==b∈D

And obviously f(x∈U)==b∈U would e random

I'm not sure I follow... $C(x)$ is, by definition, 0 or 1, and $Pr[C(x)=1]$ could be anything between 0 and 1. The hard part is designing a circuit $C$ such that $C(x)=1$ significantly more often when $x$ is sampled from $D_n$ and not from $U$.

Yeah, by the expression C(x)=f(x∈U)==b∈D I mean C(x) would evaluate the equality

(That is, that's the hard part if you're trying to show that $D$ is not pseudorandom; if you're trying to show that it is, then the hard part is showing that there cannot be such a circuit $C$.)

with b∈D being the result of f(x∈U)

Yeah I'm just wondering what I've got wrong. Too specific of a generator or something?

... I'm honestly not really following here. What's $f(x∈U)$?

A generator for the distribution D, or D_n in your notation for which the uniform input is unchanged and the pseudorandom output is only one bit

I know I have something laughably wrong in here, I just can't see it :/

I dunno... maybe you're missing the fact that the attacker (i.e. $C$ in the definition) is not given the seed for the generator?

BTW, to see the $\LaTeX$ markup I'm using properly, see the links in this post on meta.SE.

Or iow I proved the case that the attacker receiving the seed can invert the generator XD

That's what I meant by too specific of a generator.

Yeah, that might well be it.

That still leaves me wondering what the generator for D_n is supposed to look like, but thanks very much for clarifying that!

Well, that's (somewhat) explained in the next section. Basically, the generator takes in a seed of $n$ bits (for some reason, the article switches the index from $n$ to $l$ there) and spits out an output stream of $m > n$ bits.

For which the generator has to scramble the bits from the uniform distribution such that the attacker can't identify the information from the pseudorandom bit..

Simple rearrangements of bit position aren't going to work, so I'm more interested in how that one pseudorandom bit gets scattered across the distribution

Ah, now, well that is the real tricky part. :)

Naturally, or prgs would have been proved already!