Minimizing the Two-Round Even–Mansour Cipher

The r-round (iterated) Even–Mansour cipher (also known as key-alternating cipher) defines a block cipher from r fixed public n-bit permutations \(P_1,\ldots ,P_r\) as follows: Given a sequence of n-bit round keys \(k_0,\ldots ,k_r\), an n-bit plaintext x is encrypted by xoring round key \(k_0\), applying permutation \(P_1\), xoring round key \(k_1\), etc. The (strong) pseudorandomness of this construction in the random permutation model (i.e., when the permutations \(P_1,\ldots ,P_r\) are public random permutation oracles that the adversary can query in a black-box way) was studied in a number of recent papers, culminating with the work of Chen and Steinberger (EUROCRYPT 2014), who proved that the r-round Even–Mansour cipher is indistinguishable from a truly random permutation up to \(\mathcal {O}(2^{\frac{rn}{r+1}})\) queries of any adaptive adversary (which is an optimal security bound since it matches a simple distinguishing attack). All results in this entire line of work share the common restriction that they only hold under the assumption that the round keys \(k_0,\ldots ,k_r\) and the permutations \(P_1,\ldots ,P_r\) are independent. In particular, for two rounds, the current state of knowledge is that the block cipher \(E(x)=k_2\oplus P_2(k_1\oplus P_1(k_0\oplus x))\) is provably secure up to \(\mathcal {O}(2^{2n/3})\) queries of the adversary, when \(k_0\), \(k_1\), and \(k_2\) are three independent n-bit keys, and \(P_1\) and \(P_2\) are two independent random n-bit permutations. In this paper, we ask whether one can obtain a similar bound for the two-round Even–Mansour cipher from just one n-bit key and one n-bit permutation. Our answer is positive: When the three n-bit round keys \(k_0\), \(k_1\), and \(k_2\) are adequately derived from an n-bit master key k, and the same permutation P is used in place of \(P_1\) and \(P_2\), we prove a qualitatively similar \(\widetilde{\mathcal {O}}(2^{2n/3})\) security bound (in the random permutation model). To the best of our knowledge, this is the first “beyond the birthday bound” security result for AES-like ciphers that does not assume independent round keys.     

Key Recovery Attacks on Iterated Even–Mansour Encryption Schemes

Iterated Even–Mansour (EM) encryption schemes (also named “key-alternating ciphers”) were extensively studied in recent years as an abstraction of commonly used block ciphers. A large amount of previous works on iterated EM concentrated on security in an information-theoretic model. A central question studied in these papers is: What is the minimal number of rounds for which the resulting cipher is indistinguishable from an ideal cipher? In this paper, we study a similar question in the computational model: What is the minimal number of rounds, assuring that no attack can recover the secret key faster than trivial attacks (such as exhaustive search)? We study this question for the two natural key scheduling variants that were considered in most previous papers: the identical subkeys variant and the independent subkeys variant. In the identical subkeys variant, we improve the best known attack by an additional round and show that \(r=3\) rounds are insufficient for assuring security, by devising a key recovery attack whose running time is about \(n/\log (n)\) times faster than exhaustive search for an \(n\)-bit key. In the independent subkeys variant, we also extend the known results by one round and show that for \(r=2\), there exists a key recovery attack whose running time is faster than the benchmark meet-in-the-middle attack. Despite their generic nature, we show that the attacks can be applied to improve the best known attacks on several concrete ciphers, including the full \({\hbox {AES}^{2}}\) (proposed at Eurocrypt 2012) and reduced-round LED-128 (proposed at CHES 2012).     

Locally Computable UOWHF with Linear Shrinkage

We study the problem of constructing locally computable universal one-way hash functions (UOWHFs) \(\mathcal {H}:\{0,1\}^n \rightarrow \{0,1\}^m\). A construction with constant output locality, where every bit of the output depends only on a constant number of bits of the input, was established by Applebaum et al. (SIAM J Comput 36(4):845–888, 2006). However, this construction suffers from two limitations: (1) it can only achieve a sublinear shrinkage of \(n-m=n^{1-\epsilon }\) and (2) it has a super-constant input locality, i.e., some inputs influence a large super-constant number of outputs. This leaves open the question of realizing UOWHFs with constant output locality and linear shrinkage of \(n-m= \epsilon n\), or UOWHFs with constant input locality and minimal shrinkage of \(n-m=1\). We settle both questions simultaneously by providing the first construction of UOWHFs with linear shrinkage, constant input locality and constant output locality. Our construction is based on the one-wayness of “random” local functions—a variant of an assumption made by Goldreich (Studies in Complexity and Cryptography, 76–87, 2011; ECCC 2010). Using a transformation of Ishai et al. (STOC, 2008), our UOWHFs give rise to a digital signature scheme with a minimal additive complexity overhead: signing n-bit messages with security parameter \(\kappa \) takes only \(O(n+\kappa )\) time instead of \(O(n\kappa )\) as in typical constructions. Previously, such signatures were only known to exist under an exponential hardness assumption. As an additional contribution, we obtain new locally computable hardness amplification procedures for UOWHFs that preserve linear shrinkage.     

A Dichotomy for Local Small-Bias Generators

We consider pseudorandom generators in which each output bit depends on a constant number of input bits. Such generators have appealingly simple structure: They can be described by a sparse input–output dependency graph \(G\) and a small predicate \(P\) that is applied at each output. Following the works of Cryan and Miltersen (MFCS’01) and by Mossel et al (STOC’03), we ask: which graphs and predicates yield “small-bias” generators (that fool linear distinguishers)? We identify an explicit class of degenerate predicates and prove the following. For most graphs, all non-degenerate predicates yield small-bias generators, \(f:\{0,1\}^n \rightarrow \{0,1\}^m\), with output length \(m = n^{1 + \epsilon }\) for some constant \(\epsilon > 0\). Conversely, we show that for most graphs, degenerate predicates are not secure against linear distinguishers, even when the output length is linear \(m=n+\Omega (n)\). Taken together, these results expose a dichotomy: Every predicate is either very hard or very easy, in the sense that it either yields a small-bias generator for almost all graphs or fails to do so for almost all graphs. As a secondary contribution, we attempt to support the view that small-bias is a good measure of pseudorandomness for local functions with large stretch. We do so by demonstrating that resilience to linear distinguishers implies resilience to a larger class of attacks.     

The Security of Tandem-DM in the Ideal Cipher Model

We prove that Tandem-DM, one of the two “classical” schemes for turning an n-bit blockcipher of 2n-bit key into a double-block-length hash function, has birthday-type collision resistance in the ideal cipher model. For \(n=128\), an adversary must make at least \(2^{120.87}\) blockcipher queries to achieve chance 0.5 of finding a collision. A collision resistance analysis for Tandem-DM achieving a similar birthday-type bound was already proposed by Fleischmann, Gorski and Lucks at FSE 2009. As we detail, however, the latter analysis is wrong, thus leaving the collision resistance of Tandem-DM as an open problem until now. Our analysis exhibits a novel feature in that we introduce a trick never used before in ideal cipher proofs. We also give an improved bound on the preimage security of Tandem-DM. For \(n=128\), we show that an adversary must make at least \(2^{245.99}\) blockcipher queries to achieve chance 0.5 of inverting a randomly chosen point in the range. Asymptotically, Tandem-DM is proved to be preimage resistant up to \(2^{2n}/n\) blockcipher queries. This bound improves upon the previous best bound of \({{\varOmega }}(2^n)\) queries and is optimal (ignoring log factors) since Tandem-DM has range of size \(2^{2n}\).     

Automata Evaluation and Text Search Protocols with Simulation-Based Security

This paper presents efficient protocols for securely computing the following two problems: (1) The fundamental problem of pattern matching. This problem is defined in the two-party setting, where party \(P_1\) holds a pattern and party \(P_2\) holds a text. The goal of \(P_1\) is to learn where the pattern appears in the text, without revealing it to \(P_2\) or learning anything else about \(P_2\)’s text. This problem has been widely studied for decades due to its broad applicability. We present several protocols for several notions of security. We further generalize one of our solutions to solve additional pattern matching-related problems of interest. (2) Our construction from above, in the malicious case, is based on a novel protocol for secure oblivious automata evaluation which is of independent interest. In this problem, party \(P_1\) holds an automaton and party \(P_2\) holds an input string, and they need to decide whether the automaton accepts the input, without learning anything else. Our protocol obtains full security in the face of malicious adversaries.     

How Many Queries are Needed to Distinguish a Truncated Random Permutation from a Random Function?

An oracle chooses a function f from the set of n bits strings to itself, which is either a randomly chosen permutation or a randomly chosen function. When queried by an n-bit string w, the oracle computes f(w), truncates the m last bits, and returns only the first \(n-m\) bits of f(w). How many queries does a querying adversary need to submit in order to distinguish the truncated permutation from the (truncated) function? In Hall et al. (Building PRFs from PRPs, Springer, Berlin, 1998) showed an algorithm for determining (with high probability) whether or not f is a permutation, using \(O(2^{\frac{m+n}{2}})\) queries. They also showed that if \(m < n/7\), a smaller number of queries will not suffice. For \(m > n/7\), their method gives a weaker bound. In this note, we first show how a modification of the approximation method used by Hall et al. can solve the problem completely. It extends the result to practically any m, showing that \(\varOmega (2^{\frac{m+n}{2}})\) queries are needed to get a non-negligible distinguishing advantage. However, more surprisingly, a better bound for the distinguishing advantage, which we can write, in a simplified form, as \(O\left( \min \left\{ \frac{q^2}{2^n},\,\frac{q}{2^{\frac{n+m}{2}}},\,1\right\} \right) ,\) can be obtained from a result of Stam published, in a different context, already in 1978. We also show that, at least in some cases, this bound is tight.     

Error performance of optically preamplified hybrid BPSK-PPM systems with transmitter and receiver imperfections

In this paper, we investigate the impact of the transmitter finite extinction ratio and the receiver carrier recovery phase offset on the error performance of two optically preamplified hybrid M-ary pulse position modulation (PPM) systems with coherent detection. The first system, referred to as PB-mPPM, combines polarization division multiplexing (PDM) with binary phase-shift keying and M-ary PPM, and the other system, referred to as PQ-mPPM, combines PDM with quadrature phase-shift keying and M-ary PPM. We provide new expressions for the probability of bit error for PB-mPPM and PQ-mPPM under finite extinction ratios and phase offset. The extinction ratio study indicates that the coherent systems PB-mPPM and PQ-mPPM outperform the direct-detection ones. It also shows that at \(P_b=10^{-9}\) PB-mPPM has a slight advantage over PQ-mPPM. For example, for a symbol size \(M=16\) and extinction ratio \(r=30\) dB, PB-mPPM requires 0.6 dB less SNR per bit than PQ-mPPM to achieve \(P_b=10^{-9}\). This investigation demonstrates that PB-mPPM is less complex and less sensitive to the variations of the offset angle \(\theta \) than PQ-mPPM. For instance, for \(M=16\), \(r=30\) dB, and \(\theta =10^{\circ }\) PB-mPPM requires 1.6 dB less than PQ-mPPM to achieve \(P_b=10^{-9}\). However, PB-mPPM enhanced robustness to phase offset comes at the expense of a reduced bandwidth efficiency when compared to PQ-mPPM. For example, for \(M=2\) its bandwidth efficiency is 60 % that of PQ-mPPM and \(\approx 86\,\%\) for \(M=1024\). For these reasons, PB-mPPM can be considered a reasonable design trade-off for M-ary PPM systems.     

Design and Performance Study of Dynamic Fractors in Any of the Four Quadrants

A fractor is a simple fractional-order system. Its transfer function is \(1/Fs^{\alpha }\); the coefficient, F, is called the fractance, and \(\alpha \) is called the exponent of the fractor. This paper presents how a fractor can be realized, using RC ladder circuit, meeting the predefined specifications on both F and \(\alpha \). Besides, commonly reported fractors have \(\alpha \) between 0 and 1. So, their constant phase angles (CPA) are always restricted between \(0^{\circ }\) and \(-90^{\circ }\). This work has employed GIC topology to realize fractors from any of the four quadrants, which means fractors with \(\alpha \) between \(-\)2 and +2. Hence, one can achieve any desired CPA between \(+180^{\circ }\) and \(-180^{\circ }\). The paper also exhibits how these GIC parameters can be used to tune the fractance of emulated fractors in real time, thus realizing dynamic fractors. In this work, a number of fractors are developed as per proposed technique, their impedance characteristics are studied, and fractance values are tuned experimentally.     

Electrical Transport Mechanisms and Photoconduction in Undoped Crystalline Flash-Evaporated Lead Iodide Thin Films

The flash-evaporation technique was utilized to fabricate undoped 1.35-μm and 1.2-μm thick lead iodide films at substrate temperatures \( T_{\rm{s}} = 150 \)°C and 200°C, respectively. The films were deposited onto a coplanar comb-like copper (Cu-) electrode pattern, previously coated on glass substrates to form lateral metal–semiconductor–metal (MSM-) structures. The as-measured constant-temperature direct-current (dc)-voltage (\( I\left( {V;T} \right) - V \)) curves of the obtained lateral coplanar Cu-PbI₂-Cu samples (film plus electrode) displayed remarkable ohmic behavior at all temperatures (\( T = 18 - 90\,^\circ {\hbox{C}} \)). Their dc electrical resistance \( R_{\rm{dc}} (T \)) revealed a single thermally-activated conduction mechanism over the temperature range with activation energy \( E_{\rm{act}} \approx 0.90 - 0.98 \,{\hbox{eV}} \), slightly less than half of room-temperature bandgap energy \( E_{\rm{g}} \) (\( \approx \,2.3\, {\hbox{eV}} \)) of undoped 2H-polytype PbI₂ single crystals. The undoped flash-evaporated \( {\hbox{PbI}}_{\rm{x}} \) thin films were homogeneous and almost stoichiometric (\( x \approx 1.87 \)), in contrast to findings on lead iodide films prepared by other methods, and were highly crystalline hexagonal 2H-polytypic structure with c-axis perpendicular to the surface of substrates maintained at \( T_{\rm{s}} { \gtrsim }150^\circ {\hbox{C}} \). Photoconductivity measurements made on these lateral Cu-PbI₂-Cu-structures under on–off visible-light illumination reveal a feeble photoresponse for long wavelengths (\( \lambda > 570\,{\hbox{nm}} \)), but a strong response to blue light of photon energy \( E_{\rm{ph}} \) \( \approx \,2.73 \, {\hbox{eV}} \) (\( > E_{\rm{g}} \)), due to photogenerated electron–hole (e–h) pairs via direct band-to-band electronic transitions. The constant-temperature/dc voltage current–time \( I\left( {T,V} \right) - t \) curves of the studied lateral PbI₂ MSM-structures at low ambient temperatures (\( T < 50^\circ {\hbox{C}} \)), after cutting off the blue-light illumination, exhibit two trapping mechanisms with different relaxation times. These strongly depend on \( V \) and \( T \), with thermally generated charge carriers in the PbI₂ mask photogenerated (e–h) pairs at higher temperatures.     

Mixed RF/FSO bidirectional system achieving spectral efficiency

The performance of two-way relay (TWR)-assisted mixed radio-frequency/free-space optical (RF/FSO) system is evaluated in this letter. The proposed system employs decode-and-forward relaying phenomena where the relay is basically an interfacing node between two source nodes \(S_1\) and \(S_2\), where \(S_1\) supports RF signal, while \(S_2\) supports FSO signal. The TWR-assisted system helps in achieving spectral efficiency by managing bidirectional communication in three time slots, thus maximizing the achievable rate of the network. The RF link is subjected to generalized \(\eta -\mu \) distribution, and the optical channel is affected by path loss, pointing errors and gamma–gamma (gg) distributed atmospheric turbulence. The novel expressions for the probability density function and cumulative distribution function of the equivalent end-to-end signal-to-noise ratio (SNR) are derived. Capitalizing on these derived statistics of end-to-end SNR, the expressions of outage probability and the bit-error rate for different binary modulations and M-ary modulations are provided.     

Discrete Logarithm Problems with Auxiliary Inputs

Let g be an element of prime order p in an abelian group, and let α∈? _p . We show that if g,g ^α , and \(g^{\alpha^{d}}\) are given for a positive divisor d of p?1, the secret key α can be computed deterministically in \(O(\sqrt{p/d}+\sqrt{d})\) exponentiations by using \(O(\max\{\sqrt{p/d},\sqrt{d}\})\) storage. If \(g^{\alpha^{i}}\) (i=0,1,2,…,2d) is given for a positive divisor d of p+1, α can be computed in \(O(\sqrt{p/d}+d)\) exponentiations by using \(O(\max\{\sqrt{p/d},\sqrt{d}\})\) storage. We also propose space-efficient but probabilistic algorithms for the same problem, which have the same computational complexities with the deterministic algorithm.As applications of the proposed algorithms, we show that the strong Diffie–Hellman problem and related problems with public \(g^{\alpha},\ldots,g^{\alpha^{d}}\) have computational complexity up to \(O(\sqrt{d}/\log p)\) less than the generic algorithm complexity of the discrete logarithm problem when p?1 (resp. p+1) has a divisor d≤p ^1/2 (resp. d≤p ^1/3). Under the same conditions for d, the algorithm is also applicable to recovering the secret key in \(O(\sqrt{p/d}\cdot \log p)\) for Boldyreva’s blind signature scheme and the textbook ElGamal scheme when d signature or decryption queries are allowed.     

A novel optimized neutrosophic <Emphasis Type="Italic">k</Emphasis>-means using genetic algorithm for skin lesion detection in dermoscopy images

This paper implemented a new skin lesion detection method based on the genetic algorithm (GA) for optimizing the neutrosophic set (NS) operation to reduce the indeterminacy on the dermoscopy images. Then, k-means clustering is applied to segment the skin lesion regions. Therefore, the proposed method is called optimized neutrosophic k-means (ONKM). On the training images set, an initial value of \(\alpha \) in the \(\alpha \)-mean operation of the NS is used with the GA to determine the optimized \(\alpha \) value. The Jaccard index is used as the fitness function during the optimization process. The GA found the optimal \(\alpha \) in the \(\alpha \)-mean operation as \(\alpha _{\mathrm{optimal}} =0.0014\) in the NS, which achieved the best performance using five fold cross-validation. Afterward, the dermoscopy images are transformed into the neutrosophic domain via three memberships, namely true, indeterminate, and false, using \(\alpha _{\mathrm{optimal}}\). The proposed ONKM method is carried out to segment the dermoscopy images. Different random subsets of 50 images from the ISIC 2016 challenge dataset are used from the training dataset during the fivefold cross-validation to train the proposed system and determine \(\alpha _{\mathrm{optimal}}\). Several evaluation metrics, namely the Dice coefficient, specificity, sensitivity, and accuracy, are measured for performance evaluation of the test images using the proposed ONKM method with \(\alpha _{\mathrm{optimal}} =0.0014\) compared to the k-means, and the \(\gamma \)–k-means methods. The results depicted the dominance of the ONKM method with \(99.29\pm 1.61\%\) average accuracy compared with k-means and \(\gamma \)–k-means methods.     

Fabrication of a <Emphasis Type="Italic">p</Emphasis>–<Emphasis Type="Italic">n</Emphasis> Heterojunction Using Topological Insulator Bi<Subscript>2</Subscript>Te<Subscript>3</Subscript>–Si and Its Annealing Response

A junction device has been fabricated by growing p-type Bi₂Te₃ topological insulator (TI) film on an n-type silicon (Si) substrate using a thermal evaporation technique. Annealing using different temperatures and durations was employed to improve the quality of the film, as confirmed by microstructural study using x-ray diffraction (XRD) analysis and atomic force microscopy (AFM). The p–n diode characteristics of the junction devices were studied, and the effect of annealing investigated. An improved diode characteristic with good rectification ratio (RR) was observed for devices annealed for longer duration. Reduction in the leakage or reverse saturation current (\( I_{\rm{R}} \)) was observed with increase in the annealing temperature. The forward-bias current (\( I_{\rm{F}} \)) dropped in devices annealed above 400°C. The best results were observed for the sample device annealed at 450°C for 3 h, showing figure of merit (FOM) of 0.621 with RR ≈ 504 and \( I_{\rm{R}} \) = 0.25 μA. In terms of ideality factor, the sample device annealed at 550°C for 2 h was found to be the best with \( n \) = 6.5, RR ≈ 52.4, \( I_{\rm{R}} \) = 0.61 μA, and FOM = 0.358. The majority-carrier density \( \left( {N_{\rm{A}} } \right) \) in the p-Bi₂Te₃ film of the heterojunction was found to be on the order of 10⁹/cm³ to 10¹¹/cm³, quite close to its intrinsic carrier concentration. These results are significant for fundamental understanding of device applications of TI materials as well as future applications in solar cells.     

From Private Simultaneous Messages to Zero-Information Arthur–Merlin Protocols and Back

Göös et al. (ITCS, 2015) have recently introduced the notion of Zero-Information Arthur–Merlin Protocols (\(\mathsf {ZAM}\)). In this model, which can be viewed as a private version of the standard Arthur–Merlin communication complexity game, Alice and Bob are holding a pair of inputs x and y, respectively, and Merlin, the prover, attempts to convince them that some public function f evaluates to 1 on (x, y). In addition to standard completeness and soundness, Göös et al., require a “zero-knowledge” property which asserts that on each yes-input, the distribution of Merlin’s proof leaks no information about the inputs (x, y) to an external observer. In this paper, we relate this new notion to the well-studied model of Private Simultaneous Messages (\(\mathsf {PSM}\)) that was originally suggested by Feige et al. (STOC, 1994). Roughly speaking, we show that the randomness complexity of \(\mathsf {ZAM}\) corresponds to the communication complexity of \(\mathsf {PSM}\) and that the communication complexity of \(\mathsf {ZAM}\) corresponds to the randomness complexity of \(\mathsf {PSM}\). This relation works in both directions where different variants of \(\mathsf {PSM}\) are being used. As a secondary contribution, we reveal new connections between different variants of \(\mathsf {PSM} \) protocols which we believe to be of independent interest. Our results give rise to better \(\mathsf {ZAM}\) protocols based on existing \(\mathsf {PSM}\) protocols, and to better protocols for conditional disclosure of secrets (a variant of \(\mathsf {PSM}\)) from existing \(\mathsf {ZAM} \)s.     

Stream Ciphers: A Practical Solution for Efficient Homomorphic-Ciphertext Compression

In typical applications of homomorphic encryption, the first step consists for Alice of encrypting some plaintext m under Bob’s public key \(\mathsf {pk}\) and of sending the ciphertext \(c = \mathsf {HE}_{\mathsf {pk}}(m)\) to some third-party evaluator Charlie. This paper specifically considers that first step, i.e., the problem of transmitting c as efficiently as possible from Alice to Charlie. As others suggested before, a form of compression is achieved using hybrid encryption. Given a symmetric encryption scheme \(\mathsf {E}\), Alice picks a random key k and sends a much smaller ciphertext \(c' = (\mathsf {HE}_{\mathsf {pk}}(k), \mathsf {E}_k(m))\) that Charlie decompresses homomorphically into the original c using a decryption circuit \(\mathcal {C}_{{\mathsf {E}^{-1}}}\). In this paper, we revisit that paradigm in light of its concrete implementation constraints, in particular \(\mathsf {E}\) is chosen to be an additive IV-based stream cipher. We investigate the performances offered in this context by Trivium, which belongs to the eSTREAM portfolio, and we also propose a variant with 128-bit security: Kreyvium. We show that Trivium, whose security has been firmly established for over a decade, and the new variant Kreyvium has excellent performance. We also describe a second construction, based on exponentiation in binary fields, which is impractical but sets the lowest depth record to \(8\) for \(128\)-bit security.     

Conductivity and Dielectric Relaxation Properties of Annealed Cr-Substituted Ni-Ferrite Nanoparticles

Nanocrystalline NiCr _x Fe_2?x O₄ spinel samples with x = 0.1 and 0.2 have been synthesized by coprecipitation method and annealed at 620°C and 1175°C for 4 h. Their electrical properties were investigated as functions of frequency in the range of 100 Hz to 100 kHz and temperature in the range of 308 K to 358 K. The dielectric constant (\( \varepsilon^{\prime } \)) and dielectric loss factor (\( {\hbox{tan}}\,\delta \)) appeared to decrease with increasing frequency, while the alternating-current (AC) conductivity (\( \sigma^{\prime } \)) increased. These dielectric parameters increased with increasing temperature. On the other hand, impedance spectroscopy gave Cole–Cole plots with only one semicircular arc for all the samples, indicating that the grain-boundary contribution was dominant in the conduction mechanism.     

Highly efficient nonlinear regression for big data with lexicographical splitting

This paper considers the problem of online piecewise linear regression for big data applications. We introduce an algorithm, which sequentially achieves the performance of the best piecewise linear (affine) model with optimal partition of the space of the regressor vectors in an individual sequence manner. To this end, our algorithm constructs a class of \(2^D\) sequential piecewise linear models over a set of partitions of the regressor space and efficiently combines them in the mixture-of-experts setting. We show that the algorithm is highly efficient with computational complexity of only \(O(mD^2)\), where m is the dimension of the regressor vectors. This efficient computational complexity is achieved by efficiently representing all of the \(2^D\) models using a “lexicographical splitting graph.” We analyze the performance of our algorithm without any statistical assumptions, i.e., our results are guaranteed to hold. Furthermore, we demonstrate the effectiveness of our algorithm over the well-known data sets in the machine learning literature with computational complexity fraction of the state of the art.