Apple's Collatz Hash Patent Application (2013)

http://www.google.com/patents/US20130108038

by deckar01 • 11 years ago

40 26 11 years ago

vortico• 11 years ago

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.

deckar018• 11 years ago

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.

vlasev• 11 years ago

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

throwawaykf055• 11 years ago

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.

coob• 11 years ago

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

transfire• 11 years ago

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).

deckar018• 11 years ago

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?

throwawaykf055• 11 years ago

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?

deckar018• 11 years ago

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.

unavoidable• 11 years ago

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!

spacemanmatt• 11 years ago

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

monochromatic2• 11 years ago

clarified

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

throwawaykf055• 11 years ago

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

gojomo• 11 years ago

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.

otterley• 11 years ago

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.

deckar018• 11 years ago

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

monochromatic2• 11 years ago

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

deckar018• 11 years ago

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.

scottevi199• 11 years ago

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

throwawaykf055• 11 years ago

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.

bjblazkowicz• 11 years ago

This is like metallica trying to patent a guitar riff.

deckar018• 11 years ago

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.

VeejayRampay• 11 years ago

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

Apple's Collatz Hash Patent Application (2013)

Related Stories