627 results

  • Deterministic equation solving over finite fields

    • March 25, 2011

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Speaker : Christiaan van de Woestijne - Montanuniversität Leoben

    It is a curious fact that most efficient algorithms for solving algebraic equations over finite fields are probabilistic. In this talk, I will give an overview over deterministic techniques that are applicable. The case of constructing rational points on elliptic curves is especially relevant for cryptographic applications. I will give a detailed exposition of my algorithm for this purpose and[…]
  • Un algorithme de résolution des équations quadratiques

    • March 18, 2011

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Speaker : Pierre Castel - Université de Caen

    Soit Q une forme quadratique de dimension 5. Le but de cet algorithme est de trouver un vecteur isotrope pour la forme Q. Des algorithmes existent déjà pour résoudre ce type d'équation, cependant la première étape de ces algorithmes consiste à factoriser le déterminant de Q ce qui nuit considérablement à leur efficacité. Dans cet exposé, je proposerai un nouvel algorithme ne factorisant pas le[…]
  • Privacy, incentives, and truthfulness

    • March 04, 2011

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Speaker : David Xiao - LRI

    Imagine the government is taking a census, and you as an individual are worried that by participating, private information about you (such as your address, age, ethnicity, etc.) may eventually be revealed when the government publishes the census data. How can the government assure you that by using an appropriate release mechanism that "sanitizes" census data, no individual's privacy will be[…]
  • Un algorithme à la Pollard pour le problème du sac à dos

    • February 04, 2011

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Speaker : Gaetan Bisson - LORIA

    Soit S une suite d'éléments d'un groupe fini G noté multiplicativement ; le problème du sac à dos consiste à trouver une sous-suite de S dont le produit vaut un élément donné z de G. Des méthodes très efficaces pour le résoudre existent quand G=Z/nZ mais elles nous abandonnent lorsque l'on change de groupe : on peut en effet prouver qu'aucun algorithme générique (c'est-à-dire, en un sens, qui s[…]
  • Calculer dans le groupe de Picard d'une courbe projective sur un corps

    • January 14, 2011

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Speaker : Peter Bruin - Orsay

    Kamal Khuri-Makdisi a développé un cadre algorithmique pour calculer de façon efficace dans le groupe de Picard d'une courbe projective lisse sur un corps $k$. C'est une intéressante approche, par exemple, pour les courbes modulaires, où une représentation convenable de la courbe peut se calculer à partir d'un espace de formes modulaires. Le but de cet exposé est de montrer que ce cadre[…]
  • History-Free Aggregate Message Authentication Codes

    • December 10, 2010

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Speaker : Dominique Schroeder - TU Darmstadt

    Aggregate message authentication codes, as introduced by Katz and Lindell (CT-RSA 2008), combine several MACs into a single value, which has roughly the same size as an ordinary MAC. These schemes reduce the communication overhead significantly and are therefore a promising approach to achieve authenticated communication in mobile ad-hoc networks, where communication is prohibitively expensive.[…]