Discussion: Formalizing the Privacy Matrix for Security Analysis

[coinstudent2048]

We need to have a formalized version of the privacy matrix (pp. 3-4) for security analysis. So far, it is informal. For now, I don't know how to do this yet, but I already envision a master theorem like as follows:

If (<proof type 1> satisfies <insert security models properties here> and <Seraphis conditions for it>) and (<proof type 2> satisfies <insert security models properties here> and <Seraphis conditions for it>) and ..., then the resulting Seraphis instance satisfies the privacy matrix.

Being an abstraction, we do not need to focus on specific proof systems: we just assume satisfaction of security models properties.

Expected to not be part of security analysis: features akin to multisig-friendliness, etc.

[UkoeHB]

I believe the CryptoNote whitepaper, RingCT, Triptych, and perhaps others, have explored a formal 'big picture' privacy matrix to some extent.

[coinstudent2048]

@UkoeHB Thanks! I will study the security properties in those papers (+ more I found) so that I can just use them (if appropriate) or at least 'derive' variants. I imagine the formal privacy matrix as also a set of security properties anyways.

...:thinking:

[coinstudent2048]

@UkoeHB Minor comments on notation (completely unrelated to this issue):

• I suggest to remove asterisks (*) in multiplication.
• Putting 1/x in "notations" section (as modular inverse).
• The "without exponents" thing is usually called "Additive notation".
• Typo: Membership proofs -> # 2 -> a_{i, 2} G_2 should be a_{1, 2} H_2.

EDIT: Omniring paper has (almost?) exactly what we need! In Section 3 they defined 3 security properties of RingCT: balance, privacy, and non-slanderability, aside from the usual correctness. They defined more in the Appendix B. In Section 4.3 "Analysis" they have theorems like my envisioned "master" theorem. Sweet! 🧁

Though the math looks like a big mess to me right now, so I need careful reading...

[UkoeHB]

Re: Notation

Thanks! I have been using asterisks * to improve visual clarity for ugly scalar multiplications.

[UkoeHB]

@coinstudent2048 I updated the Notation section with your suggestions, let me know if I am going in the right direction!

[coinstudent2048]

@UkoeHB asterisks is now alright, as long as there is now clarification, although I still prefer no asterisks.
I am now starting formulating security properties based on formalizations in Omniring paper. It will likely take a while before I will put something in my writeups repo.

Then I will suggest further in writing style...

In any case if this would be submitted in iacr, then afaik there is a required template (which looks like the Triptych paper). (See below reply)

[UkoeHB]

@coinstudent2048 IACR has very limited requirements for submission.

[coinstudent2048]

Update: I have not yet formulated the security properties for Seraphis as a whole, but I have security properties of individual components:

• Membership proofs / Ring signature: Correctness, Unforgeability, and Anonimity (found on Triptych paper). The part "The proving system should be considered unusable if" is very similar (if not the same) to Anonimity! From Triptych,

Anonymity requires that as long as a ring contains at least two members that have not been corrupted, an adversary can do no better than guessing at determining the signer of an honest signature.

• Ownership and unspentness proofs: (Honest verifier) ZK Proof of Knowledge. Schnorr-like proofs satisfy this.
• CT / Peterson Commitment: Perfectly hiding, Computationally binding (of course).
• Range proof: (Honest verifier) ZK Proof of Knowledge. Bulletproofs+ satisfies this.

Again, since Seraphis is an abstraction, the security properties above are assumptions. Now I need to formalize Seraphis as a whole (e.g. tuple of algorithms), so that I can properly formalize our security properties. Hope I am not delayed...

Lastly, more suggestions on notation and format:

• You can use |S| instead of size(S) for the cardinality of S, although I do not know if this notation is common outside set theory, combinatorics, and related fields.
• In membership proofs section, tuple (A, B) instead of tuple {A, B} (confused for set notation), although maybe {A, B} is still fine, I don't know.
• For the "smaller" abstract format, use \begin{abstract} and \end{abstract}.
• Remove the question in the intro. Simply starting with "A p2p (peer-to-peer) electronic cash system is a monetary system..." is just fine (at least for me).
• In notations section, 'denoted like' --> 'written as' or 'denoted by' (?) (I am not a native speaker; I am quite confused by what 'denote' means).

[UkoeHB]

Thanks! I updated with several of your suggestions.

Remove the question in the intro. Simply starting with "A p2p (peer-to-peer) electronic cash system is a monetary system..." is just fine (at least for me).

I will leave this for now. I think it helps set the right pacing/cadence for this section.

In notations section, 'denoted like' --> 'written as' or 'denoted by' (?) (I am not a native speaker; I am quite confused by what 'denote' means).

'Denoted' means 'how the concept is symbolized'. I will update that part to be more clear in the next draft.

Regarding Seraphis as a whole, I refactored the main section to be agnostic to the generators chosen. Please take a look through and let me know what you think (I also moved some implementation details to later sections).

[coinstudent2048]

@UkoeHB The consistent C <-> H and K <-> G for group elements is nice!

I found the square brackets for tuple quite weird. The use of parenthesis for tuples makes it consistent with multivariable function notation f(x,y,z). However, leave this for now because tuple notation is not consistent from paper to paper (others use angle brackets like <x,y,z>) 😖 . Math notation can be messy.

Btw, Lelantus Spark has preprint now: https://firo.org/blog/assets/Lelantus_Spark_230821.pdf . They are also working on protocol security proofs, similar to what I am trying to do right now.

[UkoeHB]

I found the square brackets for tuple quite weird. The use of parenthesis for tuples makes it consistent with multivariable function notation f(x,y,z). However, leave this for now because tuple notation is not consistent from paper to paper (others use angle brackets like <x,y,z>) 😖 . Math notation can be messy.

I decided not to go with parentheses because the paper already has a lot of parentheses. In terms of 'quality of reading', it is better to mix things up sometimes. Also, it is better to avoid using parentheses for math in the middle of text because it can be confusing whether you are describing a tuple or just adding parenthesized text (like this :p).

Btw, Lelantus Spark has preprint now: https://firo.org/blog/assets/Lelantus_Spark_230821.pdf . They are also working on protocol security proofs, similar to what I am trying to do right now.

Yep I decided to generalize Seraphis like this so Spark qualifies as an instantiation of Seraphis :). If you read closely, you will see they satisfy all of the Seraphis proof requirements and e-note/e-note-image structures.

[coinstudent2048]

If you read closely, you will see they satisfy all of the Seraphis proof requirements and e-note/e-note-image structures.

Yep, I see. This makes my analysis/result more interesting!

Maybe put the notation section before public parameters, and remove specific objects. Something like this:

• We use capital letters like G, H for group elements, and small letters like k,t,a for scalar field elements. We use additive notation for group operations, which means that the binary group operation is denoted G+H, and no exponent blablabla. Also, xP or x*P for scalar multiplication blablabla... Lastly, (1/x)*P modular multiplicative inverse blablabla...
• We denote a tuple of objects like this: [Obj_1,Obj_2,Obj_3,...]. However, we still indicate that it is a tuple to prevent confusion with interval notation like [0,1].

This is so that readers are aware of specialized notation.

[UkoeHB]

Maybe put the notation section before public parameters, and remove specific objects.

I updated the notation section again. It seems useful to describe specific points in the public parameters section, but I am open to being persuaded these need to move to other sections.

I also added an appendix for a proof structure that satisfies the Seraphis ownership/unspentness requirements. It probably needs a lot of beating to get it in shape.

[coinstudent2048]

No, It's fine to describe specific objects in the public parameters. In my suggestion for the notation section to be moved, there are no specific objects, just the words "group elements" and "scalars". That's what I mean by "removing specific objects". Sorry for not being clear. I also suggest moving the notation because the public parameter section already uses the tuple notation.

For specific proving systems, I am sorry I will do the overall security analysis first. I'll just say that as long as it is "Schnorr-like", I expect Honest Verifier ZK (I just knew ✨ how to prove something like this) :D.

[coinstudent2048]

@UkoeHB Is it possible to have a generalization for "Information recovery" (Section 4.6)? I am thinking of plain ECIES (basically Diffie-Hellman + Symmetric Encryption). What do you think?

I need this to 'wrap up' everything. I actually find defining security properties more difficult than proving them.