[Q&A] Cryptographic Primitives and Assumptions

Public-Key Encryption

• Is the RSA cryptosystem provably secure?
• Are there public-key cryptosystems not relying on arithmetic over finite fields? (short answer: yes)
• Are there knapsack-based cryptosystems which have not been broken? (short answer: yes)
• Are there practical universal PKE schemes? (short answer: no)
• Are there encryption schemes where the sender cannot prove that a given plaintext was encrypted?
• Can we use ElGamal over $\mathbb{Z}_{n^2}$? (short answer: not directly)

Homomorphic Encryption

• Can FHE compute comparisons? (short answer: yes)
• Are there FHE schemes for deep learning operations? (short answer: yes)
• How short can be an FHE ciphertext? (short answer: almost as short as the message it encrypts)
• Are all homomorphic encryption schemes based on lattices? (short answer: it depends)
• Is there a BGN-like encryption scheme without restriction on the plaintext space? (short answer: yes)
• Are there additive homomorphic encryption schemes that support exponentiation?

Obfuscation

• Why do we use multilinear maps in obfuscation schemes? (short answer: they are essentially necessary in a well defined sense – though that does not mean constructions must explicitely go through them!)
• Can we obfuscate functions that are mostly zero? (short answer: there is a gradation of increasingly complex obfuscation schemes from increasingly stronger assumptions for increasingly larger subclasses of mostly zero function; the linked answer provide a detailed overview.)

Symmetric Primitives

• Why is it plausible that hash functions are quantum secure?
• Does IND-CPA security imply PRFs? (short answer: yes)
• Is it possible to build a symmetric encryption scheme with beyond-brute-force security? (short answer: yes, but only if the messages come from a specific distribution)
• What are the differences between the various notions of CPA security?

Cryptographic Assumptions

• Is it hard to compute $(g^{ab})$ given $(g^a, g^b, a/b)$? (short answer: yes, under the square Diffie-Hellman assumption)
• Why do subexponential attacks on the DLP not work for ECDLP? (short answer: you don’t have small prime values over elliptic curves in general)
• What relation is known between LWE and LPN?
• Are there known reductions from LWE to MLWE or RLWE? (short answer: no)
• Are there decisional variants of the discrete logarithm problem? (short answer: yes)

Others

• What are smooth projective hash functions?
• Why do we use pairing-based cryptography?
• Is there a password-authenticated key-exchange making only a blackbox use of standard cryptographic primitives? (short answer: this seems open, and it is a great question)
• Why are generalized Pedersen commitments secure?
• Are there results on the space complexity of cryptographic primitives? (short answer: yes)
• Why are VDFs preferred to proofs of sequential work?
• What are the cryptographic advantages of using the subgroup of pseudosquares?
• What are the standard constructions of PRFs from well-known assumptions?
• Can you build searchable encryption from the discrete logarithm problem?
• Is it possible to prove that a document was generated long ago?
• Can Pedersen commitments be made deterministic? (short answer: only if you have high min-entropy plaintexts and settle for a weaker security notion)