Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

In cryptography, two important measures of a cipher's security are its resistance to nCPA (non-adaptive chosen plaintext) and CCA (chosen ciphertext) attacks. CCA attacks are strictly more powerful than nCPA attacks, and so it is desirable to show that any adversary utilizing a CCA attack has a small advantage, that is a low probability of successfully extracting information from a ciphertext. It is well known that the total variation distance of a random permutation directly correlates to its resistance to nCPA attacks. We show that separation distance plays a similar role in measuring a random permutation's resistance to CCA attacks. We use this result to find a tight bound on the number of rounds required for the swap-or-not shuffle on n cards to have strong resistance to CCA attacks with fewer than square root of n queries.