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

Information Theoretic Framework for Single and Multi-Server Private Authentication

Narges Kazempour, Mahtab Mirmohseni, Mohammad Reza Aref

Published Jan 17, 2019• 1 citation
OpenAlex

Abstract

In this paper, the private authentication problem is considered that consists of a certificate authority, a verifier (or verifiers), many legitimate users (prover) and arbitrary number of attackers. Each legitimate user wants to be authenticated (using his personal key) by the verifier(s), while simultaneously staying anonymous. However, an attacker must fail to be authenticated. We analyze this problem from an information theoretical perspective. First, we propose a general interactive information-theoretic model. As a metric to measure reliability, we consider the key rate whose rate maximization has a trade-off with establishing privacy. We consider the problem in two different setups: single server and multi-server scenarios. In single server scenario one verifier is considered, which all the provers connected to. In multi-server scenario, $n$ verifiers are assumed, where each verifier is connected to a subset of users. For both scenarios, two regimes are considered: finite size and asymptotic regimes. In single server scenario, for both regimes, we propose schemes that satisfy completeness, soundness and privacy properties. Moreover, we show that our scheme achieves capacity in the asymptotic regime. For finite size regime our scheme achieves capacity for large field size. In multi-server scenario two methods are considered: individual and distributed authentication. In individual authentication, the process of authentication is done by one single verifier. In this case, for both regimes, we propose schemes that satisfy completeness, soundness and privacy properties. In distributed authentication, the process of authentication is done collaboratively by all the verifiers. For this case, when all the provers are connected to all the verifiers, we propose an optimal scheme in finite size regime.

Related papers

Anonymous Mutual Authentication: An Information Theoretic Framework

Narges Kazempour, Mahtab Mirmohseni, Mohammad Reza Aref

We consider the anonymous mutual authentication problem, which consists of a certificate authority, single or multiple verifiers, many legitimate users (provers) and any arbitrary number of illegitimate users. The legal verifier and a legitimate user must be mutually authenticated to each other using the user’s key, while the identity of the user must stay unrevealed. An attacker (illegitimate prover) as well as an illegal verifier must fail in authentication. A general interactive information theoretic framework in a finite field is proposed, where the normalized total key rate as a metric for reliability is defined. Maximizing this rate has a trade-off with establishing anonymity. The problem is studied in two different scenarios: centralized scenario (one single verifier performs the authentication process) and distributed scenario (authentication is done by N verifiers, distributively). For both scenarios, achievable schemes, which satisfy the completeness, soundness (at both verifier and prover) and anonymity properties, are proposed. Increasing the size of the field, results in the key rate approaching its upper bound.

Iran Workshop on Communication and Information Theory (IWCIT)•May 19, 2021•0 citations

Multi-Server Secure Aggregation with Arbitrary Collusion and Heterogeneous Security Constraints

Zhou Li, Xiang Zhang, Jiguang He +1 more

We study the fundamental limits of multi-server secure aggregation over a two-hop network where multiple servers, each connected to a disjoint subset of users, jointly compute the sum of all users' inputs. The goal is to ensure that no server can infer any information about prescribed subsets of inputs beyond the desired aggregate, even when colluding with an arbitrary subset of users. Existing works largely focus on homogeneous security requirements, where all inputs are protected against colluding sets up to a given size. Such formulations are insufficient to capture more general scenarios in which different subsets of inputs may require protection against different collusion patterns. In this paper, we consider a general model with heterogeneous security requirements and arbitrary user collusion. We characterize the communication rates for all parameter regimes, and determine the minimum key rate required for secure aggregation in most regimes. In particular, we establish tight information-theoretic lower bounds and matching achievable schemes in a broad class of regimes. For the remaining regime, we derive a general lower bound together with an achievable scheme that attains it within a bounded gap. Our results reveal how the interplay between network topology and heterogeneous security constraints fundamentally determines the communication and key generation requirements, and generalize existing results on secure aggregation.

arXiv:2604.26391•Apr 29, 2026•0 citations

Querying Twice to Achieve Information-Theoretic Verifiability in Private Information Retrieval

Stanislav Kruglik, Son Hoang Dau, Han Mao Kiah +2 more

Private Information Retrieval (PIR) protocols allow a client to retrieve any file of interest while keeping the files identity hidden from the database servers. While many existing PIR protocols assume servers to be honest but curious, we investigate the scenario of dishonest servers that provide incorrect answers to mislead clients into obtaining wrong results. We propose a unified framework for polynomial PIR protocols encompassing various existing protocols that optimize the download rate or total communication cost. We introduce a way to transform a polynomial PIR to a verifiable one without increasing the number of involved servers by doubling the queries. The security guarantees can be information-theoretic or computational, and the verification keys can be public or private. Moreover, in one of our protocols, the ratio between the additional download overhead associated with verification and the normal download cost approaches zero as the file size goes to infinity.

IEEE Transactions on Information Forensics and Security•Jan 1, 2024•3 citations

Keyless Authentication and Authenticated Capacity

Wenwen Tu, Lifeng Lai

We consider the problem of keyless message authentication over noisy channels in the presence of an active adversary. Different from the existing models, in our model, the legitimate users do not have any pre-shared key for authentication. Instead, we use the noisy channel connecting the legitimate users for authentication. The main idea is to utilize the noisy channel connecting the legitimate users to distinguish a legitimate message from a fake message, by generating an output at the receiver that is difficult for the adversary to replicate through its noisy channel. By interpreting the message authentication as a hypothesis testing problem, we investigate the authentication exponent and the authenticated channel capacity of the noisy channel. In the authentication exponent problem, for a given message rate, we investigate the speed at which the optimal successful attack probability can be driven to zero. We fully characterize the authentication exponent for the zero-rate message case and provide both an upper bound and a lower bound on the exponent for the non-zero message rate case. In the authenticated capacity problem, we study the largest data transmission rate under which the attacker's optimal successful attack probability can still be made arbitrarily small. We establish an all or nothing result. In particular, we show that the authenticated channel capacity is the same as the classic channel capacity if a simulatability condition is not satisfied, while the authenticated capacity will be zero if this condition is satisfied. We also provide efficient algorithms to check this condition. We further show that our results are robust to modeling uncertainties about the eavesdropper's channels.

IEEE Transactions on Information Theory•Feb 26, 2018•26 citations

A theoretical scheme for multi-user quantum authentication and key distribution in a network

Yu‐Guang Yang, Wen Qiao-yan, Fu-Chen Zhu +1 more

A theoretical scheme for multi-user quantum authentication and key distribution in a network is proposed. Similar to the authentication architecture of the netw ork in classical cryptography, a distributed client/server architecture with the shared Einstein-Podolsky-Rosen(EPR) entangled pairs between each user and his t rusted server used for the authentication and key distribution is proposed. Base d on this architecture, any-to-any multi-user quantum authentication and key dis tribution is realized. The trusted server only provides the authentication betwe en users and swaps the entanglement between the particles so as to entangle the particles of the two users who want to communicate secretly. The key generation is performed by the requesting user. Each user in a network only shares Einstein -Podolsky-Rosen entangled pairs with the trusted server and communicates with th e trusted server through the classical channel and quantum channel. Users need n ot share EPR entangled pairs with each other so that the number of EPR pairs in the network is reduced from O(n2) to O(n).

Acta Physica Sinica•Jan 1, 2005•9 citations

Capacity of Quantum Private Information Retrieval with Multiple Servers

Seunghoan Song, Masahito Hayashi

We study the capacity of quantum private information retrieval (QPIR) with multiple servers. In the QPIR problem with multiple servers, a user retrieves a classical file by downloading quantum systems from multiple servers each of which containing the whole classical file set, without revealing the identity of the retrieved file to any individual server. The QPIR capacity is defined as the maximum rate of the file size over the whole dimension of the downloaded quantum systems. Assuming the preexisting entanglement among servers, we prove that the QPIR capacity with multiple servers is 1 regardless of the number of servers and files. We propose a rate-one protocol which can be implemented by using only two servers. This capacity-achieving protocol outperforms its classical counterpart in the sense of the capacity, server secrecy, and upload cost. The strong converse bound is derived concisely without using the secrecy conditions.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•8 citations
In this paper, the private authentication problem is considered that consists of a certificate authority, a verifier (or verifiers), many legitimate users (prover) and arbitrary number of attackers. Each legitimate user wants to be authenticated (using his personal key) by the verifier(s), while simultaneously staying anonymous. However, an attacker must fail to be authenticated. We analyze this problem from an information theoretical perspective. First, we propose a general interactive information-theoretic model. As a metric to measure reliability, we consider the key rate whose rate maximization has a trade-off with establishing privacy. We consider the problem in two different setups: single server and multi-server scenarios. In single server scenario one verifier is considered, which all the provers connected to. In multi-server scenario, nnn verifiers are assumed, where each verifier is connected to a subset of users. For both scenarios, two regimes are considered: finite size and asymptotic regimes. In single server scenario, for both regimes, we propose schemes that satisfy completeness, soundness and privacy properties. Moreover, we show that our scheme achieves capacity in the asymptotic regime. For finite size regime our scheme achieves capacity for large field size. In multi-server scenario two methods are considered: individual and distributed authentication. In individual authentication, the process of authentication is done by one single verifier. In this case, for both regimes, we propose schemes that satisfy completeness, soundness and privacy properties. In distributed authentication, the process of authentication is done collaboratively by all the verifiers. For this case, when all the provers are connected to all the verifiers, we propose an optimal scheme in finite size regime.
We consider the anonymous mutual authentication problem, which consists of a certificate authority, single or multiple verifiers, many legitimate users (provers) and any arbitrary number of illegitimate users. The legal verifier and a legitimate user must be mutually authenticated to each other using the user’s key, while the identity of the user must stay unrevealed. An attacker (illegitimate prover) as well as an illegal verifier must fail in authentication. A general interactive information theoretic framework in a finite field is proposed, where the normalized total key rate as a metric for reliability is defined. Maximizing this rate has a trade-off with establishing anonymity. The problem is studied in two different scenarios: centralized scenario (one single verifier performs the authentication process) and distributed scenario (authentication is done by N verifiers, distributively). For both scenarios, achievable schemes, which satisfy the completeness, soundness (at both verifier and prover) and anonymity properties, are proposed. Increasing the size of the field, results in the key rate approaching its upper bound.
We study the fundamental limits of multi-server secure aggregation over a two-hop network where multiple servers, each connected to a disjoint subset of users, jointly compute the sum of all users' inputs. The goal is to ensure that no server can infer any information about prescribed subsets of inputs beyond the desired aggregate, even when colluding with an arbitrary subset of users. Existing works largely focus on homogeneous security requirements, where all inputs are protected against colluding sets up to a given size. Such formulations are insufficient to capture more general scenarios in which different subsets of inputs may require protection against different collusion patterns. In this paper, we consider a general model with heterogeneous security requirements and arbitrary user collusion. We characterize the communication rates for all parameter regimes, and determine the minimum key rate required for secure aggregation in most regimes. In particular, we establish tight information-theoretic lower bounds and matching achievable schemes in a broad class of regimes. For the remaining regime, we derive a general lower bound together with an achievable scheme that attains it within a bounded gap. Our results reveal how the interplay between network topology and heterogeneous security constraints fundamentally determines the communication and key generation requirements, and generalize existing results on secure aggregation.
Private Information Retrieval (PIR) protocols allow a client to retrieve any file of interest while keeping the files identity hidden from the database servers. While many existing PIR protocols assume servers to be honest but curious, we investigate the scenario of dishonest servers that provide incorrect answers to mislead clients into obtaining wrong results. We propose a unified framework for polynomial PIR protocols encompassing various existing protocols that optimize the download rate or total communication cost. We introduce a way to transform a polynomial PIR to a verifiable one without increasing the number of involved servers by doubling the queries. The security guarantees can be information-theoretic or computational, and the verification keys can be public or private. Moreover, in one of our protocols, the ratio between the additional download overhead associated with verification and the normal download cost approaches zero as the file size goes to infinity.
We consider the problem of keyless message authentication over noisy channels in the presence of an active adversary. Different from the existing models, in our model, the legitimate users do not have any pre-shared key for authentication. Instead, we use the noisy channel connecting the legitimate users for authentication. The main idea is to utilize the noisy channel connecting the legitimate users to distinguish a legitimate message from a fake message, by generating an output at the receiver that is difficult for the adversary to replicate through its noisy channel. By interpreting the message authentication as a hypothesis testing problem, we investigate the authentication exponent and the authenticated channel capacity of the noisy channel. In the authentication exponent problem, for a given message rate, we investigate the speed at which the optimal successful attack probability can be driven to zero. We fully characterize the authentication exponent for the zero-rate message case and provide both an upper bound and a lower bound on the exponent for the non-zero message rate case. In the authenticated capacity problem, we study the largest data transmission rate under which the attacker's optimal successful attack probability can still be made arbitrarily small. We establish an all or nothing result. In particular, we show that the authenticated channel capacity is the same as the classic channel capacity if a simulatability condition is not satisfied, while the authenticated capacity will be zero if this condition is satisfied. We also provide efficient algorithms to check this condition. We further show that our results are robust to modeling uncertainties about the eavesdropper's channels.
A theoretical scheme for multi-user quantum authentication and key distribution in a network is proposed. Similar to the authentication architecture of the netw ork in classical cryptography, a distributed client/server architecture with the shared Einstein-Podolsky-Rosen(EPR) entangled pairs between each user and his t rusted server used for the authentication and key distribution is proposed. Base d on this architecture, any-to-any multi-user quantum authentication and key dis tribution is realized. The trusted server only provides the authentication betwe en users and swaps the entanglement between the particles so as to entangle the particles of the two users who want to communicate secretly. The key generation is performed by the requesting user. Each user in a network only shares Einstein -Podolsky-Rosen entangled pairs with the trusted server and communicates with th e trusted server through the classical channel and quantum channel. Users need n ot share EPR entangled pairs with each other so that the number of EPR pairs in the network is reduced from O(n2) to O(n).
We study the capacity of quantum private information retrieval (QPIR) with multiple servers. In the QPIR problem with multiple servers, a user retrieves a classical file by downloading quantum systems from multiple servers each of which containing the whole classical file set, without revealing the identity of the retrieved file to any individual server. The QPIR capacity is defined as the maximum rate of the file size over the whole dimension of the downloaded quantum systems. Assuming the preexisting entanglement among servers, we prove that the QPIR capacity with multiple servers is 1 regardless of the number of servers and files. We propose a rate-one protocol which can be implemented by using only two servers. This capacity-achieving protocol outperforms its classical counterpart in the sense of the capacity, server secrecy, and upload cost. The strong converse bound is derived concisely without using the secrecy conditions.