Take the 2-minute tour ×
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.

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
add comment

2 Answers 2

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
4  
@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
add comment

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
add comment

Your Answer

 
discard

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.