junyechen1996 / draft-chen-cfrg-vdaf-pine

VDAF to support aggregating real number vectors with L2-norm bound
Other
5 stars 0 forks source link

Analyze overall soundness error of PINE #58

Closed junyechen1996 closed 8 months ago

junyechen1996 commented 8 months ago

Some results:

------- Target soundness error: 2^(-32)
Wraparound check parameters:
|r         |r_succ    |-log2(eta)     |-log2(zk)      |-log2(sound)   |overhead  |alpha               |
|:---------|:---------|:--------------|:--------------|:--------------|:---------|:-------------------|
|32        |32        |134            |129            |32             |672       |9.673410431465864   |
|37        |36        |69             |128            |31             |740       |6.965651630622664   |
|41        |39        |48             |130            |31             |820       |5.827882278103885   |
|86        |71        |12             |135            |31             |1634      |3.0018183401530623  |

User parameters:
|l2_norm   |frac_bits |dimension |chunk_len |field     |proofs    |r         |r_succ    |-log2(eta)|-log2(zk) |-log2(wr_sound)     |-log2(gadget_sound) |
|:---------|:---------|:---------|:---------|:---------|:---------|:---------|:---------|:---------|:---------|:-------------------|:-------------------|
|1         |15        |1000      |42        |Field64   |1         |32        |32        |134       |129       |32                  |54                  |
|1         |15        |1000      |42        |Field128  |1         |32        |32        |134       |129       |32                  |118                 |
|1         |15        |10000     |103       |Field64   |1         |32        |32        |134       |129       |32                  |54                  |
|1         |15        |10000     |103       |Field128  |1         |32        |32        |134       |129       |32                  |118                 |
|1         |15        |100000    |317       |Field64   |1         |32        |32        |134       |129       |32                  |53                  |
|1         |15        |100000    |317       |Field128  |1         |32        |32        |134       |129       |32                  |117                 |

------- Target soundness error: 2^(-64)
Wraparound check parameters:
|r         |r_succ    |-log2(eta)     |-log2(zk)      |-log2(sound)   |overhead  |alpha               |
|:---------|:---------|:--------------|:--------------|:--------------|:---------|:-------------------|
|64        |64        |134            |128            |64             |1344      |9.673410431465864   |
|70        |69        |69             |126            |63             |1400      |6.965651630622664   |
|75        |73        |48             |127            |63             |1500      |5.827882278103885   |
|101       |93        |19             |130            |63             |1919      |3.723297411059034   |
|127       |112       |12             |125            |63             |2413      |3.0018183401530623  |

User parameters:
|l2_norm   |frac_bits |dimension |chunk_len |field     |proofs    |r         |r_succ    |-log2(eta)|-log2(zk) |-log2(wr_sound)     |-log2(gadget_sound) |
|:---------|:---------|:---------|:---------|:---------|:---------|:---------|:---------|:---------|:---------|:-------------------|:-------------------|
|1         |15        |1000      |49        |Field64   |2         |64        |64        |134       |128       |64                  |106                 |
|1         |15        |1000      |49        |Field128  |1         |64        |64        |134       |128       |64                  |117                 |
|1         |15        |10000     |107       |Field64   |2         |64        |64        |134       |128       |64                  |106                 |
|1         |15        |10000     |107       |Field128  |1         |64        |64        |134       |128       |64                  |117                 |
|1         |15        |100000    |318       |Field64   |2         |64        |64        |134       |128       |64                  |105                 |
|1         |15        |100000    |318       |Field128  |1         |64        |64        |134       |128       |64                  |116                 |

------- Target soundness error: 2^(-80)
Wraparound check parameters:
|r         |r_succ    |-log2(eta)     |-log2(zk)      |-log2(sound)   |overhead  |alpha               |
|:---------|:---------|:--------------|:--------------|:--------------|:---------|:-------------------|
|80        |80        |134            |127            |80             |1680      |9.673410431465864   |
|86        |85        |69             |126            |79             |1720      |6.965651630622664   |
|92        |90        |48             |127            |79             |1840      |5.827882278103885   |
|146       |131       |12             |122            |79             |2774      |3.0018183401530623  |

User parameters:
|l2_norm   |frac_bits |dimension |chunk_len |field     |proofs    |r         |r_succ    |-log2(eta)|-log2(zk) |-log2(wr_sound)     |-log2(gadget_sound) |
|:---------|:---------|:---------|:---------|:---------|:---------|:---------|:---------|:---------|:---------|:-------------------|:-------------------|
|1         |15        |1000      |53        |Field64   |2         |80        |80        |134       |127       |80                  |106                 |
|1         |15        |1000      |53        |Field128  |1         |80        |80        |134       |127       |80                  |117                 |
|1         |15        |10000     |108       |Field64   |2         |80        |80        |134       |127       |80                  |106                 |
|1         |15        |10000     |108       |Field128  |1         |80        |80        |134       |127       |80                  |117                 |
|1         |15        |100000    |319       |Field64   |2         |80        |80        |134       |127       |80                  |105                 |
|1         |15        |100000    |319       |Field128  |1         |80        |80        |134       |127       |80                  |116                 |
junyechen1996 commented 8 months ago

Squashed.