1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – aiwl
    Feb 4, 2022 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.