  We propose the new rank-metric code-based cryptosystem LIGA which is based on
the hardness of list decoding and interleaved decoding of Gabidulin codes. LIGA
is an improved variant of the Faure-Loidreau (FL) system, which was broken in a
structural attack by Gaborit, Otmani, and Tal\'e Kalachi (GOT, 2018). We keep
the FL encryption and decryption algorithms, but modify the insecure key
generation algorithm. Our crucial observation is that the GOT attack is
equivalent to decoding an interleaved Gabidulin code. The new key generation
algorithm constructs public keys for which all polynomial-time interleaved
decoders fail---hence LIGA resists the GOT attack. We also prove that the
public-key encryption version of LIGA is IND-CPA secure in the standard model
and the KEM version is IND-CCA2 secure in the random oracle model, both under
hardness assumptions of formally defined problems related to list decoding and
interleaved decoding of Gabidulin codes. We propose and analyze various
exponential-time attacks on these problems, calculate their work factors, and
compare the resulting parameters to NIST proposals. The strengths of LIGA are
short ciphertext sizes and (relatively) small key sizes. Further, LIGA
guarantees correct decryption and has no decryption failure rate. It is not
based on hiding the structure of a code. Since there are efficient and
constant-time algorithms for encoding and decoding Gabidulin codes, timing
attacks on the encryption and decryption algorithms can be easily prevented.
