# US 2026/0312812 A1 · Articles and methods for automated parallelization of zero knowledge protocols

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2026/0312812 A1
- Document ID: US20260312812A1
- Status: Published application
- Kind: A1
- Application number: 19/478,568
- Filed: 2024-04-24
- Published: 2026-10-08
- Earliest claimed: 2023-04-25
- Assignees: Northwestern University
- Applicants: Yale University; Northwestern University
- Inventors: Yuyang Sang; Xiao Wang; Timos Antonopoulos; Ruzica Piskac; Ning Luo
- Web page: https://patentgrep.com/patent/US20260312812A1

## CPC

- H04L 9/3218: {using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs}
- H04L 2209/08: Randomization, e.g. dummy operations or using noise
- H04L 2209/125: Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Provided herein are a method of parallelizing zero-knowledge (ZK) protocols, an apparatus for parallelizing zero-knowledge (ZK) protocols, and an apparatus for proving zero-knowledge (ZK) protocols. The method includes providing a ZK framework; calculating local and communication costs for each program instruction of a ZK statement; automatically partitioning the ZK statement according to the calculation; and distributing the partitioned ZK statement to a corresponding number of computing cores for parallel proving or verification. The apparatus for parallelizing zero-knowledge (ZK) protocols includes a processor and a memory unit configured to implement the method. The apparatus for proving zero-knowledge (ZK) protocols includes at least two processors, a memory unit, a communication interface, and a ZK statement parallelized according to the method distributed among the at least two processors. Also provided herein is a non-transitory computer readable storage medium storing computer-executable instructions for performing the method.

## Claims

### Claim 1

A method of parallelizing zero-knowledge (ZK) protocols, the method comprising:
providing a ZK framework;
calculating local and communication costs for each program instruction of a ZK statement;
automatically partitioning the ZK statement according to the calculation; and
distributing the partitioned ZK statement to a corresponding number of computing cores for parallel proving or verification.

### Claim 2 (depends on 1)

The method of claim 1, wherein the calculating includes determining sums of the maximum per-machine cost and cumulative communication costs.

### Claim 3 (depends on 2)

The method of claim 2, wherein the partitioning of the ZK statement includes chunking the ZK statement to provide a lowest or substantially lowest sum of the maximum per-machine cost and cumulative communication costs based upon the calculation.

### Claim 4 (depends on 1)

The method of claim 1, wherein the partitioning of the ZK statement is arbitrary.

### Claim 5 (depends on 4)

The method of claim 4, wherein the ZK framework permits proving multiple statements of a single witness while ensuring consistency.

### Claim 6 (depends on 5)

The method of claim 5, wherein the framework is configured to execute a commit-and-prove paradigm.

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
a prover committing private inputs; and
constructing a proof establishing some public relationship among the committed values;
wherein the public relationship among the committed values is established without revealing the committed values to a verifier.

### Claim 8 (depends on 7)

The method of claim 7, further comprising establishing multiple statements on the private inputs.

### Claim 9 (depends on 1)

The method of claim 1, wherein the partitioning comprises forming at least two substatements.

### Claim 10 (depends on 9)

The method of claim 9, further comprising precomputing the input/output of each substatement.

### Claim 11 (depends on 10)

The method of claim 10, wherein precomputing comprises forming an extended witness, the extended witness resolving data dependency.

### Claim 12 (depends on 1)

The method of claim 1, wherein the partitioning comprises shallow simulation and deep simulation.

### Claim 13 (depends on 12)

The method of claim 12, wherein the shallow simulation comprises:
the automatic partitioning of the ZK statement; and
selecting of variables as witnesses for each substatement.

### Claim 14 (depends on 13)

The method of claim 13, wherein the shallow simulation comprises:
computing the costs of each instruction in the ZK statement using live variable analysis; and
modeling the computed costs as a directed acyclic graph for partitioning.

### Claim 15 (depends on 14)

The method of claim 14, wherein the partitioning comprises pseudo-Boolean optimization (PBO) or integer linear programming (ILP).

### Claim 16 (depends on 13)

The method of claim 13, wherein the deep simulation comprises:
computing extended witness values using a prover's private inputs; and
computing public variable values.

### Claim 17 (depends on 16)

The method of claim 16, wherein the computing of the extended witness values and public variable values comprises propagating input-dependent values through the ZK statement.

### Claim 18 (depends on 1)

The method of claim 1, wherein the framework comprises annotation tools configured to identify knowledge levels.

### Claim 19 (depends on 18)

The method of claim 18, wherein the knowledge levels comprises private input-independent values known at compile time, private input-dependent values that are known at distribution time, and variables that are only known at runtime.

### Claim 20 (depends on 19)

The method of claim 19, wherein the private input-independent values and the private input-dependent values are allowed to flow into the variables that are only known at runtime, but the variables that are only known at runtime are not allowed to flow into the private input-independent values and the private input-dependent values.

### Claim 21 (depends on 20)

The method of claim 20, wherein the partitioning step includes treating the variables that are only known at runtime as a single contiguous block to estimate worth-case cost and enforce sequential ordering.

### Claim 22 (depends on 1)

The method of claim 1, wherein the distributed ZK statement includes randomized verification.

### Claim 23 (depends on 1)

An apparatus for parallelizing zero-knowledge (ZK) protocols, the apparatus comprising:
a processor;
a memory unit; and
a communication interface;
wherein the processor is connected to the memory unit and the communication interface; and
wherein the processor and memory are configured to implement the method of claim 1.

### Claim 24 (depends on 1)

An apparatus for proving zero-knowledge (ZK) protocols, the apparatus comprising:
at least two processors;
a memory unit; and
a communication interface;
wherein the processors are connected to the memory unit and the communication interface; and
wherein a ZK statement parallelized according to the method of claim 1 is distributed among the at least two processors.

### Claim 25 (depends on 1)

A non-transitory computer readable storage medium storing computer-executable instructions for performing the method of claim 1.
