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

arXiv:1510.06231 · Journal of Computer Networks and Communications

Symmetric Blind Decryption with Perfect Secrecy

Juha Partala

Published Jan 1, 2017• 1 citation
arXivHTMLPDF

Abstract

A blind decryption scheme enables a user to query decryptions from a decryption server without revealing information about the plain-text message. Such schemes are useful, for example, for the implementation of privacy-preserving encrypted file storages and payment systems. In terms of functionality, blind decryption is close to oblivious transfer. For noiseless channels, information-theoretically secure oblivious transfer is impossible. However, in this paper, we show that this is not the case for blind decryption. We formulate a definition of perfect secrecy of symmetric blind decryption for the following setting: at most one of the scheme participants is a passive adversary (honest-but-curious). We also devise a symmetric blind decryption scheme based on modular arithmetic on a ring Zp2 , where p is a prime, and show that it satisfies our notion of perfect secrecy.

DOI
10.1155/2017/6575907

Related papers

Quantum secure blind decryption with two users

Masahito Hayashi, Yuki Ito

We propose two types of protocols for quantum secure blind decryption, involving two users and servers. User 1 holds the encrypted ciphertext. The servers store several indexed keys including the key encrypting the ciphertext. User 2 aims to obtain the decrypted text. The protocols are designed to preserve the following types of secrecy: Users ensure the secrecy of the text from the servers. Servers maintain the secrecy of the keys from the users. Our protocols enable User 2 to obtain the decrypted text while preserving these secrecy requirements. Additionally, the second protocol ensures the secrecy of the key index to identify the key encrypting the ciphertext from the servers, and the second protocol requires two non-commuting servers. Furthermore, we analyze the secrecy of the second protocol under post-attack scenarios, where the two servers communicates with each other after the completion of the protocol. We show that our quantum protocol satisfies the secrecy under these attacks, whereas its classical counterpart fails to do so.

quant-pharXiv:2606.01949•Jun 2, 2026•0 citations

Privacy-Preserving Server-Supported Decryption

Peeter Laud, Alisa Pankova, Jelizaveta Vakarjuk

In this paper, we consider encryption systems with two-out-of-two threshold decryption, where one of the parties (the client) initiates the decryption and the other one (the server) assists. Existing threshold decryption schemes disclose to the server the ciphertext that is being decrypted. We give a construction, where the identity of the ciphertext is not leaked to the server, and the client's privacy is thus preserved. While showing the security of this construction, we run into the issue of defining the security of a scheme with blindly assisted decryption. We discuss previously proposed security definitions for similar cryptographic functionalities and argue why they do not capture the expected meaning of security. We propose an ideal functionality for the encryption with server-supported blind threshold decryption in the universal composability model, carefully balancing between the meaning of privacy, and the ability to implement it. We construct a protocol and show that it is a secure implementation of the proposed functionality in the random oracle model.

arXiv:2410.19338•IEEE Computer Security Foundations Workshop (CSFW)•Jun 16, 2025•2 citations

Impossibility of quantum private queries

Esther Hänggi, Severin Winkler

Symmetric private information retrieval is a cryptographic task allowing a user to query a database and obtain exactly one entry without revealing to the owner of the database which element was accessed. The task is a variant of general two-party protocols called and is closely related to oblivious transfer. Under the name , quantum protocols have been proposed to solve this problem in a cheat-sensitive way: In such protocols, it is not impossible for dishonest participants to cheat, but they risk detection [Giovannetti , ]. We give an explicit attack against any cheat-sensitive symmetric private information retrieval protocol, showing that any protocol that is secure for the user cannot have nontrivial security guarantees for the owner of the database: The user is even able to retrieve the database.

arXiv:2501.12842•Physical Review Research•Apr 3, 2026•0 citations

Symmetrically private information retrieval based on blind quantum computing

Zhiwei Sun, Jianping Yu, Ping Wang +1 more

Universal blind quantum computation (UBQC) is a new secure quantum computing protocol which allows a user Alice who does not have any sophisticated quantum technology to delegate her computing to a server Bob without leaking any privacy. Using the features of UBQC, we propose a protocol to achieve symmetrically private information retrieval, which allows a quantum limited Alice to query an item from Bob with a fully fledged quantum computer; meanwhile, the privacy of both parties is preserved. The security of our protocol is based on the assumption that malicious Alice has no quantum computer, which avoids the impossibility proof of Lo. For the honest Alice, she is almost classical and only requires minimal quantum resources to carry out the proposed protocol. Therefore, she does not need any expensive laboratory which can maintain the coherence of complicated quantum experimental setups.

Physical Review A•May 4, 2015•21 citations

Exploratory designs of unconditionally secure distributed oblivious transfer protocols

Christian L. F. Corniaux

The security of digital goods buyers and sellers is unbalanced. Of course, the property of sellers is protected; for example, when customers acquire digital books or films from Internet's merchants, they only receive the products they have paid for. Unfortunately, the buyers' privacy is rarely respected: purchases are often — without the buyers' knowledge — monitored, recorded, analysed, and sometimes sold to marketing companies. As a consequence, even if the customers do not intend to acquire additional products, their computer screens are later invaded with targeted advertisements. The main purpose of this thesis is to propose some methods to restore the balance and guarantee the buyers' privacy, while protecting the interests of the sellers. To this end, it is worth looking into the area of cryptography and more specifically, it is worth studying and designing some protocols called distributed oblivious transfer (DOT) protocols. A DOT protocol allows a party A to obtain one of the secret pieces of information (a secret for short) held by a party B so that the following two fundamental conditions are satisfied: • A chooses the secrets she wishes to obtain and does not obtain anything on the secrets she has not chosen, • B does not learn which secret was obtained by A. Furthermore, to improve the availability of the information, the protocol is distributed. That is, the party B transmits his secret information to m servers and the party A needs to contact at least k of these servers to obtain the chosen secret. The servers are not fully trusted, neither by A, nor by B. Therefore, from the information exchanged with A and B, no coalition of servers should be able to learn the secrets of B or the choice of A. The results of a preliminary literature review are surprising. In fact, the number of publications on DOT protocols is small (fewer than 20) compared to, for example, the number of publications on a similar concept, secret sharing (100s of publications). And yet, oblivious transfer is a fundamental component of more complex cryptographic protocols such as multi-party computation protocols, which allow a group of participants to securely calculate any function of their joint secret inputs. So, one could expect many variants, for example of the original DOT protocol introduced in 2002 by Naor and Pinkas [74], to fulfil the requirements of specific scenarios. The design of variants of DOT protocols in traditional cryptography has been the guiding thread of my research. My contribution mainly consists in (a) a critical analysis of the existing protocols, demonstrating their limitations, weaknesses, and in some cases, flaws; and (b) the design of the following protocols,well adapted to some specific situations: A Strongly Secure DOT Protocol. This DOT protocol addresses the most important weakness of unconditionally secure, one-round, polynomial interpolation-based DOT protocols: after the protocol has been executed, if the party A corrupts only one server, she can learn all the secrets of the party B. The protocol is secure even if A corrupts up to k - 1 servers. A Verifiable DOT Protocol. The party A should obtain the secret she has chosen, even when some servers are controlled by a malicious adversary whose objective is to sabotage the protocol. This is the case with this protocol, assuming that the adversary cannot control more than k - 1 servers. A Multiple Secrets DOT Protocol. When the party A wishes to obtain n > 1 secrets, the current protocols have to be executed n times. In this context, they are inefficient. The DOT protocol introduced here allows the party A, by contacting in the same session k - 1 + n servers, to collect n secrets. Adaptive DOT Protocols. The previous protocol allows the party A to request several secrets. However, the request of one secret may depend on the values of secrets already obtained. Two efficient protocols are presented in this scenario. The first one allows A to receive a limited number of secrets and therefore, is well adapted to a single receiver. For several receivers, a second protocol is proposed. This second protocol accepts an unlimited number of queries, but requires communications amongst the servers. A Threshold DOT protocol. Most existing DOT protocols rely on threshold secret sharing schemes. In a k-threshold protocol or scheme, security is guaranteed not only when k parties are contacted, but also when more than k parties are contacted. However, the existing DOT protocols based on k-threshold secret sharing schemes require an additional mechanism to control that exactly k servers are contacted, which is an under-utilisation of the underlying functionality. The proposed protocol is the first k-threshold DOT protocol which allows the party A to contact as many servers as she wishes to obtain the chosen secret, provided that at least k servers are contacted. This research is limited to unconditionally secure protocols, i.e., protocols whose security does not depend on mathematical (unproven) assumptions; within the limits of the given security models, the protocols are secure even against an adversary with unlimited computing power and time. In brief, the results presented in this thesis are a significant advance to the state of the art research on DOT protocols because on one hand, they point out the weaknesses of the DOT protocols most commonly accepted by the cryptographic community and on the other hand, they contribute to the cryptographic field through the design of new protocols, secure and efficient.

•Oct 26, 2022•0 citations

Towards communication-efficient quantum oblivious key distribution

M. V. Panduranga Rao, Markus Jakobi

Symmetrically private information retrieval, a fundamental problem in the field of secure multiparty computation, is defined as follows: A database $D$ of $N$ bits held by Bob is queried by a user Alice who is interested in the bit ${D}_{b}$ in such a way that (1) Alice learns ${D}_{b}$ and only ${D}_{b}$ and (2) Bob does not learn anything about Alice's choice $b$. While solutions to this problem in the classical domain rely largely on unproven computational complexity theoretic assumptions, it is also known that perfect solutions that guarantee both database and user privacy are impossible in the quantum domain. Jakobi et al. [Phys. Rev. A 83, 022301 (2011)] proposed a protocol for oblivious transfer using well-known quantum key device (QKD) techniques to establish an oblivious key to solve this problem. Their solution provided a good degree of database and user privacy (using physical principles like the impossibility of perfectly distinguishing nonorthogonal quantum states and the impossibility of superluminal communication) while being loss-resistant and implementable with commercial QKD devices (due to the use of the Scarani-Acin-Ribordy-Gisin 2004 protocol). However, their quantum oblivious key distribution (QOKD) protocol requires a communication complexity of $O(N\mathrm{log}N)$. Since modern databases can be extremely large, it is important to reduce this communication as much as possible. In this paper, we first suggest a modification of their protocol wherein the number of qubits that need to be exchanged is reduced to $O(N)$. A subsequent generalization reduces the quantum communication complexity even further in such a way that only a few hundred qubits are needed to be transferred even for very large databases.

arXiv:1208.2501•Physical Review A•Jan 28, 2013•63 citations
A blind decryption scheme enables a user to query decryptions from a decryption server without revealing information about the plain-text message. Such schemes are useful, for example, for the implementation of privacy-preserving encrypted file storages and payment systems. In terms of functionality, blind decryption is close to oblivious transfer. For noiseless channels, information-theoretically secure oblivious transfer is impossible. However, in this paper, we show that this is not the case for blind decryption. We formulate a definition of perfect secrecy of symmetric blind decryption for the following setting: at most one of the scheme participants is a passive adversary (honest-but-curious). We also devise a symmetric blind decryption scheme based on modular arithmetic on a ring Zp2 , where p is a prime, and show that it satisfies our notion of perfect secrecy.
We propose two types of protocols for quantum secure blind decryption, involving two users and servers. User 1 holds the encrypted ciphertext. The servers store several indexed keys including the key encrypting the ciphertext. User 2 aims to obtain the decrypted text. The protocols are designed to preserve the following types of secrecy: Users ensure the secrecy of the text from the servers. Servers maintain the secrecy of the keys from the users. Our protocols enable User 2 to obtain the decrypted text while preserving these secrecy requirements. Additionally, the second protocol ensures the secrecy of the key index to identify the key encrypting the ciphertext from the servers, and the second protocol requires two non-commuting servers. Furthermore, we analyze the secrecy of the second protocol under post-attack scenarios, where the two servers communicates with each other after the completion of the protocol. We show that our quantum protocol satisfies the secrecy under these attacks, whereas its classical counterpart fails to do so.
In this paper, we consider encryption systems with two-out-of-two threshold decryption, where one of the parties (the client) initiates the decryption and the other one (the server) assists. Existing threshold decryption schemes disclose to the server the ciphertext that is being decrypted. We give a construction, where the identity of the ciphertext is not leaked to the server, and the client's privacy is thus preserved. While showing the security of this construction, we run into the issue of defining the security of a scheme with blindly assisted decryption. We discuss previously proposed security definitions for similar cryptographic functionalities and argue why they do not capture the expected meaning of security. We propose an ideal functionality for the encryption with server-supported blind threshold decryption in the universal composability model, carefully balancing between the meaning of privacy, and the ability to implement it. We construct a protocol and show that it is a secure implementation of the proposed functionality in the random oracle model.
Symmetric private information retrieval is a cryptographic task allowing a user to query a database and obtain exactly one entry without revealing to the owner of the database which element was accessed. The task is a variant of general two-party protocols called and is closely related to oblivious transfer. Under the name , quantum protocols have been proposed to solve this problem in a cheat-sensitive way: In such protocols, it is not impossible for dishonest participants to cheat, but they risk detection [Giovannetti , ]. We give an explicit attack against any cheat-sensitive symmetric private information retrieval protocol, showing that any protocol that is secure for the user cannot have nontrivial security guarantees for the owner of the database: The user is even able to retrieve the database.
Universal blind quantum computation (UBQC) is a new secure quantum computing protocol which allows a user Alice who does not have any sophisticated quantum technology to delegate her computing to a server Bob without leaking any privacy. Using the features of UBQC, we propose a protocol to achieve symmetrically private information retrieval, which allows a quantum limited Alice to query an item from Bob with a fully fledged quantum computer; meanwhile, the privacy of both parties is preserved. The security of our protocol is based on the assumption that malicious Alice has no quantum computer, which avoids the impossibility proof of Lo. For the honest Alice, she is almost classical and only requires minimal quantum resources to carry out the proposed protocol. Therefore, she does not need any expensive laboratory which can maintain the coherence of complicated quantum experimental setups.
The security of digital goods buyers and sellers is unbalanced. Of course, the property of sellers is protected; for example, when customers acquire digital books or films from Internet's merchants, they only receive the products they have paid for. Unfortunately, the buyers' privacy is rarely respected: purchases are often — without the buyers' knowledge — monitored, recorded, analysed, and sometimes sold to marketing companies. As a consequence, even if the customers do not intend to acquire additional products, their computer screens are later invaded with targeted advertisements. The main purpose of this thesis is to propose some methods to restore the balance and guarantee the buyers' privacy, while protecting the interests of the sellers. To this end, it is worth looking into the area of cryptography and more specifically, it is worth studying and designing some protocols called distributed oblivious transfer (DOT) protocols. A DOT protocol allows a party A to obtain one of the secret pieces of information (a secret for short) held by a party B so that the following two fundamental conditions are satisfied: • A chooses the secrets she wishes to obtain and does not obtain anything on the secrets she has not chosen, • B does not learn which secret was obtained by A. Furthermore, to improve the availability of the information, the protocol is distributed. That is, the party B transmits his secret information to m servers and the party A needs to contact at least k of these servers to obtain the chosen secret. The servers are not fully trusted, neither by A, nor by B. Therefore, from the information exchanged with A and B, no coalition of servers should be able to learn the secrets of B or the choice of A. The results of a preliminary literature review are surprising. In fact, the number of publications on DOT protocols is small (fewer than 20) compared to, for example, the number of publications on a similar concept, secret sharing (100s of publications). And yet, oblivious transfer is a fundamental component of more complex cryptographic protocols such as multi-party computation protocols, which allow a group of participants to securely calculate any function of their joint secret inputs. So, one could expect many variants, for example of the original DOT protocol introduced in 2002 by Naor and Pinkas [74], to fulfil the requirements of specific scenarios. The design of variants of DOT protocols in traditional cryptography has been the guiding thread of my research. My contribution mainly consists in (a) a critical analysis of the existing protocols, demonstrating their limitations, weaknesses, and in some cases, flaws; and (b) the design of the following protocols,well adapted to some specific situations: A Strongly Secure DOT Protocol. This DOT protocol addresses the most important weakness of unconditionally secure, one-round, polynomial interpolation-based DOT protocols: after the protocol has been executed, if the party A corrupts only one server, she can learn all the secrets of the party B. The protocol is secure even if A corrupts up to k - 1 servers. A Verifiable DOT Protocol. The party A should obtain the secret she has chosen, even when some servers are controlled by a malicious adversary whose objective is to sabotage the protocol. This is the case with this protocol, assuming that the adversary cannot control more than k - 1 servers. A Multiple Secrets DOT Protocol. When the party A wishes to obtain n > 1 secrets, the current protocols have to be executed n times. In this context, they are inefficient. The DOT protocol introduced here allows the party A, by contacting in the same session k - 1 + n servers, to collect n secrets. Adaptive DOT Protocols. The previous protocol allows the party A to request several secrets. However, the request of one secret may depend on the values of secrets already obtained. Two efficient protocols are presented in this scenario. The first one allows A to receive a limited number of secrets and therefore, is well adapted to a single receiver. For several receivers, a second protocol is proposed. This second protocol accepts an unlimited number of queries, but requires communications amongst the servers. A Threshold DOT protocol. Most existing DOT protocols rely on threshold secret sharing schemes. In a k-threshold protocol or scheme, security is guaranteed not only when k parties are contacted, but also when more than k parties are contacted. However, the existing DOT protocols based on k-threshold secret sharing schemes require an additional mechanism to control that exactly k servers are contacted, which is an under-utilisation of the underlying functionality. The proposed protocol is the first k-threshold DOT protocol which allows the party A to contact as many servers as she wishes to obtain the chosen secret, provided that at least k servers are contacted. This research is limited to unconditionally secure protocols, i.e., protocols whose security does not depend on mathematical (unproven) assumptions; within the limits of the given security models, the protocols are secure even against an adversary with unlimited computing power and time. In brief, the results presented in this thesis are a significant advance to the state of the art research on DOT protocols because on one hand, they point out the weaknesses of the DOT protocols most commonly accepted by the cryptographic community and on the other hand, they contribute to the cryptographic field through the design of new protocols, secure and efficient.
Symmetrically private information retrieval, a fundamental problem in the field of secure multiparty computation, is defined as follows: A database DDD of NNN bits held by Bob is queried by a user Alice who is interested in the bit Db{D}_{b}Db​ in such a way that (1) Alice learns Db{D}_{b}Db​ and only Db{D}_{b}Db​ and (2) Bob does not learn anything about Alice's choice bbb. While solutions to this problem in the classical domain rely largely on unproven computational complexity theoretic assumptions, it is also known that perfect solutions that guarantee both database and user privacy are impossible in the quantum domain. Jakobi et al. [Phys. Rev. A 83, 022301 (2011)] proposed a protocol for oblivious transfer using well-known quantum key device (QKD) techniques to establish an oblivious key to solve this problem. Their solution provided a good degree of database and user privacy (using physical principles like the impossibility of perfectly distinguishing nonorthogonal quantum states and the impossibility of superluminal communication) while being loss-resistant and implementable with commercial QKD devices (due to the use of the Scarani-Acin-Ribordy-Gisin 2004 protocol). However, their quantum oblivious key distribution (QOKD) protocol requires a communication complexity of O(NlogN)O(N\mathrm{log}N)O(NlogN). Since modern databases can be extremely large, it is important to reduce this communication as much as possible. In this paper, we first suggest a modification of their protocol wherein the number of qubits that need to be exchanged is reduced to O(N)O(N)O(N). A subsequent generalization reduces the quantum communication complexity even further in such a way that only a few hundred qubits are needed to be transferred even for very large databases.