Don't bother with that large table at the bottom.

With the headline as it is here, you could read the headline and know enough to possibly make a decision.

Like every theorem prover it has a logic that you use for stating propositions, and proving theorem. The logic is a specific logic that is closely related to HoTT.

- "On Zen" by Daio Kokuchi

- "Shobogenzo" by Dogen. I especially venerate the loose translation (or paraphrasing) by Brad Warner.

In fact, the article is only about indistinguishability obfuscation. What is mostly discussed in this thread is the notion of virtual black box obfuscation (VBB). VBB has been proven to be impossible in the general case (see https://www.wisdom.weizmann.ac.il/~oded/PS/obf4.pdf). There are a few special programs where VBB is feasible, such as point functions, but in general in cannot be achieved.

Indistinguishability obfuscation (iO) means that if you obfuscate two programs that compute the same function, then you cannot distinguish them. Or put in different words, if you get two obfuscated programs, then there is no better way than random guessing (except for a factor that is negligible in some security parameter) to find out if they stem from the same original program.

1. VBB would be making it so you can't glean information about A or B by running VBB(A) or VBB(B) or examining them, for various definitions of "information".

You can't tell A is a bubble sort at all, and you can't tell B is a selection sort at all.

VBB is, as mentioned, impossible in the general case.

2. IO would be making it so if you are holding IO(A) and IO(B), you can't tell them apart, and can't tell if the original was A or B.

So you can have functionally identical programs, and when you run them through IO, you can't tell whether the original was A or B.

See the formal model here: https://en.wikipedia.org/wiki/Circuit_(computer_science)

There are extensions of iO to RAM programs, but this is not it.

Or what is it for?

And how does it deal with timing? İf two programs I gave it have different complexity, would it pad the running time to some fixed value? İf so, how is that value chosen?

> Or put in different words,

I don't see how the second phrasing follows from the first one. In fact, I don't understand what the second statement is supposed to mean to begin with. Could you elaborate?

Roughly: VBB is the ability to take any program and make it indistinguishable from random.

IO is the ability to take two programs that compute the same function and make them indistinguishable from each other.

For example, if I plot how long both programs take at various scales, at some point I should be able to determine which one is O(n log(n)) right?

It is about what information you can glean about either of the originals. Formally (from the paper):

Indistinguishability: For every two ensembles {C0,λ} and {C1,λ} of polynomial-sized circuits that have the same size, input length, and output length, and are functionally equivalent, that is, ∀λ, C0,λ(x) = C1,λ(x) for every input x, the following distributions are computationally indistinguishable:

  {iO(1λ, C0,λ)} {iO(1λ, C1,λ)}

I don't understand. Shouldn't a different secret key yield a different function / circuit?

https://eprint.iacr.org/2013/454.pdf and friends have a direct description of the latter and references to the former.

This is just one mechanism.

As there are more generations of chess engines than go engines, it would be quite interesting to pull something similar off against them. My intuition is that it maybe works against Leela, as LeelaChess basically uses only neural networks (think alphago but for chess), whereas it should not work with Stockfish, as some parts of Stockfishs evaluation function are still adjusted by hand.

Users cannot be enumerated using the login, but using the signup. The author then argues that they should add the user enumeration function to the login.

This is similar to: The door is locked, but the window is open. And then consequently it makes no sense to close the door at all, as an attacker can sneak through the window.

Instead, the window should be locked as well, i.e., it should be impossible to enumerate users with the signup function.

    #!/bin/sh
    md5sum $0

  $ cat >a.py
  #! /bin/python
  import hashlib
  s='#! /bin/python\nimport hashlib\ns=%r\nprint hashlib.sha512(s%%s).hexdigest()\n'
  print hashlib.sha512(s%s).hexdigest()
  $ python a.py
  cf1daf466a7a95b245eab685b808fb861dab9af26078250a8041c4c08a8ff384 (edit: wrap)
  7f7d1853f9d62d6b40cc53d0c5be3efd80eb09f57b71250910c0d6157b73fcd3
  $ sha512sum a.py
  cf1daf466a7a95b245eab685b808fb861dab9af26078250a8041c4c08a8ff384 (edit: wrap)
  7f7d1853f9d62d6b40cc53d0c5be3efd80eb09f57b71250910c0d6157b73fcd3  a.py

In this case the hash doesn’t depend on the data at all. Do you see how that helps?

  #!/bin/sh
  HASH=6ce1c11751e405291eac368af96de90f
  # Increment until hash of this file equals $HASH: 1
  echo $HASH