Date: Sat, 25 Jan 2014 17:19:01 +0100
From: Adam Back <adam@cypherspace.org>
To: Peter Todd <pete@petertodd.org>
Message-ID: <20140125161901.GA17457@netbook.cypherspace.org>
References: <CAAS2fgQmsxjkQFSiCdeMoVMaqq5720KpUpdkKZOE+XytHsWw0w@mail.gmail.com>
	<20140124090218.GA15398@savin>
	<CANEZrP0MnXr4xjaMPg7v7vTiDQr-y7esvEBE=xk=Y0BUGXak9A@mail.gmail.com>
	<20140124154235.GA3741@netbook.cypherspace.org>
	<20140124161330.GA31233@petertodd.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Disposition: inline
In-Reply-To: <20140124161330.GA31233@petertodd.org>
User-Agent: Mutt/1.5.21 (2010-09-15)
Cc: Bitcoin Development <bitcoin-development@lists.sourceforge.net>
Subject: [Bitcoin-development] (space) efficient reusable addr via weil
 pairing IBE (Re: Bait for reusable addresses)
Precedence: list

I think I figured out a proof of existance for a space efficient way to do
better than bloom filters/prefix/bloom-bait.  (Must have been dreaming on it
as I woke up with the idea following Peter's suggestion to try prove instead
if its possible or not:).

I wrote up the details here:

https://bitcointalk.org/index.php?topic=431756.new

In summary with a use of novel application of IBE (*) based on weil-pairing
so the recipient can send a delegation private key that is specific to the
block being queried.  It means the node that services the query has no
ability to correlate with queries in other blocks from the some user.  The
sender derives a pub=IBE-extract(master-pub, id=previous block hash).  The
above link has more explanation, links and costs/risks.

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 so there remains perhaps
(speculatively) a possibility to do it without introducing weil pairing
hardness problem or using eg I mentioned public key steganography or
something like that if there is anything similarly efficient but with more
widely used hardness assumptions.

Adam

(*) analogous to the way IBE is used as a building block for Non-Interactive
Forward Secrecy (NIFS)

On Fri, Jan 24, 2014 at 11:13:30AM -0500, Peter Todd wrote:
>On Fri, Jan 24, 2014 at 04:42:35PM +0100, Adam Back wrote:
>> Now while it would be clearly a very nice win if reusable addresses could
>> be made SPV-like in network characteristics and privacy, but we dont have
>> a plausible mechanism yet IMO.  [...]
>>
>> If we can find some efficient crypto to solve that last one, we could even
>> adopt them generally if it was efficient enough without needing interactive
>> one-use address release.
>
>Conversely, it'd be interesting if someone can dig up a proof showing
>that doing much better than Gregory's ambiguity tradeoff is impossible.