Advances in Mathematics of Communications
November 2019 , Volume 13 , Issue 4
Special issue on applications of discrete mathematics in secure communication
Select all articles
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
A repairable threshold scheme (which we abbreviate to RTS) is a
In this paper we define a class of generalized Boolean functions defined on
Cover-free families are set systems used as solutions for a large variety of problems, and in particular, problems where we deal with
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 (
In CRYPTO 2016, Cogliati and Seurin have proposed a nonce-based MAC called Encrypted Wegman-Carter with Davies-Meyer (
for a nonce
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
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
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.
Add your name and e-mail address to receive news of forthcoming issues of this journal:
[Back to Top]