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 ont été perçus par le Laboratoire comme le soutien des instances du CNRS au développement de ce groupe. Le responsable du GRECC devant succéder à Claude Puech comme professeur détaché à l'ENS, à partir d'octobre 1993, la pérennité du groupe paraît maintenant établie.
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.