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

  • $\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 '16 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 '16 at 19:10
  • $\begingroup$ @ChrisPeikert, sounds like an answer too me... $\endgroup$ – SEJPM Apr 7 '16 at 19:12
  • $\begingroup$ I wonder if DualEC-DRBG fits the bill. $\endgroup$ – CodesInChaos Apr 7 '16 at 19:18


one-way permutation ​ + ​ strong hard-core functions
pseudorandom generator
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 | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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