Replace the RSA-based encryption methodology with a simplified ECIES using BN254 (aka alt_bn128) curve, which has precompiles on Ethereum.
Rationale
The two main issues with RSA are:
It may be possible to come up with a combination of (amountOut, seed) that matches an encrypted bid, but that is different than what the user submitted. This should be very difficult, but we have no way to detect it.
It also turns out that submitting decrypts to validate encryption opens a door to two issues both of which can't be solved at once. If a user submits an encrypted amount that doesn't follow the RSAOAEP specification, then it can't be decrypted. If you catch these errors, you allow the submitter to censor other bids by forcing them to fail by providing the wrong inputs and skipping them. If you don't catch the error, a bidder can DoS the bid settlement by submitting a bid that can't be decrypted (i.e. cannot provide values that will successfully pass the check the decryption check in the contract). This can be solved by decrypting the messages directly on-chain, but it is too gas intensive to do so (upwards of 100k gas per bid).
Design
Idea: use a simplified version of the Elliptic Curve Integrated Encryption Scheme (ECIES) where the auction creator provides a public key on the AltBN128 curve. Bidders create a shared key off-chain and conceal it using the public key of the auction. To settle, the private key for the auction can be provided and the encrypted amounts out can be decrypted directly using the AltBN128 ecMul precompile for ~6,000 gas. We use a simple, hash-based key derivation function and XOR encryption, which are weak by themselves, but are likely sufficient behind the EC public key cryptography.
Oighty
commented
6 months ago
Objective
Replace the RSA-based encryption methodology with a simplified ECIES using BN254 (aka alt_bn128) curve, which has precompiles on Ethereum.
Rationale
The two main issues with RSA are:
Design
Idea: use a simplified version of the Elliptic Curve Integrated Encryption Scheme (ECIES) where the auction creator provides a public key on the AltBN128 curve. Bidders create a shared key off-chain and conceal it using the public key of the auction. To settle, the private key for the auction can be provided and the encrypted amounts out can be decrypted directly using the AltBN128 ecMul precompile for ~6,000 gas. We use a simple, hash-based key derivation function and XOR encryption, which are weak by themselves, but are likely sufficient behind the EC public key cryptography.