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

Lecture notes in computer science

Negative Results on Information-Theoretic Additive Randomized Encodings

Keitaro Hiwatashi

Published Jan 1, 2025• 2 citations
Publisher
DOI
10.1007/978-3-031-95764-2_6

Related papers

Additive Randomized Encodings and Their Applications

Shai Halevi, Yuval Ishai, Eyal Kushilevitz +1 more

Lecture notes in computer science•Jan 1, 2023•8 citations

Optimal parameter encoding strategies for estimation theoretic secure communications

Çağrı Göken

Physical layer security has gained a renewed interest with the advances in modern wireless communication technologies. In estimation theoretic security, secrecy levels are measured via estimation theoretic tools and metrics, such as mean-squared error (MSE), where the objective is to perform accurate estimation of the parameter at the intended receiver while keeping the estimation error at the eavesdropper above a certain level. This framework proves useful both for analyzing the achievable performance under security constraints in parameter estimation problems, and for designing low-complexity, practical methods to enhance security in communication systems. In this dissertation, we investigate optimal deterministic encoding of random scalar and vector parameters in the presence of an eavesdropper, who is unaware of the encoding operation. We also analyze optimal stochastic encoding of a random parameter under secrecy constraints in a Gaussian wiretap channel model, where the eavesdropper is aware of the encoding strategy at the transmitter. In addition, we perform optimal parameter design for secure broadcast of a parameter to multiple receivers with fixed estimators. First, optimal deterministic encoding of a scalar parameter is investigated in the presence of an eavesdropper. The aim is to minimize the expectation of the conditional Cram´er-Rao bound (ECRB) at the intended receiver while keeping the MSE at the eavesdropper above a certain threshold. The eavesdropper is modeled to employ the linear minimum mean-squared error (LMMSE) estimator based on the encoded version of the parameter. First, the optimal encoding function is derived in the absence of secrecy constraints for any given prior distribution on the parameter. Next, an optimization problem is formulated under a secrecy constraint and various solution approaches are proposed. Also, theoretical results on the form of the optimal encoding function are provided. Furthermore, a robust parameter encoding approach is developed. In this case, the objective is to maximize the worst-case Fisher information of the parameter at the intended receiver while keeping the MSE at the eavesdropper above a certain level. The optimal encoding function is derived when there exist no secrecy constraints. Next, to obtain the solution of the problem in the presence of the secrecy constraint, the form of the encoding function that maximizes the MSE at the eavesdropper is explicitly derived for any given level of worst-case Fisher information. Then, based on this result, a low-complexity algorithm is provided to calculate the optimal encoding function for the given secrecy constraint. Numerical examples are presented to illustrate the theoretical results for both the ECRB and worst-case Fisher information based designs. Second, optimal deterministic encoding of a vector parameter is investigated in the presence of an eavesdropper. The objective is to minimize the ECRB at the intended receiver while satisfying an individual secrecy constraint on the MSE of estimating each parameter at the eavesdropper. The eavesdropper is modeled to employ the LMMSE estimator based on the noisy observation of the encoded parameter without being aware of encoding. First, the problem is formulated as a constrained optimization problem in the space of vector-valued functions. Then, two practical solution strategies are developed based on nonlinear individual encoding and affine joint encoding of parameters. Theoretical results on the solutions of the proposed strategies are provided for various scenarios on channel conditions and parameter distributions. Finally, numerical examples are presented to illustrate the performance of the proposed solution approaches. Third, estimation theoretic secure transmission of a scalar random parameter is investigated in the presence of an eavesdropper. The aim is to minimize the estimation error at the receiver under a secrecy constraint at the eavesdropper; or, alternatively, to maximize the estimation error at the eavesdropper for a given estimation accuracy limit at the receiver. In the considered setting, the encoder at the transmitter is allowed to use a randomized mapping between two one-to-one and continuous functions and the eavesdropper is fully aware of the encoding strategy at the transmitter. For small numbers of observations, both the eavesdropper and the receiver are modeled to employ LMMSE estimators, and for large numbers of observations, the ECRB metric is employed for both the receiver and the eavesdropper. Optimization problems are formulated and various theoretical results are provided in order to obtain the optimal solutions and to analyze the effects of encoder randomization. In addition, numerical examples are presented to corroborate the theoretical results. It is observed that stochastic encoding can bring significant performance gains for estimation theoretic secrecy problems. Finally, estimation theoretic secure broadcast of a random parameter is investigated. In the considered setting, each receiver device employs a fixed estimator and carries a certain security risk such that its decision can be available to a malicious third party with a certain probability. The encoder at the transmitter is allowed to use a random mapping to minimize the weighted sum of the conditional Bayes risks of the estimators under secrecy and average power constraints. After formulating the optimal parameter design problem, it is shown that the optimization problem can be solved individually for each parameter value and the optimal mapping at the transmitter involves a randomization among at most three different signal levels. Sufficient conditions for improvability and nonimprovability of the deterministic design via stochastic encoding are obtained. Numerical examples are provided to corroborate the theoretical results.

•Dec 1, 2019•0 citations

A mathematical theory of randomized computation, I

Shinichi Yamada

Proceedings of the Japan Academy Series A Mathematical Sciences•Jan 1, 1988•2 citations

Analytical construction of $(n, n-1)$ quantum random access codes saturating the conjectured bound

Takayuki Suzuki

Quantum Random Access Codes (QRACs) embody the fundamental trade-off between the compressibility of information into limited quantum resources and the accessibility of that information, serving as a cornerstone of quantum communication and computation. In particular, the $(n, n-1)$-QRACs, which encode $n$ bits of classical information into $n-1$ qubits, provides an ideal theoretical model for verifying quantum advantage in high-dimensional spaces; however, the analytical derivation of optimal codes for general $n$ has remained an open problem. In this paper, we establish an analytical construction method for $(n, n-1)$-QRACs by using an explicit operator formalism. We prove that this construction strictly achieves the numerically conjectured upper bound of the average success probability, $\mathcal{P} = 1/2 + \sqrt{(n-1)/n}/2$, for all $n$. Furthermore, we present a systematic algorithm to decompose the derived optimal POVM into standard quantum gates. Since the resulting decoding circuit consists solely of interactions between adjacent qubits, it can be implemented with a circuit depth of $O(n)$ even under linear connectivity constraints. Additionally, we analyze the high-dimensional limit and demonstrate that while the non-commutativity of measurements is suppressed, an information-theoretic gap of $O(\log n)$ from the Holevo bound inevitably arises for symmetric encoding. This study not only provides a scalable implementation method for high-dimensional quantum information processing but also offers new insights into the mathematical structure at the quantum-classical boundary.

quant-pharXiv:2601.19190•Physical Review A•Jan 28, 2026•4 citations

Estimation Theoretic Secure Communication via Encoder Randomization

Çağrı Göken, Sinan Gezici

Estimation theoretic secure transmission of a scalar random parameter is investigated in the presence of an eavesdropper. The aim is to minimize the estimation error at the receiver under a secrecy constraint at the eavesdropper; or, alternatively, to maximize the estimation error at the eavesdropper for a given estimation accuracy limit at the receiver. In the considered setting, the encoder at the transmitter is allowed to use a randomized mapping between two one-to-one and continuous functions and the eavesdropper is fully aware of the encoding strategy at the transmitter. For small numbers of observations, both the eavesdropper and the receiver are modeled to employ linear minimum mean-squared error (LMMSE) estimators, and for large numbers of observations, the expectation of the conditional Cramér-Rao bound (ECRB) metric is employed for both the receiver and the eavesdropper. Optimization problems are formulated and various theoretical results are provided in order to obtain the optimal solutions and to analyze the effects of encoder randomization. In addition, numerical examples are presented to corroborate the theoretical results. It is observed that stochastic encoding can bring significant performance gains for estimation theoretic secrecy problems.

IEEE Transactions on Signal Processing•Nov 4, 2019•5 citations

Recent Developments and Open Problems in Information Theoretic Cryptography

Shun Watanabe

IEICE Technical Report; IEICE Tech. Rep.•Nov 21, 2017•0 citations
Physical layer security has gained a renewed interest with the advances in modern wireless communication technologies. In estimation theoretic security, secrecy levels are measured via estimation theoretic tools and metrics, such as mean-squared error (MSE), where the objective is to perform accurate estimation of the parameter at the intended receiver while keeping the estimation error at the eavesdropper above a certain level. This framework proves useful both for analyzing the achievable performance under security constraints in parameter estimation problems, and for designing low-complexity, practical methods to enhance security in communication systems. In this dissertation, we investigate optimal deterministic encoding of random scalar and vector parameters in the presence of an eavesdropper, who is unaware of the encoding operation. We also analyze optimal stochastic encoding of a random parameter under secrecy constraints in a Gaussian wiretap channel model, where the eavesdropper is aware of the encoding strategy at the transmitter. In addition, we perform optimal parameter design for secure broadcast of a parameter to multiple receivers with fixed estimators. First, optimal deterministic encoding of a scalar parameter is investigated in the presence of an eavesdropper. The aim is to minimize the expectation of the conditional Cram´er-Rao bound (ECRB) at the intended receiver while keeping the MSE at the eavesdropper above a certain threshold. The eavesdropper is modeled to employ the linear minimum mean-squared error (LMMSE) estimator based on the encoded version of the parameter. First, the optimal encoding function is derived in the absence of secrecy constraints for any given prior distribution on the parameter. Next, an optimization problem is formulated under a secrecy constraint and various solution approaches are proposed. Also, theoretical results on the form of the optimal encoding function are provided. Furthermore, a robust parameter encoding approach is developed. In this case, the objective is to maximize the worst-case Fisher information of the parameter at the intended receiver while keeping the MSE at the eavesdropper above a certain level. The optimal encoding function is derived when there exist no secrecy constraints. Next, to obtain the solution of the problem in the presence of the secrecy constraint, the form of the encoding function that maximizes the MSE at the eavesdropper is explicitly derived for any given level of worst-case Fisher information. Then, based on this result, a low-complexity algorithm is provided to calculate the optimal encoding function for the given secrecy constraint. Numerical examples are presented to illustrate the theoretical results for both the ECRB and worst-case Fisher information based designs. Second, optimal deterministic encoding of a vector parameter is investigated in the presence of an eavesdropper. The objective is to minimize the ECRB at the intended receiver while satisfying an individual secrecy constraint on the MSE of estimating each parameter at the eavesdropper. The eavesdropper is modeled to employ the LMMSE estimator based on the noisy observation of the encoded parameter without being aware of encoding. First, the problem is formulated as a constrained optimization problem in the space of vector-valued functions. Then, two practical solution strategies are developed based on nonlinear individual encoding and affine joint encoding of parameters. Theoretical results on the solutions of the proposed strategies are provided for various scenarios on channel conditions and parameter distributions. Finally, numerical examples are presented to illustrate the performance of the proposed solution approaches. Third, estimation theoretic secure transmission of a scalar random parameter is investigated in the presence of an eavesdropper. The aim is to minimize the estimation error at the receiver under a secrecy constraint at the eavesdropper; or, alternatively, to maximize the estimation error at the eavesdropper for a given estimation accuracy limit at the receiver. In the considered setting, the encoder at the transmitter is allowed to use a randomized mapping between two one-to-one and continuous functions and the eavesdropper is fully aware of the encoding strategy at the transmitter. For small numbers of observations, both the eavesdropper and the receiver are modeled to employ LMMSE estimators, and for large numbers of observations, the ECRB metric is employed for both the receiver and the eavesdropper. Optimization problems are formulated and various theoretical results are provided in order to obtain the optimal solutions and to analyze the effects of encoder randomization. In addition, numerical examples are presented to corroborate the theoretical results. It is observed that stochastic encoding can bring significant performance gains for estimation theoretic secrecy problems. Finally, estimation theoretic secure broadcast of a random parameter is investigated. In the considered setting, each receiver device employs a fixed estimator and carries a certain security risk such that its decision can be available to a malicious third party with a certain probability. The encoder at the transmitter is allowed to use a random mapping to minimize the weighted sum of the conditional Bayes risks of the estimators under secrecy and average power constraints. After formulating the optimal parameter design problem, it is shown that the optimization problem can be solved individually for each parameter value and the optimal mapping at the transmitter involves a randomization among at most three different signal levels. Sufficient conditions for improvability and nonimprovability of the deterministic design via stochastic encoding are obtained. Numerical examples are provided to corroborate the theoretical results.
Analytical construction of (n,n−1)(n, n-1)(n,n−1) quantum random access codes saturating the conjectured bound
Quantum Random Access Codes (QRACs) embody the fundamental trade-off between the compressibility of information into limited quantum resources and the accessibility of that information, serving as a cornerstone of quantum communication and computation. In particular, the (n,n−1)(n, n-1)(n,n−1)-QRACs, which encode nnn bits of classical information into n−1n-1n−1 qubits, provides an ideal theoretical model for verifying quantum advantage in high-dimensional spaces; however, the analytical derivation of optimal codes for general nnn has remained an open problem. In this paper, we establish an analytical construction method for (n,n−1)(n, n-1)(n,n−1)-QRACs by using an explicit operator formalism. We prove that this construction strictly achieves the numerically conjectured upper bound of the average success probability, P=1/2+(n−1)/n/2\mathcal{P} = 1/2 + \sqrt{(n-1)/n}/2P=1/2+(n−1)/n​/2, for all nnn. Furthermore, we present a systematic algorithm to decompose the derived optimal POVM into standard quantum gates. Since the resulting decoding circuit consists solely of interactions between adjacent qubits, it can be implemented with a circuit depth of O(n)O(n)O(n) even under linear connectivity constraints. Additionally, we analyze the high-dimensional limit and demonstrate that while the non-commutativity of measurements is suppressed, an information-theoretic gap of O(log⁡n)O(\log n)O(logn) from the Holevo bound inevitably arises for symmetric encoding. This study not only provides a scalable implementation method for high-dimensional quantum information processing but also offers new insights into the mathematical structure at the quantum-classical boundary.
Estimation theoretic secure transmission of a scalar random parameter is investigated in the presence of an eavesdropper. The aim is to minimize the estimation error at the receiver under a secrecy constraint at the eavesdropper; or, alternatively, to maximize the estimation error at the eavesdropper for a given estimation accuracy limit at the receiver. In the considered setting, the encoder at the transmitter is allowed to use a randomized mapping between two one-to-one and continuous functions and the eavesdropper is fully aware of the encoding strategy at the transmitter. For small numbers of observations, both the eavesdropper and the receiver are modeled to employ linear minimum mean-squared error (LMMSE) estimators, and for large numbers of observations, the expectation of the conditional Cramér-Rao bound (ECRB) metric is employed for both the receiver and the eavesdropper. Optimization problems are formulated and various theoretical results are provided in order to obtain the optimal solutions and to analyze the effects of encoder randomization. In addition, numerical examples are presented to corroborate the theoretical results. It is observed that stochastic encoding can bring significant performance gains for estimation theoretic secrecy problems.