I'm not thinking about ORAM - as you point out, it reveals access patterns.
Thus the reference to data diffusion, i.e. inner words are not stored at a single physical outer address, they are mixed with other data, and the outer addresses used to interact with memory state vary for the same inner address, without the RAM having any secrets.
The outer addresses don't need to be plaintext, but they do need to satisfy relationships with each other that are algebraically useful yet not discernible without a secret.
> with FHE if you reveal anything then you are actually revealing everything
Is this not subject to cryptographic vs information-theoretic hardness arguments: If I reveal to you 2^-256 bits of data per operation (i.e. astronomically close to zero), we'll call that good enough because you can't do enough computation to matter?
Yes they do, because that is what you will actually be accessing on the physical system. Call it what you want, but at some point you need to have a physical address that you will read from for any computation to proceed.
"If I reveal to you 2^-256 bits of data per operation"
Sure, but that is not going to help you get around the fundamental need to simulate random access by performing linear scans when you are using FHE. Think of it this way: you need to read some physical addresses, somehow, regardless of how you encode your data. If you only revealed a vanishingly amount of information about the physical addresses to access, then you would not have given the processor enough to do anything more efficient than a linear scan.
Now assume the processor could somehow access fewer locations than a linear scan accesses, which implies that it does not access all physical addresses. The processor can try to query all logical addresses (since it must store that much data anyway it should be able to enumerate them), and choose two such that one accessed a particular physical address and another did not (this must exist, because everything is being accessed -- if somehow such an address could not be found then all queries will be linear scans). The two logical addresses must differ in a particular bit position. What the processor can do is to take a given ciphertext, homomorphically compute its individual bits, and then insert each bit in the position where the two addresses differ -- and then use the access pattern to determine the value of each bit.
Thus the reference to data diffusion, i.e. inner words are not stored at a single physical outer address, they are mixed with other data, and the outer addresses used to interact with memory state vary for the same inner address, without the RAM having any secrets.
The outer addresses don't need to be plaintext, but they do need to satisfy relationships with each other that are algebraically useful yet not discernible without a secret.
> with FHE if you reveal anything then you are actually revealing everything
Is this not subject to cryptographic vs information-theoretic hardness arguments: If I reveal to you 2^-256 bits of data per operation (i.e. astronomically close to zero), we'll call that good enough because you can't do enough computation to matter?