I was thinking about non-cryptographic hash function and PRNG design involving multiplication. I was wondering if you could use the product of two variables mod a power of two without worrying about one or both operands not being odd.

If one operand is even (or worse, a multiple of a much larger power of two) then you start losing information due to arithmetic overflow.

Use the product of two variables to modify a third, I mean. The transformation needs to be bijective. (And I'm pondering about both operands being variable because making one operand an odd constant works fine. And that's just boring.)

I was wondering if doing something feistel-like but with xnor instead of xor would be enough to cancel out the effect of trailing zeros in the factors of the product. Outside the setting of cryptography maybe some lightweight hack can compensate for that. The higher the trailing bit count, the less likely it would be for it to be the input to the first round of a function.

Anyone know of references concerning the properties of multiplication mod a power of two? (Just relying on Feistel round functions not needing to be invertible is uninteresting. Using more rounds or more-complex rounds is undesirable within the context of competing with non-secure algorithms.)

WHAT IS THIS MATHJAX GARBAGE

$P_n$ works fine but $\tilde P_n$ pushes the $n$ subscript waaaay over to the right out into the white abyss.

i demand a refund

Hi

yo

I am trying to do this problem from K&L: given that $G$ is a PRG, we define $G'(s) = G(0^{|s|}\|s)$. Is $G'$ a PRG?

Well, what's the definition of PRG?

$G$ is a PRG if there is not PPT distinguisher for it.

$\mathcal{A}$ is a PPT distinguisher for $G$, if $|\Pr[\mathcal{A}(G(s)) = 1] - \Pr[\mathcal{A}(r) = 1]| > \texttt{negl}$.

Where s and r are…?

$s$ is drawn uniformly from the domain of $G$, and $r$ from the codomain.

Is 0 || s uniform random?

I suppose not.

Satisfied?

@SqueamishOssifrage I am trying to argue that $G'$ is a PRG, by using a distinguisher for $G'$ to construct one for $G$.

Suppose G_0 is a PRG. Define G(0^n || s) = 0, G(u || s) = G_0(u || s). Is G a PRG?

(Hint: What's the probability that a uniform random string is of the form 0^n || s?)

1/ 2^n, assuming s is of length n.

(actually it doesn't matter how long s is, but that's what I intended, yes)

oh, yes.

I can make a distinguisher for G with advantage of 1/2^n - 1/2^m, not sure why that would be negligible (m is the output length).

Say n is the security parameter and m >= n.

Does that help?

ahh... okay.

The advantage is obviously smaller that 1/2^n.

So, this is not a PPT distinguisher with nonnegligible advantage. Can you either find a PPT distinguisher against G, or prove that any PPT distinguisher against G can be used to make a PPT distinguisher against G_0?

(Remember the hint! Use it with the law of total probability.)

Wait, why is this not a PPT distinguisher with non-negligible advantage?

Your distinguisher has negligible advantage.

> The advantage is obviously smaller that 1/2^n.

If possible let A be a distinguisher for G, then, |Pr[A(G(u||s)) = 1] - Pr[A(r) = 1]| > negl. Now, Pr[A(G(u||s)) = 1] = 1/2^n.Pr[A(0) = 1] + (1-1/2^n)Pr[A(G_0(u||s)) = 1].

Right?

Looks like a good start.

So, we get a distinguisher G_0

If we plug the expression for Pr[A(G(u||s)) = 1] in that inequality, we get |1/2^n(Pr[A(0)=1] - Pr[A(G_0(u||s)) = 1]) + Pr[A(G_0(u||s)) = 1] - Pr[A(r) = 1] | > negl.

By triangle inequality, 1/2^n|Pr[A(0)=1] - Pr[A(G_0(u||s)) = 1]| + |Pr[A(G_0(u||s)) = 1] - Pr[A(r) = 1] | > negl

So, let's say you finish proving that G, as defined in terms of G_0, is nearly as good a PRG as G_0. What about G'? Is there a PPT distinguisher against G' with nonnegligible advantage?

For G, it was much easier because G was taking only one value for 0^n||s. But this G' is could be taking 2^n many values.

OK, lemme put it this way: If we've defined G and G' as above, can you find a simpler way to write G'(s)?

G'(0) = G(0)? I don't see how this helps

Remind me the definition of G' you started with?

G'(s) = G(0^n || s).

G is a PRG.

Now how did we just define G?

(in terms of a PRG G_0)

G(0^n || s) = 0, G(u || s) = G_0(u || s).

*this is a different G.

So, what's G'(s), as we've defined G' and G in this example?

0, identically?

Right.

Soooooooo…does your construction G'(s) := G(0^n || s) make a PRG as long as G is a PRG?

Not necessarily

Or can you find a PRG G for which G' is in fact totally insecure?

> So, let's say you finish proving that G, as defined in terms of G_0, is nearly as good a PRG as G_0. What about G'? Is there a PPT distinguisher against G' with nonnegligible advantage?

@SqueamishOssifrage The G that we constructed does this, right?

Well, is the constant zero bit string distinguishable from a uniform random bit string?

Obviously, yes.

^ regarding this calculation, why is negl - 1/2^n|Pr[A(0)=1] - Pr[A(G_0(u||s)) = 1]| negligible?

Play around with it. Remember that probabilities are bounded in [0,1], and absolute values are nonnegative.

We just need to check that that thing is positive right?

@SqueamishOssifrage I made a tentative definition.

@fgrieu Can you define Lucas groups?

@SqueamishOssifrage I'd use this as a refresher. Will try..