Is there an authenticated encryption scheme where the recipient can attribute the message to a single sender? With a standard authenticated encryption scheme (or MAC), Alice and Bob share a symmetric key.  When Alice sends something to Bob, Bob can check that it is authentic.  At that point, Bob can deduce that the message must have been sent by someone who knows the key, i.e., it must have been sent by Alice or Bob.

How can Bob verify that the message was sent by Alice?  (not by Alice or Bob)

In particular, standard authenticated encryption only proves that the message come from someone in a trusted group (the group of people who know the symmetric key).  I'd like a scheme where the recipient can verify which individual sent it.

In other words, I'd like to get all the current guarantees of AE, plus ability to authenticate which entity sent the message (only one particular entity must have been able to authenticate the document, unless their key is compromised).  It's OK if it needs to use public-key technology.  Ideally, such a mode would be single pass (like OCB), but hopefully not patent encumbered or GPL tainted (LGPL or weaker is ok).  Getting authenticated associated data would be a bonus.

Or maybe I just need to encrypt (using a plain randomized mode, provides confidentiality only) then sign the ciphertext+associated data (which provides integrity, authentication and knowledge of the sender)?
To get non-repudiation, you must have a "proof" which can be used against the signer himself. Symmetric cryptography, by itself, will not help you there, because a cryptographic proof can only come from some "secret" which is under exclusive control of the signer, and the symmetric model assumes that there is a shared secret between two entities. The concept of non-repudiation makes sense if the signer wants to default on his signature, and the receiver of the signature sues him and wants to convince a third party (the judge) that the signature is genuine and binding. This is a scenario where both parties are adversaries with each other. In that context, there is very little provability that can be extracted from a secret value that they both know.

There are systems which provide non-repudiation and still use symmetric cryptography. That's what happens (happened ?) in payment smart cards: the cards "signs" the transaction by computing a MAC over it, with symmetric cryptography; the MAC key is user-specific, but known to both the card and the bank. Such transactions are binding in a legal way (so there is "non-repudiation") because the Law says so; but the system works in practice because it is not easy to circumvent. In particular, the bank is assumed to be honest and not to frame its customers; this assumption is not free, because it comes at the price of very heavy controls and auditing systems on the bank side.

One cornerstone of non-repudiation, as existing laws on digital signatures put it, is the notion of exclusive control. What the signer uses to sign must be proven to be usable by the signer only. In the banking smart card example, this is obtained through several mechanisms, including the inherent robustness of the card, the PIN code handling, and the expensive verifications and safeguards which are performed on the bank side of the transaction. These verifications can be made cheaper if the whole system uses asymmetric cryptography, because maintaining exclusive control of an asymmetric private key is easier than doing the same with a shared secret. For instance, in an asymmetric system, you can arrange for the private key never to leave the device on which it was generated, which makes device initialization easier, especially when already deployed in the field.

(Note that "easier" does not mean "easy".)

Anyway, non-repudiation is about people or at least legal entities; cryptography sees keys. Binding entities to key control is a complex business; one way to do it is PKI. People involved in PKI know that PKI is 5% asymmetric cryptography, 95% procedures. Getting the crypto right is the easy part. Asymmetric cryptography is not sufficient to achieve non-repudiation; and it is not strictly necessary either, but, in the current legal context, you will find that obtaining non-repudiation is even harder if your toolbox does not include asymmetric cryptography.



To say it differently, you can get non-repudiation out of an AE mode, under the same conditions that you would get non-repudiation out of a MAC. This is doable, in fact it has been done, but in a heavyweight framework of procedures, laws, controls, and a lot of money thrown at it. Banks did it with symmetric cryptography because when such systems began to be deployed (in the late 1980s in France), cards which could do asymmetric cryptography were very expensive.