What are you limitations? The problem becomes dramatically easier if you can say that every application that is going to use the system will have access to the same (private) database, or that all sites involved will be able to exchange a secret key beforehand.