Proofs of partial knowledge and simplified design of witness hiding protocols

R. Cramer, Ivan Damgard, B. Schoenmakers

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review


    Suppose we are given a proof of knowledge P in which a prover demonstrates that he knows a solution to a given problem instance. Suppose also that we have a secret sharing scheme S on n participants. Then under certain assumptions on P and S, we show how to transform P into a witness indistinguishable protocol, in which the prover demonstrates knowledge of the solution to a subset of n problem instances corresponding to a qualified set of participants. For example, using a threshold scheme, the prover can show that he knows at least d out of n solutions without revealing which d instances are involved. If the instances are independently generated, this can lead to witness hiding protocols, even if P did not have this property. Our transformation produces a protocol with the same number of rounds as P and communication complexity n times that of P. Our results use no unproven complexity assumptions.
    Originele taal-2Engels
    Pagina's (van-tot)111-127
    TijdschriftCWI Quarterly
    Nummer van het tijdschrift2
    StatusGepubliceerd - 1995


    Duik in de onderzoeksthema's van 'Proofs of partial knowledge and simplified design of witness hiding protocols'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit