Time–space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2

Classified as probably not a substantial claim.

Under the oracle assumption, Grover's algorithm asymptotically reduces the security level of most symmetric cryptosystems by half.

“It had been widely known that most symmetric cryptosystem's security levels will be simply reduced by half due to the asymptotic behavior of the query complexity of Grover's algorithm under the oracle assumption [2].”

• cites [2] Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79(2), 325–328 (1997) sourcePartly supported

  The Introduction (p. 1) and Algorithm (p. 2) describe a faster quantum search than classical search, with a condition that can be checked for each candidate. They do not state that this halves the security level of most symmetric cryptosystems; that application goes beyond what the paper says. (LLM, conf=0.84)

  Experimental — accuracy not yet measured

Classified as probably not a substantial claim.

The main reason for devaluating Grover's algorithm in symmetric cryptography is its poor parallelizability.

“The main reason for devaluating the algorithm in symmetric cryptography stems from its 'poor parallelizability.'”

• cites [1] Bernstein, D.J., Lange, T.: Post-quantum cryptography. Nature 549(7671), 188–194 (2017) sourceSupported
• cites [3] Bernstein, D.J.: Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?. In: SHARCS ’09, pp. 105–116 (2009)Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

May combine two claims.

Circuits consisting only of Clifford gates are not advantageous over classical computing, implying that a use of non-Clifford gates such as Toffoli is essential for quantum benefit.

“Second, circuits consisting only of Clifford gates are not advantageous over classical computing, implying that a use of non-Clifford gates such as Toffoli is essential for quantum benefit [36,37].”

• cites [36] Gottesman, D.: The Heisenberg representation of quantum computers. In: GP22: ICGTMP ’98, pp. 32–43 (1998)Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites [37] Aaronson, S., Gottesman, D.: Improved simulation of stabilizer circuits. Phys. Rev. A 70(5), 052328 (2004) sourcePartly supported

  The Introduction (p. 1) says Clifford-group circuits can be simulated efficiently on a classical computer. Section VII (p. 11) says adding a non-stabilizer gate can yield universal quantum computation, supporting the need to go beyond Clifford gates for computational benefit. Our copy does not identify Toffoli as an example. (LLM, conf=0.84)

  Experimental — accuracy not yet measured

Probably not a substantial claim: may not pass S3 (load-bearing).

No quantum algorithm with better time-space product complexity than O(N^{1/2}), achieved by the state-of-the-art classical algorithm, had been reported.

“Quoting the work, no quantum algorithm with better time-space product complexity than O(N 1/2 ) which is achieved by the state-of-the-art classical algorithm [25] had not been reported.”

• cites [3] Bernstein, D.J.: Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?. In: SHARCS ’09, pp. 105–116 (2009)Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites [25] van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1–28 (1999) sourceSupported

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

Amy et al.'s SHA-2 and SHA-3 pre-image search resource estimate did not consider random-like behavior of the SHA function and assumed that a unique pre-image of a given hash exists.

“One point we would like to address in the work is that random-like behavior of SHA function was not considered.It is assumed in the paper that the unique pre-image of a given hash exists.”

• cites [5] Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent, A., Schanck, J.: Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3. In: SAC 2016, pp. 317–337. ISBN: 978-3-319-69453-5 (2017) sourcePartly supported

  Section 2 (p. 3) models the search using a one-way permutation, which has a unique pre-image for each output. But its footnote explicitly considers that a length-restricted hash may fail to be injective and says this should not significantly affect Grover's success probability. The claim therefore overstates the extent to which non-unique pre-images were ignored. (LLM, conf=0.86)

  Experimental — accuracy not yet measured

May combine two claims.

For general k, the time-efficient design as in Fig. 5a requires k-2 zeroed work qubits within depth 2k-3, whereas the space-efficient design as in Fig. 5b uses only one arbitrary qubit within depth 8k-24 (for k ≥ 5).

“In fact for general k, time-efficient design as in Fig. 5a requires k-2 zeroed work qubits within depth 2k-3, whereas space-efficient design as in Fig. 5b uses only one arbitrary qubit within depth 8k-24 (for k ≥ 5) [32].”

• cites [32] Barenco, A., Bennett, C.H., Cleve, R., DiVincenzo, D.P., Margolus, N., Shor, P., Sleator, T., Smolin, J.A., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A 52, 3457–3467 (1995) sourcePartly supported

  Section 7.1 (pp. 18–20) supports a construction using one extra bit whose initial state need not be zero. Corollary 7.4 gives 8(n−5) Toffoli gates, which equals 8k−24 when n=k+2, but it counts gates rather than establishing that depth. Our copy does not establish the claimed k−2 zeroed work qubits or depth 2k−3 for the other design. (LLM, conf=0.86)

  Experimental — accuracy not yet measured

Probably not a substantial claim: may not pass S3 (load-bearing).

The ratio of physical execution time in all Clifford gates to all T gates is about 0.0001 in breaking SHA-256.

“Similar analysis that T gates are much more expansive than all the other gates can be found in [5], where the ratio of physical execution time in all Clifford gates to all T gates is about 0.0001 in breaking SHA-256.”

• cites [5] Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent, A., Schanck, J.: Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3. In: SAC 2016, pp. 317–337. ISBN: 978-3-319-69453-5 (2017) sourceSupported

May combine two claims.

In Amy et al.'s design, Ch and Maj require one and two Toffoli gates, respectively.

“Ch and Maj are bit-wise operations that do require Toffoli gates.We adopt Amy et al.'s design where Ch and Maj require one and two Toffoli gates, respectively.See Figs. 4 and 5 in [5].”

• cites [5] Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent, A., Schanck, J.: Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3. In: SAC 2016, pp. 317–337. ISBN: 978-3-319-69453-5 (2017) sourceSupported

May combine two claims.

In this work, the multiplicative inverse of α is calculated with seven multipliers, verified by quantum circuit simulation by matrix product state.

“Slight modification of previous method is found in this work with seven multipliers being used, verified by the quantum circuit simulation by matrix product state [52].”

• cites [52] Vidal, G.: Efficient classical simulation of slightly entangled quantum computations. Phys. Rev. Lett. 91(14), 147902 (2003) sourceSupported

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

Use of the poly-depth ADDER is better in saving work space, whereas the log-depth ADDER could shorten the execution time.

“Use of the poly-depth ADDER is better in saving work space, whereas the log-depth ADDER could shorten the execution time.”

• cites [54] Cuccaro, S.A., Draper, T.G., Kutin, S.A., Moulton, D.P.: A new quantum ripple-carry addition circuit. arXiv preprint arXiv:quant-ph/0410184 (2004) sourceSupported
• cites [55] Draper, T.G., Kutin, S.A., Rains, E.M., Svore, K.M.: A logarithmic-depth quantum carry-lookahead adder. Quantum Inf. Comput. 6(4 & 5), 351–369 (2006)Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

For f|X and y←Y, the expected number of pre-images of y is 1 ≈ sum_{j≥1} j q(j).

“For f | X and y $ ←Y , the expected number of pre-images of y becomes 1 ≈ j≥1 j • q( j).”

• AssumptionThe authors state this as an assumption: The restriction of f on X is a random function.

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

If a grows to 8, the failure probability decreases below 0.0004...≈1/e^8.

“If a grows to 8, the failure probability decreases below 0.0004 . . .≈ 1/e 8 .”

• AssumptionThe authors state this as an assumption: The restriction of f on X is a random function.

May combine two claims.

The optimal iteration count for Key Search is i^KS_rand=0.434...√N, and the expected iteration increases by 37.8...% compared with I_1 of Eq. 4.

“The result is i KS rand = 0.434 . . .• √ N and I KS rand = I KS rand (i KS rand ).Comparing I KS rand with I 1 of Eq. 4, the expected iteration increases by 37.8…%.”

Probably not a substantial claim: may not pass S2 (checkable), S3 (load-bearing), S4 (based).

Parallelization methods could vary depending on the search problems.

“It is also interesting to recognize that the parallelization methods could vary depending on the search problems.”

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

The number of targets probabilistically varies depending on α, which is capped at 447 (=512-64-1).

“The number of targets probabilistically varies depending on α which is capped at 447(= 512 -64 -1).”

May combine two claims.

In SHA-256, the hashing process does not involve as many work qubits as AES-128, so the lower-depth C256NOT gate cannot be implemented unless more qubits are introduced solely for hash comparison.

“Situation is different in SHA-256.It is noticeable that hashing process of SHA-256 does not involve as many work qubits as AES-128, meaning that the lower-depth C 256 NOT gate cannot be implemented unless more qubits are introduced solely for hash comparison.”

May combine two claims.

Among MixColumns, ShiftRows, and RotWord, the last two are simple bit permutations which require no quantum gates (by re-wiring) or at most SWAP gates.

“Among them, last two are simple bit permutations which require no quantum gates (by re-wiring) or at most SWAP gates.”

May combine two claims.

SHA-C5 requires zero additional qubits in hash comparison, whereas SHA-C6 needs (256d − 2) qubits in comparison, where d is the number of fixed bits in DP.

“The reason is that while SHA-C5 requires zero additional qubits in hash comparison, SHA-C6 needs (256d -2) qubits in comparison where d is the number of fixed bits in DP.”

May combine two claims.

Compared with [6], the circuit is about three times longer but requires one-third of the qubits.

“Compared with[6], the circuit is about three times longer but requires one-third of qubits.”

• cites [6] Grassl, M., Langenberg, B., Rötteler, M., Steinwandt, R.: Applying Grover’s algorithm to AES: quantum resource estimates. In: PQCrypto 2016, pp. 29–43. ISBN: 978-3-319-29360-8 (2016) sourceNot checked — no full text of the source

Probably not a substantial claim: may not pass S3 (load-bearing).

For large MAXDEPTH (for example, 2^96), Proposition 2 does not exactly hold because the size of the domain is larger than that of the codomain in AES-192 and AES-256; this factor is handled conservatively and reflected in Fig. 11.

“One minor note is that for large MAXDEPTH (for example, 2 96 ), Proposition 2 does not exactly hold since the size of the domain is larger than that of the codomain in AES-192 and AES-256.This factor is handled in a conservative way and reflected in Fig. 11.”

May combine two claims.

The Toffoli-depth and work qubits required for the lower-depth C256NOT gate are 509 and 2024, respectively, and for the less-qubit C256NOT gate are 254 and 1, respectively.

“Toffoli-depth and work qubits required for lower-depth (less-qubit) C 256 NOT gate are 509 (2024) and 254 (1), respectively.”

Probably not a substantial claim: may not pass S3 (load-bearing).

SHA-C6 cannot exactly fit into Proposition 5, but the deviation is small.

“It is also noticeable that SHA-C6 cannot exactly fit into Proposition 5 for the same reason just mentioned, but the deviation is small.”

May combine two claims.

The SHA-256 operation σ0(1) consists only of XORings of bit permutations and can be implemented with only CNOT gates using 32 work qubits.

“Among internal operations carried out in SHA-256, 0(1) consists only of XORings of bit permutations.Results of three ROTR operations are written on 32-bit output register, with being successively XOR-ed.Only CNOT gates are involved in implementation with 32 work qubits.”

May combine two claims.

MixColumns, ShiftRows, and RotWord are linear operations acting on 32 bits that do not require any work qubit nor Toffoli gate.

“MixColumns, ShiftRows, and RotWord are linear operations acting on 32 bits that do not require any work qubit nor Toffoli gate.”

Probably not a substantial claim: may not pass S3 (load-bearing).

This value is somewhat different from that of Proposition 6 because d has been rounded off.

“Note that this value is somewhat different from that of Proposition 6 as d has been rounded off.”

May combine two claims.

cCF384 and cCF512 do not show much difference because SHA-384 and SHA-512 algorithms are identical except for truncation and initial values.

“In contrast, c CF 384 and c CF 512 do not show much difference as SHA-384 and SHA-512 algorithms are identical except truncation and initial values.”

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based). May combine two claims.

In total, there exist 16 different circuit designs, but only six are taken into account as others seem flawed compared with the six.

“In total, there exist 16 (= 2 4 ) different circuit designs.We only take six of them into account as others seem to be flawed compared with the six.”

May combine two claims.

The quantum space cost of CNS is cheaper than SHA-C6 because the C(256−d)NOT gate used for list comparison requires fewer work qubits than C256NOT in Pre-image Search; it is estimated to be 939 qubits in total.

“Quantum space cost is cheaper than SHA-C6 because C (256-d) NOT gate used for list comparison requires less work qubits than C 256 NOT in Pre-image Search.It is estimated to be 939 qubits in total.”

Probably not a substantial claim: may not pass S4 (based).

Under the characteristics of pseudo-random functions or cryptographic hash functions, bijective correspondence between input and output is not guaranteed.

“Under the characteristics of such functions, bijective correspondence between input and output is not guaranteed.”

Probably not a substantial claim: may not pass S3 (load-bearing).

The target function in cryptanalytic search problems is usually modeled as a pseudo-random function or a cryptographic hash function.

“The target function in cryptanalytic search problems is usually modeled as a pseudo-random function (PRF) or a cryptographic hash function (CHF).The precise interpretation of this notions can be found in Sects.3.5 and 5.5 of [30].”

• cites [30] Katz, J., Lindell, Y.: Introduction to Modern Cryptography, 2nd edn. Chapman & Hall/CRC, London (2007) sourceNot checked — no full text of the source

May combine two claims.

A collision can be found by using Grover's algorithm in the way of second preimage search, and this has the same result as Sect. 3.3 if the input of the given pair of 'first pre-image' is not included in the domain.

“A collision could be found by using Grover's algorithm in the way of second preimage search.This has the same result as Sect.3.3 if the input of the given pair of 'first pre-image' is not included in the domain.”

May combine two claims.

It is always favored to enlarge the domain size, and for large S_q, the two parallelization methods show asymptotically the same performance.

“We conclude that it is always favored to enlarge the domain size, and then for large S q , two parallelization methods show asymptotically the same performance.”

Probably not a substantial claim: may not pass S4 (based).

In the quantum circuit model, it is often possible to sacrifice efficiency in qubits for better performance in time and vice versa.

“In quantum circuit model, it is often possible to sacrifice efficiency in qubits for better performance in time and vice versa.”

Probably not a substantial claim: may not pass S4 (based).

Taking the total number of gates as time complexity disturbs accurate estimates for the speed of quantum algorithms because of far different overheads introduced by various gates in real operation.

“Taking the total number of gates as time complexity disturbs accurate estimates for the speed of quantum algorithms due to far different overheads introduced by various gates in real operation.”

Classified as probably not a substantial claim.

Quantum security of symmetric cryptosystems can be estimated in units of elementary logic gates.

“Quantum security of symmetric cryptosystems can then be estimated in units of elementary logic gates.”

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

The implementation of a function in a quantum circuit has to be a unitary transformation such that the input can be retrieved back by knowing the output.

“In quantum circuit, the implementation of a function has to be a unitary transformation such that the input can be retrieved back by knowing the output.”

Probably not a substantial claim: may not pass S3 (load-bearing).

The CNS algorithm has O(N^{2/5}) query complexity using O(N^{1/5}) classical memory.

“In ASIACRYPT 2017, Chailloux, Naya-Plasencia, and Schrottenloher suggested a new quantum collision finding algorithm, called CNS algorithm, of O(N 2/5 ) query complexity using O(N 1/5 ) classical memory [11].”

• cites [11] Chailloux, A., Naya-Plasencia, M., Schrottenloher, A.: An efficient quantum collision search algorithm and implications on symmetric cryptography. In: ASIACRYPT 2017, pp. 211–240. ISBN: 978-3-319-70697-9. (2017) sourceNot checked — no full text of the source

May combine two claims.

For a random function with |Y|=N and |X|=aN, the probability that a random y∈Y is a j-node is q^{(aN)}(j)≈(1/e^a)(a^j/j!), and the probability that f(x) for random x∈X is a j-node is r^{(aN)}(j)≈j q^{(aN)}(j).

“For y $ ←Y , the probability of y to be a j-node, denoted by q (a N ) : Z ≥0 → [0, 1], is q (a N ) ( j) ≈ 1 e a • a j j! . (5 ) For x $ ←X , the probability of f (x) to be a j-node, denoted by r (a N ) : N → [0, 1], is r (a N ) ( j) ≈ j • q (a N ) ( j). (6 )”

• cites [29] Flajolet, P., Odlyzko, A.M.: Random mapping statistics. In: EUROCRYPT ’89, pp. 329–354. Springer, Berlin Heidelberg. ISBN: 978-3-540-46885-1 (1990) sourceNot checked — no full text of the source

May combine two claims.

While inner parallelization is a better option in Key Search, both parallelization methods have similar behaviors in Pre-image Search.

“Note that while the inner parallelization is a better option in Key Search, both parallelization methods have similar behaviors in Pre-image Search.”

Probably not a substantial claim: may not pass S3 (load-bearing).

Toffoli (and single) gates are universal.

“First, Toffoli (and single) gates are universal [33][34][35].”

• cites [33] Deutsch, D.: Quantum computational networks. Proc. R. Soc. Lond. A 425(1868), 73–90 (1989) sourceNot checked — no full text of the source
• cites [34] Shi, Y.: Both Toffoli and controlled-NOT need little help to do universal quantum computing. Quantum Inf. Comput. 3(1), 84–92 (2003) sourceNot checked — no full text of the source
• cites [35] Toffoli, T.: Reversible computing. In: de Bakker, J., van Leeuwen, J. (eds.) Automata, Languages and Programming, pp. 632–644. Springer, Berlin Heidelberg (1980) sourceNot checked — no full text of the source

May combine two claims.

If S_q=2^s, the CNS time complexity becomes O(2^{(n-d-l-s)/2}(2^{d/2}+2^l)+2^{l+d/2-s}) for s≤min(l,n-d-l); when l=d/2 and d=2/5(n+s), the complexities satisfy (T_q)^5(S_q)^3=O(N^2) and T_q(S_c)^3=O(N).

“If S q = 2 s , time complexity becomes O(2 (n-d-l-s)/2 (2 d/2 + 2 l ) + 2 l+d/2-s ) for s ≤ min(l, ndl).When l = d/2 and d = 2/5{n + s}, the complexities satisfy (T q ) 5 (S q ) 3 = O(N 2 ) and T q (S c ) 3 = O(N ).”

• cites [11] Chailloux, A., Naya-Plasencia, M., Schrottenloher, A.: An efficient quantum collision search algorithm and implications on symmetric cryptography. In: ASIACRYPT 2017, pp. 211–240. ISBN: 978-3-319-70697-9. (2017) sourceNot checked — no full text of the source

Probably not a substantial claim: may not pass S4 (based).

Two primary resources in quantum computing, circuit depth and qubit, can be exchanged to meet a certain attack design criteria.

“Two primary resources in quantum computing, circuit depth and qubit, can be exchanged to meet a certain attack design criteria.”

Probably not a substantial claim: may not pass S3 (load-bearing).

Bit multiplication is an example where qubit and depth are mutually exchangeable.

“Bit multiplication is one of examples qubit and depth are mutually exchangeable.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

The two-bit binary multiplication in classical setting can be achieved by using AND gate, but similar implementation cannot be adopted in quantum setting.

“The implementation of the two-bit binary multiplication in classical setting can be achieved by using AND gate.Similar implementation cannot be adopted in quantum setting.”

Classified as probably not a substantial claim. May combine two claims.

The three MAXDEPTH parameters adopted from [10] are 2^40, 2^64, and 2^96, corresponding to logical gates performable in a year, a decade, and a millennium respectively.

“-2 40 : Approximate number of logical gates that presently envisioned quantum computing architectures are expected to serially perform in a year.-2 64 : Approximate number of logical gates that current classical computing architectures can perform serially in a decade.-2 96 : Approximate number of logical gates that atomic scale qubits with speed of light propagation times could perform in a mill”

• cites [10] NIST: Post-quantum cryptography—call for proposals (2017). https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-Quantum-Cryptography-Standardization/Call-for-ProposalsNot checked yet

  Not checked in the free run.

May combine two claims.

Grassl et al. ensured a single target key in AES key search by encrypting r∈{3,4,5} plaintext blocks simultaneously to obtain r ciphertexts so that only the true key results in given ciphertexts; this removes ambiguity in the number of iterations at the cost of at least tripling the space cost.

“To avoid the cases, the authors encrypt r (∈ {3, 4, 5}) plaintext blocks simultaneously to obtain r ciphertexts so that only the true key results in given ciphertexts.The procedure removes the ambiguity in the number of iterations.Note, however, that the removal of the ambiguity comes in exchange of at least tripling the space cost.”

• cites [6] Grassl, M., Langenberg, B., Rötteler, M., Steinwandt, R.: Applying Grover’s algorithm to AES: quantum resource estimates. In: PQCrypto 2016, pp. 29–43. ISBN: 978-3-319-29360-8 (2016) sourceNot checked — no full text of the source

Classified as probably not a substantial claim.

The approach adopted in this work ignores the overheads introduced by fault tolerance.

“Readers should keep in mind that this approach ignores the overheads introduced by fault tolerance.”

May combine two claims.

In Key Search, the given y becomes a t-node with probability r(t), and since only one target among t pre-images is the true key, the probability that the answer is correct after measurement is 1/t.

“In Key Search, the given y ∈ Y becomes t-node with probability r (t) of Eq. 6.The probability that one of the pre-images of y is found by the measurement after i-times Grover iterations becomes p t (i) of Eq. 2. Since only one target among t pre-images is the true key, the probability that the answer is correct is 1/t.”

Probably not a substantial claim: may not pass S4 (based). May combine two claims.

It is very unlikely that larger gates such as C^k NOT can be directly operated in any realistic universal quantum computers, so decomposition into smaller gates is required in practical estimates.

“It is very unlikely that such gates can be directly operated in any realistic universal quantum computers.Decomposition of those gates into smaller ones is thus required in practical estimates.”

Probably not a substantial claim: may not pass S2 (checkable), S3 (load-bearing).

It is more transparent to connect the time complexity with Toffoli gates than any other gates.

“Therefore, it is more transparent to connect the time complexity with Toffoli gates than any other gates.”

Probably not a substantial claim: may not pass S2 (checkable).

The results summarized in Figure 11 can be interpreted as another threshold to be used for the security strength classification of proposed schemes in the NIST PQC standardization process.

“Figure 11 summarizes the results which can be interpreted as another threshold to be used, for the security strength classification of proposed schemes in NIST PQC standardization process.”

Classified as probably not a substantial claim. May combine two claims.

Since SubBytes and SubWord consist of 16 and 4 S-boxes, the S-box is the only operation to be carefully discussed.

“Since SubBytes and SubWord consist of 16 and 4 S-boxes, the S-box is the only operation to be carefully discussed.”

May combine two claims.

Although ensuring a single target can be regarded as an optimization point when using a single processor, it strictly cannot be an option in parallel attack since inner parallelization removes a penalty of random characteristics as in Eq. 8.

“Although ensuring single target can be regarded as an optimization point when using single processor, it strictly cannot be an option in parallel attack since the inner parallelization removes a penalty of random characteristics as in Eq. 8.”

May combine two claims.

Production or preparation of T gates is hardware-dependent, whereas the number of Toffoli gates is machine-independent but depends only on the algorithm.

“Production or preparation of T gates is hardware-dependent, whereas the number of Toffoli gates (which consists of several T gates) is machine-independent but rather depends only on the algorithm, justifying the choice for the resource unit.”

• cites [39] Jones, N.C., Van Meter, R., Fowler, A.G., McMahon, P.L., Kim, J., Ladd, T.D., Yamamoto, Y.: Layered architecture for quantum computing. Phys. Rev. X 2(3), 031007 (2012) sourceNot checked — no full text of the source

Probably not a substantial claim: may not pass S4 (based). May combine two claims.

AES-128 works as a PRF, so it is possible that multiple keys lead to the same ciphertext.

“Since AES-128 works as a PRF, it is possible that multiple keys lead to the same ciphertext,”

Probably not a substantial claim: may not pass S4 (based).

Despite its simplicity, counting the number of sequential Toffoli gates reflects the reliable time complexity in estimating security levels of symmetric cryptosystems.

“Despite its simplicity, counting the number of sequential Toffoli gates reflects the reliable time complexity in estimating security levels of symmetric cryptosystems.”

May combine two claims.

In SHA-256, the i-th round function is fed by the i-th word from the schedule, so parallel implementation is possible if enough work qubits are given.

“In the algorithm description, i-th round function is fed by i-th word from the schedule meaning that parallel implementation is possible if enough work qubits are given.”

May combine two claims.

Since each run of the AES round function produces garbage qubits, forward running of 10 rounds accumulates ≥1280 garbage qubits; putting reverse rounds in between forward rounds reduces a large amount of work qubits at the cost of longer Toffoli-depth.

“Since each run of round function produces garbage qubits, forward running of 10 rounds accumulates ≥ 1280 garbage qubits.Putting reverse rounds in between forward rounds reduces a large amount of work qubits at the cost of longer Toffolidepth.”

Probably not a substantial claim: may not pass S2 (checkable).

With the simplified cost measure, one can estimate the quantum complexity of a cryptosystem concisely by counting and focusing on relevant operations only.

“With simplified cost measure, one can estimate the quantum complexity of a cryptosystem concisely by counting (and focusing) relevant operations only.”

May combine two claims.

In the numerical calculation, α = 266 seems to safely achieve the optimal expected iteration number given by Proposition 3 and to remove the failure probability.

“In our numerical calculation, α = 266 seems to safely achieve the optimal expected iteration number given by Proposition 3 and to remove the failure probability.”

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

The above scheme is general for quantum resource estimates in symmetric cryptanalysis.

“It is worth noting that the above scheme is general for quantum resource estimates in symmetric cryptanalysis.”