IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
02 June 2022
Andreea B. Alexandru, Erica Blum, Jonathan Katz, and Julian Loss
ePrint ReportWe further explore efficient SMR protocols run in a network that may change between synchronous and asynchronous arbitrarily often; parties can be uncorrupted (as in the proactive model), and the protocol should remain secure as long as the appropriate corruption thresholds are always maintained. We show that proactively secure SMR using threshold cryptography is impossible without some form of synchronization between the parties. Motivated by this negative result, we consider a model where the adversary is limited in the total number of parties it can corrupt over the duration of the protocol and show, in this setting, that our SMR protocols remain secure under arbitrarily changing network conditions.
Pedro Branco, Nico Döttling, and Jesko Dujmovic
ePrint ReportDario Catalano, Dario Fiore, Rosario Gennaro, and Emanuele Giunta
ePrint ReportIn this paper, we shed light on this state of affairs by showing that a large class of concise algebraic vector commitments in pairing-free, prime order groups are impossible to realize.
Our results also preclude any cryptographic primitive that implies the algebraic vector commitments we rule out, as special cases. This means that we also show the impossibility, for instance, of succinct polynomial commitments and functional commitments (for all classes of functions including linear forms) in pairing-free groups of prime order.
Marek Bielik, Martin Jureček, Olha Jurečková, and Róbert Lórencz
ePrint ReportNils Fleischhacker, Mark Simkin, and Zhenfei Zhang
ePrint ReportWe present Squirrel, a concretely efficient lattice-based multi-signature scheme in the synchronized setting that works for a bounded number of $2^{\tau}$ time steps and allows for aggregating up to $\rho$ signatures at each step, where both $\tau$ and $\rho$ are public parameters upon which the efficiency of our scheme depends. Squirrel allows for non-interactive aggregation of independent signatures and is proven secure in the random oracle model in the presence of rogue-key attacks assuming the hardness of the short integer solution problem in a polynomial ring.
We provide a careful analysis of all parameters and show that Squirrel can be instantiated with good concrete efficiency. For $\tau = 24$ and $\rho = 4096$, a signer could sign a new message every 10 seconds for 5 years non-stop. Assuming the signer has a cache of 112 MB, signing takes 68 ms and verification of an aggregated signature takes 36 ms. The size of the public key is 1 KB, the size of an individual signature is 52 KB, and the size of an aggregated signature is 771 KB.
Shun Watanabe and Kenji Yasunaga
ePrint ReportAlessandro Budroni, Jesús-Javier Chi-Domínguez, and Mukul Kulkarni
ePrint ReportSujaya Maiyya, Seif Ibrahim, Caitlin Scarberry, Divyakant Agrawal, Amr El Abbadi, Huijia Lin, Stefano Tessaro, and Victor Zakhary
ePrint ReportYevgeniy Dodis, Willy Quach, and Daniel Wichs
ePrint ReportFirst, 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
Job PostingThe 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
ePrint ReportSubhadeep Banik, Khashayar Barooti, Andrea Caforio, and Serge Vaudenay
ePrint ReportThe 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
ePrint ReportIn 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
ePrint ReportBhuvnesh Chaturvedi, Anirban Chakraborty, Ayantika Chatterjee, and Debdeep Mukhopdhyay
ePrint ReportSergio 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
ePrint ReportKyungbae Jang, Anubhab Baksi, Gyeongju Song, Hyunji Kim, Hwajeong Seo, and Anupam Chattopadhyay
ePrint ReportKeeping 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
ePrint ReportSaikrishna Badrinarayanan, Yuval Ishai, Dakshita Khurana, Amit Sahai, and Daniel Wichs
ePrint ReportWe 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
ePrint ReportWe 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.