Zero Knowledge and Computational Indistinguishability

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
2
down vote

favorite












Having some trouble understanding the following line:
“Alice conveys zero knowledge to Bob if Bob can sample
from a distribution of messages that is computationally indistinguishable
from the distribution of messages that Alice would
send.”



From Page 122, https://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf



Could someone give a practical example of this sentence?










share|improve this question

























    up vote
    2
    down vote

    favorite












    Having some trouble understanding the following line:
    “Alice conveys zero knowledge to Bob if Bob can sample
    from a distribution of messages that is computationally indistinguishable
    from the distribution of messages that Alice would
    send.”



    From Page 122, https://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf



    Could someone give a practical example of this sentence?










    share|improve this question























      up vote
      2
      down vote

      favorite









      up vote
      2
      down vote

      favorite











      Having some trouble understanding the following line:
      “Alice conveys zero knowledge to Bob if Bob can sample
      from a distribution of messages that is computationally indistinguishable
      from the distribution of messages that Alice would
      send.”



      From Page 122, https://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf



      Could someone give a practical example of this sentence?










      share|improve this question













      Having some trouble understanding the following line:
      “Alice conveys zero knowledge to Bob if Bob can sample
      from a distribution of messages that is computationally indistinguishable
      from the distribution of messages that Alice would
      send.”



      From Page 122, https://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf



      Could someone give a practical example of this sentence?







      zero-knowledge-proofs






      share|improve this question













      share|improve this question











      share|improve this question




      share|improve this question










      asked 1 hour ago









      Kek

      233




      233




















          1 Answer
          1






          active

          oldest

          votes

















          up vote
          2
          down vote



          accepted










          Suppose in some protocol Alice is supposed to send an encryption of her special secret $s$ under a public key $pk$. She is sampling from the distribution of encryptions of $s$.



          Bob can choose a random plaintext $r$ and encrypt it under $pk$. He is sampling from the distribution of encryptions of random plaintexts.



          Even though Bob doesn't know Alice's special secret $s$, these two distributions are computationally indistinguishable (that's the basic definition of security for the encryption scheme). So this message (Alice's encryption of $s$) is zero-knowledge.



          In a real example, you would have to simulate the entire exchange of all messages (called the transcript). It doesn't really work to simulate just one at a time, you have to capture correlations along messages if there are many rounds in the protocol.




          Imagine Alice wants to prove to Bob that she is a good archer. The protocol to convince him is for Bob to paint a target on the wall, then Alice will fire an arrow into the bullseye. The "transcript" (the information that Bob leaves with) is a target painted on a wall with an arrow in the bullseye.



          But Bob can generate the same distribution of transcripts without Alice's help! He can just put an arrow into the wall first and then paint a target around it. Hence, the protocol is "zero-knowledge."






          share|improve this answer




















            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',
            convertImagesToLinks: false,
            noModals: false,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            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%2f63295%2fzero-knowledge-and-computational-indistinguishability%23new-answer', 'question_page');

            );

            Post as a guest






























            1 Answer
            1






            active

            oldest

            votes








            1 Answer
            1






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes








            up vote
            2
            down vote



            accepted










            Suppose in some protocol Alice is supposed to send an encryption of her special secret $s$ under a public key $pk$. She is sampling from the distribution of encryptions of $s$.



            Bob can choose a random plaintext $r$ and encrypt it under $pk$. He is sampling from the distribution of encryptions of random plaintexts.



            Even though Bob doesn't know Alice's special secret $s$, these two distributions are computationally indistinguishable (that's the basic definition of security for the encryption scheme). So this message (Alice's encryption of $s$) is zero-knowledge.



            In a real example, you would have to simulate the entire exchange of all messages (called the transcript). It doesn't really work to simulate just one at a time, you have to capture correlations along messages if there are many rounds in the protocol.




            Imagine Alice wants to prove to Bob that she is a good archer. The protocol to convince him is for Bob to paint a target on the wall, then Alice will fire an arrow into the bullseye. The "transcript" (the information that Bob leaves with) is a target painted on a wall with an arrow in the bullseye.



            But Bob can generate the same distribution of transcripts without Alice's help! He can just put an arrow into the wall first and then paint a target around it. Hence, the protocol is "zero-knowledge."






            share|improve this answer
























              up vote
              2
              down vote



              accepted










              Suppose in some protocol Alice is supposed to send an encryption of her special secret $s$ under a public key $pk$. She is sampling from the distribution of encryptions of $s$.



              Bob can choose a random plaintext $r$ and encrypt it under $pk$. He is sampling from the distribution of encryptions of random plaintexts.



              Even though Bob doesn't know Alice's special secret $s$, these two distributions are computationally indistinguishable (that's the basic definition of security for the encryption scheme). So this message (Alice's encryption of $s$) is zero-knowledge.



              In a real example, you would have to simulate the entire exchange of all messages (called the transcript). It doesn't really work to simulate just one at a time, you have to capture correlations along messages if there are many rounds in the protocol.




              Imagine Alice wants to prove to Bob that she is a good archer. The protocol to convince him is for Bob to paint a target on the wall, then Alice will fire an arrow into the bullseye. The "transcript" (the information that Bob leaves with) is a target painted on a wall with an arrow in the bullseye.



              But Bob can generate the same distribution of transcripts without Alice's help! He can just put an arrow into the wall first and then paint a target around it. Hence, the protocol is "zero-knowledge."






              share|improve this answer






















                up vote
                2
                down vote



                accepted







                up vote
                2
                down vote



                accepted






                Suppose in some protocol Alice is supposed to send an encryption of her special secret $s$ under a public key $pk$. She is sampling from the distribution of encryptions of $s$.



                Bob can choose a random plaintext $r$ and encrypt it under $pk$. He is sampling from the distribution of encryptions of random plaintexts.



                Even though Bob doesn't know Alice's special secret $s$, these two distributions are computationally indistinguishable (that's the basic definition of security for the encryption scheme). So this message (Alice's encryption of $s$) is zero-knowledge.



                In a real example, you would have to simulate the entire exchange of all messages (called the transcript). It doesn't really work to simulate just one at a time, you have to capture correlations along messages if there are many rounds in the protocol.




                Imagine Alice wants to prove to Bob that she is a good archer. The protocol to convince him is for Bob to paint a target on the wall, then Alice will fire an arrow into the bullseye. The "transcript" (the information that Bob leaves with) is a target painted on a wall with an arrow in the bullseye.



                But Bob can generate the same distribution of transcripts without Alice's help! He can just put an arrow into the wall first and then paint a target around it. Hence, the protocol is "zero-knowledge."






                share|improve this answer












                Suppose in some protocol Alice is supposed to send an encryption of her special secret $s$ under a public key $pk$. She is sampling from the distribution of encryptions of $s$.



                Bob can choose a random plaintext $r$ and encrypt it under $pk$. He is sampling from the distribution of encryptions of random plaintexts.



                Even though Bob doesn't know Alice's special secret $s$, these two distributions are computationally indistinguishable (that's the basic definition of security for the encryption scheme). So this message (Alice's encryption of $s$) is zero-knowledge.



                In a real example, you would have to simulate the entire exchange of all messages (called the transcript). It doesn't really work to simulate just one at a time, you have to capture correlations along messages if there are many rounds in the protocol.




                Imagine Alice wants to prove to Bob that she is a good archer. The protocol to convince him is for Bob to paint a target on the wall, then Alice will fire an arrow into the bullseye. The "transcript" (the information that Bob leaves with) is a target painted on a wall with an arrow in the bullseye.



                But Bob can generate the same distribution of transcripts without Alice's help! He can just put an arrow into the wall first and then paint a target around it. Hence, the protocol is "zero-knowledge."







                share|improve this answer












                share|improve this answer



                share|improve this answer










                answered 1 hour ago









                Mikero

                4,94111521




                4,94111521



























                     

                    draft saved


                    draft discarded















































                     


                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function ()
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f63295%2fzero-knowledge-and-computational-indistinguishability%23new-answer', 'question_page');

                    );

                    Post as a guest













































































                    Popular posts from this blog

                    How to check contact read email or not when send email to Individual?

                    Displaying single band from multi-band raster using QGIS

                    How many registers does an x86_64 CPU actually have?