Article

Free access

Security-preserving hardness-amplification for any regular one-way function

Authors:

Giovanni Di Crescenzo,

Russell ImpagliazzoAuthors Info & Claims

STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of Computing

Pages 169 - 178

https://doi.org/10.1145/301250.301296

Published: 01 May 1999 Publication History

PDF eReader

References

[1]

M. Bellaxe, J. Kilian and P. Rogaway, The Security of Cipher Block Chaining, in Proc. of CRYPTO 94.

Digital Library

Google Scholar

[2]

M. Ben-Or, O. Goldreich, S. Goldwasser, J. Hastad, J. Kilian, S. Micali, and P. Rogaway, Everything Provable is Provable in Zero-Knowledge, in Proc. of CRYPTO 88.

Digital Library

Google Scholar

[3]

M. Blum and S. Micali, How to Generate Cryptographically Stron~ Sequence of Pseudo-Random Bits, SIAM journal on Computing, vol. 13, no. 4, 1984, pp. 850-864.

Digital Library

Google Scholar

[4]

A. De Santis and P. Persiano, Zero-Knowledge Proofs oj~ Knowledge without Interaction, in Proc. of FOCS 92.

Digital Library

Google Scholar

[5]

G. Di Crescenzo, T. Malkin, and R. Ostrovsky, Single Database Private Information Retrieval Implies Oblivious Transfer, manuscript, Nov 1998.

Digital Library

Google Scholar

[6]

W. DitIie and M. Hellman, New Directions in Cryptography, in IEEE Transaction in Information Theory, 22, 1976.

Google Scholar

[7]

O. Goldreich, S. Goldwasser, and S. Micali, How to Construct Random Functions, Journal of ttxe Association for Computing Machinery, vot. 33, no. 4, 1986, pp. 792-807.

Digital Library

Google Scholar

[8]

O. Gotdreich, R. Impagliazzo, L. Levin, R. Venkatesan, and D. Zuckerman, Security- Preserving Amplification o.f Hardness, in Proc. of FOCS 9O.

Digital Library

Google Scholar

[9]

O. Goldreidx, H. Krawczyk and M. Luby, On the Existence o! Pseudorandom Generators, in SIAM Journal on Computing, vol. 22, n. 6, Dic 1993,

Digital Library

Google Scholar

[10]

O. Goldreich and L. Levin, A Hard-Core Predicate .for any One-Way Function, in Proc. of FOCS 9O.

Google Scholar

[11]

O. Goldreich, S. Micali, and A. Wigderson, Proofs that Yield Nothing but their Validity and a Methodology o.f Cryptographic Design, in Proc. of FOCS 86.

Digital Library

Google Scholar

[12]

S. G;oldwasser, S. Micali, and C. Rackoff, The KnowJedge CompJexity o} Interactive Proof- Systems, SIAM Journal on Computing, vol. 18, n. 1, Feb 1989.

Digital Library

Google Scholar

[13]

S. Goldwasser, S. Micali and R. Rivest, A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, in SIAM Journal on Computing, vol. 17, n. 2, Aug 1988.

Digital Library

Google Scholar

[14]

J. Hastad, R. Impagliazzo, L. Levin, and M. Luby, Construction of a Pseudo-Random Generator from any One-Way Function, to appear on SICOMP, previous versions in FOCS 89 and STOC 9O.

Digital Library

Google Scholar

[15]

A. Herzberg and M. Luby, Public Randomness in Cryptography, in Proc. of CRYPTO 92.

Digital Library

Google Scholar

[16]

R. Impagliazzo and S. Rudich, Limits on the Provable Consequences o.f One-Way Permutations, in Proc. of STOC 91.

Digital Library

Google Scholar

[17]

R. Impagliazzo and M. Yung, Direct Minimum Knowledge Computations, in Proc. of CRYPTO 87.

Digital Library

Google Scholar

[18]

L. Levin, One-way Functions and Pseudo- Random Generators, in Combinatorica, vol. 7, n. 4, 1987.

Digital Library

Google Scholar

[19]

M. Luby, Pseudo-Randomness and Cryptographic Applications, Princeton University Press, Princeton, N J, 1996.

Digital Library

Google Scholar

[20]

M. Luby and C. Rackoff, How to Construct a Pseudo-Random Permutation from a Pseudo- Random Function, in SIAM Journal on Computing, vol. 17, n.2, Aug 1988.

Digital Library

Google Scholar

[21]

M. Naor, Bit Commitment using Pseudorandomhess, in Proc. of CRYPTO 91.

Digital Library

Google Scholar

[22]

M. Naor and M. Yung, Universal One-way Hash Functions and their Cryptographic Applications, in Proc. of STOC 89.

Digital Library

Google Scholar

[23]

R. Ostrovsky, and A. Wigderson, One-way Functions are Essential .for Non-Trivial Zero- Knowledge, in Proc. of ISTCS 93.

Google Scholar

[24]

J. Rompel, One-way Functions are Necessary and Sufficient for Secure Signatures, in Proc. of STOC 90.

Digital Library

Google Scholar

[25]

A. Yao, Theory and Applications of Trapdoor Functions, in Proc.of FOCS 82.

Crossref

Google Scholar

Cited By

View all

Hirahara SShimizu NMohar BShinkar IO'Donnell R(2024)Planted Clique Conjectures Are EquivalentProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649751(358-366)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649751
Akavia AGoldreich OGoldwasser SMoshkovitz DKleinberg J(2006)On basing one-way functions on NP-hardnessProceedings of the thirty-eighth annual ACM symposium on Theory of Computing10.1145/1132516.1132614(701-710)Online publication date: 21-May-2006
https://dl.acm.org/doi/10.1145/1132516.1132614
Haitner IHarnik DReingold O(2006)On the power of the randomized iterateProceedings of the 26th annual international conference on Advances in Cryptology10.1007/11818175_2(22-40)Online publication date: 20-Aug-2006
https://dl.acm.org/doi/10.1007/11818175_2
Show More Cited By

Index Terms

Security-preserving hardness-amplification for any regular one-way function

Recommendations

Convertible Authenticated Encryption Scheme Without Using Conventional One-Way Function

An authenticated encryption allows the designated recipient to verify the authenticity while recovering the message. To protect the recipient's benefit in case of a later dispute, a convertible authenticated encryption scheme allows the recipient to ...
Correlated product security from any one-way function
PKC'12: Proceedings of the 15th international conference on Practice and Theory in Public Key Cryptography

It is well-known that the <em>k</em> -wise product of one-way functions remains one-way, but may no longer be when the <em>k</em> inputs are correlated. At TCC 2009, Rosen and Segev introduced a new notion known as Correlated Product secure functions. ...
Convertible multi-authenticated encryption scheme with one-way hash function

To send the message to the recipient securely, authenticated encryption schemes were proposed. In 2008, Wu et al. [T.S. Wu, C.L. Hsu, K.Y. Tsai, H.Y. Lin, T.C. Wu, Convertible multi-authenticated encryption scheme, Information Sciences 178 (1) 256-263.] ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of Computing

May 1999

790 pages

ISBN:1581130678

DOI:10.1145/301250

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC99

Sponsor:

SIGACT

STOC99: ACM Symposium on Theory of Computing

May 1 - 4, 1999

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
422
Total Downloads

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

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hirahara SShimizu NMohar BShinkar IO'Donnell R(2024)Planted Clique Conjectures Are EquivalentProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649751(358-366)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649751
Akavia AGoldreich OGoldwasser SMoshkovitz DKleinberg J(2006)On basing one-way functions on NP-hardnessProceedings of the thirty-eighth annual ACM symposium on Theory of Computing10.1145/1132516.1132614(701-710)Online publication date: 21-May-2006
https://dl.acm.org/doi/10.1145/1132516.1132614
Haitner IHarnik DReingold O(2006)On the power of the randomized iterateProceedings of the 26th annual international conference on Advances in Cryptology10.1007/11818175_2(22-40)Online publication date: 20-Aug-2006
https://dl.acm.org/doi/10.1007/11818175_2
Lu C(2006)On the complexity of parallel hardness amplification for one-way functionsProceedings of the Third conference on Theory of Cryptography10.1007/11681878_24(462-481)Online publication date: 4-Mar-2006
https://dl.acm.org/doi/10.1007/11681878_24
Di Crescenzo GCatalano DCramer RDi Crescenzo GDarmgård IPointcheval DTakagi T(2005)Foundations of Modern CryptographyContemporary Cryptology10.1007/3-7643-7394-6_3(89-131)Online publication date: 2005
https://doi.org/10.1007/3-7643-7394-6_3
Di Crescenzo G(2005)You can prove so many things in zero-knowledgeProceedings of the First SKLOIS conference on Information Security and Cryptology10.1007/11599548_2(10-27)Online publication date: 15-Dec-2005
https://dl.acm.org/doi/10.1007/11599548_2

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Convertible Authenticated Encryption Scheme Without Using Conventional One-Way Function

Correlated product security from any one-way function

Convertible multi-authenticated encryption scheme with one-way hash function