1
$\begingroup$

What's the standard way to express "$x$ knows about $y$", or "$x$ has no knowledge of $y$" in cryptographic notation?

Example (PRNG predictor):

$\exists f : P(f(G(k)|_{0..n}) = G(k)|_{n+1}) \geq 0.5 + \epsilon$, for non negligable $\epsilon$, where $f$ has no knowledge of $k$.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

The notation is "", i.e., the empty string. $\;\;$ Since $k$ is not an input of $f$, $f$ has no knowledge of $k$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ So you're saying there's no such notation? $\endgroup$
    – Polynomial
    Commented May 25, 2012 at 9:44
  • 4
    $\begingroup$ @Polynomial He's saying that in your example such a notation is not necessary, because it's implicit in the parameters of $f$. A function by definition only knows what it sees in its parameters. $\endgroup$
    – CodesInChaos
    Commented May 25, 2012 at 9:56
  • $\begingroup$ But your example is problematic, since you did not restrict the cost of calculating $f$. If you make no such restriction, you need entropy exceeding the output size, i.e. a true RNG, and not a PRNG. $\endgroup$
    – CodesInChaos
    Commented May 25, 2012 at 9:57
  • $\begingroup$ @CodeInChaos I was just using it as an example. If I were really writing that in a document, I'd put something like "where $f(x)$ runs in polynomial time or better". $\endgroup$
    – Polynomial
    Commented May 25, 2012 at 10:10
1
$\begingroup$

If you really wanted a symbol for that, I suppose you could borrow a notation from probability theory and write $f \perp k$ for "$f$ is independent of $k$". But that's definitely not standard usage, so you're going to have to define it explicitly.

Improve this answer
$\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.