Boris Boubacar

Diop

Nathalie Carré

Between mother tongue and 'ceremonial tongue'

Keywords: Boubacar Boris Diop, translation and self-translation, African languages, Wolof

This article is a case study focusing on the not-so-common experience of writing and publishing in French as well as in an African language. Senegalese writer Boubacar Boris Diop decided to switch from French to his mother tongue, Wolof, after a stay in Rwanda as part of the 'Rwanda, écrire par devoir de mémoire' project. This study focuses specifically on the novel Doomi Golo and on Diop's self-translation of the text into French. What is at stake in the translation from Wolof to French? How has Boubacar Boris Diop managed to translate or transpose his text for different audiences? To what extent have traditional literary patterns influenced the writing of the text? These are a few of the questions raised and discussed in this contribution. Résumé Cette contribution se présente sous forme d'une étude de cas et s'intéresse à une expérience encore relativement marginale dans le champ des littératures francophones: celle de l'écrivain sénégalais Boubacar Boris Diop. Représentant important de la littérature francophone durant les années 1980-2000, celui-ci a en effet décidé d'effectuer un retour vers sa langue maternelle, le wolof, après un séjour au Rwanda dans le cadre de la résidence d'écriture 'Rwanda, écrire par devoir de mémoire'. La présente contribution s'intéresse en particulier à l'expérience d'auto-traduction que son premier roman en Wolof, Doomi Golo, a fait naître. Que se joue-t-il dans le travail de traduction entre Wolof et Français? Quelles nécessaires adaptations / transpositions se font jour? Comment les traditions littéraires (génériques et de réceptions) influencent-elles le texte même? Voici quelques-unes des questions abordées au long de cette contribution.

The work of many African francophone writers agrees with this statement, demonstrating that it is possible to wage a war for cultural recognition through the French language as 'butin de guerre', as Kateb Yacine once put it. But if cross-fertilization is a possible answer, a few writers and critics such as Ngũgĩ wa Thiong'o and Obiajungwa Wali have developed another way of perceiving things and decided to fight for African literature in a different way. By denying African literature in European languages the right to be called African, they underline that the expression 'African literature' has to be used only for texts written in African languages [START_REF] Wali | The dead end of African literature[END_REF][START_REF] Thiong | Decolonizing the Mind. The Politics of Language in African Literature, London and Nairobi: James Currey/Heinemann Kenya[END_REF]. This does not mean that they do not value the works produced in European languages, but that these 'Afro-European' studies, as wa Thiong'o calls them, cannot be the right media to convey African culture and perceptions that could only be expressed in African languages (Wa Thiong'o 2011: 58).

In this special issue dedicated to 'Multilingual Francophone African Identities', I would like to explore the relations between identity(ies) and language(s) by focusing on the question of selftranslation. A few years ago, the Senegalese writer Boubacar Boris Diop wrote Doomi Golo in Wolof before translating it into French a couple of years later. The original novel was thus published in 2003 by the Dakar-based publisher Papyrus [START_REF] Joob | Doomi Golo[END_REF], while the French version, Les Petits de la guenon, was issued in 2009 by the French editor Philippe Rey [START_REF] Diop | Le français n'est pas mon destin' (interview with Taina Tervonen)[END_REF]. As it appears, Diop's experience is a very instructive testimony that explores the relationship between languages and creation, while implicitly commenting on how texts circulate between oral and written fields and underlining the interesting editorial strategies at stake.

The reason(s) for a choice

Before switching to his mother tongue Wolof, Boubacar Boris Diop had already written five novels in French: Le temps de Tamango (1981), Les Tambours de la mémoire (1991), Les traces de la meute (1993), Le cavalier et son ombre (1997), Murambi, le livre des ossements (2000) and the play Thiaroye, terre rouge (1990). Each of these works shows a deep interest in historical issues as well as a keen attention to the art of storytelling: Diop gives weight to memories (intimate as well as official) and often uses intertwined narrations. As most of his texts in French were well received in France and in Senegal and were awarded numerous and significant prizes, 1 I would like to question further what triggered his decision. Diop's choice was everything but an irrational move. It is thus important to expose the writer's motivations before moving on to a comparative work between Doomi Golo and Les Petits de la guenon, its French counterpart.

Diop was often praised for his books written in French and especially for the classical touch of his style. If Diop surely knows how to tell a story, far from subverting the French language as some other francophone writerssuch as Kourouma or Chamoiseauhave done, his writing is crystal clear, neat and precise français du roi, if we may use this expression. There is no attempt to deconstruct syntax or to Africanize vocabulary. But, as a socially and politically committed writer, deeply involved in the African continent (where he mostly lives), his writing was affected by a pivotal moment in his career when he rejected French as a creative language in order to embrace Wolof. In 1998, appalled by the lack of reaction from the African intellectuals to the Rwandan genocide, Nocky Djedanoum, then in charge of the Fest'Africa festival, decided to organize a workshop in Rwanda and invited ten African writers to participate, including Boubacar Boris Diop. 2 These writers met both victims and perpetrators of the genocide in order to try to make sense of what had happened: an experience that had a profound impact on Diop. In different interviews and articles he explains how he discovered that language policies had taken a not inconsiderable part in the Rwandan genocide. As a result, he decided to distance himself from a linguistic world that could be seen as stained with blood. Indeed, Rwanda had no diamonds, gold mines or petrol to be defended, but the population spoke French, which was one of the main reasons why France intervened. However, protecting what the French government called in 'pré-carré' did not prevent the tragedy from happening. Quite the contrary in fact. Consequently, Diop, whose writing has to play with words and language, felt that French was no longer a language to play with. 'J'ai perdu l'envie', he stated. 3 Distancing himself from French, he also lost a kind of intimacy with the language that was formerly his writing tongue. Moreover, he felt that, confronted with such a situation, he had to go back to his mother tongue to reflect on it and try to find answers: 'Cette expérience rwandaise m'a profondément perturbé. J'ai eu besoin de ma langue pour me réconcilier avec moi-même' (Diop 2003: 109-12). This testimony already draws a kind of equivalence between the mother tongue and a feeling of inner unity, a near transparency or adequacy of the self. If Diop usually underlines that he does not consider the French language as an enemy, he also states very strongly that the links between languages and thoughts are essential and that the major issue (and his main interest) can be summed up as follows: 'La question est de pouvoir articuler une pensée'. 4 And for that, the use of the mother tongue is required. While he did offer another novel in French, Murambi, le livre des ossements (2000), Diop decided that his future texts would be written in Wolof. Returning to his mother tongue, he decided to follow Ngũgĩ wa Thiong'o, whom he much admires, and whose book Decolonizing the Mind. The Politics of Language in African Literature (Wa Thiong'o 1986) was, as Ngũgĩ himself wrote, his 'farewell to English'. In this very book, Ngũgĩ had expressed the deep link between language and the self in using words very close to Diop's: 'La langue comme culture est le prisme à travers lequel nous entrons en contact avec nous-mêmes, avec les autres et avec le monde.

Elle nous traverse de l'intérieur' (Wa Thiong'o 2011: 37). Both writers state that, while Afro-European literature offers wonderful opportunities in English and French, it is high time that African literature written in African languages expands and makes its way through the continent in order to better articulate a thinking of its own, freed from the words and concepts born of and attached to European languages.

True to his words, Diop's next book was Doomi Golo. The book was quite well received by the critics, even those who were sceptical about the results. Most of the critics who were able to compare the French and Wolof texts stated that Diop's mother tongue felt more natural and managed to convey the rhythm, voices and subtleties of Senegalese life. 5 Reviewing Doomi Golo, Papa Samba Diop writes: 'A la manière d'un cinéaste, Boubacar Boris Diop vient ainsi de livrer un ouvrage difficilement égalable dans son adéquation à la gestuelle des personnages, aux couleurs des objets et aux bruits des rues de Dakar ' (2004: 113). This is one example among several others. 6 So, we might well ask, given what has just been said, how did the book eventually end up being published in French?

In November 2006, Toni Morrison was a special guest at the Louvre Museum in Paris and, as such, could invite any artist she liked. The winner of the Nobel Prize for Literature had deeply appreciated Murambi (2000) and so she invited Boris Boubacar Diop to come and read a text of his choice. Diop chose Doomi Golo, but, because of a mainly European audience, he had to translate the excerpt he had chosen to read aloud. His French publisher was in the audience, and this marked the beginning of a longer work of self-translation that would give birth to Les Petits de la guenon.

The experience of self-translation led Diop to reflect upon the relationships between cultures and languages, expanding on how identities can express themselves and be negotiated through writing.

Self-translation, which initially seemed easy for Boubacar Boris Diop, left him with a number of challenges to overcome. Confronting these difficulties, the writer also discovered new aspects of creativity that had repercussions on his literary practice.

Between mother tongue and 'Ceremonial Tongue': Experimenting in self-translation

As suggested by the title, Diop has always been aware of the very personal aspect ofand maybe opposition betweeneach of his languages. Wolof, his mother tongue, is for him very intimate, whereas French is a literary language whose codes are intimidating, even if mastered and understood:

Le français -ou l'anglaisest une langue de cérémonie, et ses codes, à la fois grammaticaux et culturels, ont quelque chose d'intimidant […] Ce sont là autant de raisons qui amènent l'écrivain à douter du sens ou de la finalité de sa pratique littéraire. [START_REF] Diop | Le français n'est pas mon destin' (interview with Taina Tervonen)[END_REF] I have already pointed to the question of the legitimacy of writing in Africa using European languages, which became so important for Boubacar Boris Diop, and I will come back to this question to consider the circulation of texts. What I find puzzling in Diop's quote, and want to reflect on more fully now though, is the feeling of reverence, which is also a feeling of inadequacy between a European language and the self. French for the non-native writer is a formal language with its rituals and strict rules, a 'ceremonial language' that can be seen as restrictive. And for Diop, the experience of writing in Wolof felt close to liberation: Après avoir écrit pendant la plus grande part de ma vie des romans en français, je peux dire aujourd'hui que j'ai une plus grande aisance d'expression dans ma langue maternelle. Les gestes banals de tous les jours se laissent dessiner sans réticence par ma plume et je n'ai plus besoin de longs détours pour exprimer les sentiments les plus simples. (1998) There is a kind of transparency between everyday life experiences and their translation into Wolof here. Words flow easily, embracing life and the self, which Diop highly valued when he experimented in his return to his mother tongue. But what happens to the transparency and the fluidity of language when it comes to translation and when the author has to express in French what has originally been written in Wolof? The writer himself has testified of the pitfalls he faced: Lorsque l'on traduit de l'italien vers l'espagnol ou du bambara vers le pulaar, on est dans le même univers sonore et les codes culturels peuvent se faire harmonieusement écho. Dans ce cas-ci, je devais me débrouiller pour faire correspondre deux univers mentaux radicalement différents, les univers pris en charge par les langues wolof et française. [START_REF] Diop | Le français n'est pas mon destin' (interview with Taina Tervonen)[END_REF] Because he had to negotiate between two drastically different worlds of reference, Diop had been forced to make choices. How could he 'freely' translate a text, which could not reach his Senegalese and French readers in exactly the same way? And how could he arrange it so that his text would better fit the cultural codes of each public?

Writing voices

One major difference between literature in Europe and Africa is the paramount importance of orality, which, even today, is the prevalent form of literature in most parts of Africa. The written word really weighs light in Senegal compared to the songs, poems and words that permeate the fabric of the whole society with the work of singers, griots and jottalikat (in charge of transmitting the words and teachings of the chefs de confrérie's). 7 Writing in Wolof engulfed Boubacar Boris Diop in a polyvocal world where voicesin their very textureshaped his text. If this point is not new to Diop's work (and to many other African writers), the author has nevertheless underlined how intense the sensation of 'hearing voices' was when writing in Wolof. The mother's voice was particularly hard hitting in the writer's mind. During his childhood, Diop was surrounded by women who used Wolof through singing and storytelling. Educated people like his father were more likely to speak French. Going back to the mother tongue was also for Diop like diving into his own memories through the sonorities of words. The author even says that writing in Wolof felt like having his mother reading over his shoulder, 8 her voice and inflexions being clearly audible. This was very important for storytelling: 'J'écris avec des échos', states Diop, 'je connais un grand nombre de langues mais celle qui me réponds, c'est le Wolof'. 9 So, the Wolof version is full of voices and noises that had to be conveyed in French. This was not an easy task and, 'poetically', Diop never really tried to transform the Wolof dynamics of sonorities into French, assuming that this was, in a way, a battle lost in advance: L'exercice a consisté, en gros, à naviguer d'un monde bruyant, aux rythmes saccadés et fous à un autre où les mots ne sont, pour dire le vrai, que des sourds-muets pompeux. Pendant l'écriture de Doomi Golo, des sonorités me sautaient à la figure, je n'avais pas affaire à des mots ou expressions sagement alignés entre les pages d'un dictionnaire mais à des êtres palpitants de vie. ( 2012)

The overwhelming presence of voices is nonetheless very noticeable throughout the French version.

It is conveyed by a dialogue between an old man, Nguirane Faye, and his grandson Badou, who has left for another place, which is likely to be Europe. Even if the play on sonorities is not so vividly audible, voices are still important in the French text. As in the Wolof version, on many occasions the written words are brought into gentle conversation where the grain de la voix is to be heard. The very first pages of Les Petits de la guenon mention the oral words of the storyteller as a model: 'J'aurais préféré te parler de vive voix, comme tout conteur digne de ce nom, pour faire battre plus vite ton coeur et t'éprouver par mes déroutantes énigmes' (Diop 2009: 19) ;and the whole text underlines the importance of the voice: 'et j'aime te parler' (Diop 2009: 242). In another section we are told, 'Nguirane Faye a alors ouvert Le livre des secrets, ce carnet rouge où il te parle à l'oreille… accroche-toi à ma voix' (Diop 2009: 435). The book is thus humming with voices, from different characters and narrators, as well as with embedded narratives whose presence necessarily brings back memories of the art of storytelling. Words are spoken, stories travel from one mouth to another: Ali Kaboyewho was once just a character (although of major importance) in the storytakes over from old Nguirane in the second part of the book (entitled 'Moi, Ali Kaboye') and assumes the narration. As for embedded stories, the dream sequence (Diop 2009: 190-98) as well as the 'Brèves digressions' (Diop 2009: 209) gives way to new stories and anecdotes not directly linked with the main plot. But if the French readership has no difficulty in picking up on such spoken words and stories, other aspects of the original text exclude the French audience because of the cultural differences between France and Senegal. It is at this point that the self-translator was forced to transpose.

Texts and contexts

Still rooted in Wolof culture, Doomi Golo presents a significant number of proverbs, signalled by italics and labelled as coming from 'wolof njaay'. 10 These sayings, which can be compared to those of the celebrated Senegalese philosopher Kocc Barma, 11 belong to the cultural heritage that informs the identity of every Wolof. They can be seen as part of the cosaan, the social and moral codes that order the society (the word cosaan means 'origins' or 'foundations'; 'traditions'). 12 Rhythmically punctuating the novel like a chorus, the proverbs also function as a strong cultural bind, making each Wolof speaker part of a community in recognizing the art of the writer as well as the usual context of uttering. These proverbs can often be easily understood on a certain level by a French audience, for example, 'Nous avons beau prétendre que rien ne nous arrête, tu ne nous verras jamais traîner près d'une maison gardée par une meute de chiens' (Diop 2009: 336) or 'Pourquoi s'accuser mutuellement d'avoir une hernie des testicules? Le plus simple n'est-il pas que chacun enlève sa culotte?' (Diop 2009: 418). But it is not always the case. For example, the proverb 'Dès qu'elle est seule, la poule gratte le sol d'une seule patte' is not very clear for a European reader, but for his Senegalese counterpart the few words are seen evidently as a way of enhancing concurrence.

However, Diop states that he sometimes had to find equivalences. 13 Besides, the feeling of community evades the French reader as well as some other cultural allusions. For example, the words Doomi Golo refer to a proverb, even in an indirect way: Golo naawul, baay ba la niru, meaning 'Le singe n'est pas laid, il ressemble seulement à son père'. A reader from Senegal will immediately recognize the allusion from the title, especially as acculturation is the main issue of the text, but it remains quite enigmatic for a French audience.

Another example of the necessary logic of transposition can be seen throughout the early pages of the original text and its translation. The Wolof version begins with 'Àddina: dund, dee': three little words (and a sparkling alliteration) that literally means 'down here (in this world). To live. To die' or 'Ici-bas. Vivre. Mourir' in Frenchthese are three words that any Wolof will understand but that cannot be translated as such because the result in French still lacks the emotional charge contained in the Senegalese formula. Diop thus decided to turn these three little words into a whole paragraph in order to explain the cultural context of funerals in his country: Depuis des générations, le rituel d'adieu est le même dans notre famille : un à un, nous pénétrons dans la pièce où le défunt est étendu sur une natte et là, nous disons en silence des prières pour le repos de son âme. Les visages sont graves et les corps refermés sur eux-mêmes, comme il se doit. Il se trouve pourtant toujours quelqu'un -c'est souvent le meilleur ami du mort, plus dévasté que tous les autrespour essayer de détendre un peu l'atmosphère. Il se moque affectueusement de celui qui a cru malin de filer en vitesse pour fuir nos petits ennuis sur terre. Et il l'avertit: 'Tu te trompes, mon gars, si tu penses en avoir fini avec moi. Je ne te laisserai jamais seul, je suis déjà en route et, je te le promets, je vais tellement te casser les pieds là-bas que tu vas regretter d'y être allé!' Et quand il le supplie de lui garder bien au chaud une des meilleures places du Paradis, certains ont la force d'esquisser un sourire, vite réprimé il est vrai.

Ces moments sont précieux, Badou.

Je trouve que c'est bien de s'entendre rappeler ainsi que la vie ça n'est pas grand-chose, même si nous en faisons toute une histoire, nous autres, de cette petite flamme qui s'agite et que le vent peut éteindre à chaque instant. Mais ne t'y trompe pas: ce n'est pas pour te dégoûter de l'existence que j'ouvre avec ces mots un peu tristes et amers le premier de mes sept Carnets.

Bien au contraire. Pour ce qui est de vivre, je ne me suis pas gêné, moi. (Diop 2009: 13-14) Such a development gives an idea of the work at stake when translating between two languages originating from different cultural spheres. The text is, in a way, less important than a context that has to be mediated. In translatingor transposinginto French, Diop had to suppress pages of work -for example, when Badou meets his childhood friend. This episode was too 'sénégalosénégalais' for the author to be transposed into French. We reach here an interesting turning point.

The process of understanding a text supposes that both author and audience share a mutual cognitive environment (Hill 2008: 16). The translator's task is to try to convey enough information to make the original context 'readable' for the foreign audience. By clearing the French version from this episode, Diop indicates a lack of cultural knowledge thought to be too difficult to bridge; the French audience could not infer the intended meaning even with the help of the translator. As Harriet Hill puts it, 'If a text does not evoke any context at all, processing is arrested ' (2008: 16). It seems to be the case here, and translation, reaching its limits, is to no avail. But if this one example underlines some untranslatability, writing in French permitted other experiences, and Boubacar Boris Diop did not only suppress certain aspects but he added some. For example, he sometimes developed the story in a different way because he considered that the writing was more interesting in French. This is the case with the story depicting Rodrigo Mancera in Gibraltar (Diop 2009: 190-98). In Wolof, the parable originating with the anecdote of some monkeys living in close relationship with human beings was not developed. However, in the French version, through the use of a dream sequence, Diop inserted a more satirical and political passage on the relationship between the western world and Africa. Quite disconnected from the plot (it has no real incidence on it), this inclusion tends to spur on the francophone reader to think about the rather unequal relationship between northern countries and their parents pauvres from the south. In a way, through the parable, Diop delivers a message and tries to awaken political awareness in his new (and different) readers. This question of sequences and episodes 'lost and gained in translation' is quite fascinating because it gives clues about the societies themselves, what message or interpretation is important to them (and also, in this precise case, what the author wants to be read). One can know more in reading about an interesting experience that took place in Mali. Since 1996, Bakary Tangara, a trained schoolteacher and school director, has been translating from French into Bamana some literary francophone works. They are then broadcast by Faso Fanu in his programme baramuso bulon (literally in French, 'Le vestibule de l'épouse préférée'). While Tangara has often chosen to translate francophone writers from Mali (Amadou Hampâté Bâ's L'Étrange Destin de Wangrin [1973] and Massa Makan Diabaté's trilogy Le Lieutenant de Kouta [1979], Le Coiffeur de Kouta [1980], et Le Boucher de Kouta [1982]), he has also presented European works by Jules Verne, Agatha Christie and Alexandre Dumas. The success of the translation of Le Comte de Monte-Cristo was overwhelming in Mali and has been smartly analysed by Tal Tamari (2010: 151-75). It is, of course, not the place here to repeat her work, but some points can be underlined. In transposing Alexandre Dumas' Le Comte de Monte-Cristo into Bamana for a Malian audience, Bakary Tangara highlighted certain themes and episodes while others (too franco-français as Diop may have put it) disappeared. In this case, what was highlighted was the importance of destiny and the role of Abbé Faria who, by his rather stoic position, can easily stand for an old wise Malian. The relationship between Faria and Dantès was also well appreciated and contributed to the success of the show, since, in an African context, the maître et disciple's relation is highly valued. These examples show how translating texts is also a way of encoding them so as to reach an audience according to specific cultural characteristics. It also brings to light the fact that, if Diop does feel the differences between French and Wolof, he is also using each of these languages according to their literary traditions; orality is a keyword in Wolof, while irony is making its way into French. By working between languages, Diop takes an approach that is quite different from Kourouma's, who mixes Malinké patterns with French structures, combining syntax. Diop does not attempt to 'cocufier la langue française', as one critic puts it, in analysing Kourouma's work (Gassama 1995: 118). The French he uses is very clear, always grammatically correct and adheres perfectly to the rules of the ceremonial language already mentioned. In his translation, there is no attempt to tropicalize French as in the case of other writers from the Caribbean and Africa. Wolof is present in the French version, but only through vocabulary, as numerous Wolof words are peppered throughout the French text. But it must be said that these words are never translated and that no glossary is offered to the reader at the end of the book. This way of dealing with foreign lexicon can be understood in two complementary ways. First, it means that the author considers that Wolof words are easily understandable and do not need translation (which is, to my mind, the case most of the time). When one reads 'il était vêtu d'un sabadoor gris et ses babouches blanches étaient couvertes de poussières. Le tengaade posé sur sa tête n'avait non plus rien de singulier' (Diop 2009: 90), even if sabadoor and tengaade are not explained, there is no ambiguity about what they refer to (a cloth; a hat). But here Diop asserts the preeminence of Wolof words over European ones.

European explorers used to pepper their travelogues with African terms. They surely had a reason for doing so. Beyond a kind of exoticism, one plausible explanation is that local languages express with a greater accuracy the reality that has to be described. Trying to translate everything may not always be the best solution as it implies that any word can find an equivalent in any target language, an assumption very likely to be challenged. Instead of trying to go on with translation, footnotes or glossaries, translators can bet on the original words themselves, considering that they are powerful enough to break through the cultural barriers. It is a way of highlighting the capacity of original languages to reveal new realities, otherwise left quite unattended.

In his way of dealing with French and Wolof, Diop seems to prefer the idea that both languages remain impervious to each other; the logic of hybridization or association is replaced by one of transposition that assumes that a writer does not write the same things when using different languages. Such a way of working on languages is also linked to Diop's conception of literary creation. Bastardizing or desacralizing the French language may be a way of subverting it, but at the same time French still stands at the centre. For Diop, what is important is to give African languages a central place and use them to offer new perspectives and new ways of telling and thinking.

Because languages and literary patterns are different, they convey experiences in their own ways.

(Self-)translation underlines that choice of narrative matters, and shifts and adaptations occur in order to reach a broader audience.

Languages and the circulation of texts

Indeed, the way of telling a story matters. I have just explained that orality remains important in the African world. By 'orality', I do not mean only how voices permeate written texts but more obviously how literature is uttered rather than read, and transmitted from mouth to mouth. This brings us to the question of the reception of Doomi Golo in Senegal. How many copies of the text were sold? How did the text manage to reach its public? And who constitutes this public? In the absence of precise figures from the publisher, it is quite difficult to tell, but some information is still available. If the text found its readership and was rather well received in Senegal, it is also true that only a few people had real access to the book. Of course, we must keep in mind that Wolof is far from being the only language spoken in Senegal. If this language is quite widely understood and spoken, there are still numerous non Wolophone Senegalese who were de facto excluded from the reading. Even for Wolophone people, things were not that easy. This was all the more true in rural areas, where Diop had an interesting experience. As few people were able to read Wolof (even the intellectual elite who are mostly educated in French are not always used to reading it) or to afford the book, a single copy was often read aloud by a literate person so that the words could reach a wider audience. 14 Wolof written words have thus quickly been re-oralizedm and Boubacar Boris Diop, deciding that it was all the more important that his text could circulate through the oral media, recorded his own reading of the book and made it available in e-book format. This leads me to think once more about how languages, texts and reception are connected. If we look back at the publication of Doomi Golo ten years ago, what can be learnt from this experience? Diop still writes in his mother tongue, but has come back to French to write and publish some of his latest books. Doomi Golo remains his only novel in Wolof. The field of publishing in France (and in French) is much more stable and efficient than the African one. Economic realities, as well as the rather small number of potential readers in Senegal, act as barriers to the consistent development of publishing companies in the country. The audio-circulation of texts could be a solution to be developed, but it is true that e-books are still expensive (the initial price came close to twenty dollars). Moreover, few people have access to credit cards in Senegal and buying a book online is far from a common habit! Diop himself admits that the system rather failed. But there are ways to bypass the problem, and five community radio stations in Dakar broadcast the whole text of Doomi Golo in August 2014, showing once more how more important the oral sphere is in regard to the written one. 15 It was such a popular success that since 31 August five other community radio stations (in Thiès, this time) have continued the experience. However, and quite interestingly, if Diop is still publishing in French, it does not mean that he has stopped writing in Wolof. On the contrary, his mother tongue is now his creative tongue, which prevails on French. Against all odds, even if Diop's text is to be published in France before Senegal, the original version of a literary text is in Wolof, to then be (self-)translated into French. This is currently the case for the biography about Capitaine M'baye Diagne that Diop is writing at present, and which will be published in Paris by Philippe Rey. 16 Confronting himself with his mother tongue, Diop made his way from a political/ethical choice to a poetic one. His mother tongue turned out to be, for him, easier and more natural to use, revealing itself as the 'true' literary language. Writing this, I am of course deeply aware that there is no 'true' or 'better' language in which to create, but that the author, in his ways of negotiating his art, feels more comfortable with onein this case Wolofto convey his feelings and stories. But, it is also interesting to point out that a kind of selection implies operating between languages, which would need to be more precisely analysed. If Diop is writing poetry, drama and fiction in Wolof, 17 he continues to use French for articles, pamphlets and essays. As far as publication is concerned, his poetry and drama are to be published in Wolof in Senegal, whereas his novels and, above all, essays are usually published in France. The author gives three main reasons to this fact. First of all, and it is especially true for essays, there are economic and political reasons: Diop wants these texts to be efficient and widely read. Thus, they must be immediately available. As publishing in Senegal, and especially in African languages, is quite hard and a long process, Diop prefers to turn to French publishers. Second, and as Diop himself puts it, feelings are not implicated while writing essays: 'Il n'y a pas d'émotion là-dedans'. As such, French can be elected as the most relevant language, especiallyand that is the third pointbecause Diop feels that he is not competent to write essays using Wolof, because he is not used to certain notions and concepts. 18 His mother tongue remains more efficient to catch sounds and voices, and to convey his inner feelings. This seems to suggest that because of the literary traditions and the different habits of the public, language may have an implication upon the generic aspect of creation and vice versa. Ngũgĩ wa Thiong'o had already given convincing examples of this interaction between language, literary patterns and writing while recording his theatre experience with the Kamiriithu Center (Wa Thiong'o 2011: 80). Looking at Diop's production, Wolof seems more likely to embrace the poetical aspects of literary creation, whereas French is seen as a more incisive tool, chosen when it comes to debate, question and denounce. 19 But between the two languages and their literary traditions, there are of course bridges to build, and there are other issues to question. As Diop finally Fall, which was published in French in 1967. If translation is giving texts a broader audience, it also proves the literary potential of every language, a potential that has sometimes been denied to African languages. Recently, Wolof and Pulaar have begun to gain their Lettres de noblesse as literary languages in Senegal, even if the economic field is still in search of firmer basis. There is no doubt that translation holds a special place in this cross-fertilization between words and cultures and that Boubacar Boris Diop's experience with Doomi Golo has borne fruit beyond expectations.

Here are a few occurrences through the pages of the French edition: 87, 93, 160, 219, 248, 291, 333, 336, 377, 418. 11 Kocc Barma Fall (Birima Maxuréja Demba Xolé Faal, 1586-1655) is a Senegalese philosopher.

His maxims are a very important part of the Wolof cultural ground. Most of the Senegalese call him 'Suñu màam Kocc': our grandfather Kocc.

12 Cosaan comes from the verb sos, which means 'to create' (to found). It can be translated as 'origins', and also as 'past', 'tradition' and even 'history'. Translation into European languages is always difficult as the meaning of the word in Wolof heavily depends on the context of utterance and also becauseand Boubacar Boris Diop clearly points out the fact in the quote already givensocieties and cultures order the world according to various perspectives. Another well-known example of 'untranslatability' has been pointed out by Ahmadou Kourouma himself about the word monnè present in his book title Monnè, outrages et défis.

13

Boubacar Boris Diop, personnal communication, 2013. 14 Boubacar Boris Diop, personnal communication, 2010. 15 The radio stations are Ndef-Leng-FM; Oxy-Jeunes; Afia-FM; Jokkoo-FM and Rail-bi-FM. They will broadcast twenty minutes of text every Monday for twenty weeks (see http://www.aps.sn/articles.php?id_article=131520).

16

By the time of revision of this text (September 2014), Diop seems to have decided to set this work apart and is currently working on a novel written in Wolof B'ammeelu Kocc Barma (Le tambour de Kocc Barma). 17 One piece of poetry 'Biir ak biti' and one play Ibu Ndaw boroom jamono have been written in Wolof and are awaiting publication. At this point, I do not want to suggest that some languages are 'only good' for poetry and others for 'thoughts, but that the way an individual is born and raised within literary traditions and specific educational systems can have a lasting impact on his/her creation. The more often essays are written and published in Wolof, the more people will read them and try their hand at the genre.

  puts it: Il ne s'agit pas simplement de jeter des passerelles entre Kocc Barma et Molière dans l'espoir de pouvoir gambader, le coeur léger, sur les deux rives de ses émotions. Le défi majeur est de réussir à concilier les deux logiquessouvent en conflit ouvertde production et de réception du texte. (2012) In Diop's case, it appears that this statement has had two repercussions: first, there is a further involvement in what the French call la chaîne du livre. Diop is not only a writer but has also become an actor of the publishing field, who tries to develop the circulation of texts and ideas. With his colleagues Felwine Sarr and Nafissatou Dia Diouf he has created and managed a bookshop in Dakar, offering texts in French as well as in Wolof. Second, experimenting in self-translation triggered a deep interest in the role of translation. Teaching Wolof literature since a few years at the Université Gaston Berger in Saint. Louis, he has also decided to pursue the translation of major francophone texts (mostly from the Senegalese area) into Wolof, making them available to a new public. Some classical works such as Cheikh Hamidou Kane's L'Aventure ambiguë (1961), Mariama Bâ's Une si longue lettre (1979/2007) and Camara Laye's L'Enfant noir (1953) have already been translated into Wolof, and Diop is currently working on La Plaie, a novel by Malick

Once again, Diop does not mean to suggest that one cannot develop philosophical discourses or thoughts in Wolofon the contrary, he can quote Senegalese intellectuals who dobut that he himself lacks the practice to do so.

Le temps de Tamango (1981) To this point, I must make it clear that it is not my case and that even if my interests lay in issues such as African languages in the editing field I cannot read Wolof. This contribution is thus indebted to many critics mentioned in the bibliography and also to Boubacar Boris Diop himself. I am very grateful to them.

6

For example, Ibrahima Wane: 'Avec Doomi Golo, Boubacar Boris Diop n'a pas seulement gagné le pari de réaliser une fiction majeure dans sa langue maternelle, l'écrivain fait du même coup un pas important dans l'approfondissement de son art du récit' (2005).

7

Both griots and jottalikat are people mastering spoken words (in fact, most jottalikat are griots) and transmitting important messages mostly dealing with history or religion. The jottalikat is speaking for the chef de confrérie (the religious leader, most of the time of a qadiriyya) because the status of this one forbids him to speak directly to his audience, especially in a loud voice. The jottalikat is the one who speaks aloud his message.

8

Boubacar Boris Diop, unpublished personal communication, 2010. 9 Boubacar Boris Diop, personal communication, 22 November 2014.


Alain Jean-Marie
email: .jean-marie@inria.fr

Issam Rabhi
email: issam.rabhi@inria.fr

marmoteCore : a software platform for Markov modeling

Keywords: Stochastic Operations Research, Markov Chain, modeling software

Introduction

We present the marmoteCore software, an open environment for modeling with Markov chains, developed within the MARMOTE project. 1 This platform aims at providing the general scientific user with tools for creating Markov models and computing, or simulating, their behavior. It provides a software library implementing both basic models and methods "from the book" and advanced solution methods : either general, or for specific classes of models. marmoteCore is devised to be a collaborative platform, able to embed solution methods and software developed by independent teams. We describe its architecture and some of its features, including its capability to communicate with established scientific software such as R.

The need for marmoteCore. Modeling with Markov chains is an activity common to many fields of science and engineering. Interacting particle systems of Physics, genome evolution models of Biology, epidemic models of Medicine, population models of Ecology, queueing systems of Operations Research, all those popular models are based on Markov chains. Monte-Carlo simulations of Markov chains are commonly used for producing samples of distributions of combinatorial objects, physical systems etc. This practical importance has prompted the development of many modeling software for specific areas : GreatSPN for Petri Nets, CADP and PRISM for Model Checking to name some of the most known, as well as demonstration packages in general modeling software such as scilab or R. On the other hand, there exists up to now no software environment providing the general scientific user with, at the same time, a collection of ready-to-use well-known models and general modeling constructions and solution methods, all accessible using an uniform programming interface. Realizing the prototype of such a platform is one of the purposes of the marmoteCore project.

Architecture

An object-oriented perspective. The objectives of the project make the choice of objectoriented programming almost obvious. Object-oriented languages give the possibility of designing high-level abstractions for mathematical concepts, representing objects with common properties. Yet, through the mechanism of inheritance, the user has the flexibility of controling the implementation of specific instances of the model. We illustrate this idea below. The organization of marmoteCore relies a lot on hierarchies of models, and polymorphism. We have chosen the C++ language, in part due to the fact that the legacy code available to us is written in C/C++. Core objects. marmoteCore is based on four principal abstractions : markovChain, statSpace, transitionStructure and distribution.

The distribution class implements the probabilistic concepts that are underlying stochastic models in general, including the ubiquitous Bernoulli, Geometric and Exponential distributions.

The transitionStructure class is an abstraction for the labeled state-to-state transitions that are common to discrete-time and continuous-time Markov chains. Typical methods of this object include get/setEntry() accessors, and evaluateMeasure()/ evaluateValue() representing respectively right-and left-vector/multiplications in the language of linear algebra. This class can be implemented with regular two-dimensional arrays (full or sparse), but also with methods not based on the comprehensive storage of values but on symbolic manipulations. It is possible to represent this way processes on potentially infinite state spaces.

The stateSpace class implements discrete sets of states, with elementary objects such as integer intervals, and elementary constructions such as Cartesian products and unions. Typical methods such as nextState(), index() and decodeState() are convenient for traversing complex state spaces and constructing transition structures in an algorithmic way.

The hierarchy of Markov models. The fourth principal class, markovChain, is developped in a large variety of specific Markov models. The idea is that to each particular family of model, there can be specific implementation of data structures and, above all, of solution methods optimized for the particular family.

As an example, consider the following sequence of inclusions of well-known models in Markov modeling : Poisson ⊂ MMPP ⊂ MMPP/M/1 ⊂ HomogeneousQBD ⊂ QBD ⊂ MarkovChain. At the level of Poisson processes, the representation of the transition structure is reduced to one parameter, the arrival rate. Also, most metrics (e.g. transient probabilities, hitting times) are available in closed form. As we move up in the hierarchy, algorithms for computing the same metrics can be implemented. For instance : specific algorithms exist to compute level passage times in QBDs (Quasi-Birth-Death processes). At the highest level, the algorithms are applicable to any Markov chain, a fortiori to subclasses.

Solution methods. This object architecture offers a large flexibility for implementing and using solution algorithms. The practitioner, developing a model for a specific situation, has the choice between several algorithms for computing performance metrics and can choose the one that turns out to be the more efficient. The developper of new solution methods uses the existing ones for checking the validity of the new computations, then as benchmark for assessing their precision and speed. The current version of marmoteCore comes with generic algorithms for finding stationary distribution and average hitting times, and performing Monte-Carlo simulation for trajectories, stationary distributions and hitting times.

Integration with existing software

The architecture of MARMOTE has been devised to ease up the interaction with existing scienfic software. This can be done in two ways. First, MARMOTE can be made available to existing platforms in the form of "plugins" or "libraries". In the other direction, MARMOTE can make use of functionalities of such platforms through calls to their specific libraries.

The first possibility can used notably in the interaction with Workflow Management Systems and related graphical programming tools, so as to make easier the use of the software by scientists not fluent in C++.

To illustratethe second possibilty, we have developped an interface with the markovchain package of the scientific software R. 2 Functions from this package such as is.irreducible(), is.accessible() or rmarkovchain() are wrapped and provided as C++ calls in the API of marmoteCore. Technically : using the RInside library of R, an execution engine for the R language is run inside marmoteCore. Markov models are passed to this engine, as well as calls to the wrapped package. We are currently wrapping other external packages such as Markov chain procedures in scilab, or the Xborne package developped at the Versailles Saint-Quentinen-Yvelines University, and the PSI3 package developped in the MESCAL team. 3 2. https://cran.rstudio.com/web/packages/markovchain/index.html 3. http://psi.gforge.inria.fr/dokuwiki/doku.php?id=psi3:start

MARMOTE (MARkovian MOdeling Tools and Environments), is a project funded by the French research agency, grant ANR-12-MONU-00019. See : https://wiki.inria.fr/MARMOTE/Welcome


Giacomo Micheli
email: giacomo.micheli@math.uzh.ch

Joachim Rosenthal
email: joachim.rosenthal@math.uzh.ch

Reto Schnyder
email: reto.schnyder@math.uzh.ch

Hiding the carriers in the polynomial Naccache Stern knapsack cryptosystem

 that are meant to hide the prime elements used for decryption.

Introduction

The Naccache Stern Knapsack cryptosystem (NSK) is a public key cryptosystem first presented in [START_REF] Naccache | A new public key cryptosystem[END_REF]. It is based on the subset product problem in a large prime field. However, as it has already been observed in [2, Subsection 5.2], in the NSK protocol a quite obvious DLP reduction is available. In Section 2 we recall the NSK and give few details on an attack that can be performed. In Section 3 we will produce a version of the polynomial knapsack presented in [START_REF] Micheli | A general construction for monoidbased knapsack protocols[END_REF] that is menat to hide the carriers p i for which one performs the attack. The main idea behind this new instance of the knapsack problem relies on the following two facts, which we present here in an informal way:

-In the isomorphism class of the prime field F p (that contains the space of cyphertexts of the NSK) there is "somehow" just one standard representative, which consists of the integers modulo p. -In the isomorphism class of the finite field F q n with n > 1 (that contains the space of cyphertexts of the polynomial knapsack cryptosystem described in [START_REF] Micheli | A general construction for monoidbased knapsack protocols[END_REF]) there are many equally valid representatives: one for each irreducible polynomial of degree n over F q . This difference will be exploited in what follows. Some security considerations are also provided in Section 5.1. Finally a more general function field version of the protocol is provided in Section 6.

Notation

Let q be a prime power and let F q be the field with q elements. In this paper, the univariate polynomial ring in Z will be denoted by F q [Z]. Let now g(Z) ∈ F q [Z] be an irreducible polynomial of degree d, and consider the quotient map π : F q [Z] -→ F q [Z]/(g(Z)). We will denote by z the element π(Z). More generally, in the whole paper a transcendental element over F q will always be denoted by a capital letter, whereas its image in some quotient field of the polynomial ring will be denoted by a lower case letter if it is clear which projection we are considering. We write an element of F q [z] = F q [Z]/(g(Z)) as h(z), where h(Z) is its unique lift to F q [Z] of degree at most d -1. We mainly encounter the following situation in this paper: Let X, Y transcendental over F q and f (X)

∈ F q [X], g(Y ) ∈ F q [Y ] irreducible polynomials over F q of degree d. Then, F q d ∼ = F q [X]/(f (X)) = F q [x] but also F q d ∼ = F q [Y ]/(g(Y )) = F q [y].

Recalling the NSK protocol

We recall the Naccache-Stern knapsack cryptosystem [START_REF] Naccache | A new public key cryptosystem[END_REF]. Let p and p 1 , . . . , p n be primes such that n i=1 p i < p. Often, the p i are the first n primes, and p is the smallest prime greater than their product. The secret key is a random invertible integer modulo p -1: s ∈ Z * p-1 as well as its inverse t = s -1 . The public key consists of v i = p s i ∈ F p . We will often call these elements carriers.

An n-bit message m = (m 1 , . . . , m n ) ∈ {0, 1} n is now ecrypted as c = n i=1 v mi i ∈ F p .
In order to decrypt a ciphertext c, it is first raised to the power t:

c t = n i=1 (p mi i ) st = n i=1 p mi i ∈ F p .

Now, since

n i=1 p mi i < p, this can be lifted to the integers, where it is easy to check divisibility by the p i .

Remark 1. The main parameter that has to be tuned in the NSK protocol is the information rate n/ log 2 (p) i.e. the ratio between the information contained in the message (number of bits of the message) divided by the modulus (number of bits of the cyphertext). For practical implementations, this ratio is about 1/10 [5, Table 1].

Remark 2. It is clear how to attack NSK assuming we can solve a DLP in F p as follows: If the p i have been chosen as the first n primes (that is a greedy choice if we want to maximize the information rate), they are assumed to be known, and s can be recovered by solving p s i = v i for any i. Even if the p i are chosen otherwise, the smallest among them has to be less than p 1/n . Since n is usually quite large (the original paper recommends n ≥ 160 [START_REF] Naccache | A new public key cryptosystem[END_REF]), it can thus be guessed for reasonable parameters.

In what follows we will provide a a way to avoid this kind of attack.

In what follows we will in fact show a strategy that hides the knowledge of the low degree polynomials keeping the information rate unchanged. The basic idea is to work in two representations of the same finite field, only one of which is public. We first observe that prime fields are not suited for this, since for each prime p we have exactly one representation of F p for which the computations in the NSK are possible. The polynomial based variant presented in [START_REF] Micheli | A general construction for monoidbased knapsack protocols[END_REF] on the other hand is very well suited for this, since each finite field F q d has roughly q d /d representations of the form F q [X]/(f (X)) (see for example [START_REF] Lidl | Finite fields[END_REF]).

Let F q be a finite field and p 1 (Z), . . . , p L (Z), f (Z), g(Z) ∈ F q [Z] be irreducible polynomials such that

L i=1 deg p i (Z) < deg f (Z) = deg g(Z) =: d. Fix furthermore a field isomorphism φ : F q [X]/(f (X)) → F q [Y ]/(g(Y )).
Fix now a random exponent s ∈ Z * q d -1 as well as its inverse t = s -1 and let v i (y) = φ(p i (x)) s ∈ F q [y] for i ∈ {1, . . . , n}. The public key consists of (g(Y ), {v i (Y )} i ). The secret key consists of (t, {p i (X)} i , f (X), φ).

The encryption of an n-bit message m = (m 1 , . . . , m n ) ∈ {0, 1} n is essentially the same as in Section 2:

c(y) = n i=1 v i (y) mi ∈ F q [y] = F q [Y ]/(g(Y )). To decrypt, compute m(x) := φ -1 (c(y) t ) = n i=1 p i (x) mi ∈ F q [x] = F q [X]/(f (X)),
and canonically lift the result to F q [X]. For all i, decrypt as

m i = 1 ⇔ m(X) ≡ 0 mod p i (X).
Remark 3. Here we would like to point out the advantage of this version of the polynomial based protocol compared to the NSK: The information rate of the NSK protocol can be tuned by minimizing the degree of the modulus p, which can be done by minimizing the degree of the carriers p i . Unfortunately, whenever this is done, a DLP reduction becomes easier, as we already pointed out in Remark 2. More generally, in the NSK and the polynomial based variant of [START_REF] Micheli | A general construction for monoidbased knapsack protocols[END_REF] it is possible to balance information rate and security. In what we presented, the information rate can always be tuned to the top, since the carriers will be hidden by the (arbitrary) choice of the finite field representation. In Section 5 a deeper analysis of the security is provided.

Remark 4. Notice that breaking this variant of the polynomial based protocol is at least as difficult as breaking the original one: just fix f = g and φ the identity morphism. Moreover the encryption is exactly as expensive as in the NSK and the polynomial based variant (under the formalism presented in [5, Section 2] it is actually the same). the decryption differs from the NSK for just one additional step: the computation of φ -1 of the cyphertext.

Example

In order to immediately clarify the ideas, we give a small example over F 2 . All calculations were done using the Sage computer algebra system [START_REF] Stein | Sage Mathematics Software (Version 6.1.1)[END_REF]. We choose d = 11 and the public polynomial

g(Y ) = Y 11 + Y 10 + Y 8 + Y 7 + Y 6 + Y 3 + 1.
Further, we pick a random element of

F 2 [y] = F 2 [Y ]/(g(Y )
) that is not contained in a proper subfield: a(y) = y 10 + y 9 + y 4 + y and compute its minimal polynomial in X i.e. f (X) ∈ F q [X] :

f (X) = X 11 + X 10 + X 9 + X 8 + X 7 + X 6 + X 5 + X 4 + X 3 + X + 1.
The isomorphism φ is now given by

φ : F 2 [x] → F 2 [y]
x → a(y).

To compute the inverse of φ, we just need to find the preimage of y. Since this preimage is a root of g(X), we can find it by factoring g(X) over the field F 2 11 in the representation F q [x] and checking for each root r(x) whether φ(r(x)) = y. b(x) = φ -1 (y) = x 10 + x 3 + 1.

We now choose p 1 (X), . . . , p n (X) to be the five irreducible polynomials of lowest degree in F 2 [X]:

p 1 (X) = X p 2 (X) = X + 1 p 3 (X) = X 2 + X + 1 p 4 (X) = X 3 + X + 1 p 5 (X) = X 3 + X 2 + 1,
and randomly select the secret exponents s = 1967 ∈ Z * 2 d -1 and t = s -1 = 1612. The public key consists of the elements

v i (y) = φ(p i (x)) s ∈ F 2 [Y ]/(g(Y )): v 1 (y) = y 9 + y 6 + y 5 + y v 2 (y) = y 8 + y 7 + y 6 + y 5 + y 4 + y 2 v 3 (y) = y 8 + y 4 + y 3 + 1 v 4 (y) = y 9 + y 6 + y 3 + y + 1 v 5 (y) = y 10 + y 9 + y 8 .
We now encrypt the message m = (1, 1, 0, 0, 1) and get the ciphertext c = v 1 (y)v 2 (y)v 5 (y) = y 9 + y 4 + y 2 + y. To decrypt, compute φ -1 (c(y) t ) = x 5 + x 3 + x 2 + x, which, when lifted to F 2 [X], factors as

X 5 + X 3 + X 2 + X = X • (X + 1) • (X 3 + X 2 + 1) = p 1 (X)p 2 (X)p 5 (X),
from which the message m is recovered.

Efficiency analysis

In this section, we compare the efficiency and performance of our new protocol to the traditional NSK [START_REF] Naccache | A new public key cryptosystem[END_REF] and the unmodified polynomial based variant [START_REF] Micheli | A general construction for monoidbased knapsack protocols[END_REF], as well as other public key cryptosystems.

The size of the public key is unchanged compared to [START_REF] Micheli | A general construction for monoidbased knapsack protocols[END_REF], being roughly (n + 1)d log q bits. The secret key contains an additional polynomial of degree d and one field element of F q [x], so it is roughly twice as large, at around 4d log q bits. Encryption consists of up to n -1 multiplications in F q d . Decryption on the other hand requires raising an element of F q d to the exponent t ≤ q d -1, which takes up to 2d log q multiplications with the square-and-multiply method. Furthermore, the evaluation of the inverse field isomorphism φ -1 consists of evaluating a polynomial in F q [Z] of degree less than d at an element of F q d , taking at most d multiplications in F q d by Horner's method. Finally, decryption involves the reduction of a polynomial in F q [Z] of degree less than d by n fixed distinct polynomials of small degree, which is cheap compared to the first two steps even when done naively. Compared to [START_REF] Micheli | A general construction for monoidbased knapsack protocols[END_REF], the only difference in cost is the evaluation of the isomorphism, so the cost of decryption only increases by a factor of roughly 1 + (2 log q) -1 .

For the multiplication of polynomials and elements of F q d , it may be worthwhile to use algorithms based on the fast Fourier transform [START_REF] Cantor | On fast multiplication of polynomials over arbitrary algebras[END_REF], since our polynomials have large degree.

We now try to find concrete secure parameters. It is recommended in [START_REF] Naccache | A new public key cryptosystem[END_REF] to use at least n ≥ 160 carriers in order to avoid birthday attacks. Following this recommendation, we can for example choose the parameters q = 19 and d = 307, which allows for n = 162 carriers. The reason we do not choose q = 2 or another very small prime is that this causes the polynomials f and g to have very large degree, making it harder to compute the preimage φ -1 (y). With these parameters, we get a public key size of roughly 212 kbit. Using different q and d that achieve a similar number of carriers does not seem to change the key size dramatically. Indeed, it appears that the value d log q is similar in size to n log n whenever n is chosen maximally.

Regarding information rate, we again get similar values to [START_REF] Micheli | A general construction for monoidbased knapsack protocols[END_REF][START_REF] Naccache | A new public key cryptosystem[END_REF]. In particular, the above parameters give an information rate of 11.8%. There are various tricks to improve on this at the cost of key size, see for example [START_REF] Naccache | A new public key cryptosystem[END_REF][START_REF] Chevallier-Mames | Linear bandwidth naccache-stern encryption[END_REF]. We will however not discuss these in this paper.

In this section we will analyse the difficulty of recovering either a field representation in which a certain set of elements has small degree or attacking the relations between the carriers v i .

Recovering the hidden field

Given a finite field F q and d > 1, we consider the question of finding a representation of F q d in which a set of field elements have low degree. By a representation of F q d , we mean a pair (f (X), φ) with f (X) ∈ F q [X] irreducible of degree d and φ : F q d → F q [X]/(f (X)) a field isomorphism fixing F q .

Proposition 1. Let a ∈ F q d and 2 ≤ m ≤ d. Then, there exist at most (m-1)q m representations (f (X), φ) of F q d such that φ(a), canonically lifted to F q [X], has degree less than m. All of these pairs can be listed in time Õ(q m ).

Proof. Let (f (X), φ) be such a representation. We have that φ(a) = h(x), where x ∈ F q [X]/(f (X)) is the equivalence class of X and h(X) ∈ F q [X] has degree less than m. By inverting the isomorphism, we get that h(φ -1 (x)) -a = 0, so

φ -1 (x) is a root of h(X) -a in F q d .
h(X) -a has at most m -1 roots in F q d . Each root ρ, if not contained in a proper subfield of F q d , uniquely determines a representation (f (X), φ). Indeed, f (X) is the minimal polynomial of ρ, and φ :

F q d → F q [X]/(f (X)) is determined by φ(ρ) = x.
Hence, for a fixed polynomial h(X) of degree less than m, there are at most m -1 representations such that φ(a) = h(x). Since there are only q m choices for h(X), there are at most (m -1)q m representations with φ(a) having degree less than m. They can be listed by simply enumerating all possible h(X) and the roots of h(X) -a in F q d . We now consider the question of finding a representation in which a set of elements a 1 , . . . , a n have a low degree simultaneously. Clearly, if such a representation exists, it can again be found in time Õ(q m ) by listing all representations in which a 1 has low degree. However, we show that such a representation is unlikely to exist for most parameters.

Corollary 1. Let 2 ≤ m ≤ d, and let a 1 , . . . , a n ∈ F q d be chosen independently and uniformly at random. Then, a representation (f (X), φ) with φ(a i ) having degree less than m for all i exists with probability less than (m -1)q d+n(m-d) .

Proof. Fix a representation (f (X), φ) such that φ(a 1 ) has degree less than m. Since the a i are independent, we have that φ(a i ) ∈ F q [X]/(f (X)) are still uniformly random for i ∈ {2, . . . , n}. Hence, the probability of all of them having degree less than m is q m q d n-1 = q (n-1)(m-d) . Since there are at most (m-1)q m choices for the representation, the total probability of a desired representation existing is less than (m -1)q m+(n-1)(m-d) = (m -1)q d+n(m-d) .

For our cryptosystem, we conclude that the exponents s are essential for security. If the public parameters are simply chosen as v i (y) = φ(p i (x)), it is easy to recover a field representation that allows decryption. On the other hand, assuming the values (φ(p i (x)) e ) i∈{1,...,n} for a random large e are sufficiently close to uniformly random elements, it is not possible to find a representation that allows decryption without finding the secret exponent s.

Attacking the relations between the v i

It is easy to see that in our scheme, unlike in the original NSK, there is no way to recover the secret exponents s and t from a single public key element v i (y) = φ(p i (x)) s . Indeed, given a fixed v i (y) ∈ F q [y], there exists for each exponent t and low degree polynomial

p i (X) a representation (f (X), φ) such that v i (y) t = φ(p i (x)) ∈ F[y], assuming that p i (X) -v i (y) t has a root in F q [y]
that is not in any proper subfield.

However, the public key consists of many elements v i (y) = φ(p i (x)) s , and they are not independent of each other. For example, consider the case p 1 (X) = X, p 2 (X) = X + 1. The attacker knows that v 1 (y) t + 1 = v 2 (y) t for some unknown t. Hence, the attacker has a criterion to check whether a guess for the secret exponents s and t is correct.

Since our goal is to repair the structural weakness of the polynomials NSK against attacks on the small factors p i , let us assume for a moment that the attacker has a way to solve the DLP in the finite field F q [y]. For example, assume the attacker knows that v 2 (y) = v 1 (y) a for some a. The above relation can be rewritten as (v 1 (y) t ) a -(v 1 (y) t ) + 1 = 0, so t can be recovered by finding roots of X a -X + 1 = 0 in F q [y] and solving another DLP. However, the degree of the polynomial equation is a, which in general is exponential, so standard methods for finding roots are not applicable.

To reduce the degree of the equation, the attacker can hope to find an integer e ∈ [1, αq d/2 ] such that (ea mod q d -1) ≤ αq d/2 , where α > 0 is some parameter. This can often be found by brute force. In that case, the solutions to the equation X ae mod q d -1 -X e + 1 = 0 correspond to the solutions of X a -X + 1 = 0, so it is enough to solve a polynomial equation of degree at most αq d/2 . However, the attack still runs in exponential time and is infeasible for practical parameters.

An attack using both a DLP-oracle and an SVP-oracle

We thank Cristophe Petit for pointing out that, having access to an SVP-and a DLP-oracle, a simple way to attack the problem is the following: Solve the discrete logarithms v xi 1 = v i and v l 1 = c. Then try to solve the additive knapsack m 1 + L i=2 m i x i ≡ l mod q d -1. This can be done using the algorithm in [START_REF] Matthijsj | Improved low-density subset sum algorithms[END_REF] for solving any of the subset sum problems m 1 + L i=2 m i x i = l + k(q d -1) for k ∈ {1, . . . , L}. It is a matter of further investigation whether this attack is practical for reasonable parameters.

The following is an attempt to prevent this kind of reduction: Restrict the space of messages to strings of constant Hamming weight T . The condition on g then becomes deg(g) > L i=L-T +1 deg(p i ). Moreover, T , g and L must be chosen in such a way that q deg(g) << 2 L . We now expect there to be many solutions to the subset sum problem, of which only one leads to the plaintext. Further analysis would be needed to establish whether this trick effectively prevents the attack.

Challenge

We provide the following instance as a challenge. Again, all calculations were done using Sage [START_REF] Stein | Sage Mathematics Software (Version 6.1.1)[END_REF]. Let q = 19, d = 307, L = 162 and

g = 72CI64EI6I6D9DGA81B2EC0GH5074I42C0F3I9B7GA22 2874FGFF2AI5CA68B20909IH60I7DH42HD8BH3964E20 H4DH39128C2I2I9FHIE4371D8HBBC4A94997BHAF6F86 GEF9BDGH4CA7H69GC21GFGEG19GH68E8CH74HAE619IB 6C35F5D7A1CFE0DD61724BD8C29F235F6C65CAB2G718 2DD9F2I22I5GCII03E0AI9399C43IC4BC453A65B3CEE 497BAC44290915DF537D0F3468D49F630C037DC06D71.
The polynomial is encoded as follows: The first character is the coefficient of the constant term, the last is the coefficient of x 307 . The elements 0 through 18 of F 19 are represented by the characters 0 through 9 and A through I. The values of the carriers v i are available upon request.

The following ciphertext encrypts a random message:

c = 97ADFGDEEH5FI3C0700E6EF4F7117CCIEG2FAFC88123 5HB7H754G406BC40D278FGEA2BA80E442DBE8F96G1E8 B2610AF99B5386DBH921A665I581F960II9D022IH0H3 A02I2E1B2HHHBDG16CID71A6GD62A7B090CGE605H1BB A5802I9279GI1CD317BGH1H7IB8857BC71848A6ABC99 21G0CE57BG3C666B4II100IGC60G2IDCA79EG857A6FF 0GE0E1F0HC9H53I4D2H67D949G4GHG2G0HA8CF5820H0.
The corresponding message should be recovered as an element of {0, 1} 162 .

Function Field Knapsack Scheme

In this section we show a more theoretical version of the scheme that uses the context of function fields of curves. For the notation and definitions we refer to [START_REF] Stichtenoth | Algebraic function fields and codes[END_REF]. Let F be a function field over a finite field F q . We denote by O P the valuation ring associated to the place P . Moreover, if f ∈ O P , then we denote by f (P ) its image in the residue field O P /P . Let {P 1 , . . . , P L } distinct places of F . Let x i be a uniformizer of the place P i invertible in the valuation ring O Pj for j = i (this can be done thanks to the Approximation Theorem for valuations). Now observe that L(D) evaluates at P into the finite field F q deg(P ) . In addition L(D) embeds into F q deg(P ) since an element in the kernel of the evaluation would live in L(D -P ) but D -P is a divisor of negative degree, so L(D -P ) = 0. Remark 6. Call ψ the embedding of L(D) into F q deg(P ) . Observe that, given an F q -basis {e 1 , . . . , e l(D) } of L(D), ψ -1 (c) is computable for any c in the image of ψ. In fact it is enough to write down c = L i=1 a i ψ(e i ) for some a i ∈ F q ; then ψ -1 (c) = L i a i e i .

Let M = {0, 1} L be the space of messages and C := F q deg(P ) be the space of cyphertexts. Let e, d ∈ Z for which ed ≡ 1 mod q deg(P ) -1. Now we are able to set up public and private key:

-Public key: (F q deg(P ) , {x 1 (P ) e , . . Remark 7. The reader should notice that in this case hiding the residue field is not necessary, since the attack does not have available the function field used for decryption, but only the residue field.

Fix P a place

  of the holomorphy ring O containing the subring generated by x 1 , . . . x L . Choose P satisfying deg(P ) > L i=1 deg((x i ) ∞ ) and let D = L i=1 (x i ) ∞ Let l(D) := dim Fq (L(D)). Remark 5. Notice that, for any (m 1 , . . . , m L ) ∈ {0, 1} L , we have

  . , x L (P ) e }) -Private key: (F, d, {x 1 , . . . , x L }, ψ) Encryption and decryption are defined as -Encryption: let m = (m 1 , . . . , m L ) ∈ M. The encryption map is defined by E(m) := L i=1 (x i (P ) e ) mi . -Decryption: Let c ∈ C. Compute c d and invert ψ, getting c = L i=1 x mi i .

The authors were supported in part by Swiss National Science Foundation grant number 149716 and Armasuisse.

Acknowledgements

The authors were supported in part by Swiss National Science Foundation grant number 149716 and Armasuisse.


Rafael Gregorio Lucas

D ' Oliveira
email: rgldoliveira@gmail.com

Marcelo Firer
email: mfirer@gmail.com

Embedding Distances into the Hamming Cube

In Coding Theory, two different decision criteria types are mostly used: a maximal likelihood (relative to a probabilistic model of a channel) and a nearest neighbour criterion (relative to a distance model of the channel). In this work we present an algorithm that, given a maximal likelihood criterion, decides if there is a nearest neighbour criterion that matches it and, in this case, produces a metric that determines such a criterion. It is also shown that the Hamming metric is universal, in the sense that any metric, up to a decoding equivalence, can be isometrically embedded into a hypercube with the Hamming metric.

Introduction

The Binary Symmetric Channel (BSC) is the simplest model of a discrete channel, and is used for many reasons, including the fact it represents the worst case scenario, when there is no available information about the channel. In this context, the Hamming metric has an outstanding and prominent status, since it is matched to the BSC, in the sense that, for any code C and for any received message x, we have that c ∈ C is the most likely codeword to be sent if, and only if, it is the codeword closest to x. Many different channels are considered in the context of Information Theory, and also many different metrics are considered in the context of Coding Theory. A recent survey can be found in [START_REF] Gabidulin | A brief survey of metrics in coding theory[END_REF] and in [START_REF] Michel | Encyclopedia of distances[END_REF][Chapter 16]. However, the general question about matching a channel and a metric has been little explored in the literature. This general setting, of matching a metric to a channel (and vice-versa) was first asked by Massey, in a class note from 1967 [START_REF] James | Notes on coding theory, class notes for course 6.575[END_REF]. Considering only the family of metrics that are defined over the alphabet and extended additively over the coordinates (which includes the Hamming and the Lee metrics), in 1980 Gérald Séguin [START_REF] Séguin | On metrics matched to the discrete memoryless channel[END_REF] gave necessary and sufficient conditions to a channel to be matched to such a metric. Since then, the problem of matching a channel and a metric stayed abandoned, until recently, when Walker and Firer proved that a metric can be matched to the Z-Channel (and some other general questions on the subject) [START_REF] Firer | Matched Metrics and Channels[END_REF].

In this work we look at this problem as a problem of finding a solution to a set of linear inequalities and produce an algorithm (Section 3) that either produces a metric matched to the channel or shows the non-existence of such a metric. If the possibility of considering metrics holds for a vast family of channels (other then the BSC) and metrics (other then the Hamming), the universality of the Hamming metric is fully assessed in Section 4, where we show that any metric on a finite set, up to a decoding equivalence, may be isometrically embedded into a hypercube with the Hamming metric (d H ), which, from now on, we refer to as the Hamming cube.

Distances, Channels and Decoders

Even though we speak about metrics in the introduction, we will consider more general distances.

Let X be a set. A distance is a function d :

X × X → R such that 1. d(x, y) ≥ 0 2. d(x, y) = d(y, x) 3. d(x, x) = 0
If the distance also satisfies the triangle inequality (d(x, z) ≤ d(x, y)+d(y, z)) and the identity of indiscernibles (d(x, y) = 0 iff x = y) it is a metric.

If the set X is an additive group and d(x + z, y + z) = d(x, y) we say that d is translation invariant. In this case the distance is totally determined by a weight function ω : X → R, defined by ω(x) := d(x, 0), so that d(x, y) = ω(x -y).

We are concerned only with finite sets, thus nothing is lost if we assume X to be the set [n] = {1, 2, 3, . . . , n}. We also identify the distance with its matrix representation d n×n such that d ij = d(i, j).

We define a channel using the notation of probability theory.

Definition 1. A channel over [n] is an n × n probability matrix P such that

P ij = P (j received |i sent).
Thus, it is a matrix P n×n with entries in [0, 1] such that

j P ij = 1.
As usual, in the context of information theory, the interpretation is that a transmitter sends a symbol j ∈ [n] to a receiver and the channel determines the probability he receives i ∈ [n]. We remark that the probabilities are defined over the set of elements of X, that may be considered as a set of all possible messages and not an alphabet out of which messages are written by considering blocks of letters.

Given a code C ⊆ [n] the maximum likelihood decoder (MLD) decodes j by searching which c ∈ C maximizes P (j recieved |c sent), that is, j is decoded as an element of the set arg max{P (j|c) : c ∈ C}. This is equivalent to looking for the largest number in the jth column restricted to the rows corresponding to codewords. This means that the MLD only cares about the ordering of the elements in the columns, and not their values.

If there is a distance function d defined on [n], then the minimum distance decoder (MDD) decodes j by searching which c ∈ C minimizes d(j, c).

Given a distance d and a channel over [n] we say that they are matched to each other if arg min{d(j, c); c ∈ C} = arg max{P (j|c); c ∈ C} for every C ⊆ [n], and j ∈ [n]. It is well known that the Hamming metric is matched to the binary symmetric channel. What about for general channels? As was said in the introduction, very little is known about this problem. We do not face this problem directly, but in the next section we will show an algorithm that enables us to match a distance for any particular channel or show that no such distance exists.

Finding a Distance Matched to a Channel

There are many different notions of equivalence between distances which are used all throughout mathematics. The following one has not been investigated yet (to the authors' knowledge), despite it being quite natural in the context of coding theory. Definition 2. Let X be a set and d 1 , d 2 two distance functions on X. We say that d 1 ∼ d 2 if they define the same minimum distance decoder, in other words, if arg min{d 1 (j, c); c ∈ C} = arg min{d 2 (j, c); c ∈ C} for any code C ⊆ X and any i ∈ X.

It is straightforward to prove that this amounts to the distances having the same set of balls:

Proposition 1. d 1 ∼ d 2 iff for every x 0 ∈ X and r 1 ∈ R there exists an r 2 = r 2 (x 0 , r 1 ) ∈ R such that B d1 (x 0 , r 1 ) = B d2 (x 0 , r 2 ), where B d (x, r) = {y ∈ X : d(y, x) ≤ r}.
In the coding theory literature most, if not all, distances used are metrics. However, there are many known basic constructions which can transform a distance satisfying the identity of indiscernibles into an equivalent metric, and thus matching a channel to a distance or to a metric is essentially the same problem. The next example is a particular case of the "squeezing" argument presented in [START_REF] Firer | Matched Metrics and Channels[END_REF].

Example 1. Let d 1 be a distance satisfying the identity of indiscernibles. Then

d 2 (x, y) = 1 + d 1 (x, y) max u,v d 1 (u, v)
for x = y and zero otherwise is a metric which is equivalent to d 1 .

Analogously to the distance case we have the following equivalence relation between channels. Definition 3. Let M and N be two channels. We say that M ∼ N if for any code C ⊂ X, they define the same maximum likelihood decoder.

As previously discussed, after Definition 1, when decoding by the MLD only the order of the elements in a column are important. We therefore define a function which orders a matrix's entries in each column. Because of space constraints we give a simple definition which is made clear by an example. A more rigorous definition would require us to define other concepts, in this case related to partially ordered sets. Definition 4. Given a matrix M its decreasing column ordered matrix is the matrix

O -M such that (O -M ) ij = k iff it is the kth largest element of the jth column.
The definition is analogous for the increasing column matrix O + M .

An example will make the idea clear.

Example 2. If M =   9 2 1 9 7 0 8 6 8   then O -M =   1 3 2 1 1 3 2 2 1   and O + M =   2 1 2 2 3 1 1 2 3   Note that O -M = O -N iff O + M = O + N .
Directly from the definition we have the following.

Proposition 2. M ∼ N iff O -M = O -N or equivalently O + M = O + N . Proposition 3. Given two distances d 1 and d 2 , d 1 ∼ d 2 iff O + d 1 = O + d 2 or equivalently O -d 1 = O -d 2 .
As said earlier we are identifying the distance with its matrix representation.

Thus, determining if for some channel M there is a distance d matched to it is equivalent to determining if there exists a distance d such that O -M = O + d, in other words, we have the following question:

Question 1. Given a matrix M n×n does there exist a distance d on [n] such that O -M = O + d?
This is equivalent to solving the following inequalities on d(i, j):

d(i, j) = d(k, j) if O -M ij = O -M kj d(i, j) < d(k, j) if O -M ij < O -M kj
and, the symmetry conditions d(i, j) = d(j, i). Note that since d(i, i) = 0, this implies that O + d ii = 1, thus we must have O -M ii = 1. Note also that the inequalities come from fixing the column.

We proceed as follows:

We have n chains of inequalities, each corresponding to a certain column. The smallest element of each chain must be d(i, i) which we set to equal zero. Then:

1. We take the first chain and set arbitrary values for the distances with the condition that the inequalities hold true; 2. We then set the same values to their corresponding symmetric term, i.e.

d(i, j) = d(j, i); 3. We continue to do this until we have assigned a value to every distance and have therefore found a distance matched to our channel; or, 3'. Find that some distance cannot have a valued assigned to it, and thus there is no distance matched for this channel. Then,

O -M =   1 3 2 2 1 3 3 2 1   .
We have the following three chains of inequalities:

0 = d(1, 1) < d(1, 2) < d(1, 3) 0 = d(2, 2) < d(2, 3) < d(2, 1) 0 = d(3, 3) < d(3, 1) < d(3, 2)
We set arbitrary values to the first column and the same ones to their symmetric counterparts.

0 = d(1, 1) < 1 = d(1, 2) < 2 = d(1, 3) 0 = d(2, 2) < d(2, 3) < 1 = d(2, 1) 0 = d(3, 3) < 2 = d(3, 1) < d(3, 2)
In the next step we must set an arbitrary value to d(2, 3) but it is impossible to do this since it must satisfy

2 = d(3, 1) < d(2, 3) < 1 = d(2, 1).
Therefore, no distance exists for M since it would need to satisfy Then,

d(2, 1) < d(3, 1) < d(2, 3) < d(2, 1).
O -M =   1 3 3 2 1 2 3 2 1   .
We have the following three chains of inequalities:

0 = d(1, 1) < d(1, 2) < d(1, 3) 0 = d(2, 2) < d(2, 3) < d(2, 1) 0 = d(3, 3) < d(3, 2) < d(3, 1)
We set arbitrary values to the first chain and to their symmetric counterparts.

0 = d(1, 1) < 1 = d(1, 2) < 2 = d(1, 3) 0 = d(2, 2) < d(2, 3) < 1 = d(2, 1) 0 = d(3, 3) < d(3, 2) < d(3, 1) = 2
We do the same for the second chain.

0 = d(1, 1) < 1 = d(1, 2) < 2 = d(1, 3) 0 = d(2, 2) < d(2, 3) = 1 2 < 1 = d(2, 1) 0 = d(3, 3) < d(3, 2) = 1 2 < d(3, 1) = 2
We were able to set values to all the distances. Therefore, M has the following distance:

d =   0 1 2 1 0 1 2 2 1 2 0   .

Embedding Distances into the Hamming Cube

In this section we prove that any distance satisfying the identity of indiscernibles is equivalent to a distance which is embeddable into the Hamming cube. If, in addition to this, the distance is translation invariant over F n 2 , the embedding, f , will behave well with respect to addition, i.e. f (x + y) = f (x) + f (y).

We first note that there is a natural bijection between the n-dimensional Hamming cube H n , and the subsets of [n], 2 [n] given by supp : H n ↔ 2 [n] where supp(x) = {i : x i = 0}. This function satisfies the following properties:

1. supp(x + y) = supp(x) supp(y) 2. ω H (x) = |supp(x)|
where A B = {x ∈ A -B} ∪ {x ∈ B -A} is the symmetric difference between the sets A and B.

This is important because we will pose the problem as a problem on sets. We first prove the translation invariant case over F n 2 . The general case will follow as a consequence.

Theorem 1. Let d 1 be a translation invariant distance, with weight ω 1 , satisfying the identity of indiscernibles over F n 2 . Then there exists a translation invariant distance d 2 , with weight ω 2 , over F n 2 that is equivalent to d 1 and is isometrically embeddable, preserving addition, into the Hamming cube.

Proof. Denote by {e

1 , e 2 , • • • e n } the canonical basis of F n 2 . Let δ I = ω 1 ( i∈I e i ) for every I ⊆ [n] such that I = ∅.
Without loss of generality we can assume that δ I ∈ Q + since only the order relation between the values matters.

Note that for any given m, k ∈ N if

w 2 ( i∈I e i ) = mδ I + k for every I ⊆ [n] such that I = ∅, then d 1 ∼ d 2 .
In Theorem 3 we prove that there exists finite sets A i and constants m, k ∈ Z + such that for every I, the cardinality of their symmetric difference is

| i∈I A i | = mδ I + k. Let N = |∪ i A i | and f : F n 2 → 2 N such that f (e i ) = A i .
Then it is straightforward to show that supp -1 • f is a weight preserving embedding from (F n 2 , d 2 ) into the Hamming cube which is equivalent to d 1 and also that the transformation from d 1 to the Hamming cube behaves well with respect to addition. The identity of indiscernibles is needed to prove that f is injective.

As a consequence of Theorem 1 we can now prove the result for any distance satisfying the identity of indiscernibles.

Theorem 2. Let d 1 be a distance over X satisfying the identity of indiscernibles. Then there exists a distance d 2 such that d 1 ∼ d 2 and d 2 is embeddable into the Hamming cube.

Proof. If we let X = {x 1 , x 2 , . . . , x n } and

δ I = d(x i1 , x i2 ) if I = {i 1 , i 2 } (i 1 = i 2 ) 1 otherwise
for every I ⊂ [n] such that I = ∅, we can use the same arguments as in Theorem 1. Essentially, we define an additive group structure on d 1 and end up in the same situation as Theorem 1.

If we remove the condition of satisfying the identity of indiscernibles, as said before, we lose injectivity in our embedding. There are many ways to deal with this, but we will not explore them here.

To prove Theorems 1 and 2 we need to solve the following problem: Given δ I ∈ Q + where I ⊂ [n], does there exist finite sets A 1 , . . . , A n and constants m, k ∈ Z + such that

| i∈Ij A i | = mδ Ij + k.
We call these equations a system of symmetric differences. We solve this system by trying to solve

| i∈Ij A i | = δ Ij
and working out the problems that prevent us from finding a solution.

We use the following relation, if

A = {A 1 , . . . , A n } then | A| = n l=1 (-2) l-1 i1 =i2 =... =i l |A i1 ∩ A i2 ∩ . . . ∩ A i l |. (1)
This gives a recursive formula to find all intersections in terms of the symmetric differences. With all the intersections it is possible to build the full Venn Diagram of A 1 , . . . , A n .

To prove that the algorithm works, at each step, the constant m is used to ensure that mδ I ∈ N (since the cardinality of a set is a natural number) and the constant k is used to ensure that, at each step, the correct intersection inequalities are satisfied, like for example,

|A ∩ B ∩ C| ≤ |A ∩ B|.
Essentially, we need each component of the Venn diagram of A 1 , . . . , A n to be non-negative.

The key to prove Theorem 3 are the following lemmas which we provide without proof, both of which can be done by induction on Equation 1.

Lemma 1. Let A = {A 1 , . . . , A n } and B = {B 1 , . . . , B n }. Suppose that for ∅ = I ⊆ [n] | i∈I A i | = δ I and | i∈I B i | = mδ I . Then, i∈I B i = m i∈I A i
considered formally in the sense that they satisfy equation 1.

Lemma 2. Let A = {A 1 , . . . , A n } and B = {B 1 , . . . , B n }. Suppose that for

∅ = I ⊆ [n] | i∈I A i | = δ I and | i∈I B i | = δ I + 1.
Then,

i∈I B i = i∈I A i + 1 2 |I|-1
considered formally in the sense that they satisfy equation 1.

With these two lemmas we can prove our result. As stated before, Theorem 1 and Theorem 2 follow straighforward from Theorem 3. Those two theorems together with the inequalities analysis made in Section 3, allows for a geometric-analytic approach to the problem of matching distances and metrics to channels including the possibility of approximating a channel by a metric and other analytic-like results. One of our goals is to study the packing radius under general metrics, and in particular to see if we can better understand perfect codes, since for many metrics, it is an open problem if there exists any. This geometric approach also allows us to get better embeddings. For example, we can show that the best embedding, in terms of minimizing the dimension of the Hamming cube, of Example 5 is into H 11 . Some results in this direction that are already proved and some that are under work, will be presented in future works.

Theorem 3 . 2 .= 2 1 |B C| = 2 Using 1 |B ∩ C| = 1 2 |A ∩ C| = 1 2 |A ∩ B ∩ C| = 1 4 1 4 |B ∩ C| = 2

 322121221142 Given δ I ∈ Q + where ∅ = I ⊂ [n], there exists finite sets A 1 , . . . , A n and constants m, k ∈ Z such that| i∈I A i | = mδ I + k.Proof. Find the values of the intersections of the A i recursively from| i∈I A i | = δ Iusing Equation 1. Then, use Lemma 1 to make all values integers and Lemma 2 to guarantee the intersection inequalities are valid, and therefore, that each component of the Venn diagram of A 1 , . . . , A n is non-negative.We give an example that illustrates how to obtain m and k. Example 5. Consider the following translation invariant metric, d with weight ω, over F 3 Thus we must solve the following system of symmetric difference. |A| = 3 |A B| = 3 |A B C| = 3 |B| = 2 |A C| = 3 |C| = Equation 1 recursively we can determine that |A ∩ B| = Adding to the initial conditions and then multiplying by 2, using the lemmas, we get |A| = 8 |A ∩ B| = 3 |A ∩ B ∩ C| = 1 |B| = 6 |A ∩ C| = 2 |C| = This gives us an embedding f : F 3 2 → H 12 such that f (001) = 111111110000 f (010) = 000001111110 f (100) = 000011000011 and decoding on the image of f in (H 12 , d H ) is equivalent to decoding on (F 3 2 , d).