Information Security and Privacy

This work considers the problem of constructing efficient MDS matrices over the field $$\mathbb {F}_{2^m}$$. Efficiency is measured by the metric XOR count which was introduced by Khoo et al. in CHES 2014. Recently Sarkar and Syed (ToSC Vol. 1, 2016) have shown the existence of $$4\times 4$$ Toeplitz MDS matrices with optimal XOR counts. In this paper, we present some characterizations of Toeplitz matrices in light of MDS property. Our study leads to improving the known bounds of XOR counts of $$8\times 8$$ MDS matrices by obtaining Toeplitz MDS matrices with lower XOR counts over $$\mathbb {F}_{2^4}$$ and $$\mathbb {F}_{2^8}$$.

This work pursues the idea of multi-forgery attacks as introduced by Ferguson in 2002. We recoin reforgeability for the complexity of obtaining further forgeries once a first forgery has succeeded. First, we introduce a security notion for the integrity (in terms of reforgeability) of authenticated encryption schemes: $$j\text {-}\textsc {Int}\text {-}\textsc {CTXT}$$, which is derived from the notion INT-CTXT. Second, we define an attack scenario called $$j\text {-IV-Collision Attack}$$ ($$j\text {-IV-CA}$$), wherein an adversary tries to construct j forgeries provided a first forgery. The term collision in the name stems from the fact that we assume the first forgery to be the result from an internal collision within the processing of the associated data and/or the nonce. Next, we analyze the resistance to $$j\text {-IV-CAs}$$ of classical nonce-based AE schemes (CCM, CWC, EAX, GCM) as well as all 3rd-round candidates of the CAESAR competition. The analysis is done in the nonce-respecting and the nonce-ignoring setting. We find that none of the considered AE schemes provides full built-in resistance to $$j\text {-IV-CAs}$$. Based on this insight, we briefly discuss two alternative design strategies to resist $$j\text {-IV-CAs}$$.

Designing a cryptographic scheme with minimal components is a main theme in cryptographic research. Regarding double-block-length (DBL) hashing, feed-forward operations are used to avoid attacks from the blockcipher’s decryption function, whereas Özen and Stam showed that by using an iterated structure the feed-forward operations can be eliminated. Precisely, DBL iterated hash functions are collision resistant up to about $$2^n$$ query complexity when a blockcipher with n-bit blocks is used.Regarding the security of hash functions, pseudorandom-oracle (PRO) security, which is a stronger security notion than collision resistance, is an important security criterion of hash functions. Though several DBL hash functions with PRO security have been proposed, these use feed-forward operations. Note that Özen-Stam’s hash functions are not secure PROs due to the length-extension attack. Hence, it remains an open problem to design a PRO-secure DBL hash function without feed-forward operations.In this paper, we show that the feed-forward operations in the PRO-secure DBL hash function can be eliminated, that is, the simplified scheme is a secure PRO up to about $$2^n$$ query complexity. To our knowledge, this is the first time PRO-secure DBL hash function without feed-forward operations.

We present a new black-box mutational fuzzing technology and the corresponding tool which named FFFuzzer to improve the efficiency of fuzzing towards serveral given suspicious vulnerable code blocks.Our main intuition is by adjusting dynamic taint tracing and doing constraint verification, we can build 2 quite light filters to sieve the mutated input, which is the result of fuzzing’s mutation stage, thus FFFuzzer can runs under fuzzing level speed while enjoys better accuracy and schedulability. We collect 14 CVEs that can get enough details to generate a POC from the PDF rendering library poppler’s recent 10 years bug list as our benchmark to fully analyzes FFFuzzer’s real world challenges. And we build 2 mathematical models to do performance analysis. Analysis and experiments show although FFFuzzer has limitations on fuzzing metadata-related vulnerabilities and its efficiency also depends on seed file like traditional fuzzer, FFFuzzer has much powerful parallellism and it can run an order of magnitude faster than traditional fuzzer.

Third-party libraries are very prevalent in the development of Android Apps. However, the wide use of third-party libraries may cause potential violations on user’s privacy. In the original Android permission mechanism, host Apps share all permissions with their third-party libraries. Moreover, the details of most third-party libraries are not very clear to developers and malicious code may be contained. With privileges and malicious code, the attack may be conducted. In this paper, we present a novel privilege splitting mechanism for the third-party libraries in Android Apps. Different from other similar approaches, our system makes full use of the original permission mechanism to minimize the attack surface and the impact on Android system. Since the lightweight customization on Android, our system can be easily adapted to both Dalvik and ART (Android Runtime) virtual machines. We deployed a prototype on a real Android device and evaluated it’s compatibility, effectiveness and performance. The experiment results show that our system is compatible with existing Apps, splits the third-party libraries’ privileges effectively according to the given policies, and works well with negligible performance overhead.

SafeStack, initially proposed as a key component of Code Pointer Integrity (CPI), separates the program stack into two distinct regions to provide a safe region for sensitive code pointers. SafeStack can prevent buffer overflow attacks that overwrite sensitive code pointers, e.g., return addresses, to hijack control flow of the program, and has been incorporated into the Clang project of LLVM as a C-based language front-end. In this paper, we propose and implement SafeStack$$^+$$, an enhanced dual stack LLVM plug-in that further protects programs from data-flow hijacking. SafeStack$$^+$$ locates data flow sensitive variables on the unsafe stack that could potentially affect evaluation of branching conditions, and adds canaries of random sizes and values to them to detect malicious overwriting. We implement SafeStack$$^+$$ as a plug-in on LLVM 3.8 and perform extensive experiments to justify a lazy checking mechanism that adds on average 3.0% of runtime and 5.3% of memory overhead on top of SafeStack on SPEC CPU2006 benchmark programs. Our security analysis confirms that SafeStack$$^+$$ is effective in detecting data-flow hijacking attacks.

With the emergence of cloud computing services, computationally weak devices (Clients) can delegate expensive tasks to more powerful entities (Servers). This raises the question of verifying a result at a lower cost than that of recomputing it. This verification can be private, between the Client and the Server, or public, when the result can be verified by any third party. We here present protocols for the verification of matrix-vector multiplications, that are secure against malicious Servers. The obtained algorithms are essentially optimal in the amortized model: the overhead for the Server is limited to a very small constant factor, even in the sparse or structured matrix case; and the computational time for the public Verifier is linear in the dimension. Our protocols combine probabilistic checks and cryptographic operations, but minimize the latter to preserve practical efficiency. Therefore our protocols are overall more than two orders of magnitude faster than existing ones.

Current web applications incorporate third-party content hosted at different origins that offer a series of online services, as well as a suit of reusable libraries. Since those services and libraries constantly demand access to privacy-sensitive data for implementing normal operations, web developers and users must trust them not to induce privacy exfiltration. However, due to a common feature of all-or-nothing fashion, the security mechanisms of present web browsers are essentially insufficient for mitigating the risks caused by third-party code.This paper presents JSFfox, a JavaScript confinement system which enforces flexible information-flow policies for Firefox. Under JSFfox, not only the compartments but also the transferred message that contains the sensitive data are associated with information-flow labels, which can be tracked for enforcing substantial policies. We characterize a wide range of web applications for demonstrating the motivations and requirements of JSFfox’s design and implement the secure versions of those applications, which guarantees flexibility for developers as well as privacy for users. We develop a functional prototype of JSFfox built on top of Firefox, and the experimental results show that JSFfox has a fully backward-compatibility with current web and introduces a negligible overhead compared with the legacy Firefox.

The ongoing threat of malware has raised significant security and privacy concerns. Motivated by these issues, the cloud-based detection system is of increasing interest to detect large-scale malware as it releases the burden of client and improves the detection efficiency. However, most existing cloud-based detection systems overlook the data privacy protection during the malware detection. In this paper, we propose a cloud-based anti-malware system named PriMal, which protects the data privacy of both the cloud server and the client, while still achieves usable detection performance. In the PriMal, a newly designed private malware signature set intersection (PMSSI) protocol is involved to enable both the cloud server and client to achieve malware confirmation without revealing the data privacy in semi-honest model. Moreover, we propose the relevant signature engine to reduce the detection range and overhead. The experimental results show that PriMal offers a practical approach to achieve both usable malware detection and strong data privacy preservation.

Dynamic analysis plays an important role in analyzing malware variants which have used obfuscation, polymorphism and metamorphism techniques. Malware classification is an emerging approach for discriminating different malware families. However, existing malware classification methods have mediocre performance in small scale datasets and some machine learning algorithms have difficulties in handling imbalanced datasets. To solve these issues, we propose an ensemble learning based dynamic malware classification approach aiming at datasets of different scales. Additionally a novel feature selection method is presented to select features with strong discrimination power. In particular, we continue to explore issues in feature representation and feature selection. To verify the efficiency of our approach, we perform a series of comparative experiments with existing feature selection methods, commercial anti-malware tools and current malware classification techniques. The experimental results demonstrate that our approach can classify malware variants in high F1-score while imposing low classification time in datasets of different scales.

Aggregator oblivious encryption was proposed by Shi et al. (NDSS 2011), where an aggregator can compute an aggregated sum of data and is unable to learn anything else (aggregator obliviousness). Since the aggregator does not learn individual data that may reveal users’ habits and behaviors, several applications, such as privacy-preserving smart metering, have been considered. In this paper, we propose aggregator oblivious encryption schemes with public verifiability where the aggregator is required to generate a proof of an aggregated sum and anyone can verify whether the aggregated sum has been correctly computed by the aggregator. Though Leontiadis et al. (CANS 2015) considered the verifiability, their scheme requires an interactive complexity assumption to provide the unforgeability of the proof. Our schemes are proven to be unforgeable under a static and simple assumption (a variant of the Computational Diffie-Hellman assumption). Moreover, our schemes inherit the tightness of the reduction of the Benhamouda et al. scheme (ACM TISSEC 2016) for proving aggregator obliviousness. This tight reduction allows us to employ elliptic curves of a smaller order and leads to efficient implementation.

Privacy-preserving data mining technologies have been studied extensively, and as a general approach, du Pin Calmon and Fawaz have proposed a data distortion mechanism based on a statistical inference attack framework. This theory has been extended by Erdogdu et al. to time-series data and been applied to energy disaggregation of smart-meter data. However, their theory assumes both smart-meter data and sensitive appliance state information are available when applying the privacy-preserving mechanism, which is impractical in typical smart-meter systems where only the total power usage is available. In this paper, we extend their approach to enable the application of a privacy-utility tradeoff mechanism to such practical applications. Firstly, we define a system model which captures both the architecture of the smart-meter system and the practical constraints that the power usage of each appliance cannot be measured individually. This enables us to formalize the tradeoff problem more rigorously. Secondly, we propose a privacy-utility tradeoff mechanism for that system. We apply a linear Gaussian model assumption to the system and thereby reduce the problem of obtaining unobservable information to that of learning the system parameters. Finally, we conduct experiments of applying the proposed mechanism to the power usage data of an actual household. The experimental results show that the proposed mechanism works partly effectively; i.e., it prevents usage analysis of certain types of sensitive appliances while at the same time preserving that of non-sensitive appliances.

A wide range of applications can benefit from storing and managing data as graph structures, and graph theory algorithms can be used to solve various computing problems. In this paper, we propose a secure two-party private graph intersection protocol against semi-honest servers. The protocol allows a server and a client, each holding a private graph, to jointly compute the intersection of their graphs. The protocol utilizes homomorphic encryptions and a private set intersection sub-protocol to prevent information leakage during the process. At the end of the protocol, the server learns the graph intersection, and the client learns the vertex intersection.

The advancement of technology and the widespread usage of smart phones have made the collection of data from users easy and cost-effective, which allows the government, urban planner, and researchers to envision novel analysis. Along with the benefits, the shared data can bring serious privacy concerns as they reveal sensitive information about a user. Differential privacy has become an effective model for sharing privacy protected data with others. To facilitate users to protect the privacy of data before it leaves their personal devices, the concept of personal local differential privacy (PLDP) has been introduced for counting queries. We formulate PLDP for computing aggregates over numeric data. We present an efficient approach, private estimation of numeric aggregates (PENA), that guarantees PLDP of numeric data while computing an aggregate (e.g., the average or the minimum). We perform extensive experiments over a real dataset to show the effectiveness of PENA.

Private set operation (PSO) protocols provide a natural way of securely performing operations on data sets, such that crucial details of the input sets are not revealed. Such protocols have an ever-increasing number of practical applications, particularly when implementing privacy-preserving data mining schemes. Protocols for computing private set operations have been prevalent in multi-party computation literature over the past decade, and in the case of private set intersection (PSI), have become practically feasible to run in real applications. In contrast, other set operations such as union have received less attention from the research community, and the few existing designs are often limited in their feasibility. In this work we aim to fill this gap, and present a new technique using Bloom filter data structures and additive homomorphic encryption to develop the first private set union protocol with both linear computation and communication complexities. Moreover, we show how to adapt this protocol to give novel ways of computing PSI and private set intersection/union cardinality with only minor changes to the protocol computation. Our work resembles therefore a toolkit for scalable private set computation with linear complexities, and we provide a thorough experimental analysis that shows that the online phase of our designs is practical up to large set sizes.

Secret handshake allows a group of authorized users to establish a shared secret key and at the same time authenticate each other anonymously. A straightforward approach to design an unlinkable secret handshake protocol is to use either long-term certificate or one-time certificate provided by a trusted authority. However, how to detect the misusing of certificates by an insider adversary is a challenging security issue when using those approaches for unlinkable secret handshake. In this paper, we propose a novel k-time authenticated secret handshake (k-ASH) protocol where each authorized user is only allowed to use the credential for k times. We formalize security models, including session key security and anonymity, for k-ASH, and prove the security of the proposed protocol under some computational problems which are proved hard in the generic bilinear group model. The proposed protocol also achieved public traceability property if a user misuses the k-time credential.

Graphical passwords (GPs) that authenticate users using images are considered as one potential alternative to overcome the issues of traditional textual passwords. Based on the idea of utilizing an extremely large image, map-based GPs like PassMap and GeoPass have been developed, where users can select their secrets (geographical points) on a world map. In particular, PassMap allows users to select two locations on a map, while GeoPass reduces the number of locations to only one. At first glance, selecting one location is more vulnerable to attacks, while increasing the location number may add burden on users. In the literature, there is no research exploring this issue. Motivated by this, our purpose in this work is to explore the effect of location number (the number of geographical points) and compare two schemes of PassMap and GeoPass in terms of users’ performance and feedback. In this work, we develop a generic and open platform for realizing map-based schemes, and conduct a user study with 60 participants. The study reveals that selecting two locations would not degrade the scheme performance. Our effort aims to complement exiting research studies in this area.

The rapid growth in Internet and communication technology has facilitated an escalation in the exchange of digital multimedia content. This has resulted in an increase in copyright infringement, which has led to a greater demand for more robust copyright protection mechanisms. Digital watermarking is a means of detecting ownership and illegal use of digital products. This paper presents an approach to watermarking images by embedding QR code information in a digital image. The notion of the proposed scheme is to capitalize on the error correction mechanism that is inherent in the QR code structure, in order to increase the robustness of the watermark. By employing the QR code’s error correction mechanism, watermark information contained within a watermarked image can potentially be decoded even if the image has been altered or distorted by an adversary. This paper studies the characteristics of the proposed scheme and presents experiment results examining the robustness and security of the QR code watermarking approach.

Twisted Edwards curves are elliptic curves of the form $$ax^2 + y^2 = 1 + dx^2y^2$$ for some constants a and d. The curves are called complete Edwards curves for the special case when $$a=1$$ and d is not a square. Using complete Edwards curves for elliptic curve cryptography has many advantages as they have very efficient, complete, and unified point addition formula. In order to use complete Edwards curves for elliptic curve cryptography, we need to specify the curve as well as a point on the curve (typically of prime order). In this paper, we introduce some algorithms for generating complete Edwards curves over $$\mathbb {F}_p$$ with $$4p_0$$ number of points, where $$p_0$$ is a prime and p is a prime of user-specified bit length. These algorithms are able to generate a complete Edwards curve over $$\mathbb {F}_p$$ and a point of prime order on the curve in less than 3 (resp. 15, 35) minutes when p is a 256 (resp. 384, 512)-bit prime. These are much faster than the running time of the twisted Edwards curves generation algorithm proposed by Costello et al. in [4].

The GLV/GLS technique speeds up scalar multiplications on elliptic curves endowed with an efficiently computable endomorphism: a scalar multiplication by a full-size scalar becomes a double scalar multiplication by half-size scalars, which is significantly faster. However, this requires to first decompose the original scalar into an appropriate linear combination of half-size scalars using reduction in a low-dimensional lattice. Since a reduced basis of the lattice can be precomputed, this is typically fast, but it tends to leak a lot of side-channel information about the scalar.To avoid this issue, Aranha et al. (ASIACRYPT 2014) proposed to use “recomposition” instead, i.e. choose the two half-sized scalars at random in a suitable interval, defining a corresponding full-size scalar implicitly. If the statistical distance to uniform of the distribution of that scalar is negligible, the recomposition method is secure and avoids any of the leakage of GLV/GLS decomposition. The original paper obtained the statistical distance result for GLS curves of prime order. In this work, we extend their proof to GLS curves having a cofactor which can be written as a sum of two squares. This shows in particular how to obtain secure recomposition for (twisted) Edwards GLS curves and the fast binary curve GLS254 of Oliveira et al. (CHES 2013), as these curves have cofactor 4 and 2 respectively.

This paper presents new differential addition (i.e., the addition of two points with the known difference) and doubling formulas, as the core step in Montgomery scalar multiplication, for twisted Edwards curves. The formulas are provided with cost of $$5\mathbf {M}+4\mathbf {S}+1\mathbf {D}$$, $$3\mathbf {M}+7\mathbf {S}+1\mathbf {D}$$ and $$3\mathbf {M}+6\mathbf {S}+3\mathbf {D}$$ when the given difference point is in affine form. Here, $$\mathbf {M}, \mathbf {S}, \mathbf {D}$$ denote the costs of a field multiplication, a field squaring and a field multiplication by a constant, respectively.

Browsers can detect malicious websites that are provisioned with forged or fake TLS/SSL certificates. However, they are not so good at detecting these websites if they are provisioned with mistakenly (or maliciously) issued certificates. Google proposed certificate transparency which is an open framework to monitor and audit certificates in real time. Thereafter, a few other certificate transparency schemes have been proposed which can even handle revocation. All currently known constructions use Merkle hash trees and have proof size logarithmic in the number of certificates/domain owners. We present a new certificate transparency scheme with short (constant size) proofs. Our construction makes use of dynamic bilinear-map accumulators. The scheme has many desirable properties like efficient revocation, low verification cost and update costs comparable to the existing schemes. We provide proofs of security and evaluate the performance of our scheme.

It is practically impossible for users to memorize a large portfolio of strong and individual passwords for their online accounts. A solution is to generate passwords randomly and store them. Yet, storing passwords instead of memorizing them bears the risk of loss, e.g., in situations where the device on which the passwords are stored is damaged, lost, or stolen. This makes the creation of backups of the passwords indispensable. However, placing such backups at secure locations to protect them as well from loss and unauthorized access and keeping them up-to-date at the same time is an unsolved problem in practice.We present PASCO, a backup solution for passwords that solves this challenge. PASCO backups need not to be updated, even when the user’s password portfolio is changed. PASCO backups can be revoked without having physical access to them. This prevents password leakage, even when a user loses control over a backup. Additionally, we show how to extend PASCO to enable a fully controllable emergency access. It allows a user to give someone else access to his passwords in urgent situations.

We revisit the previous work of Arshad et al. (CODASPY 2014) about the security of redactable graph hashing schemes. Such schemes, introduced in a series of works by Devanbu et al. (DBSec 2000, CCS 2001, Algorithmica 2004), allow to hash graphs and to release sub graphs which can be verified against the original hash value. Arshad et al. introduce security notions for collision resistance and privacy of graphs, where the latter should capture the infeasibility to reconstruct the full graph from the hash value of a redacted one.We discuss here that the original security notions of Arshad et al. are too weak. Our argument is by virtue of intuitively insecure examples which are deemed secure according to their notion. We therefore present stronger security definitions. We also point out the differences in the privacy notions with respect to redactable and sanitizable schemes: In the former case anyone can produce verifiable data from the graph, whereas in the latter case only a designated party can. Sanitizable schemes allow for stronger privacy guarantees. We finally discuss instantiation possibilities for the various security notions.

Over the years Cellular Automata (CA) have been getting importance as a better crypto-primitives in designing stream ciphers. Wolfram identified Rule 30 as a powerful nonlinear function for cryptographic applications. However, Rule 30 CA is vulnerable against Meier and Staffelbach (MS) attack. This paper analyzes maximum period nonlinear CA (M-NHCA) which is shown to be secure against MS attack. We present a new design construction of a stream cipher employing the maximum period nonlinear CA and linear CA in conjunction with a rotational symmetric bent function. The proposed cipher has also been analyzed in aspect of almost all the known attacks in particular, the fault attack against which most of the eStream candidates like Grain-128 are vulnerable.

We explore the power of steganographic computation in an game-theoretic setting, where n stegocommunicants are attempting to complete a shared computation, and where a well-resourced censor is attempting to prevent the computation. For example, when collaboratively discovering the minimum value ($$\min _i x_i$$) in a public n-vector X, each stegocommunicant reads a randomly-selected element during each timestep. Each then transmits the index i of the smallest value they have seen to a randomly-selected collaborator. We prove that most stegocommunicants will learn the minimum value in $$O(\log n)$$ time, w.h.p., if at most 10% of their population is censored in any timestep. The censor in our model retains a copy of all intercepted messages, using this information to optimally select the targets of their censorship at the beginning of each timestep. Our model of stegocomputation is relevant to stegosystems in which: (1) the stegoencoding is determined by the address of the recipient, (2) the censor does not have sufficient computational resource to stegodecode more than a fixed fraction (nominally 10%) of the messages in flight, and (3) the censor cannot store any messages other than the ones it has stegodecoded.

The Prom Problem (TPP) represents a special class of matchmaking challenges that amplify the conflicting requirements of anonymity and authentication necessitating fair and privacy-enhanced matchmaking with identity-linked wishes (ILW). ILW are wishes that involve particular identities and are valid only if all associated parties have those same wishes. In this paper, we provide a feasibility evaluation of an implementation of a previously proposed algorithm for TPP along with a detailed characterization of its fairness, and present results from computation and communication specific performance testing. To quantify fairness, we propose the use of a fairness index that combines the concepts underlying Jain’s index with previously established definitions of fair matchmaking and details of the protocol. We also delineate upper and lower bounds for the fairness index values in this context and discuss its relationship to the participants’ confidence in the result. Finally, we present performance results that answer key questions thereby demonstrating the practicality of the solution both in terms of computational costs and communication overhead. The results quantify relative impacts of higher degrees of confidence and anonymity to guide identification of appropriate tradeoffs as the solution is applied to varying problem domains with security and privacy requirements comparable to TPP with ILW.

Control-Flow Integrity (CFI) is a popular method against control-flow hijacking attacks. For Commercial Off-the-Shelf (COTS) binaries, in order to reduce the runtime overhead, traditional works provide coarse-grained CFI and thus are context-insensitive. Because of the inaccuracy of the control-flow graphs (CFGs), they can hardly defend against elaborately designed attacks. We present a fully context-sensitive CFI method (FCCFI), which determines the validity of the control flow of the current execution path through checking the whole execution path instead of the single edge or partial edges in the execution path. FCCFI gathers the control-flow information in the offline phase and tracks the execution paths to gather the process-tracking information during runtime. Then it compares the control-flow information with the process-tracking information to check the validity of the control flow. We implement the system and evaluate the security of the implementation. The evaluation results show that FCCFI can defend against most common control-flow hijacking attacks.

The existing LWE-based dual-mode scheme could not fit the framework of dual-mode cryptosystem very well. In this paper, we give two solutions of constructing “full-fledged” dual-mode cryptosystems based on LWE. In our first construction, we give a modified “dual version” of Peikert et al.’s (Crypto’08) construction, in which the simulated public keys can be uniformly and randomly chosen just like the real ones, thus it can fit the framework of dual-mode cryptosystem very well. Then, our second construction gets rid of the lattice trapdoor, which is known as lacking of efficiency and is used in our first construction as well as Peikert et al.’s construction.

Cyber-security of their critical infrastructure is the current grand challenge facing nation-states. Development and research of cyber-security solutions for operational technology environments of critical infrastructure is being inhibited by the lack of publically available datasets. This paper provides a collection of labelled datasets containing attacks on the widely used STEP 7 (S7) protocol. To achieve this goal, we designed and executed a series of process-control attacks, using our physical critical infrastructure test-bed. The created labelled datasets, and the associated process logs, will directly aid in the development and assessment of intrusion detection systems (IDSs). We validate our dataset using Snort, configured with openly available S7 rule-sets.

This paper describes methods of solving certain parameters of the discrete logarithm problem with low Hamming weight product exponents. Our approach is shown to be applicable for a concrete analysis of the GPS identification scheme. To achieve this, we introduce the notion of parameters dependent splitting system which served as tools to yield two improved results. The first attains a lower time complexity over the current state of the art without any compromise in memory. The second achieves the first known attack of the GPS scheme in a time complexity of under $$2^{64}$$ at the expense of some added memory requirements over the former.