Practical proofs of knowledge without relying on theoretical proofs of membership on languages

AbstractFormulations and properties of proving possession of knowledge in interactive protocols are investigated. A four-move protocol for quadratic residuosity is proposed and a new notion of practical soundness is introduced based on its application to a cryptographic identification scheme. The role of cryptographic assumptions in arguments (i.e., computationally convincing proofs) of knowledge is also explored