MDS Variable Generation and Secure Summation with User Selection

2022/11/02 by Yizhou Zhao, Zhao, Yizhou, Sun Hua +1 · 5 citations
Computer Science · Engineering · #Chaos-based Image/Signal Encryption #Cryptography and Data Security #FOS: Computer and information sciences #Information Theory (cs.IT) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2211.01220

openalex publication_date 2022/11/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A collection of K random variables are called (K,n)-MDS if any n of the K variables are independent and determine all remaining variables. In the MDS variable generation problem, K users wish to generate variables that are (K,n)-MDS using a randomness variable owned by each user. We show that to generate 1 bit of (K,n)-MDS variables for each n ∈ \1,2,⋯, K\, the minimum size of the randomness variable at each user is 1 + 1/2 + ⋯ + 1/K bits. An intimately related problem is secure summation with user selection, where a server may select an arbitrary subset of K users and securely compute the sum of the inputs of the selected users. We show that to compute 1 bit of an arbitrarily chosen sum securely, the minimum size of the key held by each user is 1 + 1/2 + ⋯ + 1/(K-1) bits, whose achievability uses the generation of (K,n)-MDS variables for n ∈ \1,2,⋯,K-1\.

Cited by

• Optimal Key Rates for Decentralized Secure Aggregation with Arbitrary Collusion and Heterogeneous Security Constraints
• The Capacity of Collusion-Resilient Decentralized Secure Aggregation with Groupwise Keys
• Information-Theoretic Decentralized Secure Aggregation with Passive Collusion Resilience
• Hierarchical Secure Aggregation with Heterogeneous Security Constraints and Arbitrary User Collusion
• Coding-Enforced Robust Secure Aggregation for Federated Learning Under Unreliable Communication

Related

• Weakly Secure Summation with Colluding Users
• Secure Summation: Capacity Region, Groupwise Key, and Feasibility
• Vector Linear Secure Aggregation
• Private Information Retrieval from MDS Coded Data with Colluding Servers: Settling a Conjecture by Freij-Hollanti et al.
• Secure Summation via Subset Sums: A New Primitive for Privacy-Preserving Distributed Machine Learning