Stronger security definition of PRG











up vote
3
down vote

favorite












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.










share|improve this question




























    up vote
    3
    down vote

    favorite












    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.










    share|improve this question


























      up vote
      3
      down vote

      favorite









      up vote
      3
      down vote

      favorite











      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.










      share|improve this question















      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






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited Dec 3 at 17:03

























      asked Dec 3 at 13:08









      fgrieu

      77.6k7162327




      77.6k7162327






















          1 Answer
          1






          active

          oldest

          votes

















          up vote
          4
          down vote













          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.






          share|improve this answer





















          • "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?
            – fgrieu
            Dec 3 at 17:18










          • @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.
            – Maeher
            Dec 3 at 18:16










          • Heuristically, hashing the seed is good enough. In the ROM, this is secure.
            – Yehuda Lindell
            Dec 4 at 12:37











          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
          });


          }
          });














          draft saved

          draft discarded


















          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








          up vote
          4
          down vote













          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.






          share|improve this answer





















          • "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?
            – fgrieu
            Dec 3 at 17:18










          • @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.
            – Maeher
            Dec 3 at 18:16










          • Heuristically, hashing the seed is good enough. In the ROM, this is secure.
            – Yehuda Lindell
            Dec 4 at 12:37















          up vote
          4
          down vote













          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.






          share|improve this answer





















          • "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?
            – fgrieu
            Dec 3 at 17:18










          • @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.
            – Maeher
            Dec 3 at 18:16










          • Heuristically, hashing the seed is good enough. In the ROM, this is secure.
            – Yehuda Lindell
            Dec 4 at 12:37













          up vote
          4
          down vote










          up vote
          4
          down vote









          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.






          share|improve this answer












          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.







          share|improve this answer












          share|improve this answer



          share|improve this answer










          answered Dec 3 at 14:07









          Yehuda Lindell

          18.3k3560




          18.3k3560












          • "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?
            – fgrieu
            Dec 3 at 17:18










          • @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.
            – Maeher
            Dec 3 at 18:16










          • Heuristically, hashing the seed is good enough. In the ROM, this is secure.
            – Yehuda Lindell
            Dec 4 at 12:37


















          • "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?
            – fgrieu
            Dec 3 at 17:18










          • @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.
            – Maeher
            Dec 3 at 18:16










          • Heuristically, hashing the seed is good enough. In the ROM, this is secure.
            – Yehuda Lindell
            Dec 4 at 12:37
















          "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?
          – fgrieu
          Dec 3 at 17:18




          "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?
          – fgrieu
          Dec 3 at 17:18












          @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.
          – Maeher
          Dec 3 at 18:16




          @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.
          – Maeher
          Dec 3 at 18:16












          Heuristically, hashing the seed is good enough. In the ROM, this is secure.
          – Yehuda Lindell
          Dec 4 at 12:37




          Heuristically, hashing the seed is good enough. In the ROM, this is secure.
          – Yehuda Lindell
          Dec 4 at 12:37


















          draft saved

          draft discarded




















































          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.





          Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


          Please pay close attention to the following guidance:


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


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          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





















































          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







          Popular posts from this blog

          Ellipse (mathématiques)

          Quarter-circle Tiles

          Mont Emei