Camilla Hollanti

Charul Rajput, B. Sundar Rajan, Ragnar Freij-Hollanti et al.

Function-correcting codes (FCCs) are designed to provide error protection for the value of a function computed on the data. Existing work typically focuses solely on protecting the function value and not the underlying data. In this work, we propose a general framework that offers protection for both the data and the function values. Since protecting the data inherently contributes to protecting the function value, we focus on scenarios where the function value requires stronger protection than the data itself. We first introduce a more general approach and a framework for function-correcting codes that incorporates data protection along with protection of function values. A two-step construction procedure for such codes is proposed, and bounds on the optimal redundancy of general FCCs with data protection are reported. Using these results, we exhibit examples that show that data protection can be added to existing FCCs without increasing redundancy. Using our two-step construction procedure, we present explicit constructions of FCCs with data protection for specific families of functions, such as locally bounded functions and the Hamming weight function. We associate a graph called minimum-distance graph to a code and use it to show that perfect codes and maximum distance separable (MDS) codes cannot provide additional protection to function values over and above the amount of protection for data for any function. Then we focus on linear FCCs and provide some results for linear functions, leveraging their inherent structural properties. To the best of our knowledge, this is the first instance of FCCs with a linear structure. Finally, we generalize the Plotkin and Hamming bounds well known in classical error-correcting coding theory to FCCs with data protection.

Charul Rajput, B. Sundar Rajan, Ragnar Freij-Hollanti et al.

Function-correcting codes with data protection simultaneously protect both the data and a function of the data at distinct error-correction levels. When the function receives strictly stronger protection than the data, such a code is called a strict function-correcting code with data protection. While prior work showed that perfect and MDS codes cannot serve as strict function-correcting codes, which codes can serve this role, and how to construct them, has remained open. In this paper, we address the existence and construction of strict function-correcting codes for linear codes through three main contributions. First, using the $α$-distance graph framework from our prior work, we establish a graph-theoretic existence condition under which a code can serve as a strict function-correcting code. For linear codes, we prove this distance graph is isomorphic to a Cayley graph, which implies the connected components are cosets of the subcode generated by low-weight codewords. This transforms the existence problem into a subcode generation problem. Second, a classical result of Simonis shows any linear code can be transformed into one with the same parameters whose basis consists entirely of minimum-weight codewords. We develop a converse construction: under certain conditions on the weight distribution, a linear code can be transformed into a new code with the same parameters but fewer independent minimum-weight codewords, thereby producing codes suitable for use as strict function-correcting codes. As a source of codes satisfying these conditions, we introduce chain codes, an infinite family of linear codes generated by their minimum-weight codewords. Third, we present an independent construction of strict function-correcting codes from narrow-sense BCH codes with designed distance three, by proving the minimum-weight codewords of such codes are contained in a proper subcode.

Delio Jaramillo-Velez, Charul Rajput, Ragnar Freij-Hollanti et al.

In federated learning, multiple parties train models locally and share their parameters with a central server, which aggregates them to update a global model. To address the risk of exposing sensitive data through local models, secure aggregation via secure multiparty computation has been proposed to enhance privacy. At the same time, perfect privacy can only be achieved by a uniform distribution of the masked local models to be aggregated. This raises a problem when working with real valued data, as there is no measure on the reals that is invariant under the masking operation, and hence information leakage is bound to occur. Shifting the data to a finite field circumvents this problem, but as a downside runs into an inherent accuracy complexity tradeoff issue due to fixed point modular arithmetic as opposed to floating point numbers that can simultaneously handle numbers of varying magnitudes. In this paper, a novel secure parameter aggregation method is proposed that employs the torus rather than a finite field. This approach guarantees perfect privacy for each party's data by utilizing the uniform distribution on the torus, while avoiding accuracy losses. Experimental results show that the new protocol performs similarly to the model without secure aggregation while maintaining perfect privacy. Compared to the finite field secure aggregation, the torus-based protocol can in some cases significantly outperform it in terms of model accuracy and cosine similarity, hence making it a safer choice.

Okko Makkonen, Sampo Niemelä, Camilla Hollanti et al.

This work focuses on the challenges of non-IID data and stragglers/dropouts in federated learning. We introduce and explore a privacy-flexible paradigm that models parts of the clients' local data as non-private, offering a more versatile and business-oriented perspective on privacy. Within this framework, we propose a data-driven strategy for mitigating the effects of label heterogeneity and client straggling on federated learning. Our solution combines both offline data sharing and approximate gradient coding techniques. Through numerical simulations using the MNIST dataset, we demonstrate that our approach enables achieving a deliberate trade-off between privacy and utility, leading to improved model convergence and accuracy while using an adaptable portion of non-private data.

Okko Makkonen, Camilla Hollanti

This work considers the problem of distributing matrix multiplication over the real or complex numbers to helper servers, such that the information leakage to these servers is close to being information-theoretically secure. These servers are assumed to be honest-but-curious, i.e., they work according to the protocol, but try to deduce information about the data. The problem of secure distributed matrix multiplication (SDMM) has been considered in the context of matrix multiplication over finite fields, which is not always feasible in real world applications. We present two schemes, which allow for variable degree of security based on the use case and allow for colluding and straggling servers. We analyze the security and the numerical accuracy of the schemes and observe a trade-off between accuracy and security.

Matteo Allaix, Seunghoan Song, Lukas Holzbaur et al.

In quantum private information retrieval (QPIR), a user retrieves a classical file from multiple servers by downloading quantum systems without revealing the identity of the file. The QPIR capacity is the maximal achievable ratio of the retrieved file size to the total download size. In this paper, the capacity of QPIR from MDS-coded and colluding servers is studied for the first time. Two general classes of QPIR, called stabilizer QPIR and dimension-squared QPIR induced from classical strongly linear PIR are defined, and the related QPIR capacities are derived. For the non-colluding case, the general QPIR capacity is derived when the number of files goes to infinity. A general statement on the converse bound for QPIR with coded and colluding servers is derived showing that the capacities of stabilizer QPIR and dimension-squared QPIR induced from any class of PIR are upper bounded by twice the classical capacity of the respective PIR class. The proposed capacity-achieving scheme combines the star-product scheme by Freij-Hollanti et al. and the stabilizer QPIR scheme by Song et al. by employing (weakly) self-dual Reed--Solomon codes.

Matteo Allaix, Lukas Holzbaur, Tefjol Pllaha et al.

In the classical private information retrieval (PIR) setup, a user wants to retrieve a file from a database or a distributed storage system (DSS) without revealing the file identity to the servers holding the data. In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by receiving quantum information from the servers. The QPIR problem has been treated by Song et al. in the case of replicated servers, both with and without collusion. QPIR over $[n,k]$ maximum distance separable (MDS) coded servers was recently considered by Allaix et al., but the collusion was essentially restricted to $t=n-k$ servers in the sense that a smaller $t$ would not improve the retrieval rate. In this paper, the QPIR setting is extended to allow for retrieval with high rate for any number of colluding servers $t$ with $1 \leq t \leq n-k$. Similarly to the previous cases, the rates achieved are better than those known or conjectured in the classical counterparts, as well as those of the previously proposed coded and colluding QPIR schemes. This is enabled by considering the stabilizer formalism and weakly self-dual generalized Reed--Solomon (GRS) star product codes.

Matteo Allaix, Lukas Holzbaur, Tefjol Pllaha et al.

In the classical private information retrieval (PIR) setup, a user wants to retrieve a file from a database or a distributed storage system (DSS) without revealing the file identity to the servers holding the data. In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by receiving quantum information from the servers. The QPIR problem has been treated by Song \emph{et al.} in the case of replicated servers, both without collusion and with all but one servers colluding. In this paper, the QPIR setting is extended to account for maximum distance separable (MDS) coded servers. The proposed protocol works for any $[n,k]$-MDS code and $t$-collusion with $t=n-k$. Similarly to the previous cases, the rates achieved are better than those known or conjectured in the classical counterparts. Further, it is demonstrated how the protocol can adapted to achieve significantly higher retrieval rates from DSSs encoded with a locally repairable code (LRC) with disjoint repair groups, each of which is an MDS code.

Julian Renner, Sven Puchinger, Antonia Wachter-Zeh et al.

We define and analyze low-rank parity-check (LRPC) codes over extension rings of the finite chain ring $\mathbb{Z}_{p^r}$, where $p$ is a prime and $r$ is a positive integer. LRPC codes have originally been proposed by Gaborit et al.(2013) over finite fields for cryptographic applications. The adaption to finite rings is inspired by a recent paper by Kamche et al. (2019), which constructed Gabidulin codes over finite principle ideal rings with applications to space-time codes and network coding. We give a decoding algorithm based on simple linear-algebraic operations. Further, we derive an upper bound on the failure probability of the decoder. The upper bound is valid for errors whose rank is equal to the free rank.

Arsenia Chorti, Mehdi M. Molu, David Karpuk et al.

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.