Transaction method between two entities providing anonymity revocation for tree-based schemes without trusted party

1. Transaction method of transmitting anonymous electronic cash between a first entity (U) identified by a public key (pk u ) and a second entity (M) for providing anonymity revocation comprising:

storing a divisible coin of value n L in an electronic device;

assigning the divisible coin of value n L to a tree of L+2 levels, each node having exactly n direct descendants except the n L+1 leaves (at level L+2), such that the value of the tree root at level 1 is n L , the nodes of levels between level 2 and level L+1 each have a value corresponding to 1/n of the value of their parent node, and the nodes of level L+2 have no value;

constructing a root key (K 1 ) associated with the root node of the tree by using a secret (s) known by said first entity (U);

computing respective node keys (LKey, RKey) for the n direct descendant nodes of a parent node, by using a verifiable one-way function (F), wherein said computed keys (LKey, RKey) for said n direct descendant nodes are unlinkable between them without the knowledge of the parent node key;

generating a ciphertext (T) in the electronic device by encrypting the public key (pk u ) associated with the first entity (U) with the key of a selected node of a fraction of the divisible coin of electronic cash to be transmitted to said second entity (M) by using a verifiable randomized encryption scheme (E); and

transmitting, from the electronic device to said second entity (M), a fraction of the divisible coin of electronic cash with said ciphertext (T), the keys of the direct descendants of the selected node and a proof (Φ) of validity of a correct computing of said ciphertext (T) and said keys of said direct descendants.

2. Transaction method according to claim 1 , wherein said root key (K 1 ) is constructed by using a one-way function (G).

3. Transaction method according to claim 1 , wherein said secret (s) is given to said first entity (U) in a blind manner by a third entity.

4. Transaction method according to claim 1 , wherein said randomized encryption scheme uses a random value (R) transmitted by said second entity (M) to said first entity (U).

5. Transaction method according to claim 4 , wherein said public key (pk u ) and said random value (R) are encrypted.

6. Transaction method according to claim 1 , wherein n is equal to 2.

7. Portable object comprising:

an electronic device having a memory for storing a divisible coin of value n L ; and

a processor able to generate a tree of L+2 levels assigned to the divisible coin of value n L , each node in the tree having exactly n direct descendants except the n L+1 leaves (at level L+2), such that the value of the tree root at level 1 is n L , the nodes of levels between level 2 and level L+1 each have a value corresponding to 1/n of the value of their parent node, and the nodes of level L+2 have no value;

said electronic device further computing and storing thereon:

a key (K 1 ) associated with the root node of the tree by a secret (s) only known by a first entity (U) identified by a public key (pk u ) and associated with the electronic device;

respective node keys (LKey, RKey) for each direct descendant node of a parent node, wherein said computed keys (LKey, RKey) were created by using a verifiable one-way function (F), such that, said direct descendant nodes are unlinkable between them without knowledge of the parent node key;

a ciphertext (T) generated by encrypting the public key (pk u ) associated with the first entity (U) with the key of a selected node of a fraction of the divisible coin of electronic cash to be transmitted to a second entity (M) by using a verifiable randomized encryption scheme (E).

8. Portable object according to claim 7 , wherein said object is a smart card.