Authenticated encryption with Signatures

Question

I've given a CPA secure private key encryption scheme (wich gets to a CCA secure scheme or better to an authenticated encryption scheme, when i combine it with a given MAC) and a unforgeable public key signature scheme. I want to combine both to get an authenticated encryption scheme.

My approach was to first sign the message and then encrypt(+MAC) the message with the signature. I think this should work.

But is there any possibility to combine the CPA secure private key encryption scheme with the public key signature scheme and get an authenticated encryption scheme, without using the MAC to ensure authenticity and integrity?

Mac AND Signatures seems like doing the same thing twice since encryption+mac leads to an authenticated encryption scheme. But i have to use Signatures in my scheme.

Answer 1

The ​ ​ nonce || counter ​ ​ version of CTR mode
satisfies the first two of the following conditions.


If

the symmetric encryption scheme is such that different ciphertexts
with the same nonce will decrypt to different plaintexts
and
the symmetric encryption scheme is secure against a single chosen ciphertext
whose nonce was not used for any of the challenge ciphertexts
and
the signature scheme is strongly unforgeable
and
the lengths of encodings of [message,signature] pairs don't reveal
any more about the messages than the lengths of the messages

then sign-then-encrypt will work for a single pair of users, but won't work with
signature verification keys from parties that aren't supposed to know the plaintexts.


I suspect that should generalize to arbitrary stream ciphers.