# An unconditional proof of a PRP by restricting adversary run time

I am a Ph.D. student studying CS theory, I made this account for this question.

Recently, I seem to have obtained a proof of existence of a PRP (which is unconditional in the sense that it does not rely on unproven assumptions), but in order for it to work it does require a limitation of the running time of the adversary. That is, in a usual setting, for security parameter $$n$$, the assumption normally goes that the adversary can run in time $$an^c$$ for arbitrary (positive) constants $$a, c$$. So in the case of distinguishing a PRP from a random permutation, they can make $$an^c$$ queries to the oracle.

I have constructed a PRP which I can show no adversary can distinguish from a random permutation, so long as $$c<1$$. That is, if the adversary does not run more than $$an^c$$ oracle queries, where $$a$$ is arbitrary and $$c$$ is less than 1, then I can prove the adversary cannot distinguish the PRP from a random permutation. But as soon as $$c\geq 1$$ all bets are off and the proof does not work.

I realize that this result is quite weak, so I wanted to ask here if this would be worth sharing with my advisor. I do not want to embarress myself by sharing a result like this with my advisor, when it is probably useless and not interesting. But just in case the (theoretical) community would find it interesting, I wanted to check here.

• Welcome to crytto.SE! Regarding embarrassing oneself, my personal opinion is that there are no stupid questions.... Now on the result: In the context of cryptography, afaik, "unconditional security" mainly refers to not making assumptions on the running time of the attack. So, it's unclear to me that your limited running time to $an^c$ qualifies as unconditional? Commented Jun 10, 2022 at 20:07

Many computational models break down when restricted to running times that are $$o(n)$$, as an adversary does not have time to examine their entire input (or write down an output of the same length). its not surprising to me you can show security in this restricted setting. This is to say that I don't immediately suspect you've shown some wrong result (which would be one reason to keep your result to yourself, at least until you are confident regarding the results correctness)

That being said, as you say it likely isn't particularly interesting (we typically assume adversaries have more computational power than honest parties, not less). There are many results you'll run into of this kind (a big part of research compared to homework is that something being interesting is now vital - for homework all that matters is whether it is true).

That all being said, if you can clearly present

1. The technical statement of the result itself, and

2. The limitations of the result

There's no harm discussing it with anyone. If you don't want to talk to your advisor about the result in particular, other natural things to do are

1. Talking to senior PhD students in your program, or

2. Writing up some blog post or something.

Whenever you have "useless" ideas like this, it isn't bad to share then with other people (what if you missed a usecase?). The only caveat is that you should spend more time making sure the precise result/construction is clearer than normal, as people are generally less willing to put in a lot of mental effort to understand results with less clear implications

Its worth mentioning that your idea may be less useless than you initially imagine though. There have been some proposed settings in cryptography where one assumes adversaries have sub-linear bounds (for example big key cryptography, which assumes a sublinear amount of the key itself can leak). I don't see an obvious application for your construction, but its plausible looking into this area might help. Moreover, learning about areas like this can be the benefit of talking about "useless" results.