Subterranean 2.0, a NIST second round lightweight cryptographic primitive, was introduced by Daemen et al. in 2020. It has three modes of operation: Subterranean-SAE, Subterranean-deck, and Subterranean-XOF. So far, most of the existing practical-time implementable attacks on Subterranean-SAE fall under the nonce misuse setting scenario. In this paper, we present significantly improved Differential Fault Analysis on Subterranean-SAE and Subterranean-deck. We consider a more challenging framework of unknown fault injection round, and achieve improved execution time as well as data complexity over the best known fault attack available in the literature. We utilize deep neural networks and also correlation coefficient for generation of signatures and matching them. Two general frameworks are proposed for fault location identification assuming that fault injection round is unknown. Finally, we use aSATsolver to efficiently recover the embedded encryption key with no more than 5 distinct faults. Experimental results reveal that the total time (online phase) required to mount the attack on Subterranean-SAE (Subterranean-deck) is 1234.6 (1334.6) seconds.

To support efficient design automation for emerging computing fabrics, novel data structures for logic synthesis and technology mapping are being intensively studied. It has been shown that for several promising computing technologies intermediate forms, such as Majority-inverter graph (MIG) and XOR-Majority graph (XMG) can be particularly beneficial. This has propelled the Boolean Majority operator at the forefront of research. Though these structures primarily utilize 3-input Majority nodes, the efficacy of$n$-input Majority operators has been demonstrated as well. A long-standing research problem, in that context and also for theoretical circuit complexity, is to determine efficient decomposition of an$n$-input Majority$({\mathrm{ Maj}}_{n})$function in terms of 3-input Majority$({\mathrm{ Maj}}_{3})$operator. In this manuscript, we make two significant advances in this topic. First, a practically realizable linear decomposition is provided, thus improving the previously reported quadratic bounds. Second, the theoretical upper bound of decomposing${\mathrm{ Maj}}_{n}$, in terms of${\mathrm{ Maj}}_{3}$, is reduced from$5.884n$to$3n$. The erstwhile theoretical upper bound of$5.884n$also lacked a practical construction for${\mathrm{ Maj}}_{n}$decomposition, presumably due to the presence of sequential elements in the algorithm. The proof of the linearity, detailed construction procedure along with experimental studies using state-of-the-art synthesis flows to validate the aforementioned claims are presented in this work. The results are applicable to threshold Boolean functions, too.

In this paper we exploit elementary combinatorial techniques to settle different cryptanalytic observations on RC4 that remained unproved for more than two decades. At the same time, we present new observations with theoretical proofs. We first prove the biases (non-randomness) presented by Fluhrer and McGrew (FSE 2000) two decades ago. It is surprising that though the biases have been published long back, and there are many applications of them in cryptanalysis till recent days as well, the proofs have never been presented. In this paper, we complete that task and also show that any such bias immediately provides a glimpse of hidden variables in RC4. Further, we take up the biases of two non-consecutive key-stream bytes skipping one byte in between. We show the incompleteness of such a result presented by SenGupta et al. (JoC, 2013) and provide new observations and proofs in this direction relating the key-stream bytes and glimpses. Similarly, we streamline certain missed observation in the famous Glimpse theorem presented by Jenkins in 1996. Our results point out how biases of RC4 key-stream and the Glimpses of the RC4 hidden variables are related. It is evident from our results that the biases and glimpses are everywhere in RC4 and it needs further investigation as we provide very high magnitude of glimpses that were not known earlier.

In this article, we propose key recovery attack on two stream ciphers: Kreyvium and FLIP$_{530}(42,128,360)$using Differential Fault Attack (DFA) technique. These two ciphers are being used in Fully Homomorphic Encryption (FHE) due to their low error growth during keystream generation. Kreyvium is an NFSR-based stream cipher and FLIP is a permutation-based stream cipher. We first show that the complete state of the Kreyvium can be recovered by injecting 3 faults and considering 450 many keystream bits. In case of FLIP, we show that if there is a 1-bit fault in the state of the cipher then from 9000 normal and faulty keystream bits the state (i.e., the secret key) of the cipher can be recovered. For single bit fault, one will require to solve a system of equations for each 530 possible fault locations to recover the correct key of FLIP. To the best of our knowledge, this is the first article which analyzes the security of these two FHE supported stream ciphers under DFA and it has been observed that DFA completely reveals the secret keys of these two ciphers with very minimal faults.

Boolean functions are usually studied under the assumption that each input bit is considered independent and identically distributed. However, in the case of some stream ciphers, a keystream bit is generated by using a nonlinear Boolean function with inputs from a restricted domain. At Eurocrypt 2016, one such stream cipher (FLIP) has been proposed, where a Boolean function on n variables was exploited with inputs of weight n/2 only. Recently, Carlet et al. studied several properties of such functions and obtained certain bounds on linear approximations of direct sum in the restricted domain. In this paper, we observe that for a direct sum like f = f1+ f2, the inputs to each sub-function f1, f2do not follow a uniform distribution in the restricted domain. In this regard, we study the properties of the Boolean functions by considering a general probability distribution on the inputs. We further obtain several bounds related to the biases of direct sums. Finally, we obtain a lower bound on the bias of the nonlinear filter function of FLIP. Our results provide a general framework to study security parameters of ciphers over restricted domain.

In this study, the authors construct two different distinguishers on Grain‐v1 with 112 and 114 initialisation rounds. Their first distinguisher can distinguish Grain‐v1 with 112 initialisation rounds from a uniform random source for 99% of the randomly chosen keys from full key space. The second one can distinguish Grain‐v1 from a random source for 73% of the randomly chosen keys for one‐fourth of the total key space (2 78 keys out of 2 80 keys). Our results improve upon the earlier distinguishers. The technique used for the distinguishers is conditional differential cryptanalysis. The existing works in this direction considered only one bit difference in the initialisation vector. However, for the first time, they could handle complicated conditions for the 2‐bit difference to obtain better cryptanalytic results. Extending their technique by allowing the 1‐bit difference in the pair of keys (i.e. related keys) and the 4‐bit difference in IVs, they could observe the non‐randomness till 116 initialisation rounds with a success in 62% cases.

Very recently, a class of cryptographically significant Boolean functions were constructed by Tang and Maitra [ IEEE Trans. Inform. Theory, 64 (2018), pp. 393--402] by modifying the $\mathcal{PS}_{ap}$ class of bent functions. The basic ideas used in Tang--Maitra construction were derived from a modification of a subclass of bent functions which is defined over the finite field, and a concern was raised in the same paper whether the implementation of such functions will be as efficient as that of Maiorana--McFarland type bent functions. In this paper, we look at the concrete realization of such functions over a vector space and answer the question positively. The first part of this paper investigates how the finite field implementation of the functions can be viewed as simple truth tables. Next, we present a completely new construction that itself starts from Maiorana--McFarland bent functions which are straightforward concatenations of linear functions.

Construction of Boolean functions on an odd number of variables with nonlinearity exceeding the bent concatenation bound is one of the most difficult combinatorial problems within the domain of Boolean functions. This problem also has deep implications in coding theory and cryptology. Patterson and Wiedemann demonstrated instances of such functions back in 1983. For more than three decades efforts have been channeled into obtaining such instances. For the first time, in this paper we explore nontrivial upper bounds on nonlinearity for such classes of functions that are invariant not only under several group actions but also for larger sets of functions than what have been considered so far. Further, we present tight upper bounds on the nonlinearity in several cases. To support our claims, we present computational results for functions on $n$ variables, where $n$ is an odd composite integer in the interval [9, 39]. In particular, our results for $n = 15$ and 21 are of immediate interest given recent research results in this domain. In addition to the upper bounds, we also discover the nonlinearities that can actually be achieved above the bent concatenation bound for such a class of functions. Finally, we obtain all possible values in the absolute Walsh spectra of the functions considered.

Lizard is a very recently proposed lightweight stream cipher that claims 60 bit security against distinguishing (related to state recovery) and 80 bit security against key recovery attack. This cipher has 121 bit state size. In this paper, we first note that using ψ key stream bits one can recover ψ unknown bits of the state when t state bits are fixed to a specific pattern. This is made possible by guessing the remaining state bits. We present certain values of ψ, t based on the state size that helps in mounting a generic conditional TMDTO attack following the BSW sampling. For Lizard, we obtain the preprocessing complexity as 267, and the maximum of Data, Time and Memory complexity during the online phase as 254. The parameters in the online phase are significantly less than 260.

In this paper, we consider the maximum absolute value Δfin the autocorrelation spectrum (not considering the zero point) of a function f. In an even number of variables n, bent functions possess the highest nonlinearity with Δf= 0. The long standing open question (for two decades) in this area is to obtain a theoretical construction of balanced functions with Δfn/2. So far, there are only a few examples of such functions for n = 10, 14, but no general construction technique is known. In this paper, we mathematically construct an infinite class of balanced Boolean functions on n variables having absolute indicator strictly lesser than δn= 2n/2- 2((n+6)/4), nonlinearity strictly greater than ρn= 2n-1-2n/2+2n/2-3-5·2((n-2)/4)and algebraic degree n - 1, where n ≡ 2 (mod 4) and n ≥ 46. While the bound n ≥ 46 is required for proving the generic result, our construction starts from n = 18, and we could obtain balanced functions with Δfn/2and nonlinearity > 2n-1- 2n/2for n = 18, 22, and 26.

Lightweight stream ciphers have received serious attention in the last few years. The present design paradigm considers very small state (less than twice the key size) and use of the secret key bits during pseudo-random stream generation. One such effort, Sprout, had been proposed two years back and it was broken almost immediately. After carefully studying these attacks, a modified version named Plantlet has been designed very recently. While the designers of Plantlet do not provide any analysis on fault attacks, we note that Plantlet is even weaker than Sprout in terms of Differential Fault Attack (DFA). Our investigation, following the similar ideas as in the analysis against Sprout, shows that we require only around 4 faults to break Plantlet by DFA in a few hours time. While fault attack is indeed difficult to implement and our result does not provide any weakness of the cipher in normal mode, we believe that these initial results will be useful for further understanding of Plantlet.

Nonlinearity is one of the most challenging combinatorial property in the domain of Boolean function research. Obtaining nonlinearity greater than the bent concatenation bound for odd number of variables continues to be one of the most sought after combinatorial research problems. The pioneering result in this direction has been discovered by Patterson and Wiedemann in 1983 (IEEE-IT), which considered Boolean functions on 5 × 3 = 15 variables that are invariant under the actions of the cyclic group GF(25)*· GF(23)* as well as the group of Frobenius automorphisms. Some of these Boolean functions possess nonlinearity greater than the bent concatenation bound. The next possible option for exploring such functions is on 7 × 3 = 21 variables. However, obtaining such functions remained elusive for more than three decades even after substantial efforts as evident in the literature. In this paper, we exploit combinatorial arguments together with heuristic search to demonstrate such functions for the first time.

The series of published works, related to differential fault attack (DFA) against the Grain family, require quite a large number (hundreds) of faults and also several assumptions on the locations and the timings of the faults injected. In this paper, we present a significantly improved scenario from the adversarial point of view for DFA against the Grain family of stream ciphers. Our model is the most realistic one so far as it considers that the cipher has to be re-keyed only a few times and faults can be injected at any random location and at any random point of time, i.e., no precise control is needed over the location and timing of fault injections. We construct equations based on the algebraic description of the cipher by introducing new variables so that the degrees of the equations do not increase. In line of algebraic cryptanalysis, we accumulate such equations based on the fault-free and faulty key-stream bits and solve them using the SAT Solver Cryptominisat-2.9.5 installed with SAGE 5.7. In a few minutes we can recover the state of Grain v1, Grain-128 and Grain-128a with as little as 10, 4 and 10 faults respectively.

RC4 is the most popular stream cipher in the domain of cryptology. In this paper, we present a systematic study of the hardware implementation of RC4, and propose the fastest known architecture for the cipher. We combine the ideas of hardware pipeline and loop unrolling to design an architecture that produces 2 RC4 keystream bytes per clock cycle. We have optimized and implemented our proposed design using VHDL description, synthesized with 130, 90, and 65 nm fabrication technologies at clock frequencies 625 MHz, 1.37 GHz, and 1.92 GHz, respectively, to obtain a final RC4 keystream throughput of 10, 21.92, and 30.72 Gbps in the respective technologies.

Due to ubiquitous deployment of embedded systems, security and privacy are emerging as major design concerns and new stream ciphers are being proposed by the cryptographic community. HC-128 is one of the recent stream ciphers that received attention after its selection as an eStream candidate. Till date, the cipher is believed to have a good security margin. In this paper we study several implementation issues for HC-128 in a disciplined manner. We first discuss the experience on embedded and customizable processors. Then we consider a dedicated hardware accelerator implementation. Further we explore several parallelization strategies for improving throughput. To the best of our knowledge such a detailed implementation exercise has not been presented in the literature. Our novel implementation strategies mark the fastest HC-128 execution reported till date.

Parkerconsidered a new type of discrete Fourier transform, called nega-Hadamard transform. We prove several results regarding its behavior on combinations of Boolean functions and use this theory to derive several results on negabentness (that is, flat nega-spectrum) of concatenations, and partially symmetric functions. We derive the upper bound$\lceil {{ n}\over { 2}} \rceil $for the algebraic degree of a negabent function on$n$variables. Further, a characterization of bent–negabent functions is obtained within a subclass of the Maiorana–McFarland set. We develop a technique to construct bent–negabent Boolean functions by using complete mapping polynomials. Using this technique, we demonstrate that for each$\ell \geq 2$, there exist bent–negabent functions on$n = 12\ell $variables with algebraic degree$ {{ n}\over { 4}}+1 = 3\ell + 1$. It is also demonstrated that there exist bent–negabent functions on eight variables with algebraic degrees 2, 3, and 4. Simple proofs of several previously known facts are obtained as immediate consequences of our work.

In this paper, we analyze how to calculate the GCD ofk( ≥ 2) many large integers, given their approximations. This problem is known as the approximate integer common divisor problem in literature. Two versions of the problem, presented by Howgrave-Graham in CaLC 2001, turn out to be special cases of our analysis whenk= 2. We relate the approximate common divisor problem to the implicit factorization problem as well. The later was introduced by May and Ritzenhofen in PKC 2009 and studied under the assumption that some of Least Significant Bits (LSBs) of certain primes are the same. Our strategy can be applied to the implicit factorization problem in a general framework considering the equality of (i) most significant bits (MSBs), (ii) least significant bits (LSBs), and (iii) MSBs and LSBs together. We present new and improved theoretical as well as experimental results in comparison with the state of the art work in this area.

For the first time Boolean functions on 9 variables having nonlinearity$241$are discovered, that remained as an open question in literature for almost three decades. Such functions are found by heuristic search in the space of rotation symmetric Boolean functions (RSBFs). This shows that there exist Boolean functions on$n$(odd) variables having nonlinearity$> 2^{n-1} - 2^{{ n-1}\over { 2}}$if and only if$n > 7$. Using similar search technique, balanced Boolean functions on 9, 10, and 11 variables are attained having autocorrelation spectra with maximum absolute value$< 2^{\lceil {{ n}\over { 2}}\rceil }$. On odd number of variables, earlier such functions were known for 15, 21 variables; there was no evidence of such functions at all on even number of variables. In certain cases, our functions can be affinely transformed to obtain first-order resiliency or first-order propagation characteristics. Moreover, 10 variable functions having first-order resiliency and nonlinearity$492$are presented that had been posed as an open question at Crypto 2000. The functions reported in this paper are discovered using a suitably modified steepest descent based iterative heuristic search in the RSBF class along with proper affine transformations. It seems elusive to get a construction technique to match such functions.

Studying Boolean functions with high algebraic immunity (i.e., which can provide some kind of resistance against algebraic attack) has attracted much attention recently. In FSE 2005, Dalai, Gupta and Maitra presented the first construction of Boolean functions achieving maximum possible algebraic immunity. However, the important cryptographic properties, such as algebraic degree and nonlinearity, of the Boolean functions constructed using that method could not be answered, except (by experiment) when the number of variables was small (at most 16). In this paper we solve this problem for every number of variables. Further we study the structure of the construction in detail, and we deduce an algorithm for fast evaluation of the functions, which is crucial for a practical use in stream ciphers

Recently, algebraic attacks have received a lot of attention in the cryptographic literature. It has been observed that a Boolean function f used as a cryptographic primitive, and interpreted as a multivariate polynomial over F/sub 2/, should not have low degree multiples obtained by multiplication with low degree nonzero functions. In this paper, we show that a Boolean function having low nonlinearity is (also) weak against algebraic attacks, and we extend this result to higher order nonlinearities. Next, we present enumeration results on linearly independent annihilators. We also study certain classes of highly nonlinear resilient Boolean functions for their algebraic immunity. We identify that functions having low-degree subfunctions are weak in terms of algebraic immunity, and we analyze some existing constructions from this viewpoint. Further, we present a construction method to generate Boolean functions on n variables with highest possible algebraic immunity /spl lceil/n/2/spl rceil/ (this construction, first presented at the 2005 Workshop on Fast Software Encryption (FSE 2005), has been the first one producing such functions). These functions are obtained through a doubly indexed recursive relation. We calculate their Hamming weights and deduce their nonlinearities; we show that they have very high algebraic degrees. We express them as the sums of two functions which can be obtained from simple symmetric functions by a transformation which can be implemented with an algorithm whose complexity is linear in the number of variables. We deduce a very fast way of computing the output to these functions, given their input.

In 2003, Chu proposed an oblivious watermarking algorithm by modifying the CKLS scheme proposed by Cox, Kilian, Leighton, and Shamoon in 1997, known as the CKLS scheme. In this correspondence, we report that the modification presented by Chu is susceptible to a suitably modified attack devised by Das and Maitra in 2004. In fact, the experimental results show that Chu's scheme is even weaker than the CKLS scheme in terms of our attack.

The design of Boolean functions with properties of cryptographic significance is a hard task. In this paper, we adopt an unorthodox approach to the design of such functions. Our search space is the set of functions that possess the required properties. It is “Boolean‐ness” that is evolved.

Most of the existing digital watermarking techniques are based on correlation between "some information stored in the watermarked copy" and "related information retrieved from attacked watermarked copy". We show how to remove this correlation to mount a ciphertext-only cryptanalytic attack on these watermarking schemes. The attack needs only a single watermarked copy of the image. Our work clearly raises question on the basic watermarking paradigm based on correlation measures.

In this correspondence, we use affine functions on a small number of variables to construct resilient functions on a large number of variables. We show that by properly combining these functions it is possible to achieve high nonlinearity and high algebraic degree. An important contribution of the correspondence is to show that for each order of resiliency m, it is possible to find infinitely many odd and even positive integers n, such that it is possible to construct (maximum degree) n-variable, m-resilient functions having nonlinearity strictly greater than 2/sup n-1/-2/sup /spl lfloor/n/2/spl rfloor//. We also present construction of some important functions on a small number of variables.

Most of the existing watermarking processes become vulnerable when the attacker knows the watermark insertion algorithm. This paper presents an invisible spatial domain watermark insertion algorithm for which we show that the watermark can be recovered, even if the attacker tries to manipulate the watermark with the knowledge of the watermarking process. The process incorporates buyer specific watermarks within a single multimedia object, and the same multimedia object has different watermarks that differ from owner to owner. Therefore recovery of this watermark not only authenticates the particular owner of the multimedia object but also could be used to identify the buyer involved in the forging process. This is achieved after spatially dividing the multimedia signal randomly into a set of disjoint subsets (referred to as the image key) and then manipulating the intensity of these subsets differently depending on a buyer specific key. These buyer specific keys are generated using a secret permutation of error correcting codes so that exact keys are not known even with the knowledge of the error correcting scheme. During recovery process a manipulated buyer key (due to attack) is extracted from the knowledge of the image key. The recovered buyer key is matched with the exact buyer key in the database utilizing the principles of error correction. The survival of the watermark is demonstrated for a wide range of transformations and forging attempts on multimedia objects both in spatial and frequency domains. We have shown that quantitatively our watermarking survives rewatermarking attack using the knowledge of the watermarking process more efficiently compared to a spread spectrum based technique. The efficacy of the process increases in scenarios in which there exist fewer numbers of buyer keys for a specific multimedia object. We have also shown that a minor variation of the watermark insertion process can survive a "Stirmark" attack. By making the image key and the intensity manipulation proms specific for a buyer and with proper selection of error correcting codes, certain categories of collusion attacks can also be precluded.

The design of Boolean functions with properties of cryptographic significance is a hard task. In this paper, we adopt an unorthodox approach to the design of such functions. Our search space is the set of functions that possess the required properties. It is 'Booleanness' that is evolved.

In this paper, we propose a buyer authentication scheme that ensures copyright protection of multimedia objects. We show that the authentication mark is robust and recoverable in spite of a number of intentional attacks to destroy the authentication mark. The authentication mark is introduced in the wavelet space. The wavelet coefficients of the multimedia signal are randomly grouped into a number of disjoint subsets of the wavelet coefficients. However, the manipulation of the wavelet coefficient is such that the signal quality is always within the just noticeable distortion (jnd) limit. The buyer specific key survives even though we assume that a potential forger knows the proposed authentication scheme and this knowledge can be used as an attack.

We present low cost hardware architecture for implementing state-of-the-art theoretical constructions of secure Boolean functions suitable for stream ciphers. Using a pipelined architecture, we show that it is possible to implement systems which use Boolean functions of a relatively large number of variables. Our architecture is reconfigurable and provide a universal circuit for a certain class of secure Boolean functions.

In invisible digital watermarking, given an image I, a signal s/sub i/ is added, which produces a watermarked copy I/sup (i)/ = I + s/sup (i)/, such that I, I/sup (i)/ are visually indistinguishable. The addition means the element wise addition in the image matrix. This image I/sup (i)/ is given to the i-th buyer. In the detection stage, the available image (may be attacked using image processing. or cryptanalytic techniques) I/sup (#)/ is compared to the original image I and a signal s/sup (#)/ = I/sup (#)/ - I is recovered. The buyer i is suspected if s/sup (i)/ possesses significant correlation with s/sup (#)/. For successful cryptanalysis, one has to mount an attack to construct I/sup (#)/ from I/sup (i)/ (both visually indistinguishable) such that there is no significant correlation between s/sup (#)/ = I/sup (#)/ - I and s/sup (i)/. Thus, the buyer i will not be identified. To the attacker, only I/sup (i)/ is available, but I, s/sup (i)/ are not known. Thus there is no facility for the attacker to test the correlation between s/sup (i)/ and s/sup (#)/. However, the attacker needs to be convinced indirectly that the correlation between s/sup (i)/ and s/sup (#)/ has been removed. We use the CKLS scheme to demonstrate the success of the attack. The paradigm of attack needs only a single copy in contrast to the collusion attack, which needs more than one copy.

One well-known method of generating key stream sequences for stream ciphers is to combine the outputs of several linear-feedback shift registers (LFSR) using a combining Boolean function. Here we concentrate on the design of good combining Boolean functions. We provide resilient Boolean functions with currently best known nonlinearity. These functions were not known earlier and the issues related to their existence were posed as open questions in the literature. Some of the functions we construct here achieve the provable upper bound on nonlinearity for resilient Boolean functions. Our technique interlinks mathematical results with classical computer search.

Three basic properties of Boolean functions to be useful for cryptographic purposes are balancedness, high algebraic degree, and high nonlinearity. In addition, strict avalanche criteria and propagation characteristics are required for design of S-boxes. We introduce methods to modify the Patterson-Wiedemann (19983, 1990) and bent functions to achieve the above cryptographic properties. In the process, we are able to answer some open questions about Boolean functions.

In this correspondence, we establish that for odd n, the maximum nonlinearity achievable by an n-variable symmetric Boolean function is 2/sup n-1/-2/sup (n-1)///sup 2/ and characterize the set of functions which achieve this value of nonlinearity. In particular, we show that for each odd n/spl ges/3, there are exactly four possible symmetric Boolean functions achieving the nonlinearity 2/sup n-1/-2/sup (n-1)/2/.

We provide a new generalized construction method for highly nonlinear t-resilient functions, F:F/sub 2//sup n//spl rarr/ F/sub 2//sup m/. The construction is based on the use of linear error-correcting codes together with highly nonlinear multiple output functions. Given a linear [u, m, t+1] code we show that it is possible to construct n-variable, m-output, t-resilient functions with very high nonlinearity for n>u. The method provides the currently best known nonlinearity results for most of the cases.