Summary Technique 1: Reduce soundness error with probabilistically checkable proofs Technique 2: Implement hidden random bit string with Naccache-Stern encryption Hidden bitsProof in bitsAssumption Kilian-Petrank |C|∙k T ∙k∙  (log k) Trapdoor perms This work|C|∙k T ∙polylog(k) Trapdoor perms CRS in bitsProof in bitsAssumption Gentrypoly(k)|w|∙poly(k)Lattice-based + NIZK G-Ostrovsky-Sahaik 3 /polylog(k)|C|∙k 3 /polylog(k)Pairing-based This talk|C|∙polylog(k) Naccache-Stern Other workpoly(k)|w| + poly(k)FHE + NIZK
{}