3
$\begingroup$

The Domingo-Ferrer cryptosystem is a fully homomorphic cryptosystem. It works fast enough. I have only seen known-plaintext attacks. Is this a reason not to use it in practice? Or are there more significant shortcomings due to which it is not recommended to be used?

$\endgroup$
  • 2
    $\begingroup$ If something is vulnerable to known (or chosen) plaintext attacks, it is broken. And that is enough of a reason not to use it. But maybe you should add some references to the question regarding both the construction and possible attacks. $\endgroup$ – tylo Sep 22 '19 at 18:05
7
$\begingroup$

TLDR: The scheme is symmetric only, its "provable security" argument is flawed, and it is practically insecure when even a modest amount of plaintext is available to attackers.


I'm commenting on the scheme in: Josep Domingo-Ferrer, A Provably Secure Additive and Multiplicative Privacy Homomorphism, published in proceedings of ISC 2002. I ignore the 1996 scheme, which in some sense is a subset.

The paper introduces a symmetric encryption system allowing computation (addition, subtraction, multiplication of plaintext) performed on the ciphertext without key, provided that the results remain below a certain bound ($10^5$ to $10^{20}$ in the proposed parametrizations).

Provable security is claimed for arbitrarily powerful adversary, but under the assumption that only a small number $n$ of plaintexts (including computed results) are known to an adversary: $5$ to $50$ in the proposed parametrizations.

This is an extremely serious limitation. Combined with the fact that it is a symmetric cryptosystem (encryption requires a secret, which also allows decryption of any plaintext or computed result known in ciphertext form), that greatly reduces the practical interest of the system.

In particular I see no credible case for offloading computation to a party with cheaper computational power, for the cost of encryption is going to be prohibitive compared to calculations of practical interest. And if we assume that all ciphertext is public, any party that encrypts of decrypts in legitimate use can get at all the plaintext.

Update: Worse, the information-theoretic security argument is flawed. In a nutshell, it shows that the adversary can't find the key under the assumption that limited information about plaintext is available, but fails to account for

  • equivalent keys, allowing to decipher without knowing the actual key
  • considerable information about the plaintext made available merely because it must be small enough that the homomorphic property is usable without overflow.

ACM DL shows 35 papers under cited by. Two notable ones are

  • Ueli Maurer and Dominik Raub, Black-box extension fields and the inexistence of field-homomorphic one-way permutations, in proceedings of Asiacrypt 2007: credit is given for having shown that there would be practicals applications to the objects which existence is disproved.
  • A 2018 self-citation in Anonymous and secure aggregation scheme in fog-based public cloud computing, acknowledging that the scheme is

    only secure against ciphertext-only attack

Sadly absent from that citation list are two specific refutations of the paper:


On my first glance at the paper, I found it less than fully satisfying from a modern academic perspective:
- The security proof gives no quantitative bound of the advantage for adversaries (the claim is that parameters can be made big enough that this advantage is negligible).
- Parameter $s$ is said to be secret, but its is a small integer from $5$ to $53$ in the proposed parametrizations, and can be estimated from ciphertext size and plaintext bound. The academically correct thing to do is to consider $s$ public.
- It is considered that the system could remain secure when the number of leaked plaintexts exceeds $n$. But the argument boils down to: our analysis does not demonstrate that the secret key is computationally easy to find.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.