Re: [Cfrg] Deoxys-II for AEAD

Hi Uri,

For long messages, on processors with a PCLMULQDQ instruction,
AES-GCM-SIV will be indeed faster than Deoxys-II. Yet, this might not
be the case on less fancy software platforms or in hardware. Besides,
there is no initialisation needed in Deoxys-II, so for short messages
the efficiency should be very similar.

In any case, independently of the high-end server efficiency, we
believe Deoxys-II provides interesting features listed in my previous
email. Also, I would like to emphasize that trust in a symmetric key
cipher is something extremely valuable and is provided by the actual
cryptanalysis performed on the scheme. As a winner of the CAESAR
competition, Deoxys-II went through extensive cryptanalysis from the
symmetric-key crypto community.

Regards,

Thomas.

Le ven. 22 nov. 2019 à 04:54, Blumenthal, Uri - 0553 - MITLL
<uri@ll.mit.edu> a écrit :
>
> How does Deoxys-II compare to AES-GCM-SIV+ (not AES-GCM-SIV)? E.g., https://tools.ietf.org/html/rfc8452 and https://eprint.iacr.org/2017/168.pdf ?
>
>
>
> I don’t see how you can be faster than POLYVAL…
>
>
>
> From: Cfrg <cfrg-bounces@irtf.org> on behalf of denis bider <denisbider.ietf@gmail.com>
> Date: Thursday, November 21, 2019 at 3:33 PM
> To: Thomas Peyrin <thomas.peyrin@gmail.com>
> Cc: CFRG <cfrg@irtf.org>
> Subject: Re: [Cfrg] Deoxys-II for AEAD
>
>
>
> Two comments:
>
>
>
> - I'm not a cryptographer, only a user, but the described properties sound awesome!
>
>
>
> - Have you considered making the reference implementations available under a license other than GPL?
>
>
>
> This is not going to fly very far until (and unless) BSD-licensed, MIT-licensed, fully public domain, or anything other than GPL implementations are available.
>
>
>
> denis
>
>
>
> On Thu, Nov 21, 2019 at 11:11 AM Thomas Peyrin <thomas.peyrin@gmail.com> wrote:
>
> Dear all,
>
> Following my presentation at yesterday’s CFRG meeting, we would like
> to propose Deoxys-II for consideration at IRTF. Deoxys-II is the
> winner of the CAESAR competition for Authenticated Encryption
> (portfolio “defense in depth”) that terminated a few months ago after
> a 5-year process that went through several rounds of selection
> (https://competitions.cr.yp.to/caesar-submissions.html).
>
> Deoxys-II is a nonce-misuse resistant beyond-birthday AEAD
> (Authenticated Encryption with Associated Data) scheme, with two
> versions: 128-bit key and 256-bit key. It is based on Deoxys-BC, a new
> tweakable block cipher that reuses the AES round function, and SCT-2,
> a nonce-misuse resistant AEAD operating mode. We believe it presents a
> lot of interesting features from a security and efficiency point of
> view.
>
>
> - It is a very simple, clean design, and offers a lot of flexibility
>
> - It provides full 128-bit security for both privacy and authenticity
> when the nonce is not reused (meaning the AE security bound is of the
> form O(q/2^{128}), where q is the total number of encryption or
> decryption queries). This is very different from block cipher-based
> modes such as OCB3, GCM, or AES-GCM-SIV. To give a numerical example,
> when encrypting 2^32 messages of 64 KB each, existing security proofs
> ensure that the attacker against authenticity has an advantage of at
> most 2^−37 for OCB3, 2^−41 for GCM, 2^-73 or AES-GCM-SIV, and 2^−94
> for Deoxys-II.
>
> - Nonce-misuse resistance: Deoxys-II provides very good resistance
> when the nonce is reused. Actually, if the nonce is reused only a
> small number of times, it retains most of its full 128-bit security as
> the security degrades only linearly with the number of nonce
> repetitions. This is very different from OCB3 and GCM (for which a
> single nonce reuse breaks confidentiality and allows universal
> forgeries). Compared to AES-GCM-SIV which is also nonce-misuse
> resistant, Deoxys-II provides a larger security margin: for example,
> when encrypting 2^32 messages of 64 KB each with the same nonce, the
> attacker gets an advantage of about 2^−41 against AES-GCM-SIV versus
> 2^−51 for Deoxys-II.
>
> - Deoxys-II security has been already analyzed by the designers and by
> many third parties during the CAESAR competition (a few publication
> venue examples among several others: CRYPTO 2016, ISCAS 2017,
> INDOCRYPT 2017, FSE 2018, EUROCRYPT 2018, ISC 2018, 2*FSE 2019, …).
> One can see some of these works listed on the Deoxys website:
> https://sites.google.com/view/deoxyscipher   This provides very strong
> confidence in the design.
>
> - Deoxys-II is fully parallelizable, inverse-free (no need to
> implement decryption for the internal tweakable block cipher) and
> initialization-free. It provides very good software performances,
> benefiting from the AES-NI instructions and general good performances
> of AES on any platform. Benchmarks for efficiency comparison will be
> produced soon, but one can expect a speed at about 1.5 AES-GCM-SIV for
> long messages, and about the same speed as AES-GCM-SIV for short
> messages.
>
> - Constant time implementations for Deoxys-II are straightforward,
> basically using directly bitslice implementations of AES.
>
> - A tweakable block cipher (TBC) such as Deoxys-BC is a very valuable
> primitive, that can be used to build easily lots of different more
> complex schemes, with very strong security bounds (for example,
> several NIST LWC candidates are based on a TBC and defining a hash out
> of it). To the best of our knowledge, there is no standard TBC as of
> today.
>
> - Deoxys-II is not covered by any patent.
>
>
> More details on our design, reference implementations and test
> vectors, can be found here: https://sites.google.com/view/deoxyscipher
>
>
> The Deoxys-II team.
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg