Stronger security definition of PRG
$begingroup$
By the standard security definition of a Pseudo Random Generator, if $G$ is a PRG, then $G'$ such that $G'(0mathbin|x)=0mathbin|G(x)$ and $G'(1mathbin|x)=1mathbin|G(x)$ is a PRG. We can build a PRG which output starts by some bits of its input, to some arbitrarily large extent.
This means that feeding a practical source of entropy to a PRG secure by that standard security definition can be very unsafe.
Do we have a stronger security definition of PRG (or some other standard cryptographic construction) that avoids this pitfall, and insure security of the output when the input as some (min)entropy?
Addition: there's nothing wrong with the standard definition of PRG. It is consistent, and useful. It's just not what's needed in some cases, including stretching an imperfect entropy source. I'm asking if we have some stronger security definition of crypto-gismo-with-a-PRG-interface avoiding such issue. Much like for hash we have security in the ROM that's stronger than collision and (first and second) preimage resistance.
pseudo-random-generator
asked Dec 3 '18 at 13:08
fgrieufgrieu
78.2k7166331
$endgroup$
add a comment |
$begingroup$
By the standard security definition of a Pseudo Random Generator, if $G$ is a PRG, then $G'$ such that $G'(0mathbin|x)=0mathbin|G(x)$ and $G'(1mathbin|x)=1mathbin|G(x)$ is a PRG. We can build a PRG which output starts by some bits of its input, to some arbitrarily large extent.
This means that feeding a practical source of entropy to a PRG secure by that standard security definition can be very unsafe.
Do we have a stronger security definition of PRG (or some other standard cryptographic construction) that avoids this pitfall, and insure security of the output when the input as some (min)entropy?
Addition: there's nothing wrong with the standard definition of PRG. It is consistent, and useful. It's just not what's needed in some cases, including stretching an imperfect entropy source. I'm asking if we have some stronger security definition of crypto-gismo-with-a-PRG-interface avoiding such issue. Much like for hash we have security in the ROM that's stronger than collision and (first and second) preimage resistance.
pseudo-random-generator
asked Dec 3 '18 at 13:08
fgrieufgrieu
78.2k7166331
$endgroup$
add a comment |
$begingroup$
By the standard security definition of a Pseudo Random Generator, if $G$ is a PRG, then $G'$ such that $G'(0mathbin|x)=0mathbin|G(x)$ and $G'(1mathbin|x)=1mathbin|G(x)$ is a PRG. We can build a PRG which output starts by some bits of its input, to some arbitrarily large extent.
This means that feeding a practical source of entropy to a PRG secure by that standard security definition can be very unsafe.
Do we have a stronger security definition of PRG (or some other standard cryptographic construction) that avoids this pitfall, and insure security of the output when the input as some (min)entropy?
Addition: there's nothing wrong with the standard definition of PRG. It is consistent, and useful. It's just not what's needed in some cases, including stretching an imperfect entropy source. I'm asking if we have some stronger security definition of crypto-gismo-with-a-PRG-interface avoiding such issue. Much like for hash we have security in the ROM that's stronger than collision and (first and second) preimage resistance.
pseudo-random-generator
asked Dec 3 '18 at 13:08
fgrieufgrieu
78.2k7166331
$endgroup$
By the standard security definition of a Pseudo Random Generator, if $G$ is a PRG, then $G'$ such that $G'(0mathbin|x)=0mathbin|G(x)$ and $G'(1mathbin|x)=1mathbin|G(x)$ is a PRG. We can build a PRG which output starts by some bits of its input, to some arbitrarily large extent.
This means that feeding a practical source of entropy to a PRG secure by that standard security definition can be very unsafe.
Do we have a stronger security definition of PRG (or some other standard cryptographic construction) that avoids this pitfall, and insure security of the output when the input as some (min)entropy?
Addition: there's nothing wrong with the standard definition of PRG. It is consistent, and useful. It's just not what's needed in some cases, including stretching an imperfect entropy source. I'm asking if we have some stronger security definition of crypto-gismo-with-a-PRG-interface avoiding such issue. Much like for hash we have security in the ROM that's stronger than collision and (first and second) preimage resistance.
pseudo-random-generator
pseudo-random-generator
asked Dec 3 '18 at 13:08
fgrieufgrieu
78.2k7166331
asked Dec 3 '18 at 13:08
fgrieufgrieu
78.2k7166331
edited Dec 3 '18 at 17:03
fgrieu
asked Dec 3 '18 at 13:08
fgrieufgrieu
78.2k7166331
asked Dec 3 '18 at 13:08
fgrieufgrieu
78.2k7166331
asked Dec 3 '18 at 13:08
fgrieufgrieu
78.2k7166331
78.2k7166331
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There is nothing wrong with the definition of PRG. The definition assumes that the seed is uniformly distributed. If this is not the case, and you only have a source with good min-entropy, then you should use a randomness extractor/key derivation function first. The result of this should then be input as the seed, and all will be fine.
answered Dec 3 '18 at 14:07
Yehuda LindellYehuda Lindell
18.6k3661
$endgroup$
$begingroup$
"Randomness extractor" is not quite what I'm looking for: problem is, it is not interface-compatible with a PRG, for it still needs a uniform random secret input by the definition there. Would a hash secure in the ROM, fed with enough bits that the min-entropy reaches a security parameters, then fed to a PRG (with enough expansion that the combination is a PRG) fit?
$endgroup$
– fgrieu
Dec 3 '18 at 17:18
$begingroup$
@fgrieu There are notions of "seedless extractors" which you may find interesting. Though they do require special properties of their randomness sources, for example for "extractors for independent weak random sources" that require several (at least two) sources and require that they are independent.
$endgroup$
– Maeher
Dec 3 '18 at 18:16
$begingroup$
Heuristically, hashing the seed is good enough. In the ROM, this is secure.
$endgroup$
– Yehuda Lindell
Dec 4 '18 at 12:37
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "281"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f64520%2fstronger-security-definition-of-prg%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There is nothing wrong with the definition of PRG. The definition assumes that the seed is uniformly distributed. If this is not the case, and you only have a source with good min-entropy, then you should use a randomness extractor/key derivation function first. The result of this should then be input as the seed, and all will be fine.
answered Dec 3 '18 at 14:07
Yehuda LindellYehuda Lindell
18.6k3661
$endgroup$
$begingroup$
"Randomness extractor" is not quite what I'm looking for: problem is, it is not interface-compatible with a PRG, for it still needs a uniform random secret input by the definition there. Would a hash secure in the ROM, fed with enough bits that the min-entropy reaches a security parameters, then fed to a PRG (with enough expansion that the combination is a PRG) fit?
$endgroup$
– fgrieu
Dec 3 '18 at 17:18
$begingroup$
@fgrieu There are notions of "seedless extractors" which you may find interesting. Though they do require special properties of their randomness sources, for example for "extractors for independent weak random sources" that require several (at least two) sources and require that they are independent.
$endgroup$
– Maeher
Dec 3 '18 at 18:16
$begingroup$
Heuristically, hashing the seed is good enough. In the ROM, this is secure.
$endgroup$
– Yehuda Lindell
Dec 4 '18 at 12:37
add a comment |
$begingroup$
There is nothing wrong with the definition of PRG. The definition assumes that the seed is uniformly distributed. If this is not the case, and you only have a source with good min-entropy, then you should use a randomness extractor/key derivation function first. The result of this should then be input as the seed, and all will be fine.
answered Dec 3 '18 at 14:07
Yehuda LindellYehuda Lindell
18.6k3661
$endgroup$
$begingroup$
"Randomness extractor" is not quite what I'm looking for: problem is, it is not interface-compatible with a PRG, for it still needs a uniform random secret input by the definition there. Would a hash secure in the ROM, fed with enough bits that the min-entropy reaches a security parameters, then fed to a PRG (with enough expansion that the combination is a PRG) fit?
$endgroup$
– fgrieu
Dec 3 '18 at 17:18
$begingroup$
@fgrieu There are notions of "seedless extractors" which you may find interesting. Though they do require special properties of their randomness sources, for example for "extractors for independent weak random sources" that require several (at least two) sources and require that they are independent.
$endgroup$
– Maeher
Dec 3 '18 at 18:16
$begingroup$
Heuristically, hashing the seed is good enough. In the ROM, this is secure.
$endgroup$
– Yehuda Lindell
Dec 4 '18 at 12:37
add a comment |
$begingroup$
There is nothing wrong with the definition of PRG. The definition assumes that the seed is uniformly distributed. If this is not the case, and you only have a source with good min-entropy, then you should use a randomness extractor/key derivation function first. The result of this should then be input as the seed, and all will be fine.
answered Dec 3 '18 at 14:07
Yehuda LindellYehuda Lindell
18.6k3661
$endgroup$
There is nothing wrong with the definition of PRG. The definition assumes that the seed is uniformly distributed. If this is not the case, and you only have a source with good min-entropy, then you should use a randomness extractor/key derivation function first. The result of this should then be input as the seed, and all will be fine.
answered Dec 3 '18 at 14:07
Yehuda LindellYehuda Lindell
18.6k3661
answered Dec 3 '18 at 14:07
Yehuda LindellYehuda Lindell
18.6k3661
answered Dec 3 '18 at 14:07
Yehuda LindellYehuda Lindell
18.6k3661
answered Dec 3 '18 at 14:07
Yehuda LindellYehuda Lindell
18.6k3661
18.6k3661
$begingroup$
"Randomness extractor" is not quite what I'm looking for: problem is, it is not interface-compatible with a PRG, for it still needs a uniform random secret input by the definition there. Would a hash secure in the ROM, fed with enough bits that the min-entropy reaches a security parameters, then fed to a PRG (with enough expansion that the combination is a PRG) fit?
$endgroup$
– fgrieu
Dec 3 '18 at 17:18
$begingroup$
@fgrieu There are notions of "seedless extractors" which you may find interesting. Though they do require special properties of their randomness sources, for example for "extractors for independent weak random sources" that require several (at least two) sources and require that they are independent.
$endgroup$
– Maeher
Dec 3 '18 at 18:16
$begingroup$
Heuristically, hashing the seed is good enough. In the ROM, this is secure.
$endgroup$
– Yehuda Lindell
Dec 4 '18 at 12:37
add a comment |
$begingroup$
"Randomness extractor" is not quite what I'm looking for: problem is, it is not interface-compatible with a PRG, for it still needs a uniform random secret input by the definition there. Would a hash secure in the ROM, fed with enough bits that the min-entropy reaches a security parameters, then fed to a PRG (with enough expansion that the combination is a PRG) fit?
$endgroup$
– fgrieu
Dec 3 '18 at 17:18
$begingroup$
@fgrieu There are notions of "seedless extractors" which you may find interesting. Though they do require special properties of their randomness sources, for example for "extractors for independent weak random sources" that require several (at least two) sources and require that they are independent.
$endgroup$
– Maeher
Dec 3 '18 at 18:16
$begingroup$
Heuristically, hashing the seed is good enough. In the ROM, this is secure.
$endgroup$
– Yehuda Lindell
Dec 4 '18 at 12:37
$begingroup$
"Randomness extractor" is not quite what I'm looking for: problem is, it is not interface-compatible with a PRG, for it still needs a uniform random secret input by the definition there. Would a hash secure in the ROM, fed with enough bits that the min-entropy reaches a security parameters, then fed to a PRG (with enough expansion that the combination is a PRG) fit?
$endgroup$
– fgrieu
Dec 3 '18 at 17:18
$begingroup$
"Randomness extractor" is not quite what I'm looking for: problem is, it is not interface-compatible with a PRG, for it still needs a uniform random secret input by the definition there. Would a hash secure in the ROM, fed with enough bits that the min-entropy reaches a security parameters, then fed to a PRG (with enough expansion that the combination is a PRG) fit?
$endgroup$
– fgrieu
Dec 3 '18 at 17:18
$begingroup$
@fgrieu There are notions of "seedless extractors" which you may find interesting. Though they do require special properties of their randomness sources, for example for "extractors for independent weak random sources" that require several (at least two) sources and require that they are independent.
$endgroup$
– Maeher
Dec 3 '18 at 18:16
$begingroup$
@fgrieu There are notions of "seedless extractors" which you may find interesting. Though they do require special properties of their randomness sources, for example for "extractors for independent weak random sources" that require several (at least two) sources and require that they are independent.
$endgroup$
– Maeher
Dec 3 '18 at 18:16
$begingroup$
Heuristically, hashing the seed is good enough. In the ROM, this is secure.
$endgroup$
– Yehuda Lindell
Dec 4 '18 at 12:37
$begingroup$
Heuristically, hashing the seed is good enough. In the ROM, this is secure.
$endgroup$
– Yehuda Lindell
Dec 4 '18 at 12:37
add a comment |
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f64520%2fstronger-security-definition-of-prg%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
