Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

The Optimal Rate of MDS Variable Generation

Yizhou Zhao, Hua Sun

Published Jun 25, 2023• 10 citations
Publisher

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.

DOI
10.1109/isit54713.2023.10206914

Related papers

MDS Variable Generation and Secure Summation With User Selection

Yizhou Zhao, Hua Sun

A collection ofKrandom variables are called$(K,n)$-MDS if anynof theKvariables are independent and determine all remaining variables. In the MDS variable generation problem,Kusers 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 \in \{1,2,\cdots , K\}$, the minimum size of the randomness variable at each user is$1 + 1/2 + \cdots + 1/K$bits. An intimately related problem is secure summation with user selection, where a server may select an arbitrary subset ofKusers 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 + \cdots + 1/(K-1)$bits, whose achievability uses the generation of$(K,n)$-MDS variables for$n \in \{1,2,\cdots ,K-1\}$.

arXiv:2211.01220•IEEE Transactions on Information Theory•Feb 13, 2025•22 citations

On the Fundamental Limits of Secure Summation and MDS Variable Generation

Yizhou Zhao

Secure multiparty computation refers to the problem where a number of users wish to securely compute a function on their inputs without revealing any unnecessary information. This dissertation focuses on the fundamental limits of secure summation under different constraints. We first focus on the minimal model of secure computation, in which two users each hold an input and wish to securely compute a function of their inputs at the server. We propose a novel scheme base on the algebraic structure of finite field and modulo ring of integers. Then we extend the minimal model of secure computation, in which K users wish to securely compute the sum of their inputs at the server. We prove a folklore result on the limits of communication cost and randomness cost. Then we characterized the optimal communication cost with user dropouts constraint, when some users may lose connection to the server and the server wishes to compute the sum of remaining inputs. Next, we characterize the optimal communication and randomness cost for symmetric groupwise keys and find the feasibility condition for arbitrary groupwise keys. Last, we study the secure summation with user selection, such that the server may select any subset of users to compute the sum of their inputs. This leads us to the MDS variable generation problem. We characterize the optimal individual key rate and the result is interestingly the harmonic number.

•Jul 1, 2023•0 citations

On the Randomness Cost of Linear Secure Computation : (Invited Presentation)

Yanliang Zhou, Hua Sun, Shengli Fu

We consider the problem of secure computation, where K users, each holding an independent message, wish to compute a function on the messages without revealing any additional information. We show that to compute M generic linear independent combinations of the messages securely (i.e., for the linear secure computation problem), it suffices to use min(|(K-M-1)/2|, M) randomness symbols per message symbol (i.e., the randomness cost is no larger than min(|(K-M-1)/2|, M)). The optimality of the achieved randomness cost remains open.

Conference on Information Sciences and Systems•Mar 1, 2019•9 citations

Secure Cascade Channel Synthesis

Sanket Satpathy, Paul Cuff

We consider the problem of generating correlated random variables in a distributed fashion, where communication is constrained to a cascade network. The first node in the cascade observes an i.i.d. sequence$X^{n}$locally before initiating communication along the cascade. All nodes share bits of common randomness that are independent of$X^{n}$. We consider secure synthesis—random variables produced by the system appear to be appropriately correlated and i.i.d. even to an eavesdropper who is cognizant of the communication transmissions. We characterize the optimal tradeoff between the amount of common randomness used and the required rates of communication. We find that not only does common randomness help, its usage exceeds the communication rate requirements. The most efficient scheme is based on a superposition codebook, with the first node selecting messages for all downstream nodes. We also provide a fleeting view of related problems, demonstrating how the optimal rate region may shrink or expand.

arXiv:1305.4314•IEEE Transactions on Information Theory•Jul 1, 2013•25 citations

Finite-precision intrinsic randomness and source resolvability

Yossef Steinberg, Sergio Verdú

Random number generators are important devices in randomized algorithms, Monte-Carlo methods, and in simulation studies of random systems. A random number generator is usually modeled as a random source emitting independent, equally likely random bits. In practice, the random source one has at hand can deviate from this idealized model, and the random number generator operates by applying a deterministic mapping on the output of the (nonideal) random source. The deterministic mapping is chosen so that the resulting process approximates, in some sense, a sequence of independent, equally likely random bits. A prime measure of the intrinsic randomness of a given source X is the maximal rate at which random bits can be extracted from X by suitably mapping its output. This maximal rate depends on the statistics of the source X and on the sense of approximation. We study the problem of finite-precision random bit generation, where the accuracy measure is the variational distance. The relevant information theory is addressed.

IEEE-IMS Workshop on Information Theory and Statistics•Dec 17, 2002•1 citation

Lower Bounds for the Number of Random Bits in Monte Carlo Algorithms

Stefan Heinrich

arXiv:2012.12774•Springer proceedings in mathematics & statistics•Jan 1, 2022•2 citations
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.
A collection ofKrandom variables are called(K,n)(K,n)(K,n)-MDS if anynof theKvariables are independent and determine all remaining variables. In the MDS variable generation problem,Kusers wish to generate variables that are(K,n)(K,n)(K,n)-MDS using a randomness variable owned by each user. We show that to generate 1 bit of(K,n)(K,n)(K,n)-MDS variables for eachn∈{1,2,⋯ ,K}n \in \{1,2,\cdots , K\}n∈{1,2,⋯,K}, the minimum size of the randomness variable at each user is1+1/2+⋯+1/K1 + 1/2 + \cdots + 1/K1+1/2+⋯+1/Kbits. An intimately related problem is secure summation with user selection, where a server may select an arbitrary subset ofKusers 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 is1+1/2+⋯+1/(K−1)1 + 1/2 + \cdots + 1/(K-1)1+1/2+⋯+1/(K−1)bits, whose achievability uses the generation of(K,n)(K,n)(K,n)-MDS variables forn∈{1,2,⋯ ,K−1}n \in \{1,2,\cdots ,K-1\}n∈{1,2,⋯,K−1}.
Secure multiparty computation refers to the problem where a number of users wish to securely compute a function on their inputs without revealing any unnecessary information. This dissertation focuses on the fundamental limits of secure summation under different constraints. We first focus on the minimal model of secure computation, in which two users each hold an input and wish to securely compute a function of their inputs at the server. We propose a novel scheme base on the algebraic structure of finite field and modulo ring of integers. Then we extend the minimal model of secure computation, in which K users wish to securely compute the sum of their inputs at the server. We prove a folklore result on the limits of communication cost and randomness cost. Then we characterized the optimal communication cost with user dropouts constraint, when some users may lose connection to the server and the server wishes to compute the sum of remaining inputs. Next, we characterize the optimal communication and randomness cost for symmetric groupwise keys and find the feasibility condition for arbitrary groupwise keys. Last, we study the secure summation with user selection, such that the server may select any subset of users to compute the sum of their inputs. This leads us to the MDS variable generation problem. We characterize the optimal individual key rate and the result is interestingly the harmonic number.
We consider the problem of secure computation, where K users, each holding an independent message, wish to compute a function on the messages without revealing any additional information. We show that to compute M generic linear independent combinations of the messages securely (i.e., for the linear secure computation problem), it suffices to use min(|(K-M-1)/2|, M) randomness symbols per message symbol (i.e., the randomness cost is no larger than min(|(K-M-1)/2|, M)). The optimality of the achieved randomness cost remains open.
We consider the problem of generating correlated random variables in a distributed fashion, where communication is constrained to a cascade network. The first node in the cascade observes an i.i.d. sequenceXnX^{n}Xnlocally before initiating communication along the cascade. All nodes share bits of common randomness that are independent ofXnX^{n}Xn. We consider secure synthesis—random variables produced by the system appear to be appropriately correlated and i.i.d. even to an eavesdropper who is cognizant of the communication transmissions. We characterize the optimal tradeoff between the amount of common randomness used and the required rates of communication. We find that not only does common randomness help, its usage exceeds the communication rate requirements. The most efficient scheme is based on a superposition codebook, with the first node selecting messages for all downstream nodes. We also provide a fleeting view of related problems, demonstrating how the optimal rate region may shrink or expand.
Random number generators are important devices in randomized algorithms, Monte-Carlo methods, and in simulation studies of random systems. A random number generator is usually modeled as a random source emitting independent, equally likely random bits. In practice, the random source one has at hand can deviate from this idealized model, and the random number generator operates by applying a deterministic mapping on the output of the (nonideal) random source. The deterministic mapping is chosen so that the resulting process approximates, in some sense, a sequence of independent, equally likely random bits. A prime measure of the intrinsic randomness of a given source X is the maximal rate at which random bits can be extracted from X by suitably mapping its output. This maximal rate depends on the statistics of the source X and on the sense of approximation. We study the problem of finite-precision random bit generation, where the accuracy measure is the variational distance. The relevant information theory is addressed.