PaperlayerView exact revision on arXiv

Source-linked AI summary

A Broadcast Authenticated Encryption with Keyword Search in the Standard Model: Tightly Secure in Multi-User, Multi-Challenge Settings

Sayantan Mukherjee

arXiv:2608.29191v1cs.CR

TL;DR

Existing BAEKS work did not address realistic multi-user, multi-challenge security with adaptive corruptions or tight reductions. This paper defines stronger security notions and presents a statistically consistent construction achieving adaptive tight full-cpa security under standard matrix Diffie-Hellman assumptions.

  • Problem

    Prior BAEKS constructions did not consider realistic multi-user, interleaved multi-challenge security, and their reductions incurred query- and user-dependent losses.

  • Method

    The paper defines full-cpa and unforgeability notions, then constructs a statistically consistent BAEKS scheme in bilinear pairing groups and evaluates its implementation.

  • Results

    The construction achieves adaptive tight full-cpa security under standard matrix Diffie-Hellman assumptions and yields an efficient, tightly secure PAEKS scheme for one receiver.

  • Takeaways & Limitations

    The scheme provides tight security for BAEKS while hiding keyword, sender, and receiver information against adaptive corruptions.

  • Takeaways & Limitations

    The paper notes that prior consistency analyses contain reduction arguments that are not formally proven.

Abstract

from arXiv · show

However, no known work considered the functionality requirement in its most realistic setting. We propose a new security definition of BAEKS in the multi-user (with adaptive corruptions) and multi-challenge (both in terms of ciphertext and trapdoor in an interleaved manner) settings. We also study the question of the unforgeability of BAEKS. In fact, our strong hiding requirement already implies a significant amount of unforgeability. We then propose a new BAEKS construction in the bilinear pairing groups. We prove this scheme achieves adaptive tight full-hiding security under (almost) standard MDDH assumptions. Restricting our BAEKS construction for a single receiver also gives an efficient and tightly secure PAEKS construction. We further run experiments to implement and evaluate our scheme.

1 Introduction

The introduction presents BAEKS as a multi-receiver extension of searchable authenticated encryption and identifies gaps in realistic multi-user, multi-challenge security. It then introduces full-cpa security with adaptive corruptions and argues that it implies ciphertext and trapdoor unforgeability.

  • Background: PEKS enables public testing of whether a ciphertext keyword matches a trapdoor keyword, but remains vulnerable to keyword-guessing attacks.Searchable encryption encodes attributes in ciphertexts and trapdoors, with a public Test algorithm checking matches.
  • Background: BAEKS extends PAEKS to let a sender encrypt a keyword for a set of authorized receivers.PAEKS is the singleton-authorized-set special case of BAEKS.
  • Motivation: Existing multi-user, multi-challenge reductions face ineffective |U|·ϵ bounds for exponentially large user universes and multiplicative loss J proportional to adversarial queries.The introduction identifies both large-universe dependence and query-dependent security loss as central obstacles.
  • Related work: Prior BAEKS constructions derived from PAEKS have ciphertext size O(|R|)× the size of a PAEKS ciphertext.Here R denotes the authorized receiver set, reflecting linear ciphertext dependence on its size.
  • Contributions: The proposed full-cpa definition allows interleaved ciphertext and trapdoor challenges under adaptive corruptions while hiding keywords and honest-user identities.The definition is presented as an improvement over existing PAEKS and BAEKS security notions.
  • Contributions: Full-cpa security is shown to imply both ct-cma and trap-cma unforgeability notions for ciphertexts and trapdoors.These notions capture the requirement that only authentic users can create the corresponding objects.

2 Mathematical Tools and Preliminaries

This section establishes the notation, type-3 bilinear-pairing framework, matrix distributions, and matrix Diffie–Hellman assumptions used throughout the paper. It also records relationships among the standard, lateral, and bilateral variants and their hardness properties.

  • Notation: The paper fixes notation for intervals, uniform sampling, probabilistic polynomial time, vectors, don’t-care symbols, substrings, and disjoint unions.
  • Bilinear Pairing Groups: It uses type-3 bilinear pairings e: G1 × G2 → GT over cyclic prime-order groups, with no known isomorphism between G1 and G2.The generator ABSGen outputs the pairing description and group generators.
  • Matrix Distributions: A matrix distribution Dℓ,k outputs full-rank ℓ × k matrices over Zp, while Uℓ,k is uniform over all such matrices; both require ℓ > k.The notation Dk = Dk+1,k and Uk = Uk+1,k is used for the specialized case.
  • MDDH Relationships: The preliminaries state that the bilateral MDDH assumption is standard and that bilateral and lateral MDDH are hard for k > 1.They also record Uk-MDDH equivalence with Uℓ,k-MDDH and the ordering bil-Uk-MDDH ≤ lat-Uk-MDDH ≤ Uk-MDDH.

3 Broadcast Authenticated Encryption with Keyword Search · 3.1 Definition · Correctness.

The paper defines BAEKS through five probabilistic polynomial-time algorithms for broadcast keyword search. Its correctness requires matching sender, keyword, and receiver attributes to yield a successful test except with negligible probability, and it separately formalizes consistency.

  • 3 Broadcast Authenticated Encryption with Keyword Search: BAEKS is defined as the five-algorithm tuple (Setup, KeyGen, SrchEnc, TrapGen, Test).These algorithms establish system parameters, generate keys, create broadcast ciphertexts and trapdoors, and test whether they match.
  • 3.1 Definition: Setup defines the user space U = {0, 1}^u and keyword space KW = {0, 1}^α, while publishing parameters pp.Here, u = poly(λ) and α = poly(λ), and pp implicitly defines ciphertext and trapdoor spaces.
  • 3.1 Definition: KeyGen takes pp and outputs a public-private key pair (pk, sk), keeping sk secret and publishing pk.The generated keys support sender encryption and receiver-specific search operations.
  • 3.1 Definition: SrchEnc encrypts keyword ω for receiver public keys pkR, while TrapGen creates a trapdoor from sender public key pkE, keyword w, and receiver secret key skF.The resulting ciphertext Ct belongs to CT, and the trapdoor Tr belongs to T.
  • 3.1 Definition: Test takes Tr and Ct and outputs 0/1 to determine whether the trapdoor matches the ciphertext.A match informally requires E = S, w = ω, and F ∈ R.
  • Correctness.: Correctness requires Test(TrapGen(pkS, ω, skF), SrchEnc(skS, ω, pkR)) = 1 with probability 1 − neg(λ) when F ∈ R.The probability is over setup and key generation for the sender and receivers.
  • Correctness.: Consistency is defined through a dedicated experiment for the five-algorithm BAEKS scheme, following the definition borrowed from.The experiment is presented in Figure 2.

3.2 Security

This section defines full-hiding security for BAEKS through a restricted indistinguishability game with ciphertext, trapdoor, public-key, and secret-key oracles. It also establishes that full-cpa security implies ciphertext and trapdoor integrity.

  • Full-hiding security: Full hiding requires every PPT adversary’s advantage to be bounded by a negligible function under the full-cpa experiment.The experiment restricts matching challenge queries and secret-key access for challenge senders and receivers.
  • Security experiment: Public-key and secret-key oracles return consistent keys for newly queried users, with secret-key queries retrieving previously stored key pairs.The adversary must query the public-key oracle before making a ciphertext or trapdoor query involving that user.
  • Integrity: The work studies ciphertext and trapdoor integrity and shows that full-cpa security already implies both forms of integrity.The detailed integrity discussion is deferred to Section B.1.

3.3 Differences in Security Defintions

Earlier BAEKS and PAEKS definitions address progressively different confidentiality, anonymity, corruption, and challenge settings. This work introduces full-cpa security, combining interleaved ciphertext, trapdoor, and secret-key challenges with simultaneous keyword hiding and sender and receiver anonymity.

  • Earlier definitions: Cheng and Meng defined Fully CI and Fully TI Security with interleaved ciphertext and trapdoor queries, restricting challenges against previously queried trapdoors or ciphertexts, respectively.Fully CI excludes challenge keywords from QTr, whereas Fully TI excludes them from QCt for the target receiver.
  • Earlier definitions: Their MCI/MTI-security extensions support multiple users and non-adaptive keyword sequences but address only ciphertext or trapdoor confidentiality.The cited work did not provide proofs that CI-security implies MCI-security or that TI-security implies MTI-security.
  • Earlier definitions: IND-CKA and IND-IKGA use multiple senders, a fixed target receiver, adaptive keyword and sender selection, and ciphertext or trapdoor challenges, respectively.IND-IKGA is described as identical to IND-CKA except that the challenge is a trapdoor.
  • Full-cpa security: Full-cpa security allows interleaved ciphertext, trapdoor, and secret-key challenge queries, simultaneously capturing multi-ciphertext, multi-trapdoor, keyword-hiding, sender-anonymity, and receiver-anonymity security.Because SrchEnc and TrapGen use secret keys, the model combines multi-ciphertext and multi-trapdoor security while hiding identities in ciphertexts and trapdoors.

3.4 Analysis of Consistency of Emura’s PAEKS · 3.5 System Model

The paper identifies limitations and proof gaps in Emura’s computational-consistency definition and argument for PAEKS, then specifies a system model with sender, receiver, keyword, trapdoor, and ciphertext matching requirements.

  • 3.4 Analysis of Consistency of Emura’s PAEKS: Emura’s definition omits adversarial sender and receiver selection and restricts SrchEnc and TrapGen to the same receiver.It captures adversaries producing mismatched keywords whose corresponding ciphertext and trapdoor still match.
  • 3.4 Analysis of Consistency of Emura’s PAEKS: The generic PAEKS construction reduces computational consistency to the underlying PEKS through a hybrid argument.The argument begins with the real security game G0 and replaces the projective hash function in SrchEnc in G1.
  • 3.4 Analysis of Consistency of Emura’s PAEKS: The reductions are not formally proven, including the claimed negligible difference between G0 and G1 based on WI-SPHF correctness.The critique notes that the claim is not established by explicitly forming reductions.
  • 3.4 Analysis of Consistency of Emura’s PAEKS: Most reductions in Emura’s consistency proof are inadequately argued under standard provable-security methodology.The passage observes that only the G1 ≈ G2 step receives an exception in the critique.
  • 3.4 Analysis of Consistency of Emura’s PAEKS: The expanded version provides more security-proof detail but, according to the authors, adds no consistency-proof detail beyond Emura’s original work.Therefore, the earlier concerns about the consistency argument remain.
  • 3.5 System Model: The system uses user space U = {0, 1}^u and keyword space KW = {0, 1}^α, with u = poly(λ) and α = poly(λ).Setup generates public parameters, users generate key pairs, and receivers create trapdoors using their secret keys and the sender’s public key.

4 Tight Broadcast Authenticated Encryption with Keyword Search

The section presents a BAEKS construction with trusted setup and user-generated key pairs, proves correctness and statistical consistency, and establishes adaptive full-CPA security under a lat-Uk-MDDH assumption via a tight hybrid argument.

  • Construction: The construction uses trusted one-time Setup, while each user independently runs KeyGen(j) to generate a key pair.The scheme is given in Figure 5 and is followed by correctness and statistical-consistency proofs.
  • Correctness and consistency: Distinct senders, keywords, or receiver sets yield matching trapdoors and ciphertexts only with negligible probability, even for statistical adversaries given public keys.The consistency argument covers adversarially chosen keywords and public keys for both senders and receivers.
  • Correctness and consistency: The consistency proof concludes that the relevant randomness variables are independent and uniformly random, preventing ciphertext–trapdoor matches except with negligible probability.The argument treats differing senders, differing keywords, and receiver sets absent from the ciphertext separately.
  • Security: Under the lat-Uk-MDDH assumption in G, baeks is a full-CPA-secure BAEKS scheme against adversaries making bounded challenge trapdoor, encryption, and key requests.The theorem explicitly accounts for q challenge trapdoor queries, Q challenge encryption requests, and ˜Q key requests.
  • Security proof: The security proof uses hybrids G0 through G6, transitioning from the real experiment to one where challenge ciphertext components and k1 are random quantities.The sequence includes syntactic changes, MDDH-based replacements, and removal of auxiliary terms from encryption and trapdoor responses.
  • Security proof: The resulting full-CPA security bound is tight, with the hybrid proof reducing transitions to MDDH assumptions and a core lemma.The proof is organized through lemmas for each game transition and refers to the Core Lemma in Section 5.

5 Core Lemma

The section presents a core experiment for the BAEKS construction and proves that polynomially many interleaved oracle queries reveal only negligible information about its hidden bit. The proof relies on residual entropy after projection and a sequence of hybrid experiments under MDDH assumptions.

  • Core Lemma: Even after publishing [X_jB]_2, the quantity X_j retains sufficient entropy to randomize OTag and OChal responses.This entropy observation is used to prove the Core Lemma and then Lemma 5.
  • Core Lemma: The Core Lemma establishes negligible distinguishing advantage for every PPT adversary in the defined oracle experiment.The experiment gives access to OKgen, OCor, OTag, and OChal for polynomially many queries.
  • Assumptions: The security claim holds under U3k,k-MDDH assumptions for both G1 and G2.The stated experiment allows polynomially many queries, including the query sets QK, QT, and QC.
  • Proof by hybrids: The lemma is proved through a hybrid sequence transforming ExpCore through H1–H6 and replacing structured responses with randomized ones.The hybrids inject randomness into RF, ZF, and OF functions, sample t0 values conditionally, and ultimately sample t1 uniformly.

6 Experimental Results

The experiments implement BAEKS in Python using Charm on an MNT224 pairing curve and evaluate its operation costs across system algorithms under varied security, user, and receiver-set parameters. The implementation demonstrates practicality, while the single-receiver PAEKS is reported as comparably efficient to existing works and tightly secure.

  • Implementation: BAEKS is implemented in Python 3.6.9 with Charm 0.50 on an MNT224 Type-III pairing curve, using a VirtualBox Ubuntu 18.04 VM with one processor and 4GB RAM.The implementation uses the same curve as existing works and runs under the stated virtualized hardware configuration.
  • Operation Counts: Figure 13 counts operations in G1, G2, and GT for Setup, KeyGen, SrchEnc, TrapGen, and Test.Setup and KeyGen run once, whereas SrchEnc, TrapGen, and Test are repeatedly executed by users or the cloud server.
  • Experimental Parameters: The experiments use security level k = 2, up to 100 users, and different receiver-set sizes, with each user independently running KeyGen.Security level k = 1 is excluded because lat-Uk-MDDH is easy there; the keyword and universe sizes are parameterized as |KW| = 2^α and |U| = 2^u.
  • Performance: The single-receiver PAEKS is reported as extremely comparably efficient with existing works while providing tight security.PAEKS computation can be represented by setting the receiver-set bound ℓ = 1.
  • Performance: The proof-of-concept BAEKS implementation running on VirtualBox demonstrates the protocol’s practicality, with multi-core tournament-wise parallel multiplication suggested for further efficiency gains.The claimed improvement concerns parallel multiplication of group elements across multiple cores.

7 Conclusion

The paper revises BAEKS security models to address sender, receiver, and keyword privacy, introduces consistency, and presents a statistically consistent standard-model construction. The construction achieves adaptive full-cpa security for ciphertext and trapdoor security under lateral Matrix Diffie-Hellman assumptions, while remaining somewhat less efficient than.

  • The paper revamps BAEKS security models to capture sender, receiver, and keyword privacy, and proposes a consistency definition.
  • The proposed statistically consistent BAEKS construction achieves adaptive full-cpa security for both ciphertext and trapdoor security under the standard lateral Matrix Diffie-Hellman assumption.The construction is proven secure in the standard model.
  • The scheme is slightly less efficient than in ciphertext and key size, but provides tight full-cpa security and tolerates adversarial corruption of a few users.
  • Future work includes constructing schemes with more robust security against malicious adversaries that generate their own key pairs.

A Comments on Security Proof of Ling et al.’s PEKS

The section reviews Ling et al.’s two multi-user PEKS constructions and their three-step security proofs. It identifies that the entropy argument fails, tight multi-challenge security is unsupported, and consistency was not addressed.

  • Prior constructions and proofs: Ling et al. proposed two multi-user PEKS constructions and claimed security in the multi-user, multi-ciphertext setting.Their proofs classify ciphertexts into type-0, type-1, and type-2 and proceed through three transformation steps.
  • Our Observations: The final proof step incorrectly claims that type-2 ciphertext entropy information-theoretically hides all keyword-dependent hashes.The analysis states that this sufficient-entropy claim does not hold.
  • Our Observations: The constructions use Boneh–Boyen hashes, but neither affine nor exponent-inversion hashing is known to be tightly secure for multi-challenge security.Construction-I uses the affine hash, whereas Construction-II uses an exponent-inversion-based hash.
  • Our Observations: Ling et al. did not argue consistency, a definitive characteristic of PEKS.

B Differences in Security Notions · B.1 Unforgeability of Ciphertexts and Trapdoors.

The section defines ciphertext and trapdoor unforgeability for BAEKS through oracle-based games, then argues that full-cpa security implies both forms of unforgeability. The ciphertext implication uses a reduction that distinguishes challenge-side trapdoors by testing a purported forgery, while the trapdoor case follows similarly.

  • B.1 Unforgeability of Ciphertexts and Trapdoors: BAEKS ciphertext unforgeability requires every ppt adversary’s ct-cma advantage to be negligible in the security parameter.The definition is given through the unforgeability game in Figure 15.
  • B.1 Unforgeability of Ciphertexts and Trapdoors: The ct-cma game provides encryption, trapdoor-generation, secret-key, and public-key oracles while recording relevant query lists.Encryption queries record (pkS, ω, pkR) tuples in QCt; key-generation queries also update Qsk.
  • B.1 Unforgeability of Ciphertexts and Trapdoors: BAEKS trapdoor unforgeability requires every ppt adversary’s trap-cma advantage to be negligible in the security parameter.Its game uses the same oracle framework as the ciphertext-unforgeability definition.
  • B.1 Unforgeability of Ciphertexts and Trapdoors: The trap-cma game likewise grants encryption, trapdoor-generation, secret-key, and public-key oracles, with queried tuples and keys recorded.The oracle descriptions mirror those used for ct-cma.
  • B.1 Unforgeability of Ciphertexts and Trapdoors: Full-cpa security implies ct-cma security via a reduction that converts a ciphertext forgery into a distinguishing challenge.The reduction forwards setup and oracle queries, placing encryption and trapdoor queries on both challenge sides.
  • B.1 Unforgeability of Ciphertexts and Trapdoors: A valid ciphertext forgery must satisfy the test relation for some receiver while using an unqueried (pkS*, ω*, pkR*) tuple and no secret-key query for S*.These restrictions define when the reduction may exploit the forgery.
  • B.1 Unforgeability of Ciphertexts and Trapdoors: The reduction queries a challenge trapdoor for an alternate sender and outputs left when testing succeeds, otherwise right.Correctness yields a successful test for the original sender’s trapdoor, while consistency makes the test fail for the alternate sender except with negligible probability.
  • B.1 Unforgeability of Ciphertexts and Trapdoors: Full-cpa security also implies trap-cma security through a reduction very similar to the ciphertext-unforgeability argument.The paper states this implication without detailing a separate reduction.
Loading 2608.29191v1…