<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Seongjin Kim on Medium]]></title>
        <description><![CDATA[Stories by Seongjin Kim on Medium]]></description>
        <link>https://medium.com/@seongjin.kim_68990?source=rss-2b94ab58a269------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*Gka1IHlwC_Mkd36Whq9DBA.png</url>
            <title>Stories by Seongjin Kim on Medium</title>
            <link>https://medium.com/@seongjin.kim_68990?source=rss-2b94ab58a269------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 06:44:43 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@seongjin.kim_68990/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[[zk-SNARKs 기초] 4. How to make Blind Evaluation of Polynomials Verifiable]]></title>
            <link>https://medium.com/@seongjin.kim_68990/zk-snarks-%EA%B8%B0%EC%B4%88-4-how-to-make-blind-evaluation-of-polynomials-verifiable-e914e4e55be5?source=rss-2b94ab58a269------2</link>
            <guid isPermaLink="false">https://medium.com/p/e914e4e55be5</guid>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[zksnark]]></category>
            <category><![CDATA[cryptography]]></category>
            <dc:creator><![CDATA[Seongjin Kim]]></dc:creator>
            <pubDate>Sat, 16 Feb 2019 08:45:44 GMT</pubDate>
            <atom:updated>2019-02-16T08:49:13.521Z</atom:updated>
            <content:encoded><![CDATA[<blockquote>by Seongjin Kim, Core/Security Manager at ReturnValues (<a href="/service/mailto:seongjin.kim@returnvalues.com">seongjin.kim@returnvalues.com</a>)</blockquote><p><strong>[zk-SNARKs 기초] 시리즈<br></strong><a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-1-homomorphic-hiding-e8fd1de40bbd">1. Homomorphic Hiding</a><br><a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-2-blind-evaluation-of-polynomials-ed9e3cd11bc1">2. Blind Evaluation of Polynomials</a><br><a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-3-the-knowledge-of-coefficient-test-and-assumption-1892c82341c1">3. The Knowledge of Coefficient Test and Assumption</a><br><a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-4-how-to-make-blind-evaluation-of-polynomials-verifiable-e914e4e55be5">4. How to make Blind Evaluation of Polynomials Verifiable</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/proxy/1*Feb78QK4tYZn4pIqsRxqXw.png" /></figure><p>이 글은 Zcash 블로그의 내용을 바탕으로 작성했으며, 번역 목적이 아닌 해설을 위해 작성되었기 때문에 내용의 추가와 요약이 있습니다. 원문은 아래 Zcash 블로그를 참고해주시기 바랍니다.<br><a href="https://z.cash/blog/snark-explain4">https://z.cash/blog/snark-explain4</a></p><p>미디엄의 수식 표현 한계로 인해 문장 속에 포함되는 수식을 아래와 같이 표현했습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/428/1*RmiC-40SPzP0uaEjFG26UA.png" /></figure><h3>4. How to make Blind Evaluation of Polynomials Verifiable</h3><p>이 포스팅에서는 이전 포스팅들에서 다루었던 내용을 바탕으로 검증 가능한 다항식의 blind evaluation 프로토콜을 살펴보겠습니다. 그리고 다음 포스팅에서는 이런 프로토콜이 SNARKs를 구성하는데 어떻게 사용되는지 본격적으로 살펴볼 것입니다.</p><p>“<a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-2-blind-evaluation-of-polynomials-ed9e3cd11bc1">Blind Evaluation of Polynomials</a>” 포스팅에서 살펴보았던 것처럼, Alice는 <em>d</em>차 다항식 <em>P</em>를 가지고있고, Bob은 <em>F_p</em>에서 임의로 선택한 원소 <em>s</em>를 가지고 있다고 생각해봅시다. 이 때, 우리는 Bob이 <em>E(P(s))</em>를 받을 수 있도록 프로토콜을 구성하면서 다음과 같은 두 가지 성질을 갖길 바랍니다.</p><p>1. <strong>Blindness </strong>: Alice는 Bob에게 받은 정보로부터 <em>s</em>에 대해 알아낼 수 없습니다. (또한 Bob은 Alice에게 받은 정보로부터 <em>P</em>에 대해 알아낼 수 없습니다.)<br>2. <strong>Verifiability </strong>: Alice가 올바른 <em>E(P(s))</em>를 전달하지 않았지만 Bob이 Alice의 증명을 받아들일 가능성은무시해도 될만큼 충분히 작습니다. 즉, 부정직한 증명자의 증명은 정직한 검증자가 받아들이지 않습니다.</p><p>이것을 우리는 검증 가능한 다항식의 blind evaluation이라고 합니다. 이 프로토콜의 첫 번째 성질(Blindness)은 “<a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-2-blind-evaluation-of-polynomials-ed9e3cd11bc1">Blind Evaluation of Polynomials</a>” 포스팅에서 살펴보았지만, 두 번째 성질(Verifiability)에 대해서는 살펴보지 않았습니다. Verifiability를 얻기 위해서 우리는 “The Knowledge of Coefficient Test and Assumption” 포스팅에서 살펴보았던 <em>Knowledge of Coefficient Assumption(KCA)</em>의 확장된 버전이 필요합니다.</p><p>Alice가 <em>s</em>를 알지 못하는 상태에서 다항식 <em>P</em>를 사용하도록 하는 점에서 위 두가지 성질은 유용하게 사용됩니다. 다시 말하면, Alice가 challenge point <em>s</em>에 대해 알지 못하는 상태에서 다항식의 답변을 하도록 약속합니다. 이 부분에 대해서 지금부터 구체적으로 살펴보겠습니다.</p><h4>An Extended KCA</h4><p>전 포스팅에서 KCA에 대해 다음과 같이 간단히 살펴보았습니다. Bob이 <em>(a, b = α</em>⋅<em>a)</em>인 <em>α</em>-pair를 Alice에게 전달하고, Alice는 그것을 사용해 <em>α</em>-pair <em>(a’, b’)</em>를 만듭니다. 이 때 Alice는 새로운 <em>α</em>-pair를 만들 때 새로운 계수 <em>c</em>를 선택했고, <em>c</em>를 사용해 <em>a’</em>를 계산했습니다<em>(a’ = c</em>⋅<em>a)</em>. 따라서 <em>c</em>는 곧 <em>a</em>와 <em>a’</em>의 비율이라고 볼 수 있습니다.</p><p>이제, Bob이 Alice에게 하나의 <em>α</em>-pair가 아니라 여러 <em>α</em>-pair들<em>(a_1, b_1), …, (a_d, b_d)</em>을 같은 <em>α</em>를 사용해 만들어 전달한다고 가정해봅시다. 그리고 Alice는 이 <em>α</em>-pair들을 받으면, 이것들과 다른 <em>α</em>-pair인 <em>(a’, b’)</em>를 만들어야 합니다. 여기서 Alice가 <em>α</em>에 대해 알지 못한 상태에서 <em>α</em>-pair를 만들어야 한다는 점이 중요합니다.</p><p>전 포스팅에서 보았듯이, Alice가 <em>α</em>를 모르는 상태에서 <em>α</em>-pair를 만드는 방법은, <em>F_p_*</em>에서 선택한 임의의 <em>c</em>와 Bob이 전달해준 <em>(a_i, b_i)</em> 중 하나를 곱해 <em>(c</em>⋅<em>a_i, c</em>⋅<em>b_i)</em>인 <em>α</em>-pair를 만드는 것입니다. 그렇다면, Alice는 <em>α</em>-pair를 여러개 받았으니 이제 <em>α</em>-pair를 만들 때 더 많은 방법으로 만들 수 있을까요? 여러개의 <em>α</em>-pair들 중 몇 개를 동시에 사용해 새로운 <em>α</em>-pair를 만들 수 있지 않을까요?</p><p>그렇습니다. 예를 들면, Alice는 두 개의 <em>c_1, c_2</em> 값을 선택해 다음과 같이 <em>α</em>-pair 생성에 사용할 수 있습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/374/1*f-JmiskhfI5bft_AW8Bo3g.png" /></figure><p>여기서 <em>a’</em>는 <em>0</em>이 아니며, 다음과 같이 <em>(b’ = α</em>⋅<em>a’)</em>라는 <em>α</em>-pair의 조건을 검증할 수 있습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/174/1*ZQEiZTxYQIVS0jh4aS4aPg.png" /></figure><p>이것은 다음과 같이 더 일반화할 수 있습니다. Alice는 주어진 <em>d</em>개 쌍의 어떠한 선형 결합을 취할 수 있습니다. 즉, Alice는 <em>F_p</em>의 원소 <em>c_1, …, c_d</em>를 선택하고, <em>(a’, b’)</em>를 다음과 같이 생성할 수 있습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/280/1*bNvQnRBh0rglCH_LAWKNBA.png" /></figure><p>이것은 곧, Alice가 위와 같은 방법으로 <em>α</em>-pair를 만들었을 때, Alice는 <em>a’</em>와 <em>a_1, …, a_d</em> 사이의 일차 관계식을 알게 된다는 것을 의미합니다. 즉, Alice는 아래 식을 만족하는 <em>c_1, …, c_d</em>를 알고 있습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/148/1*YjvJOggQ4_aiyb0xqIoHyw.png" /></figure><p>확장된 KCA는 이 방법이 Alice가 <em>α</em>-pair를 만들 수 있는 유일한 방법이라고 말합니다. 즉, Alice가 <em>α</em>-pair 생성에 성공한다면 <em>a’</em>와 <em>a_1, …, a_d</em> 사이의 일차 관계식을 알게 된다는 것입니다. 이것의 일반화를 위해 생성원 <em>g</em>를 갖고 크기가 <em>p</em>인 군 <em>G</em>가 있다고 생각해봅시다. 이러한 <em>G</em>에서 <em>The d-power Knowledge of Coefficient Assumption(d-KCA)</em>은 다음과 같습니다.</p><p>d-KCA : Bob이 <em>F_p^*</em>에서 임의로 <em>α</em>를 선택하고 <em>F_p</em>에서 임의로 <em>s</em>를 선택한 뒤, <em>α</em>-pair들인 <em>(g, α</em>⋅<em>g), (s</em>⋅<em>g, αs</em>⋅<em>g), …, (s^d</em>⋅<em>g, αs^d</em>⋅<em>g)</em> 들을 Alice에게 보냅니다. 그 후 Alice가 또다른 <em>α</em>-pair인 <em>(a’, b’)</em>를 만들 때, Alice는 아래 조건을 만족하는 <em>c_0, …, c_d</em>를 알게 됩니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/156/1*tjoQ-pdU8EuxaJMxV_gTjQ.png" /></figure><p>d-KCA에서는 Bob이 <em>α</em>-pair들을 제멋대로 만드는 것이 아니라 위와 같은 다항식 구조를 사용해 만드는 특징이 있습니다. 이 점은 아래 프로토콜에서 유용하게 사용됩니다.</p><h4>The Verifiable Blind Evaluation Protocol</h4><p><em>E(x) = x</em>⋅<em>g</em> 함수를 Homomorphic Hiding(HH)에 사용한다고 가정해봅시다. 이 때 <em>g</em>는 위에서 언급한 것과 같은 <em>G</em>의 생성원입니다. 간소화를 위해 이와 같은 <em>E </em>함수를 사용한 프로토콜을 아래에서 설명합니다. 식이 점점 복잡해지기 때문에 아래 설명에서 필요한 부분들을 먼저 정리해보겠습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*_2FJosZrkshsUSWQiM8Y6A.png" /></figure><p><em>E </em>: 함수 <em>E</em>는 HH로써, 입력값 <em>x</em>를 은닉하기 위해 사용합니다. <em>E(x)</em> 값으로부터 <em>x</em>값을 알아낼 수 없습니다.<br><em>P </em>: <em>X</em>에 대한 <em>d</em>차 다항식 <em>P</em>는 위와 같습니다. <em>P</em>는 크게 <em>c</em>와 <em>X </em>두 가지 요소로 구성되는데, <em>X</em>는 Bob이 <em>E(x)</em>를 사용해 전달한 값이 될 것이고, <em>c</em>는 <em>α</em>-pair를 만들기 위해 Alice가 임의로 선택한 <em>c_0, …, c_d</em>가 될 것입니다. 우리는 이와 같은 방식을 “<a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-2-blind-evaluation-of-polynomials-ed9e3cd11bc1">Blind Evaluation of Polynomials</a>” 포스팅에서 살펴보았습니다. <em>P </em>다항식의 구성에 필요한 <em>c_0, …, c_d</em>에 대해서 Bob은 알 수 없습니다.<br><em>α</em>-pair : <em>(a, b)</em> 쌍에서 <em>b</em>가 <em>b = α</em>⋅<em>a</em>를 만족할 때 우리는 이 쌍을 <em>α</em>-pair라고 부릅니다. <em>α</em>는 Bob이 임의로 선택한 값이고, 이 값은 은닉을 통해 Alice에게 전달되기 때문에 Alice는 <em>α</em>값을 알지 못합니다.</p><p>아래는 프로토콜을 단계별로 그림을 첨부해 나타낸 것입니다. 좌측이 Alice이고 우측이 Bob이며, 서로 전달하는 값들은 중앙에 표시하였습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gnPKDa4qZZvsK8VJz4XkIg.png" /></figure><p>1. Alice는 임의의 c_0, …, c_d를 선택합니다. 이 값들은 다항식 P(X)를 구성하는데 사용하며, Bob이 알 수 없습니다. Bob은 임의의 <em>α</em>와 s를 선택합니다. 이 값들은 Alice가 알 수 없습니다. g는 서로 공유하는 값입니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kjPEIfbOcSQRYAV4t-f5Wg.png" /></figure><p>2. Bob이 Alice에게 <em>g, s</em>⋅<em>g, …, s^d</em>⋅<em>g</em>를 전달합니다. 이것은 곧 <em>(1, s, …, s^d)</em>를 은닉한 것입니다. 동시에 Bob은 <em>α</em>⋅<em>g, αs</em>⋅<em>g, …, αs^d</em>⋅<em>g</em> 또한 Alice에게 전달합니다. 이것은 곧 <em>(α, αs, …, αs^d)</em>를 은닉한 것입니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DYvxHYu8HdZDr2ovKL2tog.png" /></figure><p>3. Alice는 <em>a = E(P(s))</em>와 <em>b = αE(P(s))</em>를 계산합니다. 이것은 전 과정에서 Bob이 전달해준 정보를 사용해 아래와 같이 할 수 있습니다. 아래와 같이 계산한 <em>a, b</em>를 Bob에게 전달합니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*f3NLo7FtbeSo0Yo41EPuuQ.png" /></figure><p>4. Bob은 b = <em>α</em>⋅<em>a</em>를 계산해 올바른 <em>α-</em>pair인지 확인합니다.</p><p>위와 같은 프로토콜을 정리하면, <em>E(P(s))</em>는 <em>g, s⋅g, …, s^d⋅g</em>의 선형 결합이며, <em>αE(P(S))</em>는 <em>αg, αs⋅g, …, αs^d⋅g</em>의 선형 결합이라고 할 수 있습니다. 두 번째 글에서 보았던 것처럼 Alice는 다항식 <em>P</em>를 사용해 Bob의 메세지를 위와 같이 계산할 수 있습니다.</p><p>또한, d-KCA에 의해, Alice가 <em>b = α⋅a</em>인 <em>(a, b)</em>를 보낸다면, Alice가 아래 조건을 만족하는 <em>c_0, …, c_d</em>를 알고 있다고 거의 확신할 수 있습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/153/1*it91Aq5HFR3gR8lW_rPisg.png" /></figure><p>즉, Alice가 P를 모르는 경우에는 위 프로토콜의 4단계에 의해 Bob이 Alice의 증명을 받아들이지 않습니다.</p><p>지금까지의 포스팅에서 살펴본 것들은, ZCash 블로그에서 아래와 같이 나타낸 단계에서 Computation에 해당합니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/558/1*GANucGeaHGRoenHrwy9nBg.png" /></figure><p>다음 포스팅부터는 지금까지 학습했던 계산 방법이 zk-SNARKs를 구성하기 위해 어떻게 사용되는지 살펴볼 것입니다.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e914e4e55be5" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[zk-SNARKs 기초] 3. The Knowledge of Coefficient Test and Assumption]]></title>
            <link>https://medium.com/@seongjin.kim_68990/zk-snarks-%EA%B8%B0%EC%B4%88-3-the-knowledge-of-coefficient-test-and-assumption-1892c82341c1?source=rss-2b94ab58a269------2</link>
            <guid isPermaLink="false">https://medium.com/p/1892c82341c1</guid>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[zksnark]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Seongjin Kim]]></dc:creator>
            <pubDate>Sat, 16 Feb 2019 08:45:20 GMT</pubDate>
            <atom:updated>2019-02-16T08:49:07.123Z</atom:updated>
            <content:encoded><![CDATA[<blockquote>by Seongjin Kim, Core/Security Manager at ReturnValues (<a href="/service/mailto:seongjin.kim@returnvalues.com">seongjin.kim@returnvalues.com</a>)</blockquote><p><strong>[zk-SNARKs 기초] 시리즈<br></strong><a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-1-homomorphic-hiding-e8fd1de40bbd">1. Homomorphic Hiding</a><br><a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-2-blind-evaluation-of-polynomials-ed9e3cd11bc1">2. Blind Evaluation of Polynomials</a><br><a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-3-the-knowledge-of-coefficient-test-and-assumption-1892c82341c1">3. The Knowledge of Coefficient Test and Assumption</a><br><a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-4-how-to-make-blind-evaluation-of-polynomials-verifiable-e914e4e55be5">4. How to make Blind Evaluation of Polynomials Verifiable</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Feb78QK4tYZn4pIqsRxqXw.png" /></figure><p>이 글은 Zcash 블로그의 내용을 바탕으로 작성했으며, 번역 목적이 아닌 해설을 위해 작성되었기 때문에 내용의 추가와 요약이 있습니다. 원문은 아래 Zcash 블로그를 참고해주시기 바랍니다.<br><a href="https://z.cash/blog/snark-explain3">https://z.cash/blog/snark-explain3</a></p><p>미디엄의 수식 표현 한계로 인해 문장 속에 포함되는 수식을 아래와 같이 표현했습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/426/1*IhMiMO--MAn0072BHkjSVg.png" /></figure><h3>3. The Knowledge of Coefficient Test and Assumption</h3><p>전 포스팅에서 Bob이 임의로 선택한 <em>s</em>에 대해 Alice가 <em>d</em>차 다항식 <em>P</em>의 정보를 숨기고 <em>E(P(s))</em>를 계산하는 것을 살펴보았습니다. 이 때 Alice는 <em>s</em>값이 무엇인지 알 수 없기 때문에 이런 일련의 과정을 “blind” 계산이라고 합니다.</p><p>그런데 이 과정에 대해 언급되지 않은 부분이 있습니다. Alice가 <em>E(P(s))</em>를 계산할 수 있다는 점과 무관하게, Alice가 Bob에게 올바른 <em>E(P(s))</em>를 전달하리라는 보장이 되지 않습니다.</p><p>그러므로 Alice가 프로토콜을 정직하게 수행하도록 강제할 수 있는 방법이 필요합니다. 이 방법에 대해서는 다음 포스팅에서 자세히 살펴보고, 이번 포스팅에서는 그러한 방법에 필요한 <em>Knowledge of Coefficient (KC) Test</em>라고 하는 기본적인 것을 설명하는데 집중할 것입니다.</p><p>지금까지와 같이 우리는 <em>g</em>를 이산 대수 문제의 해결이 어려운 크기가 <em>p</em>인 군 <em>G</em>의 생성원(generator)으로 쓸 것입니다. 이 포스팅에서는 앞으로 편의를 위해 군의 연산을 곱셈 대신 덧셈을 사용할 것입니다. 즉, <em>F_p</em>의 원소 <em>α</em>에 대해서, <em>α</em>⋅<em>g</em>는 <em>α</em>를 <em>g</em>번 더한 것을 의미합니다.</p><h4>The KC Test</h4><p>앞으로 사용할 군 <em>F_p^*</em>는 <em>F_p</em>에서 <em>0</em>을 제외한 것과 같고, 첫 포스팅의 <em>Z_p^*</em>와 같습니다. 또한 <em>F_p^*</em>의 원소 <em>α</em>는 <em>G</em>의 원소 두 개를 <em>(a, b)</em> 쌍으로 하는 <em>α</em>-pair로써 만들어진다고 하겠습니다. 이 때, <em>a, b ≠ 0</em>이며 <em>b = α</em> ⋅<em>a</em> 입니다.</p><p>KC Test는 아래와 같이 진행됩니다.</p><p>1. Bob이 <em>F_p^*</em>에서 임의로 <em>α</em>를 선택하고, <em>G</em>에서 임의로 <em>a</em>를 선택합니다. 그 후 <em>b = α</em> ⋅<em>a</em>를 통해 <em>b</em>를 계산합니다.<br>2. Bob은 Alice에게 <em>(a, b)</em> 쌍을 보냅니다. 여기서 <em>(a, b)</em>는 전 과정에서 보았듯이 <em>α</em>-pair입니다.<br>3. Alice는 Bob이 전달한 것과 다른 <em>α</em>-pair를 만들어 응답해야 합니다. Alice가 생성할 <em>α</em>-pair를 <em>(a’, b’)</em>라고 하겠습니다. 이 때, Alice는 <em>α</em>를 모르는 상태에서 <em>α-pair</em>를 만듭니다. 이 과정은 뒤에서 자세히 살펴보겠습니다.<br>4. Bob은 Alice가 전달한 <em>(a’, b’)</em>가 <em>α</em>-pair 기준을 만족할 때만 Alice의 응답을 받아들입니다. 이것은 <em>b’ = α</em> ⋅<em>a’</em>를 계산하여 확인할 수 있습니다. Bob은 <em>α</em>를 알고 있기 때문에 확인이 가능합니다.</p><p>여기서 Alice가 어떻게 성공적으로 Bob의 challenge를 응답할 방법이 있을지 생각해봅시다. Alice가 Bob이 임의로 선택한 <em>α</em>를 안다고 가정해봅시다. 이 경우에 Alice는 <em>G </em>안에서 아무 값을 골라 <em>a’</em>로 선택하고 <em>b’ = α</em> ⋅<em>a’</em>를 계산하여 간단하게 <em>α</em>-pair를 만들 수 있습니다. 그리고 Alice는 자신이 만든 새로운 <em>α</em>-pair를 응답하면 됩니다.</p><p>그러나, Alice가 가진 <em>α</em>에 대한 유일한 정보는 Bob에게 받은 <em>α</em> ⋅<em>a(= b)</em>인데, <em>G</em>에서는 이산 대수 문제의 해결이 어렵기 때문에 Alice가 <em>α</em>를 알아낼 수 없습니다.</p><p>그러면 Alice는 어떻게 <em>α</em>를 알지 못한 상태에서 <em>α</em>-pair를 만들어 challenge에 대해 응답할 수 있을까요? 그 방법은 다음과 같습니다. Alice는 <em>F_p^*</em>의 원소 <em>γ</em>를 임의로 선택하고 <em>γ</em> ⋅<em>a</em>를 계산한 결과를 <em>a’</em>로 사용합니다. 이제 <em>b’</em>를 계산해야 하는데, <em>α</em>-pair 조건을 만족하려면 <em>b’</em>는 <em>α</em> ⋅<em>a’</em>와 같아야 합니다. 이 때, <em>α</em>를 모르는 상황에서 <em>b’</em>를 구하는 방법은 다음과 같습니다. 이 과정에서 Bob이 전달해준 <em>b</em>가 <em>α</em> ⋅<em>a</em>와 같다는 점을 이용합니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/335/1*xXhD6JMTd77fodhIWWOyCw.png" /></figure><p>위와 같이 <em>b’</em>를 계산하면 Alice가 만든 <em>(a’, b’)</em> 쌍은 <em>α</em>-pair 기준을 만족하게 됩니다.</p><p>여기서 기억해야 할 특징은, Alice가 이런 방법으로 응답한다면, Alice는 <em>a’ = γ</em> ⋅<em>a</em>를 통해 <em>a’</em>를 만들었기 때문에, <em>a</em>와 <em>a’</em>의 비율을 알고 있고, 이는 곧 <em>a’ = γ</em> ⋅<em>a</em>에서 계수 <em>γ</em>를 알고 있다는 점입니다. 이 계수는 전 포스팅에서 Alice가 다항식 <em>P</em>의 일부인 <em>a_0, …, a_d</em>를 Bob에게 알리지 않고 사용했던 것처럼 다음 포스팅에서 활용될 것입니다.</p><p><em>Knowledge of Coefficient Assumption(KCA)</em>은 다음과 같이 기술하고 있습니다. KCA는 일반적으로 <em>Knowledge of Exponent Assumption(KEA)</em>라고도 불립니다.</p><p>KCA : Bob의 <em>(a, b)</em> challenge에 대해 Alice가 올바른 <em>(a’, b’)</em>를 만든다면, Alice는 <em>a’ = γ</em> ⋅<em>a</em>를 통해 <em>γ</em>를 알게 됩니다.</p><p>이러한 KC Test와 가정은 다음 포스팅에서 중요한 도구로 쓰일 것입니다.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1892c82341c1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[zk-SNARKs 기초] 2. Blind Evaluation of Polynomials]]></title>
            <link>https://medium.com/@seongjin.kim_68990/zk-snarks-%EA%B8%B0%EC%B4%88-2-blind-evaluation-of-polynomials-ed9e3cd11bc1?source=rss-2b94ab58a269------2</link>
            <guid isPermaLink="false">https://medium.com/p/ed9e3cd11bc1</guid>
            <category><![CDATA[zksnark]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[cryptography]]></category>
            <dc:creator><![CDATA[Seongjin Kim]]></dc:creator>
            <pubDate>Wed, 13 Feb 2019 05:34:54 GMT</pubDate>
            <atom:updated>2019-02-16T08:48:52.222Z</atom:updated>
            <content:encoded><![CDATA[<blockquote>by Seongjin Kim, Core/Security Manager at ReturnValues (<a href="/service/mailto:seongjin.kim@returnvalues.com">seongjin.kim@returnvalues.com</a>)</blockquote><p><strong>[zk-SNARKs 기초] 시리즈<br></strong><a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-1-homomorphic-hiding-e8fd1de40bbd">1. Homomorphic Hiding</a><br><a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-2-blind-evaluation-of-polynomials-ed9e3cd11bc1">2. Blind Evaluation of Polynomials</a><br><a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-3-the-knowledge-of-coefficient-test-and-assumption-1892c82341c1">3. The Knowledge of Coefficient Test and Assumption</a><br><a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-4-how-to-make-blind-evaluation-of-polynomials-verifiable-e914e4e55be5">4. How to make Blind Evaluation of Polynomials Verifiable</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Feb78QK4tYZn4pIqsRxqXw.png" /></figure><p>이 글은 Zcash 블로그의 내용을 바탕으로 작성했으며, 번역 목적이 아닌 해설을 위해 작성되었기 때문에 내용의 추가와 요약이 있습니다. 원문은 아래 Zcash 블로그를 참고해주시기 바랍니다.<br><a href="https://z.cash/blog/snark-explain2">https://z.cash/blog/snark-explain2</a></p><p>미디엄의 수식 표현 한계로 인해 문장 속에 포함되는 수식을 아래와 같이 표현했습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/401/1*WCV9qSsbSKWm8KQOf2BsDg.png" /></figure><h3>2. Blind Evaluation of Polynomials</h3><p>이번 글에서는 다항식에 대해 살펴보면서 다항식의 blind evaluation에 대해 설명하고, 이것이 어떻게 Homomorphic Hiding(이하 HH)을 사용하면서 구현되는지 설명하겠습니다. 앞으로의 포스팅에서 blind evaluation이 SNARK의 가장 중요한 도구라는 것을 볼 것입니다.</p><p>우리는 <em>p</em> 크기만한 체(field)를 <em>𝔽_p</em>라고 정의합니다. 즉, <em>𝔽_p</em>의 원소들은 <em>{0,…,p - 1}</em>이고, 이전 포스팅에서 보았던 것처럼 <em>mod p</em>를 사용한 덧셈과 곱셈 연산을 지원합니다.</p><blockquote><strong>체</strong><br>사칙연산이 자유롭고, 일반적인 산술 연산의 규칙들을 만족하는 집합입니다.</blockquote><h4>다항식과 선형 결합</h4><p><em>𝔽_p</em>를 떠나서, <em>d</em>차 다항식 <em>P</em>가 다음과 같이 표현될 수 있다는 점을 떠올려봅시다. 이 때, <em>a_0, …, a_d</em>는 <em>𝔽_p</em>의 원소입니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/830/1*Tr1dVnLML-rjCF5MD3gHZg.png" /></figure><p>이와 같은 다항식에서 <em>X</em> 대신 <em>𝔽_p</em>의 원소 <em>s</em>를 사용하면, 다항식 <em>P</em>는 다음과 같이 계산될 수 있습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/757/1*SethzrAhB5kNK31Y9pYMWg.png" /></figure><p><em>P(s)</em> 값은 <em>a_0, …, a_d</em>를 가중치로 둔 <em>1, s, …, s^d</em>의 선형 결합임을 볼 수 있습니다.</p><p>이전 포스팅에서 우리는 생성원 <em>g</em>를 사용한 HH 함수 <em>E</em>를 <em>E(x) = g^x</em>라고 정의하고, 이산 대수 문제가 어렵다는 점을 사용한 것을 보았습니다. 또한, HH는 덧셈을 지원하기 때문에 <em>E(x)</em>, <em>E(y)</em> 값이 주어졌을 때 <em>E(x + y)</em>를 계산할 수 있다는 점을 보았습니다. 이제 이런 특징들을 사용해서 선형 결합 또한 지원한다는 점을 살펴보겠습니다. 즉, <em>a, b, E(x), E(y)</em>가 주어졌을 때 우리는 <em>E(ax + by)</em>를 계산할 수 있습니다. 이것을 수식으로 풀어보자면 다음과 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PhkD6S43eZegstIEGWoxdg.png" /></figure><blockquote>g^ax가 (g^x)^a로 되는 것 역시 지수 법칙에 의한 것인데, 아래와 같이 유도할 수 있습니다.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/232/1*EAnWseFyEeOiel7mQ5hzkg.png" /></figure><h4>다항식의 Blind evaluation</h4><p>Alice에게 <em>d</em>차 다항식 <em>P</em>가 있고, Bob은 <em>F_p</em>의 원소 <em>s</em>를 임의로 선택해 갖고 있을 때, Bob이 <em>E(P(s))</em>를 알고싶어하는 상황을 가정하겠습니다. <em>E(P(s))</em>는 곧 <em>s</em>를 다항식에 대입한 것의 HH입니다. Alice와 Bob이 서로 모든 정보를 공개한다면, 다음과 같은 두 가지 방법으로 간단히 할 수 있습니다.</p><p>* Alice가 Bob에게 다항식 <em>P</em>를 전달하고, Bob은 <em>E(P(s))</em>를 계산합니다.<br>* Bob이 <em>s</em>를 Alice에게 전달해서, Alice가 <em>E(P(s))</em>를 계산해서 알려주기를 기대합니다.</p><p>그러나 우리는 Bob이 다항식 <em>P</em>를 모르게 하는 동시에, Alice 또한 <em>s</em>를 모르게 하는 Blind evaluation 문제를 살펴보겠습니다.</p><p>1. Bob이 <em>E(1), E(s),…, E(s^d)</em>를 계산해 Alice에게 전달합니다.<br>2. Alice는 Bob이 전달해준 정보로부터 <em>E(P(s))</em>를 계산해 Bob에게 전달합니다.</p><p>위와 같은 방법으로 Alice와 Bob이 각자 가지고 있는 정보를 알리지 않고 원하는 결과를 얻을 수 있습니다. Alice가 계산해야하는 <em>E(P(s))</em>를 풀어서 써보면 다음과 같습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/549/1*J9lZBnv8SF8qEn8JnuyYvQ.png" /></figure><p>여기서 Alice는 다항식 <em>P</em>를 알고 있기 때문에 이미 <em>a_0, …, a_d </em>값을 알고 있습니다. 따라서, Alice가 <em>E(P(s))</em>를 계산하기 위해서 Bob에게 <em>s</em>를 전달 받는 대신, <em>E(1), E(s),…, E(s^d)</em>를 전달 받는 것으로 계산이 가능합니다. 또한 Alice는 Bob에게 전달 받은 정보들로부터 <em>s</em> 값을 알아낼 수 없습니다.</p><h4>왜 유용한가?</h4><p>이어지는 포스팅들에서는 blind evaluation이 SNARKs 안에서 어떻게 쓰이는지 상세히 살펴볼 것입니다. 살짝 이야기해보자면, 검증자는 증명자가 올바른 다항식을 알고 있는지 확인하고 싶어합니다. 증명자가 알지 못하는 s값에 대해 다항식을 풀도록 검증자가 유도할 때, 증명자가 잘못된 다항식을 가지고 있다면 검증자가 원하는 올바른 답을 전달하지 못할 것입니다. 이것은 즉, “서로 다른 다항식은 대부분의 점에서 다르다”라는 Schwartz-Zippel Lemma와도 같습니다.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ed9e3cd11bc1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[zk-SNARKs 기초] 1. Homomorphic Hiding]]></title>
            <link>https://medium.com/@seongjin.kim_68990/zk-snarks-%EA%B8%B0%EC%B4%88-1-homomorphic-hiding-e8fd1de40bbd?source=rss-2b94ab58a269------2</link>
            <guid isPermaLink="false">https://medium.com/p/e8fd1de40bbd</guid>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[zksnark]]></category>
            <category><![CDATA[cryptography]]></category>
            <dc:creator><![CDATA[Seongjin Kim]]></dc:creator>
            <pubDate>Wed, 13 Feb 2019 05:33:48 GMT</pubDate>
            <atom:updated>2019-02-16T08:48:39.591Z</atom:updated>
            <content:encoded><![CDATA[<blockquote>by Seongjin Kim, Core/Security Manager at ReturnValues (<a href="/service/mailto:seongjin.kim@returnvalues.com">seongjin.kim@returnvalues.com</a>)</blockquote><p><strong>[zk-SNARKs 기초] 시리즈<br></strong><a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-1-homomorphic-hiding-e8fd1de40bbd">1. Homomorphic Hiding</a><br><a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-2-blind-evaluation-of-polynomials-ed9e3cd11bc1">2. Blind Evaluation of Polynomials</a><br><a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-3-the-knowledge-of-coefficient-test-and-assumption-1892c82341c1">3. The Knowledge of Coefficient Test and Assumption</a><br><a href="https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-4-how-to-make-blind-evaluation-of-polynomials-verifiable-e914e4e55be5">4. How to make Blind Evaluation of Polynomials Verifiable</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Feb78QK4tYZn4pIqsRxqXw.png" /></figure><p>이 글은 Zcash 블로그의 내용을 바탕으로 작성했으며, 번역 목적이 아닌 해설을 위해 작성되었기 때문에 내용의 추가와 요약이 있습니다. 원문은 아래 Zcash 블로그를 참고해주시기 바랍니다.<br><a href="https://z.cash/blog/snark-explain">https://z.cash/blog/snark-explain</a></p><p>미디엄의 수식 표현 한계로 인해 문장 속에 포함되는 수식을 아래와 같이 표현했습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/402/1*yQY-1fLA9oIL79SQJBEFDg.png" /></figure><h3>1. Homomorphic Hidings</h3><p>zk-SNARKs의 모든 요소들을 완전히 이해하는 것은 꽤 오래 걸릴 수 있기 때문에, Zcash 블로그에서는 여러 요소들 중 가장 중요한 한 가지로 “Homomorphic Hiding(이하 HH)”를 고르며 먼저 설명하고 있습니다.</p><p>함수 <em>E(x)</em>가 HH 함수라고 할 때 아래 조건들을 만족합니다.</p><p>* 대부분의 <em>x</em>에 대해, <em>E(x)</em> 값이 주어졌을 때 <em>x</em>를 알아내기 어렵습니다.<br>* 입력값이 달라지면 출력값도 달라집니다. 따 라서, <em>x ≠ y</em>일 때, <em>E(x) ≠ E(y)</em> 입니다.<br>* <em>E(x)</em>와 <em>E(y)</em>를 안다면, <em>x</em>와 <em>y</em>를 연산한 HH를 만들 수 있습니다. 예를 들어, <em>E(x)</em>와 <em>E(y)</em>로부터 <em>E(x + y)</em>를 계산할 수 있습니다.</p><p>아래는 HH 함수가 위 특징들을 만족할 때 왜 영지식 증명에서 유용한지를 보여주는 예제입니다.</p><p>Alice는 자신이 <em>x + y = 7</em>을 만족하는 <em>x</em>, <em>y</em>값을 알고있다는 사실을 Bob에게 증명하고 싶어합니다. 이 때, Bob은 <em>x</em>, <em>y</em>가 어떤 값인지 알 수 없어야 합니다.<br>1. Alice는 <em>E(x)</em>와 <em>E(y)</em>를 Bob에게 알립니다.<br>2. Bob은 전달 받은 <em>E(x), E(y)</em>로부터 <em>E(x + y)</em>를 계산합니다(이것은 위에서 살펴본 HH의 특징때문에 가능합니다).<br>3. Bob은 <em>E(7)</em>을 계산하고, <em>E(x + y)</em>와 <em>E(7)</em>이 일치하는지 확인합니다. 이 값이 같을 때 Alice의 증명을 받아들입니다.</p><p>이 과정에서 Bob은 <em>x</em>와 <em>y</em>가 정확히 어떤 값인지는 알아내지 못하지만, <em>x + y = 7</em>을 만족하는 <em>x</em>와 <em>y</em>가 <em>E</em>에 사용됨으로써 Alice의 증명을 받아들일 수 있습니다. 물론 이 예제는 엄밀히 따지자면 Bob이 아무 값이나 <em>E</em>에 대입해서 <em>x</em>값을 구해볼 수 있는 등 영지식 증명이라고 할 수는 없습니다.</p><p>이제 아래에서는 위와 같은 은닉이 어떻게 이루어지는지 살펴봅니다. 이 때, 일반적인 정수의 덧셈 연산을 통해서는 할 수 없기 때문에 유한군내에서 덧셈 연산을 정의해 사용합니다.</p><blockquote><strong>유한군</strong><br>유한개의 원소를 갖는 군입니다. 여기서는 mod 연산을 사용해 최대값을 두어 원소의 갯수를 유한개로 제한합니다.<br>군은 일련의 연산에 대한 항등원과 역원이 존재하는 등의 조건을 만족하는 집합입니다.</blockquote><p>임의의 정수 <em>n</em>이 있을 때, <em>A mod n</em>은 <em>A</em>를 <em>n</em>으로 나누고 남은 나머지를 의미합니다. 예를 들어, <em>9 mod 7</em>은 <em>2</em>이고, <em>13 mod 12</em>는 <em>1</em>입니다. <em>mod n</em>의 결과는 항상 <em>0</em> 이상이고 <em>n - 1</em> 이하이기 때문에, 우리는 이러한 <em>mod n</em> 연산을 <em>{0,…,n - 1}</em> 집합 내에서 덧셈 연산을 정의하기 위해 사용할 수 있습니다. 일반적인 덧셈 연산을 한 뒤 <em>mod n</em>을 취하면 그 결과값은 항상 <em>{0,…,n - 1}</em> 내에 포함됩니다. 이런 유형의 덧셈을 사용하고 있다는 것을 명확히 하기 위해 오른쪽에 <em>(mod n)</em>을 쓰기도 합니다. 예를 들어, <em>2 + 3 = 1(mod 4)</em> 와 같이 표현할 수 있습니다. 이러한 덧셈 연산을 정의한 집합 <em>{0,…,n - 1}</em>을 ℤ_<em>n</em>이라고 하겠습니다.</p><p><em>p</em>가 소수일 때, <em>{1,…,p - 1}</em> 집합 안에서 이루어지는 곱셈 연산을 정의하기 위해 <em>mod p</em> 연산을 사용할 수 있습니다. <em>{1,…,p - 1}</em> 집합 내의 원소들끼리 곱한 값에 <em>mod p</em>를 취하면 그 결과도 항상 <em>{1,…,p - 1}</em> 내에 존재합니다. 예를 들어, <em>2 * 4 = 1(mod 7)</em> 입니다. 곱셈 연산의 집합에 <em>0</em>이 포함되지 않는 이유와 <em>mod</em> 연산에 소수를 사용하는 이유는 모두 집합을 군으로 만들기 위함입니다. 군 내의 곱셈 연산에는 항등원과 역원이 존재해야 하는데, <em>0</em>이 집합에 포함되면 군의 조건을 만족하지 못합니다.</p><p>위와 같이 곱셈 연산을 정의한 집합을 ℤ_p^*라고 합니다. ℤ_p^*는 아래와 같은 성질을 지니고 있습니다.<br>1. ℤ_p^*는 순환군입니다. 따라서 생성원(generator)이라고 부르는 어떤 <em>g</em>가 ℤ_p^*의 원소일 때, ℤ_p^*의 모든 원소들은 <em>g^a</em>로 표현할 수 있습니다. 이 때, <em>a</em>는 <em>{0,…,p - 2}</em>의 원소이며 <em>g⁰=1 입니다</em>. 이런 특징들을 설명하기 위해 예제를 보겠습니다. <em>p = 13</em>, <em>g = 7</em>인 ℤ_p^*가 있을 때, <em>a</em>의 변화에 따라 <em>g^a</em>는 아래와 같이 변합니다. ℤ_p^*에서의 연산은 <em>mod p</em>를 포함하기 때문에, 아래 표의 <em>g^a</em>는 <em>g</em>의 <em>a</em>제곱에 <em>mod p</em>를 취한 것입니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*UQoE0YibN8ORf3vYVVr50w.png" /></figure><p>위를 살펴보면 <em>a</em>의 최대값이 <em>p - 2</em>가 된 이유를 찾을 수 있습니다. <em>mod 13</em>에 대한 <em>7⁰</em>과 <em>7¹²</em>는 <em>1</em>로 같고 그 뒤로 <em>a</em>값이 변할 때마다 <em>g^a</em> 값은 같은 값이 반복되기 때문에, 이 예시의 ℤ_p^*는 <em>7⁰</em>부터 <em>7¹¹</em>를 원소로 갖는 순환군이라고 볼 수 있습니다. 따라서 이 순환군의 <em>a</em>는 <em>0</em>부터 <em>11(p - 2)</em>까지로 나타낼 수 있습니다.</p><p>2. ℤ_p^* 안에서의 이산 대수 문제는 해결이 충분히 어렵다고 여겨집니다. 즉, <em>p</em>가 충분히 큰 값이고 ℤ_p^*의 원소 <em>g</em>와 <em>h</em> 값이 주어졌을 때, <em>g^a = h(mod p)</em>를 만족하는 <em>a</em>값을 <em>0,…,p - 2</em> 내에서 찾기 어렵습니다.</p><blockquote><strong>이산 대수 문제</strong><br>a^x=b에서 a와 b가 주어졌을 때 x를 찾는 문제이며, 지수적 복잡도를 가지고 있기 때문에 해결이 어렵다고 알려져 있습니다.</blockquote><p>3. 지수법칙에 따라, <em>a</em>, <em>b</em>가 <em>0,…,p - 2</em> 중에 있을 때 아래 식을 만족합니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/410/1*JXFlxPCf9FZVdjTsuIJ0Fg.png" /></figure><p>일반적인 정수의 지수법칙에서는 <em>(g^a)*(g^b)=g^(a+b)</em>가 옳다는 것이 당연한데, 이 식에서 <em>mod (p - 1)</em>이 사용된 이유는 위에서 보았던 것처럼, 지수로 쓰이는 <em>a</em>의 범위가 <em>0</em>부터 <em>p - 2</em>까지이기 때문입니다. 예를 들어, <em>13¹⁴ = 13^(14 mod 12) = 13²</em> 입니다. 즉, <em>g^a mod p</em>에서 <em>a</em>가 <em>p - 1</em> 이상일 경우 <em>g^a = g^(a mod (p - 1)) mod p</em>이기 때문에 위 식에서 <em>mod (p - 1)</em>이 사용되었습니다. 정리하면, 거듭제곱의 곱으로 인한 지수의 덧셈이 성립합니다.</p><p>이런 특징들을 사용해 덧셈을 지원하는 HH를 구성할 수 있습니다. 즉, <em>E(x)</em>와 <em>E(y)</em>로부터 <em>E(x+y)</em>를 계산할 수 있습니다. <em>E</em>의 입력값 <em>x</em>를 ℤ_<em>(p-1)</em>로 가정하면(<em>x</em>가 지수로 사용되기 때문에 ℤ_p가 아닌 ℤ_(<em>p - 1</em>)입니다), 그 범위는 <em>{0,…,p - 2}</em>가 됩니다. 그런 모든 <em>x</em>에 대한 HH 함수를 <em>E(x) = g^x</em>라고 하면 위에서 보았던 특징들을 다음과 같이 정리할 수 있습니다. <br>1. 입력값 <em>x</em>가 달라지면 결과값은 ℤ_(<em>p - 1</em>)의 다른 원소가 됩니다.<br>2. <em>E(x)=g^x</em>에서 <em>E(x)</em>, <em>g</em>값이 주어졌을 때 <em>x</em>값을 찾기는 어렵습니다.<br>3. <em>E(x)</em>와 <em>E(y)</em>가 주어졌을 때 다음과 같이 <em>E(x+y)</em>를 계산할 수 있습니다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/882/1*-BqjgegoY9tzLhNO86TORw.png" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e8fd1de40bbd" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>