Non-Transferable Anonymous Tokens by Secret Binding
https://eprint.iacr.org/2024/711

Non-transferability (NT) is a security notion which ensures that credentials are only used by their intended owners. Despite its importance, it has not been formally treated in the context of anonymous tokens (AT) which are lightweight anonymous credentials. In this work, we consider a client who "buys" access tokens which are forbidden to be transferred although anonymously redeemed. We extensively study the trade-offs between privacy (obtained through anonymity) and security in AT through the notion of non-transferability. We formalise new security notions, design a suite of protocols with various flavors of NT, prove their security, and implement the protocols to assess their efficiency. Finally, we study the existing anonymous credentials which offer NT, and show that they cannot automatically be used as AT without security and complexity implications.

Quantum NV Sieve on Grover for Solving Shortest Vector Problem
https://eprint.iacr.org/2024/712

Quantum computers can efficiently model and solve several challenging problems for classical computers, raising concerns about potential security reductions in cryptography. NIST is already considering potential quantum attacks in the development of post-quantum cryptography by estimating the quantum resources required for such quantum attacks. In this paper, we present quantum circuits for the NV sieve algorithm to solve the Shortest Vector Problem (SVP), which serves as the security foundation for lattice-based cryptography, achieving a quantum speedup of the square root. Although there has been extensive research on the application of quantum algorithms for lattice-based problems at the theoretical level, specific quantum circuit implementations for them have not been presented yet.
Notably, this work demonstrates that the required quantum complexity for the SVP in the lattice of rank 70 and dimension 70 is $2^{43}$ (a product of the total gate count and the total depth) with our optimized quantum implementation of the NV sieve algorithm.
This complexity is significantly lower than the NIST post-quantum security standard, where level 1 is $2^{157}$, corresponding to the complexity of Grover's key search for AES-128.

Analyzing Pump and jump BKZ algorithm using dynamical systems
https://eprint.iacr.org/2024/713

The analysis of the reduction effort of the lattice reduction algorithm is important in estimating the hardness of lattice-based cryptography schemes. Recently many lattice challenge records have been cracked by using the Pnj-BKZ algorithm which is the default lattice reduction algorithm used in G6K, such as the TU Darmstadt LWE and SVP Challenges. However, the previous estimations of the Pnj-BKZ algorithm are simulator algorithms rather than theoretical upper bound analyses. In this work, we present the first dynamic analysis of Pnj-BKZ algorithm. More precisely, our analysis results show that let $L$ is the lattice spanned by $(\mathbf{a}_i)_{i\leq d}$. The shortest vector $\mathbf{b}_1$ output by running $\Omega \left ( \frac{2Jd^2}{\beta(\beta-J)}\left ( \ln_{}{d} +\ln_{} \ln_{}{\max_{i}\frac{\left \| \mathbf{a}_i^{*} \right \| }{(\mathrm{det}L )^{1/d} } } \right ) \right ) $ tours reduction of pnj-BKZ$(\beta,J)$, $\mathbf{b}_1$ satisfied that \memo{$\left \| \mathbf{b}_1 \right \| \le {\gamma}_{\beta}^{\frac{d-1}{2(\beta-J)}+2 } \cdot \left ( \mathrm{det}L \right ) ^{\frac{1}{d} } $}.

Learning with Quantization, Polar Quantizer, and Secure Source Coding
https://eprint.iacr.org/2024/714

This paper presents a generalization of the Learning With Rounding (LWR) problem, initially introduced by Banerjee, Peikert, and Rosen, by applying the perspective of vector quantization. In LWR, noise is induced by rounding each coordinate to the nearest multiple of a fraction, a process inherently tied to scalar quantization. By considering a new variant termed Learning With Quantization (LWQ), we explore large-dimensional fast-decodable lattices with superior quantization properties, aiming to enhance the compression performance over conventional scalar quantization. We identify polar lattices as exemplary structures, effectively transforming LWQ into a problem akin to Learning With Errors (LWE), where the distribution of quantization noise is statistically close to discrete Gaussian. Furthermore, we develop a novel ``quancryption'' scheme for secure source coding. Notably, the scheme achieves near-optimal rate-distortion ratios for bounded rational signal sources, and can be implemented efficiently with quasi-linear time complexity. Python code of the polar-lattice quantizer is available at https://github.com/shx-lyu/PolarQuantizer.

PhD Student in Security of AI Hardware
https://iacr.org/news/item/23114

Job Posting: PhD Student in Security of AI Hardware

University at Albany, SUNY, Department of Electrical and Computer Engineering; Albany, New York
My research group at the Department of Electrical and Computer Engineering (ECE) at the University at Albany, SUNY, is hiring Ph.D. students on the Security of AI Hardware.

Responsibilities:
We are seeking students who are passionate about research, motivated to explore new ideas, and willing to work in a team environment. You will be expected to work diligently, communicate your results in writing, and publish research papers in top conferences/journals in the field of hardware security.

Qualifications:
A strong background in one or more of the following topics is required: linear algebra, probability theory, cryptography, or digital hardware design. Prior experience with Verilog hardware description language (HDL), electronic design automation (EDA) tools for application-specific integrated circuit (ASIC) design, or/and field programmable gate arrays (FPGAs) is preferred. The candidate is expected to have excellent verbal and written communication skills.

If you're interested, please reach out to me (spotluri@albany.edu) with your resume and transcripts.

Closing date for applications:
Contact: Dr. Seetal Potluri
More information: https://www.seetalpotluri.com/

Ph.D. Students in Cryptography
https://iacr.org/news/item/23113

Job Posting: Ph.D. Students in Cryptography

University of Wollongong, Australia
Multiple positions for PhD students are available at the Institute of Cybersecurity and Cryptology at the University of Wollongong.

Specifically, we are seeking for a PhD student who is interested to work in the area of "secure blockchain". The topic in the area of key-evolving signatures, proof of stake and blockchain, algorithm and security proofs, and will be expected to contribute to the research in key-evolving signatures and the applications in POS blockchain. If you are interested, please send your CV to: ic2.uow.scholarship@gmail.com.

We are also seeking for a PhD student to work in the topic of "Privacy-Preserving Information Linkage". The successful candidate will spend some time at the University of Surrey, London during their candidature. If you are interested with this topic, please contact Dr Khoa Nguyen (khoa at uow dot edu dot au).

These positions will be filled on the first come first served basis.
Closing date for applications:
Contact: Prof Willy Susilo

Postdoctoral Fellow
https://iacr.org/news/item/23112

Job Posting: Postdoctoral Fellow

University of Wollongong, Australia
We are looking for a postdoctoral research fellow (aka associate research fellow) to work in the topic of "secure blockchain". The successful candidate will be proficient with cryptography research, in the area of key-evolving signatures, proof of stake and blockchain, algorithm and security proofs, and will be expected to contribute to the research in key-evolving signatures and the applications in POS blockchain.
Closing date for applications:
Contact: Prof. Willy Susilo

Real-world Universal zkSNARKs are non-malleable
https://iacr.org/news/item/23116

ePrint Report: Real-world Universal zkSNARKs are non-malleable

Antonio Faonio, Dario Fiore, Luigi Russo
Simulation extractability is a strong security notion of zkSNARKs that guarantees that an attacker who produces a valid proof must know the corresponding witness, even if the attacker had prior access to proofs generated by other users. Notably, simulation extractability implies that proofs are non-malleable and is of fundamental importance for applications of zkSNARKs in distributed systems. In this work, we study sufficient and necessary conditions for constructing simulation-extractable universal zkSNARKs via the popular design approach based on compiling polynomial interactive oracle proofs (PIOP). Our main result is the first security proof that popular universal zkSNARKs, such as PLONK and Marlin, as deployed in the real world, are simulation-extractable. Our result fills a gap left from previous work (Faonio et al. TCC’23, and Kohlweiss et al. TCC’23) which could only prove the simulation extractability of the “textbook” versions of these schemes and does not capture their optimized variants, with all the popular optimization tricks in place, that are eventually implemented and deployed in software libraries.

MQ maps are not binding - Revisiting Multivariate Blind Signatures
https://iacr.org/news/item/23115

ePrint Report: MQ maps are not binding - Revisiting Multivariate Blind Signatures

Ward Beullens
In 2017, Petzoldt, Szepieniec, and Mohamed proposed a blind signature scheme, based on multivariate cryptography. This construction has been expanded on by several other works. This short paper shows that their construction is susceptible to an efficient polynomial-time attack. The problem is that the authors implicitly assumed that for a random multivariate quadratic map $\mathcal{R}:\mathbb{F}_q^m \rightarrow \mathbb{F}_q^m$ and a collision-resistant hash function $H: \{0,1\}^* \rightarrow \mathbb{F}_q^m$, the function $\mathsf{Com}(m;\mathbf{r}) := H(m) - \mathcal{R}(\mathbf{r})$ is a binding commitment. This paper shows that this is not the case. Given any pair of messages, one can efficiently produce a commitment that opens to both of them. We hope that by pointing out that multivariate quadratic maps are not binding, similar problems can be avoided in the future.

$\mathsf{OPA}$: One-shot Private Aggregation with Single Client Interaction and its Applications to Federated Learning
https://iacr.org/news/item/23118

ePrint Report: $\mathsf{OPA}$: One-shot Private Aggregation with Single Client Interaction and its Applications to Federated Learning

Harish Karthikeyan, Antigoni Polychroniadou
Our work aims to minimize interaction in secure computation due to the high cost and challenges associated with communication rounds, particularly in scenarios with many clients. In this work, we revisit the problem of secure aggregation in the single-server setting where a single evaluation server can securely aggregate client-held individual inputs. Our key contribution is One-shot Private Aggregation ($\mathsf{OPA}$) where clients speak only once (or even choose not to speak) per aggregation evaluation. Since every client communicates just once per aggregation, this streamlines the management of dropouts and dynamic participation of clients, contrasting with multi-round state-of-the-art protocols for each aggregation.


We initiate the study of $\mathsf{OPA}$ in several ways. First, we formalize the model and present a security definition. Second, we construct $\mathsf{OPA}$ protocols based on class groups, DCR, and LWR assumptions. Third, we demonstrate $\mathsf{OPA}$ with two applications: private stream aggregation and privacy-preserving federated learning. Specifically, $\mathsf{OPA}$ can be used as a key building block to enable privacy-preserving federated learning and critically, where client speaks once. This is a sharp departure from prior multi-round protocols whose study was initiated by Bonawitz et al. (CCS, 2017). Moreover, unlike the YOSO (You Only Speak Once) model for general secure computation, $\mathsf{OPA}$ eliminates complex committee selection protocols to achieve adaptive security. Beyond asymptotic improvements, $\mathsf{OPA}$ is practical, outperforming state-of-the-art solutions. We leverage $\mathsf{OPA}$ to develop a streaming variant named $\mathsf{SOPA}$, serving as the building block for privacy-preserving federated learning. We utilize $\mathsf{SOPA}$ to construct logistic regression classifiers for two datasets.


A new distributed key homomorphic PRF is at the core of our construction of $\mathsf{OPA}$. This key component addresses shortcomings observed in previous works that relied on DDH and LWR in the work of Boneh et al. (CRYPTO, 2013), marking it as an independent contribution to our work. Moreover, we also present new distributed key homomorphic PRFs based on class groups or DCR or the LWR assumption.

Ultrametric integral cryptanalysis
https://iacr.org/news/item/23117

ePrint Report: Ultrametric integral cryptanalysis

Tim Beyne, Michiel Verbauwhede
A systematic method to analyze \emph{divisibility properties} is proposed.
In integral cryptanalysis, divisibility properties interpolate between bits that sum to zero (divisibility by two) and saturated bits (divisibility by $2^{n - 1}$ for $2^n$ inputs).
From a theoretical point of view, we construct a new cryptanalytic technique that is a non-Archimedean multiplicative analogue of linear cryptanalysis. It lifts integral cryptanalysis to characteristic zero in the sense that, if all quantities are reduced modulo two, then one recovers the algebraic theory of integral cryptanalysis.
The new technique leads to a theory of trails. We develop a tool based on off-the-shelf solvers that automates the analysis of these trails and use it to show that many integral distinguishers on PRESENT and SIMON are stronger than expected.

MQ maps are not binding - Revisiting Multivariate Blind Signatures
https://eprint.iacr.org/2024/720

In 2017, Petzoldt, Szepieniec, and Mohamed proposed a blind signature scheme, based on multivariate cryptography. This construction has been expanded on by several other works. This short paper shows that their construction is susceptible to an efficient polynomial-time attack. The problem is that the authors implicitly assumed that for a random multivariate quadratic map $\mathcal{R}:\mathbb{F}_q^m \rightarrow \mathbb{F}_q^m$ and a collision-resistant hash function $H: \{0,1\}^* \rightarrow \mathbb{F}_q^m$, the function $\mathsf{Com}(m;\mathbf{r}) := H(m) - \mathcal{R}(\mathbf{r})$ is a binding commitment. This paper shows that this is not the case. Given any pair of messages, one can efficiently produce a commitment that opens to both of them. We hope that by pointing out that multivariate quadratic maps are not binding, similar problems can be avoided in the future.

Real-world Universal zkSNARKs are non-malleable
https://eprint.iacr.org/2024/721

Simulation extractability is a strong security notion of zkSNARKs that guarantees that an attacker who produces a valid proof must know the corresponding witness, even if the attacker had prior access to proofs generated by other users. Notably, simulation extractability implies that proofs are non-malleable and is of fundamental importance for applications of zkSNARKs in distributed systems. In this work, we study sufficient and necessary conditions for constructing simulation-extractable universal zkSNARKs via the popular design approach based on compiling polynomial interactive oracle proofs (PIOP). Our main result is the first security proof that popular universal zkSNARKs, such as PLONK and Marlin, as deployed in the real world, are simulation-extractable. Our result fills a gap left from previous work (Faonio et al. TCC’23, and Kohlweiss et al. TCC’23) which could only prove the simulation extractability of the “textbook” versions of these schemes and does not capture their optimized variants, with all the popular optimization tricks in place, that are eventually implemented and deployed in software libraries.

Ultrametric integral cryptanalysis
https://eprint.iacr.org/2024/722

A systematic method to analyze \emph{divisibility properties} is proposed.
In integral cryptanalysis, divisibility properties interpolate between bits that sum to zero (divisibility by two) and saturated bits (divisibility by $2^{n - 1}$ for $2^n$ inputs).
From a theoretical point of view, we construct a new cryptanalytic technique that is a non-Archimedean multiplicative analogue of linear cryptanalysis. It lifts integral cryptanalysis to characteristic zero in the sense that, if all quantities are reduced modulo two, then one recovers the algebraic theory of integral cryptanalysis.
The new technique leads to a theory of trails. We develop a tool based on off-the-shelf solvers that automates the analysis of these trails and use it to show that many integral distinguishers on PRESENT and SIMON are stronger than expected.

$\mathsf{OPA}$: One-shot Private Aggregation with Single Client Interaction and its Applications to Federated Learning
https://eprint.iacr.org/2024/723

Our work aims to minimize interaction in secure computation due to the high cost and challenges associated with communication rounds, particularly in scenarios with many clients. In this work, we revisit the problem of secure aggregation in the single-server setting where a single evaluation server can securely aggregate client-held individual inputs. Our key contribution is One-shot Private Aggregation ($\mathsf{OPA}$) where clients speak only once (or even choose not to speak) per aggregation evaluation. Since every client communicates just once per aggregation, this streamlines the management of dropouts and dynamic participation of clients, contrasting with multi-round state-of-the-art protocols for each aggregation.

We initiate the study of $\mathsf{OPA}$ in several ways. First, we formalize the model and present a security definition. Second, we construct $\mathsf{OPA}$ protocols based on class groups, DCR, and LWR assumptions. Third, we demonstrate $\mathsf{OPA}$ with two applications: private stream aggregation and privacy-preserving federated learning. Specifically, $\mathsf{OPA}$ can be used as a key building block to enable privacy-preserving federated learning and critically, where client speaks once. This is a sharp departure from prior multi-round protocols whose study was initiated by Bonawitz et al. (CCS, 2017). Moreover, unlike the YOSO (You Only Speak Once) model for general secure computation, $\mathsf{OPA}$ eliminates complex committee selection protocols to achieve adaptive security. Beyond asymptotic improvements, $\mathsf{OPA}$ is practical, outperforming state-of-the-art solutions. We leverage $\mathsf{OPA}$ to develop a streaming variant named $\mathsf{SOPA}$, serving as the building block for privacy-preserving federated learning. We utilize $\mathsf{SOPA}$ to construct logistic regression classifiers for two datasets.

A new distributed key homomorphic PRF is at the core of our construction of $\mathsf{OPA}$. This key component addresses shortcomings observed in previous works that relied on DDH and LWR in the work of Boneh et al. (CRYPTO, 2013), marking it as an independent contribution to our work. Moreover, we also present new distributed key homomorphic PRFs based on class groups or DCR or the LWR assumption.

IACR Statement On the War in Gaza
https://iacr.org/news/item/23119

Announcement: IACR Statement On the War in Gaza

https://www.iacr.org/petitions/gaza_war.html

AFT '24: Advances in Financial Technologies
https://iacr.org/news/item/23122

Event Calendar: AFT '24: Advances in Financial Technologies

Wien, Österreich, 23 September - 25 September 2024
Event date: 23 September to 25 September 2024

Submission deadline: 15 May 2024

Notification: 3 July 2024

UbiSec 2024: The 4th International Conference on Ubiquitous Security
https://iacr.org/news/item/23121

Event Calendar: UbiSec 2024: The 4th International Conference on Ubiquitous Security

changsha, China, 29 December - 31 December 2024
Event date: 29 December to 31 December 2024

Submission deadline: 15 July 2024

Notification: 15 August 2024

PRDC 2024: 29th IEEE Pacific Rim International Conference on Dependable Computing
https://iacr.org/news/item/23120

Event Calendar: PRDC 2024: 29th IEEE Pacific Rim International Conference on Dependable Computing

Osaka, Japan, 13 November - 15 November 2024
Event date: 13 November to 15 November 2024

Submission deadline: 31 July 2024

Notification: 31 August 2024

zkSNARKs in the ROM with Unconditional UC-Security
https://eprint.iacr.org/2024/724

The universal composability (UC) framework is a “gold standard” for security in cryptography. UC-secure protocols achieve strong security guarantees against powerful adaptive adversaries, and retain these guarantees when used as part of larger protocols. Zero knowledge succinct non-interactive arguments of knowledge (zkSNARKs) are a popular cryptographic primitive that are often used within larger protocols deployed in dynamic environments, and so UC-security is a highly desirable, if not necessary, goal.
In this paper we prove that there exist zkSNARKs in the random oracle model (ROM) that unconditionally achieve UC-security. Here, “unconditionally” means that security holds against adversaries that make a bounded number of queries to the random oracle, but are otherwise computationally unbounded.
Prior work studying UC-security for zkSNARKs obtains transformations that rely on computational assumptions and, in many cases, lose most of the succinctness property of the zkSNARK. Moreover, these transformations make the resulting zkSNARK more expensive and complicated.
In contrast, we prove that widely used zkSNARKs in the ROM are UC-secure without modifications. We prove that the Micali construction, which is the canonical construction of a zkSNARK, is UC-secure. Moreover, we prove that the BCS construction, which many zkSNARKs deployed in practice are based on, is UC-secure. Our results confirm the intuition that these natural zkSNARKs do not need to be augmented to achieve UC-security, and give confidence that their use in larger real-world systems is secure.

Let Attackers Program Ideal Models: Modularity and Composability for Adaptive Compromise
https://iacr.org/news/item/23126

ePrint Report: Let Attackers Program Ideal Models: Modularity and Composability for Adaptive Compromise

Joseph Jaeger
We show that the adaptive compromise security definitions of Jaeger and Tyagi (Crypto '20) cannot be applied in several natural use-cases. These include proving multi-user security from single-user security, the security of the cascade PRF, and the security of schemes sharing the same ideal primitive. We provide new variants of the definitions and show that they resolve these issues with composition. Extending these definitions to the asymmetric settings, we establish the security of the modular KEM/DEM and Fujisaki-Okamoto approaches to public key encryption in the full adaptive compromise setting. This allows instantiations which are more efficient and standard than prior constructions.