The problem of Byzantine Fault Tolerance (BFT) has received a lot of attention in the last 30 years. Due to the popularity of Proof of Stake (PoS) blockchains in recent years, several BFT protocols have been deployed in the large scale of Internet environment. We analyze several popular BFT protocols such as Capser FFG/CBC-FBC for Ethereum 2.0 and GRANDPA for Polkadot. Our analysis shows that the security models for these BFT protocols are slightly different from the models commonly accepted in the academic literature. For example, we show that, if the adversary has a full control of the message delivery order in the underlying network, then none of the BFT protocols for Ethereum blockchain 2.0 and Polkadot blockchain could achieve liveness even in a synchronized network. Though it is not clear whether a practical adversary could actually control and re-order the underlying message delivery system (at Internet scale) to mount these attacks, it raises an interesting question on security model gaps between academic BFT protocols and deployed BFT protocols in the Internet scale. With these analysis, this article proposes a Casper CBC-FBC style binary BFT protocol and shows its security in the traditional academic security model with complete asynchronous networks. For partial synchronous networks, we propose a multi-value BFT protocol BDLS based on the seminal DLS protocol and show that it is one of the most efficient practical BFT protocols at large scale networks in the traditional academic BFT security model. The implementation of BDLS is available at https://github.com/yonggewang/bdls . Finally, we propose a multi-value BFT protocol XP for complete asynchronous networks and show its security in the traditional academic BFT security model.

Private Function Evaluation (PFE) is the problem of evaluating one party’s private data using a private function owned by another party. Existing solutions for PFE are based on universal circuits evaluated in secure multiparty computations or on hiding the circuit’s topology and the gate’s functionality through additive homomorphic encryption. These solutions, however, are not efficient enough for practical use; hence there is a need for more efficient techniques. This work looks at utilizing the Intel Software Guard Extensions platform (SGX) to provide a more practical solution for PFE where the privacy of the data and the function are both preserved. Notably, our solution carefully avoids the pitfalls of side-channel attacks on SGX. We present solutions for two different scenarios: the first is when the function’s owner has an SGX-enabled device and the other is when a third party (or one of the data owners) has the SGX capability. Our results show a clear expected advantage in terms of running time for the first case over the second. Investigating the slowdown in the second case leads to the garbling time which constitutes more than 60% of the consumed time. Both solutions clearly outperform FairplayPF in our tests.

In November 2017, Hecht and Kamlofsky submitted HK17, a quaternion(octonion)-based Diffie-Hellman key exchange protocol, to NIST post-quantum cryptography project, and thought that at least O(p8) arithmetic operations are needed for a passive adversary to recover the shared key where p is the modulo used in the scheme. Later, Bernstein and Lange pointed out that the shared key can be recovered with O(p) arithmetic operations, which implies that HK17 with small p is not secure. However, their attack does not work in practice for the scheme with sufficiently large p, although the scheme is still efficient. In this paper, we propose an attack to show that just constant arithmetic operations, or Õ(log p) bit operations, are enough to recover the shared key for a passive adversary. Note that even the legal party in the protocol needs at least Õ(log p) bit operations to establish the shared key. We break HK17 completely in the practical sense.

Security challenges brought about by the upcoming 5G era should be taken seriously. Code-based cryptography leverages difficult problems in coding theory and is one of the main techniques enabling cryptographic primitives in the postquantum scenario. In this work, we propose the first efficient secure scheme based on polar codes (i.e., polarRLCE) which is inspired by the RLCE scheme, a candidate for the NIST postquantum cryptography standardization in the first round. In addition to avoiding some weaknesses of the RLCE scheme, we show that, with the proper choice of parameters, using polar codes, it is possible to design an encryption scheme to achieve the intended security level while retaining a reasonably small public key size. In addition, we also present a KEM version of the polarRLCE scheme that can attain a negligible decryption failure rate within the corresponding security parameters. It is shown that our proposal enjoys an apparent advantage to decrease the public key size, especially on the high-security level.

Lattice based encryption schemes and linear code based encryption schemes have received extensive attention in recent years since they have been considered as post-quantum candidate encryption schemes. Though LLL reduction algorithm has been one of the major cryptanalysis techniques for lattice based cryptographic systems, key recovery cryptanalysis techniques for linear code based cryptographic systems are generally scheme specific. In recent years, several important techniques such as Sidelnikov-Shestakov attack, filtration attacks, and algebraic attacks have been developed to crypt-analyze linear code based encryption schemes. Though most of these cryptanalysis techniques are relatively new, they prove to be very powerful and many systems have been broken using them. Thus it is important to design linear code based cryptographic systems that are immune against these attacks. This paper proposes linear code based encryption scheme RLCE which shares many characteristics with random linear codes. Our analysis shows that the scheme RLCE is secure against existing attacks and we hope that the security of the RLCE scheme is equivalent to the hardness of decoding random linear codes. Example parameters are recommended for the scheme RLCE.

LDPC codes, LT codes, and digital fountain techniques have received significant attention from both academics and industry in the past few years. By employing the underlying ideas of efficient Belief Propagation (BP) decoding process in LDPC and LT codes, this paper designs the BP-XOR codes and use them to design three classes of secret sharing schemes called BP-XOR secret sharing schemes, pseudo-BP-XOR secret sharing schemes, and LDPC secret sharing schemes. By establishing the equivalence between the edge-colored graph model and degree-two BP-XOR secret sharing schemes, we are able to design novel perfect and ideal 2-out-of-n BP-XOR secret sharing schemes. By employing techniques from array code design, we are also able to design other (n; k) threshold LDPC secret sharing schemes. In the efficient (pseudo) BP-XOR/LDPC secret sharing schemes that we will construct, only linear number of XOR (exclusive-or) operations on binary strings are required for both secret distribution phase and secret reconstruction phase. For a comparison, we should note that Shamir secret sharing schemes require O(n log n) field operations for the secret distribution phase and O(n2) field operations for the secret reconstruction phase. Furthermore, our schemes achieve the optimal update complexity for secret sharing schemes. By update complexity for a secret sharing scheme, we mean the average number of bits in the participant's shares that needs to be revised when certain bit of the master secret is changed. The extremely efficient secret sharing schemes discussed in this paper could be used for massive data storage in cloud environments achieving privacy and reliability without employing encryption techniques.

One of the important problems in secret sharing schemes is to establish bounds on the size of the shares to be given to participants in secret sharing schemes. The other important problem in secret sharing schemes is to reduce the computational complexity in both secret distribution phase and secret reconstruction phase. In this paper, we design efficient threshold (n, k) secret sharing schemes to achieve both of the above goals. In particular, we show that if the secret size |s| is larger than max{1 + log2n, n(n - k)/(n - 1)}, then ideal secret sharing schemes exist. In the efficient ideal secret sharing schemes that we will construct, only XOR-operations on binary strings are required (which is the best we could achieve). These schemes will have many applications both in practice and in theory. For example, they could be used to design very efficient verifiable secret sharing schemes which will have broad applications in secure multi-party computation and could be used to design efficient privacy preserving data storage in cloud systems.

Low Density Parity Check (LDPC) codes such as LT codes have received significant attention from both academics and industry in the past few years. By employing the underlying ideas of efficient Belief Propagation (BP) decoding process in LT codes, this paper introduces array BP-XOR codes and shows the equivalence between the edge-colored graph model and degree-one-and-two encoding symbol based array BP-XOR codes. Using this equivalence result, novel [n, n-2] and [n, 2] MDS array BP-XOR codes are designed in this paper.

Secure communications guaranteeing reliability and privacy (without unproven assumptions) in networks with active adversaries has been an important research issue. It has been studied for point to point networks by Dolev-Dwork-Waarts-Yung (J. ACM1993), Desmedt–Wang (Eurocrypt 2002), and Srinathan–Narayanan–Rangan (Crypto 2004). Dolev–Dwork–Waarts–Yung gave necessary and sufficient conditions for secure communication in networks with the condition that 1) all the channels are two-way; or 2) all the channels are one-way from the sender to the receiver. In this paper, we study the general case with a network modeled by a directed graph. In this general case, there are communication channels from the sender to the receiver and there are feedback channels from the receiver to the sender. We give necessary and sufficient bounds on the number of channels that are required from sender to receiver given a number of “feedback” channels from receiver to sender. We give these bounds for the case reliability is perfect, as well as for the case it is not perfect.

In order to generate synthetic basket datasets for better benchmark testing, it is important to integrate characteristics from real-life databases into the synthetic basket datasets. The characteristics that could be used for this purpose include the frequent itemsets and association rules. The problem of generating synthetic basket datasets from frequent itemsets is generally referred to as inverse frequent itemset mining. In this paper, we show that the problem of approximate inverse frequent itemset mining is NP-complete. Then we propose and analyze an approximate algorithm for approximate inverse frequent itemset mining, and discuss privacy issues related to the synthetic basket dataset. In particular, we propose an approximate algorithm to determine the privacy leakage in a synthetic basket dataset.

Testing of database applications is of great importance. A significant issue in database application testing consists in the availability of representative data. In this paper, we investigate the problem of generating a synthetic database based on a-priori knowledge about a production database. Our approach is to fit general location model using various characteristics (e.g., constraints, statistics, rules) extracted from the production database and then generate the synthetic data using model learnt. The generated data is valid and similar to real data in terms of statistical distribution, hence it can be used for functional and performance testing. As characteristics extracted may contain information which may be used by attacker to derive some confidential information about individuals, we present our disclosure analysis method which applies cell suppression technique for identity disclosure analysis and perturbation for value disclosure.

Association rule mining has received a lot of attention in the data mining community and several algorithms were proposed to improve the performance of association rule or frequent itemset mining. The IBM Almaden synthetic data generator has been commonly used for performance evaluation. One recent work shows that the data generated is not good enough for benchmarking as it has very different characteristics from real-world data sets. Hence there is a great need to use real-world data sets as benchmarks. However, organizations hesitate to provide their data due to privacy concerns. Recent work on privacy preserving association rule mining addresses this issue by modifying real data sets to hide sensitive or private rules. However, modifying individual values in real data may impact on other, non-sensitive rules. In this paper, we propose a feasible solution to the NP-complete problem of inverse frequent set mining. Since solving this problem by linear programming techniques is very computationally prohibitive, we apply graph-theoretical results to divide the original itemsets into components that preserve maximum likelihood estimation. We then use iterative proportional fitting method to each component. The technique is experimentally evaluated with two real data sets and one synthetic data set. The results show that our approach is effective and efficient for reconstructing market basket data set from a given set of frequent itemsets while preserving sensitive information.

We consider the problem of dependable computation with multiple inputs. The goal is to study when redundancy can help to achieve survivability and when it cannot. We use AND/OR graphs to model fault tolerant computations with multiple inputs. While there is a polynomial time algorithm for finding vertex disjoint paths in networks, we will show that the equivalent problem in computation systems with multiple inputs is NP-hard. Our main results are as follows. (1) We present a general model for fault tolerant computation systems with multiple inputs: AND/OR graphs. (2) We show that it is NP-hard to find two vertex disjoint solution graphs in an AND/OR graph. It follows that in the general case redundancy cannot help to achieve survivability, assuming P≠NP.

Polynomial-time safe and unsafe approximations for intractable sets were introduced by Meyer and Paterson [Technical Report TM-126, Laboratory for Computer Science, MIT, Cambridge, MA, 1979] and Yesha [SIAM J. Comput., 12 (1983), pp. 411--425], respectively. The question of which sets have optimal safe and unsafe approximations has been investigated extensively. Duris and Rolim [Lecture Notes in Comput. Sci. 841, Springer-Verlag, Berlin, New York, 1994, pp. 38--51] and Ambos-Spies [Proc. 22nd ICALP, Springer-Verlag, Berlin, New York, 1995, pp. 384--392] showed that the existence of optimal polynomial-time approximations for the safe and unsafe cases is independent. Using the law of the iterated logarithm for p-random sequences (which has been recently proven in [Proc. 11th Conf. Computational Complexity, IEEE Computer Society Press, Piscataway, NJ, 1996, pp. 180--189]), we extend this observation by showing that both the class of polynomial-time $\Delta$-levelable sets and the class of sets which have optimal polynomial-time unsafe approximations have p-measure 0. Hence typical sets in E (in the sense of p-measure) do not have optimal polynomial-time unsafe approximations. We will also establish the relationship between resource bounded genericity concepts and the polynomial-time safe and unsafe approximation concepts.

The stochastic properties of p-random sequences are studied in this paper. It is shown that the law of the iterated logarithm holds for p-random sequences. This law gives a quantitative characterization of the density of p-random sets. When combined with the invariance property of p-random sequences, this law is also useful in proving that some complexity classes have p-measure 0.