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•10 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•2 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

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

PK-hybrid protocols: a new framework for hybrid encryption

Scott Weeks

This thesis considers cryptographic systems that use public key encryption (PKE) as a building block in a larger system. We call these cryptosystems and develop a framework for describing such protocols that provides a clear way of describing the role of PKE in the PKE-hybrid protocol. By clarifying and generalizing the role of PKE in such protocols, we are able to state and prove a powerful lemma for proving the security of PK-hybrid protocols. We then show how this lemma can be used in a proof of security for the standard technique of hybrid encryption, substantially simplifying earlier proofs by Cramer and Shoup and by Abe, et al. In addressing these protocols we make improvements to a previously published protocol for Generalized Non-Interactive Oblivious Transfer (GNIOT) due to Gunupudi and Tate, and use our new security framework to correct a subtle error in the original security proof provided for GNIOT.

•Jan 1, 2011•0 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.
This thesis considers cryptographic systems that use public key encryption (PKE) as a building block in a larger system. We call these cryptosystems and develop a framework for describing such protocols that provides a clear way of describing the role of PKE in the PKE-hybrid protocol. By clarifying and generalizing the role of PKE in such protocols, we are able to state and prove a powerful lemma for proving the security of PK-hybrid protocols. We then show how this lemma can be used in a proof of security for the standard technique of hybrid encryption, substantially simplifying earlier proofs by Cramer and Shoup and by Abe, et al. In addressing these protocols we make improvements to a previously published protocol for Generalized Non-Interactive Oblivious Transfer (GNIOT) due to Gunupudi and Tate, and use our new security framework to correct a subtle error in the original security proof provided for GNIOT.