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
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: 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 One of the main reasons I post to the bitcoin-development mailing list rather than the forum is because the mailing list is archived by many different, independent, parties. The forum is not - as an example archive.org didn't have that URL until I manually told it to archive it. So I'm taking the liberty of reposting your two posts there below: [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: [quote author=adam3us on bitcoin-dev] 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. Close as we got was Greg's enhancement of my/your bloom bait/prefix concept to make multiple candidate baits to provide some ambiguity (still allows elimination, just slightly less of it). 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 [/quote] and Peter proposed also the related problem of proving something about that existence or not of a solution to that problem. I think I have a proof-of-concept solution that proves by example we can do better in space efficiency, linkability defense and non-interactivity than my bloom bait, Peter Todds related prefix; and Greg Maxwell's extended bloom bait described http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03705.html. So the idea is to use an IBE scheme as a building block in analogous way to my 1996 problem statement for NIFS and 1998 observation that a novel use for an IBE scheme can provide a generic solution to NIFS, and the arrival in 2001 of the first efficient / sensible trapdoor steepness (*) IBE with the introduction of the Weil Pairing problem by Dan Boneh and Matt Franklin described here http://en.wikipedia.org/wiki/Boneh%E2%80%93Franklin_scheme. Greg summarized IBE as follows on IRC: [quote] (for those who may) not be familar with IBE stuff: The idea is that the user has a master private key, which results in a master public key. Anyone can take a prior block hash and combine it with the master public key to get a session pubkey which could be used to encrypt a chaincode included in an OP_RETURN. Using the master private key the user can derrive the session private key, which can then be used to recognize transactions using the same session key. In IBE (identity based encryption) this is all used a bit differently: the master keys are held by a CA, and the session ID is your email address, and now anyone can make a public key for you— but you need the CA's help to get your private key) [/quote] Basically as Greg said your public key is your address (an email address, a block hash, whatever is convenient and unique) and from that and the master public key of the IBE server, the server can compute a private key corresponding to that. The master public is usually considered to be a system-wide domain parameter. Naturally enough because a side effect of this is that the IBE server can decrypt everyones email people were never too excited about the prospect. However my 1998 NIFS observation is by acting as your own IBE server (each user creates their own master public server key) they can create a sequence (NIFS) or set (bitcoin reusable address) of public keys with interesting and publicly derivable properties! It is my conclusion from 1996 that to solve this with DL directly at least in the NIFS case appears to be not possible. So basically the reusable address becomes an IBE public key, the existing public derivation via DH or EC Elgamal/ECIES or whatever variant (bytecoins, mine, Peter Todd/Amir Taaki's) arrives at a factor that can be recovered. So with my variant (random sender generated multiplication factor encrypted with ECIES) you could encrypt the factor with a pub=IBE-extract(master pub, id=previous block hash) using the previous block hash as the identity and the users own self-owned IBE server. For Bytecoin Peter Todd/Amir Taaki EC DH version using input or auxilliary addresses to save space its not even necessary to send the factor, its already sent. So then you send a separate message to do with
[Bitcoin-development] (space) efficient reusable addr via weil pairing IBE (Re: Bait for reusable addresses)
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. -- CenturyLink Cloud: The Leader in Enterprise Cloud Services. Learn Why More Businesses Are Choosing CenturyLink Cloud For Critical Workloads, Development Environments Everything In Between. Get a Quote or Start a Free Trial Today. http://pubads.g.doubleclick.net/gampad/clk?id=119420431iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
