T

POKs, we once more use Gen. For each Ki , Gen(1lc ) outputs a challenge c. This

challenge is hard-wired with the PUF and outputs PUF(c) = KiT . The couple

of POKs associated to the key Ki is (KiT , Ki T = KiT • Ki ). As the PUF is

T T

considered to be a perfect random-function, KiT and Ki T are considered to be

random values of entropy lK . This means that the knowledge of only one of these

T

values does not reveal anything on Ki .

6.2 The Protocol

ˆj

In Fig. 2 is the description of our new protocol, where Ki denotes the key at

the depth i on the j th branch of the tree. The TC sends to the tag a challenge

T

a0 , which is a random value. The tag T computes a random value r1 and sends

a1 = H(a0 , r1 ). The tag switches on the ¬rst POK to get K1T and computes

T

A = r1 • K1T . This operation erases in volatile memory r1 . The second POK

T T

is switched on to get K1 T , and this erases K1T . Finally the tag computes A =

Improved Privacy of the Tree-Based Hash Protocols 85

Tag T TC

a

’ ’0 ’ ’

← ’ ’ ’ pick a0

T

pick r1

T

a1 = H(a0 , r1 )

The ¬rst POK is

switched on to get K1T

A = r1 • K1T

T

The second POK is

switched on to get K1 T

A = A • K1 T

T T

= r1 • K1

a1 , r T •K T

’ ’ 1’ ’ ’

1

’’ ’ ’ ’

. .

. .

. .

T

pick rd

T

ad = H(ad’1 , rd )

.

.

.

ad , r T •K T

’’ ’ ’ ’

’ ’ d’ ’ ’

d

f or i = 1 to d

f or j = 1 to Q

j ˆj T T

ri = Ki • ri • Ki

j

if ai = H(ai’1 , ri )

then go to the next stage

associated to the found key

end f or

if no match, fails

end f or

Fig. 2. The Identi¬cation Protocol

A • K1 T and sends r1 • K1 . The tag picks a random value r2 and computes

T T T

T T T

a2 = H(a1 , r2 ) and sends it to the TC. It computes r2 • K2 using the same

tricks as before. It repeats these operations d ’ 1 times.

ˆj

Then the Trusted Center (TC) tries amongst all the key K1 in the tree™s ¬rst

T T ˆj

level whether it gets the equality H(a0 , r1 • K1 • K1 ) = a1 . If it ¬nds one

correct key, it searches the next key amongst the possible keys in the tree. If the

operation is successful for the d levels then the tag is authenticated.

This protocol has all the advantages of the Tree-Based Hash protocols: it

allows delegation and to have less computation for the TC than the exhaustive

search but with an increased time of computation for the tag.

86 J. Bringer, H. Chabanne, and T. Icart

7 Security Analysis

T T T T

In our protocol, SendTag outputs (a1 , r1 • K1 , . . . , ad , rd • Kd ) and Result

T T T T

returns whether the 2d + 1-tuple (a0 , a1 , r1 • K1 . . . , ad , rd • Kd ) is correct.

Restriction on the Corrupt Query Due to POKs

7.1

In our case, we make the hypothesis that corrupting a tag T leads an adversary

to the knowledge of only one of the three possible type of sets:

T T

1. ai’1 , ri and ai = H(ai’1 , ri ),

2. ai’1 , ri , ai = H(ai’1 , ri ) and ri • KiT ,

T T T

3. ai’1 , ai = H(ai’1 , ri ), ri • Ki T and ri • Ki .

T T T T

Note that in the two ¬rst cases, an adversary does not learn the ¬nal output.

Thanks to the possible actions of the adversary as de¬ned in Sect. 3.1, we can

prove:

Theorem 1. Corrupt queries leak at most as many information on the key

material as SendTag queries.

T T

Proof. Getting ai’1 , ri and ai is trivially of no interest. Getting ai’1 , ri , ai and

ri • KiT is equivalent as getting ai’1 , ri and KiT . As KiT is a random value of

T T

T

maximal entropy lK , this leaks no information about Ki . Finally, getting ai’1 ,

ai , ri • Ki T and ri • Ki is equivalent as getting ai’1 , ai , Ki T and ri • Ki .

T T T T T

Because Ki T is a random value of entropy lK , this is equivalent as getting ai’1 ,

T T

ai , and ri • Ki which is exactly a part of an output of a SendTag query. 2

In the sequel, we do not distinguish Corrupt from SendTag in proofs.

Remark 1. Formalizing Corrupt this way is convenient for our model and our

proofs. The reality behind this formalization is still an open implementation

issue. More concretely, the ability of an adversary to obtain a key from a POK

without destroying the tag has to be evaluated precisely. This topic is however

outside the scope of this paper.

7.2 Completeness and Soundness