From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1W75xY-0004xo-Th for bitcoin-development@lists.sourceforge.net; Sat, 25 Jan 2014 16:19:52 +0000 X-ACL-Warn: Received: from mout.perfora.net ([74.208.4.195]) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1W75xW-0002d8-RI for bitcoin-development@lists.sourceforge.net; Sat, 25 Jan 2014 16:19:52 +0000 Received: from netbook (c107-70.i07-27.onvol.net [92.251.107.70]) by mrelay.perfora.net (node=mrus3) with ESMTP (Nemesis) id 0Mhi8Z-1Vt12I2Yip-00N3hV; Sat, 25 Jan 2014 11:19:11 -0500 Received: by netbook (Postfix, from userid 1000) id 81F9A2E49B4; Sat, 25 Jan 2014 17:19:03 +0100 (CET) Received: by flare (hashcash-sendmail, from uid 1000); Sat, 25 Jan 2014 17:19:01 +0100 Date: Sat, 25 Jan 2014 17:19:01 +0100 From: Adam Back To: Peter Todd Message-ID: <20140125161901.GA17457@netbook.cypherspace.org> References: <20140124090218.GA15398@savin> <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) X-Hashcash: 1:20:140125:pete@petertodd.org::HGayDrfzr6j1K018:0000000000000000000 0000000000000000000000003JhZ X-Hashcash: 1:20:140125:mike@plan99.net::X8Ik9O7hmSw08ufb:000AV0 X-Hashcash: 1:20:140125:bitcoin-development@lists.sourceforge.net::mbcckeh1M+XKw HYO:000000000000000000006W6O X-Hashcash: 1:20:140125:adam@cypherspace.org::/+gkyODmqsTfUKau:00000000000000000 00000000000000000000000056NW X-Provags-ID: V02:K0:ym75vYfqyxdqAbSICtS6Pu9VREA7C0tTWCKFBrN9IKn mDlaCmukNACB77XShmc7n57uJ+azWR0JbzEsjrixCo77wgaDWy TFMCLW+KCgAErlBlq8i8JMyr53YVrt0jhpimziafBUxP9b6NZG ad15D0edCjHUdXHiQwx6MZAgP+ewzw1W37wcui6/sYx6s5qcIc /q+SBzemYolACCA3jTC9FjP8LUDUIV8BQEYSqTlinOX8Nf04Ll j6TXaHW+JKKjbTFKURCisSQa00QHqW+VOxstNey77j/EXphuzL 9dqIv2sh/kfwTmiuaRU3C3q6ODXp1AIay47Hp+wkjX5uK6PW9w Sios0qZIRxXm5ZVoOK2PQcRoyY191sJyRlxm/Mxbh X-Spam-Score: -0.0 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at http://www.dnswl.org/, no trust [74.208.4.195 listed in list.dnswl.org] -0.0 SPF_HELO_PASS SPF: HELO matches SPF record X-Headers-End: 1W75xW-0002d8-RI Cc: Bitcoin Development Subject: [Bitcoin-development] (space) efficient reusable addr via weil pairing IBE (Re: Bait for reusable addresses) X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 25 Jan 2014 16:19:53 -0000 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.