---
OA_place: repository
OA_type: green
_id: '19712'
abstract:
- lang: eng
  text: "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.\r\nAdditionally, 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."
acknowledgement: We thank Pierre Briaud and Morten Øygarden for helpful discussions
  on algebraic attacks on RSD, and the EC reviewers for helpful comments.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Miguel
  full_name: Cueto Noval, Miguel
  id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
  last_name: Cueto Noval
  orcid: 0000-0002-2505-4246
- first_name: Simon-Philipp
  full_name: Merz, Simon-Philipp
  last_name: Merz
- first_name: Patrick
  full_name: Stählin, Patrick
  last_name: Stählin
- first_name: Akin
  full_name: Ünal, Akin
  id: f6b56fb6-dc63-11ee-9dbf-f6780863a85a
  last_name: Ünal
  orcid: 0000-0002-8929-0221
citation:
  ama: 'Cueto Noval M, Merz S-P, Stählin P, Ünal A. On the soundness of algebraic
    attacks against code-based assumptions. In: <i>44th Annual International Conference
    on the Theory and Applications of Cryptographic Techniques</i>. Vol 15606. Springer
    Nature; 2025:385-415. doi:<a href="https://doi.org/10.1007/978-3-031-91095-1_14">10.1007/978-3-031-91095-1_14</a>'
  apa: 'Cueto Noval, M., Merz, S.-P., Stählin, P., &#38; Ünal, A. (2025). On the soundness
    of algebraic attacks against code-based assumptions. In <i>44th Annual International
    Conference on the Theory and Applications of Cryptographic Techniques</i> (Vol.
    15606, pp. 385–415). Madrid, Spain: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-91095-1_14">https://doi.org/10.1007/978-3-031-91095-1_14</a>'
  chicago: Cueto Noval, Miguel, Simon-Philipp Merz, Patrick Stählin, and Akin Ünal.
    “On the Soundness of Algebraic Attacks against Code-Based Assumptions.” In <i>44th
    Annual International Conference on the Theory and Applications of Cryptographic
    Techniques</i>, 15606:385–415. Springer Nature, 2025. <a href="https://doi.org/10.1007/978-3-031-91095-1_14">https://doi.org/10.1007/978-3-031-91095-1_14</a>.
  ieee: M. Cueto Noval, S.-P. Merz, P. Stählin, and A. Ünal, “On the soundness of algebraic
    attacks against code-based assumptions,” in <i>44th Annual International Conference
    on the Theory and Applications of Cryptographic Techniques</i>, Madrid, Spain,
    2025, vol. 15606, pp. 385–415.
  ista: 'Cueto Noval M, Merz S-P, Stählin P, Ünal A. 2025. On the soundness of algebraic
    attacks against code-based assumptions. 44th Annual International Conference on
    the Theory and Applications of Cryptographic Techniques. EUROCRYPT: International
    Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol.
    15606, 385–415.'
  mla: Cueto Noval, Miguel, et al. “On the Soundness of Algebraic Attacks against
    Code-Based Assumptions.” <i>44th Annual International Conference on the Theory
    and Applications of Cryptographic Techniques</i>, vol. 15606, Springer Nature,
    2025, pp. 385–415, doi:<a href="https://doi.org/10.1007/978-3-031-91095-1_14">10.1007/978-3-031-91095-1_14</a>.
  short: M. Cueto Noval, S.-P. Merz, P. Stählin, A. Ünal, in:, 44th Annual International
    Conference on the Theory and Applications of Cryptographic Techniques, Springer
    Nature, 2025, pp. 385–415.
conference:
  end_date: 2025-05-08
  location: Madrid, Spain
  name: 'EUROCRYPT: International Conference on the Theory and Applications of Cryptographic
    Techniques'
  start_date: 2025-05-04
corr_author: '1'
date_created: 2025-05-19T14:15:01Z
date_published: 2025-04-28T00:00:00Z
date_updated: 2025-05-28T06:12:39Z
day: '28'
department:
- _id: KrPi
doi: 10.1007/978-3-031-91095-1_14
intvolume: '     15606'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.research-collection.ethz.ch/handle/20.500.11850/732894
month: '04'
oa: 1
oa_version: Submitted Version
page: 385-415
publication: 44th Annual International Conference on the Theory and Applications of
  Cryptographic Techniques
publication_identifier:
  eisbn:
  - '9783031910951'
  eissn:
  - 1611-3349
  isbn:
  - '9783031910944'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the soundness of algebraic attacks against code-based assumptions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15606
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '20846'
abstract:
- lang: eng
  text: "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.\r\nWe 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.\r\nWe 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).\r\nWe 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+.\r\nLast,
    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."
acknowledgement: "We thank Jonas Steinbach and Gertjan De Mulder for helpful discussions
  on BIP 32, Dennis Hofheinz and Julia Kastner for helpful discussions on early prototypes
  of our CVRF, and Klaus Kraßnitzer for running pairing benchmarks on his MacBook
  Pro.\r\nChristoph U. Günther: This research was funded in whole or in part by the
  Austrian Science Fund (FWF) 10.55776/F85. For open access purposes, the author has
  applied a CC BY public copyright license to any author-accepted manuscript version
  arising from this submission."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Nicholas
  full_name: Brandt, Nicholas
  last_name: Brandt
- first_name: Miguel
  full_name: Cueto Noval, Miguel
  id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
  last_name: Cueto Noval
  orcid: 0000-0002-2505-4246
- first_name: Christoph Ullrich
  full_name: Günther, Christoph Ullrich
  id: ec98511c-eb8e-11eb-b029-edd25d7271a1
  last_name: Günther
- first_name: Akin
  full_name: Ünal, Akin
  id: f6b56fb6-dc63-11ee-9dbf-f6780863a85a
  last_name: Ünal
  orcid: 0000-0002-8929-0221
- first_name: Stella
  full_name: Wohnig, Stella
  last_name: Wohnig
citation:
  ama: 'Brandt N, Cueto Noval M, Günther CU, Ünal A, Wohnig S. Constrained verifiable
    random functions without obfuscation and friends. In: <i>23rd International Conference
    on Theory of Cryptography</i>. Vol 16271. Springer Nature; 2025:478-511. doi:<a
    href="https://doi.org/10.1007/978-3-032-12290-2_16">10.1007/978-3-032-12290-2_16</a>'
  apa: 'Brandt, N., Cueto Noval, M., Günther, C. U., Ünal, A., &#38; Wohnig, S. (2025).
    Constrained verifiable random functions without obfuscation and friends. In <i>23rd
    International Conference on Theory of Cryptography</i> (Vol. 16271, pp. 478–511).
    Aarhus, Denmark: Springer Nature. <a href="https://doi.org/10.1007/978-3-032-12290-2_16">https://doi.org/10.1007/978-3-032-12290-2_16</a>'
  chicago: Brandt, Nicholas, Miguel Cueto Noval, Christoph Ullrich Günther, Akin Ünal,
    and Stella Wohnig. “Constrained Verifiable Random Functions without Obfuscation
    and Friends.” In <i>23rd International Conference on Theory of Cryptography</i>,
    16271:478–511. Springer Nature, 2025. <a href="https://doi.org/10.1007/978-3-032-12290-2_16">https://doi.org/10.1007/978-3-032-12290-2_16</a>.
  ieee: N. Brandt, M. Cueto Noval, C. U. Günther, A. Ünal, and S. Wohnig, “Constrained
    verifiable random functions without obfuscation and friends,” in <i>23rd International
    Conference on Theory of Cryptography</i>, Aarhus, Denmark, 2025, vol. 16271, pp.
    478–511.
  ista: 'Brandt N, Cueto Noval M, Günther CU, Ünal A, Wohnig S. 2025. Constrained
    verifiable random functions without obfuscation and friends. 23rd International
    Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol.
    16271, 478–511.'
  mla: Brandt, Nicholas, et al. “Constrained Verifiable Random Functions without Obfuscation
    and Friends.” <i>23rd International Conference on Theory of Cryptography</i>,
    vol. 16271, Springer Nature, 2025, pp. 478–511, doi:<a href="https://doi.org/10.1007/978-3-032-12290-2_16">10.1007/978-3-032-12290-2_16</a>.
  short: N. Brandt, M. Cueto Noval, C.U. Günther, A. Ünal, S. Wohnig, in:, 23rd International
    Conference on Theory of Cryptography, Springer Nature, 2025, pp. 478–511.
conference:
  end_date: 2025-12-05
  location: Aarhus, Denmark
  name: 'TCC: Theory of Cryptography'
  start_date: 2025-12-01
corr_author: '1'
date_created: 2025-12-21T23:01:34Z
date_published: 2025-12-05T00:00:00Z
date_updated: 2025-12-29T11:11:29Z
day: '05'
department:
- _id: KrPi
doi: 10.1007/978-3-032-12290-2_16
intvolume: '     16271'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2025/1045
month: '12'
oa: 1
oa_version: Preprint
page: 478-511
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
  grant_number: F8509
  name: Security and Privacy by Design for Complex Systems
publication: 23rd International Conference on Theory of Cryptography
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783032122896'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Constrained verifiable random functions without obfuscation and friends
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16271
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '18756'
abstract:
- lang: eng
  text: "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:\r\n(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.\r\n\r\n(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.\r\n\r\n(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."
acknowledgement: The authors thank the anonymous reviewers for insightful comments
  which very much improved this work, in particular, sharing with us the counterexamples
  against a prior version of Hiding Evasive LWE, and against public-coin Evasive LWE
  when the sampler inputs B. Chris Brzuska and Ivy K. Y. Woo are supported by Research
  Council of Finland grant 358950. We thank Russell W. F. Lai and Hoeteck Wee for
  helpful discussions.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Chris
  full_name: Brzuska, Chris
  last_name: Brzuska
- first_name: Akin
  full_name: Ünal, Akin
  id: f6b56fb6-dc63-11ee-9dbf-f6780863a85a
  last_name: Ünal
  orcid: 0000-0002-8929-0221
- first_name: Ivy K.Y.
  full_name: Woo, Ivy K.Y.
  last_name: Woo
citation:
  ama: 'Brzuska C, Ünal A, Woo IKY. Evasive LWE assumptions: Definitions, classes,
    and counterexamples. In: <i>30th International Conference on the Theory and Application
    of Cryptology and Information Security</i>. Vol 15487. Springer Nature; 2024:418-449.
    doi:<a href="https://doi.org/10.1007/978-981-96-0894-2_14">10.1007/978-981-96-0894-2_14</a>'
  apa: 'Brzuska, C., Ünal, A., &#38; Woo, I. K. Y. (2024). Evasive LWE assumptions:
    Definitions, classes, and counterexamples. In <i>30th International Conference
    on the Theory and Application of Cryptology and Information Security</i> (Vol.
    15487, pp. 418–449). Kolkata, India: Springer Nature. <a href="https://doi.org/10.1007/978-981-96-0894-2_14">https://doi.org/10.1007/978-981-96-0894-2_14</a>'
  chicago: 'Brzuska, Chris, Akin Ünal, and Ivy K.Y. Woo. “Evasive LWE Assumptions:
    Definitions, Classes, and Counterexamples.” In <i>30th International Conference
    on the Theory and Application of Cryptology and Information Security</i>, 15487:418–49.
    Springer Nature, 2024. <a href="https://doi.org/10.1007/978-981-96-0894-2_14">https://doi.org/10.1007/978-981-96-0894-2_14</a>.'
  ieee: 'C. Brzuska, A. Ünal, and I. K. Y. Woo, “Evasive LWE assumptions: Definitions,
    classes, and counterexamples,” in <i>30th International Conference on the Theory
    and Application of Cryptology and Information Security</i>, Kolkata, India, 2024,
    vol. 15487, pp. 418–449.'
  ista: 'Brzuska C, Ünal A, Woo IKY. 2024. Evasive LWE assumptions: Definitions, classes,
    and counterexamples. 30th International Conference on the Theory and Application
    of Cryptology and Information Security. ASIACRYPT: Conference on the Theory and
    Application of Cryptology and Information Security, LNCS, vol. 15487, 418–449.'
  mla: 'Brzuska, Chris, et al. “Evasive LWE Assumptions: Definitions, Classes, and Counterexamples.”
    <i>30th International Conference on the Theory and Application of Cryptology and
    Information Security</i>, vol. 15487, Springer Nature, 2024, pp. 418–49, doi:<a
    href="https://doi.org/10.1007/978-981-96-0894-2_14">10.1007/978-981-96-0894-2_14</a>.'
  short: C. Brzuska, A. Ünal, I.K.Y. Woo, in:, 30th International Conference on the
    Theory and Application of Cryptology and Information Security, Springer Nature,
    2024, pp. 418–449.
conference:
  end_date: 2024-12-13
  location: Kolkata, India
  name: 'ASIACRYPT: Conference on the Theory and Application of Cryptology and Information
    Security'
  start_date: 2024-12-09
date_created: 2025-01-05T23:01:56Z
date_published: 2024-12-13T00:00:00Z
date_updated: 2025-09-09T12:00:51Z
day: '13'
department:
- _id: KrPi
doi: 10.1007/978-981-96-0894-2_14
external_id:
  isi:
  - '001443890800014'
intvolume: '     15487'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2024/2000
month: '12'
oa: 1
oa_version: Preprint
page: 418-449
publication: 30th International Conference on the Theory and Application of Cryptology
  and Information Security
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9789819608935'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Evasive LWE assumptions: Definitions, classes, and counterexamples'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 15487
year: '2024'
...
---
_id: '17126'
abstract:
- lang: eng
  text: "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.\r\n\r\nIn 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."
acknowledgement: We want to thank the anonymous reviewers of TCC and Eurocrypt for
  their very helpful comments and suggestions. This work has received funding from
  the Austrian Science Fund (FWF) and netidee SCIENCE via grant P31621-N38 (PROFET).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Erkan
  full_name: Tairi, Erkan
  last_name: Tairi
- first_name: Akin
  full_name: Ünal, Akin
  id: f6b56fb6-dc63-11ee-9dbf-f6780863a85a
  last_name: Ünal
  orcid: 0000-0002-8929-0221
citation:
  ama: 'Tairi E, Ünal A. Lower bounds for lattice-based compact functional encryption.
    In: <i>Advances in Cryptology – EUROCRYPT 2024</i>. Vol 14652. Springer Nature;
    2024:249-279. doi:<a href="https://doi.org/10.1007/978-3-031-58723-8_9">10.1007/978-3-031-58723-8_9</a>'
  apa: 'Tairi, E., &#38; Ünal, A. (2024). Lower bounds for lattice-based compact functional
    encryption. In <i>Advances in Cryptology – EUROCRYPT 2024</i> (Vol. 14652, pp.
    249–279). Zurich, Switzerland: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-58723-8_9">https://doi.org/10.1007/978-3-031-58723-8_9</a>'
  chicago: Tairi, Erkan, and Akin Ünal. “Lower Bounds for Lattice-Based Compact Functional
    Encryption.” In <i>Advances in Cryptology – EUROCRYPT 2024</i>, 14652:249–79.
    Springer Nature, 2024. <a href="https://doi.org/10.1007/978-3-031-58723-8_9">https://doi.org/10.1007/978-3-031-58723-8_9</a>.
  ieee: E. Tairi and A. Ünal, “Lower bounds for lattice-based compact functional encryption,”
    in <i>Advances in Cryptology – EUROCRYPT 2024</i>, Zurich, Switzerland, 2024,
    vol. 14652, pp. 249–279.
  ista: 'Tairi E, Ünal A. 2024. Lower bounds for lattice-based compact functional
    encryption. Advances in Cryptology – EUROCRYPT 2024. EUROCRYPT: Theory and Applications
    of Cryptographic Techniques, LNCS, vol. 14652, 249–279.'
  mla: Tairi, Erkan, and Akin Ünal. “Lower Bounds for Lattice-Based Compact Functional
    Encryption.” <i>Advances in Cryptology – EUROCRYPT 2024</i>, vol. 14652, Springer
    Nature, 2024, pp. 249–79, doi:<a href="https://doi.org/10.1007/978-3-031-58723-8_9">10.1007/978-3-031-58723-8_9</a>.
  short: E. Tairi, A. Ünal, in:, Advances in Cryptology – EUROCRYPT 2024, Springer
    Nature, 2024, pp. 249–279.
conference:
  end_date: 2024-05-30
  location: Zurich, Switzerland
  name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
  start_date: 2024-05-26
date_created: 2024-06-09T22:01:03Z
date_published: 2024-05-08T00:00:00Z
date_updated: 2025-09-08T07:48:18Z
day: '08'
department:
- _id: KrPi
doi: 10.1007/978-3-031-58723-8_9
external_id:
  isi:
  - '001278247600009'
intvolume: '     14652'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2023/719.pdf
month: '05'
oa: 1
oa_version: Submitted Version
page: 249-279
publication: Advances in Cryptology – EUROCRYPT 2024
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783031587221'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lower bounds for lattice-based compact functional encryption
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 14652
year: '2024'
...