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

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

Repeated Games for Generating Randomness in Encryption

Kenji Yasunaga, Kosuke Yuzawa

Published Jan 1, 2018• 3 citations
Publisher

Abstract

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.

DOI
10.1587/transfun.e101.a.697

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. 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.

•Jan 1, 2013•0 citations

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

New Notions of Secrecy and User Generated Randomness in Cryptography

Mohsen Alimomeni

Randomness plays a central role in computer science, in particular cryptography. Almost all cryptographic primitives depend crucially on randomness because randomness and unpredictability in secret keys provides the means for security. Usually one assumes that perfect randomness, a sequence of independently and uniformly distributed bits, are accessible to algorithms. This is a strong assumption. Physical sources of randomness are neither uniformly random, nor produce necessarily independent bits. Therefore, the aim of this thesis is to start from a realistic model of randomness, investigate notions of secrecy and their randomness requirements and finally find practical methods for generation of randomness that matches the requirements of cryptographic primitives. We consider a model of random source where the source output follows one distribution from a set of possible distributions, each with the property that the maximum probability of symbols is bounded and can not be arbitrarily close to 1. This model does not assume independence or uniformity of the output symbols, and is considered to be a realistic model of randomness. From this point, the thesis can be divided into two main parts: In the first part, considering various notions of information theoretic secrecy, a fundamental problem is to find the properties of randomness needed to achieve security in these notions. Traditional cryptographic protocols simply assume perfect randomness and build on this assumption. We explore the results that show secrecy can not be based on imperfect randomness that is not uniform or independent. Thus a line of work attempts to relax notions of secrecy in such a way that they can be constructed with non-perfect sources, and possibly require smaller key sizes. Yet they should match real life applications. An important work in this context is entropic security where the key size could be smaller than the message depending on message distribution. Inspired by this, we propose two relaxed notions of secrecy that are motivated by practical applications. In the first notion, motivated by an application in biometrics authentication, we propose guessing secrecy where the probability of guessing the message for a computational unbounded adversary with the best strategy remains the same when a ciphertext is given or when it is not. We compare the randomness requirements of guessing secrecy with stronger notions and show that in some cases such as key length, the requirements are the same. For key distribution however, we found a family of distributions that provide guessing secrecy but not perfect secrecy. In the second notion, we investigate randomness requirements of multiple message encryption. Considering a natural extension of secrecy definition to multiple messages, we show that independent keys are needed to encrypt each message. We then propose a relaxed notion in which the security of last message is more important than past messages, although the leakage of past messages is bounded using entropic security. By this assumption, we achieve smaller key length compared to indistinguishability, and comparable to key length for entropic security. This notion has applications such as location privacy. In the second part of the thesis, since secrecy crucially depends on perfect randomness, we investigate how perfect randomness can be practically generated, specifically from human game-play. Unlike many random number generators that assume independent or uniform random bits in the random source, we base our work on the realistic model of randomness. Our main observation is that human game-play has an element of randomness coming from the errors in their game-play which is the main entertaining factor of the game. We also observed that this game-play can distinguish among a group of people if the right features are collected from the game-play. We incrementally changed our game design until the distinguishability among a small population is maximized, and then run the experiments required to show the viability of this approach over a larger population. This approach can also provide a hard to delegate authentication property where a human could not emulate the behavior of another human even given statistical information about their game-play.

•Jan 1, 2014•1 citation

Repeated Games for Generating Randomness in Encryption.

Kenji Yasunaga, Kosuke Yuzawa

•Jan 1, 2017•0 citations

Broadcast Encryption Scheme from Lattice

Jin Wang, Bo Sun, Xin Li

Motivated by the lattice basis delegation technique due to [8, 22, 9], we propose a broadcast encryption scheme based on the hard worst-case lattice problems. The proposed scheme is secure in the random oracle model. To the best of the authors' knowledge, our construction constitute the first broadcast encryption schemes from lattices.

International Conference on E-Business and E-Government•May 11, 2012•0 citations

Games for extracting randomness

Ran Halprin, Moni Naor

Randomness is a necessary ingredient in various computational tasks and especially in Cryptography, yet many existing mechanisms for obtaining randomness suffer from numerous problems. We suggest utilizing the behavior of humans while playing competitive games as an entropy source, in order to enhance the quality of the randomness in the system. This idea has two motivations: (i) results in experimental psychology indicate that humans are able to behave quite randomly when engaged in competitive games in which a mixed strategy is optimal, and (ii) people have an affection for games, and this leads to longer play yielding more entropy overall. While the resulting strings are not perfectly random, we show how to integrate such a game into a robust pseudo-random generator that enjoys backward and forward security.

Symposium On Usable Privacy and Security•Jul 15, 2009•34 citations
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.
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.
Randomness plays a central role in computer science, in particular cryptography. Almost all cryptographic primitives depend crucially on randomness because randomness and unpredictability in secret keys provides the means for security. Usually one assumes that perfect randomness, a sequence of independently and uniformly distributed bits, are accessible to algorithms. This is a strong assumption. Physical sources of randomness are neither uniformly random, nor produce necessarily independent bits. Therefore, the aim of this thesis is to start from a realistic model of randomness, investigate notions of secrecy and their randomness requirements and finally find practical methods for generation of randomness that matches the requirements of cryptographic primitives. We consider a model of random source where the source output follows one distribution from a set of possible distributions, each with the property that the maximum probability of symbols is bounded and can not be arbitrarily close to 1. This model does not assume independence or uniformity of the output symbols, and is considered to be a realistic model of randomness. From this point, the thesis can be divided into two main parts: In the first part, considering various notions of information theoretic secrecy, a fundamental problem is to find the properties of randomness needed to achieve security in these notions. Traditional cryptographic protocols simply assume perfect randomness and build on this assumption. We explore the results that show secrecy can not be based on imperfect randomness that is not uniform or independent. Thus a line of work attempts to relax notions of secrecy in such a way that they can be constructed with non-perfect sources, and possibly require smaller key sizes. Yet they should match real life applications. An important work in this context is entropic security where the key size could be smaller than the message depending on message distribution. Inspired by this, we propose two relaxed notions of secrecy that are motivated by practical applications. In the first notion, motivated by an application in biometrics authentication, we propose guessing secrecy where the probability of guessing the message for a computational unbounded adversary with the best strategy remains the same when a ciphertext is given or when it is not. We compare the randomness requirements of guessing secrecy with stronger notions and show that in some cases such as key length, the requirements are the same. For key distribution however, we found a family of distributions that provide guessing secrecy but not perfect secrecy. In the second notion, we investigate randomness requirements of multiple message encryption. Considering a natural extension of secrecy definition to multiple messages, we show that independent keys are needed to encrypt each message. We then propose a relaxed notion in which the security of last message is more important than past messages, although the leakage of past messages is bounded using entropic security. By this assumption, we achieve smaller key length compared to indistinguishability, and comparable to key length for entropic security. This notion has applications such as location privacy. In the second part of the thesis, since secrecy crucially depends on perfect randomness, we investigate how perfect randomness can be practically generated, specifically from human game-play. Unlike many random number generators that assume independent or uniform random bits in the random source, we base our work on the realistic model of randomness. Our main observation is that human game-play has an element of randomness coming from the errors in their game-play which is the main entertaining factor of the game. We also observed that this game-play can distinguish among a group of people if the right features are collected from the game-play. We incrementally changed our game design until the distinguishability among a small population is maximized, and then run the experiments required to show the viability of this approach over a larger population. This approach can also provide a hard to delegate authentication property where a human could not emulate the behavior of another human even given statistical information about their game-play.
Randomness is a necessary ingredient in various computational tasks and especially in Cryptography, yet many existing mechanisms for obtaining randomness suffer from numerous problems. We suggest utilizing the behavior of humans while playing competitive games as an entropy source, in order to enhance the quality of the randomness in the system. This idea has two motivations: (i) results in experimental psychology indicate that humans are able to behave quite randomly when engaged in competitive games in which a mixed strategy is optimal, and (ii) people have an affection for games, and this leads to longer play yielding more entropy overall. While the resulting strings are not perfectly random, we show how to integrate such a game into a robust pseudo-random generator that enjoys backward and forward security.