Créé en 1988, le Groupe de Recherche en Complexité et Cryptographie (GRECC) a pour objet de contribuer au développement en France de ces deux thèmes d'étude qui se trouvent à l'interface des mathématiques et de l'informatique. Abrité depuis l'origine par le département de mathématiques et informatique de l'École Normale Supérieure (DMI), il a été formellement intégré au LIENS en janvier 1992. Le recrutement d'un CR1 (Claude Crépeau) et le détachement comme DR du responsable du GRECC, en attendant sa nomination sur un poste ENS, ont été perçus par le Laboratoire comme le soutien des instances du CNRS au développement de ce groupe. La pérennité du GRECC paraît maintenant établie mais le départ prochain de Claude Crépeau pose un problème d'encadrement que ne résout pas l'arrivée de Philippe Hoogvorst en provenance d'en autre thème du LIENS, puisque ce dernier effectue une conversion thématique. Le groupe espère donc vivement pouvoir bénéficier dans les années qui viennent d'un recrutement au titre du CNRS.
Le groupe essaie de développer tout à la fois les aspects théoriques et pratiques de la Complexité algorithmique, ce qui l'amène à couvrir un domaine d'étude très <<vertical>> puisqu'il va de la théorie abstraite de la complexité et de la théorie algorithmique des nombres, à l'implantation d'algorithmes cryptographiques sur ordinateur ou sur carte à mémoire. Ce domaine d'étude se trouve assez bien décrit par la liste des grands congrès internationaux auxquels les membres du groupe participent en priorité