International Association
for Cryptologic Research

The vanishing short integer solution (vSIS) assumption [Cini-Lai-Malavolta, Crypto'23], at its simplest form, asserts the hardness of finding a polynomial with short coefficients which vanishes at a given random point. While vSIS has proven to be useful in applications such as succinct arguments, not much is known about its theoretical hardness. Furthermore, without the ability to generate a hard instance together with a trapdoor, the applicability of vSIS is significantly limited.

We revisit the vSIS assumption focusing on the univariate single-point constant-degree setting, which can be seen as a generalisation of the (search) NTRU problem. In such a setting, we show that the vSIS problem is as hard as finding the shortest vector in certain ideal lattices. We also show how to generate a random vSIS instance together with a trapdoor, under the (decision) NTRU assumption. Interestingly, a vSIS trapdoor allows to sample polynomials of short coefficients which evaluate to any given value at the public point. By exploiting the multiplicativity of the polynomial ring, we use vSIS trapdoors to build a new homomorphic signature scheme for low-degree polynomials.

We point out flaw in zero-knowledge of the CROSS identification protocol, $\textsf{CROSS-ID}$, which allows a distinguisher to distinguish real and simulated transcripts given access to the witness. Moreover, we show that the real and simulated transcripts are not statistically indistinguishable, and therefore the protocol can only satisfy weak computational (rather than strong, statistical or perfect) Honest Verifier Zero-knowledge. This issue is still present in version 2.0 updated on January 31, 2025, which resolves the security losses attained via the attacks of [BLP+25]

A memory checker is an algorithmic tool used to certify the integrity of a database maintained on a remote, unreliable, computationally bounded server. Concretely, it allows a user to issue instructions to the server and after every instruction, obtain either the correct value or a failure (but not an incorrect answer) with high probability. A recent result due to Boyle, Komargodski, and Vafa (BKV, STOC '24) showed a tradeoff between the size of the local storage and the number of queries the memory checker makes to the server upon every logical instruction. Specifically, they show that every non-trivial memory checker construction with inverse-polynomial soundness and local storage at most $n^{1 - \epsilon}$ must make $\Omega(\log n/ \log \log n)$ queries, and this is tight up to constant factors given known constructions. However, an intriguing question is whether natural relaxations of the security guarantee could allow for more efficient constructions.

We consider and adapt the notion of covert security to the memory checking context, wherein the adversary can effectively cheat while taking the risk of being caught with constant probability. Notably, BKV's lower bound does not apply in this setting.

We close this gap and prove that $\Omega(\log n/ \log \log n)$ overhead is unavoidable even in the covert security setting. Our lower bound applies to any memory checker construction, including ones that use randomness and adaptivity and ones that rely on cryptographic assumptions and/or the random oracle model, as long as they satisfy a natural "read-only reads" property. This property requires a memory checker not to modify contents of the database or local storage in the execution of a logical read instruction.

Pulsars exhibit signals with precise inter-arrival times that are on the order of milliseconds to seconds depending on the individual pulsar. There is subtle variation in the timing of pulsar signals, primarily due to the presence of gravitational waves, intrinsic variance in the period of the pulsar, and errors in the realization of Terrestrial Time (TT). Traditionally, these variations are dismissed as noise in high-precision timing experiments. In this paper, we show that these variations serve as a natural entropy source for the creation of Random Number Generators (RNG). We also explore the effects of using randomness extractors to increase the entropy of random bits extracted from Pulsar timing data. To evaluate the quality of the Pulsar RNG, we model its entropy as a $k$-source and use well-known cryptographic results to show its closeness to a theoretically ideal uniformly random source. To remain consistent with prior work, we also show that the Pulsar RNG passes well-known statistical tests such as the NIST test suite.

Efficient anonymous credentials are typically constructed by combining proof-friendly signature schemes with compatible zero-knowledge proof systems. Inspired by pairing-based proof-friendly signatures such as Boneh- Boyen (BB) and Boneh-Boyen-Shacham (BBS), we propose a wide family of lattice-based proof-friendly signatures based on variants of the vanishing short integer solution (vSIS) assumption [Cini-Lai-Malavolta, Crypto'23]. In particular, we obtain natural lattice-based adaptions of BB and BBS which, similar to their pairing-based counterparts, admit nice algebraic properties.

[Bootle-Lyubashevsky-Nguyen-Sorniotti, Crypto'23] (BLNS) recently proposed a framework for constructing lattice-based proof-friendly signatures and anonymous credentials, based on another new lattice assumption called $\mathsf{ISIS}_f$ parametrised by a fixed function $f$, with focus on $f$ being the binary decomposition. We introduce a generalised $\mathsf{ISIS}_f$ framework, called $\mathsf{GenISIS}_f$, with a keyed and probabilistic function $f$. For example, picking $f_b(\mu) = 1/(b-\mu)$ with key $b$ for short ring element $\mu$ leads to algebraic and thus proof-friendly signatures. To better gauge the robustness and proof-friendliness of $\mathsf{(Gen)}\mathsf{ISIS}_f$, we consider what happens when the inputs to $f$ are chosen selectively (or even adaptively) by the adversary, and the behaviour under relaxed norm checks. While bit decomposition quickly becomes insecure, our proposed function families seem robust.

Multi-signatures allow to combine several individual signatures into a compact one and verify it against a short aggregated key. Compared to threshold signatures, multi-signatures enjoy non-interactive key generation but give up on the threshold-setting. Recent works by Das et al. (CCS'23) and Garg et al. (S&P'24) show how multi-signatures can be turned into schemes that enable efficient verification when an ad hoc threshold -- determined only at verification -- is satisfied. This allows to keep the simple key generation of multi-signatures and support flexible threshold settings in the signing process later on. Both works use the same idea of combining BLS multi-signatures with inner-product proofs over committed keys. Das et al. give a somewhat generic proof from both building blocks, which we show to be flawed, whereas Garg et al. give a direct proof for the combined construction in the algebraic group model.

In this work, we identify the common blueprint used in both works and abstract the proof-based approach through the building block of a commit-and-prove system for vectors (CP). We formally define a flexible set of security properties for the CP system and show how it can be securely combined with a multi-signature to yield a signature with ad hoc thresholds. Our scheme also lifts the threshold signatures into the multiverse setting recently introduced by Baird et al. (S&P'23), which allows signers to re-use their long-term keys across several groups. The challenge in the generic construction is to express -- and realize -- the combination of homomorphic proofs and commitments (needed to realize flexible thresholds over fixed group keys) and their simulation extractability (needed in the threshold signature security proof). We finally show that a CP instantiation closely following the ideas of Das et al. can be proven secure, but requires a new flexible-base DL-assumption to do so.

Event date: 6 March to 7 March 2025

Event date: 19 August to 20 August 2025
Submission deadline: 17 April 2025
Notification: 19 June 2025

Event date: to
Submission deadline: 15 March 2025
Notification: 30 June 2025

Event date: 1 October 2025
Submission deadline: 28 April 2025
Notification: 1 July 2025

Event date: 2 June to 5 June 2025

Event date: 16 March 2025

Your Working Environment

The Chair of Hardware/Software Co-Design at FAU explores methodologies for designing and optimizing computing systems with high demands on availability, performance, and security.

Project Description

Ensuring security in IoT systems, particularly confidentiality and integrity of data and application code, is a major challenge. While hardware security, crypto modules, secure boot, and trusted execution environments offer protection, they often increase costs and energy consumption.

This position focuses on system-level design automation for secure embedded systems-on-chip. The goal is to develop a methodology for design space exploration that generates secure architectures and evaluates countermeasures' impact on security, energy, cost, and performance. Additionally, the research includes high-level synthesis techniques to implement secure design candidates as FPGA-based system-on-chip prototypes.

Your Tasks and Opportunities

• Conduct research in embedded computer architectures and hardware security.
• Explore security-aware hardware/software co-design, system-level design space exploration, and multi-objective optimization.
• Apply high-level synthesis techniques to integrate security mechanisms into SoC designs and prototype them on FPGA platforms.

Your Profile

• Master’s degree in Computer Science, Electrical Engineering, or a related field.
• Skills and interest in computer architecture, hardware security, system-level design automation, object-oriented programming, hardware description languages, SoC design, RISC-V, or FPGA tools.
• Team-oriented, open-minded, and communicative, with an interest in both theoretical and practical aspects of embedded systems.
• High proficiency in English (German is a plus).

Closing date for applications:

Contact: Jürgen Teich ([email protected]), Stefan Wildermann ([email protected])

Event date: 24 June 2025
Submission deadline: 21 March 2025
Notification: 22 April 2025

The Department of Combinatorics and Optimization at the University of Waterloo invites applications from qualified candidates for 2-year postdoctoral fellowship appointments in post-quantum cryptography under the supervision of Prof. David Jao, Prof. Michele Mosca, and Prof. Douglas Stebila.

A Ph.D. degree and evidence of excellence in research are required. Successful applicants are expected to maintain an active program of research, and participate in research activities with academic and industry partners in the grant. The annual salary is 70,000 CAD. In addition, a travel fund of 3,000 CAD per year is provided. The positions are available immediately.

Interested individuals should apply using the MathJobs site (https://www.mathjobs.org/jobs/list/26357/). Applications should include a cover letter describing their interest in the position, a curriculum vitae and research statement and at least three reference letters.

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within our Indigenous Initiatives Office.

The University regards equity and diversity as an integral part of academic excellence and is committed to accessibility for all employees. We encourage applications from candidates who have been historically disadvantaged and marginalized, including applicants who identify as Indigenous peoples (e.g., First Nations, Métis, Inuit/Inuk), Black, racialized, people with disabilities, women and/or 2SLGBTQ+. If you have any application, interview or workplace accommodation requests, please contact Carol Seely-Morrison ([email protected]).

All qualified candidates are encouraged to apply; however, Canadians and permanent residents will be given priority.

Closing date for applications:

Contact: Douglas Stebila ([email protected])

More information: https://www.mathjobs.org/jobs/list/26357

As part of a collaborative project on data protection, we are recruiting a PhD student to carry out research on advanced cryptography (e.g. homomorphic encryption, multiparty computation). Candidates should have a strong background in cryptography. The thesis must be completed by the end of December 2025.

Closing date for applications:

Contact: Sébastien Canard ([email protected]), Qingju Wang ([email protected])

We are inviting applications for PhD student scholarships in the School of Computer Science, Faculty of Science, Queensland University of Technology (QUT). Students who are interested in cryptographic applications of algebraic curves are encouraged to apply to work on one of the following two areas:

- Isogeny-based post-quantum cryptography
- Constructive and computational aspects of zk-SNARKs

Applicants should have a strong background in mathematics and/or computer science and be highly motivated for research work with a demonstrated ability to work independently. Applications (cover letter, CV, transcripts, contacts for references) can be emailed to Craig Costello with "PhD applicant - YOUR NAME" in the subject. Applications will be processed continuously until the positions are filled.

Closing date for applications:

Contact: [email protected]

Since this position requires Swedish citizenship, the below description of the position is available in Swedish only.

Centrum för cyberförsvar och informationssäkerhet (CDIS) vid KTH — som är ett samarbete mellan KTH och Försvarsmakten, samt vissa andra myndigheter — söker doktorander. Det rör sig om en bred utlysning inom cybersäkerhetsområdet. Vi vill här särskilt peka ut en möjlig specialisering inom kryptologiområdet.

Mer specifikt har KTH i samarbete med avdelningen för krypto och IT-säkerhet vid Must pågående spetsforskning som syftar till att möta de utmaningar som följer av kvantdatorutvecklingen. Vi söker nu inom ramen för CDIS utlysning en doktorand som kan bidra till den forskningen.

Doktoranden kommer att handledas av Johan Håstad och/eller Douglas Wikström. Forskningssatsningen omfattar även Martin Ekerå och Joel Gärtner. Vid intresse, sök en av de av CDIS utlysta doktorandtjänsterna.

Tjänsten kommer att omfatta 80% doktorandstudier vid KTH och 20% placering vid Must där möjlighet ges att arbeta med några av Sveriges främsta kryptologer. Resultatet för doktoranden blir en unik kombination av teori och praktik inom kryptologiområdet.

För ytterligare information, kontakta Johan Håstad ([email protected]) eller Martin Ekerå ([email protected]).

Sista ansökningsdag är den 13 mars 2025. Observera att svenskt medborgarskap är ett krav för tjänsten, och att tjänsten medför krav på säkerhetsprövning.

Closing date for applications:

Contact: For more information about the position, please contact Johan Håstad ([email protected]) or Martin Ekerå ([email protected]).

More information: https://kth.varbi.com/se/what:job/jobID:790985

In this work, we consider the setting where the process of securely evaluating a multi-party functionality is divided into two phases: offline (or preprocessing) and online. The offline phase is independent of the parties’ inputs, whereas the online phase does require the knowledge of the inputs. We consider the problem of minimizing the round of communication required in the online phase and propose a round preserving compiler that can turn a big class of multi-party computation (MPC) protocols into protocols in which only the last two rounds are input-dependent. Our compiler can be applied to a big class of MPC protocols, and in particular to all existing round-optimal MPC protocols. All our results assume no setup and are proven in the dishonest majority setting with black-box simulation. As part of our contribution, we propose a new definition we call Multi-Party Computation with Adaptive-Input Selection, which allows the distinguisher to craft the inputs the honest parties should use during the online phase, adaptively on the offline phase. This new definition is needed to argue that not only are the messages of the offline phase input-independent but also that security holds even in the stronger (and realistic) adversarial setting where the inputs may depend on some of the offline-phase protocol messages. We argue that this is the definition that any protocol should satisfy to be securely used while preprocessing part of the rounds. We are the first to study this definition in a setting where there is no setup, and the majority of the parties can be corrupted. Prior definitions have been presented in the Universal Composable framework, which is unfortunately not well suited for our setting (i.e., no setup and dishonest majority). As a corollary, we obtain the first four-round (which is optimal) MPC protocol, where the first two rounds can be preprocessed, and its security holds against adaptive-input selection.

Blind signatures allow a user to obtain a signature from an issuer in a privacy-preserving way: the issuer neither learns the signed message, nor can link the signature to its issuance. The threshold version of blind signatures further splits the secret key among n issuers, and requires the user to obtain at least t ≤ n of signature shares in order to derive the final signature. Security should then hold as long as at most t − 1 issuers are corrupt. Security for blind signatures is expressed through the notion of one-more unforgeability and demands that an adversary must not be able to produce more signatures than what is considered trivial after its interactions with the honest issuer(s). While one-more unforgeability is well understood for the single-issuer setting, the situation is much less clear in the threshold case: due to the blind issuance, counting which interactions can yield a trivial signature is a challenging task. Existing works bypass that challenge by using simplified models that do not fully capture the expectations of the threshold setting. In this work, we study the security of threshold blind signatures, and propose a framework of one-more unforgeability notions where the adversary can corrupt c < t issuers. Our model is generic enough to capture both interactive and non-interactive protocols, and it provides a set of natural properties with increasingly stronger guarantees, giving the issuers gradually more control over how their shares can be combined. As a point of comparison, we reconsider the existing threshold blind signature models and show that their security guarantees are weaker and less clearly comprehensible than they seem. We then re-assess the security of existing threshold blind signature schemes – BLS-based and Snowblind – in our framework, and show how to lift them to provide stronger security.