Bodies on Trial: Performances and Politics in Medicine and Biology

Introduction

Marc Berg and Madeleine Akrich

Body & Society, 10, pp. 1-12. This special issue, devoted to the question of the body in medicine and biology, brings together a group of authors whose roots lie within the field of science and technology studies (STS), and at the intersections of STS with medical sociology and medical anthropology. As testified by the vitality of Body & Society, 'the body' is in the center of revived attention in the social sciences and humanities. Medical sociology and anthropology has produced important contributions to the renewal of the body's conceptualisation 1 , and feminist studies have put the construction of 'sex' and its relationships to gender center stage. 2 Some authors even argue that social theory should be re-centered around the notion of 'embodiment' or a similar concept. 3 What kind of insights can STS studies bring into this set of interrogations? Briefly said, STS approaches may help escape the pull between two powerful theoretical/philosophical positions that have, for some time, been at work in conceptualizing the body: phenomenological approaches on one side, and constructivist approaches on the other.

The field of STS gained momentum in the 1980s by turning empirical research methods on the production of scientific facts. Taking an 'agnostic' stance, ethnographers entered laboratories and started to investigate 'science in the making'. Directly questioning traditional philosophical viewpoints on the epistemological uniqueness of 'doing science', these researchers argued that the attribution of this unique epistemological quality was a thoroughly social process. 4 This reinterpretation of the nature of scientific development subsequently led to increased attention to the social nature of technological development, the place of scientific expertise in policy making, science policy, medical sociology, and so forth. Among these lines of investigation, one strong strand has most potential to contribute to discussions on the 'body': those approaches that have focused on the materiality of technoscientific practice. Starting with a deep interest in the ways experiments and technological development are social practices yet cannot be simply reduced to social interactions, many authors have started to investigate the very nature of 'matter ', 'objects' and 'embodiment'. 5 Centralizing 'embodiment' without presupposing an a-historical, biologically grounded 'body' is, of course, already a familiar challenge in studies of the body. 6 Yet starting from its interest in technoscientific objects, STS has emphasized the central role of 'objects' and 'materiality' in any viable social theory. It has emphasized the material heterogeneity of the networks that constitute society, and has stressed the active, mediating role of objects and artefacts in shaping categories previously deemed to be 'purely social': human interactions, organizations, professions, expertise, and so forth. 7 STS's emphasis on the material heterogeneity of practices and its struggle with the concurent historicity and durability of 'objects' and 'matter', when applied to the body 8 , provides the analyst with theoretical tools allowing to meet the challenge drawn by Donna Harraway: to acknowledge the body's active status as agent without implying its immediate, pre-fixed presence, in other words considering it as a 'material-semiotic generative node' which is fundamentally both discursive and material, both historical and real (Haraway 1991, 197-201). 9

A second distinctive feature of STS, its agnosticism, gives it a potent recourse when confronted with the body question: STS does not need, and even actively refuses, to make any hypothesis about the nature of the objects it studies. On the contrary, it considers this 'nature' an empirical question. In this perspective, the analysis does not privilege any 'kind' of body over the others, the body as represented in scientific discourse, the body as experienced by the patient, the body as locus of medical practices, the body as inscribed in medical records, etc. Instead it tries to trace the intricacy of all these bodies, describing how each 'body 'is specifically connected to a set of practices, material devices and rhetorical genres, which include modalities defining the way it relates to other 'bodies '. 10 In this special issue, thus, we are first of all committed to bracketing out pre-fixed notions of what a body might be, and how it might be delineated. As just pointed out, these notions should not be seen as the starting point of a theoretical analysis, but as the empirical result of practices, as the effect of the development of specific networks [START_REF] Callon | Agency and the Hybrid Collectif[END_REF]. What we attempt to do here, then, might be summarized as investigating whether a reconfigured notion of 'embodiment' might serve as a fruitful bridge between the historical specificity of bodies and the lived, 'first person' experience of having/being a body.

Embodiment, so we would claim, can be seen as a process rather than as a pre-given biological fact; it can be empirically studied as the outcome of historical processes rather than posited as the elementary starting point for social theorizing. Redefined in this way, embodiment points both at the process of the emergence of a specific (concept of the) body, and at the real-time having/being of this body. This process can be conceptualized as a series of trials, as emergences of specific characteristics in and through the confrontation with features of the network of which the emerging body is a part.

To unravel the multitude of issues that are at stake in such an approach, this special issue is divided into three parts. The first part, Performing Bodies, focuses on the production and performance of bodies within medical and biological practices. The three articles elaborate a performative notion of 'bodies' and 'embodiment'. This implies the already mentioned notion that 'the body' and 'body boundaries' are not taken as selfevident, a-historical concepts, but that they are seen as historically constructed. It makes no sense to try to debate the essential nature of the body, or, for that matter, to implicitly posit a pre-existing 'wholeness' of the body which is subsequently undone and reduced through for example 'medical technology' (cf. Berg andMol 1998, Komesaroff (1995)). The ontology of bodies is exactly what is taken to be an empirical matter -the outcome of the trials. In their study, for example, Marc Berg and Paul Harterink argue that Foucault's modern, medical body might have been a reality in research practices at the beginning of this century, but that it certainly did not figure in the everyday medical wards and offices of that time. The emergence of this body in clinical practice, they argue, was closely tied to the emergence of a technology that stands central in its performance: the patient centered medical record. Berg and Harterink argue that this body is the effect of a historical development, and that it is in fact a modest medical technology such as the medical record that has helped create it. This construction of bodies and body boundaries, moreover, is not something that has been done and is now achieved. The notions of 'performance' and 'embodiment' can be seen to point at the ongoing nature of the process: these are entities that have to be continually performed and maintained for them to persist. Bodies, Annemarie Mol and John Law argue in their article on the performance of hypoglycaemia, are enacted. Their specific reality stands or falls with the active presence of devices, routines, modes of self-monitoring, and so forth. 'Bodies' are not interpreted, not pre-existing, not merely the concrete instantiation of 'larger' historical developments, but performed, in concrete practices and in highly specific ways.

In addition, bodies and body-boundaries are seen to be variable entities which can and are performed differently in different cultures, different practices, and sometimes even within one practice. Law and Mol, for one, stress that bodies as such hardly seem to come into play when one studies the performance of hypoglycaemia. They encounter blood samples, sugar levels and accounts of life styles -but these do not unequivocally sum up to any one 'body'. The 'body as a whole', like the unified Self and the very existence of a 'first person' perspective are not only achievements rather than a priori givens -they are only rare occurences. In a similar mode, Madeleine Akrich and Bernike Pasveer analyze women's narratives on the experience of giving birth. Drawing upon a situation in which the body is often considered as a 'naturally' acting entity, they display the long series of mediations, including technologies, that perform this acting body for the woman herself.

Instead of invariable body/self divides, they argue, narratives constitute varying dichotomies between a body and an embodied self, none of which is stable. Both Mol and Law and Akrich and Pasveer, then, stress that we cannot speak of 'the' body. We face, rather, a multiplicity of partial instantiations of bodies, whose interconnections are always tentative and never self-evident.

Finally, all the authors in this part share the notion that this performance is achieved by associations of heterogeneous entities. The notion of performance does not imply that someone or something is 'doing' the performance (cf. Butler 1993). Hypoglycaemia or childbirth is not 'performed' by individuals -as actors 'performing' roles -, nor is it 'produced' in 'discourse' (as a text 'speaking' its subjects). It is not a social construction, nor a text; things, practices, architectures play a core role in its construction (as is exemplified by Berg and Harterink's emphasis on the patient centered medical record). The body is 'done' by the practice of blood sugar measurement, for one, and by the midwife, the instruments in the delivery room, the partner, and so forth. Only in the interrelation of these entities does a specific body arise. 11 This implies that performance cannot be described as re-presentation in a formal sense: that is to say, 'performance', for the authors gathered here, is not the collective production and reproduction of pre-defined categories and social roles.

In the second part, Body as Mediator, the performance of specific bodies is no longer the primary point of attention. In this part, authors focus on how bodies are implicated in the production of biological knowledge (Despret), in the treatment of drug addicts (Gomart), and in the practices of organ procurement in 'living cadavers' (Lock).

Bodies, here, are by-product and mediator: they are one of the elements that come to play in the performances at stake, yet they can only be in that position because they are themselves affected by this performance. Some social scientists have criticized western medical practices as drawing upon and performing a dualist definition -body/mind -of the person. The different contributions presented in this part show that this dualist definition is not a permanent one, and that the patient is himself or herself active in producing if not this dualism than at least a whole array of modes of body presences reaching from objectivation to subjectivity. Moreover, the positioning of the body in relations of knowledge production or treatment often takes unexpected forms, challenging traditional notions of 'passive' subjects 'undergoing' treatment and being 'objectivied' in order to be medically 'known'.

In her study of methadone substitution treatment, Emilie Gomart touches upon these issues. She focuses on the intricate relations between drugs and human agency. In her case, the point is exactly that under certain conditions the use of drugs such as methadone do not 'reduce' users to 'addicted bodies'. She problematizes received oppositions of free will versus determination (by drugs or therapists); of agency versus material constraints; of selfcontrol versus control by drugs. The question of drug use does not revolve around the determination of bodies (or minds, for that matter) by pharmacological substances. Gomart argues that her topic necessitates a new vocabulary to describe modes of human agency because the usual sociological terms of determinism, control, influence, manipulation (by substance or therapist or user) are not sufficient. These terms can only describe drug or methadone use as a limitation to true subject-hood, while 'subjects', in Gomart's analysis, can only exist in and through their constant 'submission' to the entities that surround and perform them.

Related to these issues is the question what this repositioning of the body implies for the way we conceptualize and evaluate the knowledge that results from these interactions. If the body is neither a traditional 'object' or 'subject' of knowledge practices, but figures as an active mediator upon which these practices draw, what is then the epistemological consequence of this? Vincianne Despret's article tackles this complex question head on. Her paper discusses animal experiments, and discusses the question how scientific knowledge of animal behavior is possible, and what type of relationships specific knowledge practices forge between the experimenter, the animal, and the knowledge produced. It topicalizes the different ways the experimenter and the animal can be embodied in experiments -and Despret passionately argues for an epistemology in which a care for the bodies studied, and a relation of mutual 'affectuation' between experimenter and object, produces knowledge that can take us by surprise. In her paper, then, it is again 'bodies' that are at stake -but here as the objects and subjects of knowledge. Good scientific knowledge about 'bodies', she argues, is based upon experiments that maximize the chances of the object of study to transform the expected results -and ultimately, mediate the experimenter him-or herself.

Both Despret and Gomart obviously encounter bodies as one of their core mediating actants -yet their point is that the very concept of the 'body' (what it is, how it acts) is itself at stake in the practices they study. A 'final' theory of the body could never be their entry point, since it is just one of the phenomena produced in the trials of addiction treatment and the experiments of animal behavior research. Drawing on a different theoretical framework, Lock's study of 'living cadavers' is a similar case in point. Lock focuses on the practices of organ procurement (for transplantation purposes) in brain dead subjects, and elucidates the striking differences between the way 'brain dead bodies' are handled and conceptualized in the United States and in Japan. In the former case (and in many European countries), the 'commodification' of body parts is well advanced, and it is widely accepted that a brain dead person is 'dead' for all legal, ethical and social purposes. In Japan, however, these 'warm bodies', with regular heat beats and many intact reflexes are not unequivocally considered 'dead' at all, and the procurement of organs from such bodies is rare and highly contested. Lock elucidates the subtleties of these differences through interviews with ICU physicians and nurses, amongst others, and explains these differences through an elaboration of specific historical developments, differences in legal considerations, religious backgrounds, the role of the media and so forth. Lock does not focus explicitly on the materially heterogeneous performance of bodies: her analysis articulates the culturally different practices around 'living cadavers' and is similarly not explicitly concerned with the mediating role that these cadavers themselves play in these very practices. Yet these concerns are not far from the surface: the 'brain dead' condition can only persist with 'healthy' organs through medical interventions, and the peculiar condition of these 'cadavers' does play a core role in the way these different cultures enroll them within the charged debates around organ procurement.

The third and last part, Body Collective, elaborates an issue that has been more or less present in the papers of this volume: the political nature of the performance of specific bodies. Often, the politics at stake in topicalizing 'bodies' is a struggle for the wholeness of bodies, or for the integrity of body-boundaries. In such cases, the body's wholeness and unity is taken as a primary characteristic, and its materiality is taken as a possible 'grounding' for resistance and critique. So 'invasion' of female bodies by reproductive technologies that perform the fetus as 'subject' can be criticized by pointing at the female bodies that are thereby reduced or intervened upon. Likewise, patients' dependence on medical drugs and technologies can be described as the gradual 'emptying out' of the lived body by Technology, and as the unfortunate 'medicalization' of previously 'whole' lives. This recourse to the integrity and wholeness of bodies has been a powerful and succesful political strategy for feminists and ethicists, amongst others, in claiming e.g. basic reproductive rights and, more generally, the right of the individual to decide about any intervention that deliberately affects his/her body.

At the same time, however, this position is more and more contested. The authors joined in this special issue underwrite critiques of authors such as Haraway that the political grounding that this supposed 'wholeness' and 'integrity' yields is rather problematic (1991). For one, it reinvents the body as a universal, a-historical category -and such categories have never been very generous towards women or people of colour, to name a few. In addition, the constructivist, performative position elaborated here makes any recourse to such a pre-existing entity impossible. If every 'wholeness' is a historically specific and performed 'wholeness', the question becomes which more or less 'whole' body is preferred, and by whom? Different practices within medicine and biology perform different bodies, and these differences may be a much more important point of entry for political struggle than the worn critique of the impoverished 'medical' body vis-à-vis the 'lived' body that would somehow be more pure (ibid.; [START_REF] Mol | The Body Multiple. Ontology in Medical Practice[END_REF].

In her contribution, Irma Van der Ploeg deconstructs in great detail all the operations that allow for the constitution of new 'body collectives' ('couple' and 'fetus'), in fertily treatments and fetal surgery. She shows how these medical practices and their accompanying discursive mechanisms render the treatment of male or fetal problems through interventions on women's bodies acceptable or even inevitable. But her main point is political as well as methodological. To develop a critical analysis of technologies and practices, to be able to fruitfully ask the question of patient autonomy and bodily integrity, A related yet subtly different interpretation of the body politics and the 'body collective' is given by Steve Epstein's work. Epstein focuses on the debates about the US 1993 NIH Revitalization Act, and especially about those paragraphs that require that women and members of racial and ethnic minority groups are "included as subjects" in each clinical study funded by the US National Institutes of Health. These debates, Epstein convicingly argues, are all about when bodies can be counted as 'the same' or have to be seen as 'different', and about what 'differences' should be seen to be relevant enough to count as biologically grounded, distinctive 'categories' of bodies. These debates are highly politically charged, since they are simultaneously about whether collective identities are and should be underpinned by biological differences -and about which differences matter and which not. As in van der Ploeg's article, then, Epstein argues that what counts as the biological body is a thoroughly political question, drawing novel lines around and between individuals that separate and join them in novel, ever contested ways.

In the final article, Bruno Latour draws together several of the themes brought up throughout the special issue in a novel interpretation of the question what counts as 'good science' in general, and about 'bodies' in particular. Bodies, he argues, come into being through being affected by other bodies, instruments, experiences: the more profoundly the body has been articulated with all these surrounding entities, the richer, the more collectiveand therefore more 'real' -it is. What, however, is a 'good' articulation? When the 'natural' body is lost to us as a starting point, how do we distinguish 'good' ways of performing bodies from 'bad' ways? Drawing upon the work of Isabelle Stengers (e.g. 1997) and Despret (this volume), and following a strategy similar to authors such as Haraway (e.g. 1989), Latour takes an epistemological approach to this question. Picking up a trope that has been somewhat neglected in STS since the the demise of the prescriptive philosophy of science (with Popper and Lakatos being the last 'heroes'), he pleads for a novel 'shibboleth' to distinguish 'good' science from 'bad'. As science itself, he argues, this falsification principle cannot avoid being simultaneously political and about 'truth': any epistemology is necessarily a political epistemology. To return to the question of 'bodies', any judgment about what counts as a 'scientific' mode of talking about 'bodies' is simultaneously a judgment about what types of bodies should populate our worlds, and how feasible it is to construct alternative articulations, to perform bodies differently. Addressing this question in the light of the ever increasing importance of 'bio-politics', the definition, modification and commodification of 'life' in all its forms, his article forms a fitting open end to this special issue.

This special issue, Bodies on Trial, then, first of all puts our understanding of 'bodies' to trial. What can we do, theoretically and politically, with this category? How do the modifications that the authors combined here propose matter to this question? How is the 'body' affected by its confrontation with STS? In its turn, of course, STS is put to trial as well: will the rephrasings it offers to the social study of the bodies proof to be viable? Most importantly, however, Bodies on Trial presents the body as being shaped, brought into being, transformed and known through interactions with other entities (multiple substances and interventions in the case of diabetes, resuscitation technologies, methadone, multiplicity of representations in patient records, birth technologies, odor kits and so forth). The 'lived body' is not reduced by its encounters with things and technologies -rather, these encounters are what brings it to its specific life. Such trials are what performs bodies; such trials embody us.

  one has to suspend the definition of what counts as individuality, which can no longer be equated with the boundaries of the individual body, and to describe variations of what it includes.

In this specificity lies the difference with analysis such as Terry[START_REF] Kapsalis | Public privates. Performing Gynecology from both Ends of the Speculum[END_REF]: the list of what counts to define each situation is more open-ended than in the ritualised situations described byKapsalis.

Endnotes


Keywords: borne, capacité, codes correcteurs d'erreurs centrés, construction, codes couvrants, fingerprinting, codes aléatoires, codes de Reed-Solomon, marking assumption, distortion assumption

Construction explicite et approche théorique en fingerprinting Résumé : Nous étudions les attaques par collusion dans l'espace de Hamming en utilisant le cadre de [SBM05]. Nous construisons une famille de codes anti-collusions efficace contre des coalitions de taille arbitraire : cette famille permet un traçage sans erreur des utilisateurs malhonnêtes et cela en temps polynomial. Le nombre d'utilisateurs est exponentiel en la longueur. La construction proposée repose sur les codes correcteurs d'erreurs centrés [BP99] pour lesquels nous étudions deux constructions. Nos résultats entretiennent une relation étrange avec une borne supérieure sur le nombre d'utilisateurs obtenue dans [SBM05] pour les codes à composition constante : les codes que nous construisons, sans être à composition constante, dépassent cette borne.

Introduction

When distributing digital contents, one may want to prohibit redistribution of the contents, for example when one sells video. A reasonable requirement to enforce this prohibition is to be able to trace users have redistibuted their copies.

This can be achieved in a simple way if users do not collude, and just redistribute their own original copies : the dealer can embed, in a robust way, a kind of serial number in each copy. Watermarking techniques address this embedding issue. Fighting collusion of users is more involved.

Since the introduction of this topic by [START_REF] Blakley | Fingerprinting long forgiving messages[END_REF], the most studied framework is the so-called marking assumption popularized by [START_REF] Boneh | Collusion-secure fingerprinting for digital data[END_REF]. In this setting, the extra data is a collection of marks, that is a n-tuple over some alphabet Σ. The marking assumption states that, possibly after being proceeded by some decoder, a fake copy created by some colluders will contain a ntuple z = (z 0 , ..., z n-1 ) such that in each position i ∈ {0, ..., n -1}, at least one of the colluder has symbol z i in position i.

A more recently investigated model is the one used in [START_REF] Somekh-Baruch | On the capacity game of private fingerprinting systems under collusion attacks[END_REF]. Here, the marking assumption is replaced by two constraints. The first is related to the creation of user copies : the copies must be close to the original content. The second concernes the possible fakes : a fake copy can be created by a coalition of dishonest users if and only if the fake copy is close enough to, at least, one of the members' copies. For these reasons, we will call this model the distortion assumption.

In those models, several problems arise. Among them, there are 1. the effectiveness of the solution proposed, that is the possibility to create the user copies and to trace dishonest users from fake copies using polynomial time algorithms in the content length;

2. the scalability, that is, essentially, the asymptotic behaviour of the user rate in function of the other parameters.

In this work, we will address these two problems in the settings of [START_REF] Somekh-Baruch | On the capacity game of private fingerprinting systems under collusion attacks[END_REF], namely what we call the distortion assumption. We will see, that in a very surprising fashion, it is possible to tune the parameters of the fingerprinting systems in such a way that we avoid any benefit of collusion. This is very different from what can be done with the marking assumption (e.g. [START_REF] Barg | Digital fingerprinting codes: Problem statements, constructions, identification of traitors[END_REF]).

In [START_REF] Somekh-Baruch | On the capacity game of private fingerprinting systems under collusion attacks[END_REF], the maximum number of users is investigated, under the distortion assumption and in a non constructive way, for a family of fingerprinting systems. It is proved that the logarithm of this maximum scales with O(1/L) and goes to zero if L grows linearly with n.

In this paper, we construct a family of binary fingerprinting codes with exponentially many users (in the content length). This family allows efficient user copy creation and dishonest user tracing : both of these issues can be solved with polynomial time algorithm. Moreover, our fingerprinting codes have a very interesting new property: they are effective against coalitions of arbitrary size. This, with the exponential number of users, implies that our codes beat the bound derived in [START_REF] Somekh-Baruch | On the capacity game of private fingerprinting systems under collusion attacks[END_REF] and, so, that the family of fingerprinting systems considered in [START_REF] Somekh-Baruch | On the capacity game of private fingerprinting systems under collusion attacks[END_REF] is inefficient.

To achieve efficent fingerprinting codes, we heavily rely on centered error correcting codes. In fact, we prove that fingerprinting for collusion attack under the distortion assumption is a generalisation of error correction for centered codes. Thus, we address fingerprinting via the particular problem of centered codes.

The paper is organised as follow. In Section 2 we present the framework for fingerprinting codes under the distortion assumption and our notation. Section 3 gives basic facts about the centered error correcting codes, and states a simple upper bound. We address the construction of centered codes in Section 4: First, in Section 4.1 we consider (unpractical) random construction to obtain lower bound and in Section 4.2 we give a construction which is fully practical. Section 5 explains how to use centered error correcting codes to construct fingerprinting codes. We also show how this construction allows to fight coalition of arbitrary size. We detail the parameters achieved when using the centered codes constructed in Section 4.2. Section 6 briefly compares F. Galand our results and others results on the capacity of some fingerprinting systems obtained in [START_REF] Somekh-Baruch | On the capacity game of private fingerprinting systems under collusion attacks[END_REF]. Finally, we conclude pointing out an important difference between the model we use here and the marking assumption.

Fingerprinting Formal Problem

We have a set V ⊂ F n of original data, which can be seen as sequences of length n over some alphabet F. In order to fingerprint some copyright protected data v, the dealer is allowed to change at most ∆ o coordinates, that is a fingerprinted copy of v is in B ∆o (v) = {y : d(v, y) ≤ ∆ o } -d is the Hamming distance over F n -, the ball of center v and radius ∆ o .

Definition 2.1 An (n, M, ∆ o ) fingerprinting code is a mapping, E : V × M → F n , such that 1. |M| = M ; 2. E v : m → E(v, m) is injective for all v ∈ V, i.e. ∀(m, m ) ∈ M 2 E v (m) = E v (m ) =⇒ m = m ; 3. ∀v ∈ F n E(v, M) ⊂ B ∆o (v) (E(v, M
) being the set of all possible fingerprinted copies of v)

A coalition U ⊂ E(v, M
) is a set of fingerprinted copies of some v ∈ V, and a forgery f created by this coalition must satisfy :

∃c ∈ U d(c, f ) ≤ ∆ f ,
for some fixed value ∆ f . Thus, the set of forgeries computable from a set U is

forg ∆ f (U ) = c∈U B ∆ f (c) .
Definition 2.2 A fingerprinting code is said to be (L, ∆ f )-secure if there exists a mapping D : F n → F n (called the tracing or decoding mapping), such that for any v ∈ F n and any coalition

U ⊂ E(v, M) of size at most L, D forg ∆ f (U ) ⊂ U ,
where U is the set of messages corresponding to the copies in

U , U = {m | E(v, m) ∈ U }.
Remark that this definition of secure fingerprinting codes do not allow any kind of probability of error, neither a failure in the decoding (no output), neither to frame an innocent user. Moreover, we do not require any knowledge of the original data v.

In the sequel, we will set V = F n , with F the finite field with 2 elements. The number of users M will be a power of 2, M = 2 . The set M will be [1, M ], and when it will be convenient, we will identify an integer with its binary expansion, and M with F .

Centered Error Correcting Codes

Centered error correcting (CEC) codes, which were introduced in [BP99], are a generalization of the classical notion of error correcting codes.

Roughly speaking, we add a condition on the localization of the codeword c encoding a message : we have a pair (v, m) and c must be within the ball B T (v) of center v and radius T , where T is a new parameter of the code. Definition 3.1 A centered error correcting code of parameters (n, M, T, 2e + 1) is defined by an encoding mapping E :

F n × M → F n such that 1. ∀(v, m) and (v , m ) = (v, m), B e (E(v, m)) B e (E(v , m )) = ∅ 2. ∀(v, m), E(v, m) ∈ B T (v)
The first condition is a classical one to allow correction of e Hamming errors. The second condition is the localization constraint.

As easily seen, setting T = n leads to the usual definition of error correcting codes since the condition 2) of the above definition is then always satisfied.

Another way, equivalent to Definition 3.1, to define CEC codes is by mean of coverings.

Proposition 3.2 A centered error correcting code of parameters (n, M, T, 2e + 1) is a set {C i } of M disjoint coverings of radius T of the space F n , distant from each other of at least 2e + 1 :

1. ∀i, c∈Ci B T (c) = F n ; 2. ∀i, j = i , ∀(c, c ) ∈ C i × C j , d(c, c ) ≥ 2e + 1.
Proof. The sets E(F n , m), where m ∈ M, are coverings of radius T : for all v, E(v, m) is at distance at most T from v by 2) of Definition 3.1. Moreover, those sets are 2e+1 apart from each other: otherwise, there exist couples (v, m) and (v , m

) = (v, m) with B e (E(v, m)) B e (E(v , m )) = ∅,
which would contradict 1) of Definition 3.1. The reverse way can be proved as easily as this one.

On Non-Existence Results

The following lemma, which can by found in [START_REF] Bassalygo | Centered error-correcting codes[END_REF] allows to derived an upper bound on the cardinality M of a CEC code. Then, for all set Y , the following inequality holds

N T (Y ) N e (Y ) ≤ V T V e ,
where V a is the cardinality of a ball of radius a.

Consider a CEC code of parameters (n, M, T, 2e + 1) with encoding mapping E. We will apply this lemma to the set

Y (m) = {c | ∃v E(v, m) = c} = E(F n , m)
of codewords that encode some message m. The set Y (m) is a covering of radius T , thus

|N T (Y (m)) = 2 n | .
On the other hand, since the balls of radius e centered on the elements of Y (m) are disjoint, we have

M ≤ 2 n N e (Y (m)) ≤ N T (Y (m)) N e (Y (m)) . Lemma 3.3 yields F. Galand
Proposition 3.4 For all CEC codes of parameters (n, M, T, 2e + 1), we have the upper bound

log(M ) ≤ log(V T ) -log(V e ) .
The asymptotic behavior of the volume of the ball is well-known:

1. when the radius a grows linearly with the length n we have

log(V a ) = n • h a n + o(n) , where h(x) = -x log(x) -(1 -x) log(1 -x)
is the usual binary entropy (e.g. see [MS96, chap. 10, 11, Cor. 9]) 2. when the radius a is fixed and n grows to infinity, log(V a ) = a log nlog(a!) + o(1) .

We have therefore the following two asymptotic upper bounds Corollary 3.5 For all (n, M, T, 2e + 1) CEC codes of length n large enough, we have 1. For τ = T /n and ε = e/n fixed,

log(M ) n • (h (τ ) -h (ε)) .
2. For T and e fixed,

log(M ) (T -e) • log(n) -log T ! e! .
where we write f g for f ≤ g(1 + o(1)) when n tends to infinity.

Constructing CEC Codes

On Existence Results

A simple way to construct CEC codes is to use linear codes. Proof. The code C can be partitioned in 2 k-k cosets of C , the cosets are at distance at least 2e + 1 from each other since they are composed of codewords of C, and these cosets have the same covering radius as C , namely T . This is exactly the definition (in fact the equivalent one given in Proposition 3.2) of a (n, 2 k-k , T, 2e + 1) CEC code.

Encoding

Recall that, for encoding with a CEC code, each of the M = 2 k-k sets C i is used to encode a particular message m ∈ {1, ..., M }, i.e. a word c encodes the message m if and only if c ∈ C m . Moreover, a codeword encoding the message m for a center v can be found at distance at most T , since T is the covering radius of each set C i . Now, consider a parity-check matrix H of C. A parity-check matrix H of C can be obtained by adding rows to H,

H = H Q (1)
for some (kk ) × n matrix Q. The cosets C i of C in C can be indexed in such a way that

C i = {c ∈ F n | c • H = 0 and c • Q = i}
(where needed, the integer i is identified with its binary expansion). So, we are looking for a word E(v, m) such that

E(v, m) • H Q t = E(v, m) • H t E(v, m) • Q t = (0 m) . We can choose E(v, m) = v + u where u is a solution of u • (H t Q t ) = (0 m) with w(u) ≤ T .

Decoding

If a binary word z of weight at most e is added to a codeword E(v, m) to produce y, since E(v, m) is a codeword of the e-error correcting code C, we can recover E(v, m) by adding to y the (unique) word of weight at most e and syndrome y • H t , namely z. Then, we retrieve the message by computing (y + z)

• Q t .

An Asymptotic Lower Bound

When τ = T /n and ε = e/n are fixed and n grows to infinity, two classical results on random binary linear codes allow to derive the asymptotic behavior of CEC codes constructed in Proposition 4.1. We sum up these classical results in the following theorem and refer to [Bar98, Lem. 1.2 and Th. 3.4] for detailed proofs.

(n, 2 n(h(τ )-h(2ε)) , n • τ, 2 • n • ε) .
Proposition 4.3 Providing that τ > 2ε, the construction of Proposition 4.1 allows to achieve centered error correcting codes with parameters

(n, M, n • τ, 2 • n • ε) , where log M n • (h(τ ) -h(2ε)) .
The last proposition is to be compared to the corresponding upper bound stated in 1) of Corollary 3.5.

F. Galand

Effectiveness

Centered error-correcting codes constructed with random codes have two main flaws that prevent them from being usable in practice. First, we cannot verify the "assumed" parameters. In fact, it is known by [START_REF] Vardy | The intractability of computing the minimum distance of a code[END_REF] and [START_REF] Mcloughin | The complexity of computing the covering radius of a code[END_REF] that, for linear codes, the decision problems associated with minimum distance and covering radius computations are respectively NP-complete and Π 2 -complete (the Π 2 complexity class includes the NP class). Moreover, even efficient probabilistic algorithms are not known. Second and even more painful, both encoding and decoding need to find words z of weight at most respectively T and e with a particular syndrome with respect to a linear code (in fact, decoding up to e for C and complete decoding for C ). Unfortunately, this is an NP-hard problem and, once more, we do not even know efficient probabilistic algorithm (e.g. see [START_REF] Barg | Handbook of Coding Theory, volume I, chapter Complexity Issues in Coding Theory[END_REF]). Nevertheless, using specific linear codes, this problem may be overcome. For instance, writing BCH(e) the (narrow sense and primitive) binary e-error-correcting BCH code (see [MS96, Chap. 7, 6]), we can choose C = BCH(e) and C = BCH(e ) with e > e, since those codes are nested, i.e. C is a subcode of C. For the choice (e, e ) equal to (1, 2), (1, 3) and (2, 3), the construction is effective since complete decoding are known (see [START_REF] Berlekamp | Algebraic Coding Theory[END_REF] and [START_REF] Van Der Host | Complete decoding of triple-error-correcting binary bch codes[END_REF]). The corresponding CEC codes have respectively the parameters (2 r -1, 2 r , 3, 3), (2 r -1, 2 2r , 5, 3) and (2 r -1, 2 r , 5, 5) (see [MS96, Chap. 9] and [CHLL97, Chap. 10] for the parameters of BCH codes).

A nice example of encoding and decoding, with C = BCH(1), C = BCH(2) and r = 4, can be found in [ZC91, IV.C], where a construction similar to the one we presented in this section (with the restriction e = 1) is described and applied to some BCH codes.

An Explicit Construction

The construction we propose relies on two codes: a direct sum of T binary Hamming codes of length 2 r -1 and an e-error-correcting code over a larger alphabet, the finite field with 2 r elements, denoted F 2 r . For the purpose of this construction, we will need to identify elements of vector space F r and elements of the field F 2 r . To do so, we choose a fixed basis of F 2 r over F, and write x the element in F 2 r corresponding to x ∈ F r . With a slight abuse in notation, we also write c the element of F T 2 r corresponding to c ∈ F rT F r × ... × F r , where the identification is done componentwise.

We will use the definition of CEC codes given by the Proposition 3.2 in the proof of the following result Theorem 4.4 Let C be a [T, k, 2e+1] code over F 2 r . There exists a binary ((2 r -1)•T, 2 k•r , T, 2e+ 1) centered code C. Moreover, 1. if C has a polynomial time encoding algorithm, so has C; 2. if C has a polynomial time decoding algorithm, so has C.

In the above theorem, the algorithms are polynomial with respect to the corresponding code length, that is T for C and n = (2 r -1) • T for C.

Proof. Let C be the direct sum of T Hamming codes of length 2 r -1, thus the length n of C is n = (2 r -1) • T , and let H be a parity check matrix of a Hamming code of length 2 r -1. A parity check matrix of C can be obtained from H as a block matrix by

P =    H 0 . . . 0 H    . (2)
We can now define our CEC code C, as the following set of cosets of C y + C : y • P t ∈ C where P t is the transpose of P . Since cosets have the same covering radius as the code C, and C has clearly a radius equal to T , we just have to prove that y + C and z + C are 2e + 1 apart when y • P t = z • P t . If we have y = y + c 1 and z = z + c 2 , where c 1 , c 2 ∈ C, then

(y + z ) • P t = (y + z) • P t ∈ C \ {0} .
But, since P is a block matrix, grouping the coordinates of y and z by 2 r -1, that is, writing y = y 1 . . . y T and z = z 1 . . . z T , for some y i ,z i ∈ F 2 r -1 , we have

(y + z) • P t = (y 1 + z 1 ) • H t , . . . , (y T + z T ) • H t .
On the other hand, C has minimal distance 2e + 1. Thus, there exist at least 2e + 1 coordinates of (y + z) • P t that are different from 0. Equivalently, there exist 2e + 1 values of i such that

(y i + z i ) • H t = (y i + z i ) • H t = 0, i.e. such that d(y i , z i ) ≥ 1. Finally, we get d(y , z ) = 0≤j<T d(y j , z j ) ≥ 2e + 1 ,
completing the proof of the first part of the theorem.

To prove 1), we consider a word v and a message m. We use C to encode m in a codeword c m ∈ C. Then, we look for a word E(v, m) at distance at most T from v in the coset of C of syndrome c m (with respect to P ). This can be done by computing a word u of weight at most T and syndrome c m + v • P t and taking

E(v, m) = v + u, since E(v, m) • P t = (v + u) • P t = v • P t + c m + v • P t = c m .
The computational cost is an encoding in C and the search of u. For a direct sum of T Hamming codes of length 2 r -1, the computation of u consists in T decoding of a Hamming code of length 2 r -1, so it is O(rT ) operations. Thus, if the encoding of m in a codeword of C can be done in polynomial time, the overall computational cost of E(v, m) is polynomial.

To prove 2), we consider a word y at distance at most e from E(v, m). We can recover m in the following way. First, compute the syndrome s = y • P t . Since d(y, E(v, m)) ≤ e, s is at distance at most e from E(v, m) • P t . But E(v, m) • P t is a codeword of C, and C can correct up to e errors. So, performing a decoding on s allows to recover m. The total cost is T syndrome computations with respect to H, and a decoding in C. So, it is polynomial if C can be decoded in polynomial time.

Remark that, in contrast to the construction of Proposition 4.1, the decoding used for the construction do not recover the codeword E(v, m), but directly outputs the message m. Nevertheless, it is possible to compute E(v, m): the codeword E(v, m) is the unique codeword in B e (y), since, by hypothesis, y ∈ B e (E(v, m)) and, by 1) of Definition 3. 1,B e (E(v,m)) ∪ B e (E(v , m )) = ∅ for (v , m ) = (v, m). Thus, there exists a unique word u, of weight at most e, such that y + u = E(v, m). But u • P t = c m + y • P t . Since we know m and y, we can compute right hand side of the last equation. Finding the solution u of weight at most e is then possible, thanks to the structure of P . Moreover, we can see that this is equivalent to the computation required by an encoding in the centered code. So, if C has a polynomial time encoding, recovering E(v, m) can be done in polynomial time.

Corollary 4.5 For 2 r > T > 2e, there exist binary ((2 r -1)T, 2 r(T -2e) , T, 2e + 1) CEC codes with polynomial time encoding and decoding algorithms.

Proof.

Since q = 2 r is greater than T , we can use for C a [T, T -2e, 2e + 1] Reed-Solomon code over F 2 r . The previous result gives us fully practical CEC codes. On the other hand, in view of asymptotic analysis, it has a drawback: T has to be less than 2 r . But, if we let the length n = T (2 r -1) go to infinity with T ∝ n, this implies a fixed r and, so, a bounded T , and we have a contradiction.

F. Galand

Using algebraic geometric codes [START_REF] Tsfasman | Algebraic Geometric Codes[END_REF] for C allows to drop the upper bound condition on T . So, we can fix q = 2 r (r must be even), and still have the length n of the CEC code going to infinity. From [START_REF] Tsfasman | Modular curves, Shimura curves and Goppa codes, better than Varshamov-Gilbert bound[END_REF], we can have, asymptotically, for

C k T ≤ 1 - 2e + 1 T - 1 √ q -1
for e/T fixed. Thus we can state another corollary to Theorem 4.4.

Corollary 4.6 Let r be an even integer. Let τ = (2 r -1)

-1 and ε such that τ > 2ε. For length n large enough, there exist

(n, M, n • τ, 2 • n • ε) CEC codes, with log(M ) n • τ -2ε - τ 2 r 2 -1 • log 1 + 1 τ .

Constructing Fingerprinting Codes From CEC Codes

Recall we want to distribute slightly different copies of some binary word v ∈ F n to M different users. A fingerprinted copy c must satisfy the following distortion criterion:

d(c, v) ≤ ∆ o . ( 3
)
The purpose is to trace illicit copies, computed from some fingerprinted copies where "to trace" means to find one of the fingerprinted copy used to create the forgeries. An illicit copy f computed from a set U of original copies must satisfy only a distortion criterion :

min c∈U d(f, c) ≤ ∆ f . (4)
If we have a CEC code C with parameters (n, M, ∆ o , 2∆ f + 1), it is possible to solve the fingerprinting problem by using the following scheme: denote by E the encoding mapping of C, and give to the m-th user the fingerprinted copy E(v, m). Criterion (3) is clearly satisfied. Now, if a coalition U creates an illicit copy f then, by (4), there exists m in U such that d(E(v, m), f ) ≤ ∆ f . But, C allows to correct ∆ f errors. Thus, decoding f gives E(v, m) and we can recover at least one member of U . Remark that the size of the coalition does not matter, which is a very interesting property.

To be practical, this scheme requires that the code C has two important properties. On one hand, C must have an efficient encoding mapping. On the other hand, it must have an efficient decoding algorithm, which is far more restrictive.

From our constructions of centered codes in Corollaries 4.5 and 4.6, we deduce

Theorem 5.1 1. Let r, ∆ o , ∆ f be integers such that 2∆ f < ∆ o < 2 r .
There exist binary ((2 r -1)∆ o , 2 r(∆o-2∆ f ) , ∆ o ) fingerprinting codes, with polynomial time encoding and decoding algorithms, which are (∞, e)-secure.

2. Let r be an even integer, δ o = (2 r -1)

-1 and δ f be such that 2δ f < δ o . Then, for n large enough, there exist (n, M, n

• δ o ) fingerprinting codes that are (∞, n • δ f )-secure, with log M n δ o -2δ f - 1 2 r 2 -1 (2 r -1) log 1 + 1 δ o . 3. Let δ o , δ f be real numbers such that 2δ f < δ o < 1/2. There exist (n, M, n • δ o ) fingerprinting codes that are (∞, n • δ f )-secure, with log M n h(δ o ) -h(2δ f ) .
6 On the Capacity Game of Private Fingerprinting Systems

Roughly speaking, the capacity is the highest possible rate of users log(M )/n. For a proper definition, we need to weaken Definition 2.2 of (L, ∆ o )-secure codes to allow some probability of error p e in the decoding. In this case, we say that the fingerprinting code is (L, ∆ f )p e -secure. Now, let n grow to infinity with ∆ o = n • δ o and ∆ f = n • δ f . The capacity C(L, δ o , δ f ) is the maximum rate of users log(M ))/n over sequences of (n, M, n•δ o ) fingerprinting codes, of increasing length, which are (L, n • δ f )p e -secure with p e decreasing to 0 at infinity. The model we consider in this paper come from [START_REF] Somekh-Baruch | On the capacity game of private fingerprinting systems under collusion attacks[END_REF], where the capacity of some fingerprinting systems is derived. The fingerprinting systems presented in [START_REF] Somekh-Baruch | On the capacity game of private fingerprinting systems under collusion attacks[END_REF] fulfill two technical assumptions ( [SBM05, Def. III.2 and III.3]) : The first one (constant composition) is a constraint on fingerprinting codes, and the second ("smoothness") is a constraint on sequences of fingerprinting codes. A practical consideration is given in order to justify the constant composition assumption: essentially, it allows efficient computation of the fingerprinted copies.

To emphasize the different settings, we denote by C the capacity in the sens of [START_REF] Somekh-Baruch | On the capacity game of private fingerprinting systems under collusion attacks[END_REF], that is the capacity restricted to smooth sequences of constant composition codes. Basically, the results are the following:

1. for a fixed coalition size L and the distortions ∆ o = n • δ o and ∆ f = n • δ f growing linearly with the data length n, we have

C(L, δ o , δ f ) = O 1 L ; 2. when L = n • grows linearly with n, then C(n • , δ o , δ f ) = 0 .
At first glance, these results seem in contradiction with ours since in Section 5 we construct (∞, δ f )-0-secure fingerprinting codes with an asymptotic rate bounded away from zero. Precisely, Theorem 5.1 states

C(∞, δ o , δ f ) ≥    δ o -2δ f - 1 2 r 2 -1 (2 r -1) log 1 + 1 δo h(δ o ) -h(2δ f )
at least for some particular values of the parameters δ o , δ f and r. Of course, a possible reason to explain this point is that our construction does not fulfill the two technical assumptions discussed earlier.

At least, we can say that these assumptions have very important consequences and are not so mild as suggested in [START_REF] Somekh-Baruch | On the capacity game of private fingerprinting systems under collusion attacks[END_REF], since they drastically reduce the set of achievable rates. Moreover, they do not lead to fingerprinting codes with more practical properties than our codes, since our codes fulfill the practical considerations, and much more, used to justify the constant composition assumption. Stated in another way, constant composition fingerprinting codes seem to be inefficient.

Conclusion

The model we consider in this paper was recently introduced in [START_REF] Somekh-Baruch | On the capacity game of private fingerprinting systems under collusion attacks[END_REF]. This model allows dishonest users to change any part in their own original copies as soon as they don't change too many bits, compared with at least one of their copies.

Recall another well known model, known as the marking assumption [START_REF] Boneh | Collusion-secure fingerprinting for digital data[END_REF], which allows to change positions in which at least two members of the coalition have different bits. Contrary to intuition, the new model is less favorable to dishonest users than the marking assumption for F. Galand which it is not possible to construct binary fingerprinting codes secure against coalitions, even of size two, without allowing some probability of error in the tracing algorithm (see [BS98, Th. IV.2]). Whereas with the model used in [START_REF] Somekh-Baruch | On the capacity game of private fingerprinting systems under collusion attacks[END_REF], we can do it : Namely, we have proved that binary fingerprinting codes without tracing error exist.

In fact, our proof leads to codes with a rate bounded away from zero with a new and interesting property: these codes resist to coalition of arbitrary size. Some heuristic explaining this strange, at first glance, effect is that the condition ∃c ∈ U, d(c, f ) ≤ ∆ f , is very restrictive, since it means that only a single member of the coalition, namely c, produces a forgery f . Hence, despite that formally the new model deals with coalitions of dishonest users, in fact it reduces to the case of a single user.

By exhibiting very good fingerprinting codes with interesting features, our constructive approach also allows us to prove that the capacity derived in [SBM05, Th. IV.1] for some fingerprinting systems doesn't hold for general ones and that the constant composition assumption is a severe restriction which eliminate, at least asymptotically, all interesting codes.

Lemma 3. 3

 3 Let T and e be non negative integers, with T ≥ e. Denote by N a (Y ) the set of binary words at distance at most a from the set Y N a (Y ) = y∈Y B a (y) .

Proposition 4. 1

 1 Let C be a [n, k, 2e+1] binary linear code. Let C ⊂ C be a subcode of dimension k and covering radius T . The cosets of C in C, i.e. the sets x + C , x ∈ C, form a CEC code of parameters (n, 2 k-k , T, 2e + 1).

Theorem 4. 2

 2 Let α be a real number less than 1/2 and let n grow to infinity. A [n, n • (1h(α))] linear code has minimum distance at least n • α and covering radius n • α • (1 + o(1)) with probability tending to 1. Let C be a [n, n • (1h(2ε))] code. It has minimum distance at least 2 • n • ε with hight probability and thus corrects errors of weight up to n • ε. Let C ⊂ C be a subcode of dimension n • (1h(τ )) (this implies 2ε < τ ): it has a covering radius n • τ with hight probability. Applying the construction detailed at the beginning of this section leads to a CEC code with parameters

RR n 6080