International Association
for Cryptologic Research

Constructing an efficient CCA-secure KEM is generally done by first constructing a passively-secure PKE scheme, and then applying the Fujisaki-Okamoto (FO) transformation. The original FO transformation was designed to offer security in a single user setting. A stronger notion, known as multi-user security, considers the attacker's advantage in breaking one of many user's ciphertexts. Bellare et al.~(EUROCRYPT 2020) showed that standard single user security implies multi-user security with a multiplicative tightness gap equivalent to the number of users.

To obtain even more confidence in the security of KEMs in the multi-user setting, it is a common design paradigm to also ``domain separate'' the random oracles of each user by including his public key as an input to the hash function. We are not aware of any formal analysis of this technique, but it was at least informally thought to be a computationally cheap way to add security. This design principle was carried over into the FO transformations used by several schemes in the NIST post-quantum standardization effort -- notably the lattice-based schemes Kyber and Saber, which are two of the four KEM finalists.

In this work, we formally analyze domain separation in the context of the FO transformation in the multi-user setting. We first show that including the public key in the hash function is indeed important for the tightness of the security reductions in the ROM and the QROM. At the same time, we show that including the \emph{entire} public key into the hash function is unnecessarily wasteful -- it is enough to include just a small (e.g. $32$ byte) unpredictable part of the key to achieve the same security. Reducing the input of the hash function results in a very noticeable improvement in the running time of the lattice-based KEMs. In particular, using this generic transform results in a 2X - 3X speed-up over the current (Round 3) key generation and encapsulation procedures in Kyber, and up to a $40\%$ improvement in the same functions in Saber.

Proof of liabilities (PoL) allows a prover to prove his/her liabilities to a group of verifiers. This is a cryptographic primitive once used only for proving financial solvency but is also applicable to domains outside finance, including transparent and private donations, new algorithms for disapproval voting and publicly verifiable official reports such as COVID-19 daily cases. These applications share a common nature in incentives: it's not in the prover's interest to increase his/her total liabilities. We generalize PoL for these applications by attempting for the first time to standardize the goals it should achieve from security, privacy and efficiency perspectives. We also propose DAPOL+, a concrete PoL scheme extending the state-of-the-art DAPOL protocol but providing provable security and privacy, with benchmark results demonstrating its practicality. In addition, we explore techniques to provide additional features that might be desired in different applications of PoL and measure the asymptotic probability of failure.

Private set intersection (PSI) allows two mutually distrusting parties each with a set as input, to learn the intersection of both their sets without revealing anything more about their respective input sets. Traditionally, PSI studies the static setting where the computation is performed only once on both parties' input sets. We initiate the study of updatable private set intersection (UPSI), which allows parties to compute the intersection of their private sets on a regular basis with sets that also constantly get updated. We consider two specific settings. In the first setting called UPSI with addition, parties can add new elements to their old sets. We construct two protocols in this setting, one allowing both parties to learn the output and the other only allowing one party to learn the output. In the second setting called UPSI with weak deletion, parties can additionally delete their old elements every $t$ days. We present a protocol for this setting allowing both parties to learn the output. All our protocols are secure against semi-honest adversaries and have the guarantee that both the computational and communication complexity only grow with the set updates instead of the entire sets.

Finally, we implement our UPSI with addition protocols and compare with the state-of-the-art PSI protocols. Our protocols compare favorably when the total set size is sufficiently large, the new updates are sufficiently small, or in networks with low bandwidth.

In this paper, we report the first quantum key-recovery attack on a symmetric block cipher design, using classical queries only, with a more than quadratic time speedup compared to the best classical attack.

We study the 2XOR-Cascade construction of Ga{\v{z}}i and Tessaro (EUROCRYPT~2012). It is a key length extension technique which provides an n-bit block cipher with 5n/2 bits of security out of an n-bit block cipher with 2n bits of key, with a security proof in the ideal model. We show that the offline-Simon algorithm of Bonnetain et al. (ASIACRYPT~2019) can be extended to, in particular, attack this construction in quantum time Õ(2^n), providing a 2.5 quantum speedup over the best classical attack.

Regarding post-quantum security of symmetric ciphers, it is commonly assumed that doubling the key sizes is a sufficient precaution. This is because Grover's quantum search algorithm, and its derivatives, can only reach a quadratic speedup at most. Our attack shows that the structure of some symmetric constructions can be exploited to overcome this limit. In particular, the 2XOR-Cascade cannot be used to generically strengthen block ciphers against quantum adversaries, as it would offer only the same security as the block cipher itself.

We present fully homomorphic encryption schemes for fixed-point arithmetic with fixed precision. Our scheme achieves $\mathsf{IND}$-$\mathsf{CPA^D}$ security and uses $\mathsf{RLWE}$ ring with dimension ${2^{13}}$ or less. Our techniques could also be extended to construct fully homomorphic encryption schemes for approximate numbers with $\mathsf{IND}$-$\mathsf{CPA}$ security. The bootstrapping process of our $\mathsf{IND}$-$\mathsf{CPA}$ scheme preserves about 39-bit precision with ring dimension $2^{13}$, which is the first construction that preserves high precision while keeping the parameters small.

The core technique in this paper is a new and efficient functional bootstrapping algorithm that avoids the negacyclicity constraint of the evaluated functions, which enables us to extract bits blocks homomorphically. This new functional bootstrapping algorithm could be applied to BFV and TFHE schemes as well, and is of independent interest.

The preponderance of smart devices, such as smartphones, has boosted the development and use of mobile applications (apps) in the recent years. This prevalence induces a large volume of mobile app usage data. The analysis of such information could lead to a better understanding of users' behaviours in using the apps they have installed, even more if these data can be coupled with a given context (location, time, date, sociological data...). However, mobile and apps usage data are very sensitive, and are today considered as personal. Their collection and use pose serious concerns associated with individuals' privacy. To reconcile harnessing of data and privacy of users, we investigate in this paper the possibility to conduct privacy-preserving mobile data usage statistics that will prevent any inference or re-identification risks. The key idea is for each user to encrypt their (private and sensitive) inputs before sending them to the data processor. The possibility to perform statistics on those data is then possible thanks to the use of functional encryption, a cryptographic building block permitting to perform some allowed operations over encrypted data. In this paper, we first show how it is possible to obtain such individuals' usage of their apps, which step is necessary for our use case, but can at the same time pose some security problems w.r.t. those apps. We then design our new encryption scheme, adding some fault tolerance property to a recent dynamic decentralized function encryption scheme. We finally show how we have implemented all that, and give some benchmarks.

Cryptanalysis of the LowMC block cipher when the attacker has access to a single known plaintext/ciphertext pair is a mathematically challenging problem. This is because the attacker is unable to employ most of the standard techniques in symmetric cryptography like linear and differential cryptanalysis. This scenario is particularly relevant while arguing the security of the \picnic digital signature scheme in which the plaintext/ciphertext pair generated by the LowMC block cipher serves as the public (verification) key and the corresponding LowMC encryption key also serves as the secret (signing) key of the signature scheme. In the paper by Banik et al. (IACR ToSC 2020:4), the authors used a linearization technique of the LowMC S-box to mount attacks on some instances of the block cipher. In this paper, we first make a more precise complexity analysis of the linearization attack. Then, we show how to perform a 2-stage MITM attack on LowMC. The first stage reduces the key candidates corresponding to a fraction of key bits of the master key. The second MITM stage between this reduced candidate set and the remaining fraction of key bits successfully recovers the master key. We show that the combined computational complexity of both these stages is significantly lower than those reported in the ToSC paper by Banik et al.

BIKE is a Key Encapsulation Mechanism selected as an alternate candidate in NIST’s PQC standardization process, in which performance plays a significant role in the third round. This paper presents FPGA implementations of BIKE with the best area-time performance reported in literature. We optimize two key arithmetic operations, which are the sparse polynomial multiplication and the polynomial inversion. Our sparse multiplier achieves time-constancy for sparse polynomials of indefinite Hamming weight used in BIKE’s encapsulation. The polynomial inversion is based on the extended Euclidean algorithm, which is unprecedented in current BIKE implementations. Our optimized design results in a 5.5 times faster key generation compared to previous implementations based on Fermat’s little theorem.

Besides the arithmetic optimizations, we present a united hardware design of BIKE with shared resources and shared sub-modules among KEM functionalities. On Xilinx Artix-7 FPGAs, our light-weight implementation consumes only 3 777 slices and performs a key generation, encapsulation, and decapsulation in 3 797 µs, 443 µs, and 6 896 µs, respectively. Our high-speed design requires 7 332 slices and performs the three KEM operations in 1 672 µs, 132 µs, and 1 892 µs, respectively.

Blum, Kalai and Wasserman (JACM 2003) gave the first sub-exponential algorithm to solve the Learning Parity with Noise (LPN) problem. In particular, consider the LPN problem with constant noise $\mu=(1-\gamma)/2$. The BKW solves it with space complexity $2^{\frac{(1+\epsilon)n}{\log n}}$ and time/sample complexity $2^{\frac{(1+\epsilon)n}{\log n}}\cdot 2^{O(n^{\frac{1}{1+\epsilon}})}$ for small constant $\epsilon\to 0^+$. We propose a variant of the BKW by tweaking Wagner's generalized birthday problem (Crypto 2002) and adapting the technique to a $c$-ary tree structure. In summary, our algorithm achieves the following:

(Time-space tradeoff). We obtain the same time-space tradeoffs for LPN and LWE as those given by Esser et al. (Crypto 2018), but without resorting to any heuristics. For any $2\leq c\in\mathbb{N}$, our algorithm solves the LPN problem with time/sample complexity $2^{\frac{\log c(1+\epsilon)n}{\log n}}\cdot 2^{O(n^{\frac{1}{1+\epsilon}})}$ and space complexity $2^{\frac{\log c(1+\epsilon)n}{(c-1)\log n}}$, where one can use Grover's quantum algorithm or Dinur et al.'s dissection technique (Crypto 2012) to further accelerate/optimize the time complexity.

(Time/sample optimization). A further adjusted variant of our algorithm solves the LPN problem with sample, time and space complexities all kept at $2^{\frac{(1+\epsilon)n}{\log n}}$ for $\epsilon\to 0^+$, saving factor $2^{\Omega(n^{\frac{1}{1+\epsilon}})}$ in time/sample compared to the original BKW, and the variant of Devadas et al. (TCC 2017). This benefits from a careful analysis of the error distribution among the correlated candidates, and therefore avoids repeating the same process $2^{\Omega(n^{\frac{1}{1+\epsilon}})}$ times on fresh new samples.

(Sample reduction) Our algorithm provides an alternative to Lyubashevsky's BKW variant (RANDOM 2005) for LPN with a restricted amount of samples. In particular, given $Q=n^{1+\epsilon}$ (resp., $Q=2^{n^{\epsilon}}$) samples, our algorithm saves a factor of $2^{\Omega(n)/(\log n)^{1-\kappa}}$ (resp., $2^{\Omega(n^{\kappa})}$) for constant $\kappa \to 1^-$ in running time while consuming roughly the same space, compared with Lyubashevsky's algorithm.

We seek to bridge the gaps between theoretical and heuristic LPN solvers, but take a different approach from Devadas et al. (TCC 2017). We exploit weak yet sufficient conditions (e.g., pairwise independence), and the analysis uses only elementary tools (e.g., Chebyshev's inequality).

We construct efficient functional commitments for all bounded size arithmetic circuits. A (function hiding) functional commitment scheme allows a committer to commit to a secret function f and later prove that y = f(x) for public x and y—without revealing any other information about f. Thus, functional commitments allow the operator of a secret process to prove that the process is being applied uniformly to everyone. Possible applications include bail decisions, credit scores, online ranking algorithms, and proprietary software-as-a-service. To build functional commitments, we introduce a new type of protocol: a proof of function relation (PFR) to show that a committed relation is a function. We show that combining a suitable preprocessing zk-SNARK with a PFR yields a secure functional commitment scheme. We then construct efficient PFRs for two popular preprocessing zk-SNARKs, and obtain two functional commitment schemes for arithmetic circuits. These constructions build on polynomial commitments (a special case of functional commitments), so our work shows that polynomial commitments are “complete” for functional commitments.

IRIF (Institut de Recherche en Informatique Fondamentale, https://www.irif.fr/) will be offering one to two years of postdoc in cryptography, starting October 2022. Topics of interest include, but are not limited to, secure computation, zero-knowledge proofs, post-quantum cryptography, code-based cryptography, and foundational aspects of cryptography (including black-box separations and connections to learning theory). Anyone interested should apply via algocomp-apply (at) irif (dot) fr (see https://www.irif.fr/postes/postdoc for how to apply). The deadline is November 1st, 2021. Further details: IRIF (research institute in theoretical computer science) is a laboratory of the University of Paris. It's the largest TCS lab in France, with more than 90 permanent members and dozens of PhDs & postdocs. It is located in the south of Paris, and is well connected to everything via public transportation.

Closing date for applications:

Contact: Geoffroy Couteau

More information: https://www.irif.fr/postes/postdoc

Research Internships at Microsoft provide a dynamic environment for research careers with a network of world-class research labs led by globally-recognized scientists and engineers. Our researchers and engineers pursue innovation in a range of scientific and technical disciplines to help solve complex challenges in diverse fields, including computing, healthcare, economics, and the environment.

Digital identities are foundational to the modern web and to the many services enabled by various cloud providers. The Cryptography and Privacy Research Group at Microsoft Research, Redmond, is creating new privacy and transparency technologies for the digital identity ecosystem, with the goal of giving users more control over their identity and visibility into its usage. We are looking for a research intern for the spring of 2022 to work with us on privacy-preserving and auditable data structures and applications to future digital identity ecosystems.

More information and application at https://careers.microsoft.com/us/en/job/1177611/Research-Intern-Privacy-and-Cryptography

Closing date for applications:

Contact: Kim Laine (kim.laine@microsoft.com) or Esha Ghosh (esha.ghosh@microsoft.com)

We are looking for a Research Associate (PostDoc) in Secure & Privacy-preserving AI Models to join our ambitious EnnCore (https://enncore.github.io/) project.

You will enjoy designing, developing and evaluating novel AI models (deep neural networks) that are privacy-preserving and robust against attacks. The project will involve the continuous interaction with experts in explainable AI and formal software verification. You will also have the opportunity to build use cases and to collaborate with domain experts in areas such as cancer research and energy trading. You will design, develop and evaluate new models in the context of their accuracy, privacy-protection and robustness. This position may include research on a diverse set of techniques such as federated learning, homomorphic encryption, multiparty computation and adversarial methods. The post is initially for one year, with the possibility for extensions.

You should have a PhD or equivalent in Computer Science or a closely related field together with a track record of international publications in applied machine learning or secure computation. Examples of fields of interests are:

(1) Federated Learning
(2) Homomorphic Encryption
(3) Secure Multiparty Computation
(4) Differential Privacy
(5) Safety Mechanisms in AI Systems
(6) Adversarial Methods

Closing date for applications:

Contact: Dr Mustafa A. Mustafa
mustafa.mustafa@manchester.ac.uk

More information: https://www.jobs.manchester.ac.uk/displayjob.aspx?jobid=21038

Heliax is looking for a cryptographer & researcher interested in zero-knowledge cryptographic protocols and their application to distributed ledger technology to work with us to design, evaluate, and implement zero-knowledge proof constructions such as zkSNARKs and zkSTARKs, distributed cryptographic protocols such as threshold encryption and distributed key generation, and cryptographic primitives such as elliptic curves and hash functions, then put this cryptography into practice in order to realise privacy and scalability capabilities required by the next generation of blockchain networks. This role offers the chance to work closely with a small team on compelling cross-disciplinary problems in theoretical computer science, cryptography, game theory, economics, and systems design, and enjoy a high degree of independence in working conditions and task prioritization.

Closing date for applications:

Contact: jobs@heliax.dev

More information: https://heliax.dev/jobs/zero-knowledge-cryptographer-protocol-developer/

Shantanu Sharma, Assistant Professor @ Computer Science at NJIT, has multiple fully funded Ph.D. positions in the area of databases, secure data processing, IoT, cloud/edge computing, blockchain, and secure model learning. Webpage: https://web.njit.edu/~ss797/

Details: NJIT is a Rank 1 Research University, situated in New York Metropolitan area, and is about 7 miles away from the beautiful New York City. New York Metropolitan area is a key part of the US and is the hub of several major tech and research companies. The qualified candidates will have opportunities for research internships and joint projects with lead-industrial companies.
The position is looking for highly motivated graduate as well as undergraduate students to explore, design, and implement algorithms for databases, secure computing, IoT, blockchain, and machine learning. Topics are as follows:
1. GDPR compliance trustworthy database systems
a. The implication of privacy laws in database systems
b. Design of new modules for GDPR compliance secure databases
2. Trustworthy data-driven systems
a. Application of blockchains in data-driven systems
b. Applications of security techniques in data-driven system pipeline
3. Scalable and trustworthy database processing
a. Use of encryption and secret-sharing techniques
b. Use of secure hardware
Outcome: The work will expose the student to novel data management algorithms, programming with secure hardware (Intel SGX), cluster computing frameworks such as MapReduce and Spark, and the basics of secure computing using cryptographic techniques.

Requirements:
1. You will need to be highly enthusiastic, learner, and also be interested in coding/prototyping algorithms and systems
2. Adequate knowledge of algorithms, programming, and relational database systems
3. Knowledge of Java, SQL, and C/C++
4. You must be an Undergraduate/Master student in computer science or a related field

Closing date for applications:

Contact: Shantanu Sharma shantanu[DOT]sharma[AT]njit[DOT]edu Please send your CV and other information (e.g., GitHub account, sample projects, etc.) to: Shantanu Sharma

More information: https://web.njit.edu/~ss797/

The Institute of Information Security at University of Stuttgart offers a

fully-funded Postdoc position in formal verification.

The successful candidate is expected to work on tool-supported formal verification of security-critical systems and security protocols.

The position is available immediately with an internationally competitive salary (German public salary scale TV-L E13 or TV-L E14, depending on the candidate's qualification, ranging from about 4.600 Euro to 6.200 Euro monthly gross salary). The appointment period follows the German Wissenschaftszeitvertragsgesetz (WissZeitVg), ranging from one year to up to six years.

The Institute of Information Security offers a creative international environment for top-level international research in Germany's high-tech region.

The successful candidate should have a Ph.D. (or should be very close to completion thereof) in Computer Science, Mathematics, Information Security, or a related field. We value strong analytical skills and

• solid knowledge of logic, proofs and/or formal verification techniques (Theorem Proving, Type Checking, etc.),
• solid programming experience.

Knowledge in security is not required, but a plus. Knowledge of German is not required.

See https://www.sec.uni-stuttgart.de/institute/job-openings/ for details of how to apply.

The deadline for applications is

October 31st, 2021.

Late applications will be considered until the position is filled.

Closing date for applications:

Contact: Prof. Dr. Ralf Küsters
University of Stuttgart
Institute of Information Security
ralf.kuesters@sec.uni-stuttgart.de

More information: https://www.sec.uni-stuttgart.de/institute/job-openings/

The goal of anonymous whistleblowing is to publicly disclose a message while at the same time hiding the identity of the sender in a way that even if suspected of being the sender, this cannot be proven. While many solutions to this problem have been proposed over the years, they all require some form of interaction with trusted or non-colluding parties. In this work, we ask whether this is fundamentally inherent. We put forth the notion of anonymous transfer as a primitive allowing to solve this problem without relying on any participating trusted parties.

We initiate the theoretical study of this question, and derive negative and positive results on the existence of such a protocol. We refute the feasibility of asymptotically secure anonymous transfer, where the message will be received with overwhelming probability while at the same time the identity of the sender remains hidden with overwhelming probability. On the other hand, resorting to fine-grained cryptography, we provide a heuristic instantiation (assuming ideal obfuscation) which guarantees that the message will be correctly received with overwhelming probability and the identity of the sender leaks with vanishing probability. Our results provide strong foundations for the study of the possibility of anonymous communications through authenticated channels, an intriguing goal which we believe to be of fundamental interest.

Leakage-resilient authenticated encryption (AE) schemes received considerable attention during the previous decade. Two core security models of bounded and unbounded leakage have evolved, where the latter has been motivated in a very detailed and practice-oriented manner. In that setting, designers often build schemes based on (tweakable) block ciphers due to the small state size, such as the recent two-pass AE scheme TEDT from TCHES 1/2020. TEDT is interesting due to its high security guarantees of O(n - log(n^2))-bit integrity under leakage and similar AE security in the black-box setting. Though, a detail limited it to provide only n/2-bit privacy under leakage. In this work, we extend TEDT to TEDT2 in three aspects with the help of a tweakable block cipher with a 3n-bit tweakey: we (1) adopt the idea from the design team of Romulus of replacing TEDT's previous internal hash function with Naito's MDPH, (2) move the nonce from the hash to the tag-generation function both for more efficiency, and (3) strengthen the security of the encryption to obtain beyond-birthday-bound security also under leakage.

The NIST selection process for standardizing Post-Quantum Cryptography Mechanisms is currently running. Many papers already studied their theoretical security, but the resistance in deployed device has not been much investigated so far. In particular, fault attack is a serious threat for algorithms implemented in embedded devices. One particularly powerful technique is to use safe-error attacks. Such attacks exploit the fact that a specific fault may or may not lead to a faulty output depending on a secret value. In this paper, we investigate the resistance of various Post-Quantum candidates algorithms against such attacks.

We propose a new hard problem, called the Embedded Multilayer Equations (eMLE) problem in this paper. An example of eMLE, with one secret variable x and three layers, is given below.

6268 = 57240 * x + (1248 * x + (9 * x mod 16) mod 2053) mod 65699

In this example, the eMLE problem is to find x from the above equation. eMLE in this paper has the same number of variables and equations. The hardness of eMLE problem lies in its layered structure. Without knowing the eMLE value of lower layer (i.e., the layer with modulus 2053), the top layer (i.e., the layer with modulus 65699) has many candidate solutions; the adversary has to search the solution space for a few valid ones. A lower-bound for the number of searches has been proven in the paper, together with the expected number of valid solutions. The hardness of eMLE can be increased by adding more layers, without changing the number of variables and equations; no existing NP-complete problems have this feature. Over the hardness of eMLE, a post-quantum signature scheme, eMLE-Sig, is constructed. Compared with all existing signature schemes (conventional and post-quantum), eMLE-Sig might be the simplest to understand, analyze, instantiate, and implement. At the security level above 128 bits, five configurations are provided; all of them have keys and signatures smaller than RSA keys and signatures (above 380 bytes) at the 128-bit security level. The smallest configuration is with two variables and three layers, having 84.1/52.2 bytes for private/public key and 168.4 bytes for signatures.