Cryptology City
Search
Search
Dark mode
Light mode
Explorer
Cryptology City
Home
❯
Reductions
343 items under this folder.
#
A
B
C
D
E
F
G
H
I
K
L
M
N
O
P
Q
R
S
T
U
V
Z
#
$d$-th Composite Residuosity ⇒ HE
$k$-Linear assumption ⇒ ABE
$k$-out-of-$n$ OT ⇔ cPIR
Φ-Hiding ⇒ cPIR
A
ABE ⇒ BE
ABE ⇒ Fuzzy IBE
ABE ⇒ HIBE
ABE ⇒ IBE
Adaptive robustness ⇒ PRC
Adversary models ⇒ Privacy (semi-honest)
AE + Hash function + PRF ⇒ Symmetric CP-ABE
AGM ⇒ KEA
Alternating moduli assumption ⇒ MPC
Alternating moduli assumption ⇒ PRF
Alternating moduli assumption ⇒ Pseudorandom correlation generators (PCG)
AM = coAM
Anonymous HIBE ⇒ HIBE
Arithmetization ⇒ SNARK
Arithmetization ⇒ zk-SNARK
Arithmetization + FRI (Fast Reed-Solomon IOP of Proximity) ⇒ SNARK
Arithmetization + NIZK + PCS ⇒ SNARK
Arithmetization + PCS ⇒ SNARK
Attribute-Hiding Security ⇒ Payload-Hiding Security
Authenticated key exchange (AKE) ⇒ KE
B
BDH ⇒ ABE
BDH ⇒ AC
BDH ⇒ BE
BDH ⇒ DS
BDH ⇒ HIBE
BDH ⇒ HVE
BDH ⇒ IBE
BDH ⇒ NIZK
BDH ⇒ VRF
Bilinear pairing ⇒ DS
Bilinear pairing ⇒ SNARK
Bilinear pairing + q-SDH ⇒ KZG (Kate-Zaverucha-Goldberg)
Bilinear pairing + q-SDH ⇒ PCS
BPP ⊆ AM
BPP ⊆ BQP
BPP ⊆ coAM
BPP ⊆ P/poly
BPP ⊆ PP
BPP ⊆ PSPACE
BQP ⊆ DLOG
BQP ⊆ PP
C
CCA Security ⇒ CCA1 Security
CCA1 Security ⇒ CPA Security
CDH ⇒ BDH
CDH ⇒ DDH
CDH ⇒ DLOG
Circular security + LWE ⇒ HE
Circular security + Somewhat homomorphic encryption (SHE) ⇒ HE
co-CDH ⇒ DS
COM ⇒ MPC
COM ⇒ OT
COM ⇒ Two-party computation (2PC)
COM + SS ⇒ Verifiable secret sharing (VSS)
coNP ⊆ AM
coNP ⊆ coAM
coNP ⊆ PSPACE
CPA Security ⇔ CPA Security
cPIR ⇒ OT
CZK = IP
D
DCR ⇒ COM
DCR ⇒ HE
DCR ⇒ Partially homomorphic encryption (PHE)
DCR ⇒ PKE
DCR + Sparse Learning Parity with Noise ⇒ Somewhat homomorphic encryption (SHE)
DDH ⇒ CDH
DDH ⇒ COM
DDH ⇒ KE
DDH ⇒ Non-interactive key exchange (NIKE)
DDH ⇒ PKE
DDH ⇒ PRF (Naor–Reingold)
DDH ⇒ TDH
DDH + LPN + LWE + NC1-PRG ⇒ iO
DDH + Sparse Learning Parity with Noise ⇒ Somewhat homomorphic encryption (SHE)
Decision LWE ⇒ Search LWE
DEPIR ⇒ cPIR
Differing-inputs obfuscation (diO) ⇔ iO
DKG + HE ⇒ TPKE
DLIN ⇒ IPPE
DLOG ⇒ BLS signatures
DLOG ⇒ CDH
DLOG ⇒ DDH
DLOG ⇒ DS
DLOG ⇒ PCS
DLOG ⇒ PRG
DLOG ⇒ Schnorr signatures
DLOG ⇒ TDP
DLOG ⇒ ZKP
DLOG + ROM ⇒ Schnorr signatures
DLOG ⊆ coNP
DLOG ⊆ NP
DLOG ⊆ TFNP
DPF ⇒ Computational Multi-server PIR
DPF ⇒ IT-PIR
DPF ⇒ Multi-point functions
DS ⇒ Hash function
E
Enhanced trapdoor permutations ⇒ OT
Evasive LWE ⇒ ABE
Evasive LWE ⇒ ABE
Evasive LWE ⇒ BE
F
FAC ⇒ DCR
FAC ⇒ DS
FAC ⇒ QR
FAC ⇒ RSA
FAC ⊆ TFNP
Factoring with known factor structure ⇒ PRG
Falsifiable assumption ⇒ SNARK
FE ⇒ iO
Fiat-Shamir + Honest-verifier ZK (HVZK) ⇒ NIZK
Fiat-Shamir + Schnorr signatures ⇒ DS
Fiat-Shamir + Schnorr signatures ⇒ Schnorr signatures
FRI (Fast Reed-Solomon IOP of Proximity) ⇒ SNARK
Function secret sharing (FSS) ⇒ DPF
Fuzzy IBE ⇒ IBE
G
GapSVP ⇒ LWE
GapSVP ⇒ SIS
GC + OT ⇒ Two-party computation (2PC)
GGM ⇒ ABE
H
Hash function ⇒ CZK
Hash function ⇒ DPF
Hash function ⇒ DS
Hash function ⇒ Hash-based signatures
Hash function ⇒ Hash-based signatures
Hash function ⇒ MAC
Hash function ⇒ PCS
Hash function ⇒ PRF
Hash function ⇒ PRG
Hash function ⇒ Secret-Key PIR (SK-PIR)
Hash function ⇒ SKE
Hash function ⇒ SNARK
Hash function ⇒ ZKP
Hash function + Hash-based signatures ⇒ DS
Hash function + iO ⇒ Deniable encryption
Hash function + iO ⇒ DS
Hash function + iO ⇒ FE
Hash function + iO ⇒ Lossy trapdoor functions
Hash function + iO ⇒ NIZK
Hash function + iO ⇒ PKE
Hash function + PRF ⇒ Symmetric CP-ABE
Hash-based signatures ⇒ DS
Hash-based signatures + Hash-based signatures ⇒ DS
HE ⇒ MPC with preprocessing (SPDZ, etc.)
HE ⇒ RE
HIBE ⇒ IBE
Higher residuosity ⇒ PKE
Honest majority ($t < n/3$ or $t < n/2$) ⇒ MPC
HVE ⇒ Subset and range queries
I
IBE ⇒ PKE
ID + ROM ⇒ DS
Ideal PRC ⇒ PRC
Ideal-SVP ⇒ Ring LWE
Ideal-SVP ⇒ Ring-SIS
IND-CCA security ⇒ IND-CPA KEM
IND-CPA KEM ⇒ IND-CCA security
IND-ID-CPA Security ⇒ IND-sID-CPA Security (Selective)
IND-sID-CPA Security (Selective) ⇒ IND-ID-CPA Security
interactive protocol + ROM ⇒ NIZK
interactive protocol + ROM ⇒ SNARK
Invertible PRFs ⇒ PRF
IP + ROM ⇒ SNARK
IP ⊆ AM
IP ⊆ PSPACE
IP ⊆ QIP
IP ⊆ SZK
IPPE ⇒ HVE
IPPE ⇒ Payload-only hiding
ISIS (Inhomogeneous SIS) ⇒ DS
ISIS (Inhomogeneous SIS) ⇔ SIS
IT-PIR ⇒ Computational Multi-server PIR
K
KE ⇒ Multi-party key exchange
KE ⇒ PKE
KEA ⇒ SNARK
KEM ⇒ KE
KEM + SKE ⇒ PKE
KZG (Kate-Zaverucha-Goldberg) ⇒ SNARK
L
Linear secret sharing schemes (LSSS) ⇔ MSP
Lossy trapdoor functions ⇒ PKE
Lossy trapdoor functions ⇒ TDP
LPN ⇒ PKE
LPN ⇒ Secret-Key PIR (SK-PIR)
LPN + LWE + NC1-PRG ⇒ iO
LSN ⇒ LPN
LSN ⇒ Secret-Key PIR (SK-PIR)
LWE ⇒ DE-RAM-MPC
LWE ⇒ DEPIR
LWE ⇒ IND-CPA KEM
LWE ⇒ Lattice-based signatures
LWE ⇒ Leveled fully homomorphic encryption
LWE ⇒ PKE
LWE ⇒ PRC
LWE ⇒ TDH
LWE ⇒ Zero-bit PRC
LWE + SIS ⇒ DS
M
MA ⊆ AM
MA ⊆ PP
MA ⊆ QCMA
MAC + SKE ⇒ CCA Security
MMap ⇒ iO
Module LWE ⇒ KEM
Module LWE ⇔ LWE
Module LWE ⇔ Ring LWE
Module LWE + Module-SIS ⇒ DS
Module-SIS ⇒ DS
Module-SVP ⇒ Module LWE
Module-SVP ⇒ Module-SIS
MPC ⇒ OT
N
NIZK ⇒ COM
Noise Level ⇒ DEPIR
Noise Level ⇒ DEPIR
Noise Level ⇒ Hash function
Noise Level ⇒ Noise Level
Noise Level ⇒ PKE
Noise Level ⇒ TDH
Noisy k-LIN + PC ⇒ PKE
Notable problems = QMA
NP = coNP
NP ⊆ AM
NP ⊆ MA
NP ⊆ PP
NP ⊆ PSPACE
NTRU ⇒ DS
NTRU ⇒ KEM
NTRU ⇒ PKE
O
OIHF ⇒ OT
OT ⇒ COM
OT ⇒ MPC
OT Extension ⇒ MPC with preprocessing (SPDZ, etc.)
OWF ⇒ PRG
OWP ⇒ Hash function
OWSG ⇒ QM
OWSG ⇒ Unclonable encryption
P
P ⊆ BPP
P ⊆ coNP
P ⊆ NP
P ⊆ P/poly
P ⊆ RP
P ⊆ ZPP
Partially homomorphic encryption (PHE) + Sparse Learning Parity with Noise ⇒ Somewhat homomorphic encryption (SHE)
PC + Search noisy $k$-LIN ⇒ PKE
PCS ⇒ NIZK
PCS ⇒ SNARK
PCS ⇔ Vector commitments
Permuted puzzles ⇒ DEPIR
PKE ⇒ COM
PKE ⇒ Hash function
PKE ⇒ KE
PKE ⇒ KEM
PKE ⇒ OT
PP ⊆ PSPACE
PRC ⇒ SKE
PRF ⇒ CPA-secure SKE
PRF ⇒ iPRF
PRF ⇒ MAC
PRF ⇒ PRP
PRG ⇒ COM
PRG ⇒ DPF
PRG ⇒ Hash function
PRG ⇒ PRF (GGM)
PRG ⇒ SKE
PRG in NC1 ⇒ iO
PRP ⇒ iPRF (large domains)
PRP ⇒ PRF
PSPACE ⊆ EXP
Q
QCMA ⊆ PP
QCMA ⊆ QMA
QIP = IP
QIP = PSPACE
QMA ⊆ PP
QR ⇒ COM
QR ⇒ HE
QR ⇒ PKE
QR ⇒ TDH
QR ⇒ ZKP
QSZK ⊆ QIP
R
Rabin OT ⇔ OT
Random OT ⇒ OT
Ring LWE ⇒ NTRU
Ring-LPN ⇒ MAC
Ring-LPN ⇒ Pseudorandom correlation generators (PCG)
ROM ⇒ OIHF
ROM + ZKP ⇒ DS
ROM + ZKP ⇒ NIZK
RP ⊆ BPP
RP ⊆ NP
RSA ⇒ IND-CCA security
RSA ⇒ Partially homomorphic encryption (PHE)
RSA ⇒ PKE
RSA ⇒ TDP
RSA ⇔ FAC
S
Schnorr signatures ⇒ Schnorr signatures
Search LWE ⇒ Decision LWE
Secret-Key PIR (SK-PIR) ⇒ DEPIR
Secret-Key PIR (SK-PIR) + SKE ⇒ DEPIR
SIDH ⇒ KE
SIS ⇒ DS
SIS ⇒ Hash function
SIVP ⇒ LWE
SIVP ⇒ SIS
SNARK ⇒ Hash function
SNARK ⇒ NIZK
SNARK ⇒ Recursive SNARKs
Somewhat homomorphic encryption (SHE) ⇒ HE
Sparse Learning Parity with Noise ⇒ LPN
Sparse Learning Parity with Noise ⇒ Pseudorandom correlation generators (PCG)
SPIR ⇒ IT-PIR
SS ⇒ IT-PIR
Strong alternating moduli (chosen-input) assumption ⇒ Weak alternating moduli (random-input) assumption
Strong RSA ⇒ COM
Strong RSA ⇒ DS
Strong RSA ⇒ RSA
Strong Security ⇒ PRP
Subclasses ⇒ Hash function
Subexponential LPN ⇒ OT
Subexponential LPN ⇒ PKE
Subexponential LPN ⇒ PRC
Succinct LWE ⇒ ABE
Succinct LWE ⇒ Evasive LWE
Succinct LWE ⇔ LWE
SXDH (Symmetric External Diffie-Hellman) ⇒ BDH
SXDH (Symmetric External Diffie-Hellman) ⇒ NIZK
Symmetric private information retrieval (Single-server) ⇒ cPIR
Symmetric private information retrieval (Single-server) ⇔ OT
SZK ⊆ AM
SZK ⊆ coAM
SZK ⊆ CZK
SZK ⊆ IP
SZK ⊆ QSZK
T
TDH ⇒ cPIR
TDP ⇒ Hash function
TDP ⇒ NIZK
TDP ⇒ PKE
TDP ⇔ OT
Trapdoor pseudorandom generators ⇔ PRG
U
Unkeyed DEPIR ⇒ DEPIR
V
Verifiable secret sharing (VSS) ⇒ MPC
Z
Zero-bit PRC ⇒ Trapdoor pseudorandom generators
Zero-bit PRC ⇒ Watermarking
ZKP ⇒ Hash function
ZKP ⇒ NIZK
ZPP ⊆ RP