Abstract
Many models of computation in computer science allow for conditional execution,
for example RAM machines with instructions such as conditional jumps:
where the address of the next instruction depends on the result of a comparison.
This means that only part of the program is executed, depending on the result of the comparison.
This is in contrast to e.g. Boolean circuits, where all operations (AND/XOR/OR etc.) are executed, regardless of the input.
In the zero-knowledge and secure MPC literature, the primary focus has been on computations without conditional execution,
namely functions represented as circuits over a finite field.
This means that if the function is best represented in a model with conditional execution,
it will typically result in all possible executions (branches) being executed,
after which the correct result is chosen based on the input.
This is inefficient, because the communication and prover/verifier complexity
is proportional to the number of branches: in contrast to executing the
function in a model with conditional execution, where only one branch (the active one) is executed.
\vspace{3mm}
This thesis covers techniques for proving branching computation / disjunctions inside zero-knowledge proofs,
as well as related techniques for executing branching computation in multiparty computation.
The following three works have been selected for the thesis:
- Stacking Sigmas: A Framework to Compose $\Sigma$-Protocols for Disjunctions
Which proposed a concretely efficient compiler (Stacking Sigmas)
to convert $\Sigma$-protocol into proofs of disjunctions with logarithmic overhead in the number of clauses.
- Curve Trees: Practical and Transparent Zero-Knowledge Accumulators.
Building concretely efficient cryptographic accumulator with efficient membership proofs
(a disjunction over the members of a set) from commit-and-proof techniques and a novel use of elliptic curve cycles.
- Secure Multiparty Computation with Branching
Constructs efficient protocols for executing conditional branching (``if-statements'') inside multiparty computation.
for example RAM machines with instructions such as conditional jumps:
where the address of the next instruction depends on the result of a comparison.
This means that only part of the program is executed, depending on the result of the comparison.
This is in contrast to e.g. Boolean circuits, where all operations (AND/XOR/OR etc.) are executed, regardless of the input.
In the zero-knowledge and secure MPC literature, the primary focus has been on computations without conditional execution,
namely functions represented as circuits over a finite field.
This means that if the function is best represented in a model with conditional execution,
it will typically result in all possible executions (branches) being executed,
after which the correct result is chosen based on the input.
This is inefficient, because the communication and prover/verifier complexity
is proportional to the number of branches: in contrast to executing the
function in a model with conditional execution, where only one branch (the active one) is executed.
\vspace{3mm}
This thesis covers techniques for proving branching computation / disjunctions inside zero-knowledge proofs,
as well as related techniques for executing branching computation in multiparty computation.
The following three works have been selected for the thesis:
- Stacking Sigmas: A Framework to Compose $\Sigma$-Protocols for Disjunctions
Which proposed a concretely efficient compiler (Stacking Sigmas)
to convert $\Sigma$-protocol into proofs of disjunctions with logarithmic overhead in the number of clauses.
- Curve Trees: Practical and Transparent Zero-Knowledge Accumulators.
Building concretely efficient cryptographic accumulator with efficient membership proofs
(a disjunction over the members of a set) from commit-and-proof techniques and a novel use of elliptic curve cycles.
- Secure Multiparty Computation with Branching
Constructs efficient protocols for executing conditional branching (``if-statements'') inside multiparty computation.
| Originalsprog | Engelsk |
|---|---|
| Kvalifikation | Ph.d. |
| Bevilgende institution |
|
| Vejledere/rådgivere |
|
| Bevillingsdato | 2 apr. 2024 |
| Udgivelsessted | Aarhus |
| Udgiver | |
| Status | Udgivet - 2 apr. 2024 |