Homomorphic encryption - Why does addition not imply multiplication?












8














As far as I know:



There are some partially homomorphic encryption (PHE) systems that support either addition or multiplication.



A fully homomorphic encryption (FHE) system can do addition as well as multiplication and thus supports arbitrary computation on ciphertexts.



My question is (disregarding computational efficiency):



Why does a PHE-system that allows addition on ciphertext not directly imply that it also can do multiplication, since



$$a times b$$



is the same as



$$underbrace{a + a + cdots + a}_{btext{ times}}?$$



Are there some computations that are only possible with a direct multiplication instead of a continuous addition?










share|improve this question
























  • What you do is multiplication by a constant value $b$. Indeed you can do it, and also you can use double-and-add to perform multiplication by $b$ in $log{b}$ additions. However, you can not multiply by encrypted value $b$ publicly (without knowing the secret key), and that is what FHE is expected to provide.
    – Hyperflame
    Jan 3 at 21:18


















8














As far as I know:



There are some partially homomorphic encryption (PHE) systems that support either addition or multiplication.



A fully homomorphic encryption (FHE) system can do addition as well as multiplication and thus supports arbitrary computation on ciphertexts.



My question is (disregarding computational efficiency):



Why does a PHE-system that allows addition on ciphertext not directly imply that it also can do multiplication, since



$$a times b$$



is the same as



$$underbrace{a + a + cdots + a}_{btext{ times}}?$$



Are there some computations that are only possible with a direct multiplication instead of a continuous addition?










share|improve this question
























  • What you do is multiplication by a constant value $b$. Indeed you can do it, and also you can use double-and-add to perform multiplication by $b$ in $log{b}$ additions. However, you can not multiply by encrypted value $b$ publicly (without knowing the secret key), and that is what FHE is expected to provide.
    – Hyperflame
    Jan 3 at 21:18
















8












8








8


2





As far as I know:



There are some partially homomorphic encryption (PHE) systems that support either addition or multiplication.



A fully homomorphic encryption (FHE) system can do addition as well as multiplication and thus supports arbitrary computation on ciphertexts.



My question is (disregarding computational efficiency):



Why does a PHE-system that allows addition on ciphertext not directly imply that it also can do multiplication, since



$$a times b$$



is the same as



$$underbrace{a + a + cdots + a}_{btext{ times}}?$$



Are there some computations that are only possible with a direct multiplication instead of a continuous addition?










share|improve this question















As far as I know:



There are some partially homomorphic encryption (PHE) systems that support either addition or multiplication.



A fully homomorphic encryption (FHE) system can do addition as well as multiplication and thus supports arbitrary computation on ciphertexts.



My question is (disregarding computational efficiency):



Why does a PHE-system that allows addition on ciphertext not directly imply that it also can do multiplication, since



$$a times b$$



is the same as



$$underbrace{a + a + cdots + a}_{btext{ times}}?$$



Are there some computations that are only possible with a direct multiplication instead of a continuous addition?







homomorphic-encryption






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Dec 29 '18 at 14:15









kelalaka

5,78522040




5,78522040










asked Dec 29 '18 at 13:57









AleksanderRas

1,8761625




1,8761625












  • What you do is multiplication by a constant value $b$. Indeed you can do it, and also you can use double-and-add to perform multiplication by $b$ in $log{b}$ additions. However, you can not multiply by encrypted value $b$ publicly (without knowing the secret key), and that is what FHE is expected to provide.
    – Hyperflame
    Jan 3 at 21:18




















  • What you do is multiplication by a constant value $b$. Indeed you can do it, and also you can use double-and-add to perform multiplication by $b$ in $log{b}$ additions. However, you can not multiply by encrypted value $b$ publicly (without knowing the secret key), and that is what FHE is expected to provide.
    – Hyperflame
    Jan 3 at 21:18


















What you do is multiplication by a constant value $b$. Indeed you can do it, and also you can use double-and-add to perform multiplication by $b$ in $log{b}$ additions. However, you can not multiply by encrypted value $b$ publicly (without knowing the secret key), and that is what FHE is expected to provide.
– Hyperflame
Jan 3 at 21:18






What you do is multiplication by a constant value $b$. Indeed you can do it, and also you can use double-and-add to perform multiplication by $b$ in $log{b}$ additions. However, you can not multiply by encrypted value $b$ publicly (without knowing the secret key), and that is what FHE is expected to provide.
– Hyperflame
Jan 3 at 21:18












3 Answers
3






active

oldest

votes


















10














There are at least two problems;




  1. The $b$-times addition leaks the $b$. A semi-honest observer can see that you add the $a$ by $b$ times. However, in FHE, the $b$ is also encrypted with semantically secure that leaks no information. The only information available to the observer is the circuit.


  2. In FHE, the $b$ is coming (or may come) from another result, which means that $b$ is also encrypted. In additive PHE, you cannot multiply by $b$ without decryption.



You can look at some example of FHE circuits from this answer to see that some of them are not even possible with additive PHE.






share|improve this answer























  • Why do you care about "leakage" in the first place?
    – Hyperflame
    Jan 3 at 21:16










  • @Hyperflame It is writing style, keep the important ones lastly! In Cryptanalysis every leak is important.
    – kelalaka
    Jan 3 at 21:23










  • I think the FHE notion does not care about leakage of computations. Having a gate 'multiply by 10' or 'multiply by 123' in homomorphic encryption setting is not a problem at all (and as the topic suggests, PHE implies it).
    – Hyperflame
    yesterday



















4














$b$ is encrypted and therefore unknown to the machine doing the multiplication. So, you cannot just "add $b$ times".



One thing you may be tempted to think is just subtract 1 from the encrypted $b$ and stop when $b$ is zero. For a semantically secure homomorphic cipher, this is impossible. If your homomorphic cipher is not semantically secure, it can easily be broken.






share|improve this answer

















  • 2




    Also: for any ciphertext that is larger than 128 bits in size, it would take an obscenely long amount of time to do the subtract-by-1-until-0 method, even if it worked.
    – Ella Rose
    Dec 29 '18 at 16:41



















4














The other answers are correct, but I wanted to note that:



If you can add ciphertexts together, then you can multiply them by a plaintext value, because of the reason you described in your question.



Similarly, if you can multiply ciphertexts together, then you can exponentiate them by a plaintext value as well.



So if you distribute two ciphertexts $c_0, c_1$ and your algorithm supports only the ability to add ciphertexts together, then it is not possible to meaningfully evaluate $c_0 c_1$, but it is possible for anyone to meaningfully evaluate $c_0p_0$.






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',
    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%2f66151%2fhomomorphic-encryption-why-does-addition-not-imply-multiplication%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    3 Answers
    3






    active

    oldest

    votes








    3 Answers
    3






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    10














    There are at least two problems;




    1. The $b$-times addition leaks the $b$. A semi-honest observer can see that you add the $a$ by $b$ times. However, in FHE, the $b$ is also encrypted with semantically secure that leaks no information. The only information available to the observer is the circuit.


    2. In FHE, the $b$ is coming (or may come) from another result, which means that $b$ is also encrypted. In additive PHE, you cannot multiply by $b$ without decryption.



    You can look at some example of FHE circuits from this answer to see that some of them are not even possible with additive PHE.






    share|improve this answer























    • Why do you care about "leakage" in the first place?
      – Hyperflame
      Jan 3 at 21:16










    • @Hyperflame It is writing style, keep the important ones lastly! In Cryptanalysis every leak is important.
      – kelalaka
      Jan 3 at 21:23










    • I think the FHE notion does not care about leakage of computations. Having a gate 'multiply by 10' or 'multiply by 123' in homomorphic encryption setting is not a problem at all (and as the topic suggests, PHE implies it).
      – Hyperflame
      yesterday
















    10














    There are at least two problems;




    1. The $b$-times addition leaks the $b$. A semi-honest observer can see that you add the $a$ by $b$ times. However, in FHE, the $b$ is also encrypted with semantically secure that leaks no information. The only information available to the observer is the circuit.


    2. In FHE, the $b$ is coming (or may come) from another result, which means that $b$ is also encrypted. In additive PHE, you cannot multiply by $b$ without decryption.



    You can look at some example of FHE circuits from this answer to see that some of them are not even possible with additive PHE.






    share|improve this answer























    • Why do you care about "leakage" in the first place?
      – Hyperflame
      Jan 3 at 21:16










    • @Hyperflame It is writing style, keep the important ones lastly! In Cryptanalysis every leak is important.
      – kelalaka
      Jan 3 at 21:23










    • I think the FHE notion does not care about leakage of computations. Having a gate 'multiply by 10' or 'multiply by 123' in homomorphic encryption setting is not a problem at all (and as the topic suggests, PHE implies it).
      – Hyperflame
      yesterday














    10












    10








    10






    There are at least two problems;




    1. The $b$-times addition leaks the $b$. A semi-honest observer can see that you add the $a$ by $b$ times. However, in FHE, the $b$ is also encrypted with semantically secure that leaks no information. The only information available to the observer is the circuit.


    2. In FHE, the $b$ is coming (or may come) from another result, which means that $b$ is also encrypted. In additive PHE, you cannot multiply by $b$ without decryption.



    You can look at some example of FHE circuits from this answer to see that some of them are not even possible with additive PHE.






    share|improve this answer














    There are at least two problems;




    1. The $b$-times addition leaks the $b$. A semi-honest observer can see that you add the $a$ by $b$ times. However, in FHE, the $b$ is also encrypted with semantically secure that leaks no information. The only information available to the observer is the circuit.


    2. In FHE, the $b$ is coming (or may come) from another result, which means that $b$ is also encrypted. In additive PHE, you cannot multiply by $b$ without decryption.



    You can look at some example of FHE circuits from this answer to see that some of them are not even possible with additive PHE.







    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited Dec 29 '18 at 14:23

























    answered Dec 29 '18 at 14:11









    kelalaka

    5,78522040




    5,78522040












    • Why do you care about "leakage" in the first place?
      – Hyperflame
      Jan 3 at 21:16










    • @Hyperflame It is writing style, keep the important ones lastly! In Cryptanalysis every leak is important.
      – kelalaka
      Jan 3 at 21:23










    • I think the FHE notion does not care about leakage of computations. Having a gate 'multiply by 10' or 'multiply by 123' in homomorphic encryption setting is not a problem at all (and as the topic suggests, PHE implies it).
      – Hyperflame
      yesterday


















    • Why do you care about "leakage" in the first place?
      – Hyperflame
      Jan 3 at 21:16










    • @Hyperflame It is writing style, keep the important ones lastly! In Cryptanalysis every leak is important.
      – kelalaka
      Jan 3 at 21:23










    • I think the FHE notion does not care about leakage of computations. Having a gate 'multiply by 10' or 'multiply by 123' in homomorphic encryption setting is not a problem at all (and as the topic suggests, PHE implies it).
      – Hyperflame
      yesterday
















    Why do you care about "leakage" in the first place?
    – Hyperflame
    Jan 3 at 21:16




    Why do you care about "leakage" in the first place?
    – Hyperflame
    Jan 3 at 21:16












    @Hyperflame It is writing style, keep the important ones lastly! In Cryptanalysis every leak is important.
    – kelalaka
    Jan 3 at 21:23




    @Hyperflame It is writing style, keep the important ones lastly! In Cryptanalysis every leak is important.
    – kelalaka
    Jan 3 at 21:23












    I think the FHE notion does not care about leakage of computations. Having a gate 'multiply by 10' or 'multiply by 123' in homomorphic encryption setting is not a problem at all (and as the topic suggests, PHE implies it).
    – Hyperflame
    yesterday




    I think the FHE notion does not care about leakage of computations. Having a gate 'multiply by 10' or 'multiply by 123' in homomorphic encryption setting is not a problem at all (and as the topic suggests, PHE implies it).
    – Hyperflame
    yesterday











    4














    $b$ is encrypted and therefore unknown to the machine doing the multiplication. So, you cannot just "add $b$ times".



    One thing you may be tempted to think is just subtract 1 from the encrypted $b$ and stop when $b$ is zero. For a semantically secure homomorphic cipher, this is impossible. If your homomorphic cipher is not semantically secure, it can easily be broken.






    share|improve this answer

















    • 2




      Also: for any ciphertext that is larger than 128 bits in size, it would take an obscenely long amount of time to do the subtract-by-1-until-0 method, even if it worked.
      – Ella Rose
      Dec 29 '18 at 16:41
















    4














    $b$ is encrypted and therefore unknown to the machine doing the multiplication. So, you cannot just "add $b$ times".



    One thing you may be tempted to think is just subtract 1 from the encrypted $b$ and stop when $b$ is zero. For a semantically secure homomorphic cipher, this is impossible. If your homomorphic cipher is not semantically secure, it can easily be broken.






    share|improve this answer

















    • 2




      Also: for any ciphertext that is larger than 128 bits in size, it would take an obscenely long amount of time to do the subtract-by-1-until-0 method, even if it worked.
      – Ella Rose
      Dec 29 '18 at 16:41














    4












    4








    4






    $b$ is encrypted and therefore unknown to the machine doing the multiplication. So, you cannot just "add $b$ times".



    One thing you may be tempted to think is just subtract 1 from the encrypted $b$ and stop when $b$ is zero. For a semantically secure homomorphic cipher, this is impossible. If your homomorphic cipher is not semantically secure, it can easily be broken.






    share|improve this answer












    $b$ is encrypted and therefore unknown to the machine doing the multiplication. So, you cannot just "add $b$ times".



    One thing you may be tempted to think is just subtract 1 from the encrypted $b$ and stop when $b$ is zero. For a semantically secure homomorphic cipher, this is impossible. If your homomorphic cipher is not semantically secure, it can easily be broken.







    share|improve this answer












    share|improve this answer



    share|improve this answer










    answered Dec 29 '18 at 14:11









    mikeazo

    32.8k787145




    32.8k787145








    • 2




      Also: for any ciphertext that is larger than 128 bits in size, it would take an obscenely long amount of time to do the subtract-by-1-until-0 method, even if it worked.
      – Ella Rose
      Dec 29 '18 at 16:41














    • 2




      Also: for any ciphertext that is larger than 128 bits in size, it would take an obscenely long amount of time to do the subtract-by-1-until-0 method, even if it worked.
      – Ella Rose
      Dec 29 '18 at 16:41








    2




    2




    Also: for any ciphertext that is larger than 128 bits in size, it would take an obscenely long amount of time to do the subtract-by-1-until-0 method, even if it worked.
    – Ella Rose
    Dec 29 '18 at 16:41




    Also: for any ciphertext that is larger than 128 bits in size, it would take an obscenely long amount of time to do the subtract-by-1-until-0 method, even if it worked.
    – Ella Rose
    Dec 29 '18 at 16:41











    4














    The other answers are correct, but I wanted to note that:



    If you can add ciphertexts together, then you can multiply them by a plaintext value, because of the reason you described in your question.



    Similarly, if you can multiply ciphertexts together, then you can exponentiate them by a plaintext value as well.



    So if you distribute two ciphertexts $c_0, c_1$ and your algorithm supports only the ability to add ciphertexts together, then it is not possible to meaningfully evaluate $c_0 c_1$, but it is possible for anyone to meaningfully evaluate $c_0p_0$.






    share|improve this answer


























      4














      The other answers are correct, but I wanted to note that:



      If you can add ciphertexts together, then you can multiply them by a plaintext value, because of the reason you described in your question.



      Similarly, if you can multiply ciphertexts together, then you can exponentiate them by a plaintext value as well.



      So if you distribute two ciphertexts $c_0, c_1$ and your algorithm supports only the ability to add ciphertexts together, then it is not possible to meaningfully evaluate $c_0 c_1$, but it is possible for anyone to meaningfully evaluate $c_0p_0$.






      share|improve this answer
























        4












        4








        4






        The other answers are correct, but I wanted to note that:



        If you can add ciphertexts together, then you can multiply them by a plaintext value, because of the reason you described in your question.



        Similarly, if you can multiply ciphertexts together, then you can exponentiate them by a plaintext value as well.



        So if you distribute two ciphertexts $c_0, c_1$ and your algorithm supports only the ability to add ciphertexts together, then it is not possible to meaningfully evaluate $c_0 c_1$, but it is possible for anyone to meaningfully evaluate $c_0p_0$.






        share|improve this answer












        The other answers are correct, but I wanted to note that:



        If you can add ciphertexts together, then you can multiply them by a plaintext value, because of the reason you described in your question.



        Similarly, if you can multiply ciphertexts together, then you can exponentiate them by a plaintext value as well.



        So if you distribute two ciphertexts $c_0, c_1$ and your algorithm supports only the ability to add ciphertexts together, then it is not possible to meaningfully evaluate $c_0 c_1$, but it is possible for anyone to meaningfully evaluate $c_0p_0$.







        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered Dec 29 '18 at 16:40









        Ella Rose

        15.3k44279




        15.3k44279






























            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%2f66151%2fhomomorphic-encryption-why-does-addition-not-imply-multiplication%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

            How to change which sound is reproduced for terminal bell?

            Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents

            Can I use Tabulator js library in my java Spring + Thymeleaf project?