From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1W9veV-0007T2-6t for bitcoin-development@lists.sourceforge.net; Sun, 02 Feb 2014 11:55:55 +0000 Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of petertodd.org designates 62.13.149.56 as permitted sender) client-ip=62.13.149.56; envelope-from=pete@petertodd.org; helo=outmail149056.authsmtp.com; Received: from outmail149056.authsmtp.com ([62.13.149.56]) by sog-mx-1.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1W9veT-0000Lw-46 for bitcoin-development@lists.sourceforge.net; Sun, 02 Feb 2014 11:55:55 +0000 Received: from mail-c237.authsmtp.com (mail-c237.authsmtp.com [62.13.128.237]) by punt17.authsmtp.com (8.14.2/8.14.2/) with ESMTP id s12Btgk9059552; Sun, 2 Feb 2014 11:55:42 GMT Received: from savin (76-10-178-109.dsl.teksavvy.com [76.10.178.109]) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id s12BtcHs066917 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Sun, 2 Feb 2014 11:55:40 GMT Date: Sun, 2 Feb 2014 06:55:31 -0500 From: Peter Todd To: Adam Back Message-ID: <20140202115531.GA22375@savin> References: <20140124090218.GA15398@savin> <20140124154235.GA3741@netbook.cypherspace.org> <20140124161330.GA31233@petertodd.org> <20140125161901.GA17457@netbook.cypherspace.org> <20140202023651.GA18666@savin> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="vkogqOf2sHV7VnPd" Content-Disposition: inline In-Reply-To: <20140202023651.GA18666@savin> User-Agent: Mutt/1.5.21 (2010-09-15) X-Server-Quench: f06bc6c3-8c00-11e3-94fa-002590a135d3 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR aAdMdgAUHlAWAgsB AmIbWlVeVVh7XWI7 bAxPbAVDY01GQQRq WVdMSlVNFUsrAB5z Qk1mERl0cQxHfzBx bUJnXT4NXEIoJkAu QVNcRm0GeGZhPWMC WUQOJh5UcAFPdx8U a1N6AHBDAzANdhES HhM4ODE3eDlSNilR RRkIIFQOdA5LBSY1 TB1DVTghE0wORig1 M1Q8J0MHFUwVPw07 PVc7EUwZOlcNBwxa fQlVCS5DJl8ODwsB IEsaZ0NMWBdUQDsU DBoyagVFHydbUC5V TEJJRwsCEDhIS2gg X-Authentic-SMTP: 61633532353630.1024:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 76.10.178.109/587 X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system. X-Spam-Score: -1.5 (-) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain -0.0 SPF_PASS SPF: sender matches SPF record X-Headers-End: 1W9veT-0000Lw-46 Cc: Bitcoin Development Subject: Re: [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: Sun, 02 Feb 2014 11:55:55 -0000 --vkogqOf2sHV7VnPd Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable > On Sat, Jan 25, 2014 at 05:19:01PM +0100, Adam Back wrote: > [quote author=3Dadam3us link=3Dtopic=3D431756.msg4729682#msg4729682 > date=3D1390660452] > So have been talking with Greg Maxwell, Peter Todd, Jeremy Spillman, > Mike Hearn, Bytecoin and others about reusable addresses. >=20 > There is a summary of the situation here > http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg= 03792.html > and I had posed th question of whether it was possible to do better at > all with Peter Todd: You're explanation is a bit long-winded, so I'll start with a simplified ECC-based version first and later explain how identity-based encryption applies to the problem; I have a feeling not many non-crypt-experts spent the time to figure out what you're talking about; do check if what I've written below is correct: So Alice wants to pay Bob, who is bandwidth constrained and frequently offline. Meanwhile Ivan has a full node, but can't really be trusted. Meanwhile Eve is busy trying to piece together everyones' financial details. Bob publicly publishes three pubkeys, Filter, Recover, and Spend, along with a short n-bit prefix p. When Alice needs to pay Bob she creates a ephemeral keypair and uses ECDH *two* shared secrets, n_f and n_r, from Bob's Filter and Recover pubkeys respectively. She makes a transaction that pays Bob by deriving pubkey Spend_{n_f} from the Spend and n_r nonce. She also uses the Filter nonce and the prefix to derive a encrypted prefix p'=3Dn_f^p and puts that prefix and the cleartext ephemeral pubkey in the transaction as data. When Bob wants to find that transaction he gives the prefix and Filter secret key to Ivan, who then scans the blockchain. For every transaction he computes n_f=3DECDH(Filter_sec, Ephm_pub), extracts the encrypted prefix p' from the transaction, and checks if p'=3Dn_f^p If so he gives that transaction to Bob who can then use his Recover secret key to check if the transaction was in fact for him. (note how the prefix can actually always be simply a given length of zeros) Because Bob's prefix is short Ivan only learns probabalistic information about what transactions might be Bob's. Eve doesn't know the Filter secret key, and thus learns nothing at all from the blockchain data. On the other hand after getting the key once Ivan can forever after get that probability information about what transactions might be Bob's. What we'd really like is for there to be some way for Alice to derive a time-limited Filter pubkey from some public random beacon with value R_i, such as the Bitcoin blockchain, such that each defined time interval uses a different key. Bob would then only give Ivan the secret key(s) for the time interval(s) in question. Unfortunately ECDSA doesn't have a way to do this. The closest thing available is BIP32-style key derivation, however it has the property that given a derived secret key and known master pubkey the master secret key can be derived. Thus Ivan can simply try every public Filter key/epoch tweak he knows about until he finds Q,d' st. (d+d')G=3DQ+d'G =46rom that he can recover d, reducing the security to where we started. (or put another way, Ivan can store every (d+d') secret key he is asked to search with, and test it against every public key he learns about later) Identity-based cryptograhy however can do that. Bob publishes a (single) master public key, and anyone can derive public keys based on that master key and the random beacon value R_i. Bob can then derive the corresponding secret key, but unlike with ECDSA, that secret key *can't* be used to derive the master private key. Having said that, it can of course be linked to that key, so every query that Bob makes gives Ivan some knowledge about what transactions might be in Bob's wallet. Problem is, who the hell has a production-ready Weil pairing library kicking around? (is this read? http://crypto.stanford.edu/pbc/) Also, Weil pairing is not yet trustworthy: < gmaxwell> (IMO thats how we should be using pairing in cryptosystems: for lower value applications, and solving things that can't be solved any other way) --=20 'peter'[:-1]@petertodd.org 000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0 --vkogqOf2sHV7VnPd Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.14 (GNU/Linux) iQGrBAEBCACVBQJS7jIzXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw MDAwMDAwMDAwMDAwMDA3NTgyOWY2MTY5Yzc5ZDdkNWFhYTIwYmZhOGRhNmU5ZWRi MjM5M2M0Zjg2NjJiYTAvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0 ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkftiCgf+I1LPJz3csEsWK5MnMHIbg5fv T1+oD6gPCPwub8J3p6nLQ+x8bDis/2NU/I89irzKv1Z95bhPp7fbU/i/4DBaUQq3 4zHzBieMmE7VZKxGPg8hSApgZPYduhAoXPED8maK0Jf+0DH9aejGIC5WAcOWNN6B xgRBssUCpcDicHJL1ZdHz58Qa2TEsGtnyFdwXE9LQAByxZVzojuKtZuwIBOLOc40 pRX4CMXHpgNsphpA+xC9bno6pfKxBtVx+Bx5LOTPP+pLKoXZ6A/exCXpbfiUYGy+ nvnvrzRYgcdxvfQ216EvmFav8KI7X4ZI5Wt0pNlGIz9X8fXOvqizJ2P89Kiddg== =478Q -----END PGP SIGNATURE----- --vkogqOf2sHV7VnPd--