Motivations Keaki's goal is to facilitate/accelerate the exploration of what can be built using Extractable Witness Encryption for KZG Commitments and Efficient Laconic OT (WE-KZG, for brevity) (notes, library). The idea presented here relies heavily on such primitive so I encourage you to go through the notes first. Early proposals by Ingonyama and Yiğit Kılıçoğlu suggest looking into games such as fog-of-war chess (or dark chess). Build such game in a peer to peer and trustless manner forces you to solve many challenges. One player should be able to prove to the other player the correctness of their move without revealing the move itself. At the same time, a player should be able to probe his (limited) view under the conditions that: Nothing beyond the view is revealed to the player The opponest shouldn't learn anything about the view of the player In practice, developing such games requires zero knowledge proofs for verifiable computations and MPC for performing computation on hidden data coming from different parties.

Core Resources Paper Youtube presentation of the paper Witness Encryption (WE) First of all, what is Witness Encryption? You can compare it with a normal public encryption scheme. What you would normally do is to encrypt under a public key. You encrypt a message towards a public key. The encryption returns a ciphertext that can only be decrypted using the secret key that corresponds to the public key. Instead, with WE, a message is encrypted towards a statement. $x$ is a statement, and $w$ is a valid witness for that statement. In witness encryption, we replace the public key with the statement and the secret key (or decryption key) with the witness. The formal condition is that the $(x, w)$ is a valid NP relation in R. In other words, $w$ must be a valid witness for the statement $x$ is order to allow decryption.

Overview: What is WE? What are KZG Commitments? Extractable Witness Encryption for KZG Commitments Application to Efficient Laconic OT 1. What is WE? Regular Public Key Encryption Screenshot 2024-08-20 at 11.45.06

Me My blog Introduction to FHE - 27/7/24 - Slides Theory https://cryptographycaffe.sandboxaq.com/posts/fhe-01/ https://blog.cryptographyengineering.com/2023/05/11/on-ashton-kutcher-and-secure-multi-party-computation/ https://inferati.com/blog/fhe-schemes-bfv (BFV scheme) https://vitalik.eth.limo/general/2020/07/20/homomorphic.html https://www.jeremykun.com/2024/05/04/fhe-overview/

Problem: zk-SNARKs do not work on distributed secrets Screenshot 2024-05-06 at 09.09.03 Screenshot 2024-05-06 at 10.16.39 co-SNARKs and Publicly Auditable MPC (PA-MPC) are almost the same thing. The first solves the following problem: generating a proof when the secret data is distributed among multiple parties

Cryptography Researcher Barcelona - GMT+01:00 enricobottazzi@icloud.com enrico.eth 29.10.1996 Summary I am a researcher interested in distributed ledgers, math and applied cryptography.

Resources Short intro video Longer intro video Paper Introduction Problem: zk-SNARKs do not work on distributed secrets. One party needs to know the whole witness in order to be able to generate a valid proof. But this might not always be the case. An example mentioned in the paper is when multiple credit bureaus hold the data necessary to compute the credit score of a Alice. Alice needs her credit score to access a loan. The lender also requires a proof that this credit score was generated correctly starting from public commitments of the credit bureaus' databases. By only relying on zk-SNARKs, such proof can only be generated by a party who has access to the data of all the credit bureaus. Screenshot 2024-05-06 at 09.09.03

[ ] Nodes of the treshold network requires a way to verify that what they recevied is legit. Greco (or any proof of ciphertext formation) might be a partial solution. [ ] Users (and fellow nodes) need a way to verify that the decryption share generated by a node of the threshold network is legit (proof of (partial) decryption?) [ ] Find the best setup to settle on L1, proposal by Guy is to store ciphertexts on DA Layer and commit via transciphering on L1

Alighiero Boetti, Autodisporsi, 1975 1. Introduction Fully homomorphic encryption allows for evaluations of arbitrary functions over encrypted data. One of the most common applications of FHE is confidential outsourcing of computation. A user can encrypt their data, send it to a server that performs the (intensive) computation, and return back the encrypted result. In this scenario, the user is the only one affected by the outcome of the computation, so it is not necessary for them to prove to anyone that the submitted ciphertext to the server is properly formed. However, there are other applications of FHE in which ciphertexts coming from different parties are submitted, such as sealed bid auctions, secret voting (namely, the vote is hidden), or FHE-EVMs, such as Zama's. In such applications, a party (or a network of parties) receives the ciphertexts and performs computation on top of them. The result of this computation is then decrypted. In these multi-party applications, the result is affecting more than one user. In these scenarios, it is important that each party proves that they submitted a well-formed ciphertext. Otherwise, the final result might be, unknowingly to the other participants, constructed from invalid data. Furthermore, key recovery attacks can be mounted if malformed ciphertexts are decrypted, assuming the resulting decryptions are shared with the attacker (which is the case in Zama's FHE-EVMs). For example, in a secret voting application, the tally is computed by summing up the encrypted votes. Valid encrypted votes are of the form $E(0)$ and $E(1)$. But here's the trick; since the votes are encrypted, the application cannot tell the difference between a valid encrypted vote such as $E(1)$ and an invalid encrypted vote such as $E(145127835)$, which can mess up the whole election. Because of that, users must prove that (1) the ciphertext they submitted is a valid ciphertext. This might not be enough for the requirements of the application. Users should also prove that (2) the plaintext message they encrypted is a valid vote (for example, either a 1 or 0). Greco prover allows to prove the validity of a Fully Homomorphic Encryption (FHE) ciphertext. Greco makes use of zero-knowledge proof to let a user prove that their ciphertext is well-formed. Or, in other words, that the encryption operation was performed correctly. The resulting proof can be, therefore, composed with additional application-specific logic and subject to public verification in a non-interactive setting. Considering the secret voting application, one can prove further properties of the message being encrypted or even properties about the voter, allowing the application to support anonymous voting as well.

This is a guide related to how polynomial operations affect the degree and the coefficients of the resulting polynomial. This guide is meant to provide further understanding specifically to the operations and constraints set in zk-fhe circuits. Polynomial Multiplication Let's consider the multiplation of two polynomials $F(x) * G(x) = H(x)$. $F$ and $G$ are polynomial of equal degree $n$. Assume that the coefficients of $F$ and $G$ are in the range $[0, Q)$ $F(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_{1}x + a_0$ $G(x) = b_nx^n + b_{n-1}x^{n-1} + ... + b_{1}x + b_0$ Polynomial $H$ will have degree $2n$

Multi-player FHE Application Most of the FHE-based applications aims to achieve Private Shared State. This is an encrypted state on which everyone can perform homomorphic operations. An example of such application is Private Auction. Each user can encrypt their bid $E(bid_1) = ct_1$, $E(bid_2) = ct_2$. The Auction Manager (or, even, a smart contract) can perform the homomorphic operation to evaluate which one is the highest $max(ct_1, ct_2) = ct_?$. The highest bid $ct_?$ is now the Private Shared State. Each new bidder will then "add" their encrypted bid to the Private Shared State. FHE allows to evaluate which bid is the highest without having to decrpyt each individual bids first. Note that the homomorphic operation can be performed by anyone as it doesn't require access to any secret in order to be performed correctly. The necessary condition to perform homorphic operations between two ciphertexts is that the ciphertexts must be encrypted under the same public key. Similarly, the secret key associated to the public key is needed to decrypt the ciphertext. In the described application, this would be the highest (encrypted) bid after the auction is over. You might now be thinking on how to design such application. If each user would encrypt their bid with their own public key, the homomorphic operation wouldn't be possible. The only way to achieve this is to encrypt each bid under the same public key. Picking the public key of the Auction Manager would suffice to achieve the goal of the application. The problem here is that the Auction Manager would be able to decrypt each bid while the aution is still open. In this scenario, you have to trust the Auction Manager to not decrypt the partial states and use this information to influence the auction. I'd argue that you could create a Private Auction application with the same trust assumption with less complex technologies than FHE. The de-facto standard solution (ZAMA) is to rely on a network of nodes where each of them stores a secret key share. The associated public key is used to perform encryption operations by users. In order to perform decryption, the nodes has to come together and contribute to the decryption prodcess. This is usually performed in a threshold setting in which $t$ out of $n$ nodes are required to perform such decryption. Problem

The goal is to build a new iteration of ZheroTag 1, 2, 3 leveraging Fully Homomorphic Encryption. The core cryptographic primitive that enables to play the game without a trusted third party is Private Set Intersection (PSI). PSI allows two (or more) parties, where each party holds a set, to calculate the intersection of the two sets and reveal it to one another. Elements outside the intersection should not be revealed to any party. The current version of the game is built using PSI based on Diffie Hellman. This works aims to explore the tradeoffs in building this leveraging FHE, especially in terms of: Developer experience Gamer experience (prover time, rounds of communications required, ...) Trust assumptions and overall soundness of the game dynamic Note that this is a simplified version of Fog of War Chess. Neverthelss, starting from the cryptographic primitives being built here, it's trivial to extend it to a more complex game dynamic.

Witness table Note that I modified P a little. In this way it is easier to set certain constraints. Think about the witness table as chunks of 16 rows that only represent a single user over 2 columns. P I H(Alice, 66466) 0

Preliminary Observations OBSERVATION 1: To create fiat-backed stable coin you need to rely on reserves off-chain. By design it's impossible to trustlessy (and cryptographically) verify the existance of these reserves. OBSERVATION 2: The best tooling that we have today to guarantee the existance of reserves is auditors. In other terms we don't rely on cryptography, but we trust the auditor that is putting their reputation at stake.Latest Reserves Report of USDT - September 30 2023 Latest Reserves Report of USDC - October 30 2023. (to note: interesting that bonds have an ID) The most reliable stablecoin is the one in which these reports are performed:Frequently By reputable auditors By many different auditors OBSERVATION 3: The business model of stablecoins is based on reinvesting the reserves. I think we should aim to destroy such business model. Instead we should create a more transparent infrastrcture where the user of the stablecoin is able to assess the risk of these investments.

When working with circuits, the elements of our computation can only be expressed as non-negative element of a Prime Field. If the prime field is bn254 (which is the case for halo2lib and circom) the prime is p = 21888242871839275222246405745257275088548364400416034343698204186575808495617 It means that only number is the set [0, p) can exist in a circuit. Each number $n$ outside of this set will be considered $n\mod p$. So can we deal with negatives? The answer is yes. If you want to represent $-a$ in a field $\mod p$ you simply need to find the additive inverse of $a$ which is the number $b$ that when added to $a$ gives back zero. $a + b = 0 \mod p$

Un concetto fondamentale per spiegare l'utilitá degli zkSNARKs è la Garanzia di Integrità Computazionale. Definiamo una computazione come un insieme di regole che possono essere espresse attraverso un programma informatico. La computazione può essere semplice come sommare 2 numeri. Una computazione più complessa è la validazione delle transazioni su una blockchain e la loro aggregazione in un blocco svolta da un miner. In un network blockchain il motto è "don't trust, verify". Per questo motivo, migliaia di nodi sono chiamati a verificare che il miner abbia svolto il suo compito secondo le regole e senza, per esempio, aggiungere una valanga di token al proprio account.

Nova is a prover system. The proof produced by a nova prover is not a SNARK, it is not succint. But the cool property of nova is the fact that has the "folding" property backed into the prover system. Intro to Recursion The main use-case of Recursion is IVC (Incrementally Verifiable Computation). Incremental Computation $F$ is a function that repeats itself $z_0$ is the starting input $z_1$ is the output of F that is also feed into the next step of the computation

Problem Statement Construct a circuit that, given an array in of 100 tuples and an arbitrary value match, returns: num_match: represents the number of elements within in where the first entry matches match. out: An array of 100 tuples. The beginning of this array consists of tuples from in that satisfy the match condition. Any remaining entries, after all the matching tuples, are 0-padded. The objective is to design the circuit in a way that minimizes the number of non-linear constraints.

goal: implement a specific version of Poseidon Hasher and generate its constants 1. Run calc_round_numbers script Input parameters: alpha = 5 (3 or 5 are the most common choices for alpha) p = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001 (254 bits) prime number from bn256 t = 5 is the required width of the hasher (rate + 1)