Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols

  • Ronald Cramer
  • Ivan Damgård
  • Berry Schoenmakers
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)


Suppose we are given a proof of knowledge \( \mathcal{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 \( \mathcal{S} \) on n participants. Then under certain assumptions on \( \mathcal{P} \) and \( \mathcal{S} \), we show how to transform \( \mathcal{P} \) into a witness indistinguishable protocol, in which the prover demonstrates knowledge of the solution to some subset of n problem instances out of a collection of subsets defined by \( \mathcal{S} \). 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, we get a witness hiding protocol, even if \( \mathcal{P} \) did not have this property. Our results can be used to efficiently implement general forms of group oriented identification and signatures. Our transformation produces a protocol with the same number of rounds as \( \mathcal{P} \) and communication complexity n times that of \( \mathcal{P} \). Our results use no unproven complexity assumptions.


Access Structure Secret Sharing Scheme Monotone Formula Round Complexity Qualified Subset 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. 1.
    J. Benaloh and J. Leichter: Generalized Secret Sharing and Monotone Functions, Proc. of Crypto 88, Springer Verlag LNCS series, 25–35.Google Scholar
  2. 2.
    D. Chaum and E. van Heyst: Group Signatures, Proc. of EuroCrypt 91, Springer Verlag LNCS series.Google Scholar
  3. 3.
    I. Damgård: Interactive Hashing can Simplify Zero-Knowledge Protocol Design Without Complexity Assumptions, Proc. of Crypto 93, Springer Verlag LNCS series.Google Scholar
  4. 4.
    U. Feige and A. Shamir: Witness Indistinguishable and Witness Hiding Protocols, Proc. of STOC 90.Google Scholar
  5. 5.
    U. Feige, A. Fiat and A. Shamir: Zero-Knowledge Proofs of Identity, Journal of Cryptology 1 (1988) 77–94.zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    M. Abadi, E. Allender, A. Broder, J. Feigenbaum and L. Hemachandra: On Generating Solved Instances of Computational Problems, Proc. of Crypto 88, Springer Verlag LNCS series.Google Scholar
  7. 7.
    S. Goldwasser, S. Micali and C. Rackoff: The Knowledge Complexity of Interactive Proof Systems, SIAM Journal on Computing 18 (1989) 186–208.zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    L. Guillou and J.-J. Quisquater: A Practical Zero-Knowledge Protocol fitted to Security Microprocessor Minimizing both Transmission and Memory, Proc. of EuroCrypt 88, Springer Verlag LNCS series.Google Scholar
  9. 9.
    M. Ito, A. Saito, and T. Nishizeki: Secret Sharing Scheme Realizing any Access Structure, Proc. Glob.Com. (1987).Google Scholar
  10. 10.
    T. Pedersen: A Threshold Cryptosystem without a Trusted Third Party, Proc. of EuroCrypt 91.Google Scholar
  11. 11.
    A. De Santis, G. Di Crescenzo and G. Persiano: Secret Sharing and Perfect Zero-Knowledge, Proc. of Crypto 93, Springer Verlag LNCS series.Google Scholar
  12. 12.
    A. De Santis, G. Persiano, M. Yung: Formulae over Random Self-Reducible Languages: The Extended Power of Perfect Zero-Knowledge, manuscript.Google Scholar
  13. 13.
    C.P. Schnorr: Efficient Signature Generation by Smart Cards, Journal of Cryptology 4 (1991) 161–174.zbMATHCrossRefGoogle Scholar
  14. 14.
    A. Shamir: How to Share a Secret, Communications of the ACM 22 (1979) 612–613.zbMATHCrossRefMathSciNetGoogle Scholar
  15. 15.
    G.J. Simmons, W.A. Jackson and K. Martin: The Geometry of Shared Secret Schemes, Bulletin of the Institute of Combinatorics and its Applications 1 (1991) 71–88.zbMATHMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • Ronald Cramer
    • 1
  • Ivan Damgård
    • 2
  • Berry Schoenmakers
    • 1
  1. 1.CWIDenmark
  2. 2.Aarhus UniversityDenmark

Personalised recommendations