IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
02 June 2022
Sujaya Maiyya, Seif Ibrahim, Caitlin Scarberry, Divyakant Agrawal, Amr El Abbadi, Huijia Lin, Stefano Tessaro, and Victor Zakhary
Yevgeniy Dodis, Willy Quach, and Daniel Wichs
First, we consider the symmetric-key setting, where Alice and Bob share a small secret key. Alice can authenticate arbitrarily many messages to Bob by streaming long authentication tags of size $k \gg m$, while ensuring that the tags can be generated and verified using only $n$ bits of memory. We show a solution using local extractors (Vadhan; JoC '04), which allows for up to exponentially large adversarial memory $m = 2^{O(n)}$, and has tags of size $k= O(m)$. Second, we consider the same setting as above, but now additionally require each individual tag to be small, of size $k \leq n$. We show a solution is still possible when the adversary's memory is $m = O(n^2)$, which is optimal. Our solution relies on a space lower bound for leaning parities (Raz; FOCS '16). Third, we consider the public-key signature setting. A signer Alice initially streams a long verification key over an authentic channel, while only keeping a short signing key in her memory. A verifier Bob receives the streamed verification key and generates some short verification digest that he keeps in his memory. Later, Alice can sign arbitrarily many messages using her signing key by streaming the signatures to Bob, who can verify them using his verification digest. We show a solution for $m= O(n^2)$, which we show to be optimal. Our solution relies on a novel entropy lemma, of independent interest. We show that, if a sequence of blocks has sufficiently high min-entropy, then a large fraction of individual blocks must have high min-entropy. Naive versions of this lemma are false, but we show how to patch it to make it hold.
01 June 2022
The University of Manchester, UK
The System and Software Security (S3) group at The University of Manchester is looking for a Post-Doc in Secure and Verifiable AI Models to join our ambition EPSRC-funded EnnCore project (https://enncore.github.io/).
The successful candidate will enjoy designing, developing, and evaluating novel AI models that are secure and robust against attacks. The project will involve continuous interaction with experts in explainable AI, software testing and formal software verification.
The S3 group conducts a world-leading research in the space of explainable AI, automated software verification and testing. It develops award-winning software verification tools and regularly wins prices at international competitions.
Closing date for applications:
Contact: Mustafa Mustafa (mustafa.mustafa@manchester.ac.uk)
More information: https://www.jobs.manchester.ac.uk/displayjob.aspx?jobid=22435
31 May 2022
Nilanjan Datta, Avijit Dutta, Mridul Nandi, and Suprita Talnikar
Subhadeep Banik, Khashayar Barooti, Andrea Caforio, and Serge Vaudenay
The significance of cryptanalysing LowMC was elevated by its inclusion into the NIST PQC digital signature scheme PICNIC in which a successful key recovery using a single plaintext/ciphertext pair is akin to retrieving the secret signing key. The current state-of-the-art attack in this setting is due to Dinur [Din21a], in which a novel way of enumerating the roots of a Boolean system of equation is morphed into a key recovery procedure that undercuts an ordinary exhaustive search in terms of time complexity for the variants of the cipher up to five rounds.
In this work, we demonstrate that this technique can efficiently be enriched with a specific linearization strategy that reduces the algebraic degree of the non-linear layer as put forward by Banik et al. [BBDV20]. This amalgamation yields a drastic reduction in terms of memory complexity across all instantiations of LowMC up to six rounds with a quasi-equivalent time complexity.
Dario Catalano, Dario Fiore, and Emanuele Giunta
In this paper we make progress in the study of SSLE by proposing new efficient constructions that achieve stronger security guarantees than previous work. In particular, we propose the first SSLE protocol that achieves adaptive security. Our scheme is proven secure in the universal composability model and achieves efficiency comparable to previous, less secure, realizations in the state of the art.
Benoît Cogliati, Avijit Dutta, Mridul Nandi, Jacques Patarin, and Abishanka Saha
Bhuvnesh Chaturvedi, Anirban Chakraborty, Ayantika Chatterjee, and Debdeep Mukhopdhyay
Sergio Demian Lerner, Javier Álvarez Cid-Fuentes, Julian Len, Ramsès Fernàndez-València, Patricio Gallardo, Nicolás Vescovo, Raúl Laprida, Shreemoy Mishra, Federico Jinich, and Diego Masini
Kyungbae Jang, Anubhab Baksi, Gyeongju Song, Hyunji Kim, Hwajeong Seo, and Anupam Chattopadhyay
Keeping this in mind, our work explores the key recovery attack using the Grover's search on the three variants of AES (-128, -192, -256) with respect to the quantum implementation and the quantum key search using the Grover's algorithm. We develop a pool of implementations, by mostly reducing the circuit depth metrics. We consider various strategies for optimization, as well as make use of the state-of-the-art advancements in the relevant fields.
In a nutshell, we present the least Toffoli depth and full depth implementations of AES, thereby improving from Zou et al.'s Asiacrypt'20 paper by more than 98 percent for all variants of AES. Moreover, our qubit count - Toffoli depth product is improved from theirs by more than 75 percent. Moreover, we analyze the Jaques et al.'s Eurocrypt'20 implementations in details, fix its bugs and report corrected benchmarks. To the best of our finding, our work presents the currently best-known results, thereby improving from all the previous works (including the recent Eprint'22 paper by Huang and Sun).
Songze Li, Sizai Hou, Baturalp Buyukates, and Salman Avestimehr
Saikrishna Badrinarayanan, Yuval Ishai, Dakshita Khurana, Amit Sahai, and Daniel Wichs
We provide two such constructions: 1) Our first construction is in the ideal obfuscation model (alternatively, assuming virtual black-box obfuscation for a concrete class of circuits). It develops a general framework that may be of broader interest, and allows us to embed an instance of a resettably-secure multiparty computation protocol into a one-way function. Along the way, we design the first resettably-secure multiparty computation protocol for general functionalities in the plain model with super-polynomial simulation, under standard assumptions.
2) The second construction relies on public-coin differing-inputs obfuscation (PCdiO) along with a certain form of hash-function security called extended second-preimage resistance (ESPR). It starts with a previously known counterexample to the dream direct-product hardness amplification based on ESPR, and uses PCdiO to upgrade it into a counterexample for the XOR lemma.
Prior to our work, even completely heuristic counterexamples of this type were not known.
Omid Mir, Daniel Slamanig, Balthazar Bauer, and René Mayrhofer
We present a novel delegatable anonymous credential scheme that supports attributes, provides anonymity for delegations, allows the delegators to restrict further delegations, and also comes with an efficient construction. In particular, our DAC credentials do not grow with delegations, i.e., are of constant size. Our approach builds on a new primitive that we call structure-preserving signatures on equivalence classes on updatable commitments (SPSEQ-UC). The high-level idea is to use a special signature scheme that can sign vectors of set commitments which can be extended by additional set commitments. Signatures additionally include a user's public key, which can be switched. This allows us to efficiently realize delegation in the DAC. Similar to conventional SPSEQ signatures, the signatures and messages can be publicly randomized and thus allow unlinkable showings in the DAC system. We present further optimizations such as cross-set commitment aggregation that, in combination, enable selective, efficient showings in the DAC without using costly zero-knowledge proofs. We present an efficient instantiation that is proven to be secure in the generic group model and finally demonstrate the practical efficiency of our DAC by presenting performance benchmarks based on an implementation.
Katharina Boudgoust, Amin Sakzad, and Ron Steinfeld
Mark Zhandry
- LPN in a variety of low noise or high-hardness regimes, essentially matching what is known for collision resistance from LPN.
- Finding cycles on exponentially-large expander graphs, such as those arising from isogenies on elliptic curves.
- The "optimal" hardness of finding collisions in *any* hash function.
- The *polynomial* hardness of finding collisions, assuming a certain plausible regularity condition on the hash.
As an immediate corollary, we obtain the first statistically hiding post-quantum commitments and post-quantum succinct arguments (of knowledge) under the same assumptions. Our results are obtained by a general theorem which shows how to construct a collapsing hash $H'$ from a post-quantum collision-resistant hash function $H$, regardless of whether or not $H$ itself is collapsing, assuming $H$ satisfies a certain regularity condition we call "semi-regularity."
Leon Mächler and David Naccache
We noted that the known values of $(4/\gamma_n)^n$ coincide with the values of the minimal determinants of any $n$-dimensional integral lattice when the length of the smallest lattice element $\mu$ is fixed to 4.
Based on this observation, we conjecture that the values of $\gamma_n^n$ for $n=9,\ldots,23$ are those given in Table 2.
We provide a supporting argument to back this conjecture. We also provide a provable lower bound on the Hermite constants for $1\leq n\leq24$.
Xavier Bonnetain, André Chailloux, André Schrottenloher, and Yixin Shen
The situation becomes different when one is looking for \emph{multiple} collision pairs. Here, for $2^k$ collisions, a query lower bound of $\Theta(2^{(2k+m)/3})$ was shown by Liu and Zhandry (EUROCRYPT~2019). A matching algorithm is known, but only for relatively small values of $m$, when many collisions exist. In this paper, we improve the algorithms for this problem and, in particular, extend the range of admissible parameters where the lower bound is met.
Our new method relies on a \emph{chained quantum walk} algorithm, which might be of independent interest. It allows to extract multiple solutions of an MNRS-style quantum walk, without having to recompute it entirely: after finding and outputting a solution, the current state is reused as the initial state of another walk.
As an application, we improve the quantum sieving algorithms for the shortest vector problem (SVP), with a complexity of $2^{0.2563d + o(d)}$ instead of the previous $2^{0.2570d + o(d)}$.
Nishat Koti, Shravani Patil, Arpita Patra, and Ajith Suresh
Cast in the preprocessing paradigm, our semi-honest protocol improves the online complexity of the decade-old state-of-the-art protocol of Damgård and Nielson (CRYPTO'07). In addition to having an improved online communication cost, we can shut down almost half of the parties in the online phase, thereby saving up to 50$\%$ in the system's operational costs. Our maliciously secure protocol also enjoys similar benefits and requires only half of the parties, except for one-time verification, towards the end.
To showcase the practicality of the designed protocols, we benchmark popular applications such as deep neural networks, graph neural networks, genome sequence matching, and biometric matching using prototype implementations. Our improved protocols aid in bringing up to 60-80$\%$ savings in monetary cost over prior work.
Cezary Glowacz
Alex Biryukov, Luan Cardoso dos Santos, Je Sen Teh, Aleksei Udovenko, and Vesselin Velichkov
We illustrate MiF in practice by reporting improved attacks on the ARX-based family of block ciphers Speck. We improve the time complexities of the best known attacks up to 15 rounds of Speck32 and 20 rounds of Speck64/128. Notably, our new attack on 11 rounds of Speck32 has practical analysis and data complexities of $2^{24.66}$ and $2^{26.70}$ respectively, and was experimentally verified, recovering the master key in a matter of seconds. It significantly improves the previous deep learning-based attack by Gohr from CRYPTO 2019, which has time complexity $2^{38}$. As an important milestone, our conventional cryptanalysis method sets a new high benchmark to beat for cryptanalysis relying on machine learning.