COMP90088 (2022) Tutorial Week 9 Solutions
Idioms of use
In lectures, we saw CoinJoin as an example of decentralised mixing. This is an example where the join-control heuristic fails, because input coins should then be ideally controlled by separate entities.
In the diagram, the tall 3-to-3 transaction can be ruled out. By following change outputs, the top input is from an address controlled by Alice, and the bottom two are from addresses controlled by Bob.
Copyright By PowCoder代写 加微信 powcoder
Consider the transaction above transaction (1). The change is sent to an address controlled by Alice. Since that amount is then spent by a transaction that also outputs change, then its other input must also be controlled by Alice (if the other input was not controlled by Alice, then to whom would the change belong?). Therefore, Bob paid Alice in transaction (1).
It is not entirely clear who controls the bottom output of the tall 3-to-3 transaction. There- fore, it is not clear who paid Carol. The anonymity set for this payer includes Alice, Bob, and some unknown address holder.
Confidential transactions
A brief introduction on group theory concepts. Abstractly, our group G of prime order q contains a set of q elements, alongside the multiplication operation (× or · or omitted) which can be applied between two elements of the set such that the intuitive notions of multiplication apply:
• Closure: foralla,b∈G,wehavea·b=ab∈G.
• Associativity: foralla,b,c∈Gwehave(a·b)·c=a·(b·c)=abc.
• Identity: thereexistsauniqueelemente∈Gsuchthatforalla∈G,wehaveea=ae=a. This element e is often denoted as 1 when multiplication is the group operation.
• Inversion: for each a ∈ G, there exists a unique element denoted by a−1 (or sometimes a1 ) such that aa−1 = a−1a = e.
We also define exponentiation by repeated multiplication (which can be performed efficiently using the square-and-multiply algorithm, or via a Montgomery ladder if side-channel resistance is required), so we have amn = (am)n = (am)n = amn and we also define a−n = (a−1)n = (an)−1 for a ∈ G as expected.
We are also told that G is cyclic, meaning that there exists a generator g ∈ G such that all group elements can be expressed as a power of g. Therefore, we have G = e = g0, g1, g2, . . . , gq−1, containing q distinct elements as required. We are also told that h is also a generator. Since G is cyclic with order q, we have gq = g0 = e and similarly hq = h0 = e (intuitively because exponentiating g hits each of the q separate elements in G before cycling around back to g). Therefore, we only need to be interested in exponents modulo q of our group elements. Since G is cyclic, we get another property:
• Commutativity: for all a,b ∈ G, we have ab = gmgn = gm+n = gn+m = gngm = ba, for some m, n where g is a generator of G. You will sometimes see cyclic group described as ‘abelian’ because of this property.
It turns out that since q is prime, every non-identity element of G is a generator of G (intuitively because a non-identity group element never gets itself into a generating cycle whose length divides
q without equalling q, since q is prime). Also, since we only care about exponents modulo prime q of group elements, we can define the n-th root of a group element as such:
g1/n = g(n−1)
where n−1 is defined such that nn−1 = 1 mod q. This value n−1 is guaranteed to exist and be unique for non-zero n due to primality of q, and can be calculated efficiently via the extended Eu- clidean algorithm (or in Python: pow(n, -1, q)). Therefore having defined addition, subtraction, multiplication and division modulo q of the exponents of elements of group G, we can say that the exponents are elements of the finite field Fq, and from now on we implicitly take all operations on exponents to be modulo q.
One concrete example of group G is the set {1, 3, 4, 5, 9}, with multiplication modulo 11 as the group operation. Here, e = 1, any other element can serve as a generator, and q = 5 is prime. You may wish to check that all properties (closure, associativity, identity, inversion and commutativity) hold for this group. Inverses can be calculated with the extended Euclidean algorithm: 3−1 = 4 (in Python: pow(3, -1, 11) == 4) for example. We say that G is a prime-order subgroup of the multiplicative group of integers modulo 11. Alternatively, G is a prime-order subgroup of (Z/11Z)× .
Another example is a prime-order subgroup of an elliptic curve with over a prime field Fp, sometimes denoted E(Fp). In the literature you will often see the group operation as addition rather than multiplication, so the semantics are slightly different but the ideas are identical. With most of the elliptic curves you will see in cryptography, inverting a group element is trivial.
That is a lot to take in. The main point is that because of these various properties (cyclic G of prime order q), we are able to manipulate powers of abstract group elements in ways that match our school-level intuition of index laws.
a. We have:
where r5 ∈ Fq.
gx1 hr1 gx2 hr2
gx1 +x2 hr1 +r2 gx1+x2+z(r1+r2) gzr5 gr5
= gx3 hr3 gx4 hr4 hr5
= gx3 +x4 hr3 +r4 +r5
= gx3+x4+z(r3+r4+r5)
= gx1 +x2 −x3 −x4 +z(r1 +r2 −r3 −r4 )
= gr1 +r2 −r3 −r4 +z−1 (x1 +x2 −x3 −x4 )
=r1 +r2 −r3 −r4 +z−1(x1 +x2 −x3 −x4),
c. This is similar to what we had in part a.:
gxhr =gx′hr′ hr−r′ =gx′−x
(hr−r′ )(r−r′ )−1 = (gx′−x)(r−r′)−1 h(r−r′ )(r−r′ )−1 = g(x′ −x)(r−r′ )−1 h = g(x′−x)(r−r′)−1
Therefore, logg(h) = (x′ −x)(r−r′)−1 ∈ Fq (i.e. multiplication, subtraction and division are taken modulo q).
b. We have:
gx1 +x2 hr1 +r2 = gx3 +x4 hr3 +r4 +r5 hr1+r2−r3−r4−r5 = gx3+x4−x1−x2
h = g(x3+x4−x1−x2)(r1+r2−r3−r4−r5)−1 ,
so that logg(h) = (x3 +x4 −x1 −x2)(r1 +r2 −r3 −r4 −r5)−1 ∈ Fq. Part b. showed that knowing a solution to the DLP allowed us to legitimise transactions where the total output value was not equal to the total input value. Here we showed the reverse: where a valid proof for an invalid transaction allowed us to find a discrete logarithm. Therefore the security of confidential transactions is equivalent to the DLP.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com