Folder: Reductions

Cryptology City

Cryptology City

❯

465 items under this folder.

#A B C D E F G H I K L M N O P Q R S T U W Z

#

$d$-th Composite Residuosity ⇒ Additively homomorphic encryption
$k$-Linear assumption ⇒ ABE
2PC ⇒ OT
Φ-Hiding ⇒ cPIR
Φ-Hiding ⇒ Lossy TDF (Kiltz–O'Neill–Smith)

A

ABE ⇒ BE
ABE ⇒ Fuzzy IBE
ABE ⇒ IBE
Adaptive robustness ⇒ PRC
Additively homomorphic encryption ⇒ cPIR
Additively homomorphic encryption ⇒ CRHF
Additively homomorphic encryption ⇒ MPC with preprocessing (BDOZ)
Additively homomorphic encryption + Sparse LPN ⇒ SHE
AGM ⇒ KEA
Anonymous HIBE ⇒ HIBE
Attribute-Hiding Security ⇒ Payload-Hiding Security
Authenticated key exchange (AKE) ⇒ KE
Average-case-hard CZK ⇒ CZK ⊄ BPP
Average-case-hard CZK ⇒ OWF
Average-case-hard SZK ⇒ OWF

B

BDH ⇒ ABE
BDH ⇒ CDH
BDH ⇒ HVE
BDH ⇒ IBE (random oracle model)
Bilinear pairing ⇒ CP-ABE
Bilinear pairing ⇒ zk-SNARK
Bilinear pairing + DLIN ⇒ Zaps (non-interactive)
Bilinear pairing + q-SDH ⇒ DS (Boneh–Boyen)
Bilinear pairing + q-SDH ⇒ PCS
Bootstrappable SHE ⇒ Leveled FHE
BPP ⊆ AM
BPP ⊆ BQP
BPP ⊆ coAM
BPP ⊆ P/poly
BPP ⊆ PP
BPP ⊆ PSPACE
BQP ⊆ PP

C

CCA Security ⇒ CCA1 Security
CCA1 Security ⇒ CPA Security
CDH ⇒ DLOG
CDH ⇒ IBE (Döttling–Garg)
CDH ⇒ NIKE (Diffie–Hellman with a hard-core bit)
CDH ⇒ UC-secure OT (DGHMW)
Circular-secure bootstrappable SHE ⇒ Bootstrappable SHE
Circular-secure bootstrappable SHE ⇒ Compact FHE
Claw-free permutations ⇒ Constant-round ZK proofs for NP (Goldreich–Kahan)
Claw-free permutations ⇒ CRHF (Damgård)
CLS hardness ⇒ PPAD hardness
co-CDH ⇒ DS
COM ⇒ Coin flipping (Blum)
COM ⇒ OWF
Commitment hiding for adversarial parameters ⇒ COM
Compact FHE ⇒ HE
Compactly encoded prime-order DLOG ⇒ Prime-order DLOG
coNP ⊆ coAM
coNP ⊆ PSPACE
Constant-bias coin flipping ⇒ OWF
Constant-noise LPN ⇒ PRG
CPA-secure PKE + NIZK ⇒ CCA1-secure PKE (Naor–Yung)
CPA-secure PKE + NIZK ⇒ CCA2-secure PKE (DDN, Sahai)
CPA-secure SKE ⇒ SKE
cPIR with total communication below n ⇒ Non-trivial cPIR
CRHF ⇒ Constant-round ZK argument (Barak)
CRHF ⇒ PCS
CRHF ⇒ STARK
CRHF ⇒ Statistically hiding COM
CRHF ⇒ Succinct arguments for NP (Kilian)
CRHF ⇒ Weak OWF
CRHF + One-time signature ⇒ DS
CZK ⊄ BPP ⇒ Auxiliary-input OWF
CZK ⊆ IP

D

DBDH ⇒ BDH
DBDH ⇒ IBE (Waters, standard model)
DBDH ⇒ Selectively secure IBE (Boneh–Boyen)
DBDH ⇒ Three-party NIKE (Joux)
DBDH + DLIN ⇒ HIBE
DBDH + DLIN ⇒ IBE
DCR (safe-prime moduli) ⇒ CCA-secure PKE (Cramer–Shoup)
DCR ⇒ Additively homomorphic encryption
DCR ⇒ COM
DCR ⇒ FAC
DCR ⇒ Highly lossy TDF (Freeman–Goldreich–Kiltz–Rosen–Segev)
DCR ⇒ One-round sublinear cPIR
DCR ⇒ PKE
DCR ⇒ TDH
DCR ⇒ TPKE
DCR ⇔ $d$-th Composite Residuosity
DDH ⇒ CDH
DDH ⇒ Highly lossy TDF (Peikert–Waters)
DDH ⇒ Multiplicatively homomorphic encryption
DDH ⇒ Non-interactive key exchange (NIKE)
DDH ⇒ PKE
DDH ⇒ PRF (Naor–Reingold)
DDH ⇒ TDH
DDH ⇒ UC-secure OT (PVW)
DDH + Sparse Learning Parity with Noise ⇒ Somewhat homomorphic encryption (SHE)
DDH + UOWHF ⇒ CCA-secure PKE (Cramer–Shoup)
Decision LWE ⇒ Search LWE
Differing-inputs obfuscation (diO) ⇒ iO
Distributional OWF ⇒ OWF (Impagliazzo–Luby)
DLIN ⇒ IPPE
DLIN ⇒ NIZK
DLIN ⇒ PKE (Linear Encryption)
DLOG ⇒ BLS signatures
DLOG ⇒ CDH
DLOG ⇒ CRHF
DLOG ⇒ PCS
DLOG ⇒ PRG
DLOG ⇒ Schnorr identification protocol
DLOG ⇒ Schnorr signatures
DLOG ⇒ Statistically hiding commitment
DLOG ⇒ Verifiable secret sharing (VSS)
DLOG ∈ PWPP
DLOG ∈ SZK
DLOG ⊆ BQP
DLOG ⊆ coNP
DLOG ⊆ NP
DLOG ⊆ TFNP
Doubly enhanced certified TDP ⇒ Enhanced TDP
Doubly enhanced certified TDP ⇒ NIZK
DPF ⇒ Computational Multi-server PIR
DPF ⇒ Multi-point functions
DS ⇒ OWF

E

Enhanced trapdoor permutations ⇒ OT
Evasive circular LWE ⇒ ABE
Evasive LWE ⇒ BE
Evasive LWE + LWE ⇒ Succinct LWE
Evasive LWE + Tensor LWE ⇒ ABE
EXP ⊆ NEXP
Extractable PCS ⇒ SNARK

F

FAC ⇒ DS
FAC ⇒ Factoring Blum integers
FAC ∈ BQP (Shor)
FAC ∈ coNP
FAC ∈ NP
FAC ∈ PPA (under randomized reductions)
FAC ∈ PWPP (under randomized reductions)
FAC ⊆ TFNP
Factoring ⇒ Claw-free permutations (GMR)
Factoring ⇒ TDP (Rabin)
Factoring + UOWHF ⇒ CCA-secure PKE (Hofheinz–Kiltz)
Factoring Blum integers ∈ BQP (Shor)
Factoring with known factor structure ⇒ PRG
FE ⇒ iO
FHE ⇒ cPIR
Function secret sharing (FSS) ⇒ DPF
Fuzzy IBE ⇒ IBE

G

GapSVP ∈ coAM for γ ≥ √(n/log n)
GapSVP ∈ coNP for γ ≥ c√n
GapSVP ∈ NP
GapSVP ∈ SZK for γ ≥ √(n/log n)
GapSVP for polynomial factors ⇒ GapSVP
GC + OT ⇒ Two-party computation (2PC)
GGM ⇒ CDH
GGM ⇒ DDH
GGM ⇒ DLOG
GGM ⇒ KEA

H

Hash function + PRF ⇒ DS (XMSS)
HIBE ⇒ IBE
High-noise LPN ⇒ Constant-noise LPN
High-noise LPN ⇒ Secret-Key PIR (SK-PIR)
High-noise LPN ⇒ SK-DEPIR
Higher residuosity ⇒ PKE
Highly lossy TDF ⇒ CRHF
Highly lossy TDF ⇒ Lossy TDF
Honest majority ($t < n/2$) ⇒ MPC
Honest majority ($t < n/3$) ⇒ MPC
HVE ⇒ Subset and range queries
HVSZK = SZK
HVZK ⇒ NIZK (Fiat–Shamir)

I

IBE ⇒ PKE
ID ⇒ DS
ID ⇒ OWF
Ideal-SVP ⇒ Ring LWE
Ideal-SVP ⇒ Ring-SIS
IND-CCA KEM + CCA-secure SKE ⇒ IND-CCA PKE
IND-CCA security ⇒ IND-CPA KEM
IND-CPA ⇔ Semantic security
IND-CPA KEM + SKE ⇒ IND-CPA PKE
IND-CPA PKE ⇒ IND-CCA KEM (Fujisaki–Okamoto)
IND-CPA PKE ⇒ PKE
IND-ID-CPA IBE ⇒ IBE
IND-ID-CPA Security ⇒ IND-sID-CPA Security (Selective)
IND-sID-CPA Security (Selective) ⇒ HIBE
IND$-CPA Security ⇒ CPA Security
Invertible PRFs ⇒ PRF
iO ⇒ Statistical ZK arguments for NP
iO ⇒ Witness encryption
iO + NP ⊄ io-BPP ⇒ OWF
iO + OWF ⇒ Multiparty NIKE (Boneh–Zhandry)
iO + OWP ⇒ CLS hardness
iO + OWP ⇒ PPAD hardness
IP ⊆ PSPACE
IP ⊆ QIP
IPPE ⇒ HVE
IPPE ⇒ Payload-only hiding
ISIS (Inhomogeneous SIS) ⇔ SIS
IT-PIR ⇒ Computational Multi-server PIR

K

k-Lin ⇒ VRF
KE ⇒ Multi-party key exchange
KEM ⇒ KE

L

Linear secret sharing schemes (LSSS) ⇔ MSP
Linear SS ⇒ IT-PIR
Local Hamiltonian is QMA-complete
Lossy TDF ⇒ Injective TDF
Lossy TDF ⇒ OT
Lossy trapdoor functions ⇒ IND-CCA PKE
Low-exponent RSA ⇒ RSA
Low-noise LPN ⇒ CRHF
Low-noise LPN ⇒ Mid-noise LPN
Low-noise LPN ⇒ TDH
Low-noise LPN + DDH ⇒ NIZK argument for NP
LSN ⇒ LPN
LSN ⇒ Secret-Key PIR (SK-PIR)
LWE ⇒ IBE (Gentry–Peikert–Vaikuntanathan, random oracle model)
LWE ⇒ Lossy TDF (Peikert–Waters)
LWE ⇒ NIZK
LWE ⇒ PKE
LWE ⇒ Selectively secure HIBE (bonsai trees)
LWE ⇒ UC-secure OT (PVW)
LWE at sub-exponential and polynomial ratios ⇒ Bootstrappable SHE (BV11)
LWE with polynomial ratio ⇒ BARG for NP
LWE with polynomial ratio ⇒ Leveled FHE (BV14)
LWE with polynomial ratio ⇒ LWE
LWE with polynomial ratio ⇒ SIS
LWE with polynomial ratio ⇒ SNARG for P
LWE with sub-exponential ratio ⇒ Leveled FHE (BGV12)
LWE with sub-exponential ratio ⇒ LWE
LWE with sub-exponential ratio ⇒ LWE with superpolynomial ratio
LWE with sub-exponential ratio ⇒ LWR
LWE with sub-exponential ratio ⇒ Selectively secure ABE for circuits (GVW)
LWE with superpolynomial ratio ⇒ TDH

M

MA ⊆ AM
MA ⊆ PP
MA ⊆ QCMA
Mid-noise LPN ⇒ High-noise LPN
Mid-noise LPN ⇒ IND-CCA PKE
Mid-noise LPN ⇒ PKE
Mild average-case hardness of Kᵗ ⇔ OWF
MIP = NEXP
MMap + Leveled FHE ⇒ iO
Module LWE (degree 1) ⇔ LWE
Module LWE (rank 1) ⇔ Ring LWE
Module LWE ⇒ IND-CCA KEM
Module LWE + Module-SIS ⇒ DS
Module-SIS ⇒ CRHF
Module-SIVP ⇒ Module LWE
Module-SIVP ⇒ Module-SIS
Multilinear No-Exact-Cover ⇒ Witness encryption (GGSW)

N

n-BDHE ⇒ BE
NIKE ⇒ KE
NIKE ⇒ PKE
NIZK ⇒ Zaps (Dwork–Naor)
NIZK argument for NP ⇒ Non-adaptively sound NIZK argument for NP
NIZK for NP ⇒ NIZK
NIZK proof for NP ⇒ NIZK argument for NP
NIZK proofs with a common random string ⇒ NIZK
Noisy k-LIN + PC ⇒ PKE
Non-trivial cPIR ⇒ OT
Non-trivial cPIR ⇒ OWF
NP ⊆ AM
NP ⊆ MA
NP ⊆ PP
NP ⊆ PSPACE
NTRU ⇒ IND-CCA KEM
NTRU ⇒ PKE
NTRU + NTRU-SIS ⇒ DS

O

OIHF ⇒ OT
One-round sublinear cPIR ⇒ cPIR with total communication below n
One-round sublinear cPIR ⇒ CRHF
OT ⇒ COM
OT ⇒ KE
OT ⇒ OIHF
OT ⇒ Optimally fair coin flipping (Moran–Naor–Segev)
OT ⇒ OT extension (IKNP)
OT + OWF ⇒ OT extension (Beaver)
OT Extension ⇒ MPC with preprocessing (SPDZ, etc.)
OWF ⇒ Constant-round WI proofs for NP (Feige–Shamir)
OWF ⇒ CZK
OWF ⇒ Distributional OWF
OWF ⇒ DS
OWF ⇒ One-time signatures (Lamport)
OWF ⇒ PRG
OWF ⇒ Secret-Key PIR (SK-PIR)
OWF ⇒ Statistical ZK arguments for NP
OWF ⇒ Statistically hiding COM (Haitner–Reingold)
OWF ⇒ UOWHF (Rompel)
OWF ⇒ ZKP
OWF + iO ⇒ Deniable encryption
OWF + iO ⇒ DS
OWF + iO ⇒ FE
OWF + iO ⇒ Non-adaptively sound NIZK argument
OWF + iO ⇒ PKE
OWF + IP ⇒ CZK
OWF inversion ∈ NP
OWP ⇒ OWF
OWP ⇒ PRG (Blum–Micali–Yao)
OWP ⇒ Size-verifiable OWF
OWP ⇒ Statistically hiding COM (NOVY)
OWP ⇒ UOWHF (Naor–Yung)
OWP inversion ∈ NP ∩ coNP

P

Q

QCMA ⊆ QMA
QIP = PSPACE
QM ⇒ OWSG
QMA ⊆ PP
QR ⇒ Additively homomorphic encryption
QR ⇒ COM
QR ⇒ cPIR (Kushilevitz–Ostrovsky)
QR ⇒ FAC
QR ⇒ Lossy TDF (Freeman–Goldreich–Kiltz–Rosen–Segev)
QR ⇒ NIZK proofs with a common random string (Blum–De Santis–Micali–Persiano)
QR ⇒ PKE
QR ⇒ PRG (Blum–Blum–Shub)
QR ⇒ TDH
QR ⇒ UC-secure OT (PVW)
QR ∈ coNP
QR ∈ NP
QR ∈ SZK
QSZK ⊆ QIP
Quantum polynomial-factor GapSVP ⇒ GapSVP for polynomial factors
Quantum polynomial-factor GapSVP ⇒ LWE
Quasi-polynomially hard LWE ⇒ LWE with polynomial ratio
Quasi-polynomially hard LWE ⇒ Statistical zap arguments

R

Rabin OT ⇔ OT
Random OT ⇒ OT
RE ⇒ Statistically rerandomizable encryption
Ring LWE ⇒ PKE (NTRUEncrypt with Gaussian keys)
Ring-LWE ⇒ DE-RAM-MPC
Ring-LWE ⇒ Unkeyed DEPIR
Ring-SIS ⇒ CRHF
ROM ⇒ Merkle puzzles
ROM ⇒ OIHF
ROM ⇒ SNARK (Micali's CS proofs)
RP ⊆ BPP
RP ⊆ NP
RSA ⇒ FAC
RSA ⇒ IND-CCA KEM
RSA ⇒ IND-CCA PKE (RSA-OAEP)
RSA ⇒ PKE
RSA ⇒ TDP
RSA ⇔ FAC

S

Schnorr identification ⇒ Schnorr signatures (Fiat–Shamir)
Search LWE ⇒ Decision LWE
Selective-ID IBE ⇒ CCA-secure PKE (CHK)
Selectively secure HIBE ⇒ Selectively secure IBE
Semi-honest MPC + OWF ⇒ MPC (GMW compiler)
Semi-honest OT ⇒ Malicious OT (Haitner)
Semi-honest OT ⇒ MPC (HIKLP)
SHE ⇒ MPC with preprocessing (SPDZ)
SIS ⇒ CRHF
SIS ⇒ DS
SIS ∈ PWPP
SIVP ⇒ LWE
SIVP ⇒ SIS
Size-verifiable OWF ⇒ OWF
SKE ⇒ OWF
SNARK ⇒ Recursive SNARKs
SNARK + OWF ⇒ NIZK argument
Sparse Learning Parity with Noise ⇒ Pseudorandom correlation generators (PCG)
Sparse Ring-LPN ⇒ PCG
SPIR ⇒ IT-PIR
sPRP ⇒ PRP
SSDDH ⇒ KE
Statistical Difference is SZK-complete
Statistical iO ⇒ iO
Statistically hiding COM ⇒ Statistical ZK arguments for NP
Strong RSA ⇒ COM
Strong RSA ⇒ RSA
Strong RSA + CRHF ⇒ DS
Strongly homomorphic encryption ⇒ Statistically rerandomizable encryption
Structured GGM ⇒ DLOG
Sub-exponential DDH ⇒ DDH
Sub-exponential DDH ⇒ NIZK argument for NP
Sub-exponential DDH ⇒ PPAD hardness
Sub-exponential IND-sID-CPA Security ⇒ IND-ID-CPA Security
Sub-exponential iO + Rerandomizable encryption ⇒ Compact FHE (CLTV)
Sub-exponential iO + Sub-exponential OWF ⇒ TDP (Bitansky–Paneth–Wichs)
Sub-exponential LWE ⇒ LWE
Sub-exponential LWE ⇒ PPAD hardness
Sub-exponential OWF ⇒ OWF
Sub-exponential OWF + iO ⇒ PPAD hardness
Sub-exponential SXDH ⇒ Sub-exponential DDH
Sub-exponential SXDH ⇒ SXDH
Sub-exponential SXDH + LWE + LPN + NC0-PRG ⇒ iO
Sub-exponentially hard LWE at sub-exponential ratio ⇒ LWE with sub-exponential ratio
Sub-exponentially secure iO ⇒ iO
Sub-exponentially secure NC0 PRG ⇒ NC0 PRG
Sub-exponentially selective HIBE ⇒ adaptive HIBE
Subexponential LPN ⇒ CRHF
Subexponential LPN ⇒ IND-CCA PKE
Subexponential LPN ⇒ OT
Subexponential LPN ⇒ PRC
Subexponential LPN ⇒ Zero-bit PRC
Succinct LWE ⇒ ABE
Succinct LWE ⇒ LWE
SUF-CMA MAC + CPA-secure SKE ⇒ CCA-secure SKE
SXDH (Symmetric External Diffie-Hellman) ⇒ NIZK
SXDH ⇒ DDH
Symmetric private information retrieval (Single-server) ⇒ cPIR
Symmetric private information retrieval (Single-server) ⇒ OT
SZK = coSZK
SZK ⊆ AM
SZK ⊆ coAM
SZK ⊆ CZK
SZK ⊆ IP
SZK ⊆ QSZK

T

TDH ⇒ cPIR
TDP ⇒ cPIR with total communication below n (Kushilevitz–Ostrovsky)
TDP ⇒ DS (full-domain hash, random oracle model)
TDP ⇒ Injective TDF
TDP ⇒ OWF
TDP ⇒ PKE

U

UC-secure OT ⇒ Malicious OT
UC-secure OT ⇒ MPC
Unkeyed DEPIR ⇒ cPIR
Unkeyed DEPIR ⇒ PK-DEPIR
UOWHF + One-time signature ⇒ DS (Naor–Yung)

W

WE + PRG ⇒ PKE (GGSW)
Weak alternating moduli ⇒ weak PRF
Weak OWF ⇒ Distributional OWF
Weak OWF ⇒ OWF (Yao)

Z

Zero-bit PRC ⇒ Trapdoor pseudorandom generators
Zero-bit PRC ⇒ Watermarking
ZPP ⊆ RP

Created with Quartz v4.5.2 © 2026

GitHub
Bluesky