BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

David Karpuk

David Karpuk appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITmath.NTmath.AGCryptography and Securitymath.CO

Catalog footprint

What is connected

20works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

20 published item(s)

preprint2024arXiv

Modular Polynomial Codes for Secure and Robust Distributed Matrix Multiplication

We present Modular Polynomial (MP) Codes for Secure Distributed Matrix Multiplication (SDMM). The construction is based on the observation that one can decode certain proper subsets of the coefficients of a polynomial with fewer evaluations than is necessary to interpolate the entire polynomial. We also present Generalized Gap Additive Secure Polynomial (GGASP) codes. Both MP and GGASP codes are shown experimentally to perform favorably in terms of recovery threshold when compared to other comparable polynomials codes for SDMM which use the grid partition. Both MP and GGASP codes achieve the recovery threshold of Entangled Polynomial Codes for robustness against stragglers, but MP codes can decode below this recovery threshold depending on the set of worker nodes which fails. The decoding complexity of MP codes is shown to be lower than other approaches in the literature, due to the user not being tasked with interpolating an entire polynomial.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

GASP Codes for Secure Distributed Matrix Multiplication

We consider the problem of secure distributed matrix multiplication (SDMM) in which a user wishes to compute the product of two matrices with the assistance of honest but curious servers. We construct polynomial codes for SDMM by studying a combinatorial problem on a special type of addition table, which we call the degree table. The codes are based on arithmetic progressions, and are thus named GASP (Gap Additive Secure Polynomial) Codes. GASP Codes are shown to outperform all previously known polynomial codes for secure distributed matrix multiplication in terms of download rate.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Notes on Communication and Computation in Secure Distributed Matrix Multiplication

We consider the problem of secure distributed matrix multiplication in which a user wishes to compute the product of two matrices with the assistance of honest but curious servers. In this paper, we answer the following question: Is it beneficial to offload the computations if security is a concern? We answer this question in the affirmative by showing that by adjusting the parameters in a polynomial code we can obtain a trade-off between the user's and the servers' computational time. Indeed, we show that if the computational time complexity of an operation in $\mathbb{F}_q$ is at most $\mathcal{Z}_q$ and the computational time complexity of multiplying two $n\times n$ matrices is $\mathcal{O}(n^ω\mathcal{Z}_q)$ then, by optimizing the trade-off, the user together with the servers can compute the multiplication in $\mathcal{O}(n^{4-\frac{6}{ω+1}} \mathcal{Z}_q)$ time. We also show that if the user is only concerned in optimizing the download rate, a common assumption in the literature, then the problem can be converted into a simple private information retrieval problem by means of a scheme we call Private Oracle Querying. However, this comes at large upload and computational costs for both the user and the servers.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Towards Practical Private Information Retrieval from MDS Array Codes

Private information retrieval (PIR) is the problem of privately retrieving one out of $M$ original files from $N$ severs, i.e., each individual server learns nothing about the file that the user is requesting. Usually, the $M$ files are replicated or encoded by a maximum distance separable (MDS) code and then stored across the $N$ servers. Compared to mere replication, MDS coded servers can significantly reduce the storage overhead. Particularly, PIR from minimum storage regenerating (MSR) coded servers can simultaneously reduce the repair bandwidth when repairing failed servers. Existing PIR schemes from MSR coded servers either require large sub-packetization levels or are not capacity-achieving. In this paper, a PIR protocol from MDS array codes is proposed, subsuming PIR from MSR coded servers as a special case. Particularly, the case of non-colluding, honest-but-curious servers is considered. The retrieval rate of the new PIR protocol achieves the capacity of PIR from MDS/MSR coded servers. By choosing different MDS array codes, the new PIR protocol can have some advantages when compared with existing protocols, e.g., 1) small sub-packetization, 2) (near-) optimal repair bandwidth, 3) implementable over the binary field $\mathbf{F}_2$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Well-Rounded Lattices: Towards Optimal Coset Codes for Gaussian and Fading Wiretap Channels

The design of lattice coset codes for wiretap channels is considered. Bounds on the eavesdropper's correct decoding probability and information leakage are first revisited. From these bounds, it is explicit that both the information leakage and error probability are controlled by the average flatness factor of the eavesdropper's lattice, which we further interpret geometrically. It is concluded that the minimization of the (average) flatness factor of the eavesdropper's lattice leads to the study of well-rounded lattices, which are shown to be among the optimal in order to achieve these minima. Constructions of some well-rounded lattices are also provided.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Information Bounds and Flatness Factor Approximation for Fading Wiretap MIMO Channels

In this article, the design of secure lattice coset codes for general wireless channels with fading and Gaussian noise is studied. Recalling the eavesdropper's probability and information bounds, a variant of the latter is given from which it is explicitly seen that both quantities are upper bounded by (increasing functions of) the expected flatness factor of the faded lattice related to the eavesdropper. By making use of a recently developed approximation of the theta series of a lattice, it is further shown how the average flatness factor can be approximated numerically. In particular, based on the numerical computations, the average flatness factor not only bounds but also orders correctly the performance of different lattices.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Locally Diverse Constellations from the Special Orthogonal Group

To optimize rotated, multidimensional constellations over a single-input, single-output Rayleigh fading channel, a family of rotation matrices is constructed for all dimensions which are a power of 2. This family is a one-parameter subgroup of the group of rotation matrices, and is located using a gradient descent scheme on this Lie group. The parameter defining the family is chosen to optimize the cutoff rate of the constellation. The optimal rotation parameter is computed explicitly for low signal-to-noise ratios. These rotations outperform full-diversity algebraic rotations in terms of cutoff rate at low SNR (signal-to-noise ratio) and bit error rate at high SNR in dimension $n = 4$. However, a QAM (quadrature amplitude modulation) constellation rotated by such a matrix lacks full diversity, in contrast with the conventional wisdom that good signal sets exhibit full diversity. A new notion of diversity, referred to as local diversity, is introduced to attempt to account for this behavior. Roughly, a locally fully diverse constellation is fully diverse only in small neighborhoods. A local variant of the minimum product distance is also introduced and is shown experimentally to be a superior predictor of constellation performance than the minimum product distance in dimension $n = 4$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Perfect Secrecy in Physical Layer Network Coding Systems from Structured Interference

Physical layer network coding (PNC) has been proposed for next generation networks. In this contribution, we investigate PNC schemes with embedded perfect secrecy by exploiting structured interference in relay networks with two users and a single relay. In a practical scenario where both users employ finite and uniform signal input distributions we propose upper bounds (UBs) on the achievable perfect secrecy rates and make these explicit when PAM modems are used. We then describe two simple, explicit encoders that can achieve perfect secrecy rates close to these UBs with respect to an untrustworthy relay in the single antenna and single relay setting. Lastly, we generalize our system to a MIMO relay channel where the relay has more antennas than the users and optimal precoding matrices which maintain a required secrecy constraint are studied. Our results establish that the design of PNC transmission schemes with enhanced throughput and guaranteed data confidentiality is feasible in next generation systems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Low-Complexity Message Recovery Method for Compute-and-Forward Relaying

The Compute-and-Forward relaying strategy achieves high computation rates by decoding linear combinations of transmitted messages at intermediate relays. However, if the involved relays independently choose which combinations of the messages to decode, there is no guarantee that the overall system of linear equations is solvable at the destination. In this article it is shown that, for a Gaussian fading channel model with two transmitters and two relays, always choosing the combination that maximizes the computation rate often leads to a case where the original messages cannot be recovered. It is further shown that by limiting the relays to select from carefully designed sets of equations, a solvable system can be guaranteed while maintaining high computation rates. The proposed method has a constant computational complexity and requires no information exchange between the relays.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Hybrid Channel Pre-Inversion and Interference Alignment Strategies

In this paper we consider strategies for MIMO interference channels which combine the notions of interference alignment and channel pre-inversion. Users collaborate to form data-sharing groups, enabling them to clear interference within a group, while interference alignment is employed to clear interference between groups. To improve the capacity of our schemes at finite SNR, we propose that the groups of users invert their subchannel using a regularized Tikhonov inverse. We provide a new sleeker derivation of the optimal Tikhonov parameter, and use random matrix theory to provide an explicit formula for the SINR as the size of the system increases, which we believe is a new result. For every possible grouping of K = 4 users each with N = 5 antennas, we completely classify the degrees of freedom available to each user when using such hybrid schemes, and construct explicit interference alignment strategies which maximize the sum DoF. Lastly, we provide simulation results which compute the ergodic capacity of such schemes.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Reduced Complexity Decoding of n x n Algebraic Space-Time Codes

Algebraic space-time coding allows for reliable data exchange across fading multiple-input multiple-output channels. A powerful technique for decoding space-time codes in Maximum-Likelihood (ML) decoding, but well-performing and widely-used codes such as the Golden code often suffer from high ML-decoding complexity. In this article, a recursive algorithm for decoding general algebraic space-time codes of arbitrary dimension is proposed, which reduces the worst-case decoding complexity from $O(|S|^{n^2})$ to $O(|S|^n)$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Algebraic Codes and a New Physical Layer Transmission Protocol for Wireless Distributed Storage Systems

In a wireless storage system, having to communicate over a fading channel makes repair transmissions prone to physical layer errors. The first approach to combat fading is to utilize the existing optimal space-time codes. However, it was recently pointed out that such codes are in general too complex to decode when the number of helper nodes is bigger than the number of antennas at the newcomer or data collector. In this paper, a novel protocol for wireless storage transmissions based on algebraic space-time codes is presented in order to improve the system reliability while enabling feasible decoding. The diversity-multiplexing gain tradeoff (DMT) of the system together with sphere-decodability even with low number of antennas are used as the main design criteria, thus naturally establishing a DMT-complexity tradeoff. It is shown that the proposed protocol outperforms the simple time-division multiple access (TDMA) protocol, while still falling behind the optimal DMT.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Degrees of Freedom and Secrecy in Wireless Relay Networks

We translate the problem of designing a secure communications protocol for several users communicating through a relay in a wireless network into understanding certain subvarieties of products of Grassmannians. We calculate the dimension of these subvarieties and provide various results concerning their defning equations. When the relay and all of the users have the same number of antennas, this approach places fundamental limits on the amount of data that can be passed through such a network.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Multi-Dimensional and Non-Uniform Constellation Optimization via the Special Orthogonal Group

With the goal of optimizing the CM capacity of a finite constellation over a Rayleigh fading channel, we construct for all dimensions which are a power of 2 families of rotation matrices which optimize a certain objective function controlling the CM capacity. Our construction does not depend on any assumptions about the constellation, dimension, or signal-to-noise ratio. We confirm the benefits of our construction for uniform and non-uniform constellations at a large range of SNR values through numerous simulations. We show that in two and four dimensions one can obtain a further potential increase in CM capacity by jointly considering non-uniform and rotated constellations.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Node Repair for Distributed Storage Systems over Fading Channels

Distributed storage systems and associated storage codes can efficiently store a large amount of data while ensuring that data is retrievable in case of node failure. The study of such systems, particularly the design of storage codes over finite fields, assumes that the physical channel through which the nodes communicate is error-free. This is not always the case, for example, in a wireless storage system. We study the probability that a subpacket is repaired incorrectly during node repair in a distributed storage system, in which the nodes communicate over an AWGN or Rayleigh fading channels. The asymptotic probability (as SNR increases) that a node is repaired incorrectly is shown to be completely determined by the repair locality of the DSS and the symbol error rate of the wireless channel. Lastly, we propose some design criteria for physical layer coding in this scenario, and use it to compute optimally rotated QAM constellations for use in wireless distributed storage systems.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Probability Estimates for Fading and Wiretap Channels from Ideal Class Zeta Functions

In this paper, new probability estimates are derived for ideal lattice codes from totally real number fields using ideal class Dedekind zeta functions. In contrast to previous work on the subject, it is not assumed that the ideal in question is principal. In particular, it is shown that the corresponding inverse norm sum depends not only on the regulator and discriminant of the number field, but also on the values of the ideal class Dedekind zeta functions. Along the way, we derive an estimate of the number of elements in a given ideal with a certain algebraic norm within a finite hypercube. We provide several examples which measure the accuracy and predictive ability of our theorems.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Space-Time Storage Codes for Wireless Distributed Storage Systems

Distributed storage systems (DSSs) have gained a lot of interest recently, thanks to their robustness and scalability compared to single-device storage. Majority of the related research has exclusively concerned the network layer. At the same time, the number of users of, e.g., peer-to-peer (p2p) and device-to-device (d2d) networks as well as proximity based services is growing rapidly, and the mobility of users is considered more and more important. This motivates, in contrast to the existing literature, the study of the physical layer functionality of wireless distributed storage systems. In this paper, we take the first step towards protecting the storage repair transmissions from physical layer errors when the transmission takes place over a fading channel. To this end, we introduce the notion of a space-time storage code, drawing together the aspects of network layer and physical layer functionality and resulting in cross-layer robustness. It is also pointed out that existing space-time codes are too complex to be utilized in storage networks when the number of helpers involved is larger than the number of receive antennas at the newcomer or data collector, hence creating a call for less complex transmission protocols.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Strong Secrecy in Wireless Network Coding Systems with M-QAM Modulators

We investigate the possibility of developing physical layer network coding (PNC) schemes with embedded strong secrecy based on standard QAM modulators. The proposed scheme employs a triple binning approach at the QAM front-end of the wireless PNC encoders. A constructive example of a strong secrecy encoder is presented when a BPSK and an 8-PAM modulator are employed at the wireless transmitters and generalized to arbitrary M-QAM modulators, assuming channel inversion is attainable at the first cycle of the transmission. Our preliminary investigations demonstrate the potential of using such techniques to increase the throughput while in parallel not compromise the confidentiality of the exchanged data.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Nonasymptotic Probability Bounds for Fading Channels Exploiting Dedekind Zeta Functions

In this paper, new probability bounds are derived for algebraic lattice codes. This is done by using the Dedekind zeta functions of the algebraic number fields involved in the lattice constructions. In particular, it is shown how to upper bound the error performance of a finite constellation on a Rayleigh fading channel and the probability of an eavesdropper's correct decision in a wiretap channel. As a byproduct, an estimate of the number of elements with a certain algebraic norm within a finite hyper-cube is derived. While this type of estimates have been, to some extent, considered in algebraic number theory before, they are now brought into novel practice in the context of fading channel communications. Hence, the interest here is in small-dimensional lattices and finite constellations rather than in the asymptotic behavior.

0 citations0 reviewsNo code linkedOpen access