swordswinger12

From the abstract: "The new time complexity is asymptotically worse than Shor’s algorithm, but the qubit requirements are asymptotically better, so it may be possible to physically implement it sooner."

This is a nice result that shows how to speed up the best-known classical factorization algorithm using a quantum algorithm for one of the steps. Importantly, it does it using asymptotically fewer qubits than Shor's algorithm requires. However, the overall algorithm in the paper is still subexponential, not polynomial like Shor.

I'm not an OS person, so forgive me if this is a stupid question: Lots of people are excited about Intel SGX and similar things. Are there any interesting ways people are thinking about combining, like, Docker containers with SGX enclaves and such? One could imagine (e.g.) using remote attestation to verify an entire container image.

I second this - Gross is a phenomenal lecturer. These videos would probably be a great supplement to any self-study of algebra.

Most of the modern theory of error-correcting codes has its roots in abstract algebra. It's also important in theory - Babai's recent celebrated quasipolynomial algorithm for graph isomorphism relies on group theory. Most of the recent results in cryptographic obfuscation also rely on group theory because they encode circuits as permutation matrices using Barrington's theorem.

Cool article! Gray codes are used in cryptography sometimes too; the most well-known example is probably the Offset Codebook (OCB) authenticated encryption scheme, which uses a Gray code to compute tweaks: http://web.cs.ucdavis.edu/~rogaway/papers/ocb-full.pdf

The prof of my applied ML class this semester jokingly refers to ML research's approach to statistics as "punk stats", which I find to be pretty accurate.

Of course not; I never said it did matter.

Hypothetically, if Google never happened and I was a lead dev looking across the table at Sergey Brin deciding whether to hire him with that resume, I'm saying I absolutely would. Any hiring manager or lead dev today would make the same decision, is my point.

"On Google’s platform for example, an extraction attack would cost less than $0.10, and subvert any further model monetization"

Contra all the chuckleheads making jokes about him never getting hired anywhere today, this is actually an extremely impressive resume for a third-year graduate student. He had a sole-author publication in a top conference already!

If this jury-rigged, duct-taped "password hashing" scheme impresses you, I've got some land in Florida you might be interested in.

Seriously, though, it's a complete fallacy to think that more complicated password hashing schemes with lots of fancy steps are better. I was at the talk where this scheme was presented, and Alec Muffett himself said the only reason it was so complicated is because they had to layer stronger hashes on top of existing ones instead of revoking all outstanding session cookies (forcing every Facebook user in the world to re-authenticate).

>But: all the password hashes are fine, including the ones that aren't space-hard.

Not quite sure this is true: the Alwen-Blocki attack at CRYPTO this year (and some other nice recent work) demonstrated that there are some subtleties in this area that we don't fully understand yet.

You include things like DSA and ECDSA, which are not hash algorithms, but signatures. Is a signature being computed internally? If so, with what key?

Maybe nothing, but it's just kind of a weird, nonstandard way of doing things. Also it's not immediately obvious to me that your method meets modern security definitions like IND-CCA2.

So is there a per-chunk MAC, or do you rely on the signed hashes of ciphertext for the integrity and authenticity of each chunk?

Can you describe your file encryption procedure? In the Meta::Chunk class the 'encrypt' function only computes AES-CBC with no MAC, but there are calls to compute_strong_hash at other points in the library. There are references to a (non-cryptographic) Rabin hash as well as SHA2-224 and SHA3-224 in these functions - which is used for ciphertext authenticity and integrity?

Have you thought about just not using the phrase "zero knowledge" at all?

-Usually the SSE model accounts for a malicious server that just stores every search token it's given, so the server doesn't need to reconstruct them.

- You could store W on the server, but you would leak additional information to the server during an update - namely, the per-keyword update frequency. Section 5.5 describes an extension to reduce client-side storage at the cost of additional computation.

I haven't looked closely at the full construction, but it's fairly similar to an earlier paper by Cash et al. (https://eprint.iacr.org/2014/853) which is surprisingly practical - their system can do keyword searches on the entire English Wikipedia in just a couple seconds.

In terms of security, things are a bit more complicated. The last ~year has seen a couple papers (https://eprint.iacr.org/2016/718 and https://eprint.iacr.org/2016/172) that demonstrate damaging and practical attacks against most SSE constructions. It's really not clear how secure any SSE scheme is in practice, or whether there is a sensible model in which SSE can be both secure and efficient enough for practical use.

I do research in this area. What exactly would you like clarified?

Oh god, I still have nightmares about Herstein. I took an undergrad algebra class from a very old-school prof who thought it would be good for undergrads to be exposed to some of the problems - they gave all of us quite a bit of trouble.

Why no Halmos, "Finite-dimensional vector spaces"? It's pretty theoretical but very approachable also.

Actually the secure comparison protocol is the easy part - even generic SMC techniques are getting really fast these days. Also, they only involve about as much heavyweight crypto as a few TLS handshakes. Extracting a per-user fuzzy fingerprint from mouse and keyboard movements with enough entropy to make brute-force infeasible might be harder.

This sentence worries me: "any secure computation algorithm that can compare our choice of user behavioral signature without exposing it" because it makes it seem as though there are lots of these just lying around. It seems like this would be very tricky to construct, especially given the inherent fuzziness of a signature/fingerprint based on user behavior. Do zero-knowledge 'proofs of behavior' exist?

EDIT: That said, I do think this is a cute idea.

Why roll your own consensus algorithm?

This is a garbage, clickbait, content-free article that purposely misquotes the Riffle paper.

Yeah, it's a model of computation used in this line of research. See the original Goldreich/Ostrovsky paper for more info: http://dl.acm.org/citation.cfm?id=233553

If you're interested in the basic tools used in this system, this is another paper that uses some similar ones: http://arxiv.org/abs/1503.06115

Phil Rogaway called it 'elegant', fwiw.

I have an honest, and probably dumb, question: how do warrant canaries actually avoid the prohibition against disclosing the receipt of a national security letter? Like, how is taking down a warrant canary legally dissimilar from just tweeting "we got an NSL"? If it semantically "means" the same thing, then why is one illegal and one legal?

No, I'm sorry, that's not how cryptography works. A 'skim' clarifies nothing - you need precise proofs to understand security. And yes, I'm aware they provide proofs in the extended report, but the adversarial model seems not to model a real attacker particularly well. Here's a concrete question affecting real-world security that is seemingly unaddressed: what does their scheme leak about the frequency of rule matches? Can an adversarial middlebox see that some rules are matched more frequently than others? Are there rule sets for which this frequency information allows the adversary to guess plaintexts?

I'm not sure you're right about that. There are legitimate reasons to criticize this paper (its unclear, confusing security claims, for one) but the basic functionality they build can be used for an IDS, which seems beneficial to users to me.