id matching systems. In: Workshop on Privacy in the Electronic Society (2006)

13. Nohl, K., Evans, D.: Quantifying information leakage in tree-based hash protocols

(short paper). In: ICICS, pp. 228“237 (2006)

14. Suh, G.E., Devadas, S.: Physical unclonable functions for device authentication

and secret key generation. In: DAC, pp. 9“14. IEEE, Los Alamitos (2007)

15. Tuyls, P., Batina, L.: RFID-tags for anti-counterfeiting. In: Pointcheval, D. (ed.)

CT-RSA 2006. LNCS, vol. 3860, pp. 115“131. Springer, Heidelberg (2006)

16. Vaudenay, S.: On privacy models for RFID. In: Kurosawa, K. (ed.) ASIACRYPT

2007. LNCS, vol. 4833, pp. 68“87. Springer, Heidelberg (2007)

A Security Proofs

Completeness

In our scheme, errors could occur because of collisions in the output of the hash

T T T

function. For instance, a part of a communication (ai’1 , H(ai’1 , ri ), ri • Ki )

T

could lead to an error when for a tag T , we get the equality H(ai’1 , ri ) =

T T T

H(ai’1 , ri • Ki • Ki ). This could appear with a probability at most 2Q . lH

Because there are d stages, the overall probability to fail in the identi¬cation is

O( 2lH ) which is negligible in the parameters.

dQ

Soundness

We ¬rst remark the following. Let us de¬ne a family of functions Ha,b derived

from H. b is a bit string of size lb . Ha,b is a function from {0, 1}lb to {0, 1}lH such

that Ha,b (x) = H(a, b • x). As H is preimage resistant, we can consider that an

adversary has a negligible probability to ¬nd a preimage of Ha,b (x) whatever a

and b are. If there are polynomially many ai and bj , an adversary has a negligible

probability to ¬nd x even if he knows Hai ,bj (x) for all ai and bj .

Now, we denote L1 the list of all the communications produced via the

SendTag queries, L2 the communications sent to the TC either with the

SendTC query or the Result query.

To simplify the notation, we prove that the scheme is sound with d = 1. This

is a su¬cient condition, as the di¬culty to authenticate increases with d. We

denote M , the maximum number of operations made by A.

Assume A has received the challenge aTC and outputs the couple (a1 , x1 ). We

0

overestimate the probability of success of A. There are two cases:

“ Case 1: A did not use H to output a1 . This means:

• either aTC had been tested by A thanks to the SendTag query, this

0

M

could arise with a probability less than 2lr ,

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

Table 1. Resources needed in the ¬rst case

Tag ’ TC TC

Tag

numbers non-volatile computation communication computation

memory

20

2 — 210

2 200 bits 2 AES and 2 random 328 bits

230 3 — 210

300 bits 3 AES and 3 random 492 bits

• or he tried a random answer. In this sub-case, he has a probability of

success less than M.Q thanks to the collision resistance property.

2lH

“ Case 2: A used H to output a1 . So we denote a1 = H(aTC , x1 ). This means

0

• either there is no key K like x1 = x1 • K. The probability of success is

ˆ ˆ

thus less than M.Q ,

2lH

• or there is a key K in the key material such that x1 = x1 • K. Conse-

ˆ ˆ

quently A possesses one key. He could achieve this only using the infor-

mation from L1 and L2 . A only knows triplets of the form a0 , H(a0 , rT ),

rT • K T for some tags T . A change of variable leads to: a0 , Ha0 ,rT (K T ),

rT . Thanks to the previous remark on preimage resistance property, we

can conclude that the probability A got one key is negligible.

We can conclude that our scheme is sound as the overall probability of any

adversary is negligible.

B Practical Example

We propose for our protocol, as an example, the following parameters:

“ the size of the reader challenge lr is 64,

“ the size of any POK lK is 100

“ the size of the output of H lH is 64.

For instance, the ¬rst 64 bits of AESai’1,1..28 ||ri (ai’1 ||ri,1..64 ).

They have been chosen to minimize the non-volatile memory inside the tag and

the communication between tags and readers, but they should lead to a su¬cient

security to insure the secrecy of the keys and the impossibility to authenticate

without the knowledge of the keys. We use AES as it is possible to implement

it with not too many gates and because the problem to ¬nd a preimage or any

collision is usually believed intractable.

Security can be improved by increasing the parameters:

“ the size of the reader challenge lr is 64,

“ the size of any POK lK is 116

“ the size of the output of H lH is 64.

For instance, the ¬rst 64 bits of AESai’1,1..12 ||ri (ai’1 ||ri,1..64 ).

The two tables Table 1 and Table 2 summarize the concrete resources used in

our scheme in the two previous cases for some example parameters. We use a

branching factor of 210 in all cases.

Improved Privacy of the Tree-Based Hash Protocols 91

Table 2. Resources needed in the second case

Tag ’ TC TC

Tag

numbers non-volatile computation communication computation

memory

20

2 — 210

2 232 bits 2 AES and 2 random 360 bits

30

3 — 210

2 348 bits 3 AES and 3 random 540 bits

Two Generic Constructions of Probabilistic

Cryptosystems and Their Applications

Guilhem Castagnos

GREYC, Ensicaen,

Boulevard Mar´chal Juin, BP 5186, 14032 Caen cedex, France

e

guilhem.castagnos@info.unicaen.fr

Abstract. In this paper, we build, in a generic way, two asymmetric

cryptosystems with a careful study of their security. We present ¬rst an

additively homomorphic scheme which generalizes, among others, the

Paillier cryptosystem, and then, another scheme, built from a deter-

ministic trapdoor function. Both schemes are proved semantically se-

cure against chosen plaintext attacks in the standard security model and

modify versions can be proved secure against adaptive chosen ciphertext

attacks.

By implementing these constructions with quotients of Z, elliptic

curves and quadratic ¬elds quotients we get some cryptosystems yet

described in the past few years and provide variants that achieve higher

levels of security than the original schemes. In particular, using quadratic

¬elds quotients, we show that it is possible to build a new scheme se-

cure against adaptive chosen ciphertext attacks in the standard security

model.

Keywords: Probabilistic Encryption, Homomorphic Scheme, Generic

Construction, Paillier Cryptosystem, Quadratic Fields, IND-CPA and

IND-CCA2 security, Standard Model.