2
$\begingroup$

A fan-in $2$ and fan-out $1$ Boolean circuit is a circuit consisting of $\operatorname{AND}$, $\operatorname{OR}$ and $\operatorname{NOT}$ gates where number of inputs to $\operatorname{AND}$ and $\operatorname{NOT}$ are constrained to be $2$ and number of output gates any of the gates can be connected to is $1$.

I am wondering if $\operatorname{SHA-256}$ is implemented as a multi-output (all hash bits computed by one circuit) fan-in $2$ Boolean circuit what would its depth be?

Can its depth be in the low $10$s while the number of gates could be in say range $10^6$ to $10^9$?

Direct sequential implementation of rounds would warrant a depth of at least $64$ since $\operatorname{SHA-256}$ employs $64$ rounds.

It has to be a clever optimized design.

$\endgroup$
11
  • $\begingroup$ Many definitions of fan-in 2 count NAND and NOR gates as depth 1. I even was taught to count AND and OR as depth 2 (on the grounds that AND is often physically implemented as NAND followed by NOT), and having a discussion this was unwaranted given modern technology where the cost of routing signals dominates logic. I don't know how to make a definitive answer to the question as in the title, but I'm ready to bet the house that for depth of 10 (or even 32), the answer is way above $10^{10}$. $\endgroup$ – fgrieu Mar 23 at 13:58
  • 1
    $\begingroup$ I'm guessing that you are going to implement it homomorphically. Here is an article about it: doi.org/10.1007/978-3-642-45239-0_3 $\endgroup$ – kelalaka Mar 23 at 14:10
  • $\begingroup$ @fgrieu Can you quantify way above $10^{10}$? We can pick one definition of fan-in $2$ and fan-out $1$. $\endgroup$ – 1.. Mar 23 at 14:58
  • $\begingroup$ @kelalaka Is the terminology levels similar to depth? $\endgroup$ – 1.. Mar 23 at 14:58
  • $\begingroup$ Sorry my best justification is qualitative: cost at fixed depth is likely exponential (or worse) with the number of rounds, and 64 is a lot. Also consider the reference pointed by kelalaka uses hundreds of gates for a single round with depth >40. $\endgroup$ – fgrieu Mar 23 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.