Re: [Bitcoin-development] (space) efficient reusable addr via weil pairing IBE (Re: Bait for reusable addresses)
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.
I'm not sure I've fully wrapped my head around it.
d/Q- Identity key
E - Generate an epoch-pubkey: E = Q * H1(epoch)
r/P- Ephemeral privkey/pubkey, or discoverable from inputs
S = 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 = d * H1(epoch) and provides the key to
a full node for monitoring. So you are providing a per-block or per-epoch
private key, along with the block ID or epoch ID that the key corresponds
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/template,
e.g. given a certain length OP_RETURN, pull the specific byte and decrypt.
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?
-=-=-=-==
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} ∗ → G1
H2- Hash function, G2 → {0, 1}p
Secret, as usual per ECDH:
S = r * Q
For payer to create the searchable encryption of W for Q, called 'Sw':
Sw = H2(e(H1(W), S))
OP_RETURN P, Sw
For payee to search for a given 'W', payee calculates a trapdoor 'Tw':
Tw = d * H1(W)
For a searcher, given a Trapdoor (Tw), check each Transaction (P, Sw):
H2(e(Tw, P)) ==? Sw
If the values match, the keyword matches
Without getting into the concepts of e(g,g) and binomial pairing, I think
of it this way:
Sw = H2(r * Q * H1(W)), but recall: rQ == dP, so...
= H2(d * P * H1(W)), which can be written
= 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 = d * H1(W)
Sw = 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
--
WatchGuard Dimension instantly turns raw network data into actionable
security intelligence. It gives you real-time visual feedback on key
Re: [Bitcoin-development] (space) efficient reusable addr via weil pairing IBE (Re: Bait for reusable addresses)
On Sat, Jan 25, 2014 at 05:19:01PM +0100, Adam Back wrote:
[quote author=adam3us link=topic=431756.msg4729682#msg4729682
date=1390660452]
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/bitcoin-development@lists.sourceforge.net/msg03792.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'=n_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=ECDH(Filter_sec, Ephm_pub), extracts the encrypted
prefix p' from the transaction, and checks if p'=n_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=Q+d'G
From 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)
--
'peter'[:-1]@petertodd.org
75829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0
signature.asc
Description: Digital signature
--
WatchGuard Dimension instantly turns raw network data into actionable
security intelligence. It gives you real-time visual feedback on key
security issues and trends. Skip the complicated setup - simply import
a virtual appliance and go from zero to informed in seconds.
http://pubads.g.doubleclick.net/gampad/clk?id=123612991iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] (space) efficient reusable addr via weil pairing IBE (Re: Bait for reusable addresses)
On Sun, Feb 02, 2014 at 01:16:20AM -0800, Jeremy Spilman wrote: 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. I'm not sure I've fully wrapped my head around it. d/Q- Identity key E - Generate an epoch-pubkey: E = Q * H1(epoch) r/P- Ephemeral privkey/pubkey, or discoverable from inputs S = r * K - Shared secret (ECDE) There needs to be two separate payor pubkeys, which I called elsewhere the Filter and Recover pubkeys - the latter I think corresponds to what you meant by identity key. From those two pubkeys two separate shared secrets are derived. The key idea is that you can encrypt a short string of zeros with the Filter pubkey using ECDH and place the resulting filter bait in the transaction. This lets the payor give the secret key corresponding to that pubkey to a semi-trusted third party. That third party can then trial decrypt all filter bait seen in transactions in the blockchain, and every time the decrypted string has a sufficient number of zeros it's considered a filter pass and the transaction is given to the payor. For n zero bits one in 2^n transactions will match at random, which sets your false positive rate. Basically think of it as a way to outsource the work required for zero-prefix stealth addresses, but with (less) of a sacrifice of anonymity compared to just giving the third-party your recovery pubkey. Identity-based encryption only comes into it because it's nice to be able to further limit what transactions the server knows about to specific time intervals rather than forver into the future. Interestingly both schemes can be used at once - a short public prefix combined with a second private filter. What's interesting there is that the public prefix can do a first-pass filtering, with the second private filter relatively long but still providing plausible deniability - you can always claim 100% of the matching transactions were false positives because you didn't receive any funds! 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/template, e.g. given a certain length OP_RETURN, pull the specific byte and decrypt. 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. There's no bloom filters involved; as I said before bloom bait is a misleading name. Filter bait is a better term given it's a generic concept. What encryption scheme is being used here? XOR with the ECDH-calculated nonce is fine. (run the nonce though a hash function first) -- 'peter'[:-1]@petertodd.org 75829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0 signature.asc Description: Digital signature -- WatchGuard Dimension instantly turns raw network data into actionable security intelligence. It gives you real-time visual feedback on key security issues and trends. Skip the complicated setup - simply import a virtual appliance and go from zero to informed in seconds. http://pubads.g.doubleclick.net/gampad/clk?id=123612991iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] (space) efficient reusable addr via weil pairing IBE (Re: Bait for reusable addresses)
I think you Peter Jeremy figured it out - dont disagree with the explanation details. And it seems better explained between the two posts than I did. I think Peter is right that you do not need an explicit prefix, the prefix after decryption can be a chosen number of leading 0s and this gives a tunable amount of false positives. You already have privacy becaue the query is only revealed to the semi-trusted full node, and its query scope is limited to one or a chosen batch of blocks. But you can if desired add additional ambiguity as Peter described by reducing the number of bits of 0 in the decrypted block. There is no need for matching a specific prefix as its already a recipient specific calculation. (It means the actual encrypted value where it is chosen would have to mimic false positives: random with n-bits of trailing 0s and expected probability distribution). It should be compatible for combining with sharding or public prefixes, as Peter mentioned but for short public prefixes those still has some (reduced) blockchain ledger logged possibility to reduce anonymity set when combined with flow analysis. Maybe you could vary a public prefix per block. Eg the public prefix for a given user is the LSBits of the per block IBE derived pubic key for a given user. I am not sure if that helps or hinders. Maybe it hurts anonymity set because the analyst (Eve) is given multiple chances over time to exclude an analysed flow candidate. It would desirable to find a non-IBE way to do this. (And more computationally efficient / precomputable / indexable) Or you could use different address types depending on the circumstance: one-use, stealth, or IBE. Kind of difficult to automate that (to know what the user is planning to do with it) and avoid user confusion. Clearly users are quite confused and the convenient and understandable thing is to have a (safely) reusable address. Adam On Sun, Feb 02, 2014 at 07:26:10AM -0500, Peter Todd wrote: On Sun, Feb 02, 2014 at 01:16:20AM -0800, Jeremy Spilman wrote: 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. I'm not sure I've fully wrapped my head around it. d/Q- Identity key E - Generate an epoch-pubkey: E = Q * H1(epoch) r/P- Ephemeral privkey/pubkey, or discoverable from inputs S = r * K - Shared secret (ECDE) There needs to be two separate payor pubkeys, which I called elsewhere the Filter and Recover pubkeys - the latter I think corresponds to what you meant by identity key. From those two pubkeys two separate shared secrets are derived. The key idea is that you can encrypt a short string of zeros with the Filter pubkey using ECDH and place the resulting filter bait in the transaction. This lets the payor give the secret key corresponding to that pubkey to a semi-trusted third party. That third party can then trial decrypt all filter bait seen in transactions in the blockchain, and every time the decrypted string has a sufficient number of zeros it's considered a filter pass and the transaction is given to the payor. For n zero bits one in 2^n transactions will match at random, which sets your false positive rate. Basically think of it as a way to outsource the work required for zero-prefix stealth addresses, but with (less) of a sacrifice of anonymity compared to just giving the third-party your recovery pubkey. Identity-based encryption only comes into it because it's nice to be able to further limit what transactions the server knows about to specific time intervals rather than forver into the future. Interestingly both schemes can be used at once - a short public prefix combined with a second private filter. What's interesting there is that the public prefix can do a first-pass filtering, with the second private filter relatively long but still providing plausible deniability - you can always claim 100% of the matching transactions were false positives because you didn't receive any funds! 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/template, e.g. given a certain length OP_RETURN, pull the specific byte and decrypt. 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. There's no bloom filters involved; as I said before bloom bait is a misleading name. Filter bait is a better term given it's a generic concept. What encryption scheme is being used here? XOR with the ECDH-calculated nonce is fine. (run the nonce
