Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
up vote 4 down vote accepted

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

share|improve this answer
So you're saying there's no such notation? – Polynomial May 25 '12 at 9:44
@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. – CodesInChaos May 25 '12 at 9:56
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. – CodesInChaos May 25 '12 at 9:57
@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". – Polynomial May 25 '12 at 10:10

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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