Abstract In recent years, progress in practical applications of multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZKP) motivates people to explore symmetric-key cryptographic algorithms, as well as corresponding cryptanalysis techniques (such as differential cryptanalysis, linear cryptanalysis), over finite Abelian groups or prime fields $${\mathbb {F}}_p$$ F p for large p . In this paper, we establish the links between linear cryptanalysis and differential cryptanalysis over general finite Abelian groups. As the first application, we revisit linear cryptanalysis and give general results of linear approximations over arbitrary finite Abelian groups. More precisely, we consider the linearity , which is the maximal non-trivial linear approximation, to characterize the resistance of a function against linear cryptanalysis. This thereby generalizes the work of Pott in 2004 and completes the generalization of Sidelnikov–Chabaud–Vaudenay’s bound from $${\mathbb {F}}_2^n$$ F 2 n to finite Abelian groups. As the second application, we give an exact expression for the correlation of differential-linear approximations over arbitrary finite Abelian groups ( $${\mathbb {F}}_p^n$$ F p n ) under the sole assumption that the two parts of the cipher are independent of each other. In particular, we completely generalize the differential-linear cryptanalysis from $${\mathbb {F}}_2^n$$ F 2 n to arbitrary finite Abelian groups ( $${\mathbb {F}}_p^n$$ F p n ).

With the growing number of decentralized finance (DeFi) applications, transaction fairness in blockchains has gained much research interest. As a broad concept in distributed systems and blockchains, fairness has been used in different contexts, varying from ones related to the liveness of the system to ones that focus on the received order of transactions. In this work, we revisit the fairness definitions and find that existing fairness definitions are not adapted to blockchains with multiple DApps. We then provide a more generic one calledverifiable fairness. Compared with prior definitions, our notion has two unique features: (i) it relaxes the ordering rules to apredicate; (ii) it enables users to independently verify if their transactions comply with the predicate for concrete applications. We also provide a scheme that achieves verifiable fairness, leveraging trusted hardware. Unlike prior works that usually design a dedicated consensus protocol to achieve fairness, our scheme can be integrated with any blockchain system. Our evaluation results on Amazon EC2 using up to 120 instances across different regions show that our construction imposes only minimal overhead on existing blockchain systems.

Item mining, a fundamental task for collecting statistical data from users, has raised increasing privacy concerns. To address these concerns, local differential privacy (LDP) was proposed as a privacy-preserving technique. Existing LDP item mining mechanisms primarily concentrate on global statistics, i.e., those from the entire dataset. Nevertheless, they fall short of usertailored tasks such as personalized recommendations, whereas classwise statistics can improve task accuracy with fine-grained information. Meanwhile, the introduction of class labels brings new challenges. Label perturbation may result in invalid items for aggregation. To this end, we propose frameworks for multi-class item mining, along with two mechanisms: validity perturbation to reduce the impact of invalid data, and correlated perturbation to preserve the relationship between labels and items. We also apply these optimized methods to two multi-class item mining queries: frequency estimation and top-$k$item mining. Through theoretical analysis and extensive experiments, we verify the effectiveness and superiority of these methods.

Large language models (LLMs) have shown great potential as general-purpose AI assistants across various domains. To fully leverage this potential in specific applications, many companies provide fine-tuning API services, enabling users to upload their own data for LLM customization. However, fine-tuning services introduce a new safety threat: user-uploaded data, whether harmful or benign, can break the model’s alignment, leading to unsafe outputs. Moreover, existing defense methods struggle to address the diversity of fine-tuning datasets (e.g., varying sizes, tasks), often sacrificing utility for safety or vice versa. To address this issue, we propose Safe Delta, a safety-aware post-training defense method that adjusts the delta parameters (i.e., the parameter change before and after fine-tuning). Specifically, Safe Delta estimates the safety degradation, selects delta parameters to maximize utility while limiting overall safety loss, and applies a safety compensation vector to mitigate residual safety loss. Through extensive experiments on four diverse datasets with varying settings, our approach consistently preserves safety while ensuring that the utility gain from benign datasets remains unaffected.

Secure multi-party computation (MPC) allows joint computations on sensitive data while guaranteeing privacy and correctness. In recent years, a series of MPC protocols assisted by trusted execution environments (TEEs) have been proposed to reduce overhead brought by costly cryptographic techniques. However, existing protocols either generally assume consistent trust in TEEs among all participating parties, or require dedicated designs for different applications. This prevents the protocols from being deployed in practice. To address these challenges, in this work, we propose a generic MPC protocol without assuming consistent trust in TEEs while fully utilizing heterogeneous TEEs to improve efficiency. To this end, we propose a security model to capture parties' inconsistent trust in TEEs and prove the security of our protocol under a simpler variant of the UC framework (SUC framework). In addition, we instantiate our protocol for secure aggregation based on a state-of-the-art information-theoretically secure protocol SwiftAgg+. Evaluation results among 64 parties deployed on Azure virtual machines show that our protocol reduces the running time of SwiftAgg+ by 66%. The running time of parties in our protocol is reduced by at most 91% compared to that required in SwiftAgg+.

Secure two-party computation (2PC) enables two parties to jointly evaluate a function while maintaining input privacy. Despite recent significant progress, a notable efficiency gap remains between actively secure and passively secure protocols. In S&P'12, Huang, Katz, and Evans formalized the notion of active security with one-bit leakage, providing a promising approach to bridging this gap. Protocols derived from this notion have become foundational in designing highly efficient actively secure 2PC protocols. However, a critical challenge identified by Huang, Katz, and Evans remains unexplored: these protocols face significant weaknesses in ensuring fairness for honest parties when employed in standalone settings rather than as components within larger protocols. While the authors proposed two potential solutions to mitigate this issue, both approaches are prohibitively expensive and lack formalization of security guarantees. In this paper, we first formally define an enhanced notion called active security with one-bit-advantage bound, in which the adversaries' advantages are strictly bounded to at most one bit beyond what honest parties obtain. This bound is enforced through a progressive revelation mechanism, where the evaluation result is disclosed incrementally bit by bit. In addition, we propose a novel approach leveraging label structures within garbled circuits to design a highly efficient constant-round 2PC protocol that achieves active security with one-bit advantage bound. Our protocol demonstrates runtime performance nearly identical to that of passively secure garbled-circuit counterparts in duplex networks (e.g., 1.033 × for the SHA256 circuit in LAN), with low overhead for output progressive revelation (only 80 communicated bytes per bit release). With its strengthened security guarantees and minimal overhead, our protocol is highly suitable for practical 2PC applications.

With the increasing scale and complexity of online activities, accountability, as an after-the-fact mechanism, has become an effective complementary approach to ensure system security. Decades of research have delved into the connotation of accountability. They fail, however, to achieve practical accountability of decryption. This paper seeks to address this gap. We consider the scenario where a client (called encryptor, her) encrypts her data and then chooses a delegate (a.k.a. decryptor, him) that stores data for her. If the decryptor initiates an illegitimate decryption on the encrypted data, there is a non-negligible probability that this behavior will be detected, thereby holding the decryptor accountable for his decryption. We make three contributions. First, we review key definitions of accountability known so far. Based on extensive investigations, we formalize new definitions of accountability specifically targeting the decryption process, denoted as accountable decryption, and discuss the (im)possibilities when capturing this concept. We also define the security goals in correspondence. Second, we present a novel Trusted Execution Environment(TEE)-assisted solution aligning with definitions. Instead of fully trusting TEE, we take a further step, making TEE work in the “trust, but verify” model where we trust TEE and use its service, but empower users (i.e., decryptors) to detect the potentially compromised state of TEEs. Third, we implement a full-fledged system and conduct a series of evaluations. The results demonstrate that our solution is efficient. Even in a scenario involving$300,000$log entries, the decryption process concludes in approximately 5.5ms, and malicious decryptors can be identified within 69ms.

Trusted Execution Environment (TEE)-assisted confidential smart contracts (TCSC) have attracted extensive attention from both academia and industry. Despite an enormous number of TCSC projects, the extent of confidentiality offered by them remains being questioned: the factual and fictional aspects are not well distinguished, which limits their adoption. In this paper, we provide a formal treatment of TCSC, endowing them with an expressive syntax and security definitions. Based on these definitions, we propose a provably secure TCSC instantiation. Then, we investigate each algorithm and identify the implementation flaws that may make a TCSC system violate its security properties. Our analysis reveals the gap between theoretical security models and real-world implementations: even assuming a TCSC is provably secure by design, it may still fail in practice. We further compare our TCSC instantiation with 16 representative TCSC systems. Our results show that, surprisingly, all these surveyed projects are subject to practical attacks. Finally, we implement a TCSC prototype and conduct a comprehensive evaluation, revealing the overheads of distributed key management and the performance challenges of executing complex contracts within TEEs.

Quasi complementary sequence sets (QCSSs) are important in modern communication systems as they are capable of supporting more users, which is desired in applications like MC-CDMA nowadays. In this paper, we first derive a tighter bound on the maximum aperiodic correlation among all constituent complementary sequence sets in QCSSs. By proposing a new combinatorial structure called quasi-Florentine rectangles, we obtain a new construction of QCSSs with large set sizes. Using Butson-type Hadamard matrices and quasi-Florentine rectangles, we propose another construction which can construct QCSSs with flexible parameters over any given alphabet size, including small alphabets. All the proposed sequences are optimal with respect to the newly proposed bound. Also, through some of the constructions, the column sequence PMEPR of the proposed QCSSs are upper bounded by 2.

The Decentralized Autonomous Organization (DAO) has emerged as a popular governance solution for decentralized applications (dApps), enabling them to manage their members across the world. This structure ensures that no single entity can arbitrarily control the dApp without approval from the majority of members. However, despite its advantages, DAOs face several challenges within their governance processes that can compromise their integrity and potentially lead to the loss of dApp assets. In this paper, we first provided an overview of the DAO governance process within the blockchain. Next, we identified issues within 3 key components of the governance process: the Governance Contract, Documentation, and Proposal. Regarding the Governance Contract, malicious developers could embed backdoors or malicious code to manipulate the governance process. In terms of Documentation, inadequate or unclear documentation from developers may prevent members from effectively participating, increasing the risk of undetected governance attacks or enabling a small group of members to dominate the process. Lastly, with Proposals, members could submit malicious proposals with embedded malicious code in an attempt to gain control of the DAO. To address these issues, we developed automated methods to detect such vulnerabilities. To investigate the prevalence of these issues within the current DAO ecosystem, we constructed a state-of-the-art dataset that includes 3,348 DAOs, 144 documentation, and 65,436 proposals across 9 different blockchains. Our analysis reveals that many DAO developers and members have not given sufficient attention to these issues. For the Governance Contract, 176 DAOs allow external entities to control their governance contracts, while one DAO permits developers to arbitrarily change the contract's logic. In terms of Documentation, only 71 DAOs provide adequate guidance for their members on governance processes. As for Proposals, over 90% of the examined proposals (32,500) fail to provide consistent descriptions and code for their members, highlighting a significant gap in transparency within the DAO governance process. For a better DAO governance ecosystem, DAO developers and members can utilize the methods to identify and address issues within the governance process.

Time series have numerous applications in finance, healthcare, IoT, and smart city. In many of these applications, time series typically contain personal data, so privacy infringement may occur if they are released directly to the public. Recently, local differential privacy (LDP) has emerged as the state-of-the-art approach to protecting data privacy. However, existing works on LDP-based collections cannot preserve the shape of time series. A recent work, PatternLDP, attempts to address this problem, but it can only protect a finite group of elements in a time series due to ω-event level privacy guarantee. In this paper, we propose PrivShape, a trie-based mechanism under user-level LDP to protect all elements. PrivShape first transforms a time series to reduce its length, and then adopts trie-expansion and two-level refinement to improve utility. By extensive experiments on real-world datasets, we demonstrate that PrivShape outperforms PatternLDP when adapted for offline use, and can effectively extract frequent shapes.

Linear codes are widely studied in coding theory as they have nice applications in distributed storage, combinatorics, lattices, cryptography and so on. Constructing linear codes with desirable properties is an interesting research topic. In this paper, based on the augmentation technique, we present two families of linear codes from some functions over finite fields. The first family of linear codes is constructed from monomial functions over finite fields. The weight distribution of the codes is determined in some cases. The codes are proved to be both optimally or almost optimally extendable and self-orthogonal under certain conditions. The localities of the codes and their duals are also studied and we obtain an infinite family of optimal or almost optimal locally recoverable codes. The second family of linear codes is constructed from weakly regular bent functions over finite fields and its weight distribution is explicitly determined. This family of codes is also proved to be both optimally or almost optimally extendable and self-orthogonal. Besides, this family of codes has been proven to have locality 2 or 3 under certain conditions. Particularly, we derive two infinite families of optimal locally recoverable codes. Some infinite families of 2-designs are obtained from the codes in this paper as byproducts.

With the prevalence of mobile computing, mobile devices have been generating numerous sensor data, a.k.a., time series. Since these time series may include sensitive information, users are posed with severe privacy risks. To protect individuals' privacy, local differential privacy (LDP) is proposed. However, the added noise satisfying LDP typically degrades the utility of released data, especially for anomaly detection such as healthcare monitoring and hazard alarming. In this paper, we study privacy-preserving time series release with anomalies. Recently, local differential privacy in the temporal setting (TLDP) is proposed to perturb the temporal order rather than the values. While it improves the utility for releasing value-critical data, it still suffers from low utility for anomaly detection, because of the inevitable missing and delayed values incurred by TLDP perturbation. We propose to improve its utility from two aspects. To reduce the missing values, we utilize selective substitution according to items' anomaly scores. To decrease the delayed values, we define metric-based$(\alpha , \delta )$-TLDP and propose a mechanism that can prioritize anomaly release at a close timestamp while still guaranteeing the same TLDP privacy. Through theoretical and empirical evaluation, we show superior performance gain over existing TLDP-based mechanisms on both synthetic and real-world datasets.

As blockchain-based commercial projects and startups flourish, efficiency becomes one of the critical metrics in designing blockchain systems. Due to its high efficiency, Proof of Authority (PoA) Aura has become one of the most widely adopted consensus solutions for blockchains. Our research finds over 4,000 projects have used Aura and its variants. In this paper, we provide a rigorous analysis of Aura. We propose three types of time-manipulation attacks, where a malicious leader simply needs to modify the timestamp in its proposed block or delay it to extract extra benefits. These attacks can easily break the legal leader election, thus directly harming the fairness of the block proposal. We apply our attacks to a mature Aura project called OpenEthereum. By repeatedly conducting our attacks1 over 15 days, we find that an adversary can gain on average 200% mining rewards of their fair shares. Furthermore, such attacks can even indirectly break the finality of blocks and the safety of the system. Based on the deployment of Aura as of September 2022, the potentially affected market cap is up to 2.13 billion USD. As a by-product, we further discuss solutions to mitigate such issues and report our observations to official teams.

Garg et al. (TCC 2018) defined the notion of registration-based encryption (RBE) where the private key generator (PKG) is decoupled from key management and replaced by a key curator (KC). KC does not possess any cryptographic secrets and only plays the role of aggregating the public keys of all the registered users and updating the public parameters whenever a new user joins the system, which solves the key escrow issue. Notwithstanding, RBE still places a significant amount of trust in KC, whose actions are not accountable, e.g., it could secretly register multiple keys for already registered users. In this article, we propose a blockchain-based RBE framework, which provides total transparency and decentralization of KC by leveraging smart contracts. Our framework transfers the right of key management from KC to individual participants and keeps publicly upgradable parameters on-chain. We provide a basic construction that calculates the public parameter on-chain and an extended construction with better efficiency, which merely calculates the roots of trees on-chain. Our basic version is theoretically feasible, while the extended version is practically feasible. In particular, the enhanced scheme reduces computing complexity to a constant level. Our prototype implementation and evaluation results demonstrate that our extended construction is satisfactorily efficient.

Proof of Authority (PoA) is a type of permissioned consensus algorithm with a fixed committee. PoA has been widely adopted by communities and industries due to its better performance and faster finality. In this paper, we explore the unfairness issue existing in the current PoA implementations. We have investigated 2,500+ in the wild projects and selected 10+ as our main focus (covering Ethereum, Binance smart chain, etc.). We have identified two types of order manipulation attacks to separately break the transaction-level (a.k.a. transaction ordering) and the block-level (sealer position ordering) fairness. Both of them merely rely on honest-but-profitable sealer assumption without modifying original settings. We launch these attacks on the forked branches under an isolated environment and carefully evaluate the attacking scope towards different implementations. To date (as of Nov 2021), the potentially affected PoA market cap can reach up to 681,087 million USD. Besides, we further dive into the source code of selected projects, and accordingly, propose our recommendation for the fix. To the best of knowledge, this work provides the first exploration of the unfairness issue in PoA algorithms.

In this paper, we propose a frontrunning block attack against the Clique-based Proof of Authority (PoA) algorithms. Our attack can frontrun blocks from honest in-turn sealers by breaking the leader rotation’s proper order. By falsifying the priority parameters (both difficulty and delay time), a malicious non-in-turn sealer can always successfully occupy the leader position and produce advantageous blocks that may contain profitable transactions. As a typical instance, we apply our attack to a mature Clique-based project, HPB (with the market cap $10,128,116, as of Jan 2022). Experimental results demonstrate the effectiveness and feasibility. Then, we further propose fixes by checking sealer’s identity. Our investigation and suggestion have been submitted to its official team. We believe this work can act as, at least, a warning case for Clique variants to avoid repeating such design mistakes.

The blockchain-based smart contract lacks privacy, since the contract state and instruction code are exposed to the public. Combining smart-contract execution with Trusted Execution Environments provides an efficient solution, called TEE-assisted smart contracts (TCSC), for protecting the confidentiality of contract states. However, the combination approaches are varied, and a systematic study is absent. Newly released systems may fail to draw upon the experience learned from existing protocols, such as repeating known design mistakes or applying TEE technology in insecure ways. In this paper, we first investigate and categorize existing systems into two types: the layer-one solution and the layer-two solution. Then, we establish an analysis framework to capture their common aspects, covering desired properties (for contract services), threat models, and security considerations (for underlying systems). Based on our taxonomy, we identify their ideal functionalities, and uncover fundamental flaws and challenges in each specification’s design. We believe that this work would provide a guide for the development of TEE-assisted smart contracts, as well as a framework to evaluate future TCSC systems.

Maximum distance separable (MDS) codes are very important in both theory and practice. There is a classical construction of a family of$[{2^{m}+1, 2u-1, 2^{m}-2u+3}]$MDS codes for$1 \leq u \leq 2^{m-1}$, which are cyclic, reversible and BCH codes over${\mathrm {GF}}(2^{m})$. The objective of this paper is to study the quaternary subfield subcodes and quaternary subfield codes of a subfamily of the MDS codes for even$m$. A family of quaternary cyclic codes is obtained. These quaternary codes are distance-optimal in some cases and very good in general. Furthermore, two infinite families of 3-designs from these quaternary codes and their duals are presented.

Non-overlapping codes are a set of codewords in$\bigcup _{n \ge 2} \mathbb {Z}_{q}^{n}$, where$\mathbb {Z}_{q} = \{0,1, {\dots },q-1\}$, such that the prefix of each codeword is not a suffix of any codeword in the set, including itself; and for variable-length codes, a codeword does not contain any other codeword as a subword. In this paper, we investigate a generic method to generalize binary codes to$q$-ary ones for$q > 2$, and analyze this generalization on the two constructions given by Levenshtein (also by Gilbert; Chee, Kiah, Purkayastha, and Wang) and Bilotta, respectively. The generalization on the former construction gives large non-expandable fixed-length non-overlapping codes whose size can be explicitly determined; the generalization on the latter construction is the first attempt to generate$q$-ary variable-length non-overlapping codes. More importantly, this generic method allows us to utilize the generating function approach to analyze the cardinality of the underlying$q$-ary non-overlapping codes. The generating function approach not only enables us to derive new results, e.g., recurrence relations on their cardinalities, new combinatorial interpretations for the constructions, and the superior limit of their cardinalities for some special cases, but also greatly simplifies the arguments for these results. Furthermore, we give an exact formula for the number of fixed-length words that do not contain the codewords in a variable-length non-overlapping code as subwords. This thereby solves an open problem by Bilotta and induces a recursive upper bound on the maximum size of variable-length non-overlapping codes.

A pair of sequences is called a Z-complementary pair (ZCP) if it has zero aperiodic autocorrelation sums at each of the non-zero time-shifts within a certain region, called the zero correlation zone (ZCZ). ZCPs are categorised into two types: Type-I ZCPs and Type-II ZCPs. Type-I ZCPs have the ZCZ around the in-phase position and Type-II ZCPs have the ZCZ around the end-shift position. Till now only a few constructions of Type-II ZCPs are reported in the literature, and all have lengths of the form 2m±1 or N+1 where N=2a10b26cand a, b, c are non-negative integers. In this paper, we propose a recursive construction of ZCPs based on concatenation of sequences. Inspired by Turyn's construction of Golay complementary pairs, we also propose a construction of Type-II ZCPs from known ones. The proposed constructions can generate optimal Type-II ZCPs with new flexible parameters and Z-optimal Type-II ZCPs with any odd length. In addition, we give upper bounds for the PMEPR of the proposed ZCPs. It turns out that our constructions lead to ZCPs with low PMEPR.

It has recently been pointed out that placement delivery arrays (PDAs) are equivalent to strong edge colorings of bipartite graphs. In this paper we consider various methods of combining two or more strong edge colorings of bipartite graphs to obtain new ones, and therefore new PDAs. Combining PDAs in certain ways also gives a framework for obtaining PDAs with more robust and flexible parameters. We investigate how the parameters of certain strong edge colorings change after being combined with others and, after comparing the parameters of the resulting PDAs with those of the initial ones, find that subpacketization levels thusly can often be improved.

Functions with low differential uniformity have important applications in cryptography, coding theory, and sequence design. The differential spectrum of a cryptographic function is of great interest for estimating its resistance to some variants of differential cryptanalysis. Finding power permutations (i.e., monomial bijective mappings) over finite fields with low differential uniformity and determining their differential spectra have received a lot of attention over the past two decades. The objective of this paper is to study the differential properties of the well-known Kasami power permutations x p2k-pk+1 over GF(pn), where p is an odd prime and k is an integer with gcd(n, k) = 1. It turns out that this family of monomials is differentially (p + 1)-uniform. Our result in the case of p = 3 gives an affirmative solution to a recent conjecture by Xu, Cao, and Xu. Most notably, the differential spectrum of this family of power permutations is completely determined.

In this paper, we present a new method for explicitly constructing regular low-density parity-check (LDPC) codes based on Sn(Fq), the space of n × n symmetric matrices over Fq. Using this method, we obtain two classes of binary LDPC codes, C(n, q) and CT (n, q), both of which have grith 8. Then, both the minimum distance and the stopping distance of each class are investigated. It is shown that the minimum distance and the stopping distance of CT(n, q) are both 2q. As for C(n, q), we determine the minimum distance and the stopping distance for some special cases and obtain some lower bounds for other cases.

Zero-difference balanced (ZDB) functions integrate a number of subjects in combinatorics and algebra, and have many applications in coding theory, cryptography, and communications engineering. In this paper, three new families of ZDB functions are presented. The first construction gives ZDB functions defined on the abelian groups (GF(q1)×,...,×GF(qk),+) with new and flexible parameters. The other two constructions are based on 2-cyclotomic cosets and yield ZDB functions on \BBZn with new parameters. The parameters of optimal constant composition codes, optimal, and perfect difference systems of sets obtained from these new families of ZDB functions are also summarized.

Two constructions of binary sequences with optimal autocorrelation of period N ≡ 0 (mod 4) are investigated. These two constructions are powerful and generic in the sense that many classes of binary sequences could be obtained from binary sequences with ideal autocorrelation. Both the linear complexity and the minimal polynomial of all the classes of binary sequences are determined.

Frequency hopping (FH) is one of the basic spread coding technologies in spread spectrum communications. FH sequences are needed in FH code-division multiple access (CDMA) systems. For the anti-jamming purpose, FH sequences are required to have a large linear span. A few optimal sets of FH sequences are available in the literature. However, their sequences have very small linear spans. It is known that an optimal set of FH sequences could be transformed to another optimal set of FH sequences with large linear spans by a power permutation, if the power is chosen properly [see C. Ding and J. Yin, IEEE Trans. Inf. Theory, vol. IT-54, pp. 3741-3745, 2008]. The objective of this paper is to investigate this idea of C. Ding and J. Yin further, and determine the linear span of the FH sequences in the optimal sets obtained by applying a power permutation to some existing optimal sets of FH sequences.

Binary sequences with good autocorrelation are needed in many applications. A construction of binary sequences with three-level autocorrelation was recently presented. This construction is generic and powerful in the sense that many classes of binary sequences with three-level autocorrelation could be obtained from any difference set with Singer parameters. The objective of this paper is to determine both the linear complexity and the minimal polynomial of two classes of binary sequences, i.e., the class based on the Singer difference set, and the class based on the GMW difference set.

Binary sequences with optimal autocorrelation are needed in many applications. Two constructions of binary sequences with optimal autocorrelation of period N ≡ 0 (mod 4) are investigated. The two constructions are powerful and generic in the sense that many classes of binary sequences with optimal autocorrelation could be obtained from binary sequences with ideal autocorrelation. General results on the minimal polynomials of these binary sequences are derived. Based on the results, both the linear complexities and the minimal polynomials are determined.

Secure Multi-party Computation (SMC) has been a research focus in international cryptography community in recent years. SMC deals with the following situation: Two (or many) parties want to jointly perform a computation without disclosing their private inputs. Privacy-preserving convex hulls problem is a special case of SMC and it can be applied in many fields such as military and commercial fields. In this paper, we first present two privacy-preserving protocols to solve the convex hulls problem by using Yao 's millionaire protocol. We also discuss the security, correctness and performance of the two protocols. Based on the Euclid-distance Measure Protocol, an approximate solution to the convex hulls problem is proposed for fairness, which conceals more private information.