Scientific knowledge map · Paper #65
On the Hardness of Scheme-Switching Between SIMD FHE Schemes
2023 · 14th International Conference on Post-Quantum Cryptography (PQCrypto)
- Theory
Research question
What does the paper try to establish?
Can exact SIMD ciphertexts from BGV or BFV be efficiently converted to approximate CKKS ciphertexts, and back, without making expensive FHE capabilities such as bootstrapping unexpectedly cheap?
Central answer
What is the proposed answer?
The paper gives conditional reductions rather than an unconditional lower bound: sufficiently capable scheme-switching oracles imply bootstrapping for the target schemes with little additional homomorphic work. It also relates comparison access to bootstrapping and nonlinear functions, supplying barrier evidence for general-purpose switching across exact and approximate encodings.
Evidence profile
Six dimensions, kept separate
The chart summarizes documented evidence and process. It is not a correctness probability, confidence score, or ranking, and no composite score is calculated.
LowMediumHighN/A = not assessed
A smaller value means less documented support for that dimension, not that the paper is false or unimportant.
- Epistemic evidence High
-
The full source supplies formal oracle interfaces, lemmas, reductions, and parameter conditions. High describes the documented support for conditional theorems, not an unconditional hardness proof.
Weak and strong scheme-switch definitions BGV-to-CKKS switching implies CKKS bootstrapping CKKS-to-BGV switching implies BGV bootstrapping - Auditability High
-
The full IACR manuscript and author record make assumptions, theorem statements, and proofs publicly inspectable, while the official DOI fixes the publication identity.
Problem statement, contributions, and interpretation Official publication identity - Production provenance Medium
-
Named authors, public manuscript, venue, year, and DOI are documented; author roles, revision history, tools, and proof-development process are not.
Problem statement, contributions, and interpretation Official publication identity - External scrutiny Medium
-
PQCrypto publication establishes venue scrutiny, but no public reports, independent proof audit, formal verification, or correction history was located.
Official publication identity - Reception Low
-
The dated OpenAlex snapshot located 1 citation. Under the author-defined rule, 0 through 8 located citations is Low; counts do not measure validity.
Dated citation-count snapshot - Contribution significance High
-
The reductions expose a general barrier between scheme switching and bootstrapping across major SIMD FHE families. This is a significance assessment of the theorem's scope, not a claim of unconditional impossibility.
Problem statement, contributions, and interpretation BGV-to-CKKS switching implies CKKS bootstrapping CKKS-to-BGV switching implies BGV bootstrapping
Assessment: Ai draft author review pending · 2026-07-11 · rubric 0.2. These dimensions describe documented support and process, not truth, correctness, or a universal ranking. No composite score is calculated.
Top-down and bottom-up view
Hierarchical knowledge map
Collapse a branch for a top-level reading, or follow its source links and child nodes to audit the evidence and boundaries underneath it.
Hardness of SIMD FHE scheme switching
A theory paper that studies exact-to-approximate and approximate-to-exact SIMD FHE conversion through oracle reductions, showing that broadly useful switching would subsume costly refresh capabilities.
Problem statement, contributions, and interpretation-
question Research question
research questionIs generic, efficient switching between BGV/BFV exact SIMD encodings and CKKS approximate SIMD encodings substantially easier than bootstrapping?
Problem statement, contributions, and interpretation -
contribution Conditional barrier answer
proved conditionallyUnder the formal oracle interfaces, switching in either direction yields bootstrapping for the destination scheme with small additional work. Thus an efficient switching primitive of the modeled strength would also solve a capability usually regarded as expensive.
BGV-to-CKKS switching implies CKKS bootstrapping CKKS-to-BGV switching implies BGV bootstrapping -
model Exact and approximate SIMD model defined
BGV and BFV represent exact modular plaintext slots, whereas CKKS represents approximate complex or real slots with scale and error; switching must address both ciphertext semantics and plaintext encoding.
BGV, BFV, CKKS, SIMD encodings, and oracle notation-
definition Weak versus strong switching
formalizedA weak oracle preserves a compatible underlying ring-polynomial representation without performing the full slot-encoding conversion. A strong oracle includes the encoding transformation expected by an application-facing scheme switch.
Weak and strong scheme-switch definitions -
theorem Weak-to-strong lifting
provedThe Section 3 lemmas and theorems connect the weak oracle formulations to strong switching by accounting for the relevant BGV and CKKS encoding transformations.
Weak and strong scheme-switch definitions
-
-
claim group Reduction results proved
The central results are black-box consequences of possessing the specified switching oracle; they are not constructions of a cheap switching implementation.
BGV-to-CKKS switching implies CKKS bootstrapping CKKS-to-BGV switching implies BGV bootstrapping-
theorem Exact-to-approximate switch bootstraps CKKS
provedTheorem 5 shows that a weak BGV-to-CKKS switching oracle can be used to bootstrap CKKS with one oracle call and one rescaling step, subject to the theorem's parameter and noise conditions.
BGV-to-CKKS switching implies CKKS bootstrapping -
theorem Approximate-to-exact switch bootstraps BGV
provedThe reverse reduction uses one CKKS-to-BGV oracle call followed by a homomorphic inner-product style computation, plaintext multiplication and addition, and modulus switching to obtain a refreshed BGV ciphertext; the treatment extends to BFV through the stated conversion.
CKKS-to-BGV switching implies BGV bootstrapping -
theorem Comparison access also carries refresh power
proved conditionallyThe comparison analysis shows how a suitable comparison oracle can support bootstrapping with few calls for typical parameter regimes and connects the mechanism to nonlinear operations such as minimum, maximum, and ReLU.
Comparison-oracle consequences
-
-
evidence group Formal evidence
formalThe paper's evidence consists of definitions, encoding lemmas, constructive oracle reductions, and explicit noise or parameter accounting rather than implementation benchmarks.
Weak and strong scheme-switch definitions BGV-to-CKKS switching implies CKKS bootstrapping CKKS-to-BGV switching implies BGV bootstrapping -
limitation group What the reductions do not establish explicitly bounded
The reductions delimit the consequences of modeled switching capabilities but do not prove an unconditional complexity lower bound or impossibility theorem.
Problem statement, contributions, and interpretation Interpretation and open scope-
limitation Conditional, not unconditional, hardness
logical boundaryShowing that A implies B does not prove that A is impossible or as hard as B under every implementation model; the result becomes a hardness barrier only together with an external belief or lower bound about bootstrapping cost.
BGV-to-CKKS switching implies CKKS bootstrapping CKKS-to-BGV switching implies BGV bootstrapping -
limitation Oracle-interface dependence
model boundedA specialized converter outside the weak or strong oracle semantics, a restricted plaintext domain, amortization, or changed correctness and precision requirements may fall outside a theorem's conclusion.
Weak and strong scheme-switch definitions Interpretation and open scope -
limitation No implementation comparison
not evaluatedThe work does not implement a switch, benchmark bootstrapping, or measure engineering tradeoffs; it establishes relative capability, not concrete runtime cost.
Problem statement, contributions, and interpretation Interpretation and open scope
-
-
artifact group Auditable resources
source availableThe full IACR manuscript, official DOI, and IBM author record expose the definitions and proof arguments; no code or experimental artifact is claimed.
Problem statement, contributions, and interpretation Official publication identity -
scrutiny External scrutiny
venue reviewedPQCrypto publication establishes venue review. No public proof review, correction, independent formalization, or subsequent technical critique was located in this audit.
Official publication identity -
lineage Place in the FHE design space
documentedThe paper reframes scheme switching as a relative-capability question linking exact and approximate SIMD schemes to bootstrapping and comparison, rather than proposing another FHE scheme.
Problem statement, contributions, and interpretation Interpretation and open scope
Audit trail
Source index
Locators state the depth of the current audit. PDF page numbers, where present, are one-based file pages; metadata-, summary-, and abstract-bounded records explicitly identify their limitations.
- Problem statement, contributions, and interpretation Abstract and Section 1
- BGV, BFV, CKKS, SIMD encodings, and oracle notation Section 2
- Weak and strong scheme-switch definitions Section 3, including Lemmas 3.1-3.2 and Theorems 3-4
- BGV-to-CKKS switching implies CKKS bootstrapping Section 4, Theorem 5
- CKKS-to-BGV switching implies BGV bootstrapping Section 4, Theorem 6 and BFV extension
- Comparison-oracle consequences Section 5
- Interpretation and open scope Conclusion
- Official publication identity PQCrypto 2023, DOI 10.1007/978-3-031-40003-2_8
- Dated citation-count snapshot OpenAlex cited_by_count was 1 when accessed 2026-07-11