Security of Full-State Keyed Sponge and Duplex: Applications to Authenticated Encryption

We provide a security analysis for full-state keyed Sponge and full-state Duplex constructions. Our results can be used for making a large class of Sponge-based authenticated encryption schemes more efficient by concurrent absorption of associated data and message blocks. In particular, we introduce and analyze a new variant of SpongeWrap with almost free authentication of associated data. The idea of using full-state message absorption for higher efficiency was first made explicit in the Donkey Sponge MAC construction, but without any formal security proof. Recently, Gaži, Pietrzak and Tessaro (CRYPTO 2015) have provided a proof for the fixed-output-length variant of Donkey Sponge. Yasuda and Sasaki (CT-RSA 2015) have considered partially full-state Sponge-based authenticated encryption schemes for efficient incorporation of associated data. In this work, we unify, simplify, and generalize these results about the security and applicability of full-state keyed Sponge and Duplex constructions; in particular, for designing more efficient authenticated encryption schemes. Compared to the proof of Gaži et al., our analysis directly targets the original Donkey Sponge construction as an arbitrary-output-length function. Our treatment is also more general than that of Yasuda and Sasaki, while yielding a more efficient authenticated encryption mode for the case that associated data might be longer than messages.

Boosting OMD for Almost Free Authentication of Associated Data

Reza Reyhanitabar, Serge Vaudenay, Damian Vizár

We propose pure OMD (p-OMD) as a new variant of the Offset Merkle-Damgård (OMD) authenticated encryption scheme. Our new scheme inherits all desirable security features of OMD while having a more compact structure and providing higher efficiency. The original OMD scheme, as submitted to the CAESAR competition, couples a single pass of a variant of the Merkle-Damgård (MD) iteration with the counter-based XOR MAC algorithm to provide privacy and authenticity. Our improved p-OMD scheme dispenses with the XOR MAC algorithm and is purely based on the MD iteration; hence, the name ``pure'' OMD. To process a message of

\ell

blocks and associated data of

a

blocks, OMD needs

\ell+a+2

calls to the compression function while p-OMD only requires max{

\ell, a

2

calls. Therefore, for a typical case where

\ell \geq a

, p-OMD makes just

\ell+2

calls to the compression function; that is, associated data is processed almost freely compared to OMD. We prove the security of p-OMD under the same standard assumption (pseudo-randomness of the compression function) as made in OMD; moreover, the security bound for p-OMD is the same as that of OMD, showing that the modifications made to boost the performance are without any loss of security.

Springer2015

Time in cryptography

Gwangbae Choi

Time travel has always been a fascinating topic in literature and physics. In cryptography, one may wonder how to keep data confidential for some time. In this dissertation, we will study how to make private information travel to the future. This dissertation consists of three parts: Timed-release encryption, witness encryption and self-encryption. With timed-release encryption, one can send to a counterpart a message which cannot be read before some time has elapsed. One possible solution is to use a third party. At every time period, the third party releases a time bound key, and a ciphertext which is encrypted for a time period requires the time bound key of that time period for decryption. Then, a problem occurs when the counterpart somehow loses the release time of ciphertext. We propose a solution by introducing a master time bound key which can be considered as a valid time bound key of all time periods. We propose a provably secure construction and show the experimental results. In 2018, Liu, Jager, Kakvi and Warinschi introduced a timed-release encryption scheme based on a blockchain with proof-of-work and witness encryption. Current proposals of witness encryption are based on multilinear maps. In this part, we propose a new construction without. We propose the notion of hidden group with hashing and make a witness encryption from it. We show that the construction is secure in a generic model. We propose a concrete construction based on RSA-related problems. Namely, we use an extension of the knowledge-of-exponent assumption and the order problem. We finally estimate the cost of the bitcoin blockchain implementation. Although our estimates are still high (for a release time of one hour / one year, we respectively use ciphertexts of 567 MB / 4.5 TB and a decryption time of 27 min / 5.2 months on a single core), there is room for improvement by a factor 20 000 by adapting the blockchain structure and by adopting a hash function which is better adapted to this type of programming than SHA256. In self-encryption, a device encrypts some piece of information for itself to decrypt in the future. We are interested in security of self-encryption when the state occasionally leaks. Applications where self-encryption operates are cloud storage, when a client encrypts files to be stored, and in 0-RTT session resumptions, when a server encrypts a resumption key to be stored by the client. Previous works focused on forward secrecy and resistance to replay attacks. In our work, we study post-compromise security. Post-compromise security was already solved in ratcheted instant messaging schemes, at the price of having an inflating state size. However, it was not known whether state inflation was necessary. We prove here that this is the case. In our results, we prove that post-compromise security implies a super-linear state size in terms of the number of ciphertexts which can still be decrypted by the state. We apply our result to self-encryption for cloud storage and 0-RTT session resumption, and also to secure messaging. We further show how to construct a secure scheme matching our bound on the state size.

EPFL2020

A Family of Fast Syndrome Based Cryptographic Hash Functions

Recently, some collisions have been exposed for a variety of cryptographic hash functions including some of the most widely used today. Many other hash functions using similar constructions can however still be considered secure. Nevertheless, this has drawn attention on the need for new hash function designs. In this article is presented a family of secure hash functions, whose security is directly related to the syndrome decoding problem from the theory of error-correcting codes. Taking into account the analysis by Coron and Joux based on Wagner's generalized birthday algorithm we study the asymptotical security of our functions. We demonstrate that this attack is always exponential in terms of the length of the hash value. We also study the work-factor of this attack, along with other attacks from coding theory, for non asymptotic range, i.e. for practical values. Accordingly, we propose a few sets of parameters giving a good security and either a faster hashing or a shorter description for the function.

2005