1
$\begingroup$

This question may be of no practical interest. But as a meaningful or meaningless question, can we extend the domains of the keyspace, input space and output space of a PRF to be defined over intervals of $\mathbb{R}$?

For instance, let $I := (a,b) \subset \mathbb{R}$ be some interval of $\mathbb{R}$, and $F: I\times I \to I$ be a function that takes a parameter $p\in I$ and an input $x\in I$ and maps it to $y:=F(p, x)$.

Can we still analyse this function $F$ for pseudorandomness and say that $F$ is a PRF, i.e., no adversary can distinguish it from a random function $f: I\to I$ (that must be defined as well if this question is meaningful)?

$\endgroup$

1 Answer 1

3
$\begingroup$

TL;DR: This is impossible to do in any meaningful way for cryptography since the implementation would have to be based on finite sets (keyspace, message space) and thus nullify the utility.

Yes, one can define measure preserving (m.p.) maps on intervals (or equivalently on the circle) and study their distributional and probabilistic properties. Intuitively m.p. means that if the input distribution is uniform then the output after applying such a map $F(p,x)$, conditioned on whatever $p=p_0$ is still uniform.

See:

Random Iterations of Homeomorphisms on the Unit Circle

If you're looking at a single stochastic process (though not on an interval $I$ since it won't be bounded) one classical idea is that of a Wiener Process, basically a continuous time random process which is the integral of a Gaussian white noise random process. The Gaussian distribution has the maximum entropy among all distributions with the same variance, which is attractive. Then you can just project the process onto your interval as you wish, assuming the length of $I$ is one, just take the fractional part of the process (remove the integer part).

Note: This is an abstract idea, and bears some superficial resemblance to the idea of chaotic cryptography which is largely discredited but is used extensively to churn out publications in non-crypto venues. See Explaining Chaotic Cryptography and What is preventing chaotic cryptology from practical use?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.