Apple's Collatz Hash Patent Application (2013) | Hacker News Reader

Apple's Collatz Hash Patent Application (2013)

google.com

40 pointsdeckar0126 comments

I'm not sure this warrants a patent. Upon further inspection the only real transformation they add to the Collatz function is returning the result modulo some prime. This is a very generic operation that can turn any function into hash-like mapping on a finite field.

They even had the nerve to include a generalization of the Collatz function in the patent.

> The hash function can apply more complex variations, such as adding multiplication, addition, modulo or other operation(s) in the even and/or odd operations.

With this generalization one can accidentally construct a variation that simplifies to an existing hash function (prior art?).

Should a patent really be allowed to control the use of an entire class of functions?

How can a patent claim ownership of an infinite number of transformations on an idea?

The only thing you should read when evaluating the scope of a patent or patent application is the claims. In this case, the first claim is:

1. A method comprising:

receiving an input value and an iteration value;

based on the iteration value, iteratively performing steps comprising:

if a least significant bit of the input value is 0,

(1) dividing the input value by a first value,

if a least significant bit of the input value is 1,

(1) multiplying the input value by a second value,

(2) adding one to the input value, and

(3) applying a modulo operation of a prime value to the input value, to yield a first iteration value,

to yield an updated input value;

returning the updated input value as a hash value.

Note that the "first value" and "second value" can be numbers other than 2 or 3. Not even sure how that works.

Also, as the claim is currently written, it seems indefinite, or at least incorrect, because it is unclear if the modulo In step (3) is applied to the input value, or input value + 1, or the input value * second value, or (input value * second value) + 1. An exact reading of the claim implies the former, whereas what they probably want is the latter.

I'm not an expert in either of these areas - but how is cryptographic hashing an obvious application of the Collatz function? Is there some well-known property of Collatz sequences that make them suitable for crypto hashes?

Cryptographic hashes have many different properties that make them useful and distinct. The most fundamental properties the Collatz function shares with hash functions include it being deterministic and non-invertable. Applying the modulo operation to map the input/output to a finite field provides uniformity. Change the function to b^k and you have the discrete logarithm problem.

Thanks for the simple yet clear explanation.

This claim would probably also run into issues regarding patentable subject matter post-Alice v CLS Bank. It's almost completely abstract...

edit: nevermind, it's a patent application and not an issued patent.

HN Posters: Please stop posting patent applications as patents! They are not the same!

This is merely an application; the USPTO has not granted a patent based on it.

OP or mods, can you please update the title? It's currently factually incorrect.

Updated to reflect that the link refers to a patent application.

How can someone even patent something I was able to come up with at age 14? As a teenager I would have thought it was a stupid thing to patent, because it's a straightforward reaction after learning of the Collatz conjecture. The US patent office is beyond fucked.

And it's not even remotely cryptographically secure, or even fast.

It's not that it is stupid, straight-forward, insecure, or slow.

The problem I see is that this patent claims ownership of an infinite number of transformations that can be made to the Collatz function. There is nothing novel about this. They state that it is used as a hashing function, yet provide no property of the system that qualifies it to be a hashing function.

This belongs in a research paper, not in a patent.

Imagine patenting fractals, as in functions f(z) that can be iterated to make fractals!

Pretty much all patents are written in a way that can cover an infinite number of variations of the core idea. The novelty here may actually be the use of this as a cryptographic hash function. They give no supporting property, but as my other comment asks, if such a property cannot be easily divined, it may in fact be non-obvious.

It's an application, it hasn't been granted.

I totally agree! I learned about the conjecture in my late 20s and did some extensive work on the problem. The idea of using it as a hashing function is obvious (and equally obvious, it is a terribly inefficient one).

Look, Apple's innovations and IP battles with other corporate behemoths require a big patent attorney staff. But some weeks, there's more people than genuine novelty to protect. Thus, a filler filing like this.

This is like metallica trying to patent a guitar riff.

It is more like some person trying to assert copyright over all the ways you can add, remove, or change the notes in one of Metallica's guitar riffs.

It is more like it's impossible to use a metaphor in the programming world without someone correcting you with a different metaphor :)

Fortunately, the SCOTUS clarified that abstract subject matter is still ineligible. Even when you do it on a computer.

> clarified

I don't think you and I read the same Alice v. CLS opinion.

Unfortunately, most people just read the highly inaccurate 10-word summaries that tech media outlets bandy about.

As usual, somebody has found a patent application, read the title and nothing else, and decided it was alarming enough to post.

Well, no. I read the patent application several days ago, in its entirety (quite painful), because it relates to my current research. This patent application could very well inhibit the application of my research and discourage involvement by third parties.

http://www.uspto.gov/patent/initiatives/third-party-preissua...

The first step of the petition involved finding the "Confirmation Number" in the USPTO's PAIR system. From here I was able to find out that the filing status is "Abandoned -- Failure to Pay Issue Fee". Also of note is the fact that the status was set to "Abandoned" only after the "Notice of Allowance and Fees Due" was allowed to expire. The fact that the USPTO granted preliminary approval to this patent application is troubling.

Could you describe your research? If you've been researching this and have put out or know of any relevant publications, it can act as prior art for this application. You could also post those on askpatents.com, which patent examiners are known to look at occasionally.

I have not created any works that can be considered prior art for this patent application (which is actually now abandoned). My research primarily involves exploiting the computationally intensive aspects of the Collatz function (and its inverse) to construct cryptographic systems. Systems whose elements are computationally difficult to deconstruct, but trivial to construct and verify are of particular interest to me.

Reply on news.ycombinator.com