<?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 jun on Medium]]></title>
        <description><![CDATA[Stories by jun on Medium]]></description>
        <link>https://medium.com/@jun-lee?source=rss-1f434c4cb7d8------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*K1pKbE1Jt8abGq-7MFjo6Q.jpeg</url>
            <title>Stories by jun on Medium</title>
            <link>https://medium.com/@jun-lee?source=rss-1f434c4cb7d8------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 18:15:00 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@jun-lee/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[VOLE Based Zero Knowledge Proof]]></title>
            <link>https://medium.com/4hours/vole-based-zero-knowledge-proof-7f15ff2245f3?source=rss-1f434c4cb7d8------2</link>
            <guid isPermaLink="false">https://medium.com/p/7f15ff2245f3</guid>
            <category><![CDATA[vole-zk]]></category>
            <category><![CDATA[vole-based-zk]]></category>
            <category><![CDATA[quicksilver]]></category>
            <category><![CDATA[vole-in-the-head]]></category>
            <category><![CDATA[love]]></category>
            <dc:creator><![CDATA[jun]]></dc:creator>
            <pubDate>Sun, 06 Apr 2025 15:44:51 GMT</pubDate>
            <atom:updated>2025-04-06T15:57:47.936Z</atom:updated>
            <content:encoded><![CDATA[<p>This is the second post in a series of VOLE-in-the-Head articles from the 4Hours Lab. Check out the rest of the posts in catalogue:</p><p><a href="https://medium.com/4hours/unveiling-vole-in-the-head-a-new-era-in-vole-based-zk-7cc821c9e1f0"><strong>Unveiling VOLE-in-the-Head: A New Era in VOLE-ZK</strong></a></p><h4>Introduction</h4><p>Zero-knowledge proofs (ZKPs) have become a fundamental building block in modern cryptography, enabling one party to prove to another that a statement is true without revealing any additional information. Among various approaches to constructing ZKPs, Vector Oblivious Linear Evaluation (short for <strong><em>Vector-OLE</em></strong> or <strong><em>VOLE</em></strong>) based proofs have emerged as an efficient alternative to traditional methods like SNARKs or STARKs. This article explores the concept of Vector-OLE based zero-knowledge proofs(<strong><em>VOLE-ZK</em></strong> for short) and examines its implementation in QuickSilver, a recent protocol that demonstrates practical applications of this approach.</p><h4>The Basics of Vector-OLE</h4><p>A VOLE correlation is a pair of random variables <strong>(<em>w</em>,<em>m</em>)</strong> and <strong>(<em>k</em>,∆)</strong>, where <strong>w</strong>,<strong>m</strong>,<strong>k</strong> are vectors and ∆ is a scalar, which are all random subject to the constraint that: <strong><em>m = k — w*</em>∆<em>, </em></strong>the prover <strong>P</strong> is given <strong><em>(m, w)</em></strong>, while the verifier <strong>V</strong> learns <strong><em>(k</em>, ∆<em>)</em></strong>.</p><p>We model the generation of <strong><em>VOLE</em></strong> correlations as an ideal functionality FVOLE, given in Figure 1.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cI6QRSqcfZRoVRN2OWGT3w.jpeg" /><figcaption>1. Functionality of VOLE</figcaption></figure><h4>QuickSilver Implementation</h4><p>QuickSilver is a recent zero-knowledge proof (ZKP) protocol that leverages <strong>Vector Oblivious Linear Evaluation (VOLE)</strong> to achieve efficient proofs for arithmetic and boolean circuits. The protocol can also be viewed as a <strong>sigma protocol</strong> (a three-move interactive proof system) consisting of:</p><ol><li><strong>Commit Phase</strong> (VOLE setup),</li><li><strong>Challenge Phase</strong> (verifier sends randomness),</li><li><strong>Open Phase</strong> (prover generates and sends proof, verifier checks).</li></ol><p>Below, as show in Figure 2, we break down each phase and explain how QuickSilver uses VOLE for efficient proofs:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Ia3LpSOC-PcJXmqsGZiEyg.jpeg" /><figcaption>2. Sigma Protocol view of QuickSilver</figcaption></figure><ol><li><strong>Commit Phase</strong></li></ol><ul><li>The prover (P) and verifier (V) interactively run the <strong>VOLE </strong>functionality, resulting in:<br>-<strong> Prover’s output</strong>: Two vectors (<strong><em>m,w</em></strong>)of length n(where n is the number of gates in the circuit).<br>- <strong>Verifier’s output</strong>: A vector <strong><em>K</em></strong> and a global secret <strong>∆ </strong>(delta).</li><li>This phase establishes a correlation between the prover and verifier such that: <strong><em>m=k+w⋅Δ, </em></strong>This ensures that the prover and verifier share structured randomness that will later be used for proof generation and verification.</li></ul><p>2.<strong> Challenge Phase</strong></p><ul><li>Verifier sends random challenges <strong><em>Xi</em></strong>(i ∈ {0,1,…,n-1}), where n is gate numbers.</li><li>The prover then <strong>evaluates the circuit</strong> using these challenges and the VOLE correlations, for each gate <em>i</em>, the prover computes: <br>- <strong><em>M</em></strong> = <strong><em>Σ</em></strong>(<strong><em>mi</em> * <em>Xi</em>) </strong>(sum over all gates)<strong><br>- <em>W</em></strong> = <em>Σ</em>(<strong><em>wi</em> * <em>Xi</em>).</strong></li><li>Here, <strong><em>wi</em></strong> encodes the witness, while <strong><em>mi</em></strong> is a masked version of it or <strong><em>IT-MAC</em></strong> of it.</li></ul><p>3. <strong>Open Phase</strong></p><ul><li>Prover sends (<strong><em>M</em></strong><em>,</em><strong><em>W) </em></strong>tuple as proof<strong><em> </em></strong>to verifier.</li><li>Verifier checks <strong><em>M</em></strong> ?= <strong><em>Σ</em></strong>(<strong><em>ki</em> * <em>Xi</em>) + <em>W*</em>∆, </strong>If the equation holds, the verifier accepts the proof; otherwise it rejects.</li></ul><p>We provide a high-level overview of QuickSilver. For readers interested in deeper technical details, Chainlink Labs Research offers an excellent resource about <a href="http://blog.chain.link/vole-based-zk">VOLE-based ZKPs</a>.</p><h4>Can We Make QuickSilver Non-Interactive?</h4><p>We have learned that the <strong>fiat-shamir transform</strong> is a powerful tool for converting <strong>interactive sigma protocols</strong> into <strong>non-interactive zero-knowledge proofs (NIZKs)</strong>.</p><p>If somehow we can apply the fiat-shamir transform to quicksilver then it can be converted into non-interactive protocol as shown in Figure 3.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ofPCpnwQe1z9lW1SQFxJuw.jpeg" /><figcaption>3. Non-Interactive QuickSilver</figcaption></figure><p>However applying fiat-sharmir transform to QuickSilver faces a key challenge: its <strong>Commit Phase (VOLE setup) is inherently interactive.</strong></p><p><strong>QuickSilver’s Commit Phase consists of 3 interactive steps (Figure 4):</strong></p><ul><li><strong>Step 1</strong>: The prover and verifier run the <strong><em>IKNP</em> <em>extension</em></strong> (based on oblivious transfer) to generate a small number of seed <strong><em>VOLE</em></strong> correlations.</li><li><strong>Step 2</strong>: Two parties use a <strong><em>GGM Tree-based</em></strong> <strong><em>PCG</em></strong>( pseudorandom correlated generator) to generate a large number of <strong><em>VOLE</em></strong> correlations with sparse vector <strong>e</strong>.</li><li><strong>Step 3</strong>: Two parties then compute a linear transformation (using matrix <strong>A</strong>) to derive the final <strong><em>VOLE</em></strong> correlations under <strong><em>LPN</em></strong> assumption.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4EPWBPwt_7GV0Embo543ag.jpeg" /><figcaption>4. Construct QuickSilver under LPN assumption</figcaption></figure><p><strong>⇒ The entire Commit Phase is interactive, preventing a straightforward Fiat-Shamir application.</strong></p><p>At first glance, the situation appears hopeless — the interactive nature of QuickSilver’s VOLE setup seems to present an insurmountable barrier to achieving full non-interactivity. However, this challenge is not insurmountable. The solution lies in two powerful cryptographic primitives that will serve as our key tools:</p><ol><li><strong>SoftSpokenOT</strong>: A next-generation oblivious transfer protocol that eliminates interaction requirements</li><li><strong>Tree Vector Commitments</strong>: An advanced commitment scheme enabling efficient non-interactive verification</li></ol><p>Together, these innovations will allow us to transform interactive OT operations into their non-interactive counterparts. In our upcoming technical deep dive, we will:</p><ul><li>Provide a comprehensive introduction to both tools</li><li>Demonstrate their application in cryptographic protocols</li><li>Present a complete framework for converting VOLE-based ZKPs into fully non-interactive proofs</li></ul><h4><strong>Further Reading:</strong></h4><ul><li><a href="https://eprint.iacr.org/2019/448">Pseudorandom Correlated Generator</a></li><li><a href="https://blog.chain.link/vole-based-zk/">Chainlink Labs VOLE-Based ZK</a></li><li><a href="https://blog.chain.link/realizing-vole/">Chainlink Labs Realizing VOLE</a></li><li><a href="https://blog.chain.link/realizing-spvole/">Chainlink Labs Realizing SPVOLE</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7f15ff2245f3" width="1" height="1" alt=""><hr><p><a href="https://medium.com/4hours/vole-based-zero-knowledge-proof-7f15ff2245f3">VOLE Based Zero Knowledge Proof</a> was originally published in <a href="https://medium.com/4hours">4hours</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Fiat-Shamir Transform]]></title>
            <link>https://medium.com/4hours/fiat-shamir-transform-769e4f9f4112?source=rss-1f434c4cb7d8------2</link>
            <guid isPermaLink="false">https://medium.com/p/769e4f9f4112</guid>
            <category><![CDATA[schnorr-protocol]]></category>
            <category><![CDATA[fiat-shamir-heuristic]]></category>
            <category><![CDATA[non-interactive]]></category>
            <category><![CDATA[sigma-protocol]]></category>
            <category><![CDATA[fiat-shamir-transform]]></category>
            <dc:creator><![CDATA[jun]]></dc:creator>
            <pubDate>Sat, 05 Apr 2025 14:13:25 GMT</pubDate>
            <atom:updated>2025-04-06T15:46:32.564Z</atom:updated>
            <content:encoded><![CDATA[<p>This is the first post in a series of VOLE-in-the-Head articles from the 4Hours Lab. Check out the rest of the posts in catalogue:</p><p><a href="https://medium.com/4hours/unveiling-vole-in-the-head-a-new-era-in-vole-based-zk-7cc821c9e1f0"><strong>Unveiling VOLE-in-the-Head: A New Era in VOLE-ZK</strong></a></p><h4>Introduction</h4><p>The technique of using a hash function to convert an interactive proof system into a non-interactive one is known as the <strong>Fiat-Shamir Transform</strong>. It was introduced in 1986 by cryptography pioneers <strong>Amos Fiat</strong> and <strong>Adi Shamir</strong>.</p><p>The <strong>Fiat-Shamir Transform</strong>, also referred to as the <strong>Fiat-Shamir Heuristic</strong> or <strong>Fiat-Shamir Paradigm</strong>, is a foundational method in cryptographic protocols. Proposed by Fiat and Shamir in their seminal 1986 paper, this approach enables the transform of <strong>interactive zero-knowledge proofs (IZK)</strong> into <strong>non-interactive zero-knowledge proofs (NIZK)</strong>.</p><h4>Schnorr Protcol</h4><p>The <strong>Schnorr protocol</strong> is a well-known example of a <strong>Sigma protocol</strong> (Σ-protocol), a three-phase interactive proof system where a prover convinces a verifier of knowledge of a secret without revealing it. In this case, the prover aims to prove knowledge of a point on an elliptic curve without disclosing the point itself.</p><p>Suppose a prover wants to demonstrate knowledge of a point <strong>a</strong> on an elliptic curve <strong>E</strong>, where:</p><ul><li><strong>PK = a*G</strong> (where <strong>G</strong> is a generator of the elliptic curve group, and <strong>a</strong> is a secret scalar, <strong>sk=a</strong>).</li><li>The prover must convince the verifier that she knows <strong>a</strong> <strong>without revealing a</strong>.</li></ul><p>We describe the <strong>schnorr protocol</strong> workflow in figure 1:</p><ol><li><strong>Commit Phase</strong></li></ol><ul><li>The prover selects a random scalar <strong>r</strong> and computes <strong>R = r*G</strong>.</li><li>Prover sends <strong>R</strong> (the <em>commitment</em>) and <strong>PK</strong> to the verifier.</li></ul><p><strong>2. Challenge Phase</strong></p><ul><li>The verifier picks a random challene scalar <strong>c</strong> and sends it to the prover.</li></ul><p><strong>3. Open Phase</strong></p><ul><li>The prover computes <strong>z = r + c*sk</strong> (using her secret <strong>sk=a</strong>).</li><li>Prover sends <strong>z</strong> back to the verifier.</li><li>The verifier checks whether:<strong> z * G == R + c * PK</strong></li><li>If the equation holds, the verifier accepts the proof; otherwise it rejects.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tCxAShcrIXAD3O_293RaGQ.jpeg" /><figcaption><strong>1. Execution of Schnorr Protocol</strong></figcaption></figure><h4>Why this works?</h4><ul><li><strong>Completeness</strong>: If the prover knows <strong>a</strong>, she can always compute a valid <strong>z</strong> that satisfies the verification equation.</li><li><strong>Soundness</strong>: A cheating prover who does not know <strong>a</strong> cannot forge a valid <strong>z</strong> except with negligible probability.</li><li><strong>Zero-Knowledge</strong>: The verifier learns nothing about <strong>a</strong> beyond the fact that the prover knows it.</li></ul><h4>Why verifier need challenge prover?</h4><p>If prover has some magic ability that she knows the challenge <strong>c</strong> before commit phase, the schnorr protocol becomes completely insecure.</p><p>As describe in Figure 2, if the fake prover knows challenge <strong>c</strong> in advance, so the fake prover can predicts the <strong>z </strong>without need to know private key <strong>a</strong>, the fake prover computes <strong>R’ = z*G - c*PK </strong>and sends the <strong>R’</strong> and <strong>PK</strong> to verifier, then verifier sends challenge <strong>c</strong> to prover, then prover send <strong>z</strong> to verifier, and then verifier checks if <strong>z * G == R’ + c * PK </strong>holds. It’s obvious that the equation holds and thus the <strong>soundness failed</strong>!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZpiY-5oX_CDZ12U_2C822w.jpeg" /><figcaption><strong>2. Cheated Schnorr Protocol</strong></figcaption></figure><p>If the <strong>prover </strong>knows the<strong> </strong>challenge<strong> c </strong>before sending<strong> R</strong>, the entire protocol collapses:</p><ul><li>A malicious prover can forge proofs <strong>without knowing the secret</strong>.</li><li>The <strong>order of operations (commit → challenge → open) is critical</strong> for security.</li></ul><p>This is why <strong>Schnorr protocol requires the verifier to send the challenge only after seeing the commitment</strong>.</p><h4>Non-Interactive Schnorr Protocol</h4><p>We have established that in interactive Schnorr protocol the verifier must send the challenge <strong>c</strong> only after receiving the prover’s commitment <strong>R</strong>. This sequential ordering is crucial for maintaining soundness if the prover could determine <strong>c</strong> before committing to <strong>R</strong>, they could forge proofs without knowing the secret key.</p><p>This raises an important question: <em>When we make the protocol non-interactive using the Fiat-Shamir transform by replacing the verifier’s challenge with a hash output, does the protocol remain secure even though the prover can now effectively determine the challenge after computing their commitment?</em></p><p>To make this <strong>non-interactive</strong>, the <strong>Fiat-Shamir transform</strong> replaces the verifier’s challenge <strong>c</strong> with a hash of the commitment: <strong>c = Hash(PK, R)</strong></p><p><strong>The non-interactive version works as follows (as shown in Figure 3):</strong></p><ol><li><strong>Commit Phase</strong>:</li></ol><ul><li>Prover generates random <strong>r</strong> and computes <strong>R = r·G</strong></li></ul><p><strong>2. Challenge Phase</strong>:</p><ul><li>Challenge <strong>c</strong> is computed as <strong>c = Hash(PK, R)</strong></li><li>Note: Additional context like the message being signed can be included in the hash input</li></ul><p><strong>3. Open Phase</strong>:</p><ul><li>Prover computes <strong>z = r + c·sk</strong></li><li>Sends the <strong>PK</strong> and proof tuple <strong>(R, z)</strong></li><li>Verifier recomputes <strong>c = Hash(PK, R)</strong></li><li>Checks if <strong>z·G = R + c·PK</strong></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HfW5BNmtGXeWGf41qN4NHg.jpeg" /><figcaption>3. Non-Interactive Schnorr Protocol</figcaption></figure><p><strong>Why This Remains Secure?</strong></p><p>The security relies on several key cryptographic principles:</p><p><strong>a) Hash Function as a Random Oracle</strong>:</p><ul><li>The hash function acts as a trustworthy, unpredictable “verifier”</li><li>Even though the prover can compute <strong>c</strong> after choosing <strong>R</strong>, they cannot:<br>* Find <strong>R</strong> that would result in a favorable <strong>c</strong> (preimage resistance). <br>* Change <strong>R</strong> after seeing <strong>c</strong> without breaking the hash (binding property).</li></ul><p><strong>b) Computational Binding</strong>:</p><ul><li>To cheat, the prover would need to:<br>1. First choose a desired <strong>c<br></strong>2.<strong> </strong>Then find <strong>R</strong> such that <strong>Hash(PK, R) = c</strong></li><li>This is computationally infeasible for secure hash functions</li></ul><p>Despite we challenge prover by a hash function instead of verifier , the protocol still keeps secure!</p><h4>Conclusion</h4><p>The <strong>schnorr protocol</strong> serves as a canonical example of a <strong>sigma protocol (Σ-protocol)</strong>, a class of three-phase interactive proofs consisting of:</p><ol><li><strong>Commit</strong> (Prover → Verifier)</li><li><strong>Challenge</strong> (Verifier → Prover)</li><li><strong>Open</strong> (Prover → Verifier)</li></ol><p>The <strong>Fiat-Shamir transform</strong> provides a general method to convert such <strong>interactive sigma protocols</strong> into <strong>non-interactive proofs</strong> by:</p><ol><li><strong>Replacing the verifier’s random challenge</strong> with a cryptographic hash of the prover’s initial commitment (and optionally other public parameters).</li><li><strong>Allowing the prover to generate the proof autonomously</strong>, eliminating interaction while preserving security.</li></ol><p>The Fiat-Shamir transform is a <strong>powerful paradigm</strong> that bridges interactive and non-interactive cryptography. By leveraging hash functions as “virtual verifiers,” it allows sigma protocols like schnorr to operate efficiently in <strong>non-interactive settings</strong>, making it indispensable for blockchain systems, authentication protocols, and privacy-preserving applications.</p><p>Thus, while the schnorr protocol illustrates the concept, the Fiat-Shamir heuristic <strong>generalizes to all sigma protocols</strong>, providing a versatile tool for modern cryptographic design.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=769e4f9f4112" width="1" height="1" alt=""><hr><p><a href="https://medium.com/4hours/fiat-shamir-transform-769e4f9f4112">Fiat-Shamir Transform</a> was originally published in <a href="https://medium.com/4hours">4hours</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Unveiling VOLE-in-the-Head: A New Era in VOLE-ZK]]></title>
            <link>https://medium.com/4hours/unveiling-vole-in-the-head-a-new-era-in-vole-based-zk-7cc821c9e1f0?source=rss-1f434c4cb7d8------2</link>
            <guid isPermaLink="false">https://medium.com/p/7cc821c9e1f0</guid>
            <category><![CDATA[vole-in-the-head]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[vector-ole]]></category>
            <category><![CDATA[voleith]]></category>
            <category><![CDATA[love]]></category>
            <dc:creator><![CDATA[jun]]></dc:creator>
            <pubDate>Sat, 05 Apr 2025 10:30:20 GMT</pubDate>
            <atom:updated>2025-04-06T15:45:28.404Z</atom:updated>
            <content:encoded><![CDATA[<p>VOLE-based ZK has long been a cornerstone of modern cryptography, enabling one party to efficiently prove the validity of a statement without revealing any underlying information. Among the latest breakthroughs in this field is <strong>VOLE-in-the-Head (VOLEitH)</strong>, a novel protocol that transforms designated-verifier proofs into <strong>non-interactive and publicly verifiable</strong> systems. By combining advanced techniques like <strong>VOLE-ZK, Fiat-Shamir transformations, and SoftSpokenOT</strong>, VOLEitH opens new frontiers in cryptographic efficiency and applicability.</p><p>For newcomers, however, the protocol’s complexity can feel like diving into an advanced textbook without first learning the alphabet. Terms like “Fiat-Shamir Transformation” and “Vector ommitment Scheme” might seem daunting, and the interplay between these components is far from trivial.</p><p>To bridge this gap, we’re launching a <strong>comprehensive blog series</strong> dedicated to demystifying VOLEitH. We’ll start with the <strong>foundational concepts</strong>, ensuring readers have the necessary toolkit before delving into the protocol’s inner workings. Each installment will build on the last, gradually peeling back the layers of VOLEitH’s design — from its theoretical underpinnings to its practical implications.</p><h3>Here’s what the series cover:</h3><ol><li><a href="https://medium.com/4hours/fiat-shamir-transform-769e4f9f4112">Fiat-Shamir Transformation</a></li><li><a href="https://medium.com/@jun-lee/vole-based-zero-knowledge-proof-7f15ff2245f3">VOLE-ZK</a></li><li>SoftSpoken OT(coming soon).</li><li>Vector Commitment Scheme(coming soon).</li><li>VOLEitH(coming soon).</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7cc821c9e1f0" width="1" height="1" alt=""><hr><p><a href="https://medium.com/4hours/unveiling-vole-in-the-head-a-new-era-in-vole-based-zk-7cc821c9e1f0">Unveiling VOLE-in-the-Head: A New Era in VOLE-ZK</a> was originally published in <a href="https://medium.com/4hours">4hours</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Yao’s Classical Garbled Circuits]]></title>
            <link>https://medium.com/zkpass/yaos-classical-garbled-circuits-72e366eeb555?source=rss-1f434c4cb7d8------2</link>
            <guid isPermaLink="false">https://medium.com/p/72e366eeb555</guid>
            <category><![CDATA[mpc]]></category>
            <dc:creator><![CDATA[jun]]></dc:creator>
            <pubDate>Wed, 28 Jun 2023 07:29:42 GMT</pubDate>
            <atom:updated>2023-06-28T07:29:42.898Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3oJ3BEEwc53pWDQ15BYbyQ.png" /></figure><h3>Abstract</h3><p><strong>The garbled circuit</strong> is a cryptographic protocol that enables secure two-party computation in which two mistrusting parties can jointly evaluate a function over their private inputs without the presence of a trusted third party. The function has to be described as a Boolean circuit in the garbled circuit protocol.</p><p>The history of garbled circuits is complicated. The invention of the garbled circuit was credited to Andrew Yao, as Yao introduced the idea in the oral presentation of a paper in FOCS’86. Oded Goldreich documented this in 2003. The first written document about this technique was by Goldreich, Micali, and Wigderson in STOC’87. The term “garbled circuit” was first used by Beaver, Micali, and Rogaway in STOC’90. Yao’s protocol for solving Yao’s Millionaires’ Problem was the beginning example of secure computation. Nevertheless, it is not directly related to garbled circuits.</p><h3>Garbled Circuit Protocol</h3><p>The underlying function (e.g., in the millionaires’ problem, comparison function) is described as a Boolean circuit with 2 input gates. The circuit is known to both parties. This step can be done beforehand by a third party.</p><ol><li>Alice <em>garbles</em> (encrypts) the circuit. We call Alice the <em>garbler</em>.</li><li>Alice sends the <em>garbled circuit</em> to Bob along with her encrypted input.</li><li>To calculate the circuit, Bob needs to garble his input as well. To this end, he needs Alice to help him because only the garbler knows how to encrypt. Finally, Bob can encrypt his input through oblivious transfer. In terms of the definition from above, Bob is the receiver, and Alice is the sender in this oblivious transfer.</li><li>Bob <em>evaluates</em> (decrypts) the circuit and obtains the encrypted outputs. We call Bob the <em>evaluator</em>.</li><li>Alice and Bob communicate to learn the output.</li></ol><h3>Garbling Schema</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gYnQvXBpCOdpgcXinpM2hg.png" /><figcaption>Fig 0. BHR12 Garbling Schema</figcaption></figure><p>Roughly said, a garbling algorithm Gb is a randomized algorithm that transforms a function <em>f</em>: <em>{</em>0<em>, </em>1<em>}^n → {</em>0<em>, </em>1<em>}^m </em>into a triple of functions (<em>F, e, d</em>) <em>← </em>Gb(<em>f</em>). We require that <em>f </em>= <em>d ◦F ◦ e</em>. The <em>encoding function e </em>turns an <em>initial input x ∈ {</em>0<em>, </em>1<em>}^n </em>into a <em>garbled input X </em>= <em>e</em>(<em>x</em>). Evaluating the <em>garbled function F </em>on the garbled input <em>X </em>gives a <em>garbled output Y </em>= <em>F</em>(<em>X</em>). The <em>decoding function d </em>turns the garbled output <em>Y </em>into the <em>final output y </em>= <em>d</em>(<em>Y </em>), which must coincide with <em>f</em>(<em>x</em>). Informally, one has probabilistically factored <em>f </em>into <em>d ◦ F ◦ e</em>. Formally, it is problematic to regard Gb as operating on functions. Thus a garbling scheme <em>G </em>= (Gb<em>, </em>En<em>, </em>De<em>, </em>Ev<em>, </em>ev) is regarded as a five-tuple of algorithms, with strings <em>d</em>, <em>e</em>, <em>f</em>, and <em>F </em>interpreted as functions under the auspices of functions De, En, ev, and Ev. k is the secret parameter and is usually set to 128.</p><h3><strong>Classical Yao’s Garbled Circuits</strong></h3><ol><li>Alice creates the truth table according to the circuit.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/696/1*0WwN9m15o1LaDBnnVtZflA.png" /><figcaption>Fig 1. Truth table</figcaption></figure><p>2. Alice assigns two randomly generated strings called <em>labels</em> to each wire in the circuit: one for Boolean semantic 0 and one for 1. (The label is k-bit long where k is the security parameter and is usually set to 128.) Next, she goes to all the gates in the circuit and replaces 0 and 1 in the truth tables with the corresponding labels.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/695/1*Uvz7P82HKhTNB6LI0f3aqg.png" /><figcaption>Fig 2. Set labels for each wire</figcaption></figure><p>3. Alice then encrypts the output entry of the truth table with the corresponding two input labels. The encrypted table is called the garbled table. This is done such that one can decrypt the garbled table only if he has the correct two input labels. In the table below, E is double-key symmetric encryption in which (<em>A0, B0</em>)is the secret key, and <em>E0</em> is the value to be encrypted.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/699/1*mybybXet4P314GfHqEl5HA.png" /><figcaption>Fig 3. Encrypted table</figcaption></figure><p>4. Alice then randomly permutes the table such that the output value cannot be determined from the row. The protocol’s name, <strong>garbled</strong>, is derived from this random permutation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/707/1*qHeDigaoMPYkJsMQBZQvYg.png" /><figcaption>Fig 4. Garbled table</figcaption></figure><p>5. Alice sends the computed garbled tables for all gates in the circuit to Bob. Bob needs input labels to open the garbled tables. Thus, Alice chooses the labels corresponding to her input and sends them to Bob. Let’s say A and C wires are Alice’s inputs, <em>and B</em> and <em>D</em> wires are bob’s inputs. For example, if Alice’s input is 10(<em>A1, C0</em>), then she sends <em>A1</em> and <em>C0</em> to bob(Fig 4.). Bob will not learn anything about Alice’s input since Alice randomly generates the labels that look like random strings to Bob. Bob needs the labels corresponding to his input as well. He receives his labels through oblivious transfers (We will talk about this in another article)for each bit of his input. For example, if Bob’s input is 01(<em>B0, D1</em>), Bob first asks for b=0 between Alice’s labels <em>B0</em> and <em>B1</em>. Through a 1-out-of-2 oblivious transfer, he receives <em>B0</em> and gets <em>D1</em> in the same way. After the oblivious transfers, Alice will not learn anything about Bob’s input, and Bob will not know anything about the other labels.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*yGHjwZflIQjMvEaWUEigJQ.png" /><figcaption>Fig 5. Bob gets his input labels by oblivious transfer</figcaption></figure><p>6. After the data transfer, Bob has the garbled tables and the input labels. He goes through all gates individually and tries to decrypt the rows in their garbled tables. He can open one row(red row in Fig 6.) for each table.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/706/1*s39f-LsWgPkLdqPvmQG9Xw.png" /><figcaption>Fig 6. Bob evaluate the circuit</figcaption></figure><p>7. After the evaluation, Bob obtains the output label(<em>I</em>0 in Fig6.), and Alice knows its mapping to Boolean value since she has both labels(<em>I0, I1</em>). Either Alice can share her information with Bob, or Bob can reveal the output to Alice such that one or both of them learn the output.</p><h3>At Last</h3><p>Yao’s idea has been enormously impactful, engendering numerous applications, implementations, and refinements. The following article will introduce the current state of the art for garbled circuits.</p><h3>References</h3><p>[1] Foundations of Garbled Circuits: https://eprint.iacr.org/2012/265.pdf</p><p>[2] Garbled Circuit Wiki: https://en.wikipedia.org/wiki/Garbled_circuit</p><p>[3] Dr. Mike Rosulek 2PC Course: https://web.engr.oregonstate.edu/~rosulekm/cryptabit/1-overview.pdf</p><blockquote><em>zkPass Official Links:</em></blockquote><blockquote><a href="https://zkpass.org/"><em>Website</em></a><em> | </em><a href="https://twitter.com/zkPass"><em>Twitter</em></a><em> | </em><a href="https://discord.gg/zkpass"><em>Discord</em></a><em> | </em><a href="https://medium.com/zkPass"><em>Medium</em></a><em> | </em><a href="https://github.com/zkPassOfficial"><em>Github</em></a></blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=72e366eeb555" width="1" height="1" alt=""><hr><p><a href="https://medium.com/zkpass/yaos-classical-garbled-circuits-72e366eeb555">Yao’s Classical Garbled Circuits</a> was originally published in <a href="https://medium.com/zkpass">zkPass</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Pseudorandom Correlated Generator (PCG)]]></title>
            <link>https://medium.com/zkpass/pseudorandom-correlated-generator-pcg-86490c72468e?source=rss-1f434c4cb7d8------2</link>
            <guid isPermaLink="false">https://medium.com/p/86490c72468e</guid>
            <dc:creator><![CDATA[jun]]></dc:creator>
            <pubDate>Wed, 29 Mar 2023 09:56:03 GMT</pubDate>
            <atom:updated>2024-03-20T06:24:18.893Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HzYCrBSR9SGENef3HLHDLw.jpeg" /></figure><p>This is the fourth post in a series of <strong><em>interactive zero-knowledge (IZK)</em></strong> blogs. Take a look at the previous posts in the series:</p><ul><li><a href="https://medium.com/zkpass/learning-parity-with-noise-lpn-55450fd4969c">Learning with Parity Noise (LPN)</a></li><li><a href="https://medium.com/zkpass/oblivious-transfer-ot-protocol-9611b7a615a1">Oblivious Transfer (OT)</a></li><li><a href="https://medium.com/zkpass/oblivious-transfer-extension-ote-fe6978057348">Oblivious Transfer Extension (OTE)</a></li></ul><p>The primary objective of this blog is to construct a pseudorandom correlated generator using GGM tree constructions.</p><p>A pseudorandom generator is a tool that allows us to generate a long random sequence from a short seed. In this article, we will discuss how to construct a PCG and utilize it to build a sharing sparse vector, e. Why is it necessary to build this sparse vector? Please wait for my upcoming blog to find out.</p><h4>GGM Construction</h4><p>The GGM construction [<a href="https://dl.acm.org/doi/10.1145/6490.6503">GGM86</a>], named after its inventors Oded Goldreich, Shafi Goldwasser, and Silvio Micali, is a well-known and extensively utilized method for constructing Pseudo-Random Generators (PRGs) from any one-way function.</p><p>First introduced in a seminal paper by Goldreich, Goldwasser, and Micali in 1986, titled “How to Construct Random Functions,” the GGM construction is based on the idea of repeatedly applying a one-way function to a seed value to generate a long stream of pseudorandom bits.</p><p>One of the significant advantages of the GGM construction is that it allows for the generation of pseudorandom bits of arbitrary length from a relatively small seed value. This is particularly useful in scenarios where a large amount of random-looking data is required, but storage or transmission resources are limited.</p><p>In summary, GGM construction is a powerful and widely used technique for building PRGs from one-way functions. It has numerous important applications in cryptography and computer security and serves as a fundamental building block for many cryptographic primitives, including symmetric encryption algorithms and digital signature schemes.</p><h4>Puncturable Pseudorandom Function</h4><p>The puncture function, also known as the point function or single-point function, is defined such that y is zero almost everywhere except at α. Please refer to Figure 0 for the definition.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/505/1*xGUV8J82BqJykhNOx47qlg.png" /><figcaption><strong>Fig 0. Puncture function.</strong></figcaption></figure><p>Why did we introduce this function all of a sudden? Do you remember our objective for today? We aim to construct a sharing sparse vector e. In the rest of this article, I will demonstrate how we can use the GGM tree and point function to build vector e.</p><p>Sharing the secret s between two parties can be achieved by assigning s0 and s1 to each party, respectively.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/537/1*vqWY-T8I7tsdSpN6EWnAPg.png" /><figcaption><strong>Fig 1. Secret sharing.</strong></figcaption></figure><p>And we can also share the point function.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/795/1*ydlzsAzHksFe8NvHLiDwOg.png" /><figcaption><strong>Fig 2. Function Secret Sharing.</strong></figcaption></figure><p>To provide a more intuitive understanding of point function secret sharing, we can think of the black box as representing 0 and the white box as representing 1. The two parties agree on the same value almost everywhere, except for position α where they disagree.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/785/1*a9GsKCoH3VyOYRnnC9GlZw.png" /><figcaption><strong>Fig 3. Function secret sharing as a truth table.</strong></figcaption></figure><p>If we set f = f0 ⊕ f1, we know that f = [0,0,0,0,….0,1,….,0], which is a unit vector with only position α holding a value of 1. By creating t instances of f with different positions for α and adding them together, we can obtain a sparse vector e!</p><h4>PCG for Correlated OT</h4><p>Now it’s time to show you how to construct point function secret sharing by GGM tree.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/801/1*uA9LZQJgYypSx8F2Gc6RWQ.png" /><figcaption><strong>Fig 4. Generate the tree from seed s.</strong></figcaption></figure><p>As shown in Figure 4, <strong>G</strong> is a length-doubling pseudo-random generator(PRG). To be more specific, the <strong>PRG G: {0,1}^κ → {0,1}²κ</strong> takes a random seed s of κ bits as input and generates 2κ pseudorandom bits as output.</p><p>We denote the first κ bits of the output as <strong>G0(s)</strong> and the second κ bits as G1(s), such that <strong>G(s) → G0(s) || G1(s).</strong> To provide a simple analogy, you can think of G as a sha256 hash, which takes 128 bits of input and outputs 256 bits.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/631/1*FpZbOz_ZmkyWYq6utI2U9g.png" /><figcaption><strong>Fig 5. Point function secret sharing.</strong></figcaption></figure><p>To share the point function, we will follow three steps:</p><ol><li>Bob selects a seed s and uses G to construct the GGM tree, as shown in Figure 5.</li><li>Alice uses base OT to obtain all the leaves of the tree except for one position at each level, as depicted in Figure 5.</li><li>At the end of steps 1 and 2, Alice and Bob share a unit vector, as shown in Figure 6.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/602/1*_yR-u6XjY3vM39y52MTEtw.png" /><figcaption><strong>Fig 6. unit vector shared by 2 parties.</strong></figcaption></figure><p>4. Repeat <strong>t</strong> times(HW(e)=t) and add them together we will get the sparse vector <strong>e </strong>as in Fig 7.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/599/1*JvAAnn_m_h7r261yzpf30A.png" /><figcaption><strong>Fig 7. Add all shared unit vectors to get the sparse vector e.</strong></figcaption></figure><h3>Conclusion</h3><p>Since the GGM tree is a binary tree, we can generate an N-length vector e using only t* Log(N) base OT operations.</p><p>For instance, if we consider e to have one million elements and a Hamming weight (HW) of 10, traditional OT would require one million data exchanges. However, using GGM, we only need Log(2)10⁷ * HW = 20 * 10 = 200 OTs, reducing communication costs by a factor of 5,000. This result is truly remarkable.</p><blockquote>zkPass Official Links:</blockquote><blockquote><a href="https://zkpass.org/">Website</a> | <a href="https://twitter.com/zkPass">Twitter</a> | <a href="https://discord.gg/zkpass">Discord</a> | <a href="https://medium.com/zkPass">Medium</a> | <a href="https://github.com/zkPassOfficial">Github</a></blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=86490c72468e" width="1" height="1" alt=""><hr><p><a href="https://medium.com/zkpass/pseudorandom-correlated-generator-pcg-86490c72468e">Pseudorandom Correlated Generator (PCG)</a> was originally published in <a href="https://medium.com/zkpass">zkPass</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Oblivious Transfer Extension (OTE)]]></title>
            <link>https://medium.com/zkpass/oblivious-transfer-extension-ote-fe6978057348?source=rss-1f434c4cb7d8------2</link>
            <guid isPermaLink="false">https://medium.com/p/fe6978057348</guid>
            <category><![CDATA[technology]]></category>
            <dc:creator><![CDATA[jun]]></dc:creator>
            <pubDate>Fri, 24 Mar 2023 09:47:04 GMT</pubDate>
            <atom:updated>2024-03-20T06:24:49.512Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XI1WnWihFAmlAcYIFVe8VQ.jpeg" /></figure><p><em>This is the 3rd post in the series of </em><strong><em>interactive zero-knowledge(IZK)</em></strong><em> blogs. Check out the rest of the posts in the series:</em></p><ul><li><a href="https://medium.com/zkpass/learning-parity-with-noise-lpn-55450fd4969c">Learning with Parity Noise</a></li><li><a href="https://medium.com/zkpass/oblivious-transfer-ot-protocol-9611b7a615a1">Oblivious Transfer (OT)</a></li></ul><p>Previously, we delved into the generation of <strong>Standard OT</strong>, using <strong>Random OT</strong> (ROT) to create <strong>OT</strong> instances during the preprocessing phase. Unfortunately, both Standard OT and ROT require public key encryption for each instance, making them rather costly. To address this, we’ve introduced a technique that allows for the creation of a vast number of OT instances (over a million) using a fixed number of public key encryption operations (128). In this post, we’ll be detailing an efficient protocol for OT Extension.</p><p>While there are numerous methods to implement <strong>OTE</strong>, today we’ll be concentrating specifically on the [<a href="https://www.iacr.org/archive/crypto2003/27290145/27290145.pdf">IKNP03</a>] approach.</p><h3>IKNP Details</h3><h4>1）Initialization</h4><p>Alice chooses a random s∈GF(2¹²⁸) of length 128 bits.</p><p>Bob chooses a random r∈GF(2)^n, |r|=n(length of r is n), n is up to 10k rows.</p><p>Initially, Alice acts as the receiver, and Bob acts as the sender.</p><h4>2）Extended to matrix</h4><p>Bob expands r to a matrix R with the same elements in each row (10,000 rows * 128 columns), randomly generates a matrix T of the same size, and obtains a matrix T’ = T ⊕ R.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*bKVCYsh5xHeGvmQQxx9uqg.jpeg" /><figcaption><strong>Fig 0. Bob has input <em>r </em>⇒ extend to the matrix R and secret share as (<em>T</em>, <em>T</em>′).</strong></figcaption></figure><h4>3）128 times Base OT</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1wEJoMDucfH7qeTmYB5jGg.jpeg" /><figcaption><strong>Fig 1. OT for each column ⇒ Alice obtains matrix <em>Q.</em></strong></figcaption></figure><p>When Alice’s s[i] = 0, get the matrix T[i] column through Base OT; when s[i] = 1, get the matrix T’[i] column. after 128 times Base OT, Alice obtains a new matrix Q (10,000 rows * 128 columns) which columns are composed of corresponding columns of T and T’.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qBqYdtLXsNOqXOJ19T466g.jpeg" /><figcaption><strong>Fig 2. After 128 times of OT, Alice obtains the matrix Q.</strong></figcaption></figure><p>It can be found that when</p><p><em>Bob’s r = 0, Alice’s row Q = Bob’s row T;</em></p><p><em>when Bob’s r = 1, Alice’s row Q = Bob’s row T ⊕ s.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1014/1*VXVZc4nmm-b5r3XTwg5WmA.png" /><figcaption><strong>Fig 3. Relationships between Q and T.</strong></figcaption></figure><h4>4）Role Reversal</h4><p>Initially, Alice acts as the receiver, and Bob acts as the sender. However, now Alice assumes the role of the sender, and Bob becomes the receiver.</p><p>After completing the above process, Alice has 10,000 128-bit random keys ti and ti ⊕ s, and Bob has 10,000-bit r∈{0,1}. Each row is a ROT instance(qi=ti ⊕(ri * s)).</p><p>By using only 128 instances of Base OT, we are able to create 10k ROT instances.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RG5-mZ5I6xFzQo_P_mbhrA.jpeg" /><figcaption><strong>Fig 4. IKNP summary.</strong></figcaption></figure><p>(1) Bob enters r1=0, r2=1, r3=1 into the IKNP protocol.</p><p>(2) Alice uses the keys t1, t1 ⊕ s, t2 ⊕ s, t2, t3 ⊕ s, t3 to encrypt the messages m0_1, m1_1, m0_2, m1_2, m0_3, m1_3 respectively, and then sends the encrypted results to Bob.</p><p>(3) Bob uses the decryption keys k=t1, t2, t3 to decrypt them respectively, and finally gets:</p><p>(m0_1 ⊕ t1) ⊕ t1 = m0_1</p><p>(m1_2 ⊕ t2) ⊕ t2 = m1_2</p><p>(m1_3 ⊕ t3) ⊕ t3 = m1_3</p><h3>Next</h3><p>In upcoming posts, we’ll explore cryptography using Base OT and IKNP as foundational components. These building blocks will help us create advanced protocols. Stay tuned for discussions on more cryptographic protocols.</p><blockquote>zkPass Official Links:</blockquote><blockquote><a href="https://zkpass.org/">Website</a> | <a href="https://twitter.com/zkPass">Twitter</a> | <a href="https://discord.gg/zkpass">Discord</a> | <a href="https://medium.com/zkPass">Medium</a> | <a href="https://github.com/zkPassOfficial">Github</a></blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fe6978057348" width="1" height="1" alt=""><hr><p><a href="https://medium.com/zkpass/oblivious-transfer-extension-ote-fe6978057348">Oblivious Transfer Extension (OTE)</a> was originally published in <a href="https://medium.com/zkpass">zkPass</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Learning Parity with Noise(LPN)]]></title>
            <link>https://medium.com/zkpass/learning-parity-with-noise-lpn-55450fd4969c?source=rss-1f434c4cb7d8------2</link>
            <guid isPermaLink="false">https://medium.com/p/55450fd4969c</guid>
            <category><![CDATA[technology]]></category>
            <dc:creator><![CDATA[jun]]></dc:creator>
            <pubDate>Thu, 09 Mar 2023 13:51:24 GMT</pubDate>
            <atom:updated>2024-03-20T06:25:12.496Z</atom:updated>
            <content:encoded><![CDATA[<h3>Learning Parity with Noise (LPN)</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NliKBTwMNHZAP4GgXF5nnw.jpeg" /></figure><p>LPN (Learning Parity with Noise) is a fundamental mathematical problem in modern cryptography, widely used to create secure encryption algorithms. It is based on representing secret information as a set of equations with errors, making it difficult for any bounded attacker to find it. LPN is a promising post-quantum hardness assumption with parallels to the theory of error-correcting codes.</p><h3>What is Learning Problem?</h3><p>Consider the problem depicted in Fig0. Given the blue, how can we find the red?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*svsT7yla9QWLhIfXdxPqXQ.jpeg" /><figcaption>Fig0. Linear system problem: given blue, find red.</figcaption></figure><p>One second later, we can quickly solve it using <strong>Gaussian elimination</strong>, as shown in Fig1.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DXVVXSaZM_dg6Wyw6278dw.jpeg" /><figcaption>Fig1. solve linear systems by Gaussian elimination.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_6EqMghxZleEv8A_dtcLjg.jpeg" /><figcaption>Fig2. add noise into the equation.</figcaption></figure><p>However, if we introduce some noise (yellow) to the equation, as shown in Figures 2 and 3, the problem becomes more challenging. It is difficult to find the red when only given the blue (and the yellow is unknown).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*sOensyXqn8AuTNEK9--wWQ.jpeg" /><figcaption>Fig3. the equation is hard to solve now.</figcaption></figure><p>This is the <strong>Learning Problem</strong>. The red represents the secret we want to hide, and any bounded challenger cannot find the red if they only have knowledge of the blue. The LPN, which we will introduce, is one variant of this problem.</p><h3>What is LPN?</h3><p>Learning Parity with Noise (LPN) is a mathematical problem widely utilized in cryptography to create secure encryption algorithms. It involves representing secret information as a set of equations with errors, effectively hiding the value of a secret by introducing noise. LPN is conjectured to be a hard problem to solve and is utilized as a post-quantum hardness assumption, similar to the theory of error-correcting codes and with parallels to learning with errors (LWE). While fewer cryptographic constructions are known from LPN than LWE, LPN offers concrete efficiency that can rival dedicated constructions in certain cases.</p><h3>History:</h3><p>In 1996, Oded Goldreich, Shafi Goldwasser, and Dana Ron introduced the LPN assumption in their paper “<a href="https://www.wisdom.weizmann.ac.il/~oded/PDF/ggr-jacm.pdf"><strong>Property Testing and Its Connection to Learning and Approximation.</strong></a>” The paper presented an algorithm for learning an unknown distribution that closely approximates a known discrete distribution with bounded errors. Additionally, the authors introduced the LPN assumption to analyze the algorithm’s computational complexity. In 1999, Johan Hastad formally introduced the LPN problem as a computational problem and demonstrated its NP-hardness in the worst case. Hastad’s work precisely defined the LPN problem and established its computational complexity.</p><p>The LPN assumption has become a significant assumption in symmetric cryptography. It has been utilized in various cryptographic primitives, including encryption schemes, digital signatures, and authentication protocols. The security of these cryptographic systems is based on the difficulty of solving linear equations with binary coefficients in the presence of noise, which is a challenging computational problem. Additionally, LPN is highly efficient, making use of multiplication and addition in a finite field.</p><p>An early example of a ZKP commitment scheme based on LPN is the scheme proposed by Damgard, Fitzi, and Nielsen in their 2005 paper “<a href="https://eprint.iacr.org/2005/066"><strong>Unconditionally Secure Constant-Round Multi-Party Computation for Equality, Comparison, Bits and Exponentiation.</strong></a>” This scheme provides an unconditionally secure method for multi-party computation, utilizing the LPN assumption as a cryptographic primitive.</p><p>The LPN problem is defined as follows:</p><p><strong>A</strong> · <strong><em>s</em></strong> + <strong><em>e</em></strong> mod p = <strong><em>u</em></strong></p><p>Given a matrix A, it is computationally challenging to find a vector s that infinitely approximates a target vector u, even when a sparse noise vector e is randomly sampled within a fixed range. Here, the dot product is represented by “·”, p is a prime number greater than or equal to 2, s is an n-dimensional vector in the integer field of mod p, and the noise vector e is sparse with a small Hamming weight.</p><h3>LPN vs. LWE</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ak1PaICyxVSgr3xYCrIGlA.png" /><figcaption>Fig4. LPN vs. LWE</figcaption></figure><p><strong>Boolean Circuits work better with LPN</strong></p><p>In order to commit all the wires of the circuits gate by gate, we will utilize the VOLE protocol, which is based on the LPN assumption. The details of the VOLE protocol will be discussed in the following blog.</p><blockquote>In the subsequent article, we will sequentially construct efficient and commercially viable commitment schemes for data exchange in the order of OT [<a href="https://eprint.iacr.org/2005/187.pdf"><strong>Rabin81</strong></a>], OT Extension [<a href="https://www.iacr.org/archive/crypto2003/27290145/27290145.pdf"><strong>IKNP03</strong></a>], GGM [<a href="https://dl.acm.org/doi/10.1145/6490.6503"><strong>GGM86</strong></a>], FSS [<a href="https://eprint.iacr.org/2018/707"><strong>Eurocrypt 2015</strong></a>], and PGC [<a href="https://simons.berkeley.edu/sites/default/files/docs/15517/mpcwithsilentpreprocessing.pdf"><strong>BCGIKS19</strong></a>]. Our ultimate goal is to implement Interactive Zero-Knowledge Proof (IZK).</blockquote><blockquote>zkPass Official Links:</blockquote><blockquote><a href="https://zkpass.org/">Website</a> | <a href="https://twitter.com/zkPass">Twitter</a> | <a href="https://discord.gg/zkpass">Discord</a> | <a href="https://medium.com/zkPass">Medium</a> | <a href="https://github.com/zkPassOfficial">Github</a></blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=55450fd4969c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/zkpass/learning-parity-with-noise-lpn-55450fd4969c">Learning Parity with Noise(LPN)</a> was originally published in <a href="https://medium.com/zkpass">zkPass</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>