From: Weikeng Chen <weikeng.chen@l2iterative•com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Re: SwiftSync - smarter synchronization with hints
Date: Sat, 3 May 2025 06:53:25 -0700 (PDT) [thread overview]
Message-ID: <9f9f0b4d-98b0-4e41-a1c3-903ee05da462n@googlegroups.com> (raw)
In-Reply-To: <fbf06c5b-57b6-4615-99bb-3a7ea31ebf22n@googlegroups.com>
[-- Attachment #1.1: Type: text/plain, Size: 2942 bytes --]
I want to add a footnote that, there could be a security complication for
either using SHA-256 or AES:
for this to be secure:
hash(UTXO_A||salt) + hash(UTXO_B||salt) - hash(UTXO_C||salt) -
hash(UTXO_D||salt) == 0
either:
- using a regular hash or AES_k, which should work in the same way, but
salt/AES key needs to have sufficient security and only known by trusted
parties (e.g., the user who is computing the sum). aka, the hash sum would
be the user's own bookkeeper, and other people should not trust that result.
or:
- using a significantly longer hash function, although it should still be
performant enough. A paper from Facebook "Securing Update Propagation with
Homomorphic Hashing" has cited that:
> AdHash initially received the most attention by several works which aimed
to implement the construction [SY98, CL99, GSC01], each using a 128-bit or
256-bit modulus. However, Wagner [Wag02] later showed an attack on the
generalized birthday problem which could be used to find collisions for
AdHash on an n-bit modulus in time O(2^{2\sqrt{n})), and that the AdHash
modulus needs to be greater than 1600 bits long to provide 80-bit security.
Lyubashevsky [Lyu05] and Shallue [Sha08] showed how to solve the Random
Modular Subset Sum problem (essentially equivalent to finding collisions in
AdHash) in time O(2^{n^\epsilon}) for any \epsilon < 1, which indicates
that AdHash requires several more orders of magnitude larger of a modulus
just to provide 80-bit security.
On Saturday, May 3, 2025 at 8:07:54 PM UTC+8 Greg Maxwell wrote:
> On Saturday, May 3, 2025 at 11:55:28 AM UTC Sanket Kanjalkar wrote:
>
> > hash(UTXO_A||salt) + hash(UTXO_B||salt) - hash(UTXO_C||salt) -
> hash(UTXO_D||salt) == 0 (proving (A==C && B==D) || (A==D && B==C))
>
> What if instead of hash we encrypt with AES and modular add/subs? I cannot
> prove it; but I also don't see a clear way this is broken.
>
> 1. Sample random symmetric key `k`
> 2. Instead of above; AES_k(UTXO_A) + AES_k(UTXO_B) - AES_k(UTXO_C) -
> AES(UTXO_D) == 0 => (proving (A==C && B==D) || (A==D && B==C))?
>
>
> AES in CTR mode is, I'm not sure about other modes? Obviously CTR mode
> would be unsuitable! (I mean sure modular add/sub and xor are different
> operations but they are quite close). I think that in many modes the
> collision resistance would have to at least be restricted by the birthday
> bound with the small block size. I think CMC might be needed to avoid that
> sort of issue.
>
>
>
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/9f9f0b4d-98b0-4e41-a1c3-903ee05da462n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 3765 bytes --]
prev parent reply other threads:[~2025-05-03 14:26 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-04-09 10:10 [bitcoindev] " Ruben Somsen
2025-05-02 6:47 ` [bitcoindev] " Greg Maxwell
2025-05-02 10:59 ` Ruben Somsen
2025-05-02 13:38 ` Saint Wenhao
2025-05-02 16:07 ` Greg Maxwell
2025-05-02 19:15 ` Saint Wenhao
2025-05-02 20:23 ` Sanket Kanjalkar
2025-05-03 12:02 ` Greg Maxwell
2025-05-03 13:42 ` Ruben Somsen
2025-05-03 13:57 ` Greg Maxwell
2025-05-03 14:36 ` Greg Maxwell
2025-05-03 14:55 ` Ruben Somsen
2025-05-03 15:54 ` Greg Maxwell
2025-05-03 16:24 ` Ruben Somsen
2025-05-03 13:53 ` Weikeng Chen [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=9f9f0b4d-98b0-4e41-a1c3-903ee05da462n@googlegroups.com \
--to=weikeng.chen@l2iterative$(echo .)com \
--cc=bitcoindev@googlegroups.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox