Abstract Fully homomorphic encryption (FHE) enables arbitrary computations on encrypted data while preserving strong privacy guarantees. However, the high computational cost of homomorphic operations, particularly multiplication and comparisons, remains a significant bottleneck in practical applications. In this paper, we propose a novel algorithm that efficiently evaluates univariate polynomial functions under FHE, leveraging specific optimization techniques to minimize the number of required homomorphic operations. We rigorously analyze its theoretical performance and extend it to implement an optimized equality test. Our experimental results show that comparing two 32-bit values takes only 3.9 milliseconds, and for batch comparisons between 32,768 16-bit values and a single 16-bit value, the amortized overhead is reduced to 0.01 milliseconds per comparison. Furthermore, we apply this equality test to build a practical single-round keyword private information retrieval (PIR) protocol for the single-server setting. Compared to the Constant-Weight PIR (USENIX 2022), our method achieves a 4–6× reduction in computational overhead during the server’s response phase, making it a more practical solution for real-world deployments.

Popular chained Byzantine Fault Tolerant (BFT) consensus protocols adopt a pipelined paradigm to achieve efficiency. However, these protocols remain vulnerable to critical attacks, such as forking and partitioning. While the two-phase commit rule can prevent forking, it often requires complex or expensive view-change mechanisms. Moreover, our study confirms that partitioning attacks are feasible in many existing chained BFT protocols. This paper devised NunChuck, a fully two-phase chained BFT protocol that ensures linear authenticator complexity, optimistic responsiveness, and resilience to partitioning attacks. NunChuck employs a lightweight certificate-based view-change mechanism to maintain efficiency, and introduces a unified message structure that enables leaders to make progress even under partitioned network conditions. We formally prove its safety and liveness properties. Furthermore, we develop a prototype implementation in Golang and conduct extensive evaluations. The results demonstrate that NunChuck consistently outperforms HotStuff and FastHotStuff, particularly in adversarial environments, with simulated delay analysis further corroborating our experimental findings.

Impossible differential cryptanalysis and impossible polytopic cryptanalysis are among the most effective techniques for evaluating the security of block ciphers. However, previous automatic search methods for their distinguishers—dimpossible differentials and impossible polytopic transitions—neither account for the influence of the key schedule in single-key settings nor are applicable to block ciphers featuring large S-boxes, variable rotations, or key-dependent permutations. Furthermore, existing approaches fail to search for clusters of impossible differentials when all details of a block cipher are considered. In contrast to previous methods that focus solely on the propagation of differences or s-difference, we redefine impossible differentials and impossible (s+ 1)-polytopic transitions based on state propagation. This redefinition enables us to overcome the limitations inherent in earlier methodologies. Theoretically, we demonstrate that traditional definitions of impossible differentials and impossible (s+ 1)-polytopic transitions correspond to subsets of our redefined concepts, which offer broader analytical perspectives. Technically, we reformulate the automatic search model and develop an SAT-based tool to efficiently evaluate our redefined impossible differentials and impossible (s+ 1)-polytopic transitions. Building upon this foundational search method, we construct a comprehensive framework for detecting clusters of impossible differentials and impossible (s+1)-polytopic transitions. This framework not only fully incorporates the details and differential properties of block ciphers but is also applicable to those employing large S-boxes while considering the full linear layer. As a result, we derive new impossible differentials for GIFT64, PRINTcipher48/96, MISTY1, RC5-32/64/128 and SPECK, as well as new clusters of impossible differentials for SPECK, DES and ARIA. In assessing resistance against impossible differentials, we apply our method to evaluate the security of GIFT64, PRINTcipher48/96, MISTY1, SPECK, SIMON, and DES while accounting for all details of the block ciphers. Moreover, we propose acceleration strategies and apply them to evaluate the security of MISTY1 and AES-128. Notably, we prove that no 5-round impossible differentials with one active input byte and one active output byte exist for AES-128, even when considering the dependencies among three consecutive round keys. Finally, in exploring new impossible (s+1)-polytopic transition, we apply our approach to PRINTcipher48, GIFT64, RC5-32/64 and SIMON32-64, successfully yielding the corresponding distinguishers for the first time.

Homomorphic encryption (HE) is one of the leading cryptographic approaches for enabling secure outsourced computation. In untrusted computational environments, HE serves as a crucial tool for preserving data privacy. However, performing complex operations such as matrix multiplication in deep learning inference under HE remains a significant challenge.In this paper, we propose two enhancements to the state-of-the-art ciphertext matrix multiplication scheme based on bicyclic encoding. Firstly, we introduce the Seg-Hoisting algorithm, which enables simultaneous rotation of multiple ciphertexts while significantly reducing the key size. Secondly, we apply the lazy reduction strategy during ciphertext multiplication, where modulus reduction operations are deferred until after multiple multiplications are completed, thereby reducing the number of modulus reduction operations. Furthermore, we generalize existing schemes to enhance their applicability across diverse matrix dimensions and application scenarios. Through comprehensive experimental evaluation, we demonstrate that our proposed improvements yield a significant performance gain, achieving speedups ranging from 2.7× to 4.6× compared to the existing approach.

Fuzzy Private Set Intersection (FPSI) is a cryptographic protocol that extends traditional PSI to enable privacy-preserving similarity matching, allowing the receiver to learn elements from the sender’s set with "δ − close" of the receiver’s elements, computing {yj| dist(xi, yj) ≤ δ, xi∈ X, yj∈ Y } where δ is predefined threshold. However, the current state-of-the-art integer-based approach by Chakraborti et al. (USENIX’23) suffers from excessive computation overhead, large communication costs, and limited scalability, hindering practical deployment.We construct two semi-honest $\Pi _{{\text{FPSI}}}^{{\text{int}}}$ for different scenarios. Along with compact Prefix Trie preprocessing, for the balanced settings, we propose $\Pi _{{\text{FPSI}}}^{{\text{OKVS}}}$ leveraging OKVS and subVOLE. For unbalanced scenarios, we introduce $\Pi _{{\text{FPSI}}}^{{\text{HE}}}$ protocol combining optimization techniques including Paterson-Stockmeyer algorithms and multiple algorithmic improvements.We implement our protocols in C++ using 32-bit IPv4 and 128-bit IPv6 addresses across balanced and unbalanced scenarios under single-threaded LAN environment. our balanced $\Pi _{{\text{FPSI}}}^{{\text{OKVS}}}$ protocol achieves 24.7-58.4× computational speedup across all scales and 9.9× communication reduction compared to Chakraborti et al. (USENIX'23) for datasets up to 1 million addresses. For unbalanced scenarios, our $\Pi _{{\text{FPSI}}}^{{\text{HE}}}$ protocol demonstrates superior scalability, enabling mobile devices with only 4K datasets against 16 million server elements in 56.74 seconds with 22.8 MB communication, achieving 2.8-38.5× speedup over the (USENIX'23).

Abstract In this paper, we consider a secure multi-party shuffling (MPS), in which multiple participants provide private datasets and enable to obtain secret shared values of randomly permuted whole dataset while protecting the privacy of each individual input and the permutation. MPS stands as a foundational tool for the randomized algorithm, with broad utility in a large amount of domains, offering enhancements in privacy while concurrently reducing costs. And its applications encompass machine learning, secure function evaluation, and anonymous communication. Recently, Chase, Ghosh, and Poburinnaya (2020 Secret-shared shuffle. Advances in Cryptology-ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part III 26, pp. 342-372. Springer.) introduced an innovative two-party protocol known as SSS, where participants can effectively produce additive secret shares of a shuffled dataset while preserving the privacy. Indeed, this approach transforms challenge of shuffling a dataset into the task of shuffling pseudorandom values, leading to a significant enhancement in both communication and computation efficiency. We would like to generalize the SSS in Chase, Ghosh, and Poburinnaya (2020 Secret-shared shuffle. Advances in Cryptology-ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part III 26, pp. 342-372. Springer.) to a novel multi-party variant, all while maintaining its efficiency. However, it turns out that this is not straightforward. Specifically, the communication complexity is trivially blown up about $O(m^{3}n\log n)$, where $m$ denotes the number of participants and $n$ denotes the length of message. We further reduce the cost to be linear in the number of participants. Moreover, our novel MPS operates within the preprocessing model, with the security against static semi-honest adversaries. Furthermore, our protocols rely exclusively on the oblivious transfer during the preprocessing phase and symmetric-key primitives in online phase to avoid the comparatively heavy public-key operations associated with previous MPS protocols.

Abstract Security and efficiency have always been two critical factors in the development of post-quantum digital signatures. As the best-known scheme, (Ducas et al., TCHES 2018) is SUF-CMA in QROM and has a relatively fast efficiency with many untrivial optimizations. The goal of this paper is to propose some techniques that can promote signing speed without sacrificing security. We first propose the pre-rejection sampling technique in stage to reduce the rejections of the fourth condition, consequently resulting in some speedup in stage. To prove security, we propose the c-selected MLWE problem, a variant of MLWE that can offer the equivalent security as original MLWE. Applying these two techniques to , we obtain an advanced signature scheme with better efficiency, and without any other losses except some pre-computations. Security reduction demonstrates that our scheme is also SUF-CMA in QROM. The experimental results show that pre-rejection sampling achieves a $$47\%$$ 47 % , $$22\%$$ 22 % , and $$17\%$$ 17 % reduction in the rejection probability of the fourth condition over scheme when the parameter set corresponds to NIST’s security levels 2, 3 and 5, respectively. This type of reduction increases signing speed by approximately $$1\%$$ 1 % under the parameter set 2 of .

We introduce the LightPIR family, a new series of single-server PIR protocols with reduced overhead in terms of storage, communication, and computation. The protocols rely on a new GSW-like homomorphic cryptosystem based on the Ring Learning with Rounding (RLWR) problem and several ciphertext conversion algorithms for matrix encoding. Our RLWR-based techniques offer considerable advantages across all evaluation metrics compared to the previous state-of-the-art, the Spiral family (S&P 2022), under various database configurations. On the server, the LightPIR family simultaneously achieves a 1.2--1.8× increase in the throughput and up to a 1.4× increase in the rate while reducing the storage requirements of public parameters by 1.6--5×. For the client, the LightPIR family eliminates the Gaussian noise sampling, resulting in an average 36% reduction in query encryption time and resilience against side-channel attacks. Meanwhile, communication efficiency between the client and server is also enhanced by a reduction of up to 3.8× in query size and up to 1.8× in response size. All the optimizations indicate that our constructions are more lightweight for both the client and the server, highlighting a new practical scenario where RLWR-based schemes can showcase their advantages.

We introduce NTRU-PIR and NTRU-PIR-FREE, two single-server PIR protocols that offer new trade-offs in terms of storage, communication, and computation. Both of the protocols rely on the toolkit we developed for efficient homomorphic operations and ciphertext conversion algorithms on NTRU and an NTRU-based GSW-like scheme. Across a broad range of database configurations, NTRU-PIR simultaneously achieves a 1.5-26× reduction in public parameter size and a 1.7-4.2× increase in server throughput compared to previous counterparts. NTRU-PIR-FREE, a variant of NTRU-PIR by removing the query compression technique, eliminates the storage burden on the server. In the streaming setting, when the previous best-performing scheme Spiral-streampack(s&p 2022) reaches its highest throughput, NTRU-PIR-FREE achieves a comparable throughput with a query size of only 8 MB (compared to 30 MB for Spiralstreampack)and without requiring public parameters (compared to 125 MB for Spiralstreampack).

Abstract Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) are cryptographic protocols that offer efficient and privacy-preserving means of verifying NP language relations and have drawn considerable attention for their appealing applications, e.g., verifiable computation and anonymous payment protocol. Compared with the pre-quantum case, the practicability of this primitive in the post-quantum setting is still unsatisfactory, especially for the space complexity. To tackle this issue, this work seeks to enhance the efficiency and compactness of lattice-based zk-SNARKs, including proof length and common reference string (CRS) length. In this paper, we develop the framework of square span program-based SNARKs and design new zk-SNARKs over cyclotomic rings. Compared with previous works, our construction is without parallel repetition and achieves shorter proof and CRS lengths than previous lattice-based zk-SNARK schemes. Particularly, the proof length of our scheme is around $$23.3\%$$ 23.3 % smaller than the recent shortest lattice-based zk-SNARKs by Ishai et al. (in: Proceedings of the 2021 ACM SIGSAC conference on computer and communications security, pp 212–234, 2021), and the CRS length is $$3.6\times$$ 3.6 × smaller. Our constructions follow the framework of Gennaro et al. (in: Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pp 556–573, 2018), and adapt it to the ring setting by slightly modifying the knowledge assumptions. We develop concretely small constructions by using module-switching and key-switching procedures in a novel way.

Secure aggregation becomes a major solution to providing privacy for federated learning. Secure aggregation for mobile devices typically relies on Shamir secret sharing (SSS) to achieve dropout robustness, but limits the system’s corruption and dropout tolerance. Although Prio+, a state-of-the-art method utilizing two non-colluding servers, avoids such limitations, its effectiveness is only against honest-but-curious servers. Thus, this paper presents a novel secure aggregation protocol in the malicious model. The proposed protocol uses a non-colluding server and initiator to achieve almost full (up ton-2) corruption and dropout tolerance, and exploits our discrete-logarithm (DL) extractable and equivocable commitment scheme to achieve malicious security. The proposed protocol’s security is proven in two models: malicious users colluding with the server and malicious users colluding with the initiator. Finally, a prototype of the developed protocol is implemented, with the experimental results demonstrating that our protocol is efficient and suitable for both cross-device and cross-silo federated learning scenarios. Compared with the sum protocol of Prio+, the proposed protocol achieves malicious security with affordable additional overhead, i.e., 4.8 to 6.1 times more computation cost and 2.8 to 2.9 times more communication cost for a single user.

With the growing practical applications of fully homomorphic encryption (FHE), secure multi-party computation (MPC), and zero-knowledge proofs (ZK), there has been an increasing need to design and analyze symmetric primitives that have low multiplication complexity and depth. In this paper, we propose a permutation constructed upon a 4-round nonlinear feedback resistor over$ \mathbb {F}_{q}^{4}$. Our proposed permutation has a multiplication depth of 2 and a multiplication complexity of 4. Significantly, its maximum differential/linear probability is bounded by$q^{-2}$. Based on this nonlinear function, we propose a new family of block ciphers over$ \mathbb {F}_{q}^{16}$called$ \mathsf {YuX}$, whose decryption circuit is highly efficient for FHE evaluation. We further provide specific instantiations, denoted as$ \mathsf {Yu_{2}X}$and$ \mathsf {Yu_{\mathrm {p}}X}$, wherein$q$takes the form of either$2^{n}$or a prime$p$, respectively. Furthermore, we conduct a comprehensive security analysis of$ \mathsf {YuX}$within certain parameters against various cryptanalysis methods employing automatic analysis tools, including the differential attack, linear attack, impossible differential attack, zero-correlation attack, and integral attack, as well as Gröbner basis and linearization attacks. Our research indicates that$ \mathsf {YuX}$maintains a robust security margin against those attacks. Finally, we present a detailed implementation of$ \mathsf {Yu_{2}X}$and$ \mathsf {Yu_{\mathrm {p}}X}$employing the BGV homomorphic encryption scheme. In comparison to ciphers over a field of characteristic 2, the outcomes evince that$ \mathsf {Yu_{2}X}$-8 (over$ \mathbb {F}_{2^{8}}^{16}$) and$ \mathsf {Yu_{2}X}$-16 (over$ \mathbb {F}_{2^{16}}^{16}$) achieve remarkably competitive throughputs, boasting performance approximately 12 times, 17 times, and 9 times superior to AES-128, CHAGHRI, and LowMC-128 (under 128-bit security), respectively. Furthermore, when juxtaposed with ciphers over a field of characteristic$p$, the outcomes affirm that the throughput of$ \mathsf {Yu_{\mathrm {p}}X}$-65537 (over$ \mathbb {F}_{65537}^{16}$) retains considerable competitiveness, registering an approximate fivefold enhancement relative to HERA. Evidently,$ \mathsf {YuX}$exhibits superior throughput compared to a majority of symmetric ciphers within this category.

Abstract Lightweight block ciphers are the essential encryption algorithm for devices with limited resources. Its goal is to ensure the security of data transmission through resource-constrained devices. Impossible differential cryptanalysis is one of the most effective cryptanalysis on block ciphers, and assessing the ability of resisting this attack is a basic design criterion. Shadow is a lightweight block cipher proposed by Guo et al. (IEEE Internet Things J 8(16):13014–13023, 2021). It utilizes a combination of ARX operations and generalized Feistel structure to overcome the weakness of the traditional Feistel structure that only diffuses half in one round. In this paper, we focus on the differential property of Shadow and its security against impossible differential cryptanalysis. First, we use the SAT method to automatically search for a full-round impossible differential distinguisher of Shadow-32. Then, based on the experimental results, we prove that Shadow has a differential property with probability 1 based on the propagation of the state. Further, we can obtain an impossible differential distinguisher for an arbitrary number of rounds of Shadow. Finally, we perform a full key recovery attack on the full-round Shadow-32 and Shadow-64. Both experimentally and theoretically, our results indicate that Shadow is critically flawed, and regardless of the security strength of the internal components and the number of rounds applied, the overall cipher remains vulnerable to impossible differential cryptanalysis.

We propose FBSChain, a faster blockchain sharding protocol based on quorum-based BFT algorithm (running as sharding consensus) and use a vertical committee structure to assist in the decoupling of transaction confirmation and block generation. We utilize a set of clients to drive all these related processes. In addition, we deploy an improved common-coin scheme without any private setup to generate the randomness for reconfiguration. The protocol can perform better with less computational and communication costs and improve system scalability without compromising security performance.

Abstract The division property method is a technique for automatic searching integral distinguishers on block ciphers. Previous methods only use word-based division property to search integral distinguishers for block ciphers with large S-boxes. Since using bit-based division property may find longer integral distinguishers than word-based division property, we propose a method to automatically search the integral distinguishers based on bit-based division property for block ciphers with large S-boxes. To achieve this goal, we propose a new division property propagation table for S-boxes. Theoretically, we prove that using both the new table and the traditional method to describe the bit-based division property propagation rule of S-box will lead to the same integral distinguishers. Technically, we design a mixed-integer linear programming-based tool to search the integral distinguisher based on the new table, which helps to search new integral distinguishers for block ciphers with large S-boxes efficiently. As a result, we apply our tool to derive new integral distinguishers and get the tight bound on the rounds that no integral distinguishers exist for ICEBERG, KHAZAD, Camellia, CS-Cipher, ITUbee and SMS4. Besides, to show the availability of our integral distinguishers, we form the present best five-round and the first six-round integral attack for ICEBERG as an example.

Abstract Data is a kind of important asset in the digital economy and is driving the rise of data markets. Meanwhile, data markets promote data trading efficiently and improve the utilization of data. However, several challenges about data trading need to be addressed. Here, we resolve these challenges via our blockchain-based fair and decentralized data trading model. Disputes about data correctness is settled by the decentralized arbitration mechanism in our model. To ensure the fairness of data trading, we integrate a sale contract and a deterministic public-key encryption algorithm. The decentralization feature of blockchain cuts off the single-point failure for the data trading platform. In addition, we prove that the proposed protocol achieves the desirable security properties that a secure data trading protocol should have. Moreover, utilizing the smart contract in Solidity and program in Java, we implement our model and then evaluate its performance.

Abstract This paper investigates the security of counter mode encryption with authentication tag (COMET), one of the 32 second-round candidates in National Institute of Standards and Technology’s lightweight cryptography standardization process, against differential cryptanalysis. CHAM-64/128 is a block cipher chosen as one of the underlying block ciphers in COMET for hardware-oriented applications, and a differential characteristic with a high probability for CHAM-64/128 is useful for forgery attacks on COMET. However, we find that the optimal $\mathbf{39}$-round differential characteristic for CHAM-64/128 proposed by Roh et al., which is the longest differential characteristic of CHAM-64/128, is invalid. Then, we propose a new method of distinguishing an $\mathbf{m}$-bit block cipher from an $\mathbf{m}$-bit random permutation using a differential characteristic with a probability not higher than $\mathbf{2^{-m}}$. Using our method, we use two $\mathbf{39}$-round differential characteristics with a probability of $\mathbf{2^{-64}}$ for CHAM-64/128 to distinguish $\mathbf{39}$-round-reduced CHAM-64/128 from a $\mathbf{64}$-bit random permutation, respectively. Furthermore, we refine the probabilities of two differentials with the same input and output differential masks as the two $\mathbf{39}$-round differential characteristics, respectively. Finally, we present the first forgery attacks on COMET with the two differentials without using weak keys. Our forgery attacks follow the nonce-misuse scenario. It should be noticed that this attack does not invalidate the security claims of the designers.

Abstract SIMON is one of the lightweight block ciphers designed by the National Security Agency in 2013, and a technical report including security analysis was published by the design team nearly 4 years later. As for the linear attack, it is claimed that ‘the single‐path probabilities (and linear correlations) dip below 2 −block size for 12, 16, 20, 29, and 38 rounds for SIMON32, 48, 64, 96, and 128, respectively’. However, the design team does not show details on how to get the result and there are also no published papers verified the result yet. In the present paper, an upper bound of squared correlation of SIMON‐like functions is given. As an important application of this bound, how to find optimal linear characteristics of SIMON and SIMECK under the Markov assumption with Matsui's branch‐and‐bound algorithm is shown. The authors’ results confirm the claim of the design team. Furthermore, the best‐known linear‐hull distinguishers for SIMON and SIMECK is also given.

In this paper, we propose an automatic tool to search for optimal differential and linear trails in ARX ciphers. It’s shown that a modulo addition can be divided into sequential small modulo additions with carry bit, which turns an ARX cipher into an S-box-like cipher. From this insight, we introduce the concepts of carry-bit-dependent difference distribution table (CDDT) and carry-bit-dependent linear approximation table (CLAT). Based on them, we give efficient methods to trace all possible output differences and linear masks of a big modulo addition, with returning their differential probabilities and linear correlations simultaneously. Then an adapted Matsui’s algorithm is introduced, which can find the optimal differential and linear trails in ARX ciphers. Besides, the superiority of our tool’s potency is also confirmed by experimental results for round-reduced versions of HIGHT and SPECK. More specifically, we find the optimal differential trails for up to 10 rounds of HIGHT, reported for the first time. We also find the optimal differential trails for 10, 12, 16, 8 and 8 rounds of SPECK32/48/64/96/128, and report the provably optimal differential trails for SPECK48 and SPECK64 for the first time. The optimal linear trails for up to 9 rounds of HIGHT are reported for the first time, and the optimal linear trails for 22, 13, 15, 9 and 9 rounds of SPECK32/48/64/96/128 are also found respectively. These results evaluate the security of HIGHT and SPECK against differential and linear cryptanalysis. Also, our tool is useful to estimate the security in the design of ARX ciphers.

Ciphertext-policy attribute-based encryption (CP- ABE) with verifiable outsourced decryption is a mechanism for secure fine-grained access control over encrypted data, and it is suitable for cloud computing applications. However, there exists a risk in CP-ABE with verifiable outsourced decryption that can lead to serious consequences and may limit its wide applications: the key generation center may have misbehavior. In this paper, we present BSA, the blockchain-based specification for ABE to mitigate this risk. We introduce the specification to regulate the data access control and a proof mechanism to supervise whether the key generation center has misbehavior. Also, we can provide decentralized and automated incentives with BSA by smart contracts and blockchain-based consensus.

Abstract For secure data sharing in the public cloud, attribute‐based encryption was introduced to simultaneously achieve data confidentiality and fine‐grained access control. In order to update access control of the attribute‐based encrypted data from delegation, attribute‐based proxy re‐encryption (AB‐PRE) was proposed accordingly. Most previous AB‐PRE schemes require that the proxy executes the re‐encryption honestly. However, the public cloud as a proxy may not meet the requirement because the encrypted data are delegated to the public cloud and out of control for data owners. In this paper, we introduce verifiability for AB‐PRE to check the correctness of the re‐encryption executed by the proxy. By introducing a commitment scheme and a key derivation function, we propose a generic construction of unidirectional single‐hop AB‐PRE with verifiable re‐encryption (AB‐VPRE) for both key‐policy and ciphertext‐policy settings, and the access structure can be monotonic and non‐monotonic. We prove the security and the verification soundness of our constructed AB‐VPRE scheme in the standard model and provide three instantiations. Compared with previous work on AB‐PRE, our proposed AB‐VPRE schemes require less computation and can efficiently detect the malicious behaviors of the proxy. Copyright © 2016 John Wiley & Sons, Ltd.

Carlet and colleagues conjectured that for any almost bent (AB) functionF, there exists a linear functionLsuch thatF+Lis a permutation. Budaghyan and colleagues found a new class of AB functions which is extended affine (EA)-inequivalent to any power functions and can also serve as a counterexample for the conjecture. They checked with the help of a computer that there are no linear functionsLonF25such thatx2i+1+(x2i+x) Tr (x2i+1+x)+L(x) is a permutation. In this paper, we prove that there are no permutations EA-equivalent to the AB functionx2i+1+(x2i+x) Tr (x2i+1+x) onF22m+1for anym≥ 2 and there are no permutations EA-equivalent to the APN functionx2i+1+(x2i+x+1) Tr (x2i+1) on \BBF22mform≥ 2 either. Furthermore, we present some results about characterizations of permutation polynomials of the typeL(x2i+1)+L'(x) on \BBF22m, which is essential in the construction of functions Carlet-Charpin-Zinoviev-equivalent to the Gold functions. We obtain all the linear functionsL(x) such thatx+L(x2i+1) is a permutation on \BBF22mwhen |ker(L)| ≥ 22m-2.

In this paper, the authors study binomial skew polynomial ring A. We can find a Gröbner basis of a two-sided ideal (as left ideal). Thus, we solve the question 2 in [2]: Is it true that A has a decidable membership problem for finitely generated two-sided ideals?

Let K[x1,…,xn]be a polynomial ring over a field K in variables x1,…,xn, and K[y1,…,ym] be a polynomial ring over a field K in variables y1,…,ym. m n n. Let T = (t1,…,tn) be an ordered n-tuple of non-constant polynomials in K[y1,…,ym]. For any finite set F of K[x1,…,xn], let F o T be the set obtained from F by replacing xi; by ti, thus for any FeK[x1,…,xn], FoT eK[y1,…,ym]. With the above notations, Hong's main theorem [9] and the main theorem of [6] are generalized to general cases with some new proofs.