What is meant with naïve sign & encrypt?

The author seems to use "simple" and "naïve" interchangeably. Yes it seems he is referring to the act of signing (with the senders private key) and encrypting (with the receivers public key) the plaintext before transmission.

He views this as naïve because of the ability for a third party to forward a pre-existing signed message written by the sender to the receiver and the receiver assuming it safe to trust this.

Imagine a situation where Bob and Alice are attempting to communicate securely. Chuck is an untrusted third party known to both of them.

• Chuck sends Bob a series of questions for which he expects Bob to reply with fairly generic responses. For example Chuck asks "Did you read Dons paper?" and Bob sends back "Yes" - signed and encrypted.
• Alice sends Bob a message saying "Can I trust Chuck". Chuck knows Alice is going to do this.
• Chuck decrypts the signed "Yes" message from before and re encrypts it with Alice's public key. He then sends it to her before Bob can reply.
• Alice receives a reply to her question saying "Yes". It is signed by Bob and was sent encrypted with her public key so she trusts it.

You should read the sign and encrypt scheme in the context of people in cryptography and security industry determining the correct order for combining signing and encryption into authenticated encryption to allow you to send a signed secret message.

The naive sign and encrypt is any cryptographic scheme where the message is signed by the author's private key and then encrypted to the recipient's public key in the simplest, most obvious way:

message = encrypt(recipient public key, sign(author private key, message))

This simple scheme has a number of vulnerabilities, as described in the paper.

The other naive orders: "encrypt then sign" also has a number of vulnerabilities. In the past, cryptography API used to expose signing and encryption primitives, but not authenticated encryption primitive, so protocol designers and application programmers have always had to reinvent their own combining mechanism, which usually boils down to either one of the two naive ordering and the way protocol designers and application programmers combine these primitives often led to unexpected vulnerabilities.

The non-naive sign and encrypt would then be any authenticated encryption method that combines traditional signing and encryption primitives with additional operations that interlinks the signing and encryption operations, to avoid the vulnerabilities of the naive sign and encrypt. This is as opposed to true authenticated encryption that are designed from the ground up to satisfy the design criteria of authenticated encryption.

This approach of building authenticated encryption from traditional signing and encryption is tempting because if it is done correctly, it allows you to combine any signing algorithms with any encryption algorithms, and it may make analysis easier as you start with well known, battle tested primitives rather than designing totally new ciphers. This approach also has precedents, with high level operations like PBKDF and HMAC being built based on existing hashing primitives.