Discussion: linking tag uniqueness

[UkoeHB]

@coinstudent2048 Wrote a short proof that linking tags are uniquely defined by one-time addresses if the DL assumption is held.

[coinstudent2048]

Regarding the "two DL breaks and two OTA breaks." I will delve into the formalism to see if this is allowed. While with hopium, I think Wikipedia says something like "if a successful attack is repeated a polynomial number of times, the success probability of the overall attack still remains negligible."

Source: https://en.wikipedia.org/wiki/Negligible_function#Use_in_cryptography

[coinstudent2048]

Updated paper (same link): Yes, usage of two breaks (or any finite number, generally) is allowed :partying_face: (see Lemma 1.1).

[UkoeHB]

Sounds good, thanks! I will let this marinate for a couple weeks, then incorporate it into the paper.

Do you have a name/pseudonym and email address I can add to the author list?

[coinstudent2048]

@UkoeHB Thanks! I am still contemplating if I'll give my real name, but for now, "coinstudent2048" (if this is allowed). Email: coinstudent2048@protonmail.com .

I will formalize the assumptions later on, but basically it says something like "the probability of attack success w.r.t security parameter λ, Prob(λ) is negligible (or equivalently, less than some negligible function negl(λ))."

I will study the Omniring paper, as suggested by Sarang. From the looks of it, it has several security models that can be used for analysis.

Probably, I'll also help in "academic" writing style, but just small edits.

EDIT: Even if the theorem turns out to not be useful, the technique is widely applicable. "X assumption easy => DL assumption easy" is more difficult (but not too much) and important than the other direction, which is actually trivial oftentimes.

[coinstudent2048]

Updates (same link):

• Added new theorem (second page). this takes care of the following in Section 4.3.2 "Linking Tags":

  This means for a user to create two distinct linking tags from the same address, they must be able to solve the DLP between generators U and G, which we assume to be a hard problem.

Very likely this would useful on other parts of Seraphis.

Sender-receiver anonymity (only in Section 4.3.1) is just DLP on K^'o - K^o base G (assuming t_c & t_k independent and randomly... uniform blablabla), so no need for proof.

• Took care of pesky divide-by-zero cases.

Very likely there would be new theorems when I analyze the other parts. However, I will be busy in 2 weeks starting tomorrow (job-related) ;-; . I will still try to update if time allows.

For the TeX: https://github.com/coinstudent2048/writeups

[coinstudent2048]

@UkoeHB I am sorry this can be confusing:

• My new second theorem directly implies that finding any non-trivial solution k_a & k_b to K=k_a*U+k_b*G is as hard as DLP.
• My first theorem directly implies that given the linking tag, finding the (unique) solution k_a & k_b to K=k_a*U+k_b*G is still as hard as DLP. Note that this uniqueness did not come from DLP; instead the uniqueness is trivially implied from the definition of f. This theorem actually implies that if she has all of the K, the linking tag, and k_a & k_b, and those truly satisfy the equations, then we are pretty sure that she got k_a & k_b first, and then computed K and the linking tag, not the other way around.

I think those two theorems (+ trivial ones above) complete the security analysis only for address and linking tag. Of course the addition of proof systems can affect the theorems. Now I will open another issue for outlining the analysis of Seraphis.

[UkoeHB]

@coinstudent2048 I started building C++ protocol mockups for benchmarking. My plan is to benchmark a wide range of protocols and test variables, so it will probably take me at least a couple weeks to finish coding and getting test results.

Once benchmarking is done, I will focus on completing the paper. The remaining parts are the efficiency section and security modeling/proving/etc. (which you have been working on - thanks!).

That is to say, the promised 2 weeks is being extended a bit...