Homosexualité et migration, Droit au séjour et couple homosexuel

Depuis 1974 et la fermeture des frontières françaises à l'immigration économique, seul le droit d'asile 1 et l'immigration familiale permettent aux étrangers d'être légalement admis sur le territoire français. L'immigration familiale est organisée principalement par la procédure du regroupement familial qui autorise l'accueil de la famille du ressortissant étranger séjournant en France.

Le regroupement familial a toujours été défini limitativement par le législateur. C'est sur la base d'un standard « majoritaire et dominant » 2 , « d'une normalité » de la définition de la « famille » que s'est fondé le législateur, pour définir les bénéficiaires du regroupement familial. C'est la conception de la « famille » communément admise en France ou « culturellement acceptable par la nation » 3 qui pousse le législateur français à poser une étroite définition des membres de la famille admissibles au regroupement familial. De ce fait, les bénéficiaires du regroupement sont le conjoint marié et leurs enfants mineurs. Aucune admission des concubins, des partenaires en union libre ou des partenaires de même sexe n'est possible au titre du regroupement familial. Seuls les « conjoints institutionnalisés » sont autorisés à bénéficier du regroupement familial. Cette approche traditionnelle du « couple hétérosexuel » exclut par conséquent, un certain nombre d'autres relations de couple, en particulier les couples homosexuels. En se limitant à une approche de la « famille normale » 4 , le législateur ne tient aucun compte des changements sociaux et des conceptions « nouvelles » de la « famille ».

Derrière cette conception restrictive de la famille se cache, par ailleurs, un désir de l'État de limiter les entrées légales sur le territoire. Cette absence de prise en compte des couples non mariés traduit aussi une volonté politique de limiter l'immigration légale.

Toutefois, avec l'instauration du pacte civil de solidarité ( PACS ) 5 , une forme nouvelle de couple est s'institutionnalisée. Pour la première fois en France, le « couple homosexuel » est légalement reconnu. Devant ce changement et cette innovation du droit, il est opportun de s'interroger sur la place de cette loi relative au PACS face au droit de l'immigration familiale. Apporte t-elle des ouvertures en terme de droit au séjour pour l'étranger « pacsé » qui désire faire venir son partenaire de même sexe ?

Face à cette question, le législateur français s'est montré particulièrement frileux, il n'a pas modifié les bénéficiaires du regroupement familial après l'adoption de la loi relative au PACS en 1999 6 . Les changements vont peut être avoir lieu grâce au droit communautaire de l'Union européenne. Avec la « communautarisation » de la politique migratoire, les avancées 1 Les persécutions liées à la transsexualité d'un étranger entraînent la reconnaissance de la qualité de réfugié sur la base de l'appartenance à un groupe social, CE 23 juin 1997 Ourbih, req. 171858. Il semble que le Conseil d'État reconnaisse aussi la qualité de réfugié aux persécutions d'homosexuels appartenant à un groupe social. CE 12

juridiques des États membres montrent une possible extension de la définition « du couple admissible » au regroupement familial. Les travaux préparatoires ont soulevé la possibilité d'inclure « les couples non mariés », donc les partenaires homosexuels étrangers, dans la définition communautaire des bénéficiaires du regroupement familial ( I ).

Outre l'admission au regroupement familial, il existe une autre alternative pour être admis au séjour. Celle-ci est prévue par l'article 12 bis 7 de l'ordonnance de 1945 relative au statut général de l'étranger. Cet article permet d'accorder la carte de séjour temporaire mention vie privée et familiale valable un an, après un examen de la vie privée et familiale du ressortissant étranger. Cette carte est une récente innovation instituée par la loi Chevènement7 de 1998. Cette nouveauté n'est que la traduction des conséquences de la jurisprudence8 de la Cour européenne des droits de l'Homme et plus particulièrement de l'article 8 de la Convention européenne des droits de l'homme 9 . Cet article 8 de la CEDH apparaît comme une protection subsidiaire de la vie privée et familiale de l'étranger, et ce, à côté du regroupement familial. Cette protection subsidiaire est précieuse : -elle s'est avérée être une arme efficace pour les étrangers menacés d'expulsion ou de reconduite à la frontière. Ils peuvent invoquer l'article 8 pour faire annuler une mesure d'éloignement. -Elle a permis également d'annuler des refus de titre de séjour ou des refus de visa qui portaient atteinte à la vie privée et familiale de l'étranger.

Le juge administratif est l'autorité normalement compétente quant à l'application de cette protection subsidiaire. Il est devenu aujourd'hui le gardien de la bonne application de l'article 8 de la CEDH sur le statut interne de l'étranger. L'utilisation de ce principe européen lui a permis d'élaborer sa propre approche du concept de « la vie privée et familiale ». C'est ainsi qu'il a pu élargir la conception de « la vie privée et familiale » de l'étranger puisqu'il a fait une place aux relations homosexuelles.

Peu après l'adoption de la loi relative au PACS, le juge administratif a eu en effet à se prononcer sur la « vie privée et familiale » de deux ressortissants étrangers de même sexe ayant conclu un PACS 10 . La conclusion d'un PACS a donné l'occasion au juge administratif d'examiner les relations homosexuelles des étrangers au regard du droit de séjour ou contre des mesures d'éloignement. En conséquence, les relations homosexuelles sont envisagées dans l'analyse de la vie privée et familiale de la protection subsidiaire de l'article 8 de la CEDH ( II ).

I/ Les avancées communautaires : l'admission « des partenaires non mariés » au titre du regroupement familial

Les avancées juridiques communautaires prévoient la faculté d'inclure les « partenaires non mariés », donc les relations homosexuelles, dans les catégories d'étrangers admissibles au regroupement familial ( A ). Les premiers travaux préparatoires des États membres témoignaient d'ambitieuses avancées juridiques, pourtant la directive relative au regroupement familial adoptée le 22 septembre 200311 marque un net recul. Les négociations entre pays membres ont souffert des aléas de la politique et de l'économie des différents États européens ( B ). Au final, la directive prévoit la simple « possibilité » d'inclure les partenaires non mariés dans les bénéficiaires du regroupement familial. Il ne s'agit pas là d'une obligation pour les États membres mais d'une alternative laissée à leur appréciation. Ceci amoindrit les espoirs de voir inclure les partenaires non mariés dans les droits nationaux. Seul l'opportunisme politique conduira certains États membres à introduire cette nouveauté dans leur droit interne ( C ).

A/ Apports des travaux préparatoires : les partenaires homosexuels, nouveaux bénéficiaires du regroupement familial L'immigration familiale a toujours été une importante préoccupation dans le travail des États membres. La prise en compte de la politique familiale de l'immigration a débuté dés l'adoption du Traité de Maastricht. Le 30 juin 1993, les États membres ont tenté un premier effort avec l'adoption d'une résolution12 . Cette résolution tendait à harmoniser, au plan européen, les possibilités de réunion des familles étrangères. Cet instrument ne disposant d'aucune valeur contraignante, il n'a servi qu'à influencer les différentes législations nationales, sans obligation de résultat. Par ailleurs, ce premier acte commun avait une approche minimale des conditions du regroupement familial puisque aucune disposition ne concernait l'admission des « couples non mariés », ou des couples homosexuels.

Depuis la « communautarisation »13 de la politique de l'asile et de l'immigration dans le Traité d'Amsterdam en 199914 , les États membres se sont lancés dans la préparation d'instruments législatifs contraignants sur le droit au séjour des ressortissants extra communautaires. Dés, le 1 er décembre 1999, un premier projet15 de directive16 assez ambitieux a vu le jour. Il marquait un tournant car il prévoyait une approche moins restrictive de la politique commune relative à l'immigration familiale.

L'article 5 §1 a)17 de cette proposition de directive permettait « aux partenaires non mariés » ayant une relation durable, d'entrer en Europe par le biais du regroupement familial. Que signifiaient les termes « partenaires non mariés » pour les États membres ? Incluaient-il les partenaires homosexuels ? Aucune précision n'était donnée dans la proposition.

La conférence de presse et l'exposé des motifs18 de la Commission européenne qui ont suivi cette proposition de directive, ont répondu à ces questions. Une obligation pour les États membres d'étendre le regroupement familial aux « partenaires de même sexe » était posée. Il est regrettable que ces derniers termes n'aient pas été inscrits dans le texte même de la proposition. Cette absence s'explique sans doute par les réticences de certains pays à admettre le regroupement familial aux « couples de même sexe ». Les modifications successives de la proposition de directive relative au regroupement familial confirmeront cette hypothèse par la suite. L'article 5 §1 a) expose ensuite que : « La disposition sur le partenaire non marié s'applique uniquement dans les États membres dont le cadre juridique assimile la situation des couples non mariés à celle des couples mariés ». Autrement dit, l'obligation relative aux « couples non mariés » ne s'impose que s'il existe un cadre juridique interne reconnaissant cette forme de relation. Cette précision limite la portée de l'article 5 puisqu'il ne peut pas s'appliquer aux États membres qui ne disposent pas encore de cadre de reconnaissance de cette forme de couple. En France, le cadre juridique qui permet de reconnaître la situation des couples non mariés existe, grâce à la loi relative au PACS. Cette limitation ne concerne donc pas l'État français. Pour finir, la Commission européenne impose que la preuve de la cohabitation19 du couple soit apportée et que le caractère durable de la relation soit prouvé par des témoignages dignes de foi, afin dit-elle, d'éviter les éventuels abus. La proposition de directive étendait également le regroupement familial aux enfants mineurs20 ( adoptés ou non ) du regroupant ou de son partenaire non marié, et aux enfants majeurs21 lorsqu'ils ne sont pas mariés et qu'ils ne subviennent pas objectivement à leur besoin. Ceci était particulièrement audacieux, cela revenait à reconnaître implicitement la « parentalité homosexuelle ». Autrement dit, on admettait que les couples de même sexe puissent élever ou adopter22 des enfants et les faire venir par le biais du regroupement familial ( ce qui était interdit en France ). La proposition reconnaissait aussi la possibilité de faire venir les ascendants 23 à charge qui n'avaient plus de soutien familial dans leur pays d'origine ; ceci est également interdit dans le droit français.

Au terme de cette analyse, il convient de remarquer combien cette première proposition de directive était audacieuse tant sur le plan de l'extension du droit au séjour pour le partenaire homosexuel que sur les autres membres de sa famille. Toutefois, faute d'accord sur ce premier essai, deux autres travaux préparatoires vont se succéder, dont le contenu est beaucoup moins ambitieux.

B/ Des travaux préparatoires « sous influence »

Le consensus étant impossible sur la première proposition de directive, les États membres ont élaboré un deuxième projet de directive. Cette seconde proposition24 adoptée en 2000 a confirmé globalement les avancées juridiques concernant les partenaires non mariés. Cependant, le texte du projet ne contient pas explicitement les termes de « partenaires de même sexe », seule demeure la formule « partenaire non marié ».

En raison de ses ambitions, cette deuxième proposition de directive n'a pas non plus été adoptée. Les oppositions de certains États membres s'expliquent pour partie par la conception traditionnelle de la « famille » dans les pays de fortes cultures catholiques. Ainsi, les pays du Sud25 de l'Europe se sont montrés particulièrement hostiles à l'admission des partenaires de même sexe. Ils ont beaucoup discuté cette définition extensive du « conjoint ». Elle semblait trop éloignée de leur législation. La proposition de directive du 10 octobre 2000 a donc été « remodelée » pour laisser place à une troisième proposition. Une seconde explication justifie l'absence d'accord sur le deuxième projet de directive et l'élaboration d'un troisième : les évènements du 11 septembre 2001 et le ralentissement économique qui a suivi, ont modifié les orientations de la politique européenne d'immigration. Admettre les partenaires non mariées, leurs enfants et leurs ascendants à charge, implique une augmentation conséquente de l'immigration légale. En France, l'article 29 de l'ordonnance de 1945 n'accorde le regroupement familial qu'à deux catégories : le conjoint marié et les enfants mineurs. Il écarte les unions hors mariage ( les concubins et les bénéficiaires du Pacte civil de solidarité30 ). Pourtant, la législation française reconnaît le concubinage et le PACS comme des unions alternatives en droit de la famille. A partir de là, il devient parfaitement possible pour le législateur français d'accorder le regroupement à un étranger « pacsé » ou en concubinage. Il suffirait de modifier l'article 29 de l'ordonnance de 1945 et d'accepter les autres unions à la lumière du droit au regroupement familial. Mais, la directive ne présentant pas le regroupement des partenaires non mariés comme une obligation31 pour chaque État, il est à craindre que la France tarde à modifier sa législation. La flexibilité de cet accord n'incitera pas tous les États et notamment la France à entreprendre des mesures qui admettent légalement de nouveaux étrangers sur le territoire commun. Le principal problème de cette flexibilité laissée aux États membres, est qu'elle aboutit à une « harmonisation à géométrie variable ». Les autorités nationales disposeront d'une initiative propre pour la mise en oeuvre de la disposition sur les couples non mariés. On va aboutir ainsi à des législations très variées sur l'admission des couples non mariés.

La récente modification 32 de l'ordonnance de 1945 tient compte des travaux communautaires en matière d'immigration, mais le nouveau texte est muet sur la question des couples non mariés. De surcroît, la « loi Sarkozy » a pris en compte les récentes orientations communautaires très restrictives en matière d'immigration clandestine : mesures d'éloignement prises par un autre État membre, fichiers d'empreintes digitales etc. Perdant ainsi de vue les objectifs de la directive relative au regroupement familial, l'immigration familiale, le principal volet de l'immigration légale est ainsi desservie par la lutte contre l'immigration irrégulière. Tout ceci laisse peu d'espoir sur une prochaine ouverture du regroupement familial aux couples homosexuels. Il existe cependant une alternative au regroupement familial pour les couples homosexuels : demander la carte de séjour mention « vie privée et familiale » prévue par l'article 8 de la CEDH.

II / Les relations homosexuelles : un élément d'analyse de la vie privée et familiale de l'article 8 de la CEDH

Depuis une importante jurisprudence de 1991 33 , les étrangers peuvent invoquer l'article 8 de la CEDH lorsqu'un refus de titre de séjour, un refus de visa, ou une mesure d'éloignement porte atteinte à leur vie privée et familiale.

Cette protection de la vie privée et familiale de l'article 8 de la CEDH a conduit le législateur français à instaurer une carte de séjour mention vie privée et familiale ( 12 bis 7 de l'ordonnance de 1945 ) 34 . Qu'entend le législateur par la formule « la vie privée et familiale » de l'étranger ? Inclut-il les relations issues d'un couple homosexuel ? Autrement dit, l'article 8 de la CEDH conduit-il à protéger les partenaires de même sexe contre une mesure d'expulsion ou une reconduite à la frontière ? Permet-il d'octroyer une carte mention vie privée et familiale à des partenaires de même sexe « pacsés » ?

Pour savoir si la relation homosexuelle permet d'obtenir un titre de séjour mention vie privée et familiale, il faut analyser si elle entre dans la définition posée par le juge européen et par le juge administratif ( A ). Dans cette définition de la vie privée et familiale, le juge administratif a une vision plus large que le juge européen ; pour lui, la conclusion d'un PACS, qui officialise la relation homosexuelle, devient un élément dans son analyse du respect de la vie privée et familiale ( B ). Pourtant le PACS n'entraîne pas nécessairement l'attribution d'une carte de séjour mention vie privée et familiale. Il ne constitue qu'un paramètre positif dans le faisceau d'indices examiné pour la délivrance de cette carte. Ainsi, les conséquences juridiques du PACS se révèlent très décevantes tant sur le plan du droit au séjour que sur la protection contre l'éloignement et même sur le plan du droit de la nationalité ( C ).

A/ L'appréciation du principe de la vie privée et familiale et les relations homosexuelles par les juges européens et administratifs 33 Depuis peu, le juge français adopte une approche plus large de la vie privée et familiale. Ceci s'explique par son analyse « séparée » de la notion de la vie privée et de la vie familiale de l'étranger.

Jusque là, dans le contentieux des étrangers, le juge administratif adoptait la même « conception enveloppante »35 du principe de la vie privée et familiale, que celle développée par la Cour européenne des droits de l'Homme. Celle-ci permettait de ne retenir la violation de l'article 8 que sur la base exclusive de la vie familiale de l'étranger. Ainsi, les liens privés que l'étranger avait noué ne permettaient pas à eux seuls, d'obtenir la violation de l'article 8. Or, le juge européen ne range [START_REF] Levinet | Couple et vie familiale[END_REF] pas les relations homosexuelles dans la « vie familiale » ; pour lui, elles appartiennent à la vie privée des individus. A partir de là les couples homosexuels étrangers ne sont pas pris en compte dans l'analyse européenne de l'article 8 ( 1 ). L'analyse « indépendante » de la vie privée permet au juge administratif de prendre en compte les relations homosexuelles et d'accorder la protection de l'article 8 de la CEDH ( 2 ).

1) « L'approche familiale » du juge européen : l'exclusion des relations des couples homosexuels étrangers

Pour annuler une mesure d'éloignement ou admettre au séjour un étranger, le juge européen s'intéresse surtout aux relations familiales du ressortissant étranger et ce, même si des éléments de la vie privée l'aident parfois dans son analyse [START_REF] Sudre | La construction » par le juge européen du droit au respect de la vie familiale[END_REF] . Il a ainsi une « approche familiale » de l'article 8. Même si dans les affaires Boughanemi c./ France 38 , Chorfi c. / Belgique 39 , Baghli c. / France 40 et Ezzouhdi c./ France 41 , la Cour a analysé successivement les questions de l'atteinte à la vie privée [START_REF] Carlier | A cet égard voir les critiques de la doctrine relative à l'absence de l'utilisation de la vie privée dans le contentieux des étrangers[END_REF] et à la vie familiale de l'étranger, elle ne retient pas pour autant une approche autonome [START_REF]un part on assiste au « glissement » de l'analyse de la « vie privée » vers la « vie privée et Le juge européen a, d'abord, retenu une conception stricte de la « famille », il ne reconnaissait que la seule famille légitime[END_REF] des concepts.

Le premier arrêt admet clairement l'atteinte à la vie privée d'un étranger, compagnon d'un français souffrant d'un handicap physique. Le Conseil d'État parle d'un degré d'intégration suffisant et estime que l'étranger apporte un soutien affectif et moral, indispensable à son compagnon. Le second arrêt n'a pas permis d'annuler la mesure d'éloignement car le compagnon étranger disposait encore d'attaches dans son pays d'origine, mais il a eu le mérite de s'intéresser lui aussi à la vie privée. Ces arrêts ont permis pour la première fois de protéger des étrangers jusqu'alors exclus. Avec ces récentes décisions du Conseil d'État, le juge administratif étend la protection de l'étranger et érode un peu plus, les prérogatives de l'État en matière d'éloignement ou d'admission au séjour des étrangers. En effet, en sanctionnant les mesures d'éloignement au seul motif de l'atteinte à la vie privée, le juge administratif élargi le champs dans lesquels l'étranger est protégé. Désormais, les couples homosexuels sont reconnus à condition de remplir les exigences de stabilité de la relation. Incontestablement, la Cour européenne a donné au juge administratif les conditions essentielles de cette jurisprudence, mais c'est lui, qui par son travail, a amorcé cette nouvelle protection de l'étranger, en intensifiant l'examen de l'intégration personnelle de l'étranger en France, par le biais de la vie privée issue de l'article 8 de la CEDH.

B/ Une avancée symbolique : la conclusion d'un PACS est un élément d'analyse de la vie privée de l'étranger

La loi du 15 novembre 1999 61 relative au PACS prévoit dans son article 12 62 que « la conclusion d'un PACS constitue l'un des éléments d'appréciation des liens personnels en France, au sens de l'article 12 bis 7 de l'ordonnance du 2 novembre 1945 (…), pour l'obtention d'un titre de séjour ». Cet article 12 de la loi, consacre « l'autonomie des deux notions de vie privée et familiale, puisque la délivrance d'un titre de séjour peut désormais être envisagée au seul vu des liens personnels établis en France, à l'exclusion de toute référence à la sphère familiale » 63 . Même si cette possibilité est laissée à une large appréciation des autorités administratives, l'arrivée du PACS parmi les éléments permettant d'examiner les liens personnels ou privés pour l'octroi d'un titre de séjour est une avancée symbolique considérable.

La circulaire du 10 décembre 1999 64 qui précise la loi relative au PACS, souligne que l'octroi du titre de séjour ( 12 bis 7 de l'ordonnance de 1945 ) dépend de « la stabilité et d'une carte de résident, il ne conteste pas avoir conservé des liens familiaux en Colombie ; qu'il ne produit, en outre, aucun document établissant son insertion durable dans la société française ; qu'il résulte ainsi des pièces du dossier que, compte tenu de l'ensemble des circonstances de l'espèce, et notamment de la durée et des conditions de séjour de l'intéressé, et eu égard aux effets d'une mesure de reconduite à la frontière, l'arrêté du Préfet de police n'a pas porté aux droits de l'intéressé au respect de sa vie privée une atteinte disproportionnée aux buts en vue desquels a été pris ledit arrêté ». voir FERRAN N., « Les étrangers ont-ils une vie privée », Revue Plein Droit, 47 l'ancienneté » de la relation. Cette condition est déjà exigée pour les relations familiales de concubinage 65 , elle a naturellement été intégrée aux textes traitant du PACS. Ces deux exigences de « stabilité et d'ancienneté [START_REF] Jinbao | et 1 an de PACS ont permis d'annuler la reconduite à la frontière en raison de l'atteinte à la vie privée de l'étranger[END_REF] » ont été très critiquées car elles rendent aléatoires les chances d'obtenir une carte de séjour pour les partenaires « pacsés » [START_REF] Fulchiron | note sur TA Lyon, 6 avril 2000[END_REF] . En effet, l'examen de ces deux paramètres est censé mesurer le degré de la vie privée du requérant ; mais leur estimation est laissée au bon vouloir de l'administration, ce qui laisse la porte ouverte à toutes les appréciations. Trois décisions des tribunaux administratifs de Toulouse 68 , de Lyon 69 et de Clermont Ferrand [START_REF] Ta Clermont | Préfet du puy de Dôme[END_REF] illustrent ce côté incertain. Elles refusent de retenir l'atteinte à la vie privée « compte tenu de la durée et des conditions de séjour de l'intéressée en France et eu égard au caractère récent des relations nouées dans le cadre du PACS ».

Pour apprécier l'ancienneté de la vie privée de l'étranger, la circulaire a posé un délai minimum pour les relations « pacsées ». Un délai de cinq ans 71 a d'abord été exigé pour le ressortissant étranger pacsé à un autre ressortissant étranger et un délai de trois ans pour un ressortissant étranger pacsé à un français ou un ressortissant communautaire. Mais, cette circulaire a été partiellement annulée par une décision du Conseil d'État, le 29 juillet 2002 72 . A la suite de cet arrêt, ce délai a été ramené à un an pour tous les « pacsés » pour satisfaire une totale égalité de traitement. Désormais tous les couples homosexuels peuvent demander une carte mention vie privée et familiale au bout d'un an de vie commune.

C/ Des conséquences juridiques réduites

La première version du projet de loi relative au PACS, permettait la délivrance de plein droit d'un titre de séjour à l'étranger ayant conclu un PACS avec un Français ou un autre étranger, après un délai d'un an et sous réserve d'une entrée régulière. La version finalement présentée que l'on vient d'étudier en est très éloignée. Le PACS ne constitue qu'un élément dans l'appréciation de la vie privée [START_REF] Fulchiron | Le PACS et le droit des étrangers[END_REF] . A lui seul il ne permet pas de délivrer un titre de séjour de plein droit.

La discrimination entre couple homosexuel et couple hétérosexuel subsiste donc. En effet un couple hétérosexuel « pacsé » peut toujours se marier et bénéficier ainsi du regroupement familial. Ceci n'est pas possible pour le couple homosexuel, et même si le problème du mariage des couples de même sexe est souvent abordé, il est encore loin d'être réglé. Sur le plan de la protection contre l'éloignement, l'étranger « pacsé » ne dispose d'aucune garantie légale, et ce, même si la relation qu'il a noué est ancienne. Le conjoint étranger d'un ressortissant français est protégé contre certaines mesures d'éloignement par l'article 25 de l'ordonnance de 1945. L'étranger « pacsé » n'est pas intégré dans cette catégorie de ressortissants étrangers protégés contre les mesures d'expulsion et de reconduite à la frontière. Pour remédier à cet état du droit, une proposition de loi 74 a tenté d'aligner les garanties apportées par le mariage sur celle du PACS en matière de protection contre l'éloignement. Cette proposition si elle avait été adoptée 75 , aurait permis d'intégrer les étrangers « pacsés » dans la catégorie d'étrangers protégés contre les mesures d'éloignement.

Enfin, le PACS n'entraîne aucune conséquence sur le droit de la nationalité. La conclusion d'un PACS, ici encore, ne constitue qu'un élément d'appréciation pour « la condition d'assimilation 76 à la communauté française ». L'acquisition de la nationalité étant une faveur étatique et non un droit, le poids du PACS est alors très réduit. La conclusion d'un PACS avec un français ne permet pas à l'étranger pacsé d'acquérir la nationalité comme c'est le cas pour un étranger marié avec un ressortissant français. Là encore, le couple homosexuel est défavorisé par rapport au couple hétérosexuel, ce dernier pouvant toujours se marier pour acquérir la nationalité. Au moment de l'adoption de la loi relative au PACS, une proposition du groupe parlementaire communiste visait à accorder la nationalité française à l'étranger « pacsé » avec un français depuis au moins un an et à condition que la vie commune n'ait pas cessé. Cette dernière n'avait pas été retenue par le Parlement. Il est utile de souligner que, si le PACS et ses conséquences juridiques en droit des étrangers ont eu le mérite d'innover en donnant une place aux relations homosexuelles, cette place reste limitée et les conséquences juridiques demeurent aléatoires. Le PACS a permis de créer « un statut de seconde zone » pour le couple homosexuel face au même couple hétérosexuel.

La règle de droit a jusqu'ici reproduit le modèle dominant de la famille dans le droit de l'immigration. On attend aujourd'hui du droit et du politique qu'ils se montrent moins frileux et impulsent un changement qui corresponde aux évolutions de la société et mette fin aux discriminations.

Christel Cournil ATER en Droit Public Université des Sciences Sociales de Toulouse 1

74

  Proposition de loi AN N° 380, 19 novembre 2002, Rapport AN, N° 395, 26 novembre 2002 : l'article 2 § I. -Le 4°d e l'article 25 de l'ordonnance n° 45-2658 du 2 novembre 1945 relative aux conditions d'entée et de séjour en France des étrangers et portant création de l'Office national d'immigration est ainsi rédigé : «4° L'étranger, marié ou ayant conclu un pacte civil de solidarité, depuis au moins un an avec un conjoint ou un partenaire de nationalité française, à condition que la communauté de vie n'ait pas cessé et que le conjoint ou le partenaire ait conservé la nationalité française ». 75 Cette proposition a été rejetée le 28 novembre 2002 par Assemblée Nationale. 76 Article 21-24 du Code Civil.

  Tout ceci a poussé la Commission européenne à rédiger, en 2002, une troisième proposition de directive, très restrictive au regard des deux premières et ce, dans l'espoir que cette dernière version soit adoptée le plus rapidement possible. L'échec de la deuxième proposition de directive et l'élaboration d'une troisième s'expliquent par la diversité des législations concernant les bénéficiaires du regroupement familial dans les différents États membres. Face à cette difficulté, la Commission européenne a choisi d'opter pour une « harmonisation vers le bas » contrairement aux précédentes propositions. Autrement dit, à défaut d'accord rapide sur les deux premiers projets de directives, la Commission a préféré les sacrifier au profit d'un troisième projet ne retenant que les points communs des différentes législations des États membres. Il est évident que cette « harmonisation au rabais » témoigne des réticences des États membres à changer leurs législations sur un domaine touchant directement leur souveraineté nationale, telle que l'entrée d'une catégorie nouvelle d'étrangers sur le territoire. Cette troisième proposition 26 de directive apparaît donc comme un véritable texte de compromis. Cette volonté consensuelle se retrouve, en partie, dans la définition des bénéficiaires du regroupement familial et notamment des partenaires non mariés. En effet, la Commission européenne a transformé l'obligation d'inclure les partenaires non mariés, posée par la proposition de 1999 et celle de 2000, en une simple faculté proposée aux États membres. Par conséquent, la troisième proposition instaure le droit au regroupement familial au seul conjoint 27 marié au « regroupant ». La possibilité de faire venir « le partenaire non marié qui a une relation durable » 28 devient une simple éventualité offerte aux États qui souhaitent élargir les catégories de bénéficiaires du regroupement familial. La nouvelle proposition est donc moins exigeante quant à ce type de bénéficiaires ; c'est là le résultat des divergences rencontrées dans les discussions. Cette troisième proposition semble avoir atteint son principal objectif puisqu'un accord politique a abouti, assez rapidement, le 28 février 2003. Cet accord politique marque la fin d'un long et difficile processus de négociations, il annonce l'instauration du premier instrument législatif communautaire sur l'immigration familiale.C/ La directive relative au regroupement familial et les faibles espoirs de transposition en France La directive a été finalement adoptée le 22 septembre 2003 ; elle précise que les États membres peuvent autoriser l'entrée et la résidence du partenaire non marié d'un étranger, avec lequel il a une relation durable et stable dûment prouvée ou enregistrée 29 . Ce choix laissé aux États membres de faire venir les partenaires non mariés sera-t-il envisageable dans le droit français ? Comment le législateur français va t-il transposer cette directive sur cette question ?

  CE ass. 19 avril 1991 Belgacem rec. p. 152, ABRAHAM R., « Conclusion du Commissaire du gouvernement, jurisprudences du CE, 19 avril 1991, n° 107 470, M. Belgacem-n° 117 680, Mme Babas », RUDH, 1991, p. 242. REYDELLET M., LPA 8 juillet 1991., JULIEN-LAFERRIERE F., « Note de jurisprudence, CE ass., 19 avril 1991, Belgacem et Babas », AJDA, 20 juillet/ 20 août 1991, p. 551., PRETOT X., D., 1991, J., p. 399., RUIZ-FABRI H., « Étrangers, expulsion, droits de l'homme, jurisprudence administrative », RA, 1991, n° 259 264, p. 239., TURPIN D., Revue Crit. Droit International Privée, 1991, p. 677., NGUYEN VAN TUONG, « Commentaire de l'arrêt Belgacem et Babas, CE ass., 19 avril 1991, req. 107470 et 117680 », JCP, G, n° 46, 21756-21757, p. 393. , MIGNON E., « L'expulsion d'un étranger : atteinte au droit à la vie privée ou atteinte droit à la vie familiale ? », RDE, 1991, n° 92, p. 8-9. 34 Loi N° 98-349 du 11 mai 1998 relative à l'entrée et au séjour des étrangers en France et au droit d'asile.

  Voir l'article PANSIER F.-J., « Obtention d'une carte de séjour « vie privée et familiale » par le signataire d'un PACS : une réponse ministérielle restrictive », RJPF, N° 5, mai 2000, p. 10-11. 63 FOURNALÈS R., « La protection des situations personnelles et de la vie privée en droit des étrangers, prolégomènes à l'arrêt GISTI du Conseil d'État du 30 juin 2000 », JDI, 2, 2001, p. 480. 64 Circulaire du 10 décembre 1999, relative à l'application de l'article 12 bis 7 de l'ordonnance N°45-2658 du 2 novembre 1945 modifiée aux partenaires d'un pacte civil de solidarité ( PACS ), N° NORINT/D/00251/C. La circulaire a été partiellement annulée par le Conseil d'État, le 22 juillet 2002, N° 231158, GISTI, LDH, Femme de la terre.

	/48, janvier
	2001, p. 18-21.
	61 Loi du 15 novembre 1999, JO 16 novembre 1999, p. 16959., HAUSER J. « Aujourd'hui et demain le PACS »,
	RJPF, 1999 8/ 12, et 1999 9/12.

62

Loi N° 98-349 du 11 mai 1998 relative à l'entrée et au séjour des étrangers en France et au droit d'asile.

CEDH Moustaquin c/ Belgique, 18 février 1991, série A, N° 193, Berrehab c/ Pays Bas, 21 juin 1988, N°0 0010730/84, série A N° 138.

Article 8 de la Convention européenne des droits de l'homme « Toute personne a droit au respect de sa vie privée et familiale (...) ».

CE 28 avril 2000 Préfet des Alpes maritimes c / M. Maroussitch req. N° 208925 et CE 28 juillet 2000, Préfet de police c / M. Diaz Grozco req. N° 212729.

Directive 2003/86/CE du Conseil du 22 décembre 2003 relative au droit au regroupement familial, JOCE L 251/12, 3/10/2003.

Résolution sur l'harmonisation des politiques nationales en matière de regroupement familial du 1 er juin 1993 adoptée à Copenhague, non publiée.

C'est une communautarisation partielle de la matière puisque les instruments relevant de l'article 63 du traité CE doivent recueillir les voix de l'unanimité des États membres pour être adoptés.

Entrée en vigueur du 1 er mai 1999.

L'adoption du projet par la Commission date 01/12/1999, JOCE/1999/638/final.

Pris sur la base de l'article 63 paragraphe 3 du Traité instituant la Communauté européenne ( TCE ). Auparavant les questions relatives à l'immigration relevaient de la coopération intergouvernementale faisant partie du troisième pilier.

« Le conjoint du regroupant, ou, le partenaire non marié qui a une relation durable avec le regroupant, si la législation de l'État membre concerné assimile la situation des couples non mariés à celle des couples mariés ».

Chapitre II, Article 5 § 1. Cet article précise quels sont les membres de la famille du regroupant qui sont éligibles au regroupement (a) « Cet alinéa concerne le conjoint du regroupant, ou son partenaire non marié, y compris le partenaire du même sexe ».

« Cette disposition n'engendre aucune harmonisation des règles nationales relatives à la reconnaissance des couples non mariés; elle permet uniquement d'appliquer le principe d'égalité de traitement. Afin d'éviter d'éventuelsabus, les partenaires non mariés doivent être liés par une relation durable, ce qui peut être démontré au moyen de la preuve de la cohabitation ou de témoignages dignes de foi ».

Article 5 § 1 b) et c).

Article 5 §1 e).

Le Conseil d'État a interprété très restrictivement les dispositions sur l'adoption demandée par un homme ayant un partenaire de même sexe, CE 9 octobre 1996, Département de Paris, Req. N° 22766, la Cour européenne a aussi refusé l'adoption à un couple homosexuel, CEDH 26 février 2002 Fretté c/ France., POIROT-MAZERES I., « De la gay Pride ... au Palais-Royal A propos des refus d'agrément à l'adoption opposés aux homosexuels », AJDA 2002, p. 401.

La seconde proposition de directive a été adoptée le 10/10/2000, Com/2000/624/ final du 10/10/2000, bull. 10-2000/1.4.2.

 25 Cf. les différents droits comparés sur les avantages délivrés aux droits homosexuels, MÉCARY C., op. cit., p. 117 et

s. 26 Proposition modifiée de directive du Conseil relative au droit au regroupement familial, Bruxelles, le 2/05/2002, COM ( 2002) 225 final.

Article 4) 3) « Les États membres peuvent par voie législative ou réglementaire, autoriser l'entrée et le séjour au titre de la présente directive, sous réserve du respect des conditions définies au chapitre IV, du partenaire non marié ressortissant d'un pays tiers qui a avec le regroupant une relation durable dûment prouvée, ou du ressortissant de pays tiers qui est lié au regroupant par un partenariat enregistré … ».

Article 4 § 3 de la directive du 22 septembre 2003.

Loi N° 99-944 du 15 novembre 1999, article 12.

C'est une simple faculté Cf. Préambule de la directive § 10 « Il appartient aux États membres de décider s'ils souhaitaient autoriser le regroupement familial pour ( … ) les partenaires non mariés ou enregistrés ». L'avis du Parlement européen rendu le 9 avril 2003 a sur ce point émis des amendements en revendiquant le droit au regroupement familial des couples non mariés et des couples de même sexe.

Projet de loi maîtrise de l'immigration et séjour des étrangers en France adopté le 28 octobre 2003.

LEVINET M., « L'éloignement des étrangers délinquants et l'article 8 de la CEDH », RTDH, janvier N° 37, 1999, p. 89-118.


Keywords: Manuscripts, peer-review, productivity

Background -In the Internet-able era reviewers are faced with an increased number of manuscripts and decreased time to review. In order to maintain the same, if not higher level of quality in the peer-review process, a net gain in productivity is required. Our goal is to present a manuscript peer-review checklist to help reviewers achieve this secondary yet critical task in a more systematic fashion.

Methods -To this end, we have compiled, structured and processed information from nine reference standards, guidelines or directives, resulting in a 70 criterias checklist. We ensured that criterias were assessable based on the verification, validation and evaluation paradigm.

Results -

The checklist is presented in the manuscript, along with a description of a review workflow.

Findings

It is hoped that the checklist will be widely disseminated, and we are looking for feedback on validation and improvements in order to perform a quantitative study on productivity gains using this tool.

Introduction

There are two growing trends that conspire to make peer reviews an increasingly demanding task. The first is the increase in the number of reviews. It has been reported that the number of scientific journals linearly increases year after year [START_REF] Hook | Scientific Communications: History, electronic journals and impact factors[END_REF]. Journal size also increases -both by the number of articles published, and the number of pages per article [START_REF] Tenopir | Towards Electronic Journals: Realities for Scientists, Librarians, and Publishers[END_REF]. While exact growth rates are subject to debate, the net cause (assuming that higher acceptance rates are not the sole justification) is that the number of submitted manuscripts has increased, and thus so did the number of reviews.

The second issue is the decrease in review time asked by Editors. The paradigm shift caused by the World Wide Web and the advent of electronic submissions will not be discussed here, other than to state that months-long reviews are a thing of the past. In order for journals to remain competitive, authors and readers demand that articles be reviewed and published faster, in part to make information circulate faster. It is routine now for editors to ask that reviews be completed in few weeks.

At the same time, publications reporting results from studies -clinical, methodological or otherwise -are increasingly being referred to in the context of evidence-based medicine.

Thus, readers expect, and rely on, the published articles to be objective and of increasingly higher quality. Editors and reviewers alike are faced with a trade-off between decreasing review times vs. increasing article quality.

Both of these issues are very well exemplified by the current changes in editorial policy for peer-review in NeuroImage, where the net effect is a call for more reviews, to be done in less time. We expect this trend to grow and include most scientific journals; when generalized, this will complicate even further the task of reviewers, called upon by multiple editors from different publications to perform at a quicker turnaround rate.

Reviewing remains an experience-driven process, not taught nor necessarily transmitted in the same fashion as field-specific knowledge [START_REF] Benos | How to review a paper[END_REF]. It is somewhat puzzling that the manuscript peer-review process, which is often hotly debated, has not received much attention or been the subject of much formalization in the literature.

Reviewing is an important but secondary task. In order to be successful in the face of increased demand, reviewers will need a net gain in productivity. Otherwise, either the quality of the reviews will diminish, or, in order to maintain an equal quality level, it will become a primary task. These situations are to be avoided.

We hypothesize that if the review process is formalized, review quality and reviewer productivity will increase. To address this situation, we suggest a tool to improve reviewer's productivity, the manuscript peer-review checklist. Thought of as a guide, it is not meant to be a categorical tool to arrive at a deterministic assessment of the quality of a manuscript, but rather, as an aide-memoire to help reviewers in their task.

The goal of this article is to present this checklist. For the present purposes, we have chosen to limit ourselves to the domain of medical imaging, even though these issues are not solely confined to this field. It would be difficult at this point to synthesize a list of questions that could fit all scientific journals. In fact, it must be stated that this article is intended as a presentation of the checklist, and not a report on its use. The research goal is to gauge interest in the medical imaging scientific community as to the usefulness and appropriateness of the tool in the review process, before extending further to research on its efficiency.

Method Checklist elaboration

The elaboration of the checklist followed a three part process: (a) compilation of checklist items, based on numerous sources; (b) structuration of checklist elements; and (c) assessment through the paradigm of Verification, Validation and Evaluation (VVE).

Checklist compilation

The checklist has been compiled using (a) existing checklists, such as the Consolidated Imaging (6 criterias)). Additional review forms were studied from main international conferences in medical imaging. During this process we concatenated the checklists found in the literature, removed redundancy and parallelism, and ensured coherence, resulting in a set of 70 criterias.

Checklist structure

We regrouped criterias based on the distinction between form and function, with the understanding that recommendations for publication are essentially based on a combined assessment of both categories of criteria. We organized the review criterias according to the standard Introduction, Methods, Results, and Discussion (IMRAD) structure, noting that Methods includes aspects related to the study population, imaging data, and the methods themselves, and Discussion includes aspects related to the claims, innovation and impact of the study, as well as ethics.

Checklist verification, validation and evaluation

In general system methodological assessment, it is usual to differentiate the concepts of Verification, Validation, and Evaluation (VVE) [START_REF] Balci | Verification, validation and certification of modeling and simulation applications[END_REF] in the following way.

Verification is the confirmation, through the provision of objective evidence, that specified requirements have been fulfilled (ISO9000:2000). It consists in assessing that the system is built according to its specifications. Validation is the confirmation, through the provision of objective evidence, that requirements for a specific intended use have been fulfilled (ISO9000:2000). It consists in assessing that the system actually fulfils the purpose for which it was intended. Finally, Evaluation consists in assessing that the system is accepted by the end user, adds value to the daily practice, and it is performant for a specific purpose.

We have used the VVE paradigm to generate the peer-review checklist by submitting each of the 70 review criterias used for assessing the quality of the manuscript to VVE. For any one criteria, the Verification aspect consists in assessing that the criteria is clearly and nonambiguously identified (i.e., described) in the manuscript. The Validation aspect consists in assessing that the choice made for the criteria is justified (i.e., correct), according to the clinical context and hypothesis for instance. And finally, the Evaluation aspect consists in assessing that the choice made for the criteria is valuable (e.g., brings new knowledge, improves knowledge on a subject, or introduces a new relevant system or approach). In the checklist, three columns per criteria are respectively related to these VVE aspects. For some criterias, Validation and/or Evaluation aspects are not relevant and therefore not addressed.

The complete checklist is shown in Table 1. Suggestions for use are given in the following section.

Discussion

We have proposed a 70 criterias checklist to be used in the peer-review of a submitted manuscript to a medical imaging journal. Our primary goal is one of qualitative increase in the productivity and quality of result of the reviews.

The checklist should be viewed as a series of guidelines; an aide-memoire for reviewers. It is not meant as a mean of standardizing output: the latter still needs to be personalized and tailored to the individual manuscript.

When generating the checklist, we have removed redundant items and checked for consistency. It is primarily aimed at medical imaging manuscripts, and thus elements relevant for other fields have not been included; however, it can be readily tailored to other domains. The selection of checklist items is representative of our own bias; we welcome discussion and exchance from the reviewship at large.

Evaluation and dissemination

We intend this checklist to be a public, freely accessible tool. It is downloadable at the authors' websites (http://jannin.org/RCL) and we encourage its dissemination.

There has not been a formal study of the efficiency of the proposed checklist. The purpose of this manuscript is to present the tool and gather interest from the community of reviewers to, possibly, embark in such study. By doing so, the checklist itself and the review process could be improved and formalized. -0 + Data collection setting(s) and location(s) -0 + -0 + Information on participant recruitment, sampling, and allocation -0 + -0 + Description of study population, inclusion and exclusion criteria -0 + -0 + Clinical and demographic characteristics -0 + -0 + Flow of participants through each stage -0 + -0 + Final group numbers for analysis -0 + -0 + Reference standard -0 + -0 + Clinical assumptions on participants and data sets -0 + -0 + Medical imaging data Sequence and image parameters -0 + -0 + Scanner type, make, manufacturer -0 + -0 + Sources of imaging and data noise -0 + -0 + Other materials and devices -0 + -0 + Methods Input parameters to the method -0 + -0 + Units, cutoffs, parameters -0 + -0 + Formulas and algorithms -0 + -0 + -0 + Implemented hardware and software -0 + -0 + -0 + Number, training and expertise of raters -0 + -0 + -0 + Outcome measures and methods -0 + -0 + -0 + Sample size -0 + -0 + Expected result or model, considering sample size -0 + -0 + -0 + Validation criterion -0 + -0 + -0 + Validation objective -0 + -0 + -0 + Type, number and characteristics of validation data sets -0 + -0 + Sensitivity analysis to parameters -0 + -0 + -0 + Statistical test(s) -0 + -0 + -0 + RESULTS Participants inclusion/exclusions -0 + -0 + -0 + Result of statistical test(s) -0 + -0 + -0 + Cross tabulation of test results by reference results -0 + -0 + -0 + Estimates of accuracy and measures of statistical uncertainty -0 + -0 + -0 + Measures of test reproducibility, if done -0 + -0 + -0 + Ancillary analyses, including sensitivity testing -0 + -0 + -0 + DISCUSSION Claims Clinical realism -0 + -0 + -0 + Claims supported by data -0 + -0 + -0 + Possible or actual bias, discrepancies -0 + -0 + Interpretation of results given hypotheses and sources of bias -0 + -0 + -0 + Generalization of findings, alternative explanations -0 + -0 + -0 + Innovation and impact Original concepts, new technology usage -0 + -0 + -0 + Innovation: transformational, translational, incremental -0 + -0 + -0 + Scientific and/or practical value of findings and results -0 + -0 + -0 + Clinical applicability -0 + -0 + -0 + Ethics Social, safety, ethical or economic issues -0 + -0 + -0 + Ethics committee approval and informed consent for subjects -0 + -0 + Human study -in accordance with the Declaration of Helsinki -0 + -0 + Animal study -in accordance with the Guiding Principles -0 + -0 + Sources of funding and role of study sponsor(s) -0 + Contributorship, guarantorship, medical writer involvement -0 + Potential conflicts of interest -0 +

  Standards of Reporting Trials (CONSORT) (22 criterias), the Standards for Reporting of Diagnostic Accuracy (STARD) (25 criterias), the Meta-Analyses of Observational Studies (MOOSE) (35 criterias) and the Health Technology Assessment (HTA) checklist of the International Network of Agencies for Heatlh Technology Assessment (INAHTA) (17 criterias); (b) guidelines, such as the Appraisal of Guidelines Research and Evaluation (AGREE) and the International Committee of Medical Journal Editors (ICMJE); (c) validation frameworks (Jannin et al., 2006) (27 criterias); and (d) editorial policy from peerreviewed journals (e.g. NeuroImage (3 criterias), and IEEE Transactions on Medical

Acknowledgments

We thank Dr K. Friston., editor of NeuroImage, for his input in the final version of this manuscript. S.D. and P.J. acknowledge the support of the Fond pour la Recherche en Santé du Québec and the Institut National de Santé et Recherche en Médecine.

Suggestions for use

We propose a simple review workflow to perform manuscript peer-review using the checklist (see Figure 1). We also strongly suggest reviewers that they verify, validate and evaluate their own reviews once completed. Criterias proposed by Benos [START_REF] Benos | How to review a paper[END_REF] can be helpful in this regard (Table 2).

Finally, any kind of ponderation or weighting of individual checklist element has been purposefully left out of the checklist. Reviewers will either naturally or formally declare emphasis when reading and reviewing manuscript.

Finally, it will not have escaped reviewers reading this note, who are first and foremost authors of manuscript, that a good review checklist can be used conversely as a good manuscript design tool for improving the quality of your writing.

Role of the funding sources

The funding sources had no involvement in study design, collection, analysis, and interpretation of data, writing of the report and in the decision to submit the paper for publication.

Disclosures

No disclosures

Authors' contributions

• Guarantors of integrity of entire study, all authors;

• Study concepts and design, all authors;

• Literature research, S.D.;

• Methods, analysis and interpretation, all authors.;

• Manuscript preparation, S.D.; revision/review, all authors; and

• Manuscript definition of intellectual content, editing, and final version approval: all authors There were no medical writers involved in the creation of this manuscript.

REVIEWER CHECKLIST

JOURNAL


Pierre-Alain Fouque
email: pierre-alain.fouque@ens.fr

Mehdi Tibouchi
email: tibouchi.mehdi@lab.ntt.co.jp

Jean-Christophe Zapalowicz
email: jean-christophe.zapalowicz@inria.fr

Recovering Private Keys Generated With Weak PRNGs

Keywords: linear congruential generator, discrete logarithm, factoring, cryptanalysis

Suppose that the private key of discrete logarithm-based or factoring-based public-key primitive is obtained by concatenating the outputs of a linear congruential generator. How seriously is the scheme weakened as a result?

While linear congruential generators are cryptographically very weak "pseudorandom" number generators, the answer to that question is not immediately obvious, since an adversary in such a setting does not get to examine the outputs of the congruential generator directly, but can only obtain an implicit hint about them-namely the public key.

In this paper, we take a closer look at that problem, and show that, in most cases, an attack does exist to retrieve the key much faster than with a naive exhaustive search on the seed of the generator.

The problem is similar to the one considered by Bellare, Goldwasser and Micciancio regarding DSA and "pseudorandomness", and this line of work arguably has renewed relevance in view of the sensitive role that random number generation has been found to play in a number of recent noted papers, such as the one by Lenstra et al. at CRYPTO 2012.

Introduction

Recently Lenstra et al. have proposed a sanity check of public keys collected on the web [START_REF] Arjen | Public keys[END_REF] and concluded that generating secure public keys in the real world is challenging. A related study by Heninger et al. [START_REF] Heninger | Mining your Ps and Qs: Detection of widespread weak keys in network devices[END_REF] pointed in particular to the role of (pseudo)randomness generation as the chief cause for the weak keys observed in the wild. Cryptographers have to look at the security of pseudorandom generators used to generate the secret keys.

Pseudorandom generators are one of the main component of security products and their importance for security is hard to overestimate. A number of practical attacks stem from problems with randomness generators. Indeed, it is difficult to obtain randomness on computers and embedded devices, which tend to aggregate various more or less reliable sources of entropy (mouse movements, passwords, network interrupts, electronic noise) and use pseudorandom number generators to expand them into arbitrarily long, hopefully uniform-looking bit strings.

Such practical generators have been analyzed and a framework has been given by Barak and Halevi [START_REF] Barak | A model and architecture for pseudo-random generation with applications to /dev/random[END_REF] for the Linux generators, who discuss the importance of the randomness collector which maintains a state of enough entropy and an extraction function whose aims is to output random bitstring from the state, which is then expanded into an arbitrarily long pseudorandom string. Cryptographers tend to concentrate on the second aspect: they assume that a pseudorandom generator is seeded with a uniformly distributed bitstring and the goal of the generator is to stretch the seed to a longer bitstring. They define security notions and a generator is called secure if it is hard to distinguish its output from uniformly distributed bitstring given the previous output bits.

The security of the first cryptographically secure generators has been based on some number-theoretic hard problems, in the sense that the problem of distinguishing the outputs from uniform is reduced to a number-theoretic problem. In 1981, Shamir proposed one generator based on the strong RSA problem in [START_REF] Shamir | The generation of cryptographically strong pseudo-random sequences[END_REF]; Blum and Micali proposed a generator based on the discrete logarithm problem [START_REF] Blum | How to generate cryptographically strong sequences of pseudo-random bits[END_REF]; Blum, Blum and Shub proposed a generator based on the factorization problem in [START_REF] Blum | A simple unpredictable pseudorandom number generator[END_REF]; and Micali and Schnorr defined another generator based on the problem of distinguishing small e-th root modulo a RSA modulus from uniform values in [START_REF] Micali | Efficient, perfect polynomial random number generators[END_REF].

These generators are interesting from a theoretical point of view, but they are rather inefficient and in practice more efficient generators using symmetric cryptographic functions have been preferred. For instance, ISO and NIST propose generators using symmetric primitives such as hash functions and block ciphers, which are more efficient and can be modeled as random oracles, ideal ciphers, pseudorandom functions or permutations. In [START_REF] Desai | A practice-oriented treatment of pseudorandom number generators[END_REF], Desai et al. proved the security of these symmetric primitive-based generators, provided that the underlying primitives satisfy certain standard assumptions. Linear Congruential Generators. Cryptographers have also studied the security of the linear congruential generators (LCG), widely used in simulation.

These generators are efficient and have a very small memory footprint. Moreover, with suitable parameters, they can have good statistical properties such as a large period length and their output distribution is uniform. As they are also very easy to implement, they tend to be used in the standard libraries of many languages and compilers: the rand function proposed in the POSIX standard and the ones used in many C/C++ standard libraries, Java's java.util.Random, most implementations of RAND in Fortran, etc. Their efficiency and ubiquity make them attractive to implementors, especially in constrained environments, even in some security-sensitive applications.

Unfortunately, LCGs are cryptographically insecure: Boyar [START_REF] Boyar | Inferring sequences produced by pseudo-random number generators[END_REF] proved that, with a sufficiently long run of the pseudorandom sequence, one can recover the seed in polynomial time in the size of the internal state and Stern [START_REF] Stern | Secret linear congruential generators are not cryptographically secure[END_REF] proved that this is also the case even if only the most significant bits of each successive states is revealed (see also [START_REF] Boyar | Inferring sequences produced by a linear congruential generator missing low-order bits[END_REF][START_REF] Joux | Lattice reduction: A toolbox for the cryptanalyst[END_REF][START_REF] Frieze | Reconstructing truncated integer variables satisfying linear congruences[END_REF]). These attacks are based on lattice reduction, usually LLL [START_REF] Arjen | Factoring polynomials with rational coefficients[END_REF]. However, Contini and Shparlinski have proposed a careful analysis of these algorithms in [START_REF] Contini | On Stern's attack against secret truncated linear congruential generators[END_REF] and established some limits to their applicability, indicating that with properly chosen parameters, the generator might become secure.

Related Work. In any case, these attacks assume that the adversary has direct access to a certain number of outputs (although the parameters of the generator may remain unknown). As a result, using such a cryptographically weak generator in a cryptographic protocol does not automatically make the resulting protocol insecure, because an adversary against the protocol may not have access to the actual outputs of the generator. This led Bellare et al. [START_REF] Bellare | Pseudo-random" number generation within cryptographic algorithms: The DDS case[END_REF] to analyze the security of the Digital Signature Algorithm (DSA) when the random nonces used in signature generation are computed using a linear congruential generator. They showed that this does seriously break security: a few signatures are enough to recover the secret key. This started an important line of research on the security of DSA when partial information on the nonces is revealed. For instance, Smart and Howgrave-Graham [START_REF] Howgrave | Lattice attacks on digital signature schemes[END_REF] and later Nguyen and Shparlinski [START_REF] Phong | The insecurity of the digital signature algorithm with partially known nonces[END_REF] showed that the knowledge of a small number of the most significant bits of the nonces allows to efficiently recover the secret key using LLL. Bleichenbacher even established [START_REF] Bleichenbacher | On the generation of one-time keys in DL signature schemes[END_REF] that the bias on the single most significant bit of the nonce that occurs when using some version of the NIST generator can be sufficient to efficiently recover the secret key.

Our contributions. In this paper, we investigate a question similar to the one considered by Bellare et al. but in a different direction than the DSA cryptanalysis papers. We consider the problem of the security of public-key schemes based on the hardness of the discrete logarithm problem or the factoring problem when the secret keys are constructed by concatenating the outputs of a linear congruential generator. Since the attacker does not get those outputs directly, but only an implicit hint, namely the corresponding public key, recovering the secret key is not trivial even if a cryptographically weak generator such as the LCG is used. We show that this is usually enough to recover the secret key much faster than using the trivial exhaustive search on the seed of the generator.

Our attack relies on the assumption that the secret key is obtained as the concatenation of successive outputs of a linear congruential generator. We also assume as is usual in cryptography that the parameters of the LCG are public and therefore an exhaustive search on the seed allows to recover the secret key in time 2 k where k is the size of the seed. Typical parameters for the LCG are 32 bits or 64 bits internal state to allow fast implementation without using a library for large integer arithmetic. The main observation of our work is that if we split the seed of size k into two parts (A • 2 k/2 + B) where A and B are (k/2)-bit long, the linearity of the LCG makes it "almost" possible to write the secret key as a sum U + V • 2 k/2 where U (respectively V ) only depends on B (resp. A) and the parameters of the LCG. This is correct up to carries, which do occur but can be taken care of separately. As a result, we can obtain a timememory tradeoff on the search for the LCG seed when such generators are used to generate the secret key of a discrete logarithm-based scheme or to the prime factors of an RSA modulus. The discrete logarithm case is mainly a baby-step giant-step attack on the lower and upper halves of the seed, while the factoring case proceeds similarly using multipoint polynomial evaluation.

The main advantage of these attacks is that they allow key recovery from the public key alone, independently of any further information on the underlying cryptographic schemes.

Organization of the paper. The paper is organized as follows. After some preliminaries in §2, we present our attack in the discrete logarithm case in §3 and in the factoring case in §4. Finally, in §5, we give an overview of the complexity of our attacks for typical parameter sizes.

Preliminaries

We first recall the definition of the linear congruential generator and fix some notations which will be used in the following sections; then we briefly discussion multipoint evaluation of univariate polynomials, which will be used in the factoring case.

Linear congruential generator

For M an integer of size m bits, we denote by Z M the ring of integers modulo M . The internal state of a linear congruential generator evolves according to the following recurrence relation:

v i+1 = a • v i + b mod M (1)
where a and b are fixed constant in Z M (the parameters of the generator) and v 0 = s is the secret seed. The successive outputs o i of the generator are the k least (or most) significant bits v i at each iteration (for some fixed k ∈ {1, . . . , m}). Note that the recurrence equation is easily solved as:

v i = a i • s + b • (1 + a + • • • + a i-1 ) = a i • s + b i (mod M ). (2)
The following attacks rely on the assumption that a certain secret x is computed as a concatenation of successive outputs of such a linear congruential generator, with known parameters a, b and M . In other words, x can be written as:

x = o 0 + 2 k o 1 + • • • + 2 (r-1)k o r-1 (3)
for some fixed constant r. The secret x is then of size rk bits.

Multipoint evaluation of univariate polynomials

Let P (x) ∈ Z N [x],
with N an arbitrary integer, be a polynomial of degree less than d = 2 k . The multipoint evaluation problem is the task of evaluating P at d distinct points α 0 , . . . , α d-1 ∈ Z N . Using Horner's rule, it is easy to propose a solution that uses O(d 2 ) additions and multiplications in Z N but it is well-known that one can propose an algorithm with quasi-linear complexity O(d) operations in Z N using a divide-and-conquer approach [START_REF] Fiduccia | Polynomial evaluation via the division algorithm: The fast fourier transform revisited[END_REF]; a better, more involved algorithm based on the middle product of polynomials has later been proposed in some special cases by Bostan and Schost [START_REF] Bostan | Polynomial evaluation and interpolation on special sets of points[END_REF][START_REF] Bostan | On the complexities of multipoint evaluation and interpolation[END_REF]. That observation has found several applications in cryptanalysis [START_REF] Chen | Faster algorithms for approximate common divisors: Breaking fully-homomorphic-encryption challenges over the integers[END_REF][START_REF] Coron | Cryptanalysis of the RSA subgroup assumption from TCC 2005[END_REF].

A succinct description of the classical approach, based on product and remainder trees of polynomials is given in Appendix A. The

The discrete logarithm case

We now consider key generation in a public-key scheme whose security is related to the discrete logarithm problem in some cyclic group G of prime order q and generator g. Typically, for such a scheme, G, q and g are public parameters, the secret key contains a random element x ∈ Z q , and h = g x is revealed as part of the public key.

Assume that x is obtained from the outputs of a linear congruential generator of known parameters, as in Equation ( 1). The problem is to recover x from the public data faster than by an exhaustive search on the seed s.

Our approach in a nutshell is as follows. Separate the seed in its lower-order and higher-order halves: s = u + 2 k/2 • v (we can assume for simplicity's sake that k is even). Then, by Equation (1), the internal state of the generator can be written as:

v i = a i • u + 2 k/2 • a i • v + b i mod M.
Thus, the corresponding output o i can essentially be written, in turn, as the sum of a part depending only on u and another part depending only on vonly "essentially" because of possible carry bits and of possible overflows in the addition modulo M , but this can be taken care of, and we will ignore that for the moment. Then, x is itself of the form x = U + V where U is a publicly computable function of u, and V of v. In the group G, this gives h = g U • g V , or equivalently:

g U = h • g -V .
Now, in time and space O(2 k/2 ), we can find a collision between the lists of elements of G of the form g U for all 2 k/2 possible values of u on the one hand, and h • g -V for all 2 k/2 possible values of v on the other hand, and hence recover the secret x = U + V .

The real algorithm has a slightly higher complexity due to the need to take carries and overflows into account, which we work out below first when M = 2 k (the output is the full internal state) and then in the general case.

Note that since the parameters a and b are known, the constants b i can be computed publicly and are thus irrelevant to the attack. To simplify notations, we can thus assume without loss of generality that b = 0.

Remark 1. The attack discussed here is generic and can of course be carried out in any cyclic group: it applies to (subgroups of) the multiplicative group of a finite field and to elliptic curves or abelian varieties alike. In the case of an elliptic curve group, the problem is to recover a secret value x from two points P, Q such that Q = xP , and when x is obtained from a linear congruential generator as before, it is again possible to divide x into two parts U and V , the first depending on u, the second on v. We can find a collision by checking an equality of the form Q -U P = V P .

Attack for non-truncated linear congruential generators

We first work out the details of this attack for a non-truncated linear congruential generator, which satisfies that M = 2 k . The non-truncated linear congruential generator is the most efficient of the linear congruential generator in the sense that it outputs the maximal number of available bits at each iteration.

Theorem 1. Given two group elements g, h ∈ G with h = g x , where x is an (r • k)-bit exponent generated with a non-truncated linear congruential generator with public parameters and k-bit state, there exists an algorithm which retrieves the secret x in time and memory O(2 k+r 2 ).

Proof. As mentioned previously, we may assume without loss of generality that the LCG has parameters such that b = 0. By Equation (2), its successive outputs are thus of the form:

o i = v i = (a i • s) mod M = (a i • s) mod 2 k .
Now write the seed as s = u + 2 k/2 • v, with u, v of k/2 bits. We get:

o i = a i • (u + 2 k/2 • v) mod 2 k .
We can expand that expression for o i using the following elementary lemma.

Lemma 1. For all α, β, γ ∈ Z, γ = 0, there exists ε ∈ {0, 1} such that:

(α + β) mod γ = (α mod γ) + (β mod γ) -εγ.
Proof. Indeed, let L = (α+β) mod γ and R = (α mod γ)+(β mod γ). Clearly, L and R are congruent modulo γ, so they must differ by a multiple of γ. Moreover, 0 ≤ L < γ and 0 ≤ R < 2γ, hence -γ < R -L < 2γ, so R -L must be of the form ε • γ with ε ∈ {0, 1} as required.

⊓ ⊔ Thus, for all indexes i (and any choice of the two seed halves u, v), there exists ε i ∈ {0, 1} such that:

o i = (a i • u mod 2 k ) + (a i • 2 k/2 v mod 2 k ) -ε i • 2 k = (a i • u) mod 2 k + 2 k/2 (a i • v mod 2 k/2 ) -ε i • 2 k .
If u and v are the two halves of the correct seed used to generate x, summing the 2 ik o i yields, according to Equation (3):

x = U + V -Y
where:

U = r-1 i=0 2 ik • (a i u mod 2 k ) V = r-1 i=0 2 ik+k/2 • (a i v mod 2 k/2 ) Y = r-1 i=0 2 (i+1)k • ε i .
We can also decompose Y into a sum W + Z where each of W and Z consist of r/2 terms, and obtain the relation U -Z = x + W -V , or equivalently:

g U -Z = h • g W -V . (4)
We can thus recover x by finding a collision between two lists of 2 k+r 2 elements of G, namely the g U -Z (for all values of the half-seed u and all possible choices of the bits ε i in Z) on the one hand, and the h • g W -Z (for all values of the half-seed v and all possible choices of the bits ε i in W ) on the other. Using hash tables, this can be achieved in time and space O(2 k+r 2 ). More precisely, one first computes the 2 k/2 possible values U i , the 2 r/2 possible values Z j and stores i, j in a hash table under the key g Ui-Zj . This table contains 2 k+r 2 different values accessible in constant time. Then one computes the 2 k/2 possible values V s , the 2 r/2 possible values W t and tests, for each of them, whether h • g Wt-Vs is a key of the hash table. When the test succeeds, one obtains the correct values of u and v and can deduce the value x. The attack is summarized in Algorithm 1.

⊓ ⊔

Algorithm 1 Attack overview

Require: q, g, h = g x , a, b, M Ensure: x such as h = g x Compute the hash table H by storing i, j at H(g

U i -Z j ) for each (Vs, Wt) do if H(h • g W t -Vs ) exists then return x ← Ui + Vs -Zj -Wt end if end for

Attack for truncated linear congruential generators

We now consider a truncated linear congruential generator with a modulus M > 2 k of size m (with m < rk). It is typically less efficient than the non-truncated one, but may have better properties in statistical and security terms. The attack we obtain has a slightly worse complexity than in the non-truncated setting.

Theorem 2. Given two group elements g, h ∈ G with h = g x , where x is an (r • k)-bit exponent generated with a truncated linear congruential generator outputting the k most (or least) significant bits at each iteration, with public parameters and m-bit state, there exists an algorithm which retrieves the secret x in time and memory O(2 m/2 • 5 r/2 ).

Proof. The principle of the attack remains similar however the carry is in a larger set of values. As a consequence the complexity in time and in memory is increased. Indeed, starting from Equation ( 2) with b = 0, the successive outputs are now of the form:

o i = v i mod 2 k = (a i • s) mod M mod 2 k
in the case where the least significant bits are output, and:

o i = v i ≫ (m -k) = (a i • s) mod M ≫ (m -k)
in the most significant bits case. By writing s as u + 2 m/2 v, we get:

v i = a i • (u + 2 m/2 • v) mod M.
and Lemma 1 ensures that:

(a i • u) mod M + 2 m/2 (a i • v mod M ) = v i or v i + M.
Using the same lemma and the fact that o i = v i mod 2 k (LSB case), we obtain:

(a i •u mod M ) mod 2 k +(2 m/2 •a i •v mod M ) mod 2 k =            o i o i + 2 k o i + (M mod 2 k ) o i + (M mod 2 k ) + 2 k o i + (M mod 2 k ) -2 k
In the MSB case, we have (by denoting j = m -k) o i = v i ≫ j and thus:

(a i • u mod M ) ≫ j + (2 m/2 • a i • v mod M ) ≫ j =            o i o i -1 o i + (M ≫ j) o i + (M ≫ j) + 1 o i + (M ≫ j) -1
Therefore, by applying the attack as before and using Equation ( 4), we have to find a collision between two sets of 2 m/2 • 5 r/2 , the factor 2 m/2 coming from the search of U (respectively V ) and the factor 5 r/2 coming from the search of Z (respectively W ).

⊓ ⊔

The factoring case

The attacks extend to public-key schemes whose security is related to the hardness of factoring, or of the RSA problem. Denoting p and q two secret primes obtained from outputs of a linear congruential generator, and N the resulting product published as part of the public key, we would like to find p and q given N and the parameters of the generator.

The idea is again to separate the seed into a lower-order and a higher-order part, and to obtain a time-memory tradeoff compared to exhaustive search. The key ingredient is multipoint polynomial evaluation.

Basic prime generation

We first consider a prime number generation algorithm (see [START_REF] Menezes | Handbook of Applied Cryptography[END_REF]) which consists in, from a random seed, computing the required number of outputs, concatenating them and using a probabilistic primality test such as Miller-Rabin or a deterministic one such as the AKS primality test. If the test fails, one selects another random seed and restarts the algorithm: all primality tests are independent.

As before, we consider the case where the linear congruential generator is not truncated and the case where it is truncated. Theorem 3. Given a RSA modulus N with N = pq, where p is an (r • k)bit prime generated with a non-truncated linear congruential generator (resp. a truncated linear congruential generator outputting the k most or least significant bits at each iteration), with public parameters and k-bit state (resp. m-bit state), there exists an algorithm which factorizes N in time and memory O(2 k+r 2 ) (resp. O(2 m/2 • 5 r/2 )) with overwhelming probability.

Proof. For simplicity, we will treat the case of the non-truncated LCG since the use of a truncated one implies only a difference in the exhaustive search of the carry. By splitting the seed as s = u + 2 k/2 • v, we can write p as p = U + V -Y with:

U = r-1 i=0 2 ik (a i u mod 2 k ) V = r-1 i=0 2 ik (2 k/2 (a i v mod 2 k/2 )) Y = r-1 i=0 2 (i+1)k • ε i .
We can also cut Y into two r/2-bit elements W, Z. Let us denote A = U -Z and B = V -W and suppose having c(A + B) mod N = cp mod N with c an integer. Then, except the rare case where c is a multiple of q, this value is necessarily a multiple of p. Indeed cp mod pq can only have the values 0 (case where q|c), p, • • • , (q -1)p. Thus, a greater common divisor computation (GCD) with N will reveal p.

As an attacker, one does not have access to the correct value of the seed. Since u and v can take 2 k/2 distinct values, one can compute the same amount of values U and V . Moreover there are 2 r/2 possibilities for W and Z. In other words, the values A = U -Z and B = V -W are in two sets of 2 k+r 2 elements and we have to find a test in order to determine the good ones.

More precisely, one first computes the 2 k+r 2 different values B s,t by generating the values V s and W t and we consider the following polynomial of degree 2 values of the form:

s,t (A i,j + B s,t ) mod N | i = 0, • • • , 2 k/2 -1, j = 0, • • • , 2 r/2 -1 .
Finally one has to compute a test to detect the correct values A and B. It is done by computing a GCD between each value (A i,j ) and the public modulus N . Since all the values of the seed and all the values of the carry are efficiently tested, the prime p will be recovered except if P (A) is equal to 0. However this failure case is extremely rare: it requires that at least one of the d -1 integers composing the product with p is the prime q. The probability is thus equal to d-1

2 log q . The attack is summarized in Algorithm 2. ⊓ ⊔ Algorithm 2 Attack overview (case M = 2 k )
Require: N = pq, a, b, M Ensure: p such as N = pq Generate the polynomial P (X) = s,t (X + Vs -Wt) mod N Multi-evaluate P at the points Ai,j = Ui -Zj for each point Ai,j do if gcd(P (Ai,j), N ) = 1 then return gcd(P (Ai,j), N ) end if end for

Improved prime generation

Since there is no link between each probabilistic primality test in the first prime number generating algorithm, the failed tests are useless and free of cost from the point of view of the attacker. We now propose another one with a link by using a counter. PRIMEINC Method. The PRIMEINC algorithm is a prime number generating algorithm proposed by Brandt and Damgård in [START_REF] Brandt | On generation of probable primes by incremental search[END_REF] which basically picks a random number and increases it until a prime is found. In other words, if p is not a prime (but odd), then p = p + 2 and repeat. According to the prime number theorem, we expect to find a prime number after log p trials on average. Proof. In our attack, we now search the correct value of p such as p = A + B + 2ǫ with ǫ ∈ {0, • • • , log p} (see Remark 2 for the size of the set). Thus, after the multi-evaluation, our algorithm should have computed a set covering the entire space of search as follows:

s,t (A i,j + B s,t + 2γ) mod N | i ≤ 2 k/2 -1, j ≤ 2 r/2 -1, γ ≤ log p .
An efficient way to compute the search of the correct value of γ (i.e. γ = ǫ) consists in applying the same trick as before, i.e. writing γ as γ = γ M SB + γ LSB by splitting the bits into two parts. In other words, in the first part of the algorithm, one computes the different values B s,t and the √ log p values of γ LSB . In the second part, one focus on the different values A i,j and the √ log p values of γ M SB . Thus, after the multievaluation, the resulted set corresponds to 2 With overwhelming probability, the value containing p does not contain q too and the test using the greatest common divisor will reveal p.

The modification due to the PRIMEINC method thus increases the complexity in time and in memory by a factor of √ log p, which disappears in the O since

√ log p = O( √ rk) = O r+k 2 .
⊓ ⊔ Remark 2. Brandt and Damgård prove in [START_REF] Brandt | On generation of probable primes by incremental search[END_REF] that the failure is about equal to e -2ℓ when applying ℓ • log p iterations of the PRIMEINC algorithm. In the proof, we put ℓ = 1, leading to a success rate of 86%.

Complexity estimates for concrete parameter sizes

Table 1 below presents the time complexity of our attack in the discrete logarithm case for typical parameter LCG sizes, as found in implementation of the random functions of common compilers and standard libraries, namely a modulus equal to either 2 32 or 2 64 (so that modular addition and multiplication can be implemented as simple operations on standard size registers), and an output size equal to either the full modulus size or half of it (corresponding to the top or bottom half of the state). The complexities are to be compared with that of the trivial attack: exhaustive search on seed.

Remark 3. Note that the differences of complexity between a linear congruential generator which outputs the least significant bits or the most significant bits is due to the fact that there are only three possibilities for the value of (a i • u mod M ) mod 2 k + (2 m/2 • a i • v mod M ) mod 2 k . Indeed, taking M = 2 32 or M = 2 64 yields M mod 2 k = 0.

Remark 4. In a few cases, for 16-bit output size, the complexity is in fact worse than the exhaustive search on the seed. This happens in the truncated case only, when r (the number of LCG outputs used to construct the secret) is particularly large, namely when 5 r/2 (MSB case), resp. 3 r/2 (LSB case), is greater than 2 m/2 .

Remark 5. In the factoring case, the complexities are larger by a logarithmic factor, from the use of quasilinear multipoint polynomial evaluation.

  complexity T (d) of the recursive algorithm satisfies T (d) = 2T (d/2)+O(M (d)), where M (i) denotes the arithmetic complexity to compute the product of two polynomials of degree i in Z N [x], and therefore T (d) = O(M (d) log d).

  B s,t ) mod N Then one computes the 2 k+r 2possible values A i,j by generating the values U i and Z j and proceeds a multi-evaluation of the polynomial P at the points A i,j . The result is a set of 2 k+r 2

Corollary 1 . 2 k+r 2 )

 122 Considering the two cases of Theorem 3 coupled with the PRIMEINC algorithm, there exists an algorithm which factorizes N in time and memory O((resp. O(2 m/2 • 5 r/2 )) with overwhelming probability.

k+r 2 √

 2 log p values of the form (case M = 2 k ):s,t,γ (A i,j + B s,t + 2(γ M SB + γ LSB )) mod N.

Conclusion

In this paper, we present new key-recovery attacks on discrete logarithm and factoring-based public-key schemes whose private keys are generated by concatenating the outputs of a linear congruential generator. Even though the LCG itself is known to be a cryptographically weak pseudorandom generator, it is not a priori obvious that its use would make key generation insecure, as its outputs are never revealed in clear to an adversary. It turns out, however, that the implicit hint about those outputs provided by the public key is enough to recover the private key significantly faster than with an exhaustive search on the seed. It is hoped that this attack can be generalized to other, less naive pseudorandom generators in further work. Moreover, even in the case of the LCG, it would be interesting to extend it to different scenarios, such as the generation of randomness used in padding functions for encryption and signatures, or to settings where LCG parameters are unknown to the attacker.

A Multipoint evaluation of univariate polynomials

Here is a succinct description of the classical approach, based on product and remainder trees of polynomials.

ℓ=d/2 (xα ℓ ) and let us define R 0 = P mod P 0 and R 1 = P mod P 1 . have R 0 (α i ) = P (α i ) for all i ∈ {0, . . . , d/2 -1} and R 1 (α i ) = P (α i ) for all i ∈ {d/2, . . . , d -1} and this gives immediately a recursive algorithm (i.e. compute P 0 , P 1 , R 0 , R 1 and reduce the problem to the multipoint evaluation of R 0 and R 1 of degree

for i ∈ {0, . . . , k} and 0 ≤ j < 2 k-i . We have P 0,j = A j and P i+1,j = P i,2j P i,2j+1 so for i ∈ {0, . . . , k} we can compute recursively all polynomials P i,j and 0