# Tag Info

0

Yes. Assume there is an adversary A that breaks F. We will construct an adversary A' that breaks f. A' runs A in its head, and whenever A makes a query x, A' queries its oracle R on R(x) and R(x-1), and replies with R(x)-R(x-1) to A'. If R is an oracle for a pseudo random function f, then R(x)=f(k,x) and R(x-1)=f(k,x-1), which is consistent with F(k,x). ...

2

Not if the attacker is given enough time to ask for the values $F(k,x)$ for all $2^n$ values of $x$. We have $\Sigma_x F(k,x) = 0$ which is distinguishable from random.

2

In such terms, I suppose you should to find GCD of two numbers Key1 and Key2. It seems that with big probability it will give to you one of the prime number which was generated by compromised generator. Pollards method is very hard, and I doubt, that you can successfully apply it in the case.

3

Do you want DDH/RSA-based PRFs? If so, we have them and I will answer. – xagawa @xagawa Yes, I want that :-) – Dingo13 I list the PRFs based on the number-theoretical assumptions. They are `arithmetic or mathematical function.'' You can use the Feistel network to obtain (S)PRPs from PRFs in theory. From the DDH assumption The Naor-Reingold ...

-1

No. Conceptually , not so strongly close but similar ones that would come closer is $k$-wise Independent Distributions/Functions .

4

The following was originally written as an edit to the question, but I'm going to put it here instead because I think formalizing the schemes might well provide you with enough of a hint for you to solve this question yourself: Let $f(k,m)$ be a pseudo-random function, taking as inputs a key and a message, and outputing a value of the same length as the ...

Top 50 recent answers are included