International Association
for Cryptologic Research

An average-case variant of the $k$-SUM conjecture asserts that finding $k$ numbers that sum to 0 in a list of $r$ random numbers, each of the order $r^k$, cannot be done in much less than $r^{\lceil k/2 \rceil}$ time. On the other hand, in the dense regime of parameters, where the list contains more numbers and many solutions exist, the complexity of finding one of them can be significantly improved by Wagner's $k$-tree algorithm. Such algorithms for $k$-SUM in the dense regime have many applications, notably in cryptanalysis.

In this paper, assuming the average-case $k$-SUM conjecture, we prove that known algorithms are essentially optimal for $k= 3,4,5$. For $k>5$, we prove the optimality of the $k$-tree algorithm for a limited range of parameters. We also prove similar results for $k$-XOR, where the sum is replaced with exclusive or.

Our results are obtained by a self-reduction that, given an instance of $k$-SUM which has a few solutions, produces from it many instances in the dense regime. We solve each of these instances using the dense $k$-SUM oracle, and hope that a solution to a dense instance also solves the original problem. We deal with potentially malicious oracles (that repeatedly output correlated useless solutions) by an obfuscation process that adds noise to the dense instances. Using discrete Fourier analysis, we show that the obfuscation eliminates correlations among the oracle's solutions, even though its inputs are highly correlated.

Recently, a self-sovereign identity model has been researched actively as an alternative to the existing identity models such as a centralized identity model, federated identity model, and user-centric model. The self-sovereign identity model allows a user to have complete control of his identity. Meanwhile, the core component of the self-sovereign identity model is data minimization. The data minimization signifies that the extent of the exposure of user private identity should be minimized. As a solution to data minimization, zero-knowledge proofs can be grafted to the self-sovereign identity model. Specifically, zero-knowledge Succinct Non-interactive ARgument of Knowledges(zk-SNARKs) enables proving the truth of the statement on an arbitrary relation. In this paper, we propose a privacy-preserving self-sovereign identity model based on zk-SNARKs to allow any type of data minimization beyond the selective disclosure and range proof. The security of proposed model is formally proven under the security of the zero-knowledge proof and the unforgeability of the signature in the random oracle model. Furthermore, we optimize the proving time by checking the correctness of the commitment outside of the proof relation for practical use. The resulting scheme improves proving time for hash computation (to verify a commitment input) from 0.5 s to about 0.1 ms on a 32-bit input.

The aim of this document is to clarify the DFR (Decoding Failure Rate) claims made for BIKE, a third round alternate candidate KEM (Key Encapsulation Mechanism) to the NIST call for post-quantum cryptography standardization. For the most part, the material presented here is not new, it is extracted from the relevant scientific literature, in particular [V21].

Even though a negligible DFR is not needed for a KEM using ephemeral keys (e.g. TLS) which only requires IND-CPA security, it seems that IND-CCA security, relevant for reusable/static keys, has become a requirement. Therefore, a negligible DFR is needed both for the security reduction [FO99, HHK17] and to thwart existing attacks [GJS16].

Proving a DFR lower than $2^{-\lambda}$ where $\lambda$ is the security parameter (e.g. $\lambda=128$ or $256$) is hardly possible with mere simulation. Instead a methodology based on modelization, simulation, and extrapolation with confidence estimate was devised [V21]. Models are backed up by theoretical results [T18,SV19], but do not account for some combinatorial properties of the underlying error correcting code. Those combinatorial properties give rise to what is known in telecommunication as "error floors" [R03].

The statistical modeling predicts a fast decrease of the DFR as the block size grows, the waterfall region, whereas the combinatorial properties, weak keys [DGK19] or near-codewords [V21], predict a slower decrease, the error floor region. The issue here is to show that the error floor occurs in a region where the DFR is already below the security requirement. This would validate the extrapolation approach, and, as far as we can say, this appears to be the case for the QC-MDPC codes corresponding to BIKE parameters.

The impact of the QC-MDPC code combinatorial properties on decoding, as reported in this document, is better and better understood. In particular, it strongly relates with the spectrum of low weight vectors, as defined in [GJS16]. At this point, none of the results we are aware of and which are presented here contradict in any way the DFR claims made for BIKE. Admittedly those claims remain heuristic in part, but could be understood as an additional assumption, just like the computational assumptions made for all similar primitives, under which the BIKE scheme is IND-CCA secure.

he ACME certificate issuance and management protocol, standardized as IETF RFC 8555, is an essential element of the web public key infrastructure (PKI). It has been used by Let’s Encrypt and other certification authorities to issue over a billion certificates, and a majority of HTTPS connections are now secured with certificates issued through ACME. Despite its importance, however, the security of ACME has not been studied at the same level of depth as other protocol standards like TLS 1.3 or OAuth. Prior formal analyses of ACME only considered the cryptographic core of early draft versions of ACME, ignoring many security-critical low-level details that play a major role in the 100 page RFC, such as recursive data structures, long-running sessions with asynchronous sub-protocols, and the issuance for certificates that cover multiple domains.

We present the first in-depth formal security analysis of the ACME standard. Our model of ACME is executable and comprehensive, with a level of detail that lets our ACME client interoperate with other ACME servers. We prove the security of this model using a recent symbolic protocol analysis framework called DY* , which in turn is based on the F* programming language. Our analysis accounts for all prior attacks on ACME in the literature, including both cryptographic attacks and low-level attacks on stateful protocol execution. To analyze ACME, we extend DY ★ with authenticated channels, key substitution attacks, and a concrete execution framework, which are of independent interest. Our security analysis of ACME totaling over 16,000 lines of code is one of the largest proof developments for a cryptographic protocol standard in the literature, and it serves to provide formal security assurances for a crucial component of web security.

Continuous Group Key Agreement (CGKA) -- or Group Ratcheting -- lies at the heart of a new generation of End-to-End (E2E) secure group messaging (SGM) and VoIP protocols supporting very large groups. Yet even for these E2E protocols the primary constraint limiting practical group sizes continues to be their communication complexity. To date, the most important (and only deployed) CGKA is ITK which underpins the IETF's upcoming Messaging Layer Security SGM standard.

In this work, we introduce server-aided CGKA (saCGKA) to more precisely model how E2E protocols are usually deployed. saCGKA makes explicit the presence of an (untrusted) server mediating communication between honest parties (as opposed to mere insecure channels of some form or another). Next, we provide a simple and intuitive security model for saCGKA. We modify ITK accordingly to obtain SAIK; a practically efficient and easy to implement saCGKA designed to leverage the server to obtain greatly reduced communication and computational complexity (e.g. relative to ITK). Under the hood, SAIK uses a new type of signature called Reducible Signature which we construct from, so called, Weighted Accumulators. SAIK obtains further advantages by using Multi-Recipient Multi-Message PKE. Finally, we provide empirical data comparing the communication complexity for senders, receivers and the server in ITK vs. three saCGKAs including two instantiations of SAIK.

Your Role...

The successful candidate will join the CryptoLux research team led by Prof. Alex Biryukov. He or she will contribute to a research project on future directions in cryptography and IT security and is expected to perform the following tasks:

• Shaping research directions and producing results in one or more of the following topics: o Applied Cryptography (symmetric, lightweight, AE, White-box etc.); o Financial cryptography, cryptocurrencies, blockchain technologies; o Privacy enhancing technologies (Tor, zero-knowledge, eID, etc.); • Disseminating results through scientific publications; • Providing guidance to Ph.D. and M.Sc. students.

Your Profile...

• A Ph.D. degree in Computer Science, Applied Mathematics, Electrical Engineering, or a related field; • Competitive research record in applied cryptography or information security (at least one paper in top 10 IT security conferences); • Strong mathematical and algorithmic CS background; • Good skills in C /or C++ or scripting languages; • Commitment, team working and a critical mind; • Fluent written and verbal communication skills in English are mandatory.

Closing date for applications:

Contact: alex.biryukov@uni.lu

More information: http://emea3.mrted.ly/2v77v

Job Description. You and your team will be responsible for:

• implementing state-of-the-art algorithms for homomorphic encryption
• continually improving their performance and reliability through timing optimisation and verification
• documenting and benchmarking the implemented cryptographic operations

You will be working with us on the cutting edge of fully homomorphic encryption (FHE), designing and implementing hardware that will enable privacy by default. FHE is an exciting field in cryptography with many opportunities for filing patents, publishing papers, and presenting your work at conferences.

Preferred Experience. You should have:

• a PhD in cryptography, or a Master’s degree in Engineering with more than four (4) years of industry experience
• be well versed in VHDL and/or Verilog
• a strong knowledge of FPGA tool flows, familiarity with cutting-edge FPGA devices, and be comfortable with debugging and reaching timing closure
• a strong interest in cryptography and a passion for privacy
• good analytical skills
• good written and oral communication skills
• experience implementing lattice-based cryptography on FPGA/ASIC is a plus

Full remote is possible, with a willingness to come to Paris quarterly.

Closing date for applications:

Contact: Thomas De Cnudde (thomas.decnudde(at)zama.ai)

More information: https://www.welcometothejungle.com/en/companies/zama/jobs

Multiple fully funded positions on the Ding Lab in Cryptography and its applications at the Yanqi Lake Beijing Institute of Mathematical Sciences and Applications (BIMSA).

Ding Lab

The Ding Lab in Public Key Cryptography will be led by Prof. Jintai Ding. It is an international open laboratory with English as the working language. Anyone who works in related areas including (but not restricted to) computational algebra, computational algebraic geometry, number theory, mathematical optimization, quantum algorithms, post-quantum cryptography, multi-party computation, zero-knowledge proof, fully homomorphic encryption, privacy preserving algorithms, block chain, high performance computing, and algorithm implementations are welcome to apply.

Positions

• Visiting Scholar : including short term(less than 3 months) and long term(6 months to 1 year) for persons who has been granted with PhD degree
• Post-Doc
• Senior Researcher
• Research Associate (master)

All positions require you having a master or PhD degree in Computer Science, Mathematics, Cryptography, or equivalent practical experience.

Salary

BIMSA offers internationally competitive salary packages and salary will be determined by applicant's qualification. Recent PhDs are especially encouraged to apply. A typical appointment for postdoc of BIMSA is for two-years, renewable for the third year with annual salary ranges from 300,000 RMB to 500,000 RMB depending on experience and qualifications.

BIMSA

The BIMSA is a Mathematics research institution co-sponsored by Beijing Municipal Government and Tsinghua University, and the director of BIMSA is the renowned mathematician, Prof. Shing-Tung Yau. The BIMSA is located in the Huairou District of Beijing, and is part of Beijing’s strategic plans to build world-class new-style research & development institutions and national innovation center for science and technology. The BIMSA aims to develop fundamental scientific research and build a bridge between mathematics and industry applications.

Closing date for applications:

Contact: Jintai Ding(DingLab@bimsa.cn)

The CISPA Helmholtz Center for Information Security provides a unique work environment that offers the advantages of a university department and a research laboratory alike. As the latest member of the Helmholtz Association, the largest research organization in Germany, CISPA has embarked on a mission: to rethink the digitalized world of the future from the ground up and make it safer through innovative, cutting-edge research. The center will grow to more than 800 employees in the medium term with not less than 60 Faculty and research group leaders.

CISPA maintains an open, international and diverse work environment. Every Ph.D. student is a member of a research group led by his or her supervisor. Admitted students are, as a rule, paid employees of CISPA with a full-time contract. The working language is English.

Job Description. The group of Kamil Kluczniak is looking for Ph.D. students broadly interested in theoretical and/or practical aspects of Cryptography. Although the group is currently focused on homomorphic encryption and public-key cryptography, candidates will be encouraged to find and pursue their own research interests.

How to apply: All applications have to be done through the Odoo system:

https://jobs.cispa.saarland/de_DE/jobs/detail/phd-students-1

Candidates are encouraged to send ``Hello CISPA!!!'' to the email address that is under the variable m from the following Python code:

>>> c = m**e % N

>>> print(str(c) + ", " + str(e) + ", " + str(N))

>>> 3016, 19, 10403

>>> m = str(c**d % N) + "@cispa.de"

Closing date for applications:

Contact:

https://jobs.cispa.saarland/de_DE/jobs/detail/phd-students-1

If you have any questions regarding your application please contact our Onboarding Team via otm@cispa.de.

Your Role...

In 2018, the NIST announced an initiative to standardize lightweight authenticated encryption schemes and hash functions in an open process with public evaluation. The mission of the APLICA project is to contribute to the evaluation of the third-round candidates and the eventually standardized algorithms by analyzing their theoretical and practical security properties. More concretely, APLICA will contribute to the development of new cryptanalytic techniques that can be applied to lightweight authenticated encryption algorithms and hash functions, and to the design and implementation of new countermeasures against side-channel attacks, in particular differential power analysis, that are suitable for resource-constrained IoT devices.

Your Profile...

Candidates must hold a Ph.D. degree (or obtain a Ph.D. degree before September 2020) in symmetric cryptography or a closely related field. Preference will be given to candidates with a strong publication record that includes at least one paper at an IACR-sponsored conference/workshop or one of the top-4 security conferences. Experience in software development for embedded systems and/or side-channel attacks is a plus. Candidates with an interest to conduct research in one of the following areas are particularly encouraged to apply:

Cryptanalysis of authenticated encryption algorithms or hash functions

Leakage resilience or leakage reduction by design (e.g. modes of operation)

Side-channel analysis and countermeasures

Closing date for applications:

Contact: leonard.pireaux@uni.lu

More information: http://emea3.mrted.ly/2vbse

The novel interdisciplinary Marie Skłodowska-Curie COFUND doctoral training programme

LogiCS@TUWien - Logics for Computer Science http://www.vcla.at/msca

co-funded by the European Commission, will offer 20 full-time PhD positions.The program is hosted by TU Wien, one of the most successful technical universities in Europe and the largest one in Austria. The Faculty of Informatics of TU Wien is a leading research and teaching institution which consistently ranks among the top 100 computer science faculties in the global Times Higher Education ranking. In the heart of Europe, Vienna has a distinguished history in mathematics, computer science, and logic research and offers one of the highest living standards in the world.

The doctoral positions are open to international high-potential early-stage researchers working on Logical Methods in Computer Science and their applications, including:

* Artificial Intelligence * Databases * Verification * Algorithms * Security * Cyber-Physical Systems

The programme provides a 4-year long doctoral training for international PhD candidates within an English-language curriculum. LogiCS@TUWien will run for 60 months and foresees the recruitment of 20 PhD candidates. The PhD candidates will be supervised by:

* Ezio Bartocci * Pavol Cerny * Agata Ciabattoni * Thomas Eiter * Robert Ganian * Georg Gottlob * Laura Kovács * Matteo Maffei * Magdalena Ortiz * Stefan Szeider * Georg Weissenbacher * Stefan Woltran * Florian Zuleger

Two calls will accomplish the recruitment of the 20 positions. The first call is now open, with an application deadline of December 30, 2021.

For details on how to apply, see http://www.vcla.at/msca/apply or watch the video at https://youtu.be/Aq0JGJ9eqzQ.

Closing date for applications:

Contact: If you have any questions about the application procedure, please contact us under: msca@vcla.at

More information: http://www.vcla.at/msca/apply

You will be working with the newly established Cryptography Algorithm Development Group to develop and validate algorithm implementations across IBM platforms.

Job Duties:

• Develop and support the Testing and Emulation of IBM Cryptographic Library in C (CLiC) code on various IBM platforms
• Safely implement cryptographic algorithms and optimize them for the various IBM systems
• Develop optimized code once and reuse in various software and firmware components
• Rapidly address customer demands for new or faster cryptographic capabilities
• Drive innovation in cryptographic development
• Consult hardware development teams on where to provide hardware acceleration

As a core member of the Cryptography Algorithm Development Group, you will

• Successfully deliver technical solutions
• Work and collaborate as part of one team with worldwide collaborators
• Understand the requirements and goals of the customer
• Participate in customer reviews and internal technical solution reviews
• Ensure feedback to all teams
  • Customer(s)
  • Chief Architect
  • Crypto Firmware Team(s)
  • Offering Management

Please see the online job posting for full qualifications and to apply online.

Apply online: https://careers.ibm.com/job/14168444/applied-cryptographer-poughkeepsie-ny/?codes=IBM_CareerWebSite

Closing date for applications:

Contact: Baaba Kyerewaa Forster-Forson

More information: https://careers.ibm.com/job/14168444/applied-cryptographer-poughkeepsie-ny/?codes=IBM_CareerWebSite

The Department of Combinatorics and Optimization at the University of Waterloo invites applications for two tenure-track faculty positions at the rank of Assistant Professor. Associate or Full Professors with tenure will be considered in special cases that enhance the research and teaching profile of the department. We welcome candidates in the research areas of algebraic combinatorics, continuous optimization, cryptography, discrete optimization, and graph theory. Emphasis will be given to candidates in the areas of continuous optimization, discrete optimization, and cryptography.

A Ph.D. degree and evidence of excellence in research and teaching are required. Successful applicants are expected to maintain an active program of research, to attract and supervise graduate students, and to participate in undergraduate and graduate teaching.

The salary range for the position is $105,000 to $155,000. Negotiations beyond this salary range will be considered for exceptionally qualified candidates. The effective date of appointment is July, 1 2022.

Interested individuals should apply using the MathJobs site (https://www.mathjobs.org/jobs/list/18454). Applications should include a curriculum vitae, research and teaching statements, and up to three reprints/preprints. In addition, at least three reference letters should be submitted.

If you have any questions regarding the position, the application process, assessment process, or eligibility, please contact combopt@uwaterloo.ca or Jochen Koenemann, Chair, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1. The closing date for receipt of applications is December 1, 2021.

Closing date for applications:

Contact: Jochen Koenemann, Chair, Department of Combinatorics and Optimization (jochen@uwaterloo.ca)

More information: https://uwaterloo.ca/combinatorics-and-optimization/career-opportunities

The Cryptography and Privacy Engineering Group (ENCRYPTO) @CS Department @Technical University of Darmstadt offers a fully funded position as Doctoral Researcher (Research Assistant/PhD Student) in Private Machine Learning for Mobile Applications to be filled as soon as possible for 3 years with the possibility of extension.
Job description: You'll work in the research training group/doctoral college Privacy&Trust for Mobile Users funded by the German Research Foundation (DFG). In our subproject, we build cryptography-based private machine learning services for mobile applications and investigate their legal applicability (data protection) and economic feasibility in interdisciplinary collaborations. You conduct research, implement prototypes, and publish&present the results at top venues. You'll participate in teaching and supervise thesis students & student assistants.
We offer: We demonstrate that privacy is efficiently protectable in real-world applications via cryptographic protocols. Our open and international working environment facilitates excellent research in a sociable team. TU Darmstadt is a top research university for IT security, cryptography and CS in Europe. Darmstadt is a very international, livable and well-connected city in the Rhine-Main area around Frankfurt. Knowledge of German is beneficial, but not required, and TU Darmstadt offers corresponding support.
Your profile:

• Completed Master's degree (or equivalent) at a top university with excellent grades in IT security, computer science, or a similar area.
• Extensive knowledge in applied cryptography/IT security and very good software development skills. Knowledge in cryptographic protocols (ideally MPC) is a plus.
• Experience with/motivation for working with other disciplines, e.g., law or economics.
• Self-motivated, reliable, creative, can work independently, and want to do excellent research.
• Our working language is English: able to discuss/write/present scientific results in English. German is beneficial but not required.

Application deadline: Nov 17, 2021 (Extended). Later applications are considered.

Closing date for applications:

Contact: Thomas Schneider (application@encrypto.cs.tu-darmstadt.de)

More information: https://encrypto.de/2021-RTG-EN

Asiacrypt 2021, the 27th Annual International Conference on the Theory and Application of Cryptology and Information Security, will take place virtually on December 6-10, 2021.

Registration is now open: https://asiacrypt.iacr.org/2021/registration.php

For questions please contact the General Chair: asiacrypt2021@iacr.org

The masking countermeasure is widely used to protect cryptographic implementations against side-channel attacks. While many masking schemes are shown to be secure in the widely deployed probing model, the latter raised a number of concerns regarding its relevance in practice. Offering the adversary the knowledge of a fixed number of intermediate variables, it does not capture the so-called horizontal attacks which exploit the repeated manipulation of sensitive variables. Therefore, recent works have focused on the random probing model in which each computed variable leaks with some given probability $p$. This model benefits from fitting better the reality of the embedded devices. In particular, Belaïd, Coron, Prouff, Rivain, and Taleb (CRYPTO 2020) introduced a framework to generate random probing circuits. Their compiler somehow extends base gadgets as soon as they satisfy a notion called random probing expandability (RPE). A subsequent work from Belaïd, Rivain, and Taleb (EUROCRYPT 2021) went a step forward with tighter properties and improved complexities. In particular, their construction reaches a complexity of $\mathcal{O}(\kappa^{3.9})$, for a $\kappa$-bit security, while tolerating a leakage probability of $p=2^{-7.5}$.

In this paper, we generalize the random probing expansion approach by considering a dynamic choice of the base gadgets at each step in the expansion. This approach makes it possible to use gadgets with high number of shares --which enjoy better asymptotic complexity in the expansion framework-- while still tolerating the best leakage rate usually obtained for small gadgets. We investigate strategies for the choice of the sequence of compilers and show that it can reduce the complexity of an AES implementation by a factor $10$. We also significantly improve the asymptotic complexity of the expanding compiler by exhibiting new asymptotic gadget constructions. Specifically, we introduce RPE gadgets for linear operations featuring a quasi-linear complexity as well as an RPE multiplication gadget with linear number of multiplications. These new gadgets drop the complexity of the expanding compiler from quadratic to quasi-linear.

This paper presents the details of one of the two cryptographic remote e-voting protocols used in Russian parliamentary elections of 2021. As the official full version of the scheme has never been published by the election organisers, our paper aims at putting together as complete picture as possible from various incomplete sources. As all the currently available sources are in Russian, our presentation also aims at serving the international community by making the description available in English for further studies. In the second part of the paper we provide an initial analysis of the protocol, identifying the potential weaknesses under the assumptions of corruption of the relevant key components. As a result we conclude that the biggest problems of the system stem from weak voter authentication. In addition, as it was possible to vote from any device with a browser and Internet access, the attack surface was relatively large in general.

State-separating proofs (SSPs) are a recent proof and definition style for cryptographic security games in pseudo-code. SSPs allow to carry out computational security reductions for cryptography such that "irrelevant code" can be dealt with syntactically and does not require reasoning about execution semantics. Real-world protocols have notoriously long specifications, and the SSP style of breaking down security games and identifying subgames enables the analysis of such protocols. Indeed, SSPs have been used to analyze the key schedules of TLS (ePrint 2021/467) and MLS (S&P 2022). Similarly, secure multi-party computation (MPC) protocols tend to have lengthy specifications. In this work, we explore how to use SSP techniques in the MPC context and for simulation-based security. On the example of Yao's circuit garbling scheme, we adapt the definitional style of SSPs and show that structuring the circuit and security proof in a layered way allows for a brief, compelling, syntactic construction of the reductions required in the hybrid proof of Yao's garbling scheme.

The field of post-quantum cryptography aims to develop and analyze algorithms that can withstand classical and quantum cryptanalysis. The NIST PQC standardization process, now in its third round, specifies ease of protection against side-channel analysis as an important selection criterion. In this work, we develop and validate a masked hardware implementation of Saber key encapsulation mechanism, a third-round NIST PQC finalist. We first design a baseline lightweight hardware architecture of Saber and then apply side-channel countermeasures. Our protected hardware implementation is significantly faster than previously reported protected software and software/hardware co-design implementations. Additionally, applying side-channel countermeasures to our baseline design incurs approximately 2.9x and 1.4x penalty in terms of the number of LUTs and latency, respectively, in modern FPGAs.

Many currently deployed public-key cryptosystems are based on the difficulty of the discrete logarithm and integer factorization problems. However, given an adequately sized quantum computer, these problems can be solved in polynomial time as a function of the key size. Due to the future threat of quantum computing to current cryptographic standards, alternative algorithms that remain secure under quantum computing are being evaluated for future use. One such algorithm is CRYSTALS-Dilithium, a lattice-based digital signature scheme, which is a finalist in the NIST Post Quantum Cryptography (PQC) competition. As a part of this evaluation, high-performance implementations of these algorithms must be investigated. This work presents a high-performance implementation of CRYSTALS-Dilithium targeting FPGAs. In particular, we present a design that achieves the best latency for an FPGA implementation to date. We also compare our results with the most-relevant previous work on hardware implementations of NIST Round 3 post-quantum digital signature candidates.