Scientific knowledge map · Paper #56
Optimizing Registration Based Encryption
2021 · 18th IMA International Conference on Cryptography and Coding (IMACC)
- Theory
- Applied
- scheme
Research question
What does the paper try to establish?
Can registration-based encryption preserve its no-key-escrow and asymptotic efficiency goals while reducing the enormous concrete ciphertext and decryption costs of existing constructions?
Central answer
What is the proposed answer?
Replacing Merkle trees with authenticated crit-bit trees shortens garbled inputs, and publishing a small square-root-sized identity filter lets encryptors skip roughly half the tree snapshots. The paper analytically estimates a 57.5 percent combined ciphertext reduction, proves standard RBE security for the crit-bit construction, and states important remaining security and practicality gaps.
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 Medium
-
The construction and standard-security proof are detailed, but the paper's central concrete-efficiency claims are analytical estimates without an implementation, and verifiability is only sketched.
Single-user and general RBE security proofs Analytical cost reduction Verifiability argument and proof boundary CCA, implementation, and compactness boundaries - Auditability High
-
Full archive and author-uploaded copies plus the DOI expose the definitions, proofs, and arithmetic. Anti-bot controls prevented recording a local byte hash in this pass.
Author-uploaded full text Official IMACC publication identity - Production provenance Medium
-
Authorship, venue, DOI, archive, and author upload are documented; revision history, roles, and tool use are not.
Official IMACC publication identity RBE motivation, baseline cost, and contributions - External scrutiny Medium
-
IMACC publication establishes venue review, but no public review report, artifact evaluation, or independent proof audit is represented.
Official IMACC publication identity - Reception Low
-
The dated exact-DOI OpenAlex record located 0 citations. Under the author-defined rule, 0 through 8 located citations is Low; counts vary across indexes and dates.
Dated citation-count snapshot - Contribution significance Medium
-
The work materially reduces an identified concrete bottleneck in the prior blueprint, but the resulting construction remains impractical and downstream impact is not established here.
RBE motivation, baseline cost, and contributions CCA, implementation, and compactness boundaries
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.
Optimizing Registration Based Encryption
An optimized RBE scheme using authenticated crit-bit trees and a public-parameter tradeoff to reduce the concrete cost of garbled public-key operations.
RBE motivation, baseline cost, and contributions-
question Research question
research questionCan RBE's attractive asymptotics be retained while shrinking ciphertext and decryption costs enough to move toward practice?
RBE motivation, baseline cost, and contributions -
contribution Central answer
construction and estimateCompress authenticated tree paths with crit-bit nodes, then optionally disclose a square-root-sized set of identities so encryption traverses fewer snapshots; both changes reduce the number of costly public-key operations inside garbled circuits.
Authenticated crit-bit tree Analytical cost reduction Larger-public-parameter optimization -
scope RBE model defined
Users generate their own keys; a key curator holds no secret and maintains registrations, auxiliary state, and short public parameters; an encryptor uses recipient identity plus public parameters, and a decryptor combines its secret key with periodically updated supporting information.
RBE roles, algorithms, efficiency, and message-hiding definition-
threat model Message-hiding, not chosen-ciphertext security
explicitly scopedThe proof targets the standard RBE message-hiding definition used by prior work and does not provide a decryption oracle; active chosen-ciphertext security remains open.
RBE roles, algorithms, efficiency, and message-hiding definition CCA, implementation, and compactness boundaries
-
-
scheme Crit-bit-tree RBE specified
Authenticated crit-bit trees replace balanced Merkle trees in snapshot-based registration. Each internal node stores a critical bit and two hash pointers, shortening the garbled input while preserving searchable authenticated paths.
Authenticated crit-bit tree Compact-parameter optimized RBE construction-
claim Standard RBE security
proved under assumptionsA single-user argument combines hash-garbling simulation with semantic PKE security; the general theorem replaces path programs through hybrids and concludes message-hiding for the crit-bit construction.
Hash garbling, hash encryption, and cryptographic assumptions Single-user and general RBE security proofs -
claim Compact-parameter reduction
analytical estimateFor the paper's two-billion-user, 256-bit example, shorter tree nodes are estimated to reduce encryptor public-key operations and ciphertext size by about 15 percent and decryptor work by about 30 percent on average.
Analytical cost reduction
-
-
method Larger public parameter specified tradeoff
Publishing membership information for a square-root-sized minority of snapshot users lets encryption ignore roughly half the trees. A cuckoo filter is proposed to represent that set compactly.
Larger-public-parameter optimization-
claim 57.5 percent combined ciphertext reduction
analytical estimateCombining the 15 percent crit-bit reduction with a further one-half encryptor reduction yields the stated 57.5 percent decrease; the larger-parameter example adds about 187 KB for two billion users.
RBE motivation, baseline cost, and contributions Larger-public-parameter optimization
-
-
evidence group Evidence boundary
formal and analyticalSecurity is supported by definitions and hybrid proofs, while performance is supported by operation counts and asymptotic tree-depth facts. The paper does not implement or benchmark an RBE system.
Single-user and general RBE security proofs Analytical cost reduction -
claim Verifiable registration compatibility
argued not fully provedAdjacent authenticated paths support non-membership and unique-membership proof sketches, but the paper explicitly does not provide the full verification algorithm or prove its soundness and completeness.
Verifiability argument and proof boundary -
limitation group Limitations
materialThe optimized ciphertext remains extremely large in the motivating regime, performance is estimated rather than measured, chosen-ciphertext security is absent, the verifiability extension is incomplete, and the second optimization weakens public-parameter compactness from polylogarithmic in users to square-root dependence.
RBE motivation, baseline cost, and contributions CCA, implementation, and compactness boundaries -
artifact group Publication resources
full text availableThe IACR archive, author-uploaded full text, and official DOI make the construction and proofs inspectable. No implementation or benchmark artifact is represented.
RBE motivation, baseline cost, and contributions Official IMACC publication identity -
scrutiny External scrutiny
venue reviewedThe paper appeared at IMACC 2021. Review reports and independent implementation or proof audits are not linked.
Official IMACC publication identity -
lineage Optimization of prior RBE blueprints
documentedThe work retains the hash-garbling and snapshot approach of earlier RBE and verifiable-RBE constructions while changing authenticated data structures and the public-parameter tradeoff.
RBE motivation, baseline cost, and contributions Compact-parameter optimized RBE construction
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.
- RBE motivation, baseline cost, and contributions Abstract and Sections 1.1-1.2, PDF pages 1-3
- RBE roles, algorithms, efficiency, and message-hiding definition Sections 2 and 3.5, PDF pages 4-12
- Hash garbling, hash encryption, and cryptographic assumptions Sections 3.3-3.4 and Appendix A, PDF pages 9-10 and 25-28
- Authenticated crit-bit tree Sections 3.6 and 4.1, PDF pages 12-14
- Compact-parameter optimized RBE construction Sections 4.2-4.3, PDF pages 14-17
- Single-user and general RBE security proofs Section 4.4, Theorems 1-2, PDF pages 17-19
- Analytical cost reduction Section 4.5, PDF page 19
- Verifiability argument and proof boundary Section 4.6, PDF pages 19-20
- Larger-public-parameter optimization Section 5, PDF pages 20-23
- CCA, implementation, and compactness boundaries Sections 1.2, 4.5-4.6, and 5, PDF pages 3 and 19-23
- Official IMACC publication identity DOI 10.1007/978-3-030-92641-0_7
- Dated citation-count snapshot OpenAlex reported 0 citations when accessed 2026-07-11