CryptoDB
Avichai Marmor
Publications
Year
Venue
Title
2024
EUROCRYPT
Partial Sums Meet FFT: Improved Attack on 6-Round AES
Abstract
The partial sums cryptanalytic technique was introduced in 2000 by Ferguson et al., who used it to break 6-round AES with time complexity of $2^{52}$ S-box computations -- a record that has not been beaten ever since. In 2014, Todo and Aoki showed that for 6-round AES, partial sums can be replaced by a technique based on the Fast Fourier Transform (FFT), leading to an attack with a comparable complexity.
In this paper we show that the partial sums technique can be combined with an FFT-based technique, to get the best of the two worlds. Using our combined technique, we obtain an attack on 6-round AES with complexity of about $2^{46.4}$ additions. We fully implemented the attack experimentally, along with the partial sums attack and the Todo-Aoki attack, and confirmed that our attack improves the best known attack on 6-round AES by a factor of more than 32.
We expect that our technique can be used to significantly enhance numerous attacks that exploit the partial sums technique. To demonstrate this, we use our technique to improve the best known attack on 7-round Kuznyechik by a factor of more than 80, and to reduce the complexity of the best known attack on the full MISTY1 from $2^{69.5}$ to $2^{67}$.
2024
ASIACRYPT
Tiresias: Large Scale, UC-Secure Threshold Paillier
Abstract
In the threshold version of Paillier's encryption scheme, a set of parties collectively holds the secret decryption key through a secret sharing scheme.
Whenever a ciphertext is to be decrypted, the parties send their decryption shares, which are then verified for correctness and combined into the plaintext.
The scheme has been widely adopted in various applications, from secure voting to general purpose MPC protocols.
However, among the handful of existing proposals for a maliciously secure scheme, one must choose between an efficient implementation that relies on non-standard assumptions or a computationally expensive implementation that relies on widely acceptable assumptions.
In this work, we show that one can enjoy the benefits of both worlds.
Specifically, we adjust a scheme by Damgard et al. (Int. J. Inf. Secur. 2010) to get a practical distributed key generation (DKG). While the original scheme was only known to be secure under ad-hoc non-standard assumptions, we prove that the adjusted scheme is in fact secure under the decisional composite residuosity (DCR) assumption alone, required for the semantic security of the Pallier encryption scheme itself.
This is possible thanks to a novel reduction technique, from computing and proving a false decryption share, to the factoring problem. Specifically, while there may exist false decryption shares for which the zk-proof verifies with non-negligible probability, they are computationally hard to find.
Furthermore, we use similar ideas to prove that batching techniques by Aditya et al. (ACNS 2004), which allows a prover to batch several statements into a single proof, can be applied to our adjusted scheme. This enables a batched threshold Paillier decryption in the fully distributed setting for the first time.
Until now, verifying that a decryption share is correct was the bottleneck of threshold Paillier schemes and hindered real world deployments (unless one is willing to rely on a trusted dealer).
Our work accumulates to shifting the bottleneck back to the plaintext reconstruction, just like in the semi-honest setting, and renders threshold Paillier practical for the first time, supporting large scale deployments.
We exemplify this shift by implementing the scheme and report our evaluation with up to 1000 parties, in the dishonest majority setting.
Over an EC2 c6i machine, we get a throughput of about 50 and 3.6 decryptions per second, when run over a network of 100 and 1000 parties, respectively.
Coauthors
- Orr Dunkelman (1)
- Offir Friedman (1)
- Shibam Ghosh (1)
- Nathan Keller (1)
- Gaëtan Leurent (1)
- Avichai Marmor (2)
- Victor Mollimard (1)
- Dolev Mutzari (1)
- Yehonatan C. Scaly (1)
- Yuval Spiizer (1)
- Avishay Yanai (1)