Provable Security of Submissions to the CAESAR Cryptographic Competition
The aim of this thesis was to prove some submissions to the CAESAR competition secure in the framework of provable security.
This thesis was done by Robin Ankele from Dez 2014  May 2015 during his stay at the COSIC group at the KU Leuven, Belgium. He was advised by Dr. Bart Mennink, Dr. Elena Andreeva.
Abstract
Modern cryptography is build upon the approach to design and develop provable secure primitives. Hereby, a security proof is typically the reduction from a problem P  related with the security of the candidate scheme, to a well known problem P_{1} of e.g. a random oracle or a oneway function. An authenticated encryption scheme (AE), is a symmetric primitive that provides both  data privacy and data integrity. To identify a secure and robust authenticated encryption scheme, the CAESAR competition was recently announced. COPA is an AE composition scheme used in several CAESAR candidates. We consider COPA in the noncerespecting setting, and derive a variant of the scheme COPA, which we prove secure beyond the birthday bound. For the proof, we use Patarin's coefficientH technique  a well known technique for probable security of symmetric primitives. Furthermore, we show the applicability of our results to the CAESAR candidates AESCOPA and PRØST, where we increase the INDCPA security bound from 2^{64} to 2^{83} encryption calls for AESCOPA and from 2^{64}(2^{128}) to 2^{83}(2^{168}) encryption calls for PRØSTCOPA, respectively. Moreover, we studied the mode COPA in the CAESAR candidate schemes Deoxys, Joltik and KIASU. Since COPA is used there in a slightly derivate version, we established another separate proof for privacy and integrity. Therefore, we can give first results on the conjecture of Jean et al., that Deoxys, Joltik and KIASU achieve security beyond the birthday bound in the noncerespecting setting.
Keywords: Provable Security, CAESAR, Authenticated Encryption, COPA, INDCPA, INTCTXT, Nonce, AESCOPA, PRØST, Deoxys, Joltik, KIASU
COPA
In this thesis we have analyzed COPA  an authenticated encryption scheme and derived a variant of this scheme for which we prove security beyond the birthday bound in the nonce respecting setting. COPA was announced at ASIACRYPT 2013 by Andreeva et al.
COPA
COPA is a variant of COPA, that is aimed to achieve security beyond the birthday bound. The following table shows the differences between COPA and COPA.
COPA  COPA  
Adversary  noncereusing  noncerespecting 
L_{i} (Tweaks)  E_{K}(0)  E_{K}(L) 
V_{i} (AD)  see Thesis  PRF_{K}(N, AD) 
K (Key)  K  K_{1}, K_{2}, K_{3} 
Table: Main Differences between COPA and COPA
Figure: Message Processing of COPA after replacement of PRF with a random function and E_{K} with permutations.
Privacy Proof for COPA
Theorem. Let Π = (E,E^{1}) denote the candidate COPA. Moreover, let D be a distinguisher making at most q queries to either E or $^{OAE} and using time t then,
Adv_{E}^{INDCPA}(D) ≤ 8(σ + q \choose 3) / (2^{n}  q)^{2} + 2Adv_{E}^{SPRP}(2σ + q, t') + Adv_{E}^{PRF}(q, t')
For the proof we use Patarin's coefficientH technique. For the detailed proof we refer to the thesis in the Downloads section.
Integrity of COPA
Although we haven't established a security proof for the integrity of COPA, we conjecture that the bound of the original COPA proof holds.
Application to AESCOPA
AESCOPA is a CAESAR candidate, proposed by Andreeva et al. AESCOPA uses as underlying design principle COPA. Using our improvement of COPA we can increase security beyond the birthday bound as shown in the following table:
AESCOPA  AESCOPA  
Confidentiality of plaintext  2^{64}  2^{83} 
Integrity of plaintext  2^{64}  2^{64} 
Integrity of associated data  2^{64}  2^{64} 
Integrity of PMN  2^{64}  2^{64} 
Table: Security Claims of AESCOPA and AESCOPA for n = 128.
Application to PRØSTCOPA
PRØST is a CAESAR candidate, proposed by Kavun et al. PRØSTCOPA uses as underlying design principle COPA. Using our improvement of COPA we can increase security beyond the birthday bound as shown in the following table:
PRØSTCOPA  PRØSTCOPA  
Confidentiality of plaintext  2^{64}/2^{128}  2^{83}/2^{168} 
Integrity of plaintext  2^{64}/2^{128}  2^{64}/2^{128} 
Integrity of associated data  2^{64}/2^{128}  2^{64}/2^{128} 
Integrity of PMN  2^{64}/2^{128}  2^{64}/2^{128} 
Table: Security Claims of PRØSTCOPA and PRØSTCOPA for n = {128, 256}.
Downloads
Master's Thesis  894 kB 

Presentation  770 kB 