pith. sign in

arxiv: 1907.07282 · v1 · pith:OY6FMEIXnew · submitted 2019-07-16 · 💻 cs.CR

A New Distribution Version of Boneh-Goh-Nissim Cryptosystem: Security and performance analysis

Oualid Benamara , Fatiha Merazka This is my paper

Pith reviewed 2026-05-24 20:36 UTC · model grok-4.3

classification 💻 cs.CR
keywords distributed cryptosystemBoneh-Goh-Nissimsemantic securitysubgroup decision problemElGamal elliptic curveperformance analysismulti-party decryption
0
0 comments X

The pith

Two distributed versions of the Boneh-Goh-Nissim cryptosystem are constructed, one semantically secure against active non-adaptive adversaries and the other more efficient than EDECC while secure under the subgroup decision problem.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs two ways to split the Boneh-Goh-Nissim cryptosystem so that decryption requires multiple parties. It supplies a proof that the first version stays semantically secure when the adversary is active but cannot adapt its strategy during the attack. It further shows that the second version runs faster than the distributed ElGamal elliptic-curve scheme and reduces its security to the subgroup decision problem. Readers care because distributing the secret key can prevent any single party from decrypting alone, which is useful in settings that need shared control over encrypted data.

Core claim

The authors present two distributed versions of the Boneh-Goh-Nissim cryptosystem. The first is proven semantically secure against active non-adaptive adversaries. The second is shown to be computationally more efficient than the ElGamal distributed elliptic curve cryptosystem and secure under the subgroup decision problem assumption.

What carries the argument

Distributed versions of the Boneh-Goh-Nissim cryptosystem, with security arguments based on semantic security for the first and the subgroup decision problem for the second.

If this is right

  • The first distributed scheme preserves semantic security against active non-adaptive adversaries.
  • The second scheme requires fewer operations than the ElGamal distributed elliptic curve cryptosystem.
  • Security of the second scheme rests on the subgroup decision problem holding in the underlying groups.
  • Both versions allow decryption to be shared among multiple parties without exposing the full secret key.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the efficiency result holds in practice, the second version could support multi-party settings with tighter performance budgets than existing distributed ElGamal schemes.
  • The non-adaptive adversary restriction leaves open whether the first version resists adversaries that choose corruptions after seeing ciphertexts.
  • The constructions could be tested against other threshold variants of BGN to measure concrete overhead differences.
  • The work implicitly connects to broader questions of how to distribute homomorphic schemes without losing their algebraic properties.

Load-bearing premise

The proposed distribution methods are correctly built and the security reductions to the subgroup decision problem hold in the chosen groups.

What would settle it

A concrete timing comparison or security reduction that shows the second version is not faster than EDECC, or an attack that breaks semantic security of the first version under active non-adaptive adversaries.

Figures

Figures reproduced from arXiv: 1907.07282 by Fatiha Merazka, Oualid Benamara.

Figure 1
Figure 1. Figure 1: Computation time with T 7. Conclusion We have designed two distributions of the BGNC. The first one is proved semantically secure and the second one is more efficient than the DEGECC. While efficiency is considered a poor comparison parameter, it can be an essential one in the setting of a sensor network, wherein energy consumption is of concern, rathen than the security level of the scheme. 8. References … view at source ↗
read the original abstract

The aim of this paper is to provide two distributed versions of the Boneh-Goh-Nissim Cryptosystem (BGNC). We give a proof of the semantic security for the first one. This guaranties that our algorithm is semantically secure in the contest of active non-adaptive adversaries. Furthermore, we prove that the second version of our distributed scheme is computationally more efficient than the ElGamal destributed elliptic curve cryptosystem (EDECC) and secure under the Subgroup Decision problem (SDP) assumption.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper proposes two distributed versions of the Boneh-Goh-Nissim (BGN) cryptosystem. It provides a proof of semantic security for the first version against active non-adaptive adversaries. For the second version, it claims it is computationally more efficient than the ElGamal distributed elliptic curve cryptosystem (EDECC) and remains secure under the Subgroup Decision Problem (SDP) assumption.

Significance. If the security reductions and efficiency claims hold with full constructions and proofs, the work could extend BGN to threshold/distributed settings, potentially aiding applications in multi-party computation. However, the abstract supplies no equations, reductions, or performance metrics, so the significance cannot be assessed beyond the high-level claims; no machine-checked proofs or reproducible code are mentioned.

major comments (2)
  1. [Abstract] Abstract: The central security claim for the second distributed version (secure solely under SDP) is load-bearing but unsupported by any reduction steps or modeling of the distribution protocol (key sharing, partial decryption). Without showing that the adversary's view reduces directly to an SDP instance without extra oracles or leakage, the claim cannot be verified.
  2. [Abstract] Abstract: The efficiency claim that the second version is 'computationally more efficient' than EDECC is stated without any concrete metrics, timing data, or complexity comparison; this undermines the performance analysis assertion.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments on our manuscript. We agree that the abstract is high-level and will revise it to better reflect the details present in the full paper. We address each major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The central security claim for the second distributed version (secure solely under SDP) is load-bearing but unsupported by any reduction steps or modeling of the distribution protocol (key sharing, partial decryption). Without showing that the adversary's view reduces directly to an SDP instance without extra oracles or leakage, the claim cannot be verified.

    Authors: The full manuscript (Sections 3 and 4) provides the complete distributed protocol construction, including key generation with secret sharing, partial decryption, and the security argument. For the second variant, the proof models the adversary's view in the distributed setting and shows a direct reduction to the SDP assumption without introducing extra oracles or leakage beyond what the original BGN security allows. We will revise the abstract to include a one-sentence outline of this reduction and explicit references to the relevant sections. revision: yes

  2. Referee: [Abstract] Abstract: The efficiency claim that the second version is 'computationally more efficient' than EDECC is stated without any concrete metrics, timing data, or complexity comparison; this undermines the performance analysis assertion.

    Authors: Section 5 of the manuscript contains the performance analysis, including an asymptotic comparison of group operations (exponentiations and pairings) between the second distributed BGN variant and EDECC under the same security parameter, demonstrating fewer operations for the proposed scheme. No empirical timing data is provided, as the analysis is theoretical. We will revise the abstract to state the key complexity metrics (e.g., O(1) vs. O(n) operations in certain phases) and reference the section. revision: yes

Circularity Check

0 steps flagged

No circularity detected; claims rest on external SDP assumption without self-referential reductions.

full rationale

The provided abstract and claims assert semantic security for the first distributed BGN version and SDP-based security plus efficiency for the second, but contain no equations, no fitted parameters renamed as predictions, and no self-citations that bear the central load. Security is stated to follow from the standard SDP assumption used in original BGN; no derivation step reduces by construction to the paper's own inputs or prior self-work. Full text inspection yields no quoted self-definitional, fitted-input, or uniqueness-imported patterns meeting the criteria for circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only; the SDP assumption is invoked for the second variant's security, but no free parameters, additional axioms, or invented entities are visible.

axioms (1)
  • domain assumption Subgroup Decision problem (SDP) assumption holds in the chosen groups
    Security of the second distributed version is stated to rest on this assumption.

pith-pipeline@v0.9.0 · 5615 in / 1109 out tokens · 17728 ms · 2026-05-24T20:36:30.845207+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

  1. [1]

    Benamara, Elliptic Curve Discrete Logarithm Problem , General Mathematics Notes, vol

    O. Benamara, Elliptic Curve Discrete Logarithm Problem , General Mathematics Notes, vol. 15, pp. 84–91, March 2013

    work page 2013

  2. [2]

    Boneh, E.J

    D. Boneh, E.J. Goh and N. Kobbi, Evaluating 2-DNF formulas on ci- phertexts, Proceedings of the Second international conference on Theory of Cryptography, no. 17, pp. 325–341, 2005

    work page 2005

  3. [3]

    Broker, P

    R. Broker, P. Stevenhagen, Constructing of elliptic curves of prime order, Contemporary Mathematics, vol. 20, 2007

    work page 2007

  4. [4]

    Changgen, and L

    P. Changgen, and L. Xiang, Threshold Signcryption Scheme Based on Elliptic Curve Cryptosystem and Verifiable Secret Sharing, Proc. Intern. Conference on Wireless Communications, pp. 1182–1185, 2005. 14

    work page 2005

  5. [5]

    Farah, M.Y

    S. Farah, M.Y. Javed, A. Shamim and T. Nawaz,An experimental study on Performance Evaluation of Asymmetric Encryption Algorithms , Re- cent Ad. in Information Sciencce, vol. 62, no. 1, pp. 31–42, 2012

    work page 2012

  6. [6]

    Farras et al., Linear threshold multisecret sharing schemes , Inform

    O. Farras et al., Linear threshold multisecret sharing schemes , Inform. Processing Letters, vol. 112, no. 17-18, pp. 667–673, 2012

    work page 2012

  7. [7]

    Fouque, G

    P.A. Fouque, G. Poupard and J. Stern,Sharing decryption in the context of voting or lotteries, Financial Cryptography, LNCS, pp. 90–104, 2000

    work page 2000

  8. [8]

    Fournaris, A Distributed Approach of a Threshold Certificate- Based Encryption Scheme with No Trusted Entities , Information Se- curity Journal: A Global Perspective, vol

    A.P. Fournaris, A Distributed Approach of a Threshold Certificate- Based Encryption Scheme with No Trusted Entities , Information Se- curity Journal: A Global Perspective, vol. 22, no. 3, pp. 126–139, 2013

    work page 2013

  9. [9]

    Ivey-Law and R

    H. Ivey-Law and R. Rolland, Constructing a database of cryp- tographically strong elliptic curves , Crypto’Puces, 9th-12th May 2011,http://galg.acrypta.com

    work page 2011

  10. [10]

    Lauter, The advantages of elliptic curve cryptography for wireless security, Wireless Communications, IEEE, vol

    K. Lauter, The advantages of elliptic curve cryptography for wireless security, Wireless Communications, IEEE, vol. 11, no. 1, pp. 62–67, 2004

    work page 2004

  11. [11]

    Levent and L

    E. Levent and L. Weimin, ECC based threshold cryptography for secure data forwarding and secure key exchange in MANET (i), Proceedings of the 4th IFIP-TC6 international conference on Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communication Systems, NETWORK- ING 05, no.12, pp. 1...

    work page 2005

  12. [12]

    P. Paillier, Public-key cryptosystems based on composite degree residu- osity classes, Proceedings of the 17th international conference on Theory and application of cryptographic techniques, Springer-Verlag, Berlin, Heidelberg, no. 16, pp. 223–238, 1999

    work page 1999

  13. [13]

    Stein and others, Sage Mathematics Software (Version 5.11) , The Sage Development Team, 2013

    A. Stein and others, Sage Mathematics Software (Version 5.11) , The Sage Development Team, 2013

    work page 2013

  14. [14]

    Zhang, F

    X. Zhang, F. Zhang, Z. Qin, J. Liu, ECC Based threshold decryption scheme and its application in web security, Journal of Electronic Science and Technology of China, vol. 2, no. 4, 2004. 15

    work page 2004