In case you receive an error message about missing key replace the above key with the one provided in your error message. At this stage we should be able to install spotify as per usual using apt-get command as shown below:
# apt-get install spotify-client
Once the installation is finished run spotify from terminal to catch any possible error:
Most likely your spotify client will complain about missing libgcrypt.so.11 shared library.
spotify: error while loading shared libraries: libgcrypt.so.11: cannot open shared object file: No such file or directory
I that case you need download to libgcrypt11_1.5.3-5_amd64.deb or similar version package from debian repository:
$ wget http://ftp.acc.umu.se/mirror/cdimage/snapshot/Debian/pool/main/libg/libgcrypt11/libgcrypt11_1.5.3-5_amd64.deb
# dpkg -i libgcrypt11_1.5.3-5_amd64.deb
Selecting previously unselected package libgcrypt11:amd64.
(Reading database ... 172946 files and directories currently installed.)
Preparing to unpack libgcrypt11_1.5.3-5_amd64.deb ...
Unpacking libgcrypt11:amd64 (1.5.3-5) ...
Setting up libgcrypt11:amd64 (1.5.3-5) ...
Processing triggers for libc-bin (2.21-0ubuntu5) ...