zkPass 백서

zkPass

원문

bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 13쪽 중 3쪽

nteractive Zero-Knowledge Proof (IZK). The ubiquity of HTTPS has facilitated users to access private data with robust end-to-end confidentiality and integrity. However, a shortfall exists in that they cannot inherently substantiate to third parties that the data originated from a specific website. To rectify this, we propose the zkPass protocol. This empowers users to convincingly demonstrate that data accessed via HTTPS was obtained from a particular website, asserting statements about this data within a zero-knowledge context, thereby preserving privacy and averting the exposure of sensitive information. Serving as a conduit between Web 2.0 and Web 3.0, the zkPass protocol liberates private data from the confines of centralized web servers, paving the way for seamless migration into a decentralized era. ## Notation and Preliminaries • Prover(P): or user, or client who is required to generate proof for their statement. • Verifier(V): or platform, which is responsible for verifying the Prover’s statement. • Node(N): zkPass Node, is a part of the protocol execution used to verify the authenticity and integrity of the Prover’s private data. • DataSource(S): stands for https server, is the trusted data source that owns the Prover’s data. ## 1 Overview of Solution In the traditional data validation and confirmation process, the Prover submits their information to the Verifier. The Verifier, in turn, retrieves this data and performs authentication checks in collaboration with the DataSource. Thus, the Verifier serves merely as an intermediary or broker in this model. Each party faces unique challenges in this scenario: for the Prover, there’s a risk of disclosing excessive personal information; for the DataSource, while it’s a trusted data provider, it’s incapable of offering personalized verification services; and for the Verifier, they’re privy to all the customers’ private data, gaining total access, which presents significant potential risks of data leakage. We propose a new approach that repositions these three entities, positioning the Prover between the Verifier and the DataSource. Rather than the traditional method, the Prover uses their access token to directly locate and retrieve their data from the DataSource, subsequently generating a Zero-Knowledge Proof (ZKP) for the Verifier to check. This process ensures the Verifier remains unaware of the Prover’s personal information. In order to implement this structure, we incorporate 3P-TLS, MPC, and IZK technologies. ### **1.1 3P-TLS** Transport Layer Security (TLS) is the secure protocol for HTTPS, supported by almost all DataSources. It is a two-party protocol designed for client/server structure. We have built the 3P-TLS protocol based on elliptic curve DH protocol and combined it with MPC and Oblivious Transfer(OT) to prevent cheating. ### **1.2 MPC** One challenge we face is that the Prover may forge proof information provided by the DataSource to deceive the Verifier. The solution to this problem is through MPC, where both Prover and Verifier hold half of a session MAC key, which is a data integrity key used to maintain data integrity. Since the Prover cannot forge or tamper with information responses provided by the DataSource, and it cannot deceive the Verifier. MPC can also prevent the Verifier from knowing any private information about the Prover. During MPC handshake, there is no encryption key (data confidentiality key) for the Verifier, so it cannot decrypt any data and therefore does not know any private information for the Prover. ### **1.3 IZK** After obtaining information from the DataSource, Prover needs to prove certain statements of the response in a secure and private manner. We use Zero-Knowledge Proofs(ZKP) to achieve this goal. More specifically, we use interactive commit and prove zero-knowledge proofs(ICP-ZKP) to deal with the large scale of circuit. Prover gives the commitment as $$d = commit(m, r)$$, where $$m$$ is the message and $$r$$ is the randomness. Then Verifier check $$T/F= verify(m, r, d)$$. $$d$$ wouldn't reveal any information about $$m$$, and Prover can't find different $$m$$and $$m'$$ (and $$r$$ and $$r'$$) such that $$verify(m, r, d) = verify(m', r' , d) = T$$. During the protocol, Prover needs to commit its private witness, then prove the input wires and the computation of gate one by one, and continue to commit the output wires until the final one. ## **2 TLS** ### **2.1 Overview** TLS is one of the most widely used protocols for secure communication over the Internet. It encrypts data from plaintext to ciphertext and vice versa, providing data security and privacy by encrypting traffic to prevent sensitive data from being leaked by third parties. The process consists of two sub-protocols: handshake and record layer. The goal of the first sub-protocol is to negotiate a secure key between two endpoints, while the second uses an agreed key to protect communication. ### **2.2 Handshake** We refer to the endpoint initiating the connection as the ”client,” while the term ”server” denotes the responding endpoint. Additionally, we define the ”transcript” as the comprehensive record of all messages exchanged over the connection up until the point of analysis. The Handshake protocol itself can be divided into three distinct phases: the key exchange phase, the authentication phase, and the key derivation phase. #### Key exchange phase The protocol is started by the client sending a ClientHello to the server, containing the cryptographic algorithms supported by the client. The server replies with a ServerHello, containing the cryptographic algorithms selected from those offered by the client and a Diffie-Hellman public key. When the initial exchange is concluded, the two endpoints perform a Diffie-Hellman key exchange using the keys specified in the Hello messages. #### Authentication phase Starting from the server, the endpoints exchange their certificates (ServerCertificate) and a signature on the transcript using the key specified on them (ServerCertificateVerify). Finally, they send an HMAC on the transcript using the MAC keys obtained from the key derivation (ServerFinished and ClientFinished). The client uses the first key, the server uses the second one. The endpoints verify all the signatures and the MAC provided by the other endpoint. If any check fails, the connection is closed. #### Keys Derivation phase At the end of the Handshake, the endpoints feed the new messages of the transcript into the key derivation function. The key derivation function maintains an internal state, therefore all its outputs depend on the The key exchange phase. At the end, the parties obtain application keys(encrypted keys/MAC keys). From that moment, the Record layer protects the client-toserver flow through those keys. As it was proven in the authentication phase, all the values output by the Handshake are computationally independent, even slight modifications in the transcripts input in the key derivation function would lead to completely different and unpredictable outputs. #### 3P Handshake To illustrate the 3P handshake, we first assign specific roles to the three parties involved: the Prover (P) and Node (N) jointly act as the Client, while the DataSource (S) assumes the role of the Server. This handshake process is based on the fundamental principle of Diffie-Hellman key exchange. Given the Client’s public key, all participating parties should be capable of computing a secretsharing of the exchanged secret. It is crucial to emphasize that if any party gains access to the exchanged secret, it could compute the symmetric keys and engage in unrestricted communication with the client. Therefore, to design a secure multiparty Diffie-Hellman protocol, it is essential for the parties to possess a secret-shared private key. It is worth noting that the public key does not require confidentiality. The protocol proceeds as follows: <figure><img src="https://2216484837-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FC2Jh1oquOpJPfwzD3x9L%2Fuploads%2Fn8YeSfdkwrby6v5t3zbk%2F1.png?alt=media&amp;token=db3b9804-1df5-40f9-ad74-1026e5d411c6" alt=""><figcaption></figcaption></figure> <figure><img src="https://2216484837-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FC2Jh1oquOpJPfwzD3x9L%2Fuploads%2Fd5ZJbEFkaAjBaAXDpPPy%2Fimage.png?alt=media&amp;token=24763850-a124-4f92-ad4d-eb268942f5a6" alt=""><figcaption></figcaption></figure> ### 2.3 The Record Layer The Record layer provides fragments as application data, which signifies the actual communication between the two endpoints. User-sensitive information is contained within this application data, usually in the form of HTTP requests/responses, and is encrypted/authenticated using the application keys. The security of this system is maintained if each party keeps their respective application keys private. This ensures the protection of user data throughout the communication process, minimizing the potential risks of data leakage and unauthorized access. #### **Multi-Record** TLS is performed on streams, and the data in those streams are put into one or more fragments (of max 2^14 bytes). Client message boundaries are not preserved in the record layer (i.e., multiple client messages of the same ContentType MAY be coalesced into a single TLSPlaintext record, or a single message MAY be fragmented across several records). This means that we need to authenticate all records. <figure><img src="https://2216484837-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FC2Jh1oquOpJPfwzD3x9L%2Fuploads%2FYR4cBHZ3oji1FuKqUsEv%2Fimage.png?alt=media&amp;token=b0c2cdf7-4926-4ad7-bdd4-1bc7d49fea65" alt=""><figcaption></figcaption></figure> #### **Multi-Response** In specific usage scenarios, it may be necessary for the Prover to retrieve information from multiple responses originating from different APIs, potentially requiring multiple TLS sessions with a single data source. This implies that the Prover would need to perform multiple rounds of MPC and ZKP. To handle this situation efficiently and reduce overhead, we propose leveraging the same handshake session. HTTP keep-alive is a mechanism designed to reuse the same connection for multiple HTTP requests and responses. This inherently reduces the number of TLS handshakes, as only one TLS handshake is performed per TCP connection. In other words, with HTTP keep-alive, a single TCP and TLS handshake can accommodate multiple HTTP requests. Consequently, we can transmit different application data pertaining to various requests within a single TLS session. Furthermore, resuming the TLS session allows the Prover and the DataSource to utilize the same set of keys. The TLS protocol provides a method for session resumption known as Session Tickets, as defined in [RFC 5077](https://tools.ietf.org/html/rfc5077). The server can utilize a key rotation algorithm to encrypt and decrypt tickets using different keys over time. Additionally, the server can send new tickets to the client after each successful resumption. By implementing this standard, we can ensure an efficient and secure data retrieval process. <figure><img src="https://2216484837-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FC2Jh1oquOpJPfwzD3x9L%2Fuploads%2FMgawPu4m5cXpuMB5N2rx%2Fimage.png?alt=media&amp;token=98960cd6-cb1e-4bf7-8ebb-7349aa0005c0" alt=""><figcaption><p>Figure 1: Resuming TLS Session with Session Ticket</p></figcaption></figure> ### 2.4 Additional Explanation The content we’ve presented here partially explains TLS. We still need to cover numerous additional procedures and features in this discussion. For a more comprehensive understanding and deeper insight into these topics, we highly recommend referring [RFC5246 ](https://www.rfc-editor.org/rfc/rfc5246)and [RFC8446](https://www.rfc-editor.org/rfc/rfc8446), specific internet standards that provide detailed information about the various aspects and applications of TLS. ## 3 MPC ### 3.1 OT The OT protocol is a technique first introduced by Rabin in 1981. Coupled with Garbled Circuits (GC), it can facilitate secure Multi-Party Computation (MPC) protocols. Parties involved in secure computation employ OT to establish a secure communication channel or to exchange encrypted data. This allows them to construct the GC and execute the computation without exposing sensitive information. To illustrate our protocol, we’ll concentrate on the chosen 1-out-of-2 OT, often called standard OT, though it can easily be extended to 1-out-of-N OT. There are two roles for OT: sender and receiver. Specifically, the sender has two messages $$m0$$ and $$m1$$, the receiver has an index $$c\in\left{0, 1\right}$$ and the receiver wants to receive the sender's $$c-th$$ message without letting the sender know $$c$$. At the same time, the sender wants to ensure that the recipient can only receive one of these two messages. <figure><img src="https://2216484837-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FC2Jh1oquOpJPfwzD3x9L%2Fuploads%2F1BMuzaFuGbuvmPfaRJus%2Fimage.png?alt=media&amp;token=2cd2bc53-59e2-4c39-89d2-cb0c6ed1acd7" alt=""><figcaption></figcaption></figure> In practice, we often let $$m\_1=m\_0 ⊕ Δ$$ , such that$$m\_c=m\_0 ⊕ c\* Δ$$, we call it correlated OT. Following shows the detail to implement basic OT based on Diffie-Hellman key exchange: <figure><img src="https://2216484837-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FC2Jh1oquOpJPfwzD3x9L%2Fuploads%2FEAFhXagzqnlxv3Q2PG4A%2Fimage.png?alt=media&amp;token=cedf48e8-c8ac-4cd1-a90b-4e84d73e8058" alt=""><figcaption><p>Figure 3: The Simplest Protocol for Oblivious Transfer</p></figcaption></figure> Given that OT serves as a prerequisite for both Garbled Circuits (GC) and Interactive ZeroKnowledge Proofs (IZKP), and considering our need for large-scale utilization of OT, we require an efficient methodology for generating OT instances that are optimally cost-effective. Additionally, to ensure adequate security of the entire zkPass protocol, it’s crucial that our OT protocol possesses active security. In the following section, we detail the OT protocol we are utilizing, which requires merely 128 basic OT instances. This approach eliminates the need for costly public key encryption for basic one-time passwords and aids in distributing network and computational load effectively, thereby optimizing our protocol’s overall efficiency and security. <figure><img src="https://2216484837-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FC2Jh1oquOpJPfwzD3x9L%2Fuploads%2Fe05ZcIkb1BVN7673liXP%2F2.png?alt=media&amp;token=b4b83921-7704-4786-8949-52cd9b296e79" alt=""><figcaption></figcaption></figure> #### 3.2 GC GC is an encryption protocol that facilitates secure computation between two parties. It allows two participants, who may not trust each other, to jointly evaluate a function on their respective private inputs without necessitating a trusted third party. For the GC protocol, the function to be evaluated must be defined as a Boolean circuit. The function underlying this, such as the comparison function in the millionaire problem, is presented as a Boolean circuit with two input gates. Both parties are aware of this circuit. What follows is an illustration of the GC workflow. A component of a garbling scheme $$G = (G\_b, E\_n, D\_e, E\_v, e\_v)$$. The function $$G\_b$$ maps $$f$$ and $$k$$ to $$(F, e, d),$$ where strings encode the garbled function, encoding function and decoding function. With $$e$$ and $$x$$ one can compute the garbled input $$X=E\_n(e, x)$$; with $$F$$ and $$X$$ one can compute the garbled output $$Y = E\_v(F, X)$$; knowing $$d$$ and $$Y$$ allows for recovery of the final output $$y = D\_e(d, Y)$$, which must be equal to $$e\_v(f, x)$$. <figure><img src="https://2216484837-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FC2Jh1oquOpJPfwzD3x9L%2Fuploads%2Fk2pQIeAzpqIwWdxwJt6U%2Fimage.png?alt=media&amp;token=df872c4c-5c29-46c7-978d-468cafbab6c8" alt=""><figcaption><p>Figure 4: Foundations of Garbled Circuits</p></figcaption></figure> Considering that both the Prover and the Node maintain their respective private keys during the key exchange phase of the 3P handshake, both parties need to use their own private keys to compute the Pre-Master Secret (PMS). This PMS is then further derived into a session key. We employ Garbled Circuits (GC) for this calculation. Below, we detail the specific implementation of GC as used in zkPass. <figure><img src="https://2216484837-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FC2Jh1oquOpJPfwzD3x9L%2Fuploads%2FaSXCFUhl0msxTQcNU3E1%2Fimage.png?alt=media&amp;token=e98c8911-2d9e-4436-a552-5eec7480dfda" alt=""><figcaption></figcaption></figure> ## 4 IZK In Non-interactive Zero-Knowledge (NIZK) Proof systems, such as zk-SNARK and zk-STARK, computations are represented as circuits, and the gate constraints within the circuit are depicted as a set of polynomials. If a computation requires multiple circuits, all these circuits need to be amalgamated into a single, large circuit that is then submitted. Despite the trust assumptions associated with this approach, it necessitates a very large memory space which is typically not feasible within browser environments. To tackle the issue, we employ VOLE (Vector Oblivious Linear Evaluation)-based IZKP. Its linear nature allows us to submit circuits individually, effectively balancing memory size. Moreover, IZKP doesn’t require a trusted setup, thereby enabling the generation of zero-knowledge proofs in a browser environment. ### 4.1 VOLE VOLE is the arithmetic counterpart of string OT. Concretely, the VOLE functionality is a two-party functionality that takes a pair of vectors from the sender $$P\_0$$, and allows the receiver $$P\_1$$ to learn a chosen linear combination of these vectors. More formally, given a finite field $$F$$, the VOLE functionality takes a pair of vectors $$(u, v) \in F\_n \times F\_n$$from $$P\_0$$ and a scalar $$x\in F$$ from $$P\_1$$. It outputs $$w = ux + v$$ to $$P\_1$$. We will also consider a randomized version of VOLE where the sender’s inputs $$(u, v)$$ are picked at random by the functionality and delivered as outputs to the sender. The deterministic VOLE functionality can be easily reduced to the randomized one analogously to the reduction of OT to random OT. Below is how we generate the VOLE instanances: <figure><img src="https://2216484837-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FC2Jh1oquOpJPfwzD3x9L%2Fuploads%2FdARud5pKKqrAKcUBd0Ci%2Fimage.png?alt=media&amp;token=b153e965-d1c8-45e2-8cc8-8cc14f4d06a9" alt=""><figcaption></figcaption></figure> ### 4.2 ICP-ZKP We employ ICP-ZKP, a variant of interactive protocols that primarily uses symmetric key operations, thus achieving high efficiency and scalability. It can process millions of gates per second and manage large circuits consisting of billions of gates. The protocol includes a method for associating commitment schemes with proof commitment values. The commitment scheme actually serves as an Information-Theoretic Message Authentication Code (IT-MAC). This can be efficiently implemented using VOLE, and its homomorphic properties help to reduce the cost associated with addition gates. The functionality of the ICP-IZK is described as follows: <figure><img src="https://2216484837-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FC2Jh1oquOpJPfwzD3x9L%2Fuploads%2FTfO6Z23WOQs9URSupORk%2F3.png?alt=media&amp;token=d874023b-264a-409c-891b-7548bedadb06" alt=""><figcaption></figcaption></figure> ### 4.3 Circuit Factory #### **Bristol Fashion Circuit** We utilize Bristol-style circuits, which are composed of AND, XOR, and INV gates. The format is defined as follows: <figur
프로젝트로 돌아가기