Publication Details
Title: Public Randomness in Cryptography
Author: A. Herzberg and M. Luby
Group: ICSI Technical Reports
Date: October 1992
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-068.pdf
Overview:
The main contribution of this paper is the introduction of a formal notion of public randomness in the context of cryptography. We show how this notion affects the definition of the security of a cryptoigraphic primitive and the definition of how much security is preserved when one cryptographic primitive is reduced to another. Previous works considered the public random bits as a part of the input, and security was parameterized in terms of the total length of the input. We parameterize security solely in terms of the length of the private input, and treat the public random bits as a separate resource. This separation allows us to independently address the important issues of how much security is preserved by a reduction and how many public random bits are used in the reduction. To exemplify these new definitions, we present reductions from weak one-way permutations to one-way permutations with strong security preserving properties that are simpler than previously known reductions.
Bibliographic Information:
ICSI Technical Report TR-92-068
Bibliographic Reference:
A. Herzberg and M. Luby. Public Randomness in Cryptography. ICSI Technical Report TR-92-068, October 1992
Author: A. Herzberg and M. Luby
Group: ICSI Technical Reports
Date: October 1992
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-068.pdf
Overview:
The main contribution of this paper is the introduction of a formal notion of public randomness in the context of cryptography. We show how this notion affects the definition of the security of a cryptoigraphic primitive and the definition of how much security is preserved when one cryptographic primitive is reduced to another. Previous works considered the public random bits as a part of the input, and security was parameterized in terms of the total length of the input. We parameterize security solely in terms of the length of the private input, and treat the public random bits as a separate resource. This separation allows us to independently address the important issues of how much security is preserved by a reduction and how many public random bits are used in the reduction. To exemplify these new definitions, we present reductions from weak one-way permutations to one-way permutations with strong security preserving properties that are simpler than previously known reductions.
Bibliographic Information:
ICSI Technical Report TR-92-068
Bibliographic Reference:
A. Herzberg and M. Luby. Public Randomness in Cryptography. ICSI Technical Report TR-92-068, October 1992