We present zero-knowledge interactive arguments for proofs of knowledge in which the communications traffic and the amount of computation and storage for the verifier are much smaller than the size of prover's knowledge. In black-box simulation zero-knowledge proofs, it is strongly unlikely that there is an interactive protocol such that the communications traffic is smaller than the size of prover's knowledge. To realize such a protocol, we introduce a few non-standard computational assumptions, which are factoring versions of non-standard assumptions that appeared in [2], [4], [8]. Our zero-knowledge simulator and knowledge extractor for the proposed protocols are both constructed in a way of "non-black-box simulation".
展开▼
