On the Hp hash choice in the Cryptonote
This is a continuation for the previous post.
As stated in the Cryptonote whitepaper,
We defined Hp as deterministic hash function from E(Fq) to E(Fq). None of the proofs demands Hp to be an ideal cryptographic hash function. It’s main purpose is to get a pseudo-random base for image key I = xHp(xG) in some determined way.
Let’s look closer, what the deterministic Hp has to be in the Cryptonote, and what it shouldn’t be.
Anonymity in the Cryptonote with the Hp
The main anonymity-breaking attack, that the Hp defends from, is when Alice sends multiple transactions to Bob, keeps a linear combination of the stealth P’s, then scans the blockchain for I’s falling under the same linear combination. Thus she links those I’s together and concludes they belong to Bob’s outgoing transactions.
Obviously, the Hp should always return different points for different P’s. Otherwise, if this is not the case, Alice can easily link two corresponding I’s together.
Moreover, in general sense:
For any set of different {Pi}’s generated for a fixed set {B}’s
of wallet public keys, there shouldn’t be computable tuple
(coefficients {ei}’s, some point E), such that:e1*I1+e2*I2+...+en*In=E
Otherwise, Alice would be able to link all these {I}’s together and, consequently, to link them with the {B}’s.
This means, for instance, that:
For any stealth P1 and P2 sent to B, the Hp shouldn’t return two
points that differ only by k*G, where k is computable from the data
known to Alice when she builds P1, P2.Suppose, that this is not so:
P1=a1*G+B
P2=a2*G+B, where a1 and a2 are shortenings
for the corresponding Hs(...) expressions.
Hp(P1)=Hp(P2)+k*GThen:
I1-I2=a1*Hp(P1)+b*Hp(P1)-a2*Hp(P2)-b*Hp(P2)=
=a1*Hp(P2)+a1*k*G+b*Hp(P2)+b*k*G-a2*Hp(P2)-b*Hp(P2)=
=a1*Hp(P2)+a1*k*G+b*k*G-a2*Hp(P2)=
=(a1-a2)*Hp(P2)+k*P1Letting e1=1, e2=-1, E=(a1-a2)*Hp(P2)+k*P1, Alice is able
to link I1 and I2 with B by checking: e1*I1+e2*I2=E.
Contradiction.
Thus, at least, for two P’s sent to the same wallet, the Hp(P) shouldn’t return values that differ only by computable k*G.
This property highly likely holds for the chosen Hp, although I haven’t check.
Anonymity for the schemes from the previous post
As far as I can see, the auditable wallet and the generalized schemes from my previous post are anonymous with that Hp that makes the original Cryptonote anonymous.
In other words, if the original Cryptonote is truly anonymous with certain Hp, then my schemes are anonymous too with that Hp.
To prove this, the same cases are to be considered for the extended sets, where {P}→{P}⋃{T} and {I}→{I}⋃{Ï}
Side note: another formula for the T, that simplifies interpretation of the auditable wallet scheme
Instead of T=Hs(r*D)*D, let’s define T as:
T=Hs((r+1)*A)*G+D, so that T=t*G, where t=Hs(a*(R+G))+d.
This has the following meaning: when Alice makes a payment to Bob, she simultaneously makes two standard Cryptonote transactions (as an atomic one). Namely, the first transaction she makes is to the stealth P=Hs(r*A)*G+B, and the second transaction is to the T=Hs((r+1)*A)*G+D.
Literally, making the output (P, T) she simultaneously sends the same funds to Bob and to the Bob’s wallet Auditor.
After that, Bob is always able to spend these funds by proving knowledge of b and d and providing key image tuple (I=x*Hp(P), Ï=t*Hp(P)).
At the same time, the Auditor is never able to spend these funds, as it doesn’t know b. However, looking at Bob’s proof the Auditor is able to see, that the (P, T) is spent.
All the other parts of the auditable wallet scheme and all formulas (with appropriate substitutions) remain as before.