From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1W9tAI-0001oJ-5M for bitcoin-development@lists.sourceforge.net; Sun, 02 Feb 2014 09:16:34 +0000 Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of taplink.co designates 50.117.27.232 as permitted sender) client-ip=50.117.27.232; envelope-from=jeremy@taplink.co; helo=mail.taplink.co; Received: from mail.taplink.co ([50.117.27.232]) by sog-mx-4.v43.ch3.sourceforge.com with smtp (Exim 4.76) id 1W9tAH-0006W9-7x for bitcoin-development@lists.sourceforge.net; Sun, 02 Feb 2014 09:16:34 +0000 Received: from laptop-air ([192.168.168.135]) by mail.taplink.co ; Sun, 2 Feb 2014 01:16:43 -0800 Content-Type: text/plain; charset=utf-8; format=flowed; delsp=yes To: "Adam Back" , "Peter Todd" References: <20140124090218.GA15398@savin> <20140124154235.GA3741@netbook.cypherspace.org> <20140124161330.GA31233@petertodd.org> <20140125161901.GA17457@netbook.cypherspace.org> <20140202023651.GA18666@savin> Date: Sun, 02 Feb 2014 01:16:20 -0800 MIME-Version: 1.0 Content-Transfer-Encoding: Quoted-Printable From: "Jeremy Spilman" Organization: TapLink Message-ID: In-Reply-To: <20140202023651.GA18666@savin> User-Agent: Opera Mail/1.0 (Win32) oclient: 192.168.168.135#jeremy@taplink.co#465 X-Spam-Score: -2.1 (--) 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 -0.5 RP_MATCHES_RCVD Envelope sender domain matches handover relay domain -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-Headers-End: 1W9tAH-0006W9-7x 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 09:16:34 -0000 > > Consequently you can now securely and very network/space efficiently > securely delegate searching a block by computing the private key for t= he > IBE pub key that any sender would use for that block, and sending it a= s > 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. > I'm not sure I've fully wrapped my head around it. d/Q - Identity key E - Generate an epoch-pubkey: E =3D Q * H1(epoch) r/P - Ephemeral privkey/pubkey, or discoverable from inputs S =3D r * K - Shared secret (ECDE) Payer derives an encryption key H(S), and encrypts M, which is a 1 byte = = bloom bait. For each epoch, payee generates e =3D d * H1(epoch) and provides the key= to = a full node for monitoring. So you are providing a per-block or per-epoc= h = private key, along with the block ID or epoch ID that the key correspond= s = to. The full node then uses this privkey to decrypt the same byte in all the= = transactions in that epoch/block which match the expected layout/templat= e, = e.g. given a certain length OP_RETURN, pull the specific byte and decryp= t. This decrypted byte is then in turn used as bloom bait which may or may = = not cause the transaction to be sent back to the SPV client. Am I right in saying the full node has no idea if decryption is = 'succeeding' it just feeds the resultant bait into the bloom filter and = = the transaction may match or not? So we do get some level of repudiation= = by the SPV client -- the server doesn't know exactly which transactions = = belong to the SPV client. The bloom bait specified in the reusable address is still making the = bandwidth/privacy trade-off, it just doesn't become public information, = = because it's protected by another factor? What encryption scheme is being used here? -=3D-=3D-=3D-=3D=3D Another approach (inspired by IBE) which narrows the discoverability of = = transactions to the nodes that your SPV client is actually communicating= = with, for the specific blocks/epochs that you specify, would be to use = PEKS. PEKS(Q, W) for a public key Q and a keyword W produces a searchable = encryption of the word W. The payee holding 'd' (privkey for Q) can create a trapdoor which allows= a = server to search for transactions with W, where the searching party only= = knows if a match is found or not. Payer: d/Q - Longstanding / identity privkey/pubkey r/P - Ephemeral privkey/pubkey, or discoverable from inputs W - Searchable Keyword H1 - Hash function, {0, 1} =E2=88=97 =E2=86=92 G1 H2 - Hash function, G2 =E2=86=92 {0, 1}p Secret, as usual per ECDH: S =3D r * Q For payer to create the searchable encryption of W for Q, called 'Sw': Sw =3D H2(e(H1(W), S)) OP_RETURN P, Sw For payee to search for a given 'W', payee calculates a trapdoor 'Tw': Tw =3D d * H1(W) For a searcher, given a Trapdoor (Tw), check each Transaction (P, Sw): H2(e(Tw, P)) =3D=3D? Sw If the values match, the keyword matches Without getting into the concepts of e(g,g) and binomial pairing, I thin= k = of it this way: Sw =3D H2(r * Q * H1(W)), but recall: rQ =3D=3D dP, so... =3D H2(d * P * H1(W)), which can be written =3D H2(d * H1(W) * P) Severs finds all transactions with 'P' on relevant parts of the = blockchain, multiplies by the provided trapdoor 'Tw', applies 'H2', and = = checks for a matching 'Sw' in the transaction; Tw =3D d * H1(W) Sw =3D H2(Tw * P) H2(d * H1(W) * P) PEKS is vulnerable to an offline keyword guessing attack, where you can = = discover the value of the keyword being searched, if the keyword is low = = entropy. The server/attacker can figure out the value of W, but they can= 't = generate their own trapdoors to search for other keywords. But in this case, the 'keyword' can simply be the block ID / epoch ID = itself, not a secret value at all. In other words, the server can only = search for your transactions within the blocks/epochs that you specify. Using blockID/epochID as W, this would allow a server to find all = transactions belonging to the payer for that blockID / epochID. The SPV = = client would simply provide the trapdoor for each block/epoch to be = searched. There are extensions to PEKS which provide for 'fuzzy' matching but they= = are 'fuzzy' within the scope of Q, not across different Q, so that doesn= 't = help provide any repudiation. So I see this as only slightly improving = Peter's original proposal of providing 'Q' to the searcher, but if you = want repudiation, not as good as Adam's solution. Perfunctory disclaimer... Hopefully this is close to correct, but please= = don't anyone actually try to implement this! Thanks, Jeremy