What are some innovative encryption methods? | Hacker News Reader

What are some innovative encryption methods?

46 pointsask2sk37 comments

A friend of mine is doing PhD and in-need of some latest and innovative encryption methods for the thesis. Could anyone please recommend something?

View on HN

Not exactly "innovative", since it's one of the oldest encryption methods, but the One-Time Pad[0] is considered "perfect encryption" and proven to be unbreakable. The mere possibility of unbreakable encryption could fill up a thesis by itself.

[0] http://www.cs.utsa.edu/~wagner/laws/pad.html

<strike>edit to clarify: "unbreakable" is the wrong word, since it could be brute-forced with enough time and energy, like any encryption method.</strike>

yes it is completely unbreakable.

I don't believe that it can be brute forced, as brute-forcing may yield multiple reasonable decryptions with conflicting interpretations.

No, one-time pads are really unbreakable. You can't tell if the key you generated, which yielded "ATTACK AT DAWN", decrypted to the real message. It might have been "HN != SLASHDOT" -- all decrypts are equally likely.

edited thanks. he even explicitly said that it was unbreakable in the article I linked :-).

I was wondering if using randomly generated shared 1GB or so file as a kind of one-time pad would be useful. Xor data with it using it as circular buffer, do messages must be of the same length or it will go out of sync.

If you reuse your pad, you're vulnerable to frequency analysis, which is literally the oldest trick in the book. You might as well send in plaintext.

How easy would it be if you would go through the entire 1GB and only then from the beginning? I guess it is a question of how big messages are.

If you're only reusing it once, then I guess frequency analysis gets tricky, but the problem you have instead is that you have provided a validation function: Where, using a one-time-pad, any key that yields plausible cleartext is a possible candidate, if you have two cyphertexts encoded with the same (piece of) the one-time-pad, only keys that result in plausible decrypted cleartext for both cyphertexts are possible candidates.

This was how an early break-through in breaking the Enigma was achieved (tangentially, as the Enigma isn't a one-time-pad, but the analysis is similar): Codes were rotated daily, but the first message sent out every morning with the new codes was a weather-report. Thus, the team could immediately cull the search-space to keys that would decrypt to "Weather on [date]" for the first n characters.

The problem, of course, is that you're just flipping the problem around. For every bit you need to send A->B, you need to first securely send a bit B->A (the pad). That's practical for a number of applications, and obviously not for many others.

Combined with envelope keys it can be effective for many applications.

An envelope key is a securely, randomly generated key used to encrypt the large payload. Then the envelope key (much smaller than the payload) can be encrypted using a one time pad.

The result is that the precious bits of encryption provided by the one time pad are used up at a predictable rate.

Guessing the envelope key is more probable than guessing the one time pad key, but that only breaks a single message's encryption.

If you use good encryption and a reasonable key size, that’s good in practice, but theoretically, that’s a lot less secure than a one time pad.

An attacker can ‘simply’ try all possible keys and use statistics to filter out those that look like natural language.

If the encrypted text is large enough, chances are you will be left with only one plausible plaintext.

Also, AFAIK, we don’t know whether good encryption using a key much shorter than the plaintext, in the sense that an attacker can’t use statistics on the encrypted text to learn something about the key, exists at all.

Your final aside, "good encryption using a key much shorter than the plaintext," is something I hadn't really thought much about and seems like a reasonable way to go directly from a one time pad to the ciphertext.

As you say, there doesn't seem to be a way to guess the key length from the ciphertext. Ignoring side channel attacks for the moment, it does seem like the one time pad could encrypt the entire message simply by using some clever way of "extending" the key.

> it does seem like the one time pad could encrypt the entire message simply by using some clever way of "extending" the key

Any way of meaningfully extending the key will be vulnerable to a kind of analysis well understood 70 years ago.

This is basically what almost the entire field of cryptography is about: Figure out how you can effectively and securely encrypt things with a key that's a lot shorter than your cleartext.

Indeed. The two simplest examples are the Caesar cipher (https://learncryptography.com/classical-encryption/caesar-ci..., key length of 1 character) and the Vigenère Cipher (https://learncryptography.com/classical-encryption/vigenere-..., key length as long as you want it to be)

Both extend the key by repeating it. That is not a good idea.

this is the only fully 100% proven crypto method. rest is 'weak' , only saved by lack of computing power, not actual difficulty of algorithm. problem with otp is dat if you can send the pad... you mightswell not use it. as the pad needs to be sent over secure channel. So it's unbreakable, but also impractical.

Your friend is not going to get PhD thesis topics by asking his friend to post on HN.

Regardless, here's what I think are interesting areas in recent crypto:

- Performance improvements in fully homomorphic encryption, starting with Gentry's work in 2009.

- Practical applications of secure multiparty computation, e.g. Dyadic Security and Google's SMC work.

- Non-NIST standards with actual adoption like Curve25519 and Chacha20-Poly1305

- Functional Encryption: http://eprint.iacr.org/2010/543

- Post-quantum crypto like New Hope (https://eprint.iacr.org/2015/1092) and Supersingular Isogenies (http://eprint.iacr.org/2011/506)

- Candidate functions for Multilinear Maps, e.g. https://eprint.iacr.org/2012/610

- Hardware-based secure enclaves like SGX

Hellow sweis, actually he is posted for me, due to some technical issues I could not. how can u say that I can't get thesis topic? and thank you for your reference links.

Innovative methods of gathering entropy is interesting to me. Because encryption methods are pretty darwinian. The good ones are heavily used and the quirky/bad ones fall into disuse.

But methods of gathering entropy can range from a microphone recording a city street to the classic keyboard/mouse.

Both are valid, but not as practical.

Personally I have the OneRNG, an open source usb-stick that gathers entropy by generating RF noise.

There are other devices like that out today.

Zero knowledge proofs https://en.wikipedia.org/wiki/Zero-knowledge_proof

Expanding on that, zk-snarks[0], a kind of non-interactive zero-knowledge proof[1] are really interesting. They're used as the basis for the anonymous cryptocurrency zcash[2], where one can prove they haven't already spent an input without actually revealing which input they are spending.

[0]: https://z.cash/technology/zksnarks.html

[1]: https://en.wikipedia.org/wiki/Non-interactive_zero-knowledge...

[2]: https://z.cash/

Post-quantum key exchange using ring learning with errors and hybrid solutions: https://eprint.iacr.org/2014/599.pdf

This is really cool! I know Supersingular Isogeny Diffie-Hellman has a patch to build the cipher suite into OpenSSL [0] like the paper you linked. I know that Microsoft Research also has the best known implementation of SIDH [1]. Do you know of any paper studying the performance of those two?

[0] https://github.com/dconnolly/sidh-for-openssl-patch

[1] https://github.com/Microsoft/PQCrypto-SIDH

The closest paper I can find comparing performance would be this one (section 3.4 for performance): https://eprint.iacr.org/2016/1017.pdf

Check out the Open Quantum Systems implementation, they've got a suite incorporating a number of quantum resistant algorithms: https://github.com/open-quantum-safe/liboqs

They have the SIDH implementation you mentioned (https://github.com/open-quantum-safe/liboqs/blob/master/docs...), and a test harness for comparing performance.

Really great stuff. Thanks!

Obligatory mention of homomorphic encryption [0].

[0] https://en.wikipedia.org/wiki/Homomorphic_encryption

I initially read this as “homeopathic encryption”, and was prepared to be very amused! Expected something along the lines of “the input is subjected to a random bit flip approximately once per 10kB; amongst practitioners, this is considered more effective than the unnecessarily heavyweight approach taken by Western-style encryption schemes.”

Oh, I think you're thinking of homeopathic KDFs. Homeopathic encryption users just use the Crystalline cipher, because it helps center our chakras.

Post-Quantum Cryptography using Supersingular Isogenies: https://eprint.iacr.org/2011/506.pdf

Cryptography with Cellular Automata:

http://www.stephenwolfram.com/publications/academic/cryptogr...

Nobody uses anything related Wolfram's cellular automata. I don't think there are any robust security proofs.

I'd like to see more analysis of things like CHAFFINCH.

https://www.cl.cam.ac.uk/~rnc1/Chaffinch.html

Hi, thank you. it seems novel. can you please elaborate it, could it be applied for biometric authentication!

Identity based encryption.

https://en.wikipedia.org/wiki/ID-based_encryption

"Identity-based systems allow any party to generate a public key from a known identity value such as an ASCII string. A trusted third party, called the Private Key Generator (PKG), generates the corresponding private keys...."

I think it's innovative and a bit of "thinking outside the box". You do need to ultimately trust a 3rd party (same as in PKI or WOT I guess?).

Shamir Secret Sharing is very cool and fairly old. It introduces a tool that inspires many neat applications.

There is a lot of interesting work in privacy preserving databases as well.

functional encryption https://en.wikipedia.org/wiki/Functional_encryption

i think this is pretty cool ,and getting more relevant now quantum computers are comming closer...

https://en.wikipedia.org/wiki/McEliece_cryptosystem

Thanks everyone. I have forward all your ideas and suggestions to my friend.

Reply on news.ycombinator.com