Article

Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols

Authors:

Berry SchoenmakersAuthors Info & Claims

CRYPTO '94: Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology

Pages 174 - 187

Published: 21 August 1994 Publication History

Abstract

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 some subset of n problem instances out of a collection of subsets denned by 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 axe independently generated, we get a witness hiding protocol, even if 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 P and communication complexity n times that of P . Our results use no unproven complexity assumptions.

References

[1]

J. Benaloh and J. Leichter: Generalized Secret Sharing and Monotone Functions , Proc. of Crypto 88, Springer Verlag LNCS series, 25-35.

[2]

D. Chaum and E. van Heyst: Group Signatures , Proc. of EuroCrypt 91, Springer Verlag LNCS series.

[3]

I. Damgård: Interactive Hashing can Simplify Zero-Knowledge Protocol Design Without Complexity Assumptions , Proc. of Crypto 93, Springer Verlag LNCS series.

[4]

U. Feige and A. Shamir: Witness Indistinguishable and Witness Hiding Protocols , Proc. of STOC 90.

[5]

U. Feige, A. Fiat and A. Shamir: Zero-Knowledge Proofs of Identity , Journal of Cryptology 1 (1988) 77-94.

[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.

[7]

S. Goldwasser, S. Micali and C. Rackoff: The Knowledge Complexity of Interactive Proof Systems , SIAM Journal on Computing 18 (1989) 186-208.

[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.

[9]

M. Ito, A. Saito, and T. Nishizeki: Secret Sharing Scheme Realizing any Access Structure , Proc. Glob. Com. (1987).

[10]

T. Pedersen: A Threshold Cryptosystem without a Trusted Third Party , Proc. of EuroCrypt 91.

[11]

A. De Santis, G. Di Crescenzo and G. Persiano: Secret Sharing and Perfect Zero-Knowledge , Proc. of Crypto 93, Springer Verlag LNCS series.

[12]

A. De Santis, G. Persiano, M. Yung: Formulae over Random Self-Reducible Languages: The Extended Power of Perfect Zero-Knowledge , manuscript.

[13]

C.P. Schnorr: Efficient Signature Generation by Smart Cards , Journal of Cryptology 4 (1991) 161-174.

[14]

A. Shamir: How to Share a Secret , Communications of the ACM 22 (1979) 612-613.

[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.

Cited By

AlTawy RGalal HYoussef A(2023)Mjolnir: Breaking the Glass in a Publicly Verifiable Yet Private MannerIEEE Transactions on Network and Service Management10.1109/TNSM.2023.324450620:3(2942-2956)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1109/TNSM.2023.3244506
Fouque PGeorgescu AQian CRoux-Langlois AWen W(2023)A Generic Transform from Multi-round Interactive Proof to NIZKPublic-Key Cryptography – PKC 202310.1007/978-3-031-31371-4_16(461-481)Online publication date: 7-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-31371-4_16
Ciampi MParisella RVenturi D(2020)On Adaptive Security of Delayed-Input Sigma Protocols and Fiat-Shamir NIZKsSecurity and Cryptography for Networks10.1007/978-3-030-57990-6_33(670-690)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-57990-6_33
Show More Cited By

Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols

Recommendations

Zero-knowledge proofs of knowledge without interaction
SFCS '92: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science

A zero-knowledge proof system of knowledge is a protocol between two parties called the prover and the verifier. The prover wants to convince the verifier that he 'knows' the proof of a given theorem without revealing any additional information. This is ...
Efficient Constructions of Composable Commitments and Zero-Knowledge Proofs
CRYPTO 2008: Proceedings of the 28th Annual conference on Cryptology: Advances in Cryptology
Canetti et al. [7] recently proposed a new framework - termed Generalized Universal Composability (GUC) - for properly analyzing concurrent execution of cryptographic protocols in the presence of a global setup, and constructed the first known GUC-...
Witness-Authenticated Key Exchange

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CRYPTO '94: Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology

August 1994

438 pages

ISBN:3540583335

Editor:
Yvo Desmedt

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 21 August 1994

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

296
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

AlTawy RGalal HYoussef A(2023)Mjolnir: Breaking the Glass in a Publicly Verifiable Yet Private MannerIEEE Transactions on Network and Service Management10.1109/TNSM.2023.324450620:3(2942-2956)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1109/TNSM.2023.3244506
Fouque PGeorgescu AQian CRoux-Langlois AWen W(2023)A Generic Transform from Multi-round Interactive Proof to NIZKPublic-Key Cryptography – PKC 202310.1007/978-3-031-31371-4_16(461-481)Online publication date: 7-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-31371-4_16
Ciampi MParisella RVenturi D(2020)On Adaptive Security of Delayed-Input Sigma Protocols and Fiat-Shamir NIZKsSecurity and Cryptography for Networks10.1007/978-3-030-57990-6_33(670-690)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-57990-6_33
Pass R(2020)Unprovability of Leakage-Resilient Cryptography Beyond the Information-Theoretic LimitSecurity and Cryptography for Networks10.1007/978-3-030-57990-6_31(621-642)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-57990-6_31
Couteau GHartmann D(2020)Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic LanguagesAdvances in Cryptology – CRYPTO 202010.1007/978-3-030-56877-1_27(768-798)Online publication date: 17-Aug-2020
https://dl.acm.org/doi/10.1007/978-3-030-56877-1_27
Attema TCramer R(2020)Compressed -Protocol Theory and Practical Application to Plug & Play Secure AlgorithmicsAdvances in Cryptology – CRYPTO 202010.1007/978-3-030-56877-1_18(513-543)Online publication date: 17-Aug-2020
https://dl.acm.org/doi/10.1007/978-3-030-56877-1_18
Badrinarayanan SFernando RJain AKhurana DSahai A(2020)Statistical ZAP ArgumentsAdvances in Cryptology – EUROCRYPT 202010.1007/978-3-030-45727-3_22(642-667)Online publication date: 10-May-2020
https://dl.acm.org/doi/10.1007/978-3-030-45727-3_22
Heath DKolesnikov V(2020)Stacked Garbling for Disjunctive Zero-Knowledge ProofsAdvances in Cryptology – EUROCRYPT 202010.1007/978-3-030-45727-3_19(569-598)Online publication date: 10-May-2020
https://dl.acm.org/doi/10.1007/978-3-030-45727-3_19
Abe MAmbrona MOhkubo M(2020)On Black-Box Extensions of Non-interactive Zero-Knowledge Arguments, and Signatures Directly from Simulation SoundnessPublic-Key Cryptography – PKC 202010.1007/978-3-030-45374-9_19(558-589)Online publication date: 4-May-2020
https://dl.acm.org/doi/10.1007/978-3-030-45374-9_19
Derler DSamelin KSlamanig D(2020)Bringing Order to Chaos: The Case of Collision-Resistant Chameleon-HashesPublic-Key Cryptography – PKC 202010.1007/978-3-030-45374-9_16(462-492)Online publication date: 4-May-2020
https://dl.acm.org/doi/10.1007/978-3-030-45374-9_16
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents