Secure Wire Shuffling in the Probing Model

in Crypto 2021 (2021, August)

A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem

in Advances in Cryptology -- CRYPTO 2020 (2020, August 10)

At Crypto '99, Nguyen and Stern described a lattice based algorithm for solving the hidden subset sum problem, a variant of the classical subset sum problem where the n weights are also hidden. While the ... [more ▼]

At Crypto '99, Nguyen and Stern described a lattice based algorithm for solving the hidden subset sum problem, a variant of the classical subset sum problem where the n weights are also hidden. While the Nguyen-Stern algorithm works quite well in practice for moderate values of n, we argue that its complexity is actually exponential in n; namely in the final step one must recover a very short basis of a n-dimensional lattice, which takes exponential-time in n, as one must apply BKZ reduction with increasingly large block-sizes. [less ▲]

Side-Channel Masking with Pseudo-Random Generator

in Eurocrypt 2020 (2020)

Cryptanalysis of CLT13 Multilinear Maps with Independent Slots

in Advances in Cryptology – ASIACRYPT 2019, 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8–12, 2019, Proceedings, Part II (2019, December)

Improved Cryptanalysis of the AJPS Mersenne Based Cryptosystem

in Journal of Mathematical Cryptology (2019)

At Crypto 2018, Aggarwal, Joux, Prakash and Santha (AJPS) described a new public-key encryption scheme based on Mersenne numbers. Shortly after the publication of the cryptosystem, Beunardeau et al ... [more ▼]

At Crypto 2018, Aggarwal, Joux, Prakash and Santha (AJPS) described a new public-key encryption scheme based on Mersenne numbers. Shortly after the publication of the cryptosystem, Beunardeau et al. described an attack with complexity O(2^(2h)). In this paper, we describe an improvedattack with complexity O(2^(1.75h)) . [less ▲]

Zeroizing Attacks on Indistinguishability Obfuscation over CLT13

in Proceedings of PKC 2017 (2017)

Cryptanalysis of GGH15 Multilinear Maps

in Proceedings of Crypto 2016 (2016)

New Multilinear Maps over the Integers

in Proceedings of Crypto 2015 (2015)

Conversion from Arithmetic to Boolean Masking with Logarithmic Complexity

in Leander, Gregor (Ed.) Fast Software Encryption, 22nd International Workshop, FSE 2015, Istanbul, Turkey, March 8-11, 2015, Revised Selected Papers (2015, March)

A general technique to protect a cryptographic algorithm against side-channel attacks consists in masking all intermediate variables with a random value. For cryptographic algorithms combining Boolean ... [more ▼]

A general technique to protect a cryptographic algorithm against side-channel attacks consists in masking all intermediate variables with a random value. For cryptographic algorithms combining Boolean operations with arithmetic operations, one must then perform conversions between Boolean masking and arithmetic masking. At CHES 2001, Goubin described a very elegant algorithm for converting from Boolean masking to arithmetic masking, with only a constant number of operations. Goubin also described an algorithm for converting from arithmetic to Boolean masking, but with O(k) operations where k is the addition bit size. In this paper we describe an improved algorithm with time complexity O(log k) only. Our new algorithm is based on the Kogge-Stone carry look-ahead adder, which computes the carry signal in O(log k) instead of O(k) for the classical ripple carry adder. We also describe an algorithm for performing arithmetic addition modulo 2^k directly on Boolean shares, with the same complexity O(log k) instead of O(k). We prove the security of our new algorithm against first-order attacks. Our algorithm performs well in practice, as for k=64 we obtain a 23% improvement compared to Goubin’s algorithm. [less ▲]

Higher Order Masking of Look-Up Tables

in Proceedings of Eurocrypt 2014 (2014)