Article

Compressing Cryptographic Resources

Authors:

Yuval IshaiAuthors Info & Claims

CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology

Pages 591 - 608

Published: 15 August 1999 Publication History

Abstract

A private-key cryptosystem may be viewed as a means by which a trusted dealer privately conveys a large, shared pseudo-random object to a pair of players, using little communication. Alternatively, the messages distributed by the dealer may be viewed as a secure compression of a pair of large identical random pads (or random functions) into a shorter shared "key" or "seed".

We pose the question of extending this compression problem to more general correlation patterns among several players. Unlike the simple case of identical pads, where the main security concern is with respect to external eavesdroppers, in the case of general correlations participants also have to be protected from each other. That is, collusions of computationally-bounded players should gain no additional knowledge about the joint pads of the remaining players from the compressed messages they receive, other than what follows from the pads they generate and from knowing the joint distribution of all pads. While this ideal requirement is inherently impossible to meet using little communication, it turns out that it can be approximated to a satisfactory level, allowing to securely use such compressed correlated pads in a wide class of protocols. We propose a simple and modular replication-based approach for securely compressing any linear correlation pattern, using pseudo-random generators or pseudo-random functions in a black-box manner. Applications include amortizing the communication costs of private multiparty computation and proactive secret-sharing of large secrets.

References

[1]

D. Beaver. Foundations of secure interactive computing. In Proceedings of CRYPTO, 1991.

[2]

D. Beaver. Correlated pseudorandomness and the complexity of private computation. In Proc. of 28th STOC, pages 479-488, 1996.

[3]

D. Beaver. Commodity-based cryptography. In Proc. of 29th STOC, pages 446- 455, 1997.

[4]

D. Beaver and A. Wool. Quorum-based secure multi-party computation. In Proc. of EUROCRYPT'98, LNCS 1403, Springer Verlag, pages 375-390, 1998.

[5]

M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for noncryptographic fault-tolerant distributed computation. In Proc. of 20th STOC, pages 1-10, 1988.

[6]

M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing, 13(4):850-864, 1984.

[7]

B. Bollobás. Graph Theory. Springer-Verlag, 1979.

[8]

R. Canetti. Security and composition of multi-party cryptographic protocols. Theory of Cryptography Library, Record 98-18, 1998.

[9]

D. Chaum, C. CrÉpeau, and I. Damgård. Multiparty unconditionally secure protocols (extended abstract). In Proc. of 20th STOC, pages 11-19, 1988.

[10]

B. Chor and E. Kushilevitz. A communication-privacy tradeoff for modular addition. Information Processing Letters, 45(4):205-210, March 1993.

[11]

S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing contracts. Comm. of ACM, 28:637-647, 1985.

[12]

O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. JACM, 33(4):792-807, October 1986.

[13]

A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung. Proactive secret sharing or: How to cope with perpetual leakage. In Proceedings of CRYPTO, 1995.

[14]

M. Hirt and U. Maurer. Complete characterization of adversaries tolerable in secure multi-party computation (extended abstract). In Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, pages 25-34, 1997.

[15]

Y. Ishai and E. Kushilevitz. Improved upper bound on information theoretic private information retrieval. In Proc. of 31th STOC, 1999.

[16]

M. Ito, A. Saito, and T. Nishizeki. Secret sharing schemes realizing general access structures. In Proc. IEEE Global Telecommunication Conf., Globecom 87, pages 99-102, 1987.

[17]

H. Krawczyk. Secret sharing made short. In Proceedings of CRYPTO, 1994.

[18]

M. Luby. Pseudorandomness and Cryptographic Applications. Princeton University Press, 1996.

[19]

F.J. Macwilliams and N.J. Sloane. The theory of error correcting codes. North Holland, 1978.

[20]

S. Micali and P. Rogaway. Secure computation. In Proceedings of CRYPTO, 1991.

[21]

S. Micali and R. Sidney. A simple method for generating and sharing pseudo-random functions with applications to clipper-like key escrow systems. In Advances in Cryptology - CRYPTO '95, pages 185-196, 1995.

[22]

M. Naor, B. Pinkas, and O. Reingold. Distributed pseudo-random functions and KDCs. In Proc. of EUROCRYPT'99, LNCS 1592, Springer Verlag, pages 327-346, 1999.

[23]

R. Ostrovsky and V. Shoup. Private information storage. In Proc. of the 29th Annu. ACM Symp. on the Theory of Computing, pages 294-303, 1997.

[24]

R. Ostrovsky and M. Yung. How to withstand mobile virus attacks. In Proc. 10th ACM Symp. on Principles of Distributed Computation, pages 51-61, 1991.

[25]

M. O. Rabin. How to exchange secrets by oblivious transfer. Technical Report TR-81, Harvard Aiken Computation Laboratory, 1981.

[26]

T. Rabin. A simplified approach to threshold and proactive RSA. In Proceedings of CRYPTO, 1998.

[27]

A. Shamir. How to share a secret. Commun. ACM, 22(6):612-613, June 1979.

[28]

A. C. Yao. Theory and application of trapdoor functions. In Proc. of the 23th Annu. IEEE Symp. on Foundations of Computer Science, pages 80-91, 1982.

Cited By

Boyle ECouteau GGilboa NIshai YLie DMannan MBackes MWang X(2018)Compressing Vector OLEProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security10.1145/3243734.3243868(896-912)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.1145/3243734.3243868
Beimel AIshai YKushilevitz E(2005)General constructions for information-theoretic private information retrievalJournal of Computer and System Sciences10.1016/j.jcss.2005.03.00271:2(213-247)Online publication date: 1-Aug-2005
https://dl.acm.org/doi/10.1016/j.jcss.2005.03.002
Cramer RDamgård IIshai Y(2005)Share conversion, pseudorandom secret-sharing and applications to secure computationProceedings of the Second international conference on Theory of Cryptography10.1007/978-3-540-30576-7_19(342-362)Online publication date: 10-Feb-2005
https://dl.acm.org/doi/10.1007/978-3-540-30576-7_19
Show More Cited By

Recommendations

Stateless Cryptographic Protocols
FOCS '11: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science

Secure computation protocols inherently involve multiple rounds of interaction among the parties where, typically a party has to keep a state about what has happened in the protocol so far and then \emph{wait} for the other party to respond. We study if ...
Resource Fairness and Composability of Cryptographic Protocols

We introduce the notion of resource-fair protocols. Informally, this property states that if one party learns the output of the protocol, then so can all other parties, as long as they expend roughly the same amount of resources. As opposed to ...
Cryptographic protocol design concept with genetic algorithms
KES'05: Proceedings of the 9th international conference on Knowledge-Based Intelligent Information and Engineering Systems - Volume Part II

This paper describes design concepts of genetic algorithms in the cryptographic protocols for a fault-tolerant agent replication system. The principles of cryptographic protocols are outlined, followed by the specification of modal logic that is used to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology

August 1999

638 pages

ISBN:3540663479

Editor:
Michael J. Wiener

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 15 August 1999

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Boyle ECouteau GGilboa NIshai YLie DMannan MBackes MWang X(2018)Compressing Vector OLEProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security10.1145/3243734.3243868(896-912)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.1145/3243734.3243868
Beimel AIshai YKushilevitz E(2005)General constructions for information-theoretic private information retrievalJournal of Computer and System Sciences10.1016/j.jcss.2005.03.00271:2(213-247)Online publication date: 1-Aug-2005
https://dl.acm.org/doi/10.1016/j.jcss.2005.03.002
Cramer RDamgård IIshai Y(2005)Share conversion, pseudorandom secret-sharing and applications to secure computationProceedings of the Second international conference on Theory of Cryptography10.1007/978-3-540-30576-7_19(342-362)Online publication date: 10-Feb-2005
https://dl.acm.org/doi/10.1007/978-3-540-30576-7_19
Damgård IIshai Y(2005)Constant-round multiparty computation using a black-box pseudorandom generatorProceedings of the 25th annual international conference on Advances in Cryptology10.1007/11535218_23(378-394)Online publication date: 14-Aug-2005
https://dl.acm.org/doi/10.1007/11535218_23

View Options

View options

Get Access

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