How to Break Another “Provably Secure” Payment System

At Eurocrypt’ 94, Stefano D’Amiano and Giovanni Di Crescenzo presented a proto- col for untraceable electronic cash based on non-interactive zero-knowledge proofs of knowl- edge with preprocessing. It was supposed to be provably secure given this and a few other general cryptographic tools.We show that this protocol nevertheless does not provide any untraceability and has some further weaknesses. We also break another “provably secure” system proposed by Di Crescenzo at CIAC 94.This is the second case of problems with “provably secure” payment systems. Moreover, yet another system with this name tacitly solves a much weaker problem than the seminal paper by Chaum, Fiat, and Naor and most other “practical” papers in thisfield (de Santis and Persiano, STACS 92). We therefore identify some principal problems with definitions and proofs of such schemes, and sketch better ways to handle them.