Score:1

Generating a public-private key pair from another key pair

sa flag

Is the following problem a known cryptographic problem?

Find algorithms for functions $f$ and $g$, such that

$$ f(x, \alpha_{enc}) \rightarrow \beta_{enc}\\ g(x, \alpha_{dec}) \rightarrow \beta_{dec} $$

where $x$ is some data of $n$ bits, and $(\alpha_{enc}, \alpha_{dec})$ and $(\beta_{enc}, \beta_{dec})$ are (public, private) key pairs.

The problem probably depends on the type of asymmetric encryption algorithm being used. For simplicity we can assume that the key pairs are RSA key pairs.

If this isn't a known problem in cryptography, is it possible to find the algorithms for $f$ and $g$?


As a side note, I'm familiar with programming but I'm not very familiar with cryptography.

Score:1
ru flag

I don't think that there's a good way to instantiate this directly with RSA, but what you describe seems to be a rough description of identifier-based encryption. If we think of the value $x$ as representing a user's identifier and $\alpha_{enc}$ as a publicly known system parameter. Then $\beta_{enc}$ represents the ability to encrypt with a key specific to the user $x$,. We then ask if it is possible for a central authority that knows $\alpha_{dec}$ to securely generate $\beta_{dec}$ and provide that only to the user with identifier $x$.

The concept of identifier-based cryptography was introduced by Adits Shamir in his seminal paper "Identity-based cryptosystems and signature schemes" and that is a good place to read around the central concepts. He also has an example identifier-based signature scheme using RSA-like structure (an $\alpha$ values are an RSA modulus and factors; $\beta$ values are simply $x$ and the RSA decryption of $x$), which although it doesn't work for encryption is a useful starting point if RSA is the asymmetric method with which you are most familiar.

Identifier-based cryptography hit a rich patch with the advent of pairing-based cryptography, which did allow efficient identifier-based encryption using more sophisticated mathematics in such schemes as Sakai-Kasahara or Boneh-Franklin. There are many examples of standards, implementations and libraries for such schemes.

All of the above has the assumption that you want it to be hard to recover $\alpha_{dec}$ even if in possession of $\beta_{dec}$. If this is not a requirement then much simpler methods using El Gamal encryption are possible.

aiwl avatar
sa flag
Perfect! The problem description in the first paragraph seems to be exactly what I am looking for, except I originally had it in mind for time lock encryption, in which case $x$ is a specific time, and the central authority only generates $\beta_{dec}$ if $x \geq t$, where $t$ is the current time. I appreciate the detailed answer; it is very useful.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.