A weaker version of NCE introduced by AC:HazPatWar15. My attempt at understanding it, dated [[12023-05-30]]: > The more I try to understand this notion the more the writeup pisses me off. In the intro, AC:HazPatWar15 write: "while in NCER a fake ciphertext can be efficiently decrypted to any plaintext (by producing a matching secret key), in tweaked NCER a fake ciphertext can only be efficiently decrypted to a concrete predetermined plaintext." While an intuitive enough statement, I can't for the life of me see how this follows from their actual definition. The entire definition hinges on how the $m'$ is chosen, yet their definition just states "for some $m' \in Mquot;. For some? For one? For any? And then in the security experiment, $m'$ is not chosen, nor drawn, nor is the notion relative to $m'$: it just magically appears. I am honestly tempted to banish the entire notion from this SoK. > Ok, time for an honest attempt to understand what's going on here: So, the fake ciphertext is generated by a fake encryption algorithm that takes the public and private key and a message $m$ and outputs some $c$. Presumably, then, $m$ is the "concrete predetermined plaintext" which is the only one it can be *efficiently* decrypted to (by running the normal decryption algorithm with the real private key). Then the *inefficient* opening algorithm is given an alternative message $m'$, and asked to produce an alternative private key such that running the normal decryption algorithm on $c$ with the alternative private key produces $m'$. (One thing I didn't realize earlier is that since the opening is inefficient, we don't have to give it the original $m$ or the private key---it can just crack the ciphertext itself! Then it becomes in a way similar to our $m_0 \rightarrow m_1$ key transform for the MI OTP.) If I understand this correctly, that means that the missing quantification really is "for any". > So, then it sounds like tweaked NCE can be captured by our NCE notion by saying that Sim is allowed to be inefficient when sender-or-receiver opening---but only when running opening subroutines. But! If the simulator is stateful, then this reduces to simply saying that the simulator is allowed to be inefficient in general, as it can then just run the opening subroutines by itself to "access" unbounded power, and store the results in its state. So for stateful simulators then, tweaked NCE becomes just NCE with unbounded simulators, which (as pointed out by Martijn) is trivially implied by NCE (unlike HazPatWar's tNCE notion...? They say they couldn't show it, but isn't it still just a strictly stronger simulator?). So, as weaker simulators yield stronger notions, our new "stateful unbounded simulator NCE" notion would be weaker than both NCE and tNCE. > A question begs itself: would "unbounded stateful simulator NCE" still be a strong enough security notion to imply ISO, like HazPatWar showed tNCE does (while stating that it *doesn't* seem to imply SSO)? Well, there is an easy, concrete reduction from NCE to ISO (with a factor $2$ loss, plus a resampling term as usual), and looking at the overheads, the runtime of the simulator does not affect the reduction at all (the reduction only ever calls the adversary and the samplers). So the answer seems to be yes. It could be argued then that this notion is just as meaningful as tNCE, if not more so. > As for the NCE $\rightarrow$ SSO implication, a quick glance at (thm:nce-sso) reveals that if $\text{Sim}_{\text{NCE}}$ is inefficient, then $\text{Sim}_{\text{SSO}}$ will also end up inefficient, begging the question what *this* notion would be. Has it shown up in the literature? (Once again, looking at (thm:sso-iso) it seems it would imply ISO at least.) > In conclusion, if we're going to include this notion, I agree with Martijn that we should let it simply be "NCE with unbounded simulators", making both presentation and implications cleaner, and letting HazPatWar's notion be a special case (for a fixed choice of $\text{Sim}$). This would also highlight the fact that the notion only makes sense in an asymptotic setting; thus, how/if/where we choose to tackle this notion depends on how we end up tackling asymptotics in general.