The McEliece / Niederreiter Signature Scheme

The new McEliece-based signature scheme CFS

Yes, it is possible to build a digital signature scheme based on McEliece (or Niederreiter) cryptosystem. The problem open for more than 20 years have been recently solved by Matthieu Finiasz, Nicolas Sendrier and Nicolas Courtois. It gives the shortest signatures ever known: 87 bits and for the binary workfactor of 2^85, signing time of 30 s and verification time of about 1 s.
The shortest signature scheme previously known was Quartz with 128 bits.

How to achieve a McEliece-based Digital Signature Scheme: Here is the McEliece signature scheme paper published at Asiacrypt 2001, LNCS 2248, Springer, pp. 157-174. An early version was published as Inria rapport de recherche 4118, February 2001.

And here are the early slides presented at the rump session of Crypto 2001.

And here is a report on FPGA implementation of it.

Interesting links: multivariate cryptanalysis:
Algebraic attacks on AES, Rijndael, Serpent, Camellia, etc.., the XSL attack on block ciphers
Algebraic attacks (or XL attacks) applied to stream ciphers
Interesting links: multivariate cryptography:
The McEliece_based short signature scheme CFS
The HFE cryptosystem home page
The Minrank Zero-knowledge identification scheme
Quartz /Flash /Sflash signature schemes
Nicolas Courtois research page
TTM cryptosystem, GPT cryptosystem