Topic: (space) efficient reusable addr via weil pairing IBE (Read 8938 times)

I see I dont think I realized that aspect of how bloom query works.  So you then with IBE-based filtering could send multiple keys, one for each block; but you are implicitly linked by being in one query, so you'd just as well mark your key with your preferred epoch size and sender uses epoch number in the query.

I think Greg is pointing out on IRC that by having a fairly small epoch you can choose later to go down to that epoch size or scale up by sending multiple epoch keys in a batch, a privacy/network round-trip trade off.

Re my other problem with epochs ("In practice you might need an epoch not block or overlapping test because the user does not have full assurance of their tx ending up in the pending block") I think that maybe fixable, if the blocknumber is chosen by the sender, and communicated in enough bits to be mostly unambiguous in the message.  Then the node can index them by sen block num and no ambiguity.

It could be that another way to partly obscure ownership of queries would be to relay queries and responses and mix other peoples queries with your own in a batch, however as we are considering the SPV client case relaying other peoples queries seems hard to gather query traffic on demand and to use more bandwidth than it saves relative just issuing smaller batches.

You could have relaying in the network eg using the embedded Tor but waiting for queries to mix with adds latency, and suffers flood attacks on mix-nets (send fake encrypted query traffic to flush out a tx, that has no-anon set vs the person doing the flooding who can distinguish their own queries).

Adam

You would need epochs for another reason. Recall that with Bloom filtering the remote node is asked for blocks in batches of 500 at a time and the remote end handles updating the filter as transactions are matched. This is to avoid the performance hit of a network round-trip for every block.

So have been talking with Greg Maxwell, Peter Todd, Jeremy Spillman, Mike Hearn, Bytecoin and others about reusable addresses.

There is a summary of the situation here http://www.mail-archive.com/[email protected]/msg03792.html and I had posed th question of whether it was possible to do better at all with Peter Todd:


and Peter proposed also the related problem of proving something about that existence or not of a solution to that problem. 

I think I have a proof-of-concept solution that proves by example we can do better in space efficiency, linkability defense and non-interactivity than my bloom bait, Peter Todds related prefix; and Greg Maxwell's extended bloom bait described http://www.mail-archive.com/[email protected]/msg03705.html.

So the idea is to use an IBE scheme as a building block in analogous way to my 1996 problem statement for NIFS and 1998 observation that a novel use for an IBE scheme can provide a generic solution to NIFS, and the arrival in 2001 of the first efficient / sensible trapdoor steepness (*) IBE with the introduction of the Weil Pairing problem by Dan Boneh and Matt Franklin described here http://en.wikipedia.org/wiki/Boneh%E2%80%93Franklin_scheme.

Greg summarized IBE as follows on IRC:


Basically as Greg said your public key is your address (an email address, a block hash, whatever is convenient and unique) and from that and the master public key of the IBE server, the server can compute a private key corresponding to that.  The master public is usually considered to be a system-wide domain parameter.   Naturally enough because a side effect of this is that the IBE server can decrypt everyones email people were never too excited about the prospect.

However my 1998 NIFS observation is by acting as your own IBE server (each user creates their own master public server key) they can create a sequence (NIFS) or set (bitcoin reusable address) of public keys with interesting and publicly derivable properties!

It is my conclusion from 1996 that to solve this with DL directly at least in the NIFS case appears to be not possible.


So basically the reusable address becomes an IBE public key, the existing public derivation via DH or EC Elgamal/ECIES or whatever variant (bytecoins, mine, Peter Todd/Amir Taaki's) arrives at a factor that can be recovered.  So with my variant (random sender generated multiplication factor encrypted with ECIES) you could encrypt the factor with a pub=IBE-extract(master pub, id=previous block hash) using the previous block hash as the "identity" and the users own self-owned IBE "server". 

For Bytecoin & Peter Todd/Amir Taaki EC DH version using input or auxilliary addresses to save space its not even necessary to send the factor, its already sent.  So then you send a separate message to do with secure delegatable filtering, a more secure/more space efficient bloom filter/prefix replacement, and this is a more flexible structure.

So the secure delegatable filter is you separately add an encrypted bloom bait Greg suggested (eg 1byte prefix communicated with public address.)  And you can even combine that with Greg's extended bloom bait above to add anonymity set within the block.

Consequently you can now securely and very network/space efficiently securely delegate searching a block by computing the private key for the IBE pub key that any sender would use for that block, and sending it as a query to a random (or node-capture defended random selected node).  The node can decrypt the encrypted bloom baits with it, but remains powerless to correlate with bloom baits to other payments received by the same user in bother blocks.

(In practice you might need an epoch not block or overlapping test because the user does not have full assurance of their tx ending up in the pending block).

About weil pairing, and new hardness crypto risk, this is also the hardness assumption under some ZK-SNARKs as I think used in zerocash, and while ZK-SNARK introduces its own complexity/crypto system risk on top; in my view weil pairing is slightly lower assurance/review not so widely used relative to EC DL problem.  Anyway the interesting thing to say about that is in the event this scheme got broken in the future it falls back to the scheme that is being proposed using prefix.  Ie its no worse than that from linkability and likely would retain some cost even if broken-- asymmetric crypto breaks are usually somewhat gradual.

This looks more expensive and non-indexable though I didnt look to see if there is any ciphertext only or batch precomputation that could be squeezed out of it.

Obviously its more CPU intensive and some eg fee mechanism to prevent node DoS could be nice, but it seems to demonstrate a proof by existence that it is possible to do better.


Finally I think it maybe within possibility to do further than this because it is not technically necessary to delegate decryption, only to delegate filtering, which can be a simpler requirement.

Adam

(*) There was an earlier scheme by Maurer et al if I recall, but to get a 1024-bit security margin you had to perform a discrete log attack on a 512-bit prime, so the key generation cost was immense, hence "sensible trapdoor steepness" thats very shallow in tems of work difference between setup cost and crypto system strength.