With full password authentication, you need to enter the full password every time.
With partial password authentication, you're asked for some subset of the password each time, and which characters you need is different for each attempt.
The main security benefit supposedly is that it guards against people who see you enter the password. With full passwords, once it's been seen once, they can login whenever they want. With partial passwords, seeing it once doesn't get them in unless, the exact same characters are requested again.
Just for the sake of discussion, I'll call the one who sees you the "observer" and the event where they see you enter a correct partial password once an "observation".
Observer doesn't need to be a person. Key-loggers can do the job too.
The paper looks at an attack where an attacker gets one chance to login and can only know characters that have been observed, and how the probability of success is related to the number of observations. Actually that probability increases very fast, which suggests partial passwords aren't adding all that much security.
But of course real attackers are a lot smarter than that. They may only need one observation for a brute force attack to be viable. There's various different ways of making passwords, like Diceware, but generally the characters are related, because that makes them easy for us to remember. It also means that knowing one character helps figure out the others. At the very least an attacker can apply a dictionary to cut down the password search space by a lot. That's also assuming they need the full password, which they don't, they only need some few characters when they try to login, and some of those they may already know.
With full passwords, one observation brings the guessing entropy down to 0. With partial passwords, it wouldn't destroy all the guessing entropy, but I think the drop would be large enough to push most passwords into brute forcing range, so not much improvement there over full passwords.
Attackers can also guess the characters in an authentication challenge. Those few characters have a lot less guessing entropy than the full password, so there is a weak point there. If they get it right, they will be authenticated once. It also reveals some characters like an observation, and those known characters can be used in other attacks.
As for database compromises and offline cracking, partial passwords are a little worse. Once an attacker has one observation, either created from brute forcing or actually observed, they can figure out the rest of the characters. They can have one guessed character and the rest known characters, and try the values for the guessed character until they get it. The whole password is revealed in linear time. At least, that's what would happen with a simple implementation using Shamir's secret sharing and some hashing, perhaps other methods can mitigate these problems.
Some banks are already using this, so it seems partial passwords are more secure in some way, or maybe it's just security theater. I'm skeptical that partial passwords offer much security improvement, but I haven't done much statistics to see how much protection it could offer. Have I missed something here? Are partial passwords any significantly more secure than full passwords? Or perhaps less secure?
I intended originally to compare the guessing attacks to the Hangman game, but it's different enough that I'd be giving the wrong idea, so I cut that out. Still interesting to think about it that way though, Hangman with passwords.