Is F(F(s,x), x) necessarily a PRF if F is?
Generalized Behrend version for Grothendieck-Lefschetz trace formula
Why does the Antonov AN-225 not have any winglets?
What would +1/+2/+3 items be called in game?
Computer name naming convention for security
This LM317 diagram doesn't make any sense to me
Any unique interactions, with an Altmer Dragonborn?
What are the consequences for a developed nation to not accept any refugees?
Is it ok for parents to kiss and romance with each other while their 2- to 8-year-old child watches?
Users forgetting to regenerate PDF before sending it
How do I explain that I don't want to maintain old projects?
Why is the Cauchy Distribution is so useful?
QR codes, do people use them?
How to convert diagonal matrix to rectangular matrix
How do I separate enchants from items?
Can a landlord force all residents to use the landlord's in-house debit card accounts?
Why AI became applicable only after Nvidia's chips were available?
Is there a method for differentiating informative comments from commented out code?
Is it okay to use open source code to do an interview task?
Compressed gas thruster for an orbital launch vehicle?
Need a non-volatile memory IC with near unlimited read/write operations capability
What does the multimeter dial do internally?
What are the effects of abstaining from eating a certain flavor?
No Torah = Revert to Nothingness?
Four ships at the ocean with the same distance
Is F(F(s,x), x) necessarily a PRF if F is?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
Given a PRF - F, is $G_s(x)=F_F_s(x)(x)$ necessarily a PRF?
First I thought how to tackle this problem. First I tried using a hybrid argument:
$|mathbb P[F_F_s(x)(x)] -mathbb P[f(x)]|leq |mathbb P[F_F_s(x)(x)] -mathbb P[F_f(x)(x)]| + |mathbb P[F_f(x)(x)] -mathbb P[f(x)]|$ so I can contradict the possibility that the first part of the is not negligible but the second part of the sum is problematic.
Then I tried to think of counter examples. But it seems to me that because I dont know what the key of F will be if I could break G then I could break F with one single query..
So i'm pretty stuck and would appreciate help.
cryptography pseudo-random-functions
edited Jun 30 at 15:09
xskxzr
4,6123 gold badges11 silver badges36 bronze badges
asked Jun 30 at 6:02
Yuval KirstainYuval Kirstain
184 bronze badges
$endgroup$
add a comment |
$begingroup$
Given a PRF - F, is $G_s(x)=F_F_s(x)(x)$ necessarily a PRF?
First I thought how to tackle this problem. First I tried using a hybrid argument:
$|mathbb P[F_F_s(x)(x)] -mathbb P[f(x)]|leq |mathbb P[F_F_s(x)(x)] -mathbb P[F_f(x)(x)]| + |mathbb P[F_f(x)(x)] -mathbb P[f(x)]|$ so I can contradict the possibility that the first part of the is not negligible but the second part of the sum is problematic.
Then I tried to think of counter examples. But it seems to me that because I dont know what the key of F will be if I could break G then I could break F with one single query..
So i'm pretty stuck and would appreciate help.
cryptography pseudo-random-functions
edited Jun 30 at 15:09
xskxzr
4,6123 gold badges11 silver badges36 bronze badges
asked Jun 30 at 6:02
Yuval KirstainYuval Kirstain
184 bronze badges
$endgroup$
$begingroup$
Can you include your definition of PRF? In particular, is $s$ distributed uniformly or not?
$endgroup$
– Yuval Filmus
Jun 30 at 10:36
$begingroup$
When applying the hybrid argument, there is no reason to use $f(x)$ twice. You can consider two different uniformly random functions instead.
$endgroup$
– Yuval Filmus
Jun 30 at 10:37
add a comment |
$begingroup$
Given a PRF - F, is $G_s(x)=F_F_s(x)(x)$ necessarily a PRF?
First I thought how to tackle this problem. First I tried using a hybrid argument:
$|mathbb P[F_F_s(x)(x)] -mathbb P[f(x)]|leq |mathbb P[F_F_s(x)(x)] -mathbb P[F_f(x)(x)]| + |mathbb P[F_f(x)(x)] -mathbb P[f(x)]|$ so I can contradict the possibility that the first part of the is not negligible but the second part of the sum is problematic.
Then I tried to think of counter examples. But it seems to me that because I dont know what the key of F will be if I could break G then I could break F with one single query..
So i'm pretty stuck and would appreciate help.
cryptography pseudo-random-functions
edited Jun 30 at 15:09
xskxzr
4,6123 gold badges11 silver badges36 bronze badges
asked Jun 30 at 6:02
Yuval KirstainYuval Kirstain
184 bronze badges
$endgroup$
Given a PRF - F, is $G_s(x)=F_F_s(x)(x)$ necessarily a PRF?
First I thought how to tackle this problem. First I tried using a hybrid argument:
$|mathbb P[F_F_s(x)(x)] -mathbb P[f(x)]|leq |mathbb P[F_F_s(x)(x)] -mathbb P[F_f(x)(x)]| + |mathbb P[F_f(x)(x)] -mathbb P[f(x)]|$ so I can contradict the possibility that the first part of the is not negligible but the second part of the sum is problematic.
Then I tried to think of counter examples. But it seems to me that because I dont know what the key of F will be if I could break G then I could break F with one single query..
So i'm pretty stuck and would appreciate help.
cryptography pseudo-random-functions
cryptography pseudo-random-functions
edited Jun 30 at 15:09
xskxzr
4,6123 gold badges11 silver badges36 bronze badges
asked Jun 30 at 6:02
Yuval KirstainYuval Kirstain
184 bronze badges
edited Jun 30 at 15:09
xskxzr
4,6123 gold badges11 silver badges36 bronze badges
asked Jun 30 at 6:02
Yuval KirstainYuval Kirstain
184 bronze badges
edited Jun 30 at 15:09
xskxzr
4,6123 gold badges11 silver badges36 bronze badges
edited Jun 30 at 15:09
xskxzr
4,6123 gold badges11 silver badges36 bronze badges
edited Jun 30 at 15:09
xskxzr
4,6123 gold badges11 silver badges36 bronze badges
4,6123 gold badges11 silver badges36 bronze badges
asked Jun 30 at 6:02
Yuval KirstainYuval Kirstain
184 bronze badges
asked Jun 30 at 6:02
Yuval KirstainYuval Kirstain
184 bronze badges
asked Jun 30 at 6:02
Yuval KirstainYuval Kirstain
184 bronze badges
184 bronze badges
$begingroup$
Can you include your definition of PRF? In particular, is $s$ distributed uniformly or not?
$endgroup$
– Yuval Filmus
Jun 30 at 10:36
$begingroup$
When applying the hybrid argument, there is no reason to use $f(x)$ twice. You can consider two different uniformly random functions instead.
$endgroup$
– Yuval Filmus
Jun 30 at 10:37
add a comment |
$begingroup$
Can you include your definition of PRF? In particular, is $s$ distributed uniformly or not?
$endgroup$
– Yuval Filmus
Jun 30 at 10:36
$begingroup$
When applying the hybrid argument, there is no reason to use $f(x)$ twice. You can consider two different uniformly random functions instead.
$endgroup$
– Yuval Filmus
Jun 30 at 10:37
$begingroup$
Can you include your definition of PRF? In particular, is $s$ distributed uniformly or not?
$endgroup$
– Yuval Filmus
Jun 30 at 10:36
$begingroup$
Can you include your definition of PRF? In particular, is $s$ distributed uniformly or not?
$endgroup$
– Yuval Filmus
Jun 30 at 10:36
$begingroup$
When applying the hybrid argument, there is no reason to use $f(x)$ twice. You can consider two different uniformly random functions instead.
$endgroup$
– Yuval Filmus
Jun 30 at 10:37
$begingroup$
When applying the hybrid argument, there is no reason to use $f(x)$ twice. You can consider two different uniformly random functions instead.
$endgroup$
– Yuval Filmus
Jun 30 at 10:37
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let $mathrmRF_n$ be the set of random functions over $0,1^n$. Let $F_f,i$ be an oracle that answers the first $i$ queries with $F_f(cdot)(cdot)$ and answers the remaining queries with $f(cdot)$. Now suppose a polynomial-time distinguisher $D$ can distinguish $fleftarrow mathrmRF_n:F_f(cdot)(cdot)$ and $fleftarrow mathrmRF_n:f(cdot)$, it can also distinguish $fleftarrow mathrmRF_n:F_f,k-1(cdot)$ and $fleftarrow mathrmRF_n:F_f,k(cdot)$ for some $k$.
Now construct a new distinguisher $D'$. Given an oracle $mathcalO(cdot)$, it selects a random function $f$, then calls $D$. Each time $D$ gives a query $x$ (suppose it is the $i$th query), $D'$ returns
$F_f(x)(x)$ if $i<k$, or
$mathcalO(x)$ if $i=k$, or
$f(x)$ if $i>k$.
We can see if $mathcalO$ is $fleftarrow mathrmRF_n:f(cdot)$, the queries $D$ made as well as their answers have the same distribution as the ones when $D$ is facing $fleftarrow mathrmRF_n:F_f,k(cdot)$. If $mathcalO$ is $sleftarrow0,1^n:F_s(cdot)$, the queries $D$ made as well as their answers have the same distribution as the ones when $D$ is facing $fleftarrow mathrmRF_n:F_f,k-1(cdot)$. Since $D$ can distinguish $fleftarrow mathrmRF_n:F_f,k-1(cdot)$ and $fleftarrow mathrmRF_n:F_f,k(cdot)$, our distinguisher $D'$ can distinguish $fleftarrow mathrmRF_n:f(cdot)$ and $sleftarrow0,1^n:F_s$, which contradicts to the fact that $F$ is a PRF.
So $fleftarrow mathrmRF_n:F_f(cdot)(cdot)$ and $fleftarrow mathrmRF_n:f(cdot)$ cannot be distinguished by any polynomial-time distinguisher. Your second part of the sum is negligible.
answered Jun 30 at 14:56
xskxzrxskxzr
4,6123 gold badges11 silver badges36 bronze badges
$endgroup$
$begingroup$
wow thank you ! :)
$endgroup$
– Yuval Kirstain
Jun 30 at 15:41
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f111308%2fis-ffs-x-x-necessarily-a-prf-if-f-is%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let $mathrmRF_n$ be the set of random functions over $0,1^n$. Let $F_f,i$ be an oracle that answers the first $i$ queries with $F_f(cdot)(cdot)$ and answers the remaining queries with $f(cdot)$. Now suppose a polynomial-time distinguisher $D$ can distinguish $fleftarrow mathrmRF_n:F_f(cdot)(cdot)$ and $fleftarrow mathrmRF_n:f(cdot)$, it can also distinguish $fleftarrow mathrmRF_n:F_f,k-1(cdot)$ and $fleftarrow mathrmRF_n:F_f,k(cdot)$ for some $k$.
Now construct a new distinguisher $D'$. Given an oracle $mathcalO(cdot)$, it selects a random function $f$, then calls $D$. Each time $D$ gives a query $x$ (suppose it is the $i$th query), $D'$ returns
$F_f(x)(x)$ if $i<k$, or
$mathcalO(x)$ if $i=k$, or
$f(x)$ if $i>k$.
We can see if $mathcalO$ is $fleftarrow mathrmRF_n:f(cdot)$, the queries $D$ made as well as their answers have the same distribution as the ones when $D$ is facing $fleftarrow mathrmRF_n:F_f,k(cdot)$. If $mathcalO$ is $sleftarrow0,1^n:F_s(cdot)$, the queries $D$ made as well as their answers have the same distribution as the ones when $D$ is facing $fleftarrow mathrmRF_n:F_f,k-1(cdot)$. Since $D$ can distinguish $fleftarrow mathrmRF_n:F_f,k-1(cdot)$ and $fleftarrow mathrmRF_n:F_f,k(cdot)$, our distinguisher $D'$ can distinguish $fleftarrow mathrmRF_n:f(cdot)$ and $sleftarrow0,1^n:F_s$, which contradicts to the fact that $F$ is a PRF.
So $fleftarrow mathrmRF_n:F_f(cdot)(cdot)$ and $fleftarrow mathrmRF_n:f(cdot)$ cannot be distinguished by any polynomial-time distinguisher. Your second part of the sum is negligible.
answered Jun 30 at 14:56
xskxzrxskxzr
4,6123 gold badges11 silver badges36 bronze badges
$endgroup$
$begingroup$
wow thank you ! :)
$endgroup$
– Yuval Kirstain
Jun 30 at 15:41
add a comment |
$begingroup$
Let $mathrmRF_n$ be the set of random functions over $0,1^n$. Let $F_f,i$ be an oracle that answers the first $i$ queries with $F_f(cdot)(cdot)$ and answers the remaining queries with $f(cdot)$. Now suppose a polynomial-time distinguisher $D$ can distinguish $fleftarrow mathrmRF_n:F_f(cdot)(cdot)$ and $fleftarrow mathrmRF_n:f(cdot)$, it can also distinguish $fleftarrow mathrmRF_n:F_f,k-1(cdot)$ and $fleftarrow mathrmRF_n:F_f,k(cdot)$ for some $k$.
Now construct a new distinguisher $D'$. Given an oracle $mathcalO(cdot)$, it selects a random function $f$, then calls $D$. Each time $D$ gives a query $x$ (suppose it is the $i$th query), $D'$ returns
$F_f(x)(x)$ if $i<k$, or
$mathcalO(x)$ if $i=k$, or
$f(x)$ if $i>k$.
We can see if $mathcalO$ is $fleftarrow mathrmRF_n:f(cdot)$, the queries $D$ made as well as their answers have the same distribution as the ones when $D$ is facing $fleftarrow mathrmRF_n:F_f,k(cdot)$. If $mathcalO$ is $sleftarrow0,1^n:F_s(cdot)$, the queries $D$ made as well as their answers have the same distribution as the ones when $D$ is facing $fleftarrow mathrmRF_n:F_f,k-1(cdot)$. Since $D$ can distinguish $fleftarrow mathrmRF_n:F_f,k-1(cdot)$ and $fleftarrow mathrmRF_n:F_f,k(cdot)$, our distinguisher $D'$ can distinguish $fleftarrow mathrmRF_n:f(cdot)$ and $sleftarrow0,1^n:F_s$, which contradicts to the fact that $F$ is a PRF.
So $fleftarrow mathrmRF_n:F_f(cdot)(cdot)$ and $fleftarrow mathrmRF_n:f(cdot)$ cannot be distinguished by any polynomial-time distinguisher. Your second part of the sum is negligible.
answered Jun 30 at 14:56
xskxzrxskxzr
4,6123 gold badges11 silver badges36 bronze badges
$endgroup$
$begingroup$
wow thank you ! :)
$endgroup$
– Yuval Kirstain
Jun 30 at 15:41
add a comment |
$begingroup$
Let $mathrmRF_n$ be the set of random functions over $0,1^n$. Let $F_f,i$ be an oracle that answers the first $i$ queries with $F_f(cdot)(cdot)$ and answers the remaining queries with $f(cdot)$. Now suppose a polynomial-time distinguisher $D$ can distinguish $fleftarrow mathrmRF_n:F_f(cdot)(cdot)$ and $fleftarrow mathrmRF_n:f(cdot)$, it can also distinguish $fleftarrow mathrmRF_n:F_f,k-1(cdot)$ and $fleftarrow mathrmRF_n:F_f,k(cdot)$ for some $k$.
Now construct a new distinguisher $D'$. Given an oracle $mathcalO(cdot)$, it selects a random function $f$, then calls $D$. Each time $D$ gives a query $x$ (suppose it is the $i$th query), $D'$ returns
$F_f(x)(x)$ if $i<k$, or
$mathcalO(x)$ if $i=k$, or
$f(x)$ if $i>k$.
We can see if $mathcalO$ is $fleftarrow mathrmRF_n:f(cdot)$, the queries $D$ made as well as their answers have the same distribution as the ones when $D$ is facing $fleftarrow mathrmRF_n:F_f,k(cdot)$. If $mathcalO$ is $sleftarrow0,1^n:F_s(cdot)$, the queries $D$ made as well as their answers have the same distribution as the ones when $D$ is facing $fleftarrow mathrmRF_n:F_f,k-1(cdot)$. Since $D$ can distinguish $fleftarrow mathrmRF_n:F_f,k-1(cdot)$ and $fleftarrow mathrmRF_n:F_f,k(cdot)$, our distinguisher $D'$ can distinguish $fleftarrow mathrmRF_n:f(cdot)$ and $sleftarrow0,1^n:F_s$, which contradicts to the fact that $F$ is a PRF.
So $fleftarrow mathrmRF_n:F_f(cdot)(cdot)$ and $fleftarrow mathrmRF_n:f(cdot)$ cannot be distinguished by any polynomial-time distinguisher. Your second part of the sum is negligible.
answered Jun 30 at 14:56
xskxzrxskxzr
4,6123 gold badges11 silver badges36 bronze badges
$endgroup$
Let $mathrmRF_n$ be the set of random functions over $0,1^n$. Let $F_f,i$ be an oracle that answers the first $i$ queries with $F_f(cdot)(cdot)$ and answers the remaining queries with $f(cdot)$. Now suppose a polynomial-time distinguisher $D$ can distinguish $fleftarrow mathrmRF_n:F_f(cdot)(cdot)$ and $fleftarrow mathrmRF_n:f(cdot)$, it can also distinguish $fleftarrow mathrmRF_n:F_f,k-1(cdot)$ and $fleftarrow mathrmRF_n:F_f,k(cdot)$ for some $k$.
Now construct a new distinguisher $D'$. Given an oracle $mathcalO(cdot)$, it selects a random function $f$, then calls $D$. Each time $D$ gives a query $x$ (suppose it is the $i$th query), $D'$ returns
$F_f(x)(x)$ if $i<k$, or
$mathcalO(x)$ if $i=k$, or
$f(x)$ if $i>k$.
We can see if $mathcalO$ is $fleftarrow mathrmRF_n:f(cdot)$, the queries $D$ made as well as their answers have the same distribution as the ones when $D$ is facing $fleftarrow mathrmRF_n:F_f,k(cdot)$. If $mathcalO$ is $sleftarrow0,1^n:F_s(cdot)$, the queries $D$ made as well as their answers have the same distribution as the ones when $D$ is facing $fleftarrow mathrmRF_n:F_f,k-1(cdot)$. Since $D$ can distinguish $fleftarrow mathrmRF_n:F_f,k-1(cdot)$ and $fleftarrow mathrmRF_n:F_f,k(cdot)$, our distinguisher $D'$ can distinguish $fleftarrow mathrmRF_n:f(cdot)$ and $sleftarrow0,1^n:F_s$, which contradicts to the fact that $F$ is a PRF.
So $fleftarrow mathrmRF_n:F_f(cdot)(cdot)$ and $fleftarrow mathrmRF_n:f(cdot)$ cannot be distinguished by any polynomial-time distinguisher. Your second part of the sum is negligible.
answered Jun 30 at 14:56
xskxzrxskxzr
4,6123 gold badges11 silver badges36 bronze badges
answered Jun 30 at 14:56
xskxzrxskxzr
4,6123 gold badges11 silver badges36 bronze badges
answered Jun 30 at 14:56
xskxzrxskxzr
4,6123 gold badges11 silver badges36 bronze badges
answered Jun 30 at 14:56
xskxzrxskxzr
4,6123 gold badges11 silver badges36 bronze badges
4,6123 gold badges11 silver badges36 bronze badges
$begingroup$
wow thank you ! :)
$endgroup$
– Yuval Kirstain
Jun 30 at 15:41
add a comment |
$begingroup$
wow thank you ! :)
$endgroup$
– Yuval Kirstain
Jun 30 at 15:41
$begingroup$
wow thank you ! :)
$endgroup$
– Yuval Kirstain
Jun 30 at 15:41
$begingroup$
wow thank you ! :)
$endgroup$
– Yuval Kirstain
Jun 30 at 15:41
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f111308%2fis-ffs-x-x-necessarily-a-prf-if-f-is%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Can you include your definition of PRF? In particular, is $s$ distributed uniformly or not?
$endgroup$
– Yuval Filmus
Jun 30 at 10:36
$begingroup$
When applying the hybrid argument, there is no reason to use $f(x)$ twice. You can consider two different uniformly random functions instead.
$endgroup$
– Yuval Filmus
Jun 30 at 10:37