Does a cipher exist with the following properties? The key can unlock the ciphertext in polytime (measured in length of key + cipher).
a. Given the key + ciphertext as input, if you cannot unlock it in some fixed number of steps (relative to input size (key + cipher)) you reject.

b. No one can break your cipher in under this ^ number of steps without a valid key (not the average case--worse case)
The length of the ciphertext is no more than polynomially longer than the key.
Could you be looking for a password hashing KDF function with a secret parameter (a.k.a. pepper)?

With the correct password, the verification succeeds in a flash; without it, you can neither find the password, nor the keys derived from it. 

Also, since it's not data/message encryption, the input and output are "short".

Of course, what appears to meet the description could still fail to provide the functionality that you want, so you have to rethink from the start to determine what security service(s) you want. 

E.g.


confidentiality, 
integrity protection, 
authenticity guarantee, 
non-repudiation, 
recipient exclusion, 
proof-of-work.