3
$\begingroup$

I've read our recent question: "One-time pad using RSA and Diffie-Hellman functions" which asks about the security of a particular way to convert RSA and discrete exponentiation into a stream cipher. The approach didn't work out, as expected, knowing that it was an interview question.

Now, the following question came over me:
Is it (constructively) possible to create a stream cipher whose IND-CPA security can be directly reduced to a well-known number-theoretic assumption?

To be clear: I'd like to know (out of curiosity, no deployment intended) whether there exists a stream cipher which is as hard to break as CDH (or another assumption) with no other assumptions (no random oracles, no constructed PRPs like AES, no constructed PRFs like SHA-2, ...) and if such a stream cipher can exist , I'd also like to know how to build it (e.g. give a brief description please).

Example assumptions: "factoring is hard", "the RSA problem is hard", DLOG, CDH, DDH

Improve this question
$\endgroup$
4
  • $\begingroup$ I'm open for improvements to the title of the question and / or any parts of the question (please just suggest an edit then). $\endgroup$
    – SEJPM
    Apr 7, 2016 at 18:38
  • $\begingroup$ There are many examples, e.g., Blum-Goldwasser is based on "factoring is hard." More generally, any public-key encryption can be used to share a random seed for a stream cipher. Such a stream cipher can be built from any PRG, which can be built based on any of the assumptions you list. $\endgroup$
    – Chris Peikert
    Apr 7, 2016 at 19:10
  • $\begingroup$ @ChrisPeikert, sounds like an answer too me... $\endgroup$
    – SEJPM
    Apr 7, 2016 at 19:12
  • $\begingroup$ I wonder if DualEC-DRBG fits the bill. $\endgroup$
    – CodesInChaos
    Apr 7, 2016 at 19:18

1 Answer 1

Reset to default
2
$\begingroup$

Sure.

one-way permutation ​ + ​ strong hard-core functions
$\to$
pseudorandom generator
$\to$
stream cipher

The keystream is concatenation of the strong hard-core function's values at
the iterates of the one-way permutation on the key. ​ ( k,f(k),f(f(k)),f(f(f(k))),... )

Improve this answer
$\endgroup$

Your Answer

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

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