Browsing by Author "Matthews, Gretchen L."
Now showing 1 - 14 of 14
Results Per Page
Sort Options
- Codes from norm-trace curves: local recovery and fractional decodingMurphy, Aidan W. (Virginia Tech, 2022-04-04)Codes from curves over finite fields were first developed in the late 1970's by V. D. Goppa and are known as algebraic geometry codes. Since that time, the construction has been tailored to fit particular applications, such as erasure recovery and error correction using less received information than in the classical case. The Hermitian-lifted code construction of L'opez, Malmskog, Matthews, Piñero-González, and Wootters (2021) provides codes from the Hermitian curve over $F_{q^2}$ which have the same locality as the well-known one-point Hermitian codes but with a rate bounded below by a positive constant independent of the field size. However, obtaining explicit expressions for the code is challenging. In this dissertation, we consider codes from norm-trace curves, which are a generalization of the Hermitian curve. We develop norm-trace-lifted codes and demonstrate an explicit basis of the codes. We then consider fractional decoding of codes from norm-trace curves, extending the results obtained for codes from the Hermitian curve by Matthews, Murphy, and Santos (2021).
- Computing the trace of an endomorphism of a supersingular elliptic curveWills, Michael Thomas (Virginia Tech, 2021-06-10)We provide an explicit algorithm for computing the trace of an endomorphism of an elliptic curve which is given by a chain of small-degree isogenies. We analyze its complexity, determining that if the length of the chain, the degree of the isogenies, and the log of the field-size are all O(n), the trace of the endomorphism can be computed in O(n⁶) bit operations. This makes explicit a theorem of Kohel which states that such a polynomial time algorithm exists. The given procedure is based on Schoof's point-counting algorithm.
- Deciding if a Genus 1 Curve has a Rational PointSwanson, Nicolas J. Brennan (Virginia Tech, 2024-05-23)Many sources suggest a folklore procedure to determine if a smooth curve of genus 1 has a rational point. This procedure terminates conditionally on the Tate-Shafarevich conjecture. In this thesis, we provide an exposition for this procedure, making several steps explicit. In some instances, we also provide MAGMA implementations of the subroutines. In particular, we give an algorithm to determine if a smooth, genus 1 curve of arbitrary degree is locally soluble, we compute its Jacobian, and we give an exposition for descent in our context. Additionally, we prove there exists an algorithm to decide if smooth, genus 1 curve has a rational point if and only if there exists an algorithm to compute the Mordeil-Weil group of an elliptic curve.
- Fractional decoding of r-Hermitian codesMatthews, Gretchen L.; Murphy, Aidan W.; Santos, Welington (Academic Press – Elsevier, 2023-12)In this paper, we present a fractional decoding algorithm for a new family of codes which are constructed from the Hermitian curve, called r-Hermitian codes. These codes of length n are defined over an extension field Fq2l of Fq2 and the fractional decoding algorithms that we present are algorithms for error correction that use only αln symbols of a subfield of size q2 as input into the decoding algorithm, where α<1, meaning a fraction of the subsymbols that are typically utilized. We demonstrate that collaborative decoding of interleaved codes supports fractional decoding of the r-Hermitian codes, allowing for improved bounds on the fractional decoding radius.
- Graph-based and algebraic codes for error-correction and erasure recoveryKshirsagar, Rutuja Milind (Virginia Tech, 2022-02-25)Expander codes are sparse graph-based codes with good decoding algorithms. We present a linear-time decoding algorithm for (C,D, alpha, gamma) expander codes based on graphs with any expansion factor given that the minimum distances of the inner codes are bounded below. We also design graph-based codes with hierarchical locality. Such codes provide tiered recovery, depending on the number of erasures. A small number of erasures may be handled by only accessing a few other symbols, allowing for small locality, while larger number may involve a greater number of symbols. This provides an alternative to requiring disjoint repair groups. We also consider availability in this context, relying on the interplay between inner codes and the Tanner graph. We define new families of algebraic geometry codes for the purpose of code-based cryptography. In particular, we consider twisted Hermitian codes, twisted codes from a quotient of the Hermitian curve; and twisted norm-trace codes. These codes have Schur squares with large dimensions and hence could be considered as potential replacements for Goppa codes in the McEliece cryptosytem. However, we study the code-based cryptosystem based on twisted Hermitian codes and lay foundations for a potential attack on such a cryptosystem.
- Highly Robust and Efficient Estimators of Multivariate Location and Covariance with Applications to Array Processing and Financial Portfolio OptimizationFishbone, Justin Adam (Virginia Tech, 2021-12-21)Throughout stochastic data processing fields, mean and covariance matrices are commonly employed for purposes such as standardizing multivariate data through decorrelation. For practical applications, these matrices are usually estimated, and often, the data used for these estimates are non-Gaussian or may be corrupted by outliers or impulsive noise. To address this, robust estimators should be employed. However, in signal processing, where complex-valued data are common, the robust estimation techniques currently employed, such as M-estimators, provide limited robustness in the multivariate case. For this reason, this dissertation extends, to the complex-valued domain, the high-breakdown-point class of multivariate estimators called S-estimators. This dissertation defines S-estimators in the complex-valued context, and it defines their properties for complex-valued data. One major shortcoming of the leading high-breakdown-point multivariate estimators, such as the Rocke S-estimator and the smoothed hard rejection MM-estimator, is that they lack statistical efficiency at non-Gaussian distributions, which are common with real-world applications. This dissertation proposes a new tunable S-estimator, termed the Sq-estimator, for the general class of elliptically symmetric distributions—a class containing many common families such as the multivariate Gaussian, K-, W-, t-, Cauchy, Laplace, hyperbolic, variance gamma, and normal inverse Gaussian distributions. This dissertation demonstrates the diverse applicability and performance benefits of the Sq-estimator through theoretical analysis, empirical simulation, and the processing of real-world data. Through analytical and empirical means, the Sq-estimator is shown to generally provide higher maximum efficiency than the leading maximum-breakdown estimators, and it is also shown to generally be more stable with respect to initial conditions. To illustrate the theoretical benefits of the Sq for complex-valued applications, the efficiencies and influence functions of adaptive minimum variance distortionless response (MVDR) beamformers based on S- and M-estimators are compared. To illustrate the finite-sample performance benefits of the Sq-estimator, empirical simulation results of multiple signal classification (MUSIC) direction-of-arrival estimation are explored. Additionally, the optimal investment of real-world stock data is used to show the practical performance benefits of the Sq-estimator with respect to robustness to extreme events, estimation efficiency, and prediction performance.
- Linear Exact Repair Schemes for Distributed Storage and Secure Distributed Matrix MultiplicationValvo, Daniel William (Virginia Tech, 2023-05-08)In this thesis we develop exact repair schemes capable of repairing or circumventing unavailable servers of a distributed network in the context of distributed storage and secure distributed matrix multiplication. We develop the (Λ, Γ, W, ⊙)-exact repair scheme framework for discussing both of these contexts and develop a multitude of explicit exact repair schemes utilizing decreasing monomial-Cartesian codes (DMC codes). Specifically, we construct novel DMC codes in the form of augmented Cartesian codes and rectangular monomial-Cartesian codes, as well as design exact repair schemes utilizing these constructions inspired by the schemes from Guruswami and Wootters [16] and Chen and Zhang [6]. In the context of distributed storage we demonstrate the existence of both high rate and low bandwidth systems based on these schemes, and we develop two methods to extend them to the l-erasure case. Additionally, we develop a family of hybrid schemes capable of attaining high rates, low bandwidths, and a balance in between which proves to be competitive compared to existing schemes. In the context of secure distributed matrix multiplication we develop similarly impactful schemes which have very competitive communication costs. We also construct an encoding algorithm based on multivariate interpolation and prove it is T-secure.
- Miki Images of Quantum Toroidal Algebra Generators in the Shuffle AlgebraQuinlan, Isis Angelina Marie (Virginia Tech, 2020-06-04)Through composition of isomorphisms from results by Miki and Negut, this paper seeks to simplify calculations of the images of generators of the quantum toroidal algebra. We will be working in the small shuffle algebra, which is isomorphic to the positive part of the quantum toroidal algebra. There, we will be computing commutators, which are equal to images under the Miki automorphism, though are much simpler to compute.
- Multishot Capacity of Adversarial NetworksShapiro, Julia Marie (Virginia Tech, 2024-05-08)Adversarial network coding studies the transmission of data over networks affected by adversarial noise. In this realm, the noise is modeled by an omniscient adversary who is restricted to corrupting a proper subset of the network edges. In 2018, Ravagnani and Kschischang established a combinatorial framework for adversarial networks. The study was recently furthered by Beemer, Kilic and Ravagnani, with particular focus on the one-shot capacity: a measure of the maximum number of symbols that can be transmitted in a single use of the network without errors. In this thesis, both bounds and capacity-achieving schemes are provided for families of adversarial networks in multiple transmission rounds. We also demonstrate scenarios where we transmit more information using a network multiple times for communication versus using the network once. Some results in this thesis are joint work with Giuseppe Cotardo (Virginia Tech), Gretchen Matthews (Virginia Tech) and Alberto Ravagnani (Eindhoven University of Technology).
- Polar Coding in Certain New Transmission EnvironmentsTimmel, Stephen Nicholas (Virginia Tech, 2023-05-15)Polar codes, introduced by Arikan in 2009, have attracted considerable interest as an asymptotically capacity-achieving code with sufficient performance advantages to merit inclusion in the 5G standard. Polar codes are constructed directly from an explicit model of the communication channel, so their performance is dependent on a detailed understanding of the transmission environment. We partially remove a basic assumption in coding theory that channels are identical and independent by extending polar codes to several types of channels with memory, including periodic Markov processes and Information Regular processes. In addition, we consider modifications to the polar code construction so that the inclusion of a shared secret in the frozen set naturally produces encryption via one-time pad. We describe one such modification in terms of the achievable frozen sets which are compatible with the polar code automorphism group. We then provide a partial characterization of these frozen sets using an explicit construction for the Linear Extension Diameter of channel entropies.
- Repairing Cartesian Codes with Linear Exact Repair SchemesValvo, Daniel William (Virginia Tech, 2020-06-10)In this paper, we develop a scheme to recover a single erasure when using a Cartesian code,in the context of a distributed storage system. Particularly, we develop a scheme withconsiderations to minimize the associated bandwidth and maximize the associateddimension. The problem of recovering a missing node's data exactly in a distributedstorage system is known as theexact repair problem. Previous research has studied theexact repair problem for Reed-Solomon codes. We focus on Cartesian codes, and show wecan enact the recovery using a linear exact repair scheme framework, similar to the oneoutlined by Guruswami and Wooters in 2017.
- Security of Lightweight Cryptographic PrimitivesVennos, Amy Demetra Geae (Virginia Tech, 2021-06-10)Internet-of-Things (IoT) devices are increasing in popularity due to their ability to help automate many aspects of daily life while performing these necessary duties on billions of low-power appliances. However, the perks of these small devices also come with additional constraints to security. Security always has been an issue with the rise of cryptographic backdoors and hackers reverse engineering the security protocols within devices to reveal the original state that was encrypted. Security researchers have done much work to prevent attacks with high power algorithms, such as the international effort to develop the current Advanced Encryption Standard (AES). Unfortunately, IoT devices do not typically have the computational resources to implement high-power algorithms such as AES, and must rely on lightweight primitives such as pseudorandom number generators, or PRNGs.This thesis explores the effectiveness, functionality, and use of PRNGs in different applications. First, this thesis investigates the confidentiality of a single-stage residue number system PRNG, which has previously been shown to provide extremely high quality outputs for simulation and digital communication applications when evaluated through traditional techniques like the battery of statistical tests used in the NIST Random Number Generation and DIEHARD test suites or in using Shannon entropy metrics. In contrast, rather than blindly performing statistical analyses on the outputs of the single-stage RNS PRNG, this thesis provides both white box and black box analyses that facilitate reverse engineering of the underlying RNS number generation algorithm to obtain the residues, or equivalently the key, of the RNS algorithm. This thesis develops and demonstrate a conditional entropy analysis that permits extraction of the key given a priori knowledge of state transitions as well as reverse engineering of the RNS PRNG algorithm and parameters (but not the key) in problems where the multiplicative RNS characteristic is too large to obtain a priori state transitions. This thesis then discusses multiple defenses and perturbations for the RNS system that defeat the original attack algorithm, including deliberate noise injection and code hopping. We present a modification to the algorithm that accounts for deliberate noise, but rapidly increases the search space and complexity. Lastly, a comparison of memory requirements and time required for the attacker and defender to maintain these defenses is presented. The next application of PRNGs is in building a translation for binary PRNGs to non-binary uses like card shuffling in a casino. This thesis explores a shuffler algorithm that utilizes RNS in Fisher-Yates shuffles, and that calls for inputs from any PRNG. Entropy is lost through this algorithm by the use of PRNG in lieu of TRNG and by its RNS component: a surjective mapping from a large domain of size $2^J$ to a substantially smaller set of arbitrary size $n$. Previous research on the specific RNS mapping process had developed a lower bound on the Shannon entropy loss from such a mapping, but this bound eliminates the mixed-radix component of the original formulation. This thesis calculates a more precise formula which takes into account the radix, $n$. This formulation is later used to specify the optimal parameters to simulate the shuffler with different test PRNGs. After implementing the shuffler with PRNGs with varying output entropies, the thesis examines the output value frequencies to discuss if utilizing PRNG is a feasible alternative for casinos to the higher-cost TRNG.
- Squares of bivariate Goppa codesBasener, Wesley; Cotardo, Giuseppe; Krebs, Jenna; Liu, Yihan; Matthews, Gretchen L.; Ufferman, Eric (2023-10-13)In this paper, we study squares of bivariate Goppa codes, as they relate to the Goppa code distinguishing problem for bivariate Goppa codes. Introduced in 2021, multivariate Goppa codes are subfield subcodes of certain evaluation codes defined by evaluating polynomials in m variables. The evaluation codes are augmented Cartesian codes, a generalization of Reed-Muller codes. Classical Goppa codes are obtained by taking m=1. The multivariate Goppa code distinguishing problem is to distinguish efficiently a generator matrix of a multivariate Goppa code from a randomly drawn one. Because a randomly drawn code has a large square, codes with small squares may be considered distinguishable, revealing structure which facilitates private key recovery in a code-based cryptosystem.
- Twisted Hermitian CodesAllen, Austin; Blackwell, Keller; Fiol, Olivia; Kshirsagar, Rutuja; Matsick, Bethany; Matthews, Gretchen L.; Nelson, Zoe (MDPI, 2020-12-26)We define a family of codes called twisted Hermitian codes, which are based on Hermitian codes and inspired by the twisted Reed–Solomon codes described by Beelen, Puchinger, and Nielsen. We demonstrate that these new codes can have high-dimensional Schur squares, and we identify a subfamily of twisted Hermitian codes that achieves a Schur square dimension close to that of a random linear code. Twisted Hermitian codes allow one to work over smaller alphabets than those based on Reed–Solomon codes of similar lengths.