Home Edition

Discussion notes #2.1: SoK - Lifting Transformations for Simulation Extractable Subversion and Updatable SNARKs

Presenter: Behzad Abdolmaleki

Authors:

• Behzad Abdolmaleki [e-mail]
• Sebastian Ramacher [e-mail]
• Daniel Slamanig [e-mail]

To be presented on 2020-04-23.

Resources:

• Latest PDF version
• Miro Whiteboard
• SoK Working Group
• Additional related links

---

Real-time notes

Note taker: Markulf Kohlweiss.

Others are welcome to augment/annotate using notes. Add your name. –-MyName

Problem statement:

Compiler of (Blackbox) Simulation-Extractable Subversion SNARK from SNARK that is knowledge sound (or whitebox simulation-extractable) that preserves subversion ZK and updatable CRS property.

Two compilers are presented:

1. Optimized version of C0C0
2. Independent and even better compiler

Background:

• zk-SNARKs: Groth16 state of the art
• subversion security: BFS16, ABLZ17, Fuc18
• updatable SNARK: GKM+18
• (simulation) BB extractability: Folklore x in L and w encrypted
• simulation soundness: x in L or statement signed using authenticated one-tiem signing key
• C0C0: A comipler that given a sound NIZK for language
  $L$ lifts it to a NIZK for language
  $L^{\prime }$ that can achieve black-box simulation extractability. To do so, a prover needs to prove that for public
  $(x,c,p{k}_{sig},\mu ,\rho )$ he/she knows
  $(w,r,s,t)$ such that
  $c=Enc(w,r)\cap ((x,w)\in R_L)\cup (\rho =f_s(p{k}_{sig})\cap \mu =com(s,t))$
• [Bag19]: A compiler[BG90] (used also in COCO) to lift a subversion resistant SNARK [i.e., BFS16, ABLZ17, Fuc18] to a subversion-resistant nBB simulation extractable SNARK. The prover needs to prove that for public
  $(x,p{k}_{sig},\mu ,\rho )$ he/she knows
  $(w,s,t)$ such that
  $((x,w)\in R_L)\cup (\rho =f_s(p{k}_{sig})\cap \mu =com(s,t))$.

Updated the background about building BB simulation extractable zk-SNARKs (with COCO) or building nBB simulation extractable subversion-resistant SNARKs (with [BG90] technique, [Bag19]). Karim Baghery

First compiler: OC0C0

Uses fixed-value key-binding PRF

Hard to find values such that

$f_s(x)=f_{s_0}(x)$.

Second compiler: Lamassu

Can also transfer Subversion resistant and Updatable CRS SNARKs

Uses updatable signatures than can be 'build' from key-homomorphic signature.

Updatable signature is unforgeable if either the original public key was honest or one of the updates was honest.

Either

$x\in L$ or

$p{k}^{\prime }$ is randomization of

$pk$. Sign

$p{k}^1$ using

$s{k}^{\prime }$ and

$x$ using

$s{k}^1$.

Question, why not sign x directly with

$s{k}^{\prime }$?

Q: Where do transparent proof systems fit in?

A: They live in a different model

Q: Is the point to prevent practical attacks or achieve provable security

A: It could also prevent the recent practical attacks but mostly it is provable security. This is not expensive, and assumptions are not worse than those already used by SNARKs.

---

Charter Ideas

Goals:

• add this document to reference documents (?)

Milestones:

• real work will happen in working groups, please join

---

Discussion topics

Suggestions welcome! Please append at the end, and the moderators will incorporate into the schedule.

~15 minutes each, by default.

(1) What are the challenges to obtain the updatability for the (o)coco approach?

Related question: how does simulation-extraction relate to UC security? Answer: BB simulation-extraction is equivalent to UC security. See. e.g. http://www0.cs.ucl.ac.uk/staff/J.Groth/NIZKGroupSignFull.pdf (Section 6.1, page 33) but also C0C0 paper.

Subversion ZK and BB extraction are (partly) contradictory. One can however base extraction on a common random string.

Tiramisu allows to build NIZK arguments that can achieve Black-Box Simulation Extractability in the updatable CRS model.

Mahdi Sedaghat

In terms of the black box (BB) extraction issue, indeed in Lamassu, we used non-BB extraction in both ZK proof (for extracting the trapdoor) and Knowledge sound proof (extracting the witness). But Trimusa (by adding encryption of the witness to the relation) can only guarantee a BB extraction in soundness proof (witness extraction) but not in ZK property and so I am not sure if it returns a fully BB extraction construction of NIZK in updatable CRS.

In general, I think our main motivation (and the challenge) of having BB extraction version of Lamassu is to achieve UC secure version of it but I do not think Tiramisu can solve this issue as it is assumed that the CRS is generated honestly (used F_crs functionality) to get the UC security and so I think we can not claim that it guarantees UC security in updatable CRS.

In terms of UC security, I see Trimusa added an updatable encryption of the witness to the Lamassu construction and claimed that it can get UC security only for the proof generation where its UC proof relies on the CRS model and so it does not consider the updatibility property at all. Thus I wonder in the UC proof where "this updatibility property appears in the proof generation" when the CRS elements used in the proof came from a trusted party (or its corresponding ideal functionality F_crs) in its UC proof.
So it is not clear to me how it can achieve UC secure version (even in the proof generation) of it as I see no proof for that in the paper exept some explanition in section 5.

My understanding is that the technique of adding Enc(withness) to get BB extraction and so UC property works when the crs is generated honestly. i.e., COCO can convert SNARK (with nbb extaction) to UC secure SNARK since adding encryption of witness removes the need for knowledge assumption in soundness proof… but at the present of a valid CRS.

But in the updatable CRS, adding such Enc(witness) only can remove the use of knowledge assumption in soundness proof but still one needs some knowledge assumption (non-falsifiable assumption) for the trapdoor extraction in ZK proof and so in its corresponding UC proof. otherwise, Sim in UC proof can not simulate the proof and etc…
I think in updatable setting for the UC security if one would use F_crs instead of F_upd-crs, then it should somehow apply the updatibility property in the proof generation and then it could guarantee a UC secure proof generation.

An general comment about the technique of adding Enc(withness) and thesuccinctness, I think there might be an issue by adding encryption of the witness to Lamassu (as Tiramusa does) which it makes the construction non-succinct as the size of the proof grows by the size of the witness. (but Lamassu's aim is to get SE updatable or Sub "SNARK")

Behzad Abdolmaleki

Regards to the above explanation about Tiramisu, we would recommend checking the paper of Tiramisu once more. In the above explanation, there are some statements that are not precise.
For instance,

• "it is assumed that the CRS is generated honestly (used F_crs functionality)", Tiramisu does not assume CRS is generated honestly, it assumes one honest party has updated the CRS.
• "can only guarantee a BB extraction in soundness proof (witness extraction) but not in ZK property", Tiramisu achieves to the defined definitions in the paper, namely U-ZK and U-BB-SE.
• "I see Trimusa added an updatable encryption of the witness to the Lamassu construction", Tiramisu works stand-alone and currently there are several constructions that allow us to instantiate it, but we wrote only one ad-hoc instantiation and one recomended in Lamassu. Indeed, we observed that ad-hoc instantiations can result in more efficient constructions than the case one uses Lamassu.
• …

Karim Baghery

Related question by Yuval: Transferrability is a problem because of local setup. Answer: F_NIZK models transferrable proofs, consequently the ideal- and the real-world model similar properties, but "ideal" ZK should be non-transferrable. (?)

Rafael Pass: On Deniability in the Common Reference String and Random Oracle Model. CRYPTO 2003: 316-337

(2) Can we construct a black-box version of Lamassu that works with updatable and subversion SNARKs?

Referring to Figures 1 ant 2 in Tiramisu, one can construct a Black-Box version of Lamassu in the updatable CRS model.

Mahdi Sedaghat

(3) What are the challenges in achieving UC security?

A. Particularly about NIZK arguments, the proofs should be non-malleable and the scheme should achieve BB extractability (to give the possibility to the UC simulator to extract the witness from the corrupted parties). These are achieved with black-box simulation extractability.

Karim Baghery

(4) Can we construct other natural compilers that would be compatible with updatability/subversion?

(5) How can we ensure developers include the important information in the instance when using simulation-extractable SNARKs.

(6) Are we happy with the Lamassu choice of signature scheme. Would there be any benefit in avoiding signature schemes secure in the random-oracle model?

(7) Are we comfortable using Random Oracles and Knowledge-Extractor assumptions at the same time?