Let's assume that a reversible circuit with $n^$ wires and $m^$ gates permutes the input such that the output permutation is indistinguishable from a strong pseudo-random permutation. The authors use this property of reversible circuits to build an algorithm that satisfies ROI (ROI is also program obfuscation and is similar to iO) for all reversible circuits. Reversible circuits Reversible circuits were first explored to express computation such that it can be reveresed. For example, a + b = c is not a reversible operation. Because it is not possible to derive a, b from c. However, if the circuit outputs b as an auxilary value, the computation becomes reversible. Reversible circuits apparently are also natural fit for quantum circuits (a quick search for "reversible circuits and quantum computation" will produce many useful resources). The other property that reversible circuits have, and the one we're interested in, is that if you chain enough reversible gates the reversible circuit can be called a strong pesudorandom permutation. In others words, the reversible circuits permutes the input bits such that the output is indistinguishable from the truly random permutation to an adversary with polynomial resources. A reversible circuit is expressed as collection of $n$ parallel wires and $m$ gates and, usually, the computation flow is from left to right. Each gate mutates at least 1 wire based on signals of other wires. There're several varieties of gates but we're only interested in Toffoli gate. Toffoli gate is defined by 2 control wires, control function, and a target wire. The gate applies the control function on the control wires and sets the target wire as XOR of output of control function by itself. For example, if a, b are the control wires, $\phi$ is the control function, and c is the target wire. Then the gate computes: $c = \phi(a, b)\oplus c$. Observe that with 2-bit controls there can only be $2^{2^4} = 16$ control functions. We refer to these gates as the "base gates". A base gate is defined over $n$ wires but it only touches 3 wires (2 controls and 1 target) called active wires. Another observation to make is any base gate is an inverse of itself and there exist a identity base gate with control function $\phi(a, b) = 0$

Goal of the bounty To win the bounty you must find a reversible circuit with < 1014 gates which is funtionally equivalent to the obfuscted circuit we've provided. We've provided an obfuscated circuit of a randomly sampled reversible circuit which is also an strong pseudo random permutation (SPRP). SPRP implies that the output permutation on any input bitstring is indistinguishable from a truly random permutation. The original reversible circuit has n=64 wires and 1014 gates. The task is to find the original "reversible circuit" only given the obfuscated circuit. The obfuscated circuit has n=64 wires and 12111 gates. If you're able to find another circuit with <= 1014 gates that is not the orignal circuit you still win the bounty because doing so breaks the assumption that original circuit is an SPRP. Note: Generating input to output map of the permutation that obfuscted circuit computes is not "finding the original circuit". Hence, is not a valid submission. Submission To submit send the circuit JSON file of the circuit to dada@gmail.com. To pay out the bounty it suffices to verify that your circuit is funtionally equivalent to our original/obfuscated circuit.

image We spend numerous hours imagining the world we want to live in, imagining its bits and pieces that will be different. Imagining how we will shape it when we burst into action. Ruminating for hours thinking of new things it will have. And that's what we have been doing at Gauss for last few months. We have been building the Phantom zone. It's similar to the zone where superman gets locked and observes everything outside the zone, but no one outside can see or hear superman. However, our phantom zone isn't meant to lock anyone. Instead it's meant to be a new zone in parallel to reality. It's the zone to which you teleport yourself with others, take arbitrary actions, and only remember predefined set of memories when you're back. It's the zone where you can have conversations and forget undesirable parts, negotiate contracts and not leak strategies, play hidden information games, and many more. Think of the zone as a computer that erases itself off of the face of the earth after it returns necessary outputs, leaving no trace behind. Phantom zone is built using multi-party fully homomorphic encryption and provide APIs to evaluate any arbitrary function on private inputs from multiple parties. At the moment, phantom zone is experimental and limited in its functionality. It restricts arbitrary functions to use unsigned 8 bit integers and only allows upto 8 parties. Despite the limitations, we want to release it because we believe phantom zone will unleash everyone's imagination and enable new & unique user applications. More so, at our core, we believe we cannot build the phantom zone just by ourselves. We provide the tools, but it will be our creative imagination as a whole that will bring the phantom zone to reality. We invite you to try the phantom zone and let your imaginative forces fly!

Summary of Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption TLDR This paper proposes practical witness encryption from ADP and uses it to construct a public-key encryption scheme with very short secret and public keys (around 300 bits) but large ciphertexts (around 400MB). The ADP construction is then used as a potential candidate for IO, but it is not practical yet, essentially because it requires a super-polynomial error in the depth of the branching program to protect against invalid inputs. Given $\ell$ the size of the branching program, modulus $p$ (error is sampled mod $p$) must be $\mathcal{O}(\ell^{4+\epsilon})$, i.e. super-polynomial in $\ell$. An example is given: if $\ell = 2^{13}$, then the ADP would be around 100 terabytes. More Recent Attacks

struct Coordinate { x: int, y: int } struct Monster { index: int coordinate: Coordinate }

I am wondering whether we can use technique of gadget decomposition in decryption to replace degree 2 PRNG in your paper (I believe the PRNG is there to add smudging noise). Let's say user provides $\beta^k s'$ where $\beta^k s'[i] = \beta^k s[i] + e_{i,k}$ for $k \in [0,l)$, where $i \in [0, n)$, $n$ being the LWE dimension. We can assume $e_{i, k}$ to be bounded by some bound $B$. To decrypt LWE ciphertext $$LWE_{s}(m) = (b, a) = (b = a \cdot s + e + \Delta m, a)$$ decompose vector $a$ in multiple limbs, $a_0, .., a_{l-1}$ s.t. $a[i] = \sum \beta^k a_j[i]$. Then calculate inner product, $$b - a \cdot s + E = b - \sum_{k \in [0, l)} a_k \cdot \beta^k s'$$

The compiler should take as input a python, C++ file and output a circuit descruption file. Let's refer to circuit file as CDF (circuit description file). Following is the flow I have in mind Python -> MLIR The front-end language does not necessarily be Python. But I suspect python will be easier. Compile down source code (ie program) to MLIR. This is required for next step because HEIR only accepts MLIR as input. MLIR -> BOOLEAN GATES

Let $\gamma$ be the publicly known main seed. Set no. of parties to P. Sample party specific seeds $\gamma_i$ from $\gamma$ for $i \in [0, P)$. Sample key specific seeds \gamma_{k}, Key generation party j Generate RLWE secrets $s_j, u_j$, LWE secret $\hat{s_j}. Generate shares for $ksk(u_j \to s)$:Sample $a''{0, j}, a''{1,j}, ..., a''{d-1,j}$ from pseudo random generated seeded with $\gamma{j}$ For i in 0..d-1 generate

Let $s = \sum s_{i}$, $m = \sum m_{i}$, $u = \sum u_{i}$. We seek to generate $\textsf{RLWE}{s}(-sm)$ from $\textsf{RLWE}{s_{i}}(-sm_{i})$. Let $a$ and $[a_{1}, \dots, a_{j}]$ be common reference polynomials derived from a public seed. Offline Setup $P_{i}$ sends to the server: $\textsf{RLWE}{u{i}}^{a}(m_{i}) = [(au_{i}+m_{i}+e)]{QP}$ where $u\leftarrow\chi{sk}$ $\textsf{GRLWE}{s{i}}^{a_{j}}(u_{i}) = [(-a_{1}s_{1}+ P'\cdot \mathbf{w}{1}\cdot u{i}+e), \dots, (-a_{j}s_{1}+P'\cdot\mathbf{w}{j}\cdot u{i}+e)]_{QPP'}$ $\textsf{RLWE}{s{i}}^{a}(0) = [(-as_i+e)]_{QP}$

Obtain error term by repeated squaring Intuitively it works by repeatedly doubling the zero LWE (or RLWE) ciphertext for $k$ times where $k \approx \log{\Delta}$ such that one obtains the error term $e$ in fresh zero LWE ciphertext in the plaintext space of resulting ciphertext. If the decryption oracle does not reject decryption request of resulting ciphertext based on exact/heuristic estimation of noise growth, it will return the attacker error $e$ in original zero LWE ciphertext. Given original LWE ciphertext encrypts 0, that is it equals $(b = a \cdot s + e , a)$ the attacker can obtain a linear equation with variable $s$ as $a_0s_0 + ... + a_{n-1}s_{n-1} = b-e$. Repeating the attack $n$ times with $n$ zero LWE ciphertext, the attacker can recover the secret key. Countermeasure for FHEW/CGGI A way to counteract such attacks without having to track the noise growth in ciphertext during circuit evaluation is to bootstrap the ciphertext before sending it back to the user (or, in case of decryption oracle, the oracle bootstraps and then decrypts). Since noise in bootstrapped ciphertext is independent of noise in input ciphertext, the attack fails. Check algorithm 4 of eprint 2024/127

Overview of eprint 2024/155 the key idea is that they reduce the number of external products by splitting the homomorphic inner product $a \cdot s$ Define $m$ st it divides $n$. Then split the secret key into $n/m$ continuous chunks. Define $s_k$ as the $k^{th}$ chunk. We can re-write $$a \cdot s = \sum_{k=0}^{(n/m)-1} a_k \cdot s_k$$ Define $\delta_{j, s^k} = 1$ when $j == s^k$ where $j \in S^{m}$ ($S^m$ is essentially all possible values that $s^k$, for some $k$, can have).

We need a way to map a vector in $C^{N/2}$ to polynomial in $R/X^N+1$. Define the $M^{th}$ cyclotomic polynomial $$X^N+1 = \prod_{\omega_j \in P_M} X - \omega_j$$ where $P_M = {\zeta^i | i \in Z^*_M}$ (i.e. the set of all $M^{th}$ primitive root of unity) Since $X-\omega_j$ are co-primes, due to CRT, there exist following isomorphism: $$X^N+1 \cong \prod_{\omega_j \in P_M} X - \omega_j$$ The map that reduces polynomial in $R/X^N+1$ to its representation in $X-\omega_j$ is a simple evaluation of polynomial over $\omega_j$.

BFV setup Let $Q$ be the ciphertext modulus and $t$ be plaintext modulus. Let $R_Q$ denote the polynomial ring $Z_Q[X]/X^N+1$. In practice we leverage RNS and set $Q = \prod{q_i}$ where $\log q_i < 61$ and the $q_i$ factor are pairwise coprimes. This modiication was suggested by Bayard et al., 2016 to make arithmetic operations faster as these no longer need to be work with Big integer arithmetic. Note that $Q$ and $t$ are co-prime. Using the Chinese Remainder Theorem (CRT), an integer $x ∈ Z_Q$ can be represented by its CRT components ${ x_i = x \mod q_i \in \mathbb{Z}{q_i} }i$, and operations on $x$ in $Z_Q$ can be implemented by applying the same operations to each CRT component $x_i$ in its own ring $Z{q{i}}$. BFV secret key encryption $$Ct = (Ct_0, Ct_1) = ([A \cdot S + E + K]Q, A)$$ Where $A \in R_Q, S \in \chi{key}, E \in \chi_{error}$ and $K = \lceil \frac{Q [M]_t}{t} \rfloor$ [1].

Jumboji Requirements: Problem 1, public key set PSI Take two sets of (baby jubjub ECDSA) signatures A, B with |A| = n, |B| = m, n != m necessarily. Define the set of public keys that with signatures in A as A_pk and B as B_pk. A_pk and B_pk are subsets of a fixed set T, which is the total set of "meaningful" public keys. Currently |T| = 201, interested in |T| for size 25,000 Within either set A or B, all the signatures are from different public keys (thus |A_pk| = n, |B_pk| = m) Determine the intersection of A_pk and B_pk Problem 2, public key set PSI + signature verify