back to article Researchers crack homomorphic encryption

Homomorphic encryption is one idea offered to secure data in the cloud: the idea is to let software work on data without decrypting it. It's mostly a research project at this stage, because it's very processor-intensive and therefore slow, and now one such scheme has the added problem of being vulnerable. A trio of boffins …

  1. Paul Renault

    Interesting: the orginal, now-worthless paper describing the scheme is is paywalled..

    ..and the paper destroying it is free for the taking.

    Oh, irony, they name is Bogos, Gaspoz, and Vaudena.

    1. Notas Badoff

      Re: Interesting: the orginal, now-worthless paper describing the scheme is is paywalled..

      The 'capture' of academic papers by the various nefarious institutions has been reviewed extensively here in these pages.

      In the meantime, may I suggest an orientation at Wikipedia? Unfortunately there was insufficient computational resources available for me to decrypt the scheme used therein...

      1. Destroy All Monsters Silver badge
        Holmes

        Re: Interesting: the orginal, now-worthless paper describing the scheme is is paywalled..

        IEEE is hardly a "nefarious institution" and the original paper is hardly "worthless".

        As Google-Fu is less than overwhelming, I bring you this

  2. Anonymous Coward
    Anonymous Coward

    can't resist

    Big faping motion to Ivory Tower nerd wars. Let us know when they come up with something actually useful to the real world.

    1. Richard 12 Silver badge

      Re: can't resist

      Put down your phone and tablet, and step away from your computer.

      Those are all direct results of long-running "nerd wars".

      And while you're at it, hand in your satnav, disconnect your electricity, gas and oil, and don't eat any food that came further than a day's walk.

      I tip my hat to the nerds that came before, for they built our world.

    2. PassiveSmoking

      Re: can't resist

      I can only assume you do all your online banking and shopping in the clear then, if you don't think encryption is useful. That or you're Donald Trump or Theresa May.

  3. JeffyPoooh
    Pint

    If One-Time Pads could self-regenerate...

    'Two-Time Pads':

    Use One-Time Pad #1 to encrypt the Data #1

    Transmit the encrypted Data #1

    Generate a new One-Time Pad #2 using random noise

    Use One-Time Pad #1 (again) to encrypt the new One-Time Pad #2

    Transmit the new One-Time Pad #2 to regenerate the One-Time Pad.

    ...

    Anyone trying to correlate the two usages of One-Time Pad #N will be looking at Data #N and Noise.

    Reusing a One-Time Pad with Data #1 and Data #2 is deadly.

    Not so sure about Data and Noise.

    1. Dr Spork
      Pirate

      Re: If One-Time Pads could self-regenerate...

      Use One-Time Pad #1 (again) to encrypt the new One-Time Pad #2

      Not so sure about Data and Noise.

      Here be dragons

    2. allthecoolshortnamesweretaken

      Re: If One-Time Pads could self-regenerate...

      "Reusing a One-Time Pad with Data #1 and Data #2 is deadly."

      Yeah, well, if you reuse a One-Time Pad it isn't a OTP. That's the whole point of OTPs; always use once only and discard afterwards, so that no patterns emerge that can be analysed.

      1. JeffyPoooh
        Pint

        Re: If One-Time Pads could self-regenerate...

        atcsnwt "...patterns emerge..."

        Yes. Patterns emerge when the same OTP is used twice, with data each time. That's known by everyone.

        What's not clear, at least to me, is if any 'patterns emerge' when a given OTP is used the second time to send an equally sized batch of noise to refill the distant collection of pads.

        My instinct tells me this can work, but I'm not overly confident.

        1. SCP

          Re: If One-Time Pads could self-regenerate...

          JeffyPooh wrote:

          "What's not clear, at least to me, is if any 'patterns emerge' when a given OTP is used the second time to send an equally sized batch of noise to refill the distant collection of pads."

          To illustrate the problem consider a OTP being used to XOR [I know I know - but it keeps the example simple] data streams. You propose sending:

          D1 (+) OTP1

          OTP2 (+) OTP1

          Then later:

          D2 (+) OTP2

          Assuming that Eve has got all this she can now do:

          ( D2 (+) OTP2 ) (+) ( OTP2 (+) OTP1 ) giving

          D2 (+) OTP1

          Effectively - you are just re-using OTP1, with all the insecurities that incurs.

          HTH

    3. BinkyTheHorse
      Facepalm

      Re: If One-Time Pads could self-regenerate...

      If I had a penny for every time people forget the "One" being a critical element of the "One Time Pad", I could afford one more of OP's icon.

      And if I had a dollar for every time I saw someone using "OTP" and "XOR" synonymously, I could buy a whole crate.

      1. h4rm0ny

        Re: If One-Time Pads could self-regenerate...

        And if I had a pound for every time someone sent me the PRIVATE key for their entire organizations authentication servers instead of the public key, I'd have £1.00.

        But it was a good one pound.

      2. JeffyPoooh
        Pint

        Re: If One-Time Pads could self-regenerate...

        That's why it's headed 'Two-Time Pads'.

        This naming was intended to assist with getting over the semantic point (which is trivial and non value-added), and hopefully consider the actual concept itself.

        There's not going to be any correlation between 'encrypted data' and 'encrypted noise'. Two 'encrypted data' would be fatal. But 2nd use with noise?

        The noise is random, so reveals nothing about the encrypted data.

        The data remains unknown, so the new pad is also securely transmitted.

        There's likely to be some subtle flaw, but it's not to found by trivial semantic review of 'One...'.

  4. Pete4000uk

    Oops...

    I came in here to see how encryption could be homophobic...

    Its to early

  5. Anonymous Coward
    Headmaster

    I could be wrong about this, but isn't the idea of homomorphic encryption to let software work on data without DEcrypting it? So, for example, I can write an app that updates a cloud database without at any point leaving any unencrypted data lying (or flying) around.

    1. scarletherring

      I could be wrong about this, but isn't the idea of homomorphic encryption to let software work on data without DEcrypting it?

      You're not wrong. The article is.

    2. Anonymous Coward
      Anonymous Coward

      The "F" in FHE is "Fully".

      Something governments aren't really keen on, as it means their access to data is controlled.

  6. Dotzero

    Top notch security

    "The activation key is the same for all the customers."

    What could possibly go wrong?

  7. Nigel Smart
    Holmes

    Not interesting

    The scheme broken here is not that interesting in the first place. Of course "The Register" should probably validate any article which appears on the IACR ePrint archive for "interestingness" before they just write an article on it. :-)

    More interesting, was the break presented at CRYPTO yesterday here in Santa Barbara (https://www.iacr.org/conferences/crypto2016/) of the NTRU based FHE scheme (http://eprint.iacr.org/2016/127.pdf). This is the FHE scheme used by the Microsoft Research Labs demo applications of FHE talked about in previous Register articles.

    Luckily though, even if the scheme in this article and the NTRU based FHE scheme have attacks, the main FHE scheme proposed by most researchers is the BGV one; which is the one implemented in the IBM library HELib (based on earlier code by yours truly).

    In addition the break on the NTRU based FHE scheme does not apply to the "standard" NTRU scheme; which is kind of important as NTRU encryption is one of the prime contenders to replace standard schemes like RSA and ECC once a quantum computer is available.

    As for the other points above. Any crypto paper worth its salt is open access in any case, as it would be published by the IACR and hence would be cross-posted to IACR ePrint. So if a crypto paper is behind a paywall; either it is rubbish or the paper can be obtained via ePrint.

  8. Gary Bickford

    HME will be enabling tech for agents and "uploading humans" - transhumanism

    HME will probably always require 100-1000 times as much CPU power and possibly data space as unencrypted computation. But it will be an essential tool for maintaining the internal privacy and security of "agent" systems traversing the internet. Without it, while data at rest may be encrypted it is still in plain text while in memory for processing. Since an agent has no way to predict or restrict what processors it is being run on - in fact not even whether it is on a real processor or a virtual one, those processors may be on compromised services that could be reading that memory and tracking the computation.

    The only way that has been proposed to protect such agents from compromise is homomorphic encryption, which allows the entire data collection that represents the agent can be kept in encrypted form at all times, even when it is running its computation processes. (In fact I would expect a higher degree of encryption for the data at rest, and a less-secure simulacrum used for the processing phase. This may be a necessary compromise.)

    IOW, if you have uploaded your mind and personality to the Net, that "evil" processor could be reading your mind and even erasing your memories and substituting new memories. But agents have many other practical purposes.

    The two most important factors in preservation of the internal integrity - identity - of any system are privacy, and protection against undesired or unnoticed modification from external forces. Only HME has this capability.

    As a side effect, this requirement will drive another wave to higher performance and capacity. An individual encrypted agent might require from one to 100 petabytes of storage and equivalent increases in computing and network traffic, within this century.

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon