Bitcoin Forum
February 28, 2015, 05:27:10 PM *
News: Latest stable version of Bitcoin Core: 0.10.0 [Torrent] (New!)
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: (space) efficient reusable addr via weil pairing IBE  (Read 2764 times)
adam3us
Sr. Member
****
expert
Offline Offline

Activity: 388


in bitcoin we trust


View Profile WWW

Ignore
January 25, 2014, 02:34:12 PM
 #1

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 from: 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

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)

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 secure delegatable filtering, a more secure/more space efficient bloom filter/prefix replacement, and this is a more flexible structure.

So the secure delegatable filter is you separately add an encrypted bloom bait Greg suggested (eg 1byte prefix communicated with public address.)  And you can even combine that with Greg's extended bloom bait above to add anonymity set within the block.

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.

(In practice you might need an epoch not block or overlapping test because the user does not have full assurance of their tx ending up in the pending block).

About weil pairing, and new hardness crypto risk, this is also the hardness assumption under some ZK-SNARKs as I think used in zerocash, and while ZK-SNARK introduces its own complexity/crypto system risk on top; in my view weil pairing is slightly lower assurance/review not so widely used relative to EC DL problem.  Anyway the interesting thing to say about that is in the event this scheme got broken in the future it falls back to the scheme that is being proposed using prefix.  Ie its no worse than that from linkability and likely would retain some cost even if broken-- asymmetric crypto breaks are usually somewhat gradual.

This looks more expensive and non-indexable though I didnt look to see if there is any ciphertext only or batch precomputation that could be squeezed out of it.

Obviously its more CPU intensive and some eg fee mechanism to prevent node DoS could be nice, but it seems to demonstrate a proof by existence that it is possible to do better.


Finally 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.

Adam

(*) There was an earlier scheme by Maurer et al if I recall, but to get a 1024-bit security margin you had to perform a discrete log attack on a 512-bit prime, so the key generation cost was immense, hence "sensible trapdoor steepness" thats very shallow in tems of work difference between setup cost and crypto system strength.

hashcash, committed transactions, homomorphic values, blind kdf; researching decentralization, scalability and fungibility/anonymity
1425144430
Hero Member
*
Offline Offline

Posts: 1425144430

View Profile Personal Message (Offline)

Ignore
1425144430
Reply with quote  #2

1425144430
Report to moderator
Primedice.com The Most Popular Bitcoin Gambling GameNo, we still don't accept ___coin.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1425144430
Hero Member
*
Offline Offline

Posts: 1425144430

View Profile Personal Message (Offline)

Ignore
1425144430
Reply with quote  #2

1425144430
Report to moderator
1425144430
Hero Member
*
Offline Offline

Posts: 1425144430

View Profile Personal Message (Offline)

Ignore
1425144430
Reply with quote  #2

1425144430
Report to moderator
1425144430
Hero Member
*
Offline Offline

Posts: 1425144430

View Profile Personal Message (Offline)

Ignore
1425144430
Reply with quote  #2

1425144430
Report to moderator
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1470


View Profile

Ignore
January 25, 2014, 03:47:47 PM
 #2

You would need epochs for another reason. Recall that with Bloom filtering the remote node is asked for blocks in batches of 500 at a time and the remote end handles updating the filter as transactions are matched. This is to avoid the performance hit of a network round-trip for every block.
adam3us
Sr. Member
****
expert
Offline Offline

Activity: 388


in bitcoin we trust


View Profile WWW

Ignore
January 25, 2014, 05:05:42 PM
 #3

You would need epochs for another reason. Recall that with Bloom filtering the remote node is asked for blocks in batches of 500 at a time and the remote end handles updating the filter as transactions are matched. This is to avoid the performance hit of a network round-trip for every block.

I see I dont think I realized that aspect of how bloom query works.  So you then with IBE-based filtering could send multiple keys, one for each block; but you are implicitly linked by being in one query, so you'd just as well mark your key with your preferred epoch size and sender uses epoch number in the query.

I think Greg is pointing out on IRC that by having a fairly small epoch you can choose later to go down to that epoch size or scale up by sending multiple epoch keys in a batch, a privacy/network round-trip trade off.

Re my other problem with epochs ("In practice you might need an epoch not block or overlapping test because the user does not have full assurance of their tx ending up in the pending block") I think that maybe fixable, if the blocknumber is chosen by the sender, and communicated in enough bits to be mostly unambiguous in the message.  Then the node can index them by sen block num and no ambiguity.

It could be that another way to partly obscure ownership of queries would be to relay queries and responses and mix other peoples queries with your own in a batch, however as we are considering the SPV client case relaying other peoples queries seems hard to gather query traffic on demand and to use more bandwidth than it saves relative just issuing smaller batches.

You could have relaying in the network eg using the embedded Tor but waiting for queries to mix with adds latency, and suffers flood attacks on mix-nets (send fake encrypted query traffic to flush out a tx, that has no-anon set vs the person doing the flooding who can distinguish their own queries).

Adam

hashcash, committed transactions, homomorphic values, blind kdf; researching decentralization, scalability and fungibility/anonymity
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!