@inproceedings{19712,
  abstract     = {We study recent algebraic attacks (Briaud-Øygarden EC’23) on the Regular Syndrome Decoding (RSD) problem and the assumptions underlying the correctness of their attacks’ complexity estimates. By relating these assumptions to interesting algebraic-combinatorial problems, we prove that they do not hold in full generality. However, we show that they are (asymptotically) true for most parameter sets, supporting the soundness of algebraic attacks on RSD. Further, we prove—without any heuristics or assumptions—that RSD can be broken in polynomial time whenever the number of error blocks times the square of the size of error blocks is larger than 2 times the square of the dimension of the code.
Additionally, we use our methodology to attack a variant of the Learning With Errors problem where each error term lies in a fixed set of constant size. We prove that this problem can be broken in polynomial time, given a sufficient number of samples. This result improves on the seminal work by Arora and Ge (ICALP’11), as the attack’s time complexity is independent of the LWE modulus.},
  author       = {Cueto Noval, Miguel and Merz, Simon-Philipp and Stählin, Patrick and Ünal, Akin},
  booktitle    = {44th Annual International Conference on the Theory and Applications of Cryptographic Techniques},
  isbn         = {9783031910944},
  issn         = {1611-3349},
  location     = {Madrid, Spain},
  pages        = {385--415},
  publisher    = {Springer Nature},
  title        = {{On the soundness of algebraic attacks against code-based assumptions}},
  doi          = {10.1007/978-3-031-91095-1_14},
  volume       = {15606},
  year         = {2025},
}

@inproceedings{20846,
  abstract     = {CVRFs are PRFs that unify the properties of verifiable and constrained PRFs. Since they were introduced concurrently by Fuchsbauer and Chandran-Raghuraman-Vinayagamurthy in 2014, it has been an open problem to construct CVRFs without using heavy machinery such as multilinear maps, obfuscation or functional encryption.
We solve this problem by constructing a prefix-constrained verifiable PRF that does not rely on the aforementioned assumptions. Essentially, our construction is a verifiable version of the Goldreich-Goldwasser-Micali PRF. To achieve verifiability we leverage degree-2 algebraic PRGs and bilinear groups. In short, proofs consist of intermediate values of the Goldreich-Goldwasser-Micali PRF raised to the exponents of group elements. These outputs can be verified using pairings since the underlying PRG is of degree 2.
We prove the selective security of our construction under the Decisional Square Diffie-Hellman (DSDH) assumption and a new assumption, which we dub recursive Decisional Diffie-Hellman (recursive DDH).
We prove the soundness of recursive DDH in the generic group model assuming the hardness of the Multivariate Quadratic (MQ) problem and a new variant thereof, which we call MQ+.
Last, in terms of applications, we observe that our CVRF is also an exponent (C)VRF in the plain model. Exponent VRFs were recently introduced by Boneh et al. (Eurocrypt’25) with various applications to threshold cryptography in mind. In addition to that, we give further applications for prefix-CVRFs in the blockchain setting, namely, stake-pooling and compressible randomness beacons.},
  author       = {Brandt, Nicholas and Cueto Noval, Miguel and Günther, Christoph Ullrich and Ünal, Akin and Wohnig, Stella},
  booktitle    = {23rd International Conference on Theory of Cryptography},
  isbn         = {9783032122896},
  issn         = {1611-3349},
  location     = {Aarhus, Denmark},
  pages        = {478--511},
  publisher    = {Springer Nature},
  title        = {{Constrained verifiable random functions without obfuscation and friends}},
  doi          = {10.1007/978-3-032-12290-2_16},
  volume       = {16271},
  year         = {2025},
}

@inproceedings{18756,
  abstract     = {The evasive LWE assumption, proposed by Wee [Eurocrypt’22 Wee] for constructing a lattice-based optimal broadcast encryption, has shown to be a powerful assumption, adopted by subsequent works to construct advanced primitives ranging from ABE variants to obfuscation for null circuits. However, a closer look reveals significant differences among the precise assumption statements involved in different works, leading to the fundamental question of how these assumptions compare to each other. In this work, we initiate a more systematic study on evasive LWE assumptions:
(i) Based on the standard LWE assumption, we construct simple counterexamples against three private-coin evasive LWE variants, used in [Crypto’22 Tsabary, Asiacrypt’22 VWW, Crypto’23 ARYY] respectively, showing that these assumptions are unlikely to hold.

(ii) Based on existing evasive LWE variants and our counterexamples, we propose and define three classes of plausible evasive LWE assumptions, suitably capturing all existing variants for which we are not aware of non-obfuscation-based counterexamples.

(iii) We show that under our assumption formulations, the security proofs of [Asiacrypt’22 VWW] and [Crypto’23 ARYY] can be recovered, and we reason why the security proof of [Crypto’22 Tsabary] is also plausibly repairable using an appropriate evasive LWE assumption.},
  author       = {Brzuska, Chris and Ünal, Akin and Woo, Ivy K.Y.},
  booktitle    = {30th International Conference on the Theory and Application of Cryptology and Information Security},
  isbn         = {9789819608935},
  issn         = {1611-3349},
  location     = {Kolkata, India},
  pages        = {418--449},
  publisher    = {Springer Nature},
  title        = {{Evasive LWE assumptions: Definitions, classes, and counterexamples}},
  doi          = {10.1007/978-981-96-0894-2_14},
  volume       = {15487},
  year         = {2024},
}

@inproceedings{17126,
  abstract     = {Functional encryption (FE) is a primitive where the holder of a master secret key can control which functions a user can evaluate on encrypted data. It is a powerful primitive that even implies indistinguishability obfuscation (iO), given sufficiently compact ciphertexts (Ananth-Jain, CRYPTO’15 and Bitansky-Vaikuntanathan, FOCS’15). However, despite being extensively studied, there are FE schemes, such as function-hiding inner-product FE (Bishop-Jain-Kowalczyk, AC’15, Abdalla-Catalano-Fiore-Gay-Ursu, CRYPTO’18) and compact quadratic FE (Baltico-Catalano-Fiore-Gay, Lin, CRYPTO’17), that can be only realized using pairings. This raises the question if there are some mathematical barriers that hinder us from realizing these FE schemes from other assumptions.

In this paper, we study the difficulty of constructing lattice-based compact FE. We generalize the impossibility results of Ünal (EC’20) for lattice-based function-hiding FE, and extend it to the case of compact FE. Concretely, we prove lower bounds for lattice-based compact FE schemes which meet some (natural) algebraic restrictions at encryption and decryption, and have ciphertexts of linear size and secret keys of minimal degree. We see our results as important indications of why it is hard to construct lattice-based FE schemes for new functionalities, and which mathematical barriers have to be overcome.},
  author       = {Tairi, Erkan and Ünal, Akin},
  booktitle    = {Advances in Cryptology – EUROCRYPT 2024},
  isbn         = {9783031587221},
  issn         = {1611-3349},
  location     = {Zurich, Switzerland},
  pages        = {249--279},
  publisher    = {Springer Nature},
  title        = {{Lower bounds for lattice-based compact functional encryption}},
  doi          = {10.1007/978-3-031-58723-8_9},
  volume       = {14652},
  year         = {2024},
}