International Association
for Cryptologic Research

We design several new protocols for private set intersection (PSI) with active security: one for the two party setting, and two protocols for the multi-party setting. In recent years, the state-of-the-art protocols for two party PSI have all been built from OT-extension. This has led to extremely efficient protocols that provide correct output to one party;~seemingly inherent to the approach, however, is that there is no efficient way to relay the result to the other party with a provable correctness guarantee. Furthermore, there is no natural way to extend this line of works to more parties. We consider a new instantiation of an older approach. Using the MPC-in-the-head paradigm of Ishai et al [IPS08], we construct a polynomial with roots that encode the intersection, without revealing the inputs. Our reliance on this paradigm allows us to base our protocol on passively secure Oblivious Linear Evaluation (OLE) (requiring 4 such amortized calls per input element). Unlike state-of-the-art prior work, our protocols provide correct output to all parties. We have implemented our protocols, providing the first benchmarks for PSI that provides correct output to all parties. Additionally, we present a variant of our multi-party protocol that provides output only to a central server.

We consider protocols for secure multi-party computation (MPC) under honest majority, i.e., for $N=2t+1$ players of which $t$ are corrupt, that achieve {guaranteed output delivery} (GOD), and in {constant latency}, independently from the circuit and $N$. A generic approach to this problem requires at least $3$ consecutive broadcasts in the plain model without PKI. State-of-the-art protocols with $2$ consecutive broadcasts, namely [GLS, Crypto'15] and [BJMS, Asiacrypt'20], however, suffer from a large size of threshold homomorphic ciphertexts. We aim for more efficient protocols in $2$ broadcasts, that subsequently enjoy a {Responsive execution}, i.e., at the speed of the network.

To achieve this goal, we design a new approach with short threshold fully homomorphic (FHE) ciphertexts, which in turn impacts the computational complexity. The main building block of our technique is a threshold encryption scheme which is Ad-Hoc, i.e., which only takes as parameter $N$ public keys independently generated, equipped with a threshold shrinking mechanism into threshold FHE ciphertexts.

One ingredient of independent interest is a linear secret sharing over RLWE rings with arbitrary modulus. By contrast, previous threshold FHE required the modulus to be prime and at least as large as $N+1$.

Another significant advantage of this approach is that it also allows an arbitrary number of lightweight {external input owners} to feed their inputs in the computation by simply encrypting them with the Ad-Hoc scheme, then go offline.

We finally prove the impossibility of $1$-Broadcast-then-Asynchronous MPC for $N\leq 3t-4$, showing tightness of our $2$ broadcasts.

Predictable arguments introduced by Faonio, Nielsen and Venturi (PKC17) are private-coin argument systems where the answer of the prover can be predicted in advance by the verifier. In this work, we study predictable arguments with additional privacy properties. While the authors in [PKC17] showed compilers for transforming PAs into PAs with zero-knowledge property, they left the construction of witness indistinguishable predictable arguments (WI-PA) in the plain model as an open problem. In this work, we first propose more efficient constructions of zero-knowledge predictable arguments (ZK-PA) based on trapdoor smooth projective hash functions (TSPHFs). Next, we consider the problem of WI-PA construction in the plain model and show how to transform PA into WI-PA using non-interactive witness-indistinguishable proofs. As a relaxation of predictable arguments, we additionally put forth a new notion of predictability called Commit-and-Prove Predictable Argument (CPPA), where except the first (reusable) message of the prover, all the prover’s responses can be predicted. We construct an efficient zero-knowledge CPPA in the non-programmable random oracle model for the class of all polynomial-size circuits. Finally, following the connection between predictable arguments and witness encryption, we show an application of CPPAs with privacy properties to the design of witness encryption schemes, where in addition to standard properties, we also require some level of privacy for the decryptors who own a valid witness for the statement used during the encryption process.

ISML (https://ai-security.github.io/index_e.htm) has conducted research in a range of areas including artificial intelligence, cyber security and cryptography. We are also extending our areas to emerging areas such as quantum computing and parallel computing. Post-doctoral research fellows are welcome from computer science/engineering, electric/electronics, and mathematics/statistics. Applicants with good high-impact journal publication records are encouraged to send their CVs via to Professor Seong Oun Hwang (seongoun.hwang at gmail.com). 1st round of application deadline: April 10, 2022 2nd round of application deadline: May 30, 2022 3rd round of application deadline: July 30, 2022

Closing date for applications:

Contact: Professor Seong Oun Hwang (seongoun.hwang at gmail.com).

More information: https://ai-security.github.io/index_e.htm

The Department of Computer Science and the School of Law at Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU) invite applications for
10 PhD positions (m/f/d) (salary level 13 TV-L) in Computer Science (full time) and Law (part time, 75%)
within the Research Training Group 2475 „Cybercrime and Forensic Computing“ funded by the German Research Foundation (DFG) commencing on October 1, 2022. The Research Training Group aims to systematically analyse research questions arising from the interaction between computer science and criminal law. The principal investigators of this project offer expertise in the following areas:

- Computer security, digital forensic science
- Criminal law, criminal procedure
- Criminology
- Theoretical computer science (logic, semantics, automata)
- Pattern recognition, image processing, image forensics
- Cryptography
- Hardware-software-co-design


More information about the project can be found at https://cybercrime.fau.de Applicants should have an excellent academic record, hold an MSc, LL.M. or an equivalent university degree in computer science, law or related disciplines, and have the goal to finish a PhD degree within three years.

Founded in 1743 and situated at the heart of the Nuremberg Metropolitan Region, FAU is a strong research university with an international perspective and one of the largest universities in Germany. FAU’s outstanding research and teaching is reflected in top positions in both national and international rankings, as well as the high amount of DFG funding which its researchers are able to secure. FAU aims to increase the number of women in scientific positions. Female candidates are therefore particularly encouraged to apply. In case of equal qualifications, candidates with disabilities will take precedence. Please submit your complete application documents by 18.4.2022 to cybercrime-applications@fau.de. Please mention in your application at least two research areas from the above list which you are specifically interested in. Interviews will commence between 7. and 10.6.2022 in Erlangen.

Closing date for applications:

Contact: Felix Freiling (felix.freiling@fau.de) regarding positions in computer science and Dominique Schröder (dominique.schroeder@fau.de) regarding cryptography.

More information: https://www.cybercrime.fau.de/stellen-open-positions/

Event date: 24 August to 30 August 2022

The Institute of Logic and Computation, research unit Security and Privacy, at TU Wien offers a position as a university assistant (post-doc) for 2 years for 40 hours/week with the possibility of an extension up to 6 years after a positive evaluation. Expected start: May 2022.

Tasks:

• Deep interest in scientific problems and the motivation for independent and goal-oriented research
• Independent teaching or participation in teaching and supervision of students
• Ability to develop methods, concepts, as well as their realization and evaluation and the willingness to contribute in interdisciplinary scientific projects
• Participation in organizational and administrative tasks of the research unit and the faculty

Your profile:

• Completion of an appropriate doctorate and in-depth knowledge of the subject area
• An outstanding publication record in top security and privacy conferences
• Research background in one of the following topics: formal methods for security and privacy, blockchain technologies, intersection between machine learning and security or privacy, or web security
• Experience in teaching and publication activities as well as interest and pleasure in research and working with students
• Organisational and analytical skills as well as a structured way of working
• Excellent skills in English communication and writing

We offer:

• Continuing personal and professional education and flexible working hours
• Central location of workplace with very good accessibility (U1/U4 Karlsplatz)
• A creative environment in one of the most liveable cities in the world
• (B1 scale, 56.861,70 EUR per year before tax)
• Additional benefits for employees

The application deadline is 28.04.2022. Online application link: https://jobs.tuwien.ac.at/Job/179063

Closing date for applications:

Contact: Matteo Maffei

More information: https://jobs.tuwien.ac.at/Job/179063

The group is renowned for its cyber security research, with currently more than 15 faculty members and over 30 researchers. It is looking for three post-docs to enhance the information security R&D. The applicants should be related to one of the following topics:

• Lattice-based cryptography
• Privacy-preserving machine learning
• Privacy and applied cryptography
• Blockchain/smart contract security

The basic requirements are:

• PhD in Computer Science, Information Security, Maths.
• Strongly related knowledge and backgrounds (e.g., research papers) of privacy-oriented cryptography (theory and/or practice).
• Professional in English (writing, speaking). Note Dutch is NOT required.

All positions will be available from September 2022 (starting with competitive salary - depending on qualifications and experience, including bonus, 30% tax ruling and other benefits). There will be great opportunities to engage with various ongoing projects, and international academia and industry partners. Please feel free to send CV, publication list and reference to the contact email.

Closing date for applications:

Contact: Dr. S. Fu (shihui.fu@tudelft.nl)

iTrust is a Cyber Security Research Center in SUTD and a National Satellite of Excellence in Singapore for securing critical infrastructure. iTrust hosts the world-class cyber-physical system (CPS) testbeds which are used for research, education, training, live-fire exercise, and technology validation. We are looking for postdocs / research fellows with expertise on cybersecurity and applied cryptography in general and CPS security in particular. The candidates should have track record of strong R&D capability, with publications at leading security conferences. The candidates familiar with maritime and shipboard OT systems will be considered with the priority. Candidate working in the current position less than one year will not be considered (unless due to the end of contract). Fresh PhD graduates are welcome. Only short-listed candidates will be contacted for interview. Successful candidates will be offered internationally competitive remuneration. Interested candidates please send your CV to Prof. Jianying Zhou. Email: jianying_zhou (at) sutd.edu.sg. Home: http://jianying.space/

Closing date for applications:

Contact: Prof. Jianying Zhou. Email: jianying_zhou (at) sutd.edu.sg

More information: http://jianying.space/

The Physical Analysis and Cryptographic Engineering (PACE), Temasek Laboratories (TL) @ Nanyang Technological University, Singapore is seeking motivated researchers, in the area of hardware security.

Candidates should ideally have already completed, or be close to completing a Master’s (with relevant experience) or PhD degree in mathematics, computer science, electrical engineering, or related disciplines, with track record in R&D (publications in international journals and conferences).

You will be joining a dynamic group performing research on embedded security. The research focus of the current roles are:

1. Hardware forensics with focus on vulnerability assessment in commercial and industrial devices.

2. Physical attack and countermeasures for novel cryptographic primitives

3. Micro-architectural attacks

This position is available from May 2022. TL offers competitive salary package plus other benefits.

Review of applications will start immediately until position is filled.

Interested candidates should send their detailed CVs, cover letter and references.

Closing date for applications:

Contact: Shivam Bhasin, Principal Investigator: sbhasin (at) ntu.edu.sg

The job holder's mission will be to:

• Develop effective (security, latency, silicon area/code size costs), countermeasures against side-channel and fault attacks, by working in conjunction with SW and HW designers
• Contribute to the definition of effective post-quantum public key cryptographic implementations
• Deploy security expertise and help ST product divisions shape the right security solutions for their products (ICs).
• Stay on top of security needs and state-of-the-art evolution, anticipating/identifying solutions and partners, developing or making available the security competences and IPs that will be needed by the Company in a 3-5 years time frame.

The candidate should have:

• An extensive background in mathematics and public key cryptography
• Knowledge of state-of-the-art side-channel and fault attacks and related countermeasures
• Teamwork, networking, customer-orientation & communication skills
• Motivation for bridging research outcomes and product design
• Experience in embedded SW design or HW design is a plus

Closing date for applications:

Contact: Matteo BOCCHI (matteo.bocchi@st.com), Ruggero SUSELLA (ruggero.susella@st.com)

More information: https://stcareers.talent-soft.com/job/job-security-engineer-m-f_18168.aspx

We provide a full-fledged security analysis of the Signal end-to-end messaging protocol within the UC framework. In particular:

(1) We formulate an ideal functionality that captures end-to-end secure messaging, in a setting with PKI and an untrusted server, against an adversary that has full control over the network and can adaptively and momentarily compromise parties at any time and obtain their entire internal states. In particular our analysis captures the forward and backwards secrecy properties of Signal and the conditions under which they break. (2) We model the various components of Signal (PKI and long-term keys, backbone "asymmetric ratchet", epoch-level symmetric ratchets, authenticated encryption) as individual ideal functionalities that are analysed separately and then composed using the UC and Global-State UC theorems. (3) We use the Random Oracle Model to model non-committing encryption for arbitrary-length messages, but the rest of the analysis is in the plain model based on standard primitives. In particular, we show how to realize Signal's key derivation functions in the standard model, from generic components, and under minimalistic cryptographic assumptions.

Our analysis improves on previous ones in the guarantees it provides, in its relaxed security assumptions, and in its modularity. We also uncover some weaknesses of Signal that were not previously discussed.

Our modeling differs from previous UC models of secure communication in that the protocol is modeled as a set of local algorithms, keeping the communication network completely out of scope. We also make extensive, layered use of global-state composition within the plain UC framework. These innovations may be of separate interest.

Double-block Hash-then-Sum (DbHtS) MACs is a class of MACs achieve beyond-birthday-bound (BBB) security, including SUM-ECBC, PMAC_Plus, 3kf9 and LightMAC_Plus etc. Recently, Shen et al. (Crypto 2021) proposed a security framework for two-key DbHtS MACs in the multi-user setting, stating that when the underlying blockcipher is ideal and the universal hash function is almost regular and universal, the two-key DbHtS MACs achieve 2n/3-bit security. Unfortunately, the regular and universal properties can not guarantee the BBB security of two-key DbHtS MACs. We propose three counter-examples which are proved to be 2n/3-bit secure in the multi-user setting by the framework, but can be broken with probability $1$ using only O(2^{n/2}) queries even in the single-user setting. We also point out the miscalculation in their proof leading to such a flaw.

In a multiparty signing protocol, also known as a threshold signature scheme, the private signing key is shared amongst a set of parties and only a quorum of those parties can generate a signature. Research on multiparty signing has been growing in popularity recently due to its application to cryptocurrencies. Most work has focused on reducing the number of rounds to two, and as a result: (a) are not fully simulatable in the sense of MPC real/ideal security definitions, and/or (b) are not secure under concurrent composition, and/or (c) require proofs of security in the generic or algebraic group models. In this paper, we describe a simple three-round multiparty protocol for Schnorr signatures and prove its security. The protocol is fully simulatable, secure under concurrent composition, and proven secure in the standard model or random-oracle model (depending on the instantiations of the commitment and zero-knowledge primitives). The protocol realizes an ideal Schnorr signing functionality with perfect security in the ideal commitment and zero-knowledge hybrid model (and thus the only assumptions needed are for realizing these functionalities). We also show how to achieve proactive security and identifiable abort.

In our presentation, we do not assume that all parties begin with the message to be signed, the identities of the participating parties and a unique common session identifier, since this is often not the case in practice. Rather, the parties achieve consensus on these parameters as the protocol progresses.

We present a novel cryptographic primitive, blind accumulator, aimed at constructing e-voting systems. Blind accumulators collect private keys of eligible voters in a decentralized manner not getting information about the keys. Once the accumulation is complete, a voter processes the resulting accumulator deriving a public key that refers to the private key previously added by this voter. Public keys are derived deterministically and can therefore stand as fixed voter pseudonyms. The voter can prove that the derived key refers to some accumulated private key without revealing neither that key nor the voter itself. The voter uses the accumulated private key to sign a ballot. The corresponding public key is used to verify the signature. Since the public key is fixed, it is easy to achieve verifiability, to protect against multiple submissions of ballots by the same voter or, conversely, to allow multiple submissions but count only the last one. We suggest a syntax of blind accumulators and security requirements for them. We embed blind accumulators in the Pseudonymous Key Generation (PKG) protocol which details the use of accumulators in practical settings close to e-voting. We propose an implementation of the blind accumulator scheme whose main computations resemble the Diffie-Hellman protocol. We justify the security of the proposed implementation.

We give a novel procedure for approximating general single-qubit unitaries from a finite universal gate set by reducing the problem to a novel magnitude approximation problem, achieving an immediate improvement in sequence length by a factor of 7/9. Extending the works arXiv:1612.01011 and arXiv:1612.02689, we show that taking probabilistic mixtures of channels to solve fallback (arXiv:1409.3552) and magnitude approximation problems saves factor of two in approximation costs. In particular, over the Clifford+$\sqrt{T}$ gate set we achieve an average non-Clifford gate count of 0.23log2(1/$\varepsilon$)+2.13 and T-count 0.56log2(1/$\varepsilon$)+5.3 with mixed fallback approximations for diamond norm accuracy $\varepsilon$. This paper provides a holistic overview of gate approximation, in addition to these new insights. We give an end-to-end procedure for gate approximation for general gate sets related to some quaternion algebras, providing pedagogical examples using common fault-tolerant gate sets (V, Clifford+T and Clifford+$\sqrt{T}$). We also provide detailed numerical results for Clifford+T and Clifford+$\sqrt{T}$ gate sets. In an effort to keep the paper self-contained, we include an overview of the relevant algorithms for integer point enumeration and relative norm equation solving. We provide a number of further applications of the magnitude approximation problems, as well as improved algorithms for exact synthesis, in the Appendices.

In this paper, we present a high-performance architecture for elliptic curve cryptography (ECC) over Curve448, which to the best of our knowledge, is the fastest implementation of ECC point multiplication over Curve448 to date. Firstly, we introduce a novel variant of the Karatsuba formula for asymmetric digit multiplier, suitable for typical DSP primitive with asymmetric input. It reduces the number of required DSPs compared to previous work and preserves the performance via full parallelization and pipelining. We then construct a 244-bit pipelined multiplier and interleaved fast reduction algorithm, yielding a total of 12 stages of pipelined modular multiplication with four stages of input delay. Additionally, we present an efficient Montgomery ladder scheduling with no additional register is required. The implementation on the Xilinx 7-series FPGA: Virtex-7, Kintex-7, Artix-7, and Zynq 7020 yields execution times of 0.12, 0.13, 0.24, and 0.24 ms, respectively. It increases the throughput by 242% compared to the best previous work on Zynq 7020 and by 858% compared to the best previous work on Virtex-7. Furthermore, the proposed architecture optimizes nearly 63% efficiency improvement in terms of Area×Time tradeoff. Lastly, we extend our architecture with well-known side-channel protections such as scalar blinding, base-point randomization, and continuous randomization.

All existing methods of building non-interactive zero-knowledge (NIZK) arguments for $\mathsf{NP}$ from the Learning With Errors (LWE) assumption have relied on instantiating the Fiat-Shamir paradigm on a parallel repetition of an underlying honest-verifier zero knowledge (HVZK) $\Sigma$ protocol, via an appropriately built correlation-intractable (CI) hash function from LWE. This technique has inherent efficiency losses that arise from parallel repetition.

In this work, we build the first NIZK argument for $\mathsf{NP}$ from the LWE assumption that does not rely on parallel repetition. Instead, we show how to make use of the more efficient ``MPC in the Head'' technique for building an underlying honest-verifier protocol upon which to apply the Fiat-Shamir paradigm. The key to making this possible is a new construction of CI hash functions from LWE, using efficient algorithms for polynomial reconstruction as the main technical tool.

We stress that our work provides a new and more efficient ``base construction'' for building LWE-based NIZK arguments for $\mathsf{NP}$. Our protocol can be the building block around which other efficiency-focused bootstrapping techniques can be applied, such as the bootstrapping technique of Gentry et al. (Journal of Cryptology 2015).

This paper considers a problem of identifying matching attacks against Romulus-M, one of the ten finalists of NIST Lightweight Cryptography standardization project. Romulus-M is provably secure, i.e., there is a theorem statement showing the upper bound on the success probability of attacking the scheme as a function of adversaries' resources. If there exists an attack that matches the provable security bound, then this implies that the attack is optimal, and that the bound is tight in the sense that it cannot be improved. We show that the security bounds of Romulus-M are tight for a large class of parameters by presenting concrete matching attacks.

We introduce the Spiral family of single-server private information retrieval (PIR) protocols. Spiral relies on a composition of two lattice-based homomorphic encryption schemes: the Regev encryption scheme and the Gentry-Sahai-Waters encryption scheme. We introduce new ciphertext translation techniques to convert between these two schemes and in doing so, enable new trade-offs in communication and computation. Across a broad range of database configurations, the basic version of Spiral simultaneously achieves at least a 4.5x reduction in query size, 1.5x reduction in response size, and 2x increase in server throughput compared to previous systems. A variant of our scheme, SpiralStreamPack, is optimized for the streaming setting and achieves a server throughput of 1.9 GB/s for databases with over a million records (compared to 200 MB/s for previous protocols) and a rate of 0.81 (compared to 0.24 for previous protocols). For streaming large records (e.g., a private video stream), we estimate the monetary cost of SpiralStreamPack to be only 1.9x greater than that of the no-privacy baseline where the client directly downloads the desired record.