Score:4

UF-naCMA not implies UF-CMA

hm flag

I am trying to show that UF-naCMA doesn't imply UF-CMA. UF-naCMA is actually defined as UF-CMA but the adversary should send $q \in poly$ messages $m_i$ chosen non-adaptively (i.e. all at the same time) before obtaining the public key. Then, as in UF-CMA in order to win he has to forge a valid $(m^*,\sigma^*)$ with $m^*$ fresh.
I can see the implication doesn't hold intuitively but can't figure out an efficient attack to show it.
I thougth of showing textbook RSA is UF-naCMA would solve my problem but don't know how.

Score:0
ru flag

A good place to start is likely to be Bellare et al's 1998 paper Relations Among Notions of Security for Public-Key Encryption Schemes. In particular, their theorem 3.7 shows that NM-CCA1 does not imply NM-CCA2. Their proof uses a NM-CCA1 safe scheme to construct a NM-CCA1 safe/NM-CCA2 vulnerable scheme (see page 18). UF-naCMA/UF-CMA and NM-CCA1/NMA-CCA2 are sort of the same problems but couched in the languages of signatures versus public key encryption.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.