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

Theory and Application of Cryptographic Techniques

Public-randomness in public-key cryptography (extended abstract)

Alfredo De Santis, Giuseppe Persiano

Published Feb 1, 1991• 1 citation
OpenAlex

Abstract

In this work we investigate the power of Public Randomness in the context of Public-key cryptosystems. We consider the Diffie-Hellman Public-key model in which an additional short random string is shared by all users. This, which we call Public-Key Public-Randomness (PKPR) model, is very powerful as we show that it supports simple non-interactive implementations of important cryptographic primitives.We give the first completely non-interactive implementation of Oblivious Transfer. Our implementation is also secure against receivers with unlimited computational power.We propose the first implementation of non-interactive nature for Perfect Zero-Knowledge in the dual model of Brassard, Crepeau, and Chaum for all NP-languages.

Related papers

Independent Oblivious Transfer

Qiong Huang

This paper presents a flavor of OT named Independent Oblivious Transfer in the Public-Key Public-Randomness Model (PKPR IOT, in short), with respect to the open problem given by De Santis. First it gives a non-interactive implementation of IOT, which can independently and obliviously transfer polynomial messages. The implementation is based on Quadratic Residuosity Assumption. Since it is limited to pre-fixed times, then another non-interactive implementation of IOT is presented, which can independently transfer messages for any times. The second implementation requires the sender to be honest and the receiver couldn’t make his choice independently. So, the third interactive implementation is given. It is based on the BBCS oblivious transfer scheme of Rivest, and is rather more efficient than the above two non-interactive counterparts. All the three implementations presented are secure against receivers with unlimited computational power.

Journal of Software•Jan 1, 2007•0 citations

Security Notions for Quantum Public-Key Cryptography

Takeshi Koshiba

It is well known that Shor's quantum algorithm for integer factorization can break down the RSA public-key cryptosystem, which is widely used in many cryptographic applications. Thus, public-key cryptosystems in the quantum computational setting are longed for cryptology. In order to define the security notions of public-key cryptosystems, we have to model the power of the sender, receiver, adversary and channel. While we may consider a setting where quantum computers are available only to adversaries, we generally discuss what are the right security notions for (quantum) public-key cryptosystems in the quantum computational setting. Moreover, we consider the security of quantum public-key cryptosystems known so far.

arXiv:quant-ph/0702183•Feb 19, 2007•13 citations

Randomness Recoverable Secret Sharing Schemes

Mohammad Hajiabadi, Shahram Khazaei, Behzad Vahdani

It is well-known that randomness is essential for secure cryptography. The randomness used in cryptographic primitives is not necessarily recoverable even by the party who can, e.g., decrypt or recover the underlying secret/message. Several cryptographic primitives that support randomness recovery have turned out useful in various applications. In this paper, we study randomness recoverable secret sharing schemes (RR-SSS), in both information-theoretic and computational settings and provide two results. First, we show that while every access structure admits a perfect RR-SSS, there are very simple access structures (e.g., in monotone $$\textsf{AC}^0$$ ) that do not admit efficient perfect (or even statistical) RR-SSS. Second, we show that the existence of efficient computational RR-SSS for certain access structures in monotone $$\textsf{AC}^0$$ implies the existence of one-way functions. This stands in sharp contrast to (non-RR) SSS schemes for which no such results are known. RR-SSS plays a key role in making advanced attributed-based encryption schemes randomness recoverable, which in turn have applications in the context of designated-verifier non-interactive zero knowledge.

Journal of Cryptology•Aug 20, 2024•3 citations

On the Power of Random Oracles.

Iftach Haitner, Eran Omri, Hila Zarosim

In the random oracle model, the parties are given oracle access to a random member of a (typically huge) function family, and are assumed to have unbounded computational power (though they can only make a bounded number of oracle queries). This model provides powerful properties that allow proving the security of many protocols, even such that cannot be proved secure in the standard model (under any hardness assumption). The random oracle model is also used to show that a given cryptographic primitive cannot be used in a black-box way to construct another primitive; in their seminal work, Impagliazzo and Rudich [STOC ’89] showed that in the random function model – when the function family is the set of all functions – it is impossible to construct (secure) key-agreement protocols, yielding that key-agreement cannot be black-box reduced to one-way functions. Their work has a long line of followup works (Simon [EC ’98], Gertner et al. [STOC ’00] and Gennaro et al. [SICOMP ’05], to name a few), showing that given oracle access to a certain type of function family (e.g., the family that “implements ” public-key encryption) is not sufficient for building a given cryptographic primitive (e.g., oblivious transfer). Yet, in the more general sense, the following fundamental question remained open: What is the exact power of the random oracle model, and more specifically, of the random function model? We make progress towards answering the above question, showing that any (no private input) semi-honest two-party functionality that can be securely implemented in the random function model, can be securely implemented information theoretically (where parties are assumed to be all powerful, and no oracle is given). We further generalize the above result to function families that provide some natural combinatorial property. To exhibit the power of our result, we use the recent information theoretic impossibility result of McGregor et al. [FOCS ’10], to show the existence of functionalities (e.g., inner product) that cannot be computed both accurately and in a differentially private manner in the random function model; yielding that protocols for computing these functionalities cannot be black-box reduced to the existence of one-way functions.

Electronic colloquium on computational complexity•Jan 1, 2012•3 citations

Noninteractive oblivious transfer

Lein Harn, H.-Y. Lin

Two new approaches to implement oblivious transfer and 1–2 oblivious transfer without interaction, based on the wellknown, Diffie–Hellman public-key distribution algorithm are proposed.

Electronics Letters•May 1, 1990•10 citations

Performance of Practical Quantum Oblivious Key Distribution

Mariano Lemus, Peter Schiansky, Manuel Goulão +5 more

Motivated by the applications of secure multi-party computation as a privacy-protecting data analysis tool, and identifying oblivious transfer as one of its main practical enablers, we propose a practical realization of randomized quantum oblivious transfer. By using only symmetric cryptography primitives to implement commitments, we construct computationally secure randomized oblivious transfer without the need for public-key cryptography or assumptions imposing limitations on the adversarial devices. We show that the protocol is secure under an indistinguishability-based notion of security and demonstrate an experimental implementation to test its real-world performance. Its security and performance are then compared to both quantum and classical alternatives, showing potential advantages over existing solutions based on the noisy storage model and public-key cryptography.

arXiv:2501.03973•PRX Quantum•Aug 21, 2025•5 citations
In this work we investigate the power of Public Randomness in the context of Public-key cryptosystems. We consider the Diffie-Hellman Public-key model in which an additional short random string is shared by all users. This, which we call Public-Key Public-Randomness (PKPR) model, is very powerful as we show that it supports simple non-interactive implementations of important cryptographic primitives.We give the first completely non-interactive implementation of Oblivious Transfer. Our implementation is also secure against receivers with unlimited computational power.We propose the first implementation of non-interactive nature for Perfect Zero-Knowledge in the dual model of Brassard, Crepeau, and Chaum for all NP-languages.
This paper presents a flavor of OT named Independent Oblivious Transfer in the Public-Key Public-Randomness Model (PKPR IOT, in short), with respect to the open problem given by De Santis. First it gives a non-interactive implementation of IOT, which can independently and obliviously transfer polynomial messages. The implementation is based on Quadratic Residuosity Assumption. Since it is limited to pre-fixed times, then another non-interactive implementation of IOT is presented, which can independently transfer messages for any times. The second implementation requires the sender to be honest and the receiver couldn’t make his choice independently. So, the third interactive implementation is given. It is based on the BBCS oblivious transfer scheme of Rivest, and is rather more efficient than the above two non-interactive counterparts. All the three implementations presented are secure against receivers with unlimited computational power.
It is well known that Shor's quantum algorithm for integer factorization can break down the RSA public-key cryptosystem, which is widely used in many cryptographic applications. Thus, public-key cryptosystems in the quantum computational setting are longed for cryptology. In order to define the security notions of public-key cryptosystems, we have to model the power of the sender, receiver, adversary and channel. While we may consider a setting where quantum computers are available only to adversaries, we generally discuss what are the right security notions for (quantum) public-key cryptosystems in the quantum computational setting. Moreover, we consider the security of quantum public-key cryptosystems known so far.
It is well-known that randomness is essential for secure cryptography. The randomness used in cryptographic primitives is not necessarily recoverable even by the party who can, e.g., decrypt or recover the underlying secret/message. Several cryptographic primitives that support randomness recovery have turned out useful in various applications. In this paper, we study randomness recoverable secret sharing schemes (RR-SSS), in both information-theoretic and computational settings and provide two results. First, we show that while every access structure admits a perfect RR-SSS, there are very simple access structures (e.g., in monotone AC0\textsf{AC}^0AC0 ) that do not admit efficient perfect (or even statistical) RR-SSS. Second, we show that the existence of efficient computational RR-SSS for certain access structures in monotone AC0\textsf{AC}^0AC0 implies the existence of one-way functions. This stands in sharp contrast to (non-RR) SSS schemes for which no such results are known. RR-SSS plays a key role in making advanced attributed-based encryption schemes randomness recoverable, which in turn have applications in the context of designated-verifier non-interactive zero knowledge.
In the random oracle model, the parties are given oracle access to a random member of a (typically huge) function family, and are assumed to have unbounded computational power (though they can only make a bounded number of oracle queries). This model provides powerful properties that allow proving the security of many protocols, even such that cannot be proved secure in the standard model (under any hardness assumption). The random oracle model is also used to show that a given cryptographic primitive cannot be used in a black-box way to construct another primitive; in their seminal work, Impagliazzo and Rudich [STOC ’89] showed that in the random function model – when the function family is the set of all functions – it is impossible to construct (secure) key-agreement protocols, yielding that key-agreement cannot be black-box reduced to one-way functions. Their work has a long line of followup works (Simon [EC ’98], Gertner et al. [STOC ’00] and Gennaro et al. [SICOMP ’05], to name a few), showing that given oracle access to a certain type of function family (e.g., the family that “implements ” public-key encryption) is not sufficient for building a given cryptographic primitive (e.g., oblivious transfer). Yet, in the more general sense, the following fundamental question remained open: What is the exact power of the random oracle model, and more specifically, of the random function model? We make progress towards answering the above question, showing that any (no private input) semi-honest two-party functionality that can be securely implemented in the random function model, can be securely implemented information theoretically (where parties are assumed to be all powerful, and no oracle is given). We further generalize the above result to function families that provide some natural combinatorial property. To exhibit the power of our result, we use the recent information theoretic impossibility result of McGregor et al. [FOCS ’10], to show the existence of functionalities (e.g., inner product) that cannot be computed both accurately and in a differentially private manner in the random function model; yielding that protocols for computing these functionalities cannot be black-box reduced to the existence of one-way functions.
Motivated by the applications of secure multi-party computation as a privacy-protecting data analysis tool, and identifying oblivious transfer as one of its main practical enablers, we propose a practical realization of randomized quantum oblivious transfer. By using only symmetric cryptography primitives to implement commitments, we construct computationally secure randomized oblivious transfer without the need for public-key cryptography or assumptions imposing limitations on the adversarial devices. We show that the protocol is secure under an indistinguishability-based notion of security and demonstrate an experimental implementation to test its real-world performance. Its security and performance are then compared to both quantum and classical alternatives, showing potential advantages over existing solutions based on the noisy storage model and public-key cryptography.