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

Public-Key Encryption with Lazy Parties.

Kenji Yasunaga

Published Jan 1, 2013• 0 citations
OpenAlex

Abstract

In a public-key encryption scheme, if a sender is not concerned about the security of a message and is unwilling to generate costly randomness, the security of the encrypted message can be compromised. In this work, we characterize such lazy parties, who are regraded as honest parties, but are unwilling to perform a costly task when they are not concerned about the security. Specifically, we consider a rather simple setting in which the costly task is to generate randomness used in algorithms, and parties can choose either perfect randomness or a fixed string. We model lazy parties as rational players who behave rationally to maximize their utilities, and define a security game between the parties and an adversary. Since a standard secure encryption scheme does not work in the setting, we provide constructions of secure encryption schemes in various settings.

Related papers

Public-Key Encryption with Lazy Parties

Kenji Yasunaga

In a public-key encryption scheme, if a sender is not concerned about the security of a message and is unwilling to generate costly randomness, the security of the encrypted message can be compromised. This is caused by the laziness of the sender. In this work, we characterize lazy parties in cryptography. Lazy parties are regarded as honest parties in a protocol, but they are not concerned about the security of the protocol in a certain situation. In such a situation, they behave in an honest-looking way, and are unwilling to do a costly task. We study, in particular, public-key encryption with lazy parties. Specifically, as the first step toward understanding the behavior of lazy parties in public-key encryption, we consider a rather simple setting in which the costly task is to generate randomness used in algorithms, and parties can choose either costly good randomness or cheap bad randomness. We model lazy parties as rational players who behaves rationally to maximize their utilities, and define a security game between lazy parties and an adversary. A secure encryption scheme requires that the game is conducted by lazy parties in a secure way if they follow a prescribed strategy, and the prescribed strategy is a good equilibrium solution for the game. Since a standard secure encryption scheme does not work for lazy parties, we present some public-key encryption schemes that are secure for lazy parties.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2016•5 citations

Repeated Games for Generating Randomness in Encryption

Kenji Yasunaga, Kosuke Yuzawa

In encryption schemes, the sender may not generate randomness properly if generating randomness is costly, and the sender is not concerned about the security of a message. The problem was studied by the first author (2016), and was formalized in a game-theoretic framework. In this work, we construct an encryption scheme with an optimal round complexity on the basis of the mechanism of repeated games.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2018•3 citations

Adaptively-Secure, Non-Interactive Public-Key Encryption.

Ran Canetti, Shai Halevi, Jonathan I. Katz

Abstract. Adaptively-secure encryption schemes ensure secrecy even in the presence of an adversary who can corrupt parties in an adaptive manner based on public keys, ciphertexts, and secret data of alreadycorrupted parties. Ideally, an adaptively-secure encryption scheme should, like standard public-key encryption, allow arbitrarily-many parties to use a single encryption key to securely encrypt arbitrarily-many messages to a given receiver who maintains only a single short decryption key. However, it is known that these requirements are impossible to achieve: no non-interactive encryption scheme that supports encryption of an unbounded number of messages and uses a single, unchanging decryption key can be adaptively secure. Impossibility holds even if secure data erasure is possible. We show that this limitation can be overcome by updating the decryption key over time and making some mild assumptions about the frequency of communication between parties. Using this approach, we construct adaptively-secure, completely non-interactive encryption schemes supporting secure encryption of arbitrarily-many messages from arbitrarilymany senders. Our schemes additionally provide forward security and security against chosen-ciphertext attacks. 1

•Jan 1, 2004•1 citation

Deterministic quantum-public-key encryption: Forward search attack and randomization

Georgios M. Nikolopoulos, Lawrence M. Ioannou

In the classical setting, public-key encryption requires randomness in order to be secure against a forward search attack, whereby an adversary compares the encryption of a guess of the secret message with the encryption of the actual secret message. We show that this is also true in the information-theoretic setting---where the public keys are quantum systems---by defining and giving an example of a forward search attack for any deterministic quantum-public-key bit-encryption scheme. However, unlike in the classical setting, we show that any such deterministic scheme can be used as a black box to build a randomized bit-encryption scheme that is no longer susceptible to this attack.

arXiv:0903.4744•Physical Review A•Apr 21, 2009•36 citations

Encryption Schemes Secure under Selective Opening Attack

Mihir Bellare Y, Scott Yilek

We provide the first public key encryption schemes proven secure against selective opening attack (SOA). This means that if an adversary obtains a number of ciphertexts and then corrupts some fraction of the senders, obtaining not only the corresponding messages but also the coins under which they were encrypted then the security of theothermessagesisguaranteed. Whetherornotschemeswith this property exist has been open for many years. Our schemes are based on a primitive we call lossy encryption. Our schemes have short keys (public and secret keys of a fixed length suffice for encrypting an arbitrary number of messages), are stateless, are non-interactive, and security does not rely on erasures. The schemes are without random oracles, proven secure under standard assumptions (DDH, Paillier’s DCR, QR, lattices), and even efficient. We are able to meet both an indistinguishability

•Jan 20, 2014•34 citations

On the Leakage Resilient Cryptography in Game-Theoretic Settings

Mohammad Shahriar Rahman, Keita Emura, Shinsaku Kiyomoto

In this paper, we reevaluate leakage resilient cryptography from the viewpoint of game theory. We provide a general framework on leakage resilience in game theoretic setting and show that it is of each party's interest not to deviate from the protocol, i.e., their behavior is rational which assures them the highest incentive. We show that it is enough for a Public Key Encryption (PKE) scheme to be Computational Threat-Free Nash Equilibrium (CTFNE) for being leakage resilient. To be specific, CTFNE is not guaranteed if an internal state of a CCLA1 (Chosen Ciphertext with Leakage Attack)-secure Key Encapsulation Mechanism (KEM) of PKE is updated using a poor randomness with low-entropy. This work thus allows us for arguing about the strategic behavior of players in protocols where leakage is allowed.

IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)•Aug 1, 2016•0 citations
In a public-key encryption scheme, if a sender is not concerned about the security of a message and is unwilling to generate costly randomness, the security of the encrypted message can be compromised. In this work, we characterize such lazy parties, who are regraded as honest parties, but are unwilling to perform a costly task when they are not concerned about the security. Specifically, we consider a rather simple setting in which the costly task is to generate randomness used in algorithms, and parties can choose either perfect randomness or a fixed string. We model lazy parties as rational players who behave rationally to maximize their utilities, and define a security game between the parties and an adversary. Since a standard secure encryption scheme does not work in the setting, we provide constructions of secure encryption schemes in various settings.
In a public-key encryption scheme, if a sender is not concerned about the security of a message and is unwilling to generate costly randomness, the security of the encrypted message can be compromised. This is caused by the laziness of the sender. In this work, we characterize lazy parties in cryptography. Lazy parties are regarded as honest parties in a protocol, but they are not concerned about the security of the protocol in a certain situation. In such a situation, they behave in an honest-looking way, and are unwilling to do a costly task. We study, in particular, public-key encryption with lazy parties. Specifically, as the first step toward understanding the behavior of lazy parties in public-key encryption, we consider a rather simple setting in which the costly task is to generate randomness used in algorithms, and parties can choose either costly good randomness or cheap bad randomness. We model lazy parties as rational players who behaves rationally to maximize their utilities, and define a security game between lazy parties and an adversary. A secure encryption scheme requires that the game is conducted by lazy parties in a secure way if they follow a prescribed strategy, and the prescribed strategy is a good equilibrium solution for the game. Since a standard secure encryption scheme does not work for lazy parties, we present some public-key encryption schemes that are secure for lazy parties.
Abstract. Adaptively-secure encryption schemes ensure secrecy even in the presence of an adversary who can corrupt parties in an adaptive manner based on public keys, ciphertexts, and secret data of alreadycorrupted parties. Ideally, an adaptively-secure encryption scheme should, like standard public-key encryption, allow arbitrarily-many parties to use a single encryption key to securely encrypt arbitrarily-many messages to a given receiver who maintains only a single short decryption key. However, it is known that these requirements are impossible to achieve: no non-interactive encryption scheme that supports encryption of an unbounded number of messages and uses a single, unchanging decryption key can be adaptively secure. Impossibility holds even if secure data erasure is possible. We show that this limitation can be overcome by updating the decryption key over time and making some mild assumptions about the frequency of communication between parties. Using this approach, we construct adaptively-secure, completely non-interactive encryption schemes supporting secure encryption of arbitrarily-many messages from arbitrarilymany senders. Our schemes additionally provide forward security and security against chosen-ciphertext attacks. 1
In the classical setting, public-key encryption requires randomness in order to be secure against a forward search attack, whereby an adversary compares the encryption of a guess of the secret message with the encryption of the actual secret message. We show that this is also true in the information-theoretic setting---where the public keys are quantum systems---by defining and giving an example of a forward search attack for any deterministic quantum-public-key bit-encryption scheme. However, unlike in the classical setting, we show that any such deterministic scheme can be used as a black box to build a randomized bit-encryption scheme that is no longer susceptible to this attack.
We provide the first public key encryption schemes proven secure against selective opening attack (SOA). This means that if an adversary obtains a number of ciphertexts and then corrupts some fraction of the senders, obtaining not only the corresponding messages but also the coins under which they were encrypted then the security of theothermessagesisguaranteed. Whetherornotschemeswith this property exist has been open for many years. Our schemes are based on a primitive we call lossy encryption. Our schemes have short keys (public and secret keys of a fixed length suffice for encrypting an arbitrary number of messages), are stateless, are non-interactive, and security does not rely on erasures. The schemes are without random oracles, proven secure under standard assumptions (DDH, Paillier’s DCR, QR, lattices), and even efficient. We are able to meet both an indistinguishability
In this paper, we reevaluate leakage resilient cryptography from the viewpoint of game theory. We provide a general framework on leakage resilience in game theoretic setting and show that it is of each party's interest not to deviate from the protocol, i.e., their behavior is rational which assures them the highest incentive. We show that it is enough for a Public Key Encryption (PKE) scheme to be Computational Threat-Free Nash Equilibrium (CTFNE) for being leakage resilient. To be specific, CTFNE is not guaranteed if an internal state of a CCLA1 (Chosen Ciphertext with Leakage Attack)-secure Key Encapsulation Mechanism (KEM) of PKE is updated using a poor randomness with low-entropy. This work thus allows us for arguing about the strategic behavior of players in protocols where leakage is allowed.