American Institute of Mathematical Sciences

We give an overview of our critiques of "proofs" of security and a guide to our papers on the subject that have appeared over the past decade and a half. We also provide numerous additional examples and a few updates and errata.

Using the class of information set decoding algorithms is the best known way of decoding general codes, i.e. codes that admit no special structure, in the Hamming metric. The Stern algorithm is the origin of the most efficient algorithms in this class. We consider the same decoding problem but for a channel with soft information. We give a version of the Stern algorithm for a channel with soft information that includes some novel steps of ordering vectors in lists, based on reliability values. We demonstrate how the algorithm constitutes an improvement in some cryptographic and coding theoretic applications. We also indicate how to extend the algorithm to include multiple iterations and soft output values.

The associated codes of almost perfect nonlinear (APN) functions have been widely studied. In this paper, we consider more generally the codes associated with functions that have differential uniformity at least \begin{document}$ 4 $\end{document}. We emphasize, for such a function \begin{document}$ F $\end{document}, the role of codewords of weight \begin{document}$ 3 $\end{document} and \begin{document}$ 4 $\end{document} and of some cosets of its associated code \begin{document}$ C_F $\end{document}. We give some properties on codes associated with differential uniformity exactly \begin{document}$ 4 $\end{document}. We obtain lower bounds and upper bounds for the numbers of codewords of weight less than \begin{document}$ 5 $\end{document} of the codes \begin{document}$ C_F $\end{document}. We show that the nonlinearity of \begin{document}$ F $\end{document} decreases when these numbers increase. We obtain a precise expression to compute these numbers, when \begin{document}$ F $\end{document} is a plateaued or a differentially two-valued function. As an application, we propose a method to construct differentially \begin{document}$ 4 $\end{document}-uniform functions, with a large number of \begin{document}$ 2 $\end{document}-to-\begin{document}$ 1 $\end{document} derivatives, from APN functions.

A repairable threshold scheme (which we abbreviate to RTS) is a \begin{document}$ (\tau,n) $\end{document}-threshold scheme in which a subset of players can "repair" another player's share in the event that their share has been lost or corrupted. This will take place without the participation of the dealer who set up the scheme. The repairing protocol should not compromise the (unconditional) security of the threshold scheme. Combinatorial repairable threshold schemes (or combinatorial RTS) were recently introduced by Stinson and Wei [8]. In these schemes, "multiple shares" are distributed to each player, as defined by a suitable combinatorial design called the distribution design. In this paper, we study the reliability of these combinatorial repairable threshold schemes in a setting where players may not be available to take part in a repair of a given player's share. Using techniques from network reliability theory, we consider the probability of existence of an available repair set, as well as the expected number of available repair sets, for various types of distribution designs.

In this paper we define a class of generalized Boolean functions defined on \begin{document}$ {\mathbb F}_2^n $\end{document} with values in \begin{document}$ {\mathbb Z}_q $\end{document} (we consider \begin{document}$ q = 2^k $\end{document}, \begin{document}$ k\geq 1 $\end{document}, here), which we call landscape functions (whose class contains generalized bent, semibent, and plateaued) and find their complete characterization in terms of their Boolean components. In particular, we show that the previously published characterizations of generalized plateaued Boolean functions (which includes generalized bent and semibent) are in fact particular cases of this more general setting. Furthermore, we provide an inductive construction of landscape functions, having any number of nonzero Walsh-Hadamard coefficients. We also completely characterize generalized plateaued functions in terms of the second derivatives and fourth moments.

Cover-free families are set systems used as solutions for a large variety of problems, and in particular, problems where we deal with \begin{document}$ n $\end{document} elements and want to identify \begin{document}$ d $\end{document} defective ones among them by performing only \begin{document}$ t $\end{document} tests (\begin{document}$ t \leq n $\end{document}). We are especially interested in cryptographic problems, and we note that some of these problems need cover-free families with an increasing size \begin{document}$ n $\end{document}. Solutions that propose the increase of \begin{document}$ n $\end{document}, such as monotone families and nested families, have been recently considered in the literature. In this paper, we propose a generalization that we call embedding families, which allows us to increase both \begin{document}$ n $\end{document} and \begin{document}$ d $\end{document}. We propose constructions of embedding families using polynomials over finite fields embedded via extension fields; we study how different parameter combinations can be used to prioritize increase of \begin{document}$ d $\end{document} or of the compression ratio as \begin{document}$ n $\end{document} grows. We also provide new constructions for monotone families with improved compression ratio. Finally, we show how to use embedded sequences of orthogonal arrays and packing arrays to build embedding families.

This work studies the success probability of key recovery attacks based on using a single linear approximation. Previous works had analysed success probability under different hypotheses on the distributions of correlations for the right and wrong key choices. This work puts forward a unifying framework of general key randomisation hypotheses. All previously used key randomisation hypotheses as also zero correlation attacks can be seen as special cases of the general framework. Derivations of expressions for the success probability are carried out under both the settings of the plaintexts being sampled with and without replacements. Compared to previous analysis, we uncover several new cases which have not been considered in the literature. For most of the cases which have been considered earlier, we provide complete expressions for the respective success probabilities. Finally, the full picture of the dependence of the success probability on the data complexity is revealed. Compared to the extant literature, our work provides a deeper and more thorough understanding of the success probability of single linear cryptanalysis.

Salsa and ChaCha are well known names in the family of stream ciphers. In this paper, we first revisit the existing attacks on these ciphers. We first perform an accurate computation of the attack complexities of the existing technique instead of the estimation used in previous works. This improves the complexity by some margin. The differential attacks using probabilistic neutral bits against ChaCha and Salsa involve two probability biases: forward probability bias (\begin{document}$ \epsilon_d $\end{document}) and backward probability bias (\begin{document}$ \epsilon_a $\end{document}). In the second part of the paper, we suggest a method to increase the backward probability bias, which helps reduce the attack complexity. Finally, we focus on the design principle of ChaCha. We suggest a slight modification in the design of this cipher as a countermeasure of the differential attacks against it. We show that the key recovery attacks proposed against ChaCha will not be effective on this modified version.

In CRYPTO 2016, Cogliati and Seurin have proposed a nonce-based MAC called Encrypted Wegman-Carter with Davies-Meyer (\begin{document}$\textsf{EWCDM}$\end{document}), from an \begin{document}$n$\end{document}-bit block cipher \begin{document}$\textsf{E}$\end{document} and an \begin{document}$n$\end{document}-bit almost xor universal hash function\begin{document}$\textsf{H}$\end{document} as

\begin{document}$\textsf{E}_{K_2}\bigl(\textsf{E}_{K_1}(N)\oplus N\oplus \textsf{H}_{K_h}(M)\bigr),$ \end{document}

for a nonce \begin{document}$N$\end{document} and a message \begin{document}$M$\end{document} that provides roughly \begin{document}$2n/3$\end{document}-bit MAC security. However, obtaining the similar security using a single block cipher key was posed as an open research problem. In this paper, we present Decrypted Wegman-Carter with Davies-Meyer (\begin{document}$\textsf{DWCDM+}$\end{document}) construction based on a single block cipher key that provides \begin{document}$2n/3$\end{document}-bit MAC security from an \begin{document}$n$\end{document}-bit block cipher \begin{document}$\textsf{E}$\end{document} and an \begin{document}$n$\end{document}-bit \begin{document}$k$\end{document}-regular (\begin{document}$\forall k \leq n$\end{document}), almost xor universal hash function \begin{document}$\textsf{H}$\end{document} as

\begin{document} $ \textsf{E}^{-1}_{K}\bigl(\textsf{E}_{K}(N)\oplus N \oplus \textsf{H}_{K_h}(M)\bigr). $ \end{document}

\begin{document}$\textsf{DWCDM+}$\end{document} is structurally very similar to its predecessor \begin{document}$\textsf{EWCDM}$\end{document} except that the facts that (i) the number of block cipher keys reduced from \begin{document}$2$\end{document} to \begin{document}$1$\end{document} and (ⅱ) the outer encryption call is replaced by a decryption one. To make the construction truely single-keyed, here we derive the hash key \begin{document}$K_h$\end{document} as the block cipher output of a fixed string \begin{document}$0^{n-2} \| 10$\end{document} as long as the hash key is of \begin{document}$n$\end{document} bits. We show that if the nonce space is restricted to \begin{document}$(n-1)$\end{document} bits, \begin{document}$\textsf{DWCDM+}$\end{document} is secured roughly up to \begin{document}$2^{2n/3}$\end{document} MAC queries (\begin{document}$2^{n/2}$\end{document} MAC queries) and \begin{document}$2^n$\end{document} verification queries against nonce respecting (nonce misuse resp.) adversaries.

Link Prediction is an important and well-studied problem for social networks. Given a snapshot of a graph, the link prediction problem predicts which new interactions between members are most likely to occur in the near future. As networks grow in size, data owners are forced to store the data in remote cloud servers which reveals sensitive information about the network. The graphs are therefore stored in encrypted form.

We study the link prediction problem on encrypted graphs. To the best of our knowledge, this secure link prediction problem has not been studied before. We use the number of common neighbors for prediction. We present three algorithms for the secure link prediction problem. We design prototypes of the schemes and formally prove their security. We execute our algorithms in real-life datasets.

A key-aggregate cryptosystem (KAC) is the dual of the well-known notion of broadcast encryption (BE). In KAC, each plaintext message is encrypted with respect to some identity, and a single aggregate key can be generated for any arbitrary subset \begin{document}$ \mathcal{S} $\end{document} of identities, such that any ciphertext designated for any identity in \begin{document}$ \mathcal{S} $\end{document} can be decrypted using this aggregate key. A KAC scheme is said to be efficient if all public parameters, ciphertexts and aggregate keys have polynomial overhead, and can be generated using poly-time algorithms.

A KAC scheme is said to be identity-based if remains efficient even when the number of unique identities supported by the system is exponential in the security parameter \begin{document}$ \lambda $\end{document}. Unfortunately, existing KAC constructions do not satisfy this property. In particular, adopting these constructions to the identity-based setting leads to public parameters with exponential overhead.

In this paper, we propose new identity-based KAC constructions using multilinear maps that are secure in the generic multilinear map model, and are fully collusion resistant against any number of colluding parties. Our first construction is based on asymmetric multilinear maps, with a poly-logarithmic overhead for the public parameters, and a constant overhead for the ciphertexts and aggregate keys. Our second construction is based on the more generalized symmetric multilinear maps, and offers tighter security bounds in the generic multilinear map model. This construction has a poly-logarithmic overhead for the public parameters and the ciphertexts, while the overhead for the aggregate keys is still constant.

A matrix is MDS or super-regular if and only if every square submatrices of it are nonsingular. MDS matrices provide perfect diffusion in block ciphers and hash functions. In this paper we provide a brief survey on cryptographically significant MDS matrices - a first to the best of our knowledge. In addition to providing a summary of existing results, we make several contributions. We exhibit some deep and nontrivial interconnections between different constructions of MDS matrices. For example, we prove that all known Vandermonde constructions are basically equivalent to Cauchy constructions. We prove some folklore results which are used in MDS matrix literature. Wherever possible, we provide some simpler alternative proofs. We do not discuss efficiency issues or hardware implementations; however, the theory accumulated and discussed here should provide an easy guide towards efficient implementations.