A multi-party cryptographic protocol and a proof of its security are presented. The protocol is based on RSA using a one-way-function.
Its participants are individuals and organizations, which are not assumed to trust each other. The protocol implements a “credential
mechanism”, which is used to transfer personal information about individuals from one organization to another, while allowing
individuals to retain substantial control over such transfers.
It is proved that the privacy of individuals is protected in a way that is optimal against cooperation of all organizations,
even if the organizations have infinite computational resources. We introduce a “formal credential mechanism”, based on an
“ideal RSA cryptosystem”. It allows individuals a chance of successful cheating that is proved to be exponentially small in
the amount of computation required. The new proof techniques used are based on probability theory and number theory and may
be of more general applicability.
This research was supported in part by the Netherlands Organization for the Advancement of Pure Research (Z.W.O.).