Confidential Virtual Machines (CVMs), such as AMD SEV, offer external protection but lack a privilege hierarchy, making them vulnerable to susceptible loadable kernel modules (LKMs). Although the Integrity Measurement Architecture (IMA) checks load-time integrity, it is prone to kernel exploits. While AMD SEV-SNP’s VM Privilege Levels (VMPLs) offer hardware-enforced intra-CVM isolation, they remain underexploited for kernel protection. This paper presents VMPL-KMI, utilizing VMPLs to enforce both load-time measurement and runtime protection of LKMs. By maintaining MList in the most privileged VMPL0 and synchronizing integrity checks with memory protection, VMPL-KMI prevents tampering and eliminates Time-Of-Check-to-Time-Of-Use (TOCTTOU) vulnerabilities. To minimize the overhead, we introduce a service protocol based on the Secure VM Service Module (SVSM) standard, reducing verification to a single interaction. Experimental results demonstrate practical efficiency: 5–10% overhead for small modules (over 20% for larger ones) during loading and less than 5% during unloading.

Private Information Retrieval (PIR) allows a client to retrieve an entry from a database held by a server without leaking which entry is being requested. Symmetric PIR (SPIR) is a stronger variant of PIR with database privacy so that the client knows nothing about the database other than the retrieved entry. This work studies SPIR in the batch setting (BatchSPIR), where the client wants to retrieve multiple entries. In particular, we focus on the case of bit entries, which has important realworld applications. We set up the connection between bit-entry information retrieval and set operation, and propose a black-box construction of BatchSPIR from Private Set Intersection (PSI). By applying an efficient PSI protocol with asymmetric set sizes, we obtain our BatchSPIR protocol named BitBatSPIR. We also introduce several optimizations for the underlying PSI. These optimizations improve the efficiency of our concrete BatchSPIR construction as well as the PSI protocol. We implement BitBatSPIR and compare the performance with the state-of-the-art PIR protocol in the batch setting. Our experimental results show that BitBatSPIR not only achieves a stronger security guarantee (symmetric privacy) but also has a better performance for large databases, especially in the Wide Area Network (WAN) setting.

The online realm has witnessed a surge in the buying and selling of data, prompting the emergence of dedicated data marketplaces. These platforms cater to servers (sellers), enabling them to set prices for access to their data, and clients (buyers), who can subsequently purchase these data, thereby streamlining and facilitating such transactions. However, the current data market is primarily confronted with the following issues. Firstly, they fail to protect client privacy, presupposing that clients submit their queries in plaintext. Secondly, these models are susceptible to being impacted by malicious client behavior, for example, enabling clients to potentially engage in arbitrage activities. To address the aforementioned issues, we propose payable secure computation, a novel secure computation paradigm specifically designed for data pricing scenarios. It grants the server the ability to securely procure essential pricing information while protecting the privacy of client queries. Additionally, it fortifies the server’s privacy against potential malicious client activities. As specific applications, we have devised customized payable protocols for two distinct secure computation scenarios: Keyword Private Information Retrieval (KPIR) and Private Set Intersection (PSI). We implement our two payable protocols and compare them with the state-of-the-art related protocols that do not support pricing as a baseline. Since our payable protocols are more powerful in the data pricing setting, the experiment results show that they do not introduce much overhead over the baseline protocols. Our payable KPIR achieves the same online cost as baseline, while the setup is about 1.3−1.6× slower than it. Our payable PSI needs about 2× more communication cost than that of baseline protocol, while the runtime is 1.5−3.2× slower than it depending on the network setting.

Secure multiparty computation (MPC) protocols enable n parties, each with private inputs, to compute a given function without leaking information beyond the outputs. One of the main approaches to designing efficient MPC protocols is to use secret sharing. In general, secret sharing based MPC contains three phases: input sharing, circuit evaluation, and output recovery. If the adversary corrupts at most t parties, the protocol typically uses (t,n) threshold secret sharing to share the inputs. In this work, we consider a weaker variant of threshold secret sharing called lazy threshold secret sharing (or simply lazy sharing) and show that: Lazy sharing can serve as a viable alternative to threshold secret sharing in MPC without compromising security. Lazy sharing could be generated more efficiently than threshold secret sharing.

Abstract In truncated differential cryptanalysis of symmetric primitives, a generalized framework is to search a distinguisher concerning part of output differences, like truncated differential distribution (TDD) on certain bits (e.g. a nibble) first, and then append several rounds before and after it to recover the secret key. The logarithmic likelihood ratio statistic with respect to the TDD is usually used to distinguish guessed key bits. In this paper, we study how to improve the effect of truncated differential cryptanalysis by considering key schedules of the attacked ciphers. It turns out that for a cipher with a simple key schedule, certain guessed subkey bits may reveal information of the master key, which will help build a stronger TDD distinguisher and reduce the key recovery complexity or attack more rounds. As a result, we explore heuristic techniques to search key-recovery-friendly TDDs and construct automatic search models based on MILP. The refined methods are applied to two recent designs of symmetric primitives, WARP and Orthros, together with peculiarities of their structures as well. For WARP, after making two observations on relations between certain differences with key bits, we propose an algorithm that can find TDDs with low complexities and having potentialities to cover more rounds. Consequently, we launch key recovery attacks on 24 to 27 rounds of WARP. When it comes to Orthros, we present a two-step search algorithm to balance the number of guessed key bits and TDDs, obtaining a key recovery attack on a 7-round variant of it in the weak-key setting. Finally, we perform several verification experiments on round-reduced versions of WARP and Orthros, and the experimental results are consistent with the theoretical distributions and the analysis of generalized key recovery attack framework.

Abstract The fast correlation attack (FCA) is one of the most important cryptanalytic techniques against LFSR-based stream ciphers. In CRYPTO 2018, Todo et al. found a new property for the FCA and proposed a novel algorithm which was successfully applied to the Grain family of stream ciphers. Nevertheless, these techniques cannot be directly applied to Grain-like small state stream ciphers with keyed update, such as Plantlet, Fruit-v2 and Fruit80. In this paper, we study the security of Grain-like small state stream ciphers by the FCA. We first observe that the number of required parity-check equations can be reduced when there are multiple different parity-check equations. With exploiting the Skellam distribution, we introduce a sufficient condition to identify the correct LFSR initial state and derive a new relationship between the number and bias of the required parity-check equations. Then, a modified algorithm is presented based on this new relationship, which can recover the LFSR initial state no matter what the round key bits are. Under the condition that the LFSR initial state is known, an algorithm is given against the degraded system and to recover the NFSR state at some time instant, along with the round key bits. As cases study, we apply our cryptanalytic techniques to Plantlet, Fruit-v2 and Fruit-80. As a result, for Plantlet, our attack takes $ 2^{73.75} $ time complexity and $ 2^{73.06} $ keystream bits to recover the full 80-bit key. Regarding Fruit-v2, $ 2^{55.34} $ time complexity and $ 2^{55.62} $ keystream bits are needed to determine the secret key. As for Fruit-80, $2^{64.47}$ time complexity and $2^{62.82}$ keystream bits are required to recover the secret key. More flexible attacks can be obtained with lower data complexity at the cost of increasing the attack time. Especially, for Fruit-v2, a key recovery attack can be launched with data complexity of $2^{42.38}$ and time complexity of $2^{73.31}$. Moreover, we have implemented our attack methods on a toy version of Fruit-v2. The attack matches the expected complexities predicted by our theoretical analysis quite well, which proves the validity of our cryptanalytic techniques.

Abstract Differential-linear cryptanalysis, as the combination of differential and linear cryptanalysis, is an efficient way to attack many kinds of ciphers. Recently, various refinements to this cryptanalytic technique have been proposed, especially with good effects on ARX ciphers. In the current framework of a differential-linear attack, a cipher $E$ is often divided into three parts: a differential part $E_1$, a linear part $E_2$ and a connective part $E_m$. It is a challenging problem to deal with the connective part when building a differential-linear distinguisher, and for ARX ciphers, estimating the correlation of $ E_m $ experimentally under given input difference $\Delta _m$ and output linear mask $\Gamma _m$ is the main approach so far. In this paper, we discuss the effects of $ \Delta _{m} $ and $ \Gamma _{m} $ on the correlation of $ E_m $ for the first time. As a result, we propose a new strategy to find $\Delta _m$ and $\Gamma _m$ to build differential-linear distinguishers with high correlations for ARX ciphers based on algebraic equations derived from their round functions. For the key recovery parts of differential-linear attacks, we also find a new partitioning technique which will reduce the time complexity. Based on our new methods, we improve the differential-linear attack on 7-round Chaskey.

Due to the absence of in-enclave isolation, today's trusted execution environment (TEE), specifically Intel's Software Guard Extensions (SGX), does not have the capability to securely run different users’ tasks within a single enclave, which is required for supporting real-world services, such as an in-enclave machine learning model that classifies the data from various sources, or a microservice (e.g., data search) that performs a very small task (within sub-seconds) for a user and therefore cannot afford the resources and the delay for creating a separate enclave for each user. To address this challenge, we developedLiveries, a technique that enables lightweight, verifiable in-enclave user isolation for protecting time-sharing services. Our approach restricts an in-enclave thread's privilege when configuring an enclave, and further performs integrity check and sanitization on critical enclave data upon user switches. For this purpose, we developed a novel technique that ensures the protection of sensitive user data (e.g., session keys) even in the presence of the adversary who may have compromised the enclave. Our study shows that the new technique is lightweight (1% overhead) and verifiable (about 3200 lines of code), making a step towards assured protection of real-world in-enclave services.

De Bruijn sequences can be categorized by the weight of the truth tables of the generating functions. Among all the weight classes, the numbers of de Bruijn sequences with minimum and maximum weights draw much attention. Fredricksen and Mayhew proposed six conjectures about them, some of which have remained unsolved for about forty years. In this paper, we give the exact formulas of de Bruijn sequences with extremal weights and then prove all the conjectures in the affirmative.

We propose the concept of partial cycle structure of feedback shift registers, and study its applications in searching the characteristic functions of de Bruijn sequences. We show that, if a function generates de Bruijn sequences then its partial cycle structure does not contain cycles, and conversely, if the partial cycle structure of a function does not contain cycles then it can be extended into a function that generates de Bruijn sequences. By using this property, we analyze the low degree terms in the characteristic functions of de Bruijn sequences, and in particular give a full description of the linear terms in them. We also design an algorithm to search the characteristic functions of de Bruijn sequences which should perform better than the random search algorithm.

Nonlinear feedback shift registers (NFSRs) are used in many stream ciphers as their main building blocks. One security criterion for the design of stream ciphers is to assure the output sequences of their used NFSRs have long periods. The periodicity of those sequences are guaranteed by the NFSRs’ nonsingularity. The nonsingularity is well solved for Fibonacci NFSRs, whereas it is not for Galois ones. This paper considers the nonsingularity of Galois NFSRs. Some necessary conditions are presented, first for general Galois NFSRs, and then for submaximum and maximum length Galois NFSRs. Moreover, both particular Galois NFSRs are enumerated. All these extend the known results for Fibonacci NFSRs into Galois ones.

The purpose of this paper is to determine the 4-adic complexity of the balanced quaternary sequences of period 2(2n−1) with ideal autocorrelation defined by Jang et al. (ISIT, pp. 278-281, 2009). Results show that the 4-adic complexity of such sequences is large enough to resist the attack of the rational approximation algorithm for feedback with carry shift registers.

Abstract Nonlinear feedback shift register (NFSR) is one of the most important cryptographic primitives in lightweight cryptography. At ASIACRYPT 2010, Knellwolf et al. proposed conditional differential attack to perform a cryptanalysis on NFSR-based cryptosystems. The main idea of conditional differential attack is to restrain the propagation of the difference and obtain a detectable bias of the difference of the output bit. QUARK is a lightweight hash function family which is designed by Aumasson et al. at CHES 2010. Then the extended version of QUARK was published in Journal of Cryptology 2013. In this paper, we propose an improved conditional differential attack on QUARK. One improvement is that we propose a method to select the input difference. We could obtain a set of good input differences by this method. Another improvement is that we propose an automatic condition imposing algorithm to deal with the complicated conditions efficiently and easily. It is shown that with the improved conditional differential attack on QUARK, we can detect the bias of output difference at a higher round of QUARK. Compared to the current literature, we find a distinguisher of U-QUARK/D-QUARK/S-QUARK/C-QUARK up to 157/171/292/460 rounds with increasing 2/5/33/8 rounds respectively. We have performed the attacks on each instance of QUARK on a 3.30 GHz Intel Core i5 CPU, and all these attacks take practical complexities which have been fully verified by our experiments. As far as we know, all of these results have been the best thus far.

We study the adjacency graphs of feedback shift registers (FSRs) with affine characteristic functions. We first show that, similar to the linear case, the output sequences of FSRs with affine characteristic functions also have the direct sum decompositions. The only difference from the linear case is that one component of the decomposition is a family of affine sequences, rather than linear sequences. Then, based on this fact, we give a relationship between the adjacency graphs of FSRs with affine characteristic functions and the generalized adjacency graphs of FSRs whose characteristic functions correspond to the components of the decomposition. This relationship establishes the algebraic structure of adjacency graphs and greatly simplifies the calculation of them. At last, we especially study the adjacency graph of the FSR whose characteristic function is$q_{k}(x)+1$where$q_{k}(x)$is the linear function corresponding to the polynomial$(1+x)^{k}$. We prove that for any two cycles of this FSR, the number of conjugate pairs shared by them is no more than 4 if$k$is a power of 2, and no more than 2 if$k$is not a power of 2.

De Bruijn sequences and l-sequences are defined to be the maximum-period sequences generated by feedback shift registers (FSRs) and feedback with carry shift registers (FCSRs), respectively. In this paper we give some relationships between de Bruijn sequences and l-sequences, and we propose an efficient method to generate de Bruijn sequences from l-sequences. The experimental results indicate that this method should be able to generate de Bruijn sequences of any order.

Nonlinear feedback shift registers (NFSRs) are generally classified as Fibonacci NFSRs and Galois NFSRs according to their implementation configurations. Some Galois NFSRs can be equivalent to Fibonacci ones in the sense that their sets of output sequences are equal. Finding the characterization of those equivalent NFSRs is helpful to the design of NFSR-based stream ciphers. Moreover, one of their design's security criteria is to assure their used NFSRs are nonsingular. This paper considers the Galois NFSRs with terminal bits, which have the first several bits involved only shifts and have been used in many stream ciphers such as Grain and Trivium. The paper first gives a special class of such Galois NFSRs and reveals its relation with Fibonacci ones with respect to their sets of output sequences. It then presents a necessary and sufficient condition for an n- stage Galois NFSR with terminal bit equivalent to an n-stage Fibonacci NFSR. Based on this condition, the paper enumerates those n-stage Galois NFSRs with the same terminal bit that are equivalent to a given n-stage Fibonacci NFSR. Finally, the paper gives a necessary/sufficient condition for the nonsingularity of Galois NFSRs with terminal bits.

In this paper, we study the 4-adic complexity of two classes of quaternary sequences of period$2p$with ideal autocorrelation defined by Kim et al. (ISIT, 2009). Our results show that the 4-adic complexity of these two kinds of quaternary sequences is large enough to resist the attack of the rational approximation algorithm.

Abstract In this paper, we greatly increase the number of impossible differentials for SIMON and SIMECK by eliminating the 1-bit constraint in input/output difference, which is the precondition to ameliorate the complexity of attacks. We propose an algorithm which can greatly reduce the searching complexity to find such trails efficiently since the search space exponentially expands to find impossible differentials with multiple active bits. There is another situation leading to the contradiction in impossible differentials except for miss-in-the-middle. We show how the contradiction happens and conclude the precondition of it defined as miss-from-the-middle. It makes our results more comprehensive by applying these two approach simultaneously. This paper gives for the first time impossible differential characteristics with multiple active bits for SIMON and SIMECK, leading to a great increase in the number. The results can be verified not only by covering the state-of-art, but also by the MILP model.

We study the cross-join pairs in the cycles of linear feedback shift registers whose characteristic polynomials are of the form$l(x) = p_{1}(x)p_{2}(x)\cdots p_{k}(x)$, where$p_{i}(x), 1\leq i\leq k$are primitive polynomials of coprime degrees. Firstly, we use Coppersmithet al.’sgenerating function theory to derive the lower and upper bounds for the number of cross-join pairs. Then we design an algorithm to generate these cross-join pairs. The algorithm requires a preparatory phase which costs$O(2^{n'})$time where$n'$is the largest degree of$p_{i}(x), 1\leq i\leq k$, and after that it costs only$O(n^{3})$time to generate one cross-join pair where$n$is the degree of$l(x)$. We also consider a special class of cross-join pairs, for which the preparatory phase costs only$O(2^{n''})$time where$n''$is the second-largest degree of$p_{i}(x), 1\leq i\leq k$. The number of these special cross-join pairs is about$\frac {1}{12}2^{2n-n'}$. We present some experimental results, which validate our analysis and demonstrate the efficiencies of the algorithms. These cross-join pairs can be used in the cross-joining method to construct de Bruijn sequences.

In this paper, we analyze the weight class distribution of de Bruijn sequences. The main tool we use is the generating function theory, proposed recently by Coppersmith et al. By analyzing the weights of cycles generated by the pure circulating register, we give explicit formulas for the numbers of de Bruijn sequences in the extremal weight classes. Moreover, we use these formulas to prove some conjectures proposed by Fredricksen and Mayhew, which seems have been opened for a long time. In addition to these theoretical results, some experimental results are also provided.

Abstract Efficient key revocation in Identity-based Encryption (IBE) has been a both fundamental and critical problem when deploying an IBE system in practice. Boneh and Franklin proposed the first revocable IBE (RIBE) scheme where the size of key updates is linear in the number of users. Then, Boldyreva, Goyal and Kumar proposed the first scalable RIBE by using the tree-based approach where the size of key updates is $O(r\log (N/r))$ and the size of every user’s long-term secret key is $O(\log N)$ with $N$ being the number of users and $r$ the number of revoked users. Recently, Qin et al. presented the notion of server-aided RIBE where the size of every user’s long-term secret key is $O(1),$ and users do not need to communicate with Key Generator Center (KGC) during every key updates. However, users must change their identities once their secret keys are revoked as they cannot decrypt ciphertexts by using their revoked secret keys. To address the above problem, we formalize the notion of RIBE with identity reuse. In our system model, users can obtain a new secret key called the reuse secret key from KGC when their secret keys are revoked. The decryption key can be derived from the reuse secret key and new key updates while it cannot be derived from the revoked secret key and the new key updates. We present a concrete construction that is secure against adaptive-ID chosen plaintext attacks and decryption key exposure attacks under the $\mathsf{ADDH}1$ and $\mathsf{DDH}2$ assumptions in the standard model. Furthermore, we extend it to server-aided RIBE scheme with identity reuse property that is more suitable for lightweight devices.

Abstract Grain is a hardware-oriented finalist in the eSTREAM Stream Cipher Project. As a particular Galois nonlinear feedback shift register (NFSR), cascade connection of two NFSRs has been used as the main building block in the Grain family of stream ciphers. Two NFSRs are said to be equivalent if their sets of output sequences are equal. Finding properties of equivalent cascade connections of two NFSRs is useful to the design of the Grain family of stream ciphers. This paper first gives some properties of feedback functions between equivalent cascade connections of two NFSRs. It then shows that a cascade connection of two NFSRs and its equivalent Galois NFSR have isomorphic state diagrams if they have the same stage number. Finally, the paper reveals that for any given cascade connection of an $m$-stage NFSR1 into an $n$-stage NFSR2, there is only another one equivalent cascade connection of an $m$-stage NFSR3 into an $n$-stage NFSR4; moreover, the feedback functions of NFSR1 and NFSR3 are dual complementary, and the feedback functions of NFSR2 and NFSR4 are complementary. As an application of this property, the paper shows that the existing Grain family of stream ciphers have used the ones with lower cost of hardware implementations between their own two equivalent cascade connections, confirming their good design criteria.

For locally repairable codes (LRCs), Cadambe and Mazumdar derived the first field-dependent parameter bound, known as the C-M bound. However, the C-M bound depends on an undetermined parameter kopt(q)(n, d). In this paper, a sphere-packing approach is developed for upper bounding the parameter k for [n, k, d] linear LRCs with locality r. When restricted to the binary field, three upper bounds (i.e., Bound A, Bound B, and Bound C) are derived in an explicit form. More specifically, Bound A holds under the hypothesis that the local repair groups are disjoint and of equal size. Comparing with previous bounds obtained under the same hypothesis, Bound A either covers them as special cases or has an advantage due to its explicit form. Then, the hypothesis is removed in Bound B and Bound C. As the price for explicit form, Bound B specially holds for d ≥ 5 and Bound C for r = 2. Through specific comparisons, we show that Bound B and Bound C both tend to outperform the C-M bound, as n goes large. Moreover, a family of binary linear LRCs with d ≥ 6 attaining Bound B are constructed and later extended to a wider range of parameters by a shortening technique. Lastly, most of the bounds and constructions are extended to q-ary LRCs.

In this paper, we present HYPERRACE, an LLVM-based tool for instrumenting SGX enclave programs to eradicate all side-channel threats due to Hyper-Threading. HYPERRACE creates a shadow thread for each enclave thread and asks the underlying untrusted operating system to schedule both threads on the same physical core whenever enclave code is invoked, so that Hyper-Threading side channels are closed completely. Without placing additional trust in the operating system's CPU scheduler, HYPERRACE conducts a physical-core co-location test: it first constructs a communication channel between the threads using a shared variable inside the enclave and then measures the communication speed to verify that the communication indeed takes place in the shared L1 data cache-a strong indicator of physical-core co-location. The key novelty of the work is the measurement of communication speed without a trustworthy clock; instead, relative time measurements are taken via contrived data races on the shared variable. It is worth noting that the emphasis of HYPERRACE's defense against Hyper-Threading side channels is because they are open research problems. In fact, HYPERRACE also detects the occurrence of exception-or interrupt-based side channels, the solution.s of which have been studied by several prior works.

Fault attack is one of the most efficient side channel attacks and has attracted much attention in recent public cryptographic literatures. In this work, we introduce a fault attack on the authenticated cipher ACORN v3. Our attack is done under the assumption that a fault is injected into an initial state of ACORN v3 randomly, and contains two main steps: fault locating and equation solving. At the first step, we introduce concepts of unique set and non-unique set, where differential strings belonging to unique sets can determine the fault location uniquely. For strings belonging to non-unique sets, we use some strategies to increase the probability of determining the fault location uniquely to almost 1. At the second step, we demonstrate several ways of retrieving equations, and then obtain the initial state by solving equations with the guess-and-determine method. With n fault experiments, we can recover the initial state with time complexity c⋅2146.5−3.52⋅n⁠, where c is the time complexity of solving linear equations and 26 <n< 43⁠. We also apply the attack to ACORN v2, which shows that the changes from ACORN v2 to ACORN v3 have reduced the security margin of this algorithm against the differential fault attack.

Since proposed by the National Security Agency in June 2013, two lightweight block ciphers‐SIMON and SPECK have attracted the attention of cryptographers from all over the world. At CHES 2015, Simeck, a new block cipher inspired from both SIMON and SPECK is proposed, which is more compact and efficient. However, the security evaluation on Simeck against zero‐correlation linear cryptanalysis seems missing from the specification. The main focus of this study is to fill this gap and evaluate the security level of Simeck against zero‐correlation linear cryptanalysis. According to the authors' study, 11‐, 13‐ and 15‐round zero‐correlation linear distinguishers on Simeck32/48/64 are proposed, respectively, then zero‐correlation linear cryptanalysis on 21‐, 24‐, 28‐round Simeck32/48/64 are first proposed. As far as they know, for Simeck32, their result is the best result up to date.

A nonlinear feedback shift register (NFSR) of n-stage is called irreducible if, the family of output sequences of any NFSR of stage less than $n$ is not included in that of the NFSR. Tian and Qi in this paper [IEEE-IT, 2013(6),4006-4012] gave a lower bound on the density of irreducible NFSRs. In this paper, we improve their lower bound and also give an upper bound on the density of irreducible NFSRs. Moreover, the gap between our upper and lower bounds is less than 0.04.

We study the problem of constructing De Bruijn sequences by joining cycles of linear feedback shift registers (LFSRs) with reducible characteristic polynomials. The main difficulty for joining cycles is to find the location of conjugate pairs between cycles, and the distribution of conjugate pairs in cycles is defined to be adjacency graphs. Let$l(x)$be a characteristic polynomial, and$l(x)=l_{1}(x)l_{2}(x)\cdots l_{r}(x)$be a decomposition of$l(x)$into pairwise co-prime factors. First, we show a connection between the adjacency graph of$\mathrm {FSR}(l(x))$and the association graphs of$\mathrm {FSR}(l_{i}(x))$,$1\leq i\leq r$. By this connection, the problem of determining the adjacency graph of$\mathrm {FSR}(l(x))$is decomposed to the problem of determining the association graphs of$\mathrm {FSR}(l_{i}(x))$,$1\leq i\leq r$, which is much easier to handle. Then, we study the association graphs of LFSRs with irreducible characteristic polynomials and give a relationship between these association graphs and the cyclotomic numbers over finite fields. At last, as an application of these results, we explicitly determine the adjacency graphs of some LFSRs and show that our results cover the previous ones.

Grain is one of three hardware-oriented finalists of the eSTREAM Project. A nonlinear feedback shift register (NFSR) in Grain-like structure is a cascade connection of a linear feedback shift register (LFSR) into an NFSR, in which the characteristic polynomial of the LFSR is primitive and the feedback function of the NFSR is nonsingular. In 2011 Hu and Gong pointed out that the period of the sequence generated by an NFSR in Grain-like structure is a multiple of the period of the sequence generated by its LFSR if the initial state of the LFSR is nonzero. Meanwhile, they proposed an open problem: for fixed feedback functions of an NFSR and an LFSR, determine whether the sequences generated by the NFSR in Grain-like structure can achieve the minimum period, i.e., the period of the LFSR, when the initial state of the LFSR is nonzero, and if they can achieve, provide at least one pair of the initial states of the NFSR and LFSR. Clearly, from a security point of view, it is not preferable if the sequences generated by an NFSR in Grain-like structure achieve the minimum period. This paper converts the open problem into a problem of solving an integer equation with respect to two unknown integers that uniquely correspond to the initial states of the NFSR and LFSR, by viewing the NFSR as a Boolean control network. Based on the integer equation, this paper shows that for any given initial state of an n-stage NFSR and any given nonzero initial state of an m-stage LFSR, the probability that the sequence generated by the NFSR in Grain-like structure achieves the minimum period 2m-1 is at most 2-n. This implies that the probability of the cascade connection used in Grain achieving the minimum period is very small.

For binary [n, k, d] linear locally repairable codes (LRCs), two new upper bounds on k are derived. The first one applies to LRCs with disjoint local repair groups, for general values of n, d and locality r, containing some previously known bounds as special cases. The second one is based on solving an optimization problem and applies to LRCs with arbitrary structure of local repair groups. Particularly, an explicit bound is derived from the second bound when d ≥ 5. A specific comparison shows this explicit bound outperforms the Cadambe-Mazumdar bound for 5 ≤ d ≤ 8 and large values of n. Moreover, a construction of binary linear LRCs with d ≥ 6 attaining our second bound is provided.

In the past decade, the researchers paid more attention to the cheating problem in visual cryptography (VC) so that many cheating prevention visual cryptography schemes (CPVCS) have been proposed. In this paper, the authors propose a novel method, which first makes use of Latin square to prevent cheating in VC. Latin squares are utilised to guide the choosing of authentication regions in different rows and columns of each divided block of the shares, which ensures that the choosing of authentication regions is both random and uniform. Without pixel expansion, the new method provides random regions authentication in each divided block of all shares. What is important is that the proposed method is applicable to both ( k , n )‐deterministic visual cryptography scheme (( k , n )‐DVCS) and ( k , n )‐probabilistic visual cryptography scheme (( k , n )‐PVCS). Experimental results and properties analysis are given to show the effectiveness of the proposed method.

Fault attack is an efficient cryptanalysis method against cipher implementations and has attracted a lot of attention in recent public cryptographic literatures. In this work we introduce a fault attack on the CAESAR candidate ACORN v2. Our attack is done under the assumption of random fault injection into an initial state of ACORN v2 and contains two main steps: fault locating and equation solving. At the first step, we first present a fundamental fault locating method, which uses 99-bit output keystream to determine the fault injected location with probability 97.08% . And then several improvements are provided, which can further increase the probability of fault locating to almost 1. As for the system of equations retrieved at the first step, we give two solving methods at the second step, that is, linearization and guess-and-determine. The time complexity of our attack is not larger than c·2179.19-1.76N at worst, where N is the number of fault injections such that 31≤N≤88 and c is the time complexity of solving linear equations. Our attack provides some insights into the diffusion ability of such compact stream ciphers.

We consider the adjacency graphs of the linear feedback shift registers (LFSRs) with characteristic polynomials of the form$l(x)p(x)$, where$l(x)$is a polynomial of small degree and$p(x)$is a primitive polynomial. It is shown that their adjacency graphs are closely related to the association graph of$l(x)$and the cyclotomic numbers over finite fields. By using this connection, we give a unified method to determine their adjacency graphs. As an application of the method, we explicitly calculate the adjacency graphs of LFSRs with the characteristic polynomials of the form$(1+x+x^{3}+x^{4})p(x)$, and construct a large class of De Bruijn sequences from them.

In sparse representation based face recognition systems, the dictionary is assumed to be trained using well-controlled face images. Many classic and contemporary face recognition algorithms work well under the assumption, but degrade sharply when they are used in a real recognition system. This is mostly due to the fact that, in real-world scenarios, the training faces often appear to be loosely controlled, which are with different poses, occlusions and lighting conditions. In this paper, we propose a method to simultaneously handle the difficulties mentioned above. Our method eliminates the pose ambiguity and the effect of occlusion and illumination by imposing spatial and temporal structure constraints, respectively. Experimental results on both synthetic and real data demonstrate the efficacy of our proposed method.

An (r, t)-locally repairable code satisfies a property that the value at each coordinate can be recovered from t disjoint repair sets each containing at most r other coordinates. This property is extremely useful in distributed storage systems for hot data. In this paper, we propose two constructions of (r, t)-LRCs. The first one is a cyclic code of which the parity check polynomial is closely related to the trace function over finite fields. This code can achieve high availability and large minimum distance. The second one is based on the inclusion matrix of linear subspaces in Fqm. For some specific parameters, we prove that its information rate is always higher than r over r+t which was conjectured to be near to the optimal rate for (r, t)-LRCs (A. Wang and Z. Zhang, ISIT 2015). By shortening this code in a specially designed way, we obtain (r, t)-LRCs with more desirable locality r at a slight expense of information rate.

Abstract In this work, we generalize the paradigm of the hash proof system (HPS) proposed by Cramer and Shoup (EUROCRYPT 2002). In the center of our generalization, we lift a subset membership problem to a distribution‐distinguishing problem. Our generalized HPS clarifies and encompasses all the known public‐key encryption (PKE) schemes that essentially implement the idea of an HPS. Moreover, besides the existing smoothness property, we introduce an additional property named anonymity for HPS. As a natural application, we consider anonymity for PKE in the presence of key leakage and provide a generic construction of leakage‐resilient anonymous PKE from an anonymous HPS. We then extend our generalization to the identity‐based setting. Concretely, we generalize the paradigm of the identity‐based HPS (IB‐HPS) proposed by Boneh et al. (FOCS 2007) and Alwen et al. (EUROCRYPT 2010) and introduce anonymity for it. As an interesting application of the anonymous IB‐HPS, we consider security for PKE with keyword search (PEKS) in the presence of token leakage and provide a generic construction of leakage‐resilient secure PEKS from leakage‐resilient anonymous identity‐based encryption, which in turn is based on anonymous IB‐HPS. Copyright © 2013 John Wiley & Sons, Ltd.

Driven stable nonlinear feedback shift registers (NFSRs) with inputs are not only able to limit error propagations in convolutional decoders, but also helpful to analyze the period properties of sequences generated by a cascade connection of NFSRs in stream ciphers. An NFSR is driven stable if and only if the reachable set is a subset of the basin. Due to lack of efficient algebraic tools, the driven stability of NFSRs with inputs has been much less studied. This paper continues to address this research using a Boolean control network approach. Viewing an NFSR with input as a Boolean control network, we first give its Boolean control network representation, which is characterized with a state transition matrix. Some properties of the state transition matrix are then provided. Based on these, explicit forms are given for the reachable set and the set of basin. Two algorithms for obtaining both the sets are provided as well. Compared with the exhaustive search and the existing state operator method, the Boolean control network approach requires lower computational complexity for those NFSRs with their stages greater than 1.

In this paper, we describe a sub-maximal degree monomial test and propose a heuristic algorithm for searching favourable cubes, for testing Boolean functions formed by stream ciphers. We apply them to Trivium, and mount a distinguisher on Trivium reduced to 839 rounds with 237complexity, which is so far the best distinguisher on reduced Trivium.

In this paper, we for the first time construct three cubic rotation symmetric bent functions in 2k+3, k ≥ 0, variables. Our work solves the open problem left by Gao et al. (IEEE TIT 58(7): 4908–4913, 2012).

We introduce and study dual functions of generalized Boolean bent functions over ℤ4, i.e., functions from F2-vector spaces to ℤ4whose Fourier transforms have constant magnitudes. For a special class of generalized Boolean bent functions with even number of variables constructed from a class of quadratic binary bent functions in polynomial forms proposed by the first author, we explicitly determine their dual functions by explicitly determining duals of these binary bent functions.

In this paper, we investigate on constructing cryptographically significant Boolean functions with n variables based on decompositions of the multiplicative group of the finite field F2nof the form F2n* = U × V, where U and V are cyclic subgroups of F2n* satisfying (|U|, |V|) = 1. For positive integers s, m and n = 2sm, we obtain classes of unbalanced functions with optimal algebraic immunity in the cases |U| = 2m+ 1, |V| = (2n-1)/(2m+1) and |U| = 2m-1, |V| = (2n-1)/(2m-1), respectively, where in the latter case the optimal algebraic immunity is based on correctness of the Tu-Deng conjecture. Functions belonging to both classes can be modified to be balanced ones with (potentially) optimal algebraic immunity and optimal algebraic degree, and computer experiments show that they also have high nonlinearity and good immunity against fast algebraic attacks. As by-products, variants of the Tu-Deng conjecture and combinatorial results on binary strings in analogy to it are also obtained.

Face clustering is a key component either in image managements or video analysis. Wild human faces vary with the poses, expressions, and illumination changes. All kinds of noises, like block occlusions, random pixel corruptions, and various disguises may also destroy the consistency of faces referring to the same person. This motivates us to develop a robust face clustering algorithm that is less sensitive to these noises. To retain the underlying structured information within facial images, we use tensors to represent faces, and then accomplish the clustering task based on the tensor data. The proposed algorithm is called robust tensor clustering (RTC), which firstly finds a lower-rank approximation of the original tensor data using a L1 norm optimization function. Because L1 norm does not exaggerate the effect of noises compared with L2 norm, the minimization of the L1 norm approximation function makes RTC robust. Then, we compute high-order singular value decomposition of this approximate tensor to obtain the final clustering results. Different from traditional algorithms solving the approximation function with a greedy strategy, we utilize a nongreedy strategy to obtain a better solution. Experiments conducted on the benchmark facial datasets and gait sequences demonstrate that RTC has better performance than the state-of-the-art clustering algorithms and is more robust to noises.

The generalized Hamming weights dr(C) of a linear code C are a natural generalization of the minimum Hamming distance d(C)[=d1(C)] and have become an important research object in coding theory since Wei's originary work in 1991. In this paper, two general formulas on d(C) for irreducible cyclic codes are presented using Gauss sums and the weight hierarchy {d1(C), d2(C), ... , dk(C)} (k= dim C) is completely determined for several cases.

In this paper, it is proven that a family of 2k-variable Boolean functions, including the function recently constructed by Tang et al. [IEEE TIT 59(1): 653-664, 2013], are almost perfect algebraic immune for any integer k ≥ 3. More exactly, they achieve optimal algebraic immunity and almost perfect immunity to fast algebraic attacks. The functions of such family are balanced and have optimal algebraic degree. A lower bound on their nonlinearity is obtained based on the work of Tang et al., which is better than that of Carlet-Feng function. It is also checked for 3 ≤ k ≤ 9 that the exact nonlinearity of such functions is very good, which is slightly smaller than that of Carlet-Feng function, and some functions of this family even have a slightly larger nonlinearity than Tang et al.'s function. To sum up, among the known functions with provable good immunity against fast algebraic attacks, the functions of this family make a trade-off between the exact value and the lower bound of nonlinearity.

We propose a general approach to construct cryptographic significant Boolean functions of (r + 1)m variables based on the additive decomposition F2rm× F2mof the finite field F2(r+1)m, where r ≥ 1 is odd and m ≥ 3. A class of unbalanced functions is constructed first via this approach, which coincides with a variant of the unbalanced class of generalized Tu-Deng functions in the case r = 1. Functions belonging to this class have high algebraic degree, but their algebraic immunity does not exceed m, which is impossible to be optimal when r > 1. By modifying these unbalanced functions, we obtain a class of balanced functions which have optimal algebraic degree and high nonlinearity (shown by a lower bound we prove). These functions have optimal algebraic immunity provided a combinatorial conjecture on binary strings which generalizes the Tu-Deng conjecture is true. Computer investigations show that, at least for small values of number of variables, functions from this class also behave well against fast algebraic attacks.

In this paper, we introduce a general paradigm called identity-based extractable hash proof system (IB-EHPS), which is an extension of extractable hash proof system (EHPS) proposed by Wee (CRYPTO'10). We show how to construct identity-based key encapsulation mechanism (IB-KEM) from IB-EHPS in a simple and modular fashion. Our construction provides a generic method of building and interpreting CCA-secure IB-KEMs based on computational assumptions. As instantiations, we realize IB-EHPS from the bilinear Diffie–Hellman assumption and the modified bilinear Diffie–Hellman assumption, respectively. Besides, we carefully investigate the relation between EHPS and IB-EHPS, and indicate possible refinement and generalization of EHPS.

Symmetry as an intrinsic shape property is often observed in natural objects. In this paper, we discuss how explicitly taking into account the symmetry constraint can enhance the quality of foreground object extraction. In our method, a symmetry foreground map is used to represent the symmetry structure of the image, which includes the symmetry matching magnitude and the foreground location prior. Then, the symmetry constraint model is built by introducing this symmetry structure into the graph-based segmentation function. Finally, the segmentation result is obtained via graph cuts. Our method encourages objects with symmetric parts to be consistently extracted. Moreover, our symmetry constraint model is applicable to weak symmetric objects under the part-based framework. Quantitative and qualitative experimental results on benchmark datasets demonstrate the advantages of our approach in extracting the foreground. Our method also shows improved results in segmenting objects with weak, complex symmetry properties.

Let a and b be primitive sequences over ℤ/(pe) with odd prime p and e ≥ 2. For certain compressing maps, we consider the distribution properties of compressing sequences of a and b, and prove that a = b if the compressing sequences are equal at the times t such that α(t) = k, where α is a sequence related to a. We also discuss the s-uniform distribution property of compressing sequences. For some compressing maps, we obtain that there exist different primitive sequences such that the compressing sequences are s-uniform. We also discuss that for how many elements s, compressing sequences of different primitive sequences can be s-uniform.

In this correspondence, first we give a decomposition of symmetric Boolean functions, then we show that almost all symmetric Boolean functions, including these functions with good algebraic immunity, behave badly against fast algebraic attacks. Besides, we improve the relations between algebraic degree and algebraic immunity of symmetric Boolean functions.

An accumulator based on bilinear pairings was proposed at CT-RSA'05. Here, it is first demonstrated that the security model proposed by Lan Nguyen does lead to a cryptographic accumulator that is not collision resistant. Secondly, it is shown that collision-resistance can be provided by updating the adversary model appropriately. Finally, an improvement on Nguyen's identity escrow scheme, with membership revocation based on the accumulator, by removing the trusted third party is proposed.

Deniability is a privacy property that ensures protocol participants can later deny taking part in a particular protocol run. A deniable authentication protocol enables an intended receiver to identify the source of a given message, but not prove the identity of the sender to a third party even if the intended receiver is willing to reveal his secret-key. In this paper, we present an efficient ID-based deniable authentication protocol from pairings. The proposed protocol satisfies the correctness, authentication and deniability properties.

Ring authenticated encryption has the following security requirements: semantic-security, recipient-designation, verification-dependence, verification-convertibility, recipient-ambiguity, recipient-verifiability, signer-ambiguity and signer-verifiability. Ring authenticated encryption can be used to enhance user privacy. In this paper, based on Boneh and Frankliny's ID-based encryption scheme and Zhang and Kim's ID-based ring signature scheme, we propose an ID-based ring authenticated encryption scheme. We also show that the proposed scheme satisfies the correctness property and all security requirements.

Internet Accessible Mathematical Computation (IAMC) is a distributed framework to supply mathematical computing powers over the Internet. Presented are conceptual and experimental work on the IAMC architecture, a client prototype (Dragonfly), client GUI, a server prototype (Starfish), the Mathematical Computation Protocol (MCP), mathematical data encoding, and the external compute engine interface.

In this paper, we discuss Wu's well ordering principle and theorem proving over finite fields, try to prove some theorems in the geometry over finite fields.

The structure of linear recurring m-arrays is studied. It is proved that any linear recurring m-array can be obtained by "folding" an m-sequence. The properties of translation-addition, sampling and correlation of linear recurring m-arrays are also discussed.>