Verifying signature of plaintext using encrypted message only I'm looking for an algorithm which allows verifying a signature of a plaintext message but while only having the encrypted message.

The requirement is for Alice to send Bob a plaintext message (M) which is signed (S) by central authority (CA), the message should be encrypted (E) to Bob.

Anyone should be able to verify (V) that each of the encrypted messages (E) matches its signature (S).

CA = Central authority signing plaintext messages

M = Plaintext message

S = Signature of M by CA

E = Encryption of M

V = Function validating S against E. V(E,S) is in {true,false}
What you want is a "signature-friendly" encryption scheme, where one can verify a signature on an encrypted message. We can define it as follows:


KeyGen: generate keys $(\mathsf{pk},\mathsf{sk})$
Encrypt: given $\mathsf{pk}$, a message $m$, and a signature $s$, output a ciphertext $c$
Decrypt: given $\mathsf{sk}$, and a ciphertext $c$, output a plaintext $m$
Verify: given $\mathsf{pk}$, a ciphertext $c$, and a signature $s$, output a bit $b$


With the following (informal) guarantees: (KeyGen,Encrypt,Decrypt) is one-way (as pointed out by SEJPM in the comments to the question, the scheme cannot be IND-CPA secure), encryption/decryption work correctly, and Verify($\mathsf{pk},c,s$) outputs 1 if and only if Check(Decrypt($c,\mathsf{sk}$),$s)=1$, where Check is the signature verification algorithm.

We can build such an encryption scheme in a natural way, starting from any encryption scheme, any signature scheme, and a non-interactive zero-knowledge (NIZK) proof system. A NIZK proof system for a language $L$ works as follows:


Setup: generate a common reference string crs
Prove: given a word $x$ and a witness $w$ for $x\in L$ (and the crs), output a proof $\pi$ of $x\in L$
Verify: given a word $x$ and a proof $\pi$ (and the crs), output a bit


with the following guarantees: if the prover is honest (and $x\in L$), Verify outputs 1, if $x\notin L$, no prover can construct a proof $\pi$ accepted by Verify, and the proof leaks no information about $w$ (slightly more formally, the proof can be simulated without $w$).

Let $E$ denote some arbitrary encryption scheme, and $S$ denote some arbitrary signature scheme. Consider a NIZK proof system for the language $L$ of triples $(\mathsf{pk},c,s)$ such that $c$ is an encryption with $\mathsf{pk}$ (under $E$) of a message $m$ satisfying Check$(m,s)=1$ (where Check is the signature verification algorithm of $S$). The witness for $(\mathsf{pk},c,s)\in L$ is the pair $(m,r)$ such that $c=$Encrypt$(\mathsf{pk},m;r)$ and Check$(m,s)=1$.


KeyGen: generates keys $(\mathsf{pk},\mathsf{sk})$ for $E$, and a common reference string crs for the NIZK proof system. The public key is $(\mathsf{pk},$crs$)$ an the secret key is $\mathsf{sk}$.
Encrypt: given $(\mathsf{pk}$,crs$)$, a message $m$, and a signature $s$, check that Check$(m,s)=1$; output $\bot$ if this is not the case. Else, compute an encryption $c$ of $m$ under $E$ with $\mathsf{pk}$ (with a random coin $r$), and a proof $\pi$ of $(\mathsf{pk},c,s)\in L$, using witness $(m,r)$. Output the ciphertext $(c,\pi)$.
Decrypt: given a ciphertext $(c,\pi)$ and $\mathsf{sk}$, output the decryption of $c$ under $E$ with $\mathsf{sk}$.
Verify: given the public key $(\mathsf{pk}$,crs$)$, a ciphertext $(c,\pi)$, and a signature $s$, output NIZK.Verify(crs,$(\mathsf{pk},c,s), \pi$).


The security properties of the above scheme follow immediately from those of $E$ and from the zero-knowledge property of the NIZK proof system, and the signature verification property follows from the soundness of the NIZK proof system.

The above scheme is a somewhat generic template; to get an efficient construction, one must carefully choose the underlying primitives, with proof-friendly encryption scheme and signature scheme. To obtain better efficiency, it would probably be wise to use an interactive zero-knowledge proof, and to make it non-interactive in the random oracle model using the Fiat-Shamir transform. It requires some work, but it should be feasible to make this quite efficient with appropriate choice of the underlying primitives.