KSW correctness for PBE I would like to understand why some definitions of correctness allow a negligible failure probability. i.e. the probability that decryption reverses encryption is 1 minus a negligibly small amount.

I have noticed in the Katz, Sahai, Waters Predicate based encryption scheme that when defining correctness in the two cases where either the predicate is satisfied when trying to decrypt or when the predicate is not satisfied, there is a small failure probability only in the case when the predicate is not satisfied (I have attached an image of this).

Katz, Sahai, Waters correctness of PBE

What is the reason for the negligible probability of failure in the second case?

  • 1
    $\begingroup$ This seems to be a duplicate of this question, presumably by the same user. $\endgroup$ – Maeher Feb 20 '18 at 9:51

This condition is here just because it is the one that appears in the proof.

Usually, decryption will output $\bot$ if some relation is not satisfied. However, there is a non zero probability that the relation is satisfied even when it is not supposed to (it can be some weird case where the secret key is all zeros for example).

In practice, this doesn't matter since an event with negligible probability will never occur.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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