# [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)

** Tags: **
assumptions,
cryptography stackexchange,
primitives

** Categories: **
Q&A

** Updated:**