Cryptology City
Search
Search
Dark mode
Light mode
Explorer
Cryptology City
Home
❯
Reductions
619 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 ⇒ 2PC with expected-time simulation
2PC ⇒ Malicious OT
Φ-Hiding ⇒ cPIR
Φ-Hiding ⇒ DS (RSA full-domain hash, tight)
Φ-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 ⇒ HE
Additively homomorphic encryption + Sparse LPN ⇒ SHE
AGM ⇒ KEA
Anonymous HIBE ⇒ HIBE
Attribute-Hiding Security ⇒ Payload-Hiding Security
Authenticated channels ⇒ Broadcast against $t < n/3$ (Lamport–Shostak–Pease)
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 + k-Lin ⇒ BARG for NP
Bilinear pairing + q-DLOG ⇒ Universal SNARK (PLONK)
Bilinear pairing + q-DLOG ⇒ zk-SNARK (Groth16 in the AGM)
Bilinear pairing + q-SDH ⇒ DS (Boneh–Boyen)
Bilinear pairing + q-SDH ⇒ PCS
BLS signatures ⇒ DS
Bootstrappable SHE ⇒ Leveled FHE
Bootstrappable SHE ⇒ SHE
BPP ⊆ AM
BPP ⊆ BQP
BPP ⊆ coAM
BPP ⊆ P/poly
BPP ⊆ PP
BPP ⊆ PSPACE
BQP ⊆ PP
Byzantine broadcast ⇒ Broadcast against $t < n/3$
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 ⇒ Two-round UC-secure OT (DGHMW)
Circuit-private HE for NC1 ⇒ IND-CPA PKE
Circular-secure bootstrappable SHE ⇒ Bootstrappable SHE
Circular-secure bootstrappable SHE ⇒ Compact FHE
Circular-secure FHE ⇒ Compact FHE
Circular-secure FHE ⇒ NIZK argument for NP
Claw-free permutations ⇒ Concurrent ZK proofs for NP in ω(log n) rounds
Claw-free permutations ⇒ Constant-round ZK proofs for NP (Goldreich–Kahan)
Claw-free permutations ⇒ CRHF (Damgård)
CLS hardness ⇒ PPAD hardness
co-CDH ⇒ Aggregate signatures (BGLS)
co-CDH ⇒ BLS multi-signatures with public-key aggregation
co-CDH ⇒ BLS signatures
co-CDH ⇒ co-CDH without an isomorphism
COM ⇒ Coin flipping (Blum)
COM ⇒ OWF
Commitment hiding for adversarial parameters ⇒ COM
Compact FHE ⇒ HE
Compact private-key XOR-homomorphic encryption ⇒ PKE
Compactly encoded prime-order DLOG ⇒ Prime-order DLOG
coNP ⊆ coAM
coNP ⊆ PSPACE
Constant-bias coin flipping ⇒ OWF
Constant-noise LPN ⇒ PRG
Constant-round black-box ZK with strict polynomial-time simulation ⊆ BPP
Constant-round public-coin black-box ZK ⊆ BPP
Correlated randomness ⇒ UC MPC (BDOZ online phase)
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
cPIR with total communication below n ⇒ OT
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 ⇒ constant-bandwidth ORAM (Onion ORAM)
DCR ⇒ FAC
DCR ⇒ Four-round MPC (Badrinarayanan–Goyal–Jain–Kalai–Khurana–Sahai)
DCR ⇒ Highly lossy TDF (Freeman–Goldreich–Kiltz–Rosen–Segev)
DCR ⇒ Length-flexible additively homomorphic encryption (Damgård–Jurik)
DCR ⇒ One-round sublinear cPIR
DCR ⇒ PKE
DCR ⇒ TDH
DCR ⇒ TPKE
DCR ⇔ $d$-th Composite Residuosity
DDH ⇒ CDH
DDH ⇒ Four-round MPC (Badrinarayanan–Goyal–Jain–Kalai–Khurana–Sahai)
DDH ⇒ Highly lossy TDF (Peikert–Waters)
DDH ⇒ Multiplicatively homomorphic encryption
DDH ⇒ Non-interactive key exchange (NIKE)
DDH ⇒ PIR with client preprocessing (CHK22)
DDH ⇒ PKE
DDH ⇒ PRF (Naor–Reingold)
DDH ⇒ TDH
DDH ⇒ Two-round 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
Digital signatures ⇒ Byzantine broadcast (Dolev–Strong)
Distributional OWF ⇒ OWF (Impagliazzo–Luby)
DLIN ⇒ IPPE
DLIN ⇒ NIZK
DLIN ⇒ PKE (Linear Encryption)
DLOG ⇒ Blind Okamoto–Schnorr signatures
DLOG ⇒ BLS signatures
DLOG ⇒ CDH
DLOG ⇒ CRHF
DLOG ⇒ EdDSA
DLOG ⇒ MuSig
DLOG ⇒ Okamoto identification protocol
DLOG ⇒ PCS
DLOG ⇒ PRG
DLOG ⇒ Schnorr identification protocol
DLOG ⇒ Schnorr signatures
DLOG ⇒ Schnorr signatures (tight, AGM)
DLOG ⇒ Statistically hiding commitment
DLOG ⇒ Succinct arguments for NP (Bootle et al.)
DLOG ⇒ Verifiable secret sharing (VSS)
DLOG ∈ PWPP
DLOG ∈ SZK
DLOG + KEA3 ⇒ Three-message ZK arguments for NP
DLOG ⊆ BQP
DLOG ⊆ coNP
DLOG ⊆ NP
DLOG ⊆ TFNP
Doubly enhanced certified TDP ⇒ Enhanced TDP
Doubly enhanced certified TDP ⇒ Five-round 2PC (Katz–Ostrovsky)
Doubly enhanced certified TDP ⇒ NIZK
DPF ⇒ Computational Multi-server PIR
DPF ⇒ Multi-point functions
DS ⇒ OWF
E
EdDSA ⇒ DS
EDL signatures ⇒ DS
Enhanced TDP ⇒ 2PC with expected-time simulation (Ostrovsky–Richelson–Scafuro)
Enhanced TDP ⇒ MPC with honest majority ($t < n/2$) (GMW)
Enhanced TDP ⇒ UC MPC in the CRS model (CLOS)
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
Fair MPC ⇒ MPC
FE ⇒ iO
Few-round black-box concurrent ZK ⊆ BPP
Five-round 2PC ⇒ 2PC with expected-time simulation
Four-message black-box ZK proofs ⊆ coMA
Four-round MPC ⇒ MPC with expected-time simulation
Four-round OT ⇒ Four-round MPC (Choudhuri–Ciampi–Goyal–Jain–Ostrovsky)
Four-round OT ⇒ Malicious OT with expected-time simulation
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 ⇒ Semi-honest 2PC (Yao)
Generic bilinear group model ⇒ asymmetric q-SDH
GGM ⇒ CDH
GGM ⇒ DDH
GGM ⇒ DLOG
GGM ⇒ KEA
GGM ⇒ LRSW
GGM ⇒ OMDL
GGM with preprocessing ⇒ DLOG
H
Hash function + PRF ⇒ DS (XMSS)
HE ⇒ IND-CPA PKE
HIBE ⇒ IBE
High-noise LPN ⇒ Constant-noise LPN
High-noise LPN ⇒ Secret-Key PIR (SK-PIR)
Higher residuosity ⇒ PKE
Highly lossy TDF ⇒ CRHF
Highly lossy TDF ⇒ Lossy TDF
HVCZK = CZK
HVE ⇒ Subset and range queries
HVSZK = SZK
HVZK ⇒ NIZK (Fiat–Shamir)
I
IBE ⇒ garbled RAM
IBE ⇒ PKE
ID ⇒ DS
ID ⇒ OWF
Ideal OT ⇒ 2PC (Kilian)
Ideal OT ⇒ COM (Kilian)
Ideal OT + PRG ⇒ UC MPC (IPS)
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-CPA statically approximate HE ⇒ IND-CPA-D approximate HE (LMSS22)
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
Injective OWF ⇒ Four-message ZK arguments for NP (fully black-box)
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
Katz–Wang signatures ⇒ DS
KE ⇒ Multi-party key exchange
KEM ⇒ KE
L
Length-flexible additively homomorphic encryption ⇒ Additively homomorphic encryption
Length-flexible additively homomorphic encryption ⇒ PIR with polylogarithmic communication (Lipmaa)
Leveled FHE ⇒ HE
Linear secret sharing schemes (LSSS) ⇔ MSP
Linear SS ⇒ IT-PIR
Linear-only encryption ⇒ Designated-verifier SNARG
Linear-only vector encryption ⇒ Designated-verifier SNARG (lattice-based)
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)
LSN ⇒ SK-DEPIR
LWE ⇒ IBE (Gentry–Peikert–Vaikuntanathan, random oracle model)
LWE ⇒ Lossy TDF (Peikert–Waters)
LWE ⇒ NIZK
LWE ⇒ PKE
LWE ⇒ Selectively secure HIBE (bonsai trees)
LWE ⇒ Two-round UC-secure OT (PVW)
LWE + NIZK ⇒ Two-round MPC in the CRS model (Mukherjee–Wichs)
LWE at sub-exponential and polynomial ratios ⇒ Bootstrappable SHE (BV11)
LWE with polynomial ratio ⇒ BARG for NP
LWE with polynomial ratio ⇒ Circuit-private HE for NC1
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
Malicious OT ⇒ 2PC by cut-and-choose (Lindell–Pinkas)
Malicious OT ⇒ COM (Kilian)
Malicious OT ⇒ Malicious OT with expected-time simulation
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
MPC ⇒ 2PC
MPC ⇒ MPC with abort and honest majority ($t < n/2$)
MPC ⇒ MPC with expected-time simulation
MPC with honest majority ($t < n/2$) ⇒ MPC with abort and honest majority ($t < n/2$)
MPC with honest majority ($t < n/2$) ⇒ MPC with honest majority ($t < n/3$)
MPC with preprocessing ⇒ MPC
Multi-signatures in the plain public-key model ⇒ Multi-signatures in the KOSK model
Multi-signatures with proofs of possession ⇒ Multi-signatures in the KOSK model
Multilinear No-Exact-Cover ⇒ Witness encryption (GGSW)
Multiplicatively homomorphic encryption ⇒ HE
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-interactive zap ⇒ Zap
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
OLDC ⇒ Passive-server SK-DEPIR
OMDL ⇒ MuSig2
OMDL ⇒ Prime-order DLOG
OMDL ⇒ Schnorr identification under concurrent attack
OMDL + ROS ⇒ Blind Schnorr signatures
One-round sublinear cPIR ⇒ cPIR with total communication below n
One-round sublinear cPIR ⇒ CRHF
One-round sublinear cPIR ⇒ Keyword PIR
Optimally short structure-preserving signatures ⇒ Structure-preserving signatures
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 ⇒ Concurrent ZK arguments for NP in ω(log n) rounds
OWF ⇒ Constant-round WI proofs for NP (Feige–Shamir)
OWF ⇒ CZK
OWF ⇒ Distributional OWF
OWF ⇒ DS
OWF ⇒ Four-message ZK arguments for NP
OWF ⇒ garbled RAM (black-box)
OWF ⇒ One-time signatures (Lamport)
OWF ⇒ PIR with client preprocessing (Piano)
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 ⇒ ZKP (MPC in the head)
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
P ⊆ BPP
P ⊆ coNP
P ⊆ NP
P ⊆ P/poly
P ⊆ RP
P ⊆ ZPP
Passive-server SK-DEPIR ⇒ SK-DEPIR
Passive-server SK-DEPIR with a database-independent key ⇒ Passive-server SK-DEPIR
PC + Search noisy $k$-LIN ⇒ PKE
PCP = NP
PCS ⇒ Vector commitments
Perfectly correct CPA-secure PKE ⇒ CPA-secure PKE
Permuted puzzles ⇒ OLDC
PIR with polylogarithmic communication ⇒ cPIR
PIR with polylogarithmic communication ⇒ Designated-verifier delegation for P
PIR with polylogarithmic communication ⇒ Non-trivial cPIR
PK-DEPIR ⇒ SK-DEPIR
PK-DEPIR with a sublinear key ⇒ PK-DEPIR
PKE ⇒ COM
PKE ⇒ KE
PKE ⇒ KEM
PKE ⇒ OWF
Polynomial-factor GapSVP ⇒ LWE (exponential modulus)
Polynomial-factor GapSVP ⇒ LWE (polynomial modulus)
Polynomial-factor GapSVP ⇒ SIS
PP ⊆ PSPACE
PPA ⊆ PPA under randomized reductions
PPA ⊆ TFNP
PPP ⊆ TFNP
PRC ⇒ SKE
PRF ⇒ CPA-secure SKE
PRF ⇒ Garbled circuits (BHR)
PRF ⇒ iPRF
PRF ⇒ logarithmic-overhead ORAM (OptORAMa)
PRF ⇒ MAC
PRF ⇒ polylogarithmic-overhead ORAM (hierarchical ORAM)
PRF ⇒ PRP
PRF ⇒ Strong PRP
PRG ⇒ Average-case hardness of NP
PRG ⇒ COM
PRG ⇒ DPF
PRG ⇒ OWF
PRG ⇒ PRF (GGM)
PRG in NC1 ⇒ PRG in NC0 (AIK)
Prime-order CDH ⇒ CDH
Prime-order CDH ⇒ EDL signatures
Prime-order DDH ⇒ DDH
Prime-order DDH ⇒ Katz–Wang signatures
Prime-order DLOG ⇒ DLOG
PRP ⇒ iPRF (large domains)
PRP ⇒ PRF
PSPACE ⊆ EXP
PSPACE ⊆ IP
Public-coin black-box ZK under parallel repetition ⊆ BPP
PWPP ⊆ PPP
PWPP ⊆ PWPP under randomized reductions
Q
q-DLOG ⇒ Prime-order DLOG
QCMA ⊆ QMA
QIP = PSPACE
QM ⇒ OWSG
QMA ⊆ PP
QR ⇒ Additively homomorphic encryption
QR ⇒ COM
QR ⇒ cPIR (Kushilevitz–Ostrovsky)
QR ⇒ FAC
QR ⇒ Four-round MPC (Badrinarayanan–Goyal–Jain–Kalai–Khurana–Sahai)
QR ⇒ Lossy TDF (Freeman–Goldreich–Kiltz–Rosen–Segev)
QR ⇒ NIZK proofs with a common random string (Blum–De Santis–Micali–Persiano)
QR ⇒ PIR with client preprocessing (CHK22)
QR ⇒ PKE
QR ⇒ PRG (Blum–Blum–Shub)
QR ⇒ TDH
QR ⇒ Two-round UC-secure OT (PVW)
QR ∈ coNP
QR ∈ NP
QR ∈ SZK
QROM ⇒ zk-SNARK (Micali's construction in the QROM)
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 with quasi-polynomial factors ⇒ Ring LWE
Ring-LWE with quasi-polynomial factors ⇒ Unkeyed DEPIR
Ring-SIS ⇒ CRHF
ROM ⇒ Merkle puzzles
ROM ⇒ OIHF
ROM ⇒ SNARK (Micali's CS proofs)
RP ⊆ BPP
RP ⊆ NP
RSA ⇒ DS (Hohenberger–Waters, short and stateless)
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)
Schnorr identification under concurrent attack ⇒ Schnorr identification protocol
Schnorr signatures ⇒ DS
Search LWE ⇒ Decision LWE
Secure channels ⇒ MPC with abort and honest majority ($t < n/2$) (CGH+18)
Secure channels ⇒ MPC with honest majority ($t < n/2$) (Rabin–Ben-Or)
Secure channels ⇒ MPC with honest majority ($t < n/3$) (BGW)
Secure channels ⇒ MPC with honest majority ($t < n/3$) (Chaum–Crépeau–Damgård)
Secure channels ⇒ MPC with honest majority ($t < n/3$) from linear secret sharing (Cramer–Damgård–Maurer)
Secure channels ⇒ MPC with honest majority ($t < n/3$) with linear communication (Beerliová-Trubíniová–Hirt)
Secure channels ⇒ Semi-honest MPC with honest majority ($t < n/2$) (BGW)
Selective-ID IBE ⇒ CCA-secure PKE (CHK)
Selectively secure HIBE ⇒ Selectively secure IBE
Semi-homomorphic encryption ⇒ MPC with preprocessing (BDOZ)
Semi-honest 2PC ⇒ OT
Semi-honest MPC ⇒ Semi-honest 2PC
Semi-honest MPC ⇒ Semi-honest MPC with honest majority
Semi-honest MPC + OWF ⇒ MPC (GMW compiler)
Semi-honest OT ⇒ Malicious OT (Haitner)
Semi-honest OT ⇒ MPC (HIKLP)
Semi-honest OT ⇒ Semi-honest MPC (GMW)
SHE ⇒ IND-CPA PKE
SHE + correlated randomness ⇒ MPC with preprocessing (SPDZ)
SIS ⇒ CRHF
SIS ⇒ DS
SIS ∈ PWPP
SIVP ⇒ LWE
SIVP ⇒ SIS
Size-verifiable OWF ⇒ OWF
SKE ⇒ OWF
Small sorting circuits ⇒ sublogarithmic-overhead offline ORAM with fixed instructions
SNARK ⇒ Recursive SNARKs
SNARK + CRHF ⇒ Fully succinct SNARK (bootstrapping)
SNARK + OWF ⇒ NIZK argument
Sparse Learning Parity with Noise ⇒ Pseudorandom correlation generators (PCG)
Sparse Ring-LPN ⇒ PCG
SPIR ⇒ IT-PIR
sPRP ⇒ PRP
SSDDH ⇒ KE
Statically approximate HE ⇒ Approximate HE
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 ⇒ IND-CPA PKE
Strongly homomorphic encryption ⇒ Statistically rerandomizable encryption
Structure-preserving signatures ⇒ DS
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
Subgroup decision ⇒ BARG for NP
Subgroup decision ⇒ Perfect NIZK arguments for NP
Succinct LWE ⇒ ABE
Succinct LWE ⇒ LWE
Succinct state-restoration-sound IOP ⇒ STARK (BCS transform)
SUF-CMA MAC + CPA-secure SKE ⇒ CCA-secure SKE
SXDH (Symmetric External Diffie-Hellman) ⇒ NIZK
SXDH ⇒ DDH
SXDH ⇒ Structure-preserving signatures (Kiltz–Pan–Wee)
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
Three-message black-box ZK ⊆ BPP
Twisted Edwards DLOG ⇒ Prime-order DLOG
Two-message auxiliary-input ZK ⊆ BPP
Two-round MPC ⇒ MPC
Two-round OT ⇒ OT
Two-round OT ⇒ Two-round semi-honest MPC (Garg–Srinivasan, Benhamouda–Lin)
Two-round semi-honest MPC ⇒ Semi-honest MPC
Two-round semi-honest MPC ⇒ Two-round OT
Two-round UC OT ⇒ Two-round MPC in the CRS model (Garg–Srinivasan)
Two-round UC-secure OT ⇒ Two-round OT
Two-round UC-secure OT ⇒ UC-secure OT
Type 1 pairing + CDH ⇒ Multi-signatures in the KOSK model (Boldyreva)
Type 1 pairing + CDH ⇒ Multi-signatures with proofs of possession
Type 1 pairing + CDH ⇒ Waters signatures
Type 1 pairing + DLIN ⇒ Structure-preserving signatures, tightly (Hofheinz–Jager)
Type 1 pairing + LRSW ⇒ DS (Camenisch–Lysyanskaya)
Type 3 pairing ⇒ DS (Pointcheval–Sanders)
Type 3 pairing ⇒ Optimally short structure-preserving signatures (AGHO)
U
UC MPC ⇒ MPC
UC-secure OT ⇒ Malicious OT
UC-secure OT ⇒ OT
Universal SNARK ⇒ SNARK
Unkeyed DEPIR ⇒ cPIR
Unkeyed DEPIR ⇒ PK-DEPIR
UOWHF + One-time signature ⇒ DS (Naor–Yung)
W
Waters signatures ⇒ DS
WE + PRG ⇒ PKE (GGSW)
Weak alternating moduli ⇒ weak PRF
Weak OWF ⇒ Distributional OWF
Weak OWF ⇒ OWF (Yao)
Z
Zap + HSG ⇒ Non-interactive zaps (BOV)
Zero-bit PRC ⇒ Trapdoor pseudorandom generators
Zero-bit PRC ⇒ Watermarking
ZPP ⊆ RP