Et si PCV était difficile ?
Ajtai a démontré en 1997 que PCV est NP-dur.
Or si l’on suppose que les problèmes de réseaux sont difficiles, on peut construire des systèmes à clef publique, parfois prouvés sûrs !
C’est la cryptographie à base de réseaux.