{"action":"created","issue":{"url":"https://api.github.com/repos/zcash/zcash/issues/792","repository_url":"https://api.github.com/repos/zcash/zcash","labels_url":"https://api.github.com/repos/zcash/zcash/issues/792/labels{/name}","comments_url":"https://api.github.com/repos/zcash/zcash/issues/792/comments","events_url":"https://api.github.com/repos/zcash/zcash/issues/792/events","html_url":"https://github.com/zcash/zcash/issues/792","id":141332161,"number":792,"title":"Write security proofs for nonstandard primitives","user":{"login":"defuse","id":4211072,"avatar_url":"https://avatars.githubusercontent.com/u/4211072?v=3","gravatar_id":"","url":"https://api.github.com/users/defuse","html_url":"https://github.com/defuse","followers_url":"https://api.github.com/users/defuse/followers","following_url":"https://api.github.com/users/defuse/following{/other_user}","gists_url":"https://api.github.com/users/defuse/gists{/gist_id}","starred_url":"https://api.github.com/users/defuse/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/defuse/subscriptions","organizations_url":"https://api.github.com/users/defuse/orgs","repos_url":"https://api.github.com/users/defuse/repos","events_url":"https://api.github.com/users/defuse/events{/privacy}","received_events_url":"https://api.github.com/users/defuse/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/zcash/zcash/labels/SECURITY","name":"SECURITY","color":"e01010"}],"state":"open","locked":false,"assignee":{"login":"daira","id":643204,"avatar_url":"https://avatars.githubusercontent.com/u/643204?v=3","gravatar_id":"","url":"https://api.github.com/users/daira","html_url":"https://github.com/daira","followers_url":"https://api.github.com/users/daira/followers","following_url":"https://api.github.com/users/daira/following{/other_user}","gists_url":"https://api.github.com/users/daira/gists{/gist_id}","starred_url":"https://api.github.com/users/daira/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/daira/subscriptions","organizations_url":"https://api.github.com/users/daira/orgs","repos_url":"https://api.github.com/users/daira/repos","events_url":"https://api.github.com/users/daira/events{/privacy}","received_events_url":"https://api.github.com/users/daira/received_events","type":"User","site_admin":false},"milestone":null,"comments":16,"created_at":"2016-03-16T16:47:58Z","updated_at":"2016-03-26T13:59:25Z","closed_at":null,"body":"Looking over the current `protocol.pdf`, we are using the following nonstandard primitives. We should prove all of them secure using reasonable assumptions about SHA256.\r\n\r\n- The four PRFs.\r\n- The fixed-depth merkle tree which uses the SHA256 compression function as the hash.\r\n- The way the coin commitment is computed.\r\n- The way h_{sig} is computed.\r\n- The way the key-private encryption works, which includes a KDF based on SHA256.\r\n\r\n[Edit by Daira: the KDF is now based on SHA-512.]"},"comment":{"url":"https://api.github.com/repos/zcash/zcash/issues/comments/201829854","html_url":"https://github.com/zcash/zcash/issues/792#issuecomment-201829854","issue_url":"https://api.github.com/repos/zcash/zcash/issues/792","id":201829854,"user":{"login":"daira","id":643204,"avatar_url":"https://avatars.githubusercontent.com/u/643204?v=3","gravatar_id":"","url":"https://api.github.com/users/daira","html_url":"https://github.com/daira","followers_url":"https://api.github.com/users/daira/followers","following_url":"https://api.github.com/users/daira/following{/other_user}","gists_url":"https://api.github.com/users/daira/gists{/gist_id}","starred_url":"https://api.github.com/users/daira/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/daira/subscriptions","organizations_url":"https://api.github.com/users/daira/orgs","repos_url":"https://api.github.com/users/daira/repos","events_url":"https://api.github.com/users/daira/events{/privacy}","received_events_url":"https://api.github.com/users/daira/received_events","type":"User","site_admin":false},"created_at":"2016-03-26T13:59:25Z","updated_at":"2016-03-26T13:59:25Z","body":"I'm happy about the security of the PRF and KDF now, but less so about the security of the commitment. Does anyone know of a proof that a Merkle-Damgård hash makes a secure (computationally binding and computationally hiding) commitment scheme given reasonable assumptions about the hash other than modeling it as a random oracle? (The proof that @defuse [mentioned](https://github.com/zcash/zcash/issues/792#issuecomment-197512482) models it such, and as he mentioned, has some deficiencies in its definitions.]\r\n\r\nI can only find this: [Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing](https://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC07/Halevi-Micali.pdf) which explains in section 1.3 why collision resistance is not sufficient to prove security of the scheme we're considering. I didn't expect it to be, but it's unclear precisely what property of the hash is needed, which makes me uneasy. The scheme they suggest instead is undesirably heavy for the SNARK, since it requires a UOWHF as well as two CRHF invocations. (Hmm, perhaps we could use Poly1305 for the UOWHF? That's very SNARK-efficient, but I'd rather avoid implementing more primitives for the SNARK if at all possible.)"}}