# Tag Info

1

Your simple approach is not bad, but you might consider these modifications: First, you don't need a PRF, any form of hashed key or a simple hash over the concatenation of a key and the element should be enough. Basically any one-way function over elements and some sort of key should do the trick, and you can optimize for speed. The key is not chosen by ...

2

Theorem. (Barring any errors, which are certainly possible): Let $A$ be any adversary attacking $F$. As long as $A$ makes fewer than $2^n$ queries, there is an adversary $B[A]$ attacking $f$, making at most twice the queries of $A$ and running in (roughly) the same time such that $\mathsf{Adv}^{\mathsf{prf}}_F(A) = \mathsf{Adv}^{\mathsf{prf}}_{f}(B[A]).$ ...

2

I agree with user12400’s answer. Regarding the two issues you pointed out: there are no issues with too many queries; true, the number of queries can not be infinite but this is the way the "game" is played to test whether a PRF is secure, namely the challenger fixes the key $k$ (choosing a single function from the family of functions) and sends to the ...

2

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)$, ...

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