International Association
for Cryptologic Research

We study new candidates for symmetric cryptographic primitives that leverage alternation between linear functions over $\mathbb{Z}_2$ and $\mathbb{Z}_3$ to support fast protocols for secure multiparty computation (MPC). This continues the study of weak pseudorandom functions of this kind initiated by Boneh et al. (TCC 2018) and Cheon et al. (PKC 2021).

We make the following contributions. (Candidates). We propose new designs of symmetric primitives based on alternating moduli. These include candidate one-way functions, pseudorandom generators, and weak pseudorandom functions. We propose concrete parameters based on cryptanalysis.

(Protocols). We provide a unified approach for securely evaluating modulus-alternating primitives in different MPC models. For the original candidate of Boneh et al., our protocols obtain at least 2x improvement in all performance measures. We report efficiency benchmarks of an optimized implementation.

(Applications). We showcase the usefulness of our candidates for a variety of applications. This includes short "Picnic-style" signature schemes, as well as protocols for oblivious pseudorandom functions, hierarchical key derivation, and distributed key generation for function secret sharing.

In recent years, research has shown the networking layer’s significant influence on the scalability, security, and privacy of blockchain systems. Such large-scale networks however exhibit a degree of complexity that demands model-based simulations as real-world experiments are often not possible. In this work, we methodically characterize blockchain networks by reference to the paradigmatic Bitcoin peer-to-peer network, explore the state-of-the-art protocols, and emphasize this key design space. To this end, we conducted a longitudinal measurement study on the Bitcoin network, from which we extract a comprehensive network model and implement it as part of the bns network simulation framework. We validate the model in comparison to real-world measurements as well as to results from related work. Moreover, we experimentally show how network utilization and miners’ geographical location impact the block propagation characteristics.

Many recent private set intersection (PSI) protocols encode input sets as polynomials. We consider the more general notion of an oblivious key-value store (OKVS), which is a data structure that compactly represents a desired mapping $k_i \mapsto v_i$. When the $v_i$ values are random, the OKVS data structure hides the $k_i$ values that were used to generate it. The simplest (and size-optimal) OKVS is a polynomial $p$ that is chosen using interpolation such that $p(k_i)=v_i$.

We initiate the formal study of oblivious key-value stores, and show new constructions resulting in the fastest OKVS to date.

Similarly to cuckoo hashing, current analysis techniques are insufficient for finding {\em concrete} parameters to guarantee a small failure probability for our OKVS constructions. Moreover, it would cost too much to run experiments to validate a small upper bound on the failure probability. We therefore show novel techniques to amplify an OKVS construction which has a failure probability $p$, to an OKVS with a similar overhead and failure probability $p^c$. Setting $p$ to be moderately small enables to validate it by running a relatively small number of $O(1/p)$ experiments. This validates a $p^c$ failure probability for the amplified OKVS.

Finally, we describe how OKVS can significantly improve the state of the art of essentially all variants of PSI. This leads to the fastest two-party PSI protocols to date, for both the semi-honest and the malicious settings. Specifically, in networks with moderate bandwidth (e.g., 30 - 300 Mbps) our malicious two-party PSI protocol has 40\% less communication and is 20-40\% faster than the previous state of the art protocol, even though the latter only has heuristic confidence.

Secure multi-party computation allows mutually distrusting parties to compute securely over their private data. However, guaranteeing output delivery to honest parties when the adversarial parties may abort the protocol has been a challenging objective. As a representative task, this work considers two-party coin-tossing protocols with guaranteed output delivery, a.k.a., fair coin-tossing.

In the information-theoretic plain model, as in two-party zero-sum games, one of the parties can force an output with certainty. In the commitment-hybrid, any $r$-message coin-tossing protocol is ${1/\sqrt r}$-unfair, i.e., the adversary can change the honest party's output distribution by $1/\sqrt r$ in the statistical distance. Moran, Naor, and Segev (TCC--2009) constructed the first $1/r$-unfair protocol in the oblivious transfer-hybrid. No further security improvement is possible because Cleve (STOC--1986) proved that $1/r$-unfairness is unavoidable. Therefore, Moran, Naor, and Segev's coin-tossing protocol is optimal. However, is oblivious transfer necessary for optimal fair coin-tossing?

Maji and Wang (CRYPTO--2020) proved that any coin-tossing protocol using one-way functions in a black-box manner is at least $1/\sqrt r$-unfair. That is, optimal fair coin-tossing is impossible in Minicrypt. Our work focuses on tightly characterizing the hardness of computation assumption necessary and sufficient for optimal fair coin-tossing within Cryptomania, outside Minicrypt. Haitner, Makriyannia, Nissim, Omri, Shaltiel, and Silbak (FOCS--2018 and TCC--2018) proved that better than $1/\sqrt r$-unfairness, for any constant $r$, implies the existence of a key-agreement protocol.

We prove that any coin-tossing protocol using public-key encryption (or, multi-round key agreement protocols) in a black-box manner must be $1/\sqrt r$-unfair. Next, our work entirely characterizes the additional power of secure function evaluation functionalities for optimal fair coin-tossing. We augment the model with an idealized secure function evaluation of $f$, \aka, the $f$-hybrid. If $f$ is complete, that is, oblivious transfer is possible in the $f$-hybrid, then optimal fair coin-tossing is also possible in the $f$-hybrid. On the other hand, if $f$ is not complete, then a coin-tossing protocol using public-key encryption in a black-box manner in the $f$-hybrid is at least $1/\sqrt r$-unfair.

Code-based public key cryptosystems are one of the main techniques available in the area of Post-Quantum Cryptography. This work aims to propose a key encapsulation mechanism (KEM) with short ciphertext and secret key. Our goal is achieved in two steps. We first present a public key encryption (PKE) scheme, basicPKE, using a parity check matrix of Maximum Distance Separable (MDS) code as the public key matrix. In our construction, we exploit the structure of a companion matrix to obtain an MDS code which significantly reduces the storage of the secret key. The scheme basicPKE provides security against Indistinguishability under Chosen Plaintext Attacks (IND-CPA). Secondly, following the design framework of basicPKE, we construct another PKE scheme, fullPKE, that leads us to design our KEM scheme, fullKEM. We have shown that the scheme fullPKE is secure against One-Wayness under Plaintext and Validity Checking Attacks (OW-PCVA) and the scheme fullKEM achieves security against Indistinguishability under Chosen Ciphertext Attacks (IND-CCA) in the random oracle model. Moreover, our KEM can be shown to accomplish post-quantum security in the quantum random oracle model.

Proving the security of masked implementations in theoretical models that are relevant to practice and match the best known attacks of the side-channel literature is a notoriously hard problem. The random probing model is a good candidate to contribute to this challenge, due to its ability to capture the continuous nature of physical leakage (contrary to the threshold probing model), while also being convenient to manipulate in proofs and to automate with verification tools. Yet, despite recent progresses in the design of masked circuits with good asymptotic security guarantees in this model, existing results still fall short when it comes to analyze the security of concretely useful circuits under realistic noise levels and with low number of shares. In this paper, we contribute to this issue by introducing a new composability notion, the Probe Distribution Table (PDT), and a new tool (called STRAPS, for the Sampled Testing of the RAndom Probing Security). Their combination allows us to significantly improve the tightness of existing analyses in the most practical (low noise, low number of shares) region of the design space. We illustrate these improvements by quantifying the random probing security of an AES S-box circuit, masked with the popular multiplication gadget of Ishai, Sahai and Wagner from Crypto 2003, with up to six shares.

Structured encryption (STE) is a form of database encryption that enables searching directly over symmetrically encrypted "structured databases". STE is known to be vulnerable to leakage-abuse attacks that allow data/query reconstruction given only some auxiliary information about the original database. Many existing countermeasures against leakage-abuse attacks perturb the leakage from STE schemes so as to render the attacks infeasible in practice.

We present the first leakage-abuse attacks that achieve practically efficient and highly scalable query reconstruction against state-of-the-art STE schemes with perturbed leakage profiles while relying only no noisy co-occurrence pattern leakage and without making strong assumptions on the auxiliary information available to the adversary. Our attacks subvert the query privacy guarantees of STE schemes with differentially private access patterns (Chen et al., INFOCOM'18) and STE schemes built in a naturally efficient manner from volume-hiding encrypted multi-maps (Kamara and Moataz, Eurocrypt'19 and Patel et al., CCS'19).

Many existing leakage-abuse attacks only work in a strong known-data model where the auxiliary information available to the adversary is either an exact replica of or a "noise-free" subset of the target database. Our attacks are the first to work in a weaker and more realistic inference model where the auxiliary information available to the adversary is sampled independently from but statistically close to the target database. Compared to (a handful of) existing inference attacks, our attacks make significantly relaxed assumptions about the nature of auxiliary information available to the adversary.

Technically, our attacks exploit insufficiencies in existing leakage-perturbation techniques as well as novel observations surrounding inevitable system-wide leakage from efficient realizations of STE. We model the attacks as optimization problems with carefully designed objective functions that are maximized via simulated annealing. We demonstrate the practical effectiveness of our attacks via extensive experimentation over real-world databases. Our attacks achieve up to 90% query reconstruction against STE implementations using recommended security parameters, with 5x greater scalability than any existing attack exploiting access pattern leakage.

Side-channel and fault injection attacks reveal secret information by monitoring or manipulating the physical effects of computations involving secret variables. Circuit-level countermeasures help to deter these attacks, and traditionally such countermeasures have been developed for each attack vector separately. We demonstrate a multipurpose ring oscillator design - Programmable Ring Oscillator (PRO) to address both fault attacks and side-channel attacks in a generic, application-independent manner. PRO, as an integrated primitive, can provide on-chip side-channel resistance, power monitoring, and fault detection capabilities to a secure design. We present a grid of PROs monitoring the on-chip power network to detect anomalies. Such power anomalies may be caused by external factors such as electromagnetic fault injection and power glitches, as well as by internal factors such as hardware Trojans. By monitoring the frequency of the ring oscillators, we are able to detect the on-chip power anomaly in time as well as in location. Moreover, we show that the PROs can also inject a random noise pattern into a design's power consumption. By randomly switching the frequency of a ring oscillator, the resulting power-noise pattern significantly reduces the power-based side-channel leakage of a cipher. We discuss the design of PRO and present measurement results on a Xilinx Spartan-6 FPGA prototype, and we show that side-channel and fault vulnerabilities can be addressed at a low cost by introducing PRO to the design. We conclude that PRO can serve as an application-independent, multipurpose countermeasure.

The idea of smart contracts has been around for a long time. The introduction of Ethereum has taken the concept of smart contracts to new heights because of its integration with Blockchain technology. As a result, the applications of smart contracts have also surged in areas such as e-Voting, Insurance, Crowdfunding, etc. In this paper, we aim to present the construction of a “Fully Anonymous e-Voting” protocol using the concepts of zkHawk and Zcash. zkHawk is a novel smart contract protocol designed during this Ph.D. that improves upon the Hawk protocol by solving the underlying anonymity problem of a trusted manager. We will leverage the concept of zk-SNARKs in Zcash to carry out the voting phase of the election and the zkHawk smart contract protocol to tally the results of the election. The voting phase employing Zcash will be initially designed with Non-Universal zk-SNARKs and improved upon with Universal zk-SNARKs.

Consider the identification (ID) via channels problem, where a receiver decides whether the transmitted identifier is its identifier, rather than decoding it. This model allows to transmit identifiers whose size scales doubly-exponentially in the blocklength, unlike common transmission codes with exponential scaling. Binary constant-weight codes (CWCs) suffice to achieve the ID capacity. Relating parameters of a binary CWC to the minimum distance of a code and using higher-order correlation moments, two upper bounds on binary CWC sizes are proposed. These bounds are also upper bounds on identifier sizes for ID codes constructed by using binary CWCs. We propose two constructions based on optical orthogonal codes (OOCs), which are used in optical multiple access schemes, have constant-weight codewords, and satisfy cyclic cross-correlation and auto-correlation constraints. These constructions are modified and concatenated with outer Reed-Solomon codes to propose new binary CWCs being optimal for ID. Improvements to the finite-parameter performance of both our and existing code constructions are shown by using outer codes with larger minimum distance vs. blocklength ratios. We illustrate ID regimes for which our ID code constructions perform significantly better than existing constructions. An extensive list of other modified OOCs that can be used as binary CWCs is provided.

The Signal protocol is used in many messaging applications today. While it is an active research topic to design a post-quantum variant of the protocol, no such variant is currently realized in the real world. In the following document we describe a hybrid version of the Signal protocol, that will be implemented to achieve post-quantum security for Tutanota’s end-to-end encrypted e-mails.

This study proposes a chosen-ciphertext side-channel attack against a lattice-based key encapsulation mechanism (KEM), the third-round candidate of the national institute of standards and technology (NIST) standardization project. Unlike existing attacks that target operations such as inverse NTT and message encoding/decoding, we target Barrett Reduction in the decapsulation phase of CRYSTALS-KYBER to obtain a secret key. We show that a sensitive variable-dependent leakage of Barrett Reduction exposes an entire secret key. The results of experiments conducted on the ARM Cortex-M4 microcontroller accomplish a success rate of 100%. We only need six chosen ciphertexts for KYBER512 and KYBER768 and eight chosen ciphertexts for KYBER1024. We also show that the m4 scheme of the pqm4 library, an implementation with the ARM Cortex-M4 specific optimization (typically in assembly), is vulnerable to the proposed attack. In this scheme, six, nine, and twelve chosen ciphertexts are required for KYBER512, KYBER768, and KYBER1024, respectively.

OPAQUE [Jarecki et al., Eurocrypt 2018] is an asymmetric password authenticated key exchange (aPAKE) protocol that is being developed as an Internet standard and for use within TLS 1.3. OPAQUE combines an Oblivious PRF (OPRF) with an authenticated key exchange to provide strong security properties, including security against pre-computation attacks (called saPAKE security). However, the security of OPAQUE relies crucially on the security of the OPRF. If the latter breaks (by cryptanalysis, quantum attacks or security compromise), the user's password is exposed to an offline dictionary attack. To address this weakness, we present KHAPE, a variant of OPAQUE that does not require the use of an OPRF to achieve aPAKE security, resulting in improved resilience and near-optimal computational performance. An OPRF can be optionally added to KHAPE, for enhanced saPAKE security, but without opening the password to an offline dictionary attack upon OPRF compromise.

In addition to resilience to OPRF compromise, a DH-based implementation of KHAPE (using HMQV) offers the best performance among aPAKE protocols in terms of exponentiations with less than the cost of an exponentiation on top of an UNauthenticated Diffie-Hellman exchange. KHAPE uses three messages if the server initiates the exchange or four when the client does (one more than OPAQUE in the latter case).

All results in the paper are proven within the UC framework in the ideal cipher model. Of independent interest is our treatment of key-hiding AKE which KHAPE uses as a main component as well as our UC proofs of AKE security for protocols 3DH (a basis of Signal), HMQV and SKEME, that we use as efficient instantiations of KHAPE.

We introduce a new key generation mechanism where users can generate a ``back up key'', securely nested inside the secret key of a signature scheme.

Our main motivation is that in case of leakage of the secret key, established techniques based on zero-knowledge proofs of knowledge are void since the key becomes public. On the other hand, the ``back up key'', which is secret, can be used to generate a ``proof of ownership'', i.e., only the real owner of this secret key can generate such a proof. To the best of our knowledge, this extra level of security is novel, and could have already been used in practice, if available, in digital wallets for cryptocurrencies that suffered massive leakage of account private keys. In this work, we formalize the notion of ``Proof of Ownership'' and ``Fallback'' as new properties. Then, we introduce our construction, which is compatible with major designs for wallets based on ECDSA, and adds a $\mbox{W-OTS}^{+}$ signing key as a ``back up key''. Thus offering a quantum secure fallback. This design allows the hiding of any quantum secure signature key pair, and is not exclusive to $\mbox{W-OTS}^{+}$. Finally, we briefly discuss the construction of multiple generations of proofs of ownership.

Consider a scenario where Alice stores some secret data $s$ on $n$ servers using a $t$-out-of-$n$ secret sharing scheme. Trudy (the collector) is interested in the secret data of Alice and is willing to pay for it. Trudy publishes an advertisement on the internet which describes an elaborate cryptographic scheme to collect the shares from the $n$ servers. Each server who decides to submit its share is paid a hefty monetary reward and is guaranteed ``immunity" from being caught or prosecuted in a court for violating its service agreement with Alice. Bob is one of the servers and sees this advertisement. On examining the collection scheme closely, Bob concludes that there is no way for Alice to prove anything in a court that he submitted his share. Indeed, if Bob is rational, he might use the cryptographic scheme in the advertisement and submit his share since there are no penalties and no fear of being caught and prosecuted. Can we design a secret sharing scheme which Alice can use to avoid such a scenario?

We introduce a new primitive called as Traceable Secret Sharing to tackle this problem. In particular, a traceable secret sharing scheme guarantees that a cheating server always runs the risk of getting traced and prosecuted by providing a valid evidence (which can be examined in a court of law) implicating its dishonest behavior. We explore various definitional aspects and show how they are highly non-trivial to construct (even ignoring efficiency aspects). We then give an efficient construction of traceable secret sharing assuming the existence of a secure two-party computation protocol. We also show an application of this primitive in constructing traceable protocols for multi-server delegation of computation.

Your Tasks: • Specification of innovative and disruptive crypto & security solutions • Definition of crypto & security algorithms and related IP architectures • Definition of advanced crypto protocols • Definition of crypto & security mechanisms in hardware, firmware, etc. • Specification and review of crypto & security architectures • Detailed attack modeling and security mechanism specification for hardware and software blocks • Advising and training the product and IP teams on design, implementation and test • Root cause analysis of security defects • Technical interface to customers, evaluation labs and to the product development team • Certification support and technical interface with evaluator and certifier Your Profile: • Have a PhD/Master in Cryptography, Security or Mathematics • Very good knowledge of cryptography (incl. symmetric and asymmetric crypto) • Very good knowledge of discrete mathematics, algebra and number theory • Good knowledge of SoCs and/or Secure Element products • Good knowledge of crypto hardware implementation • Strong security background • Have >5 years of experience in embedded security • Used to an independent working style • Be willing to listen and to adapt • Very good communication skills • Be willing to travel

Closing date for applications:

Contact: Ulrich Althen

More information: https://nxp.wd3.myworkdayjobs.com/careers/job/Gratkorn/Principal-Cryptographer--m-f-d-_R-10028227

Event date: 17 December to 19 December 2021
Submission deadline: 8 August 2021
Notification: 12 September 2021

Closing Date 5th September 2021

The Department of Computer Science at the University of Surrey is seeking to appoint two Lecturers / Senior Lecturers in Cyber Security to strengthen its research within the Surrey Centre for Cyber Security (SCCS) and to support the Department’s ambitious strategic growth in this area. The appointments are on a full-time and permanent basis.

Of particular interest are the following research areas: applied cryptography, privacy enhancing technologies (incl. anonymisation, secure multi-party computation, computing on encrypted data), software security (e.g., malware analysis), system security (incl., security of autonomous or cyber-physical systems), security architectures (incl., trusted computing, TEEs), security protocols for blockchain and/or machine learning, or tool-assisted formal verification of security and privacy.

The Department of Computer Science has a world-class reputation in cyber security and regularly publishes at top-tier conferences and journals. The Department is home to Surrey Centre for Cyber Security (SCCS) and Surrey is only one of four institutions in the UK holding recognition from the National Cyber Security Centre as an Academic Centre of Excellence in both Cyber Security Research and in Cyber Security Education (Gold).

SCCS maintains close links with leading industries, the public sector and governmental bodies, leading to a strong heritage of real-world impact. The Department has made significant investment in its facilities with a new 200-seater computer science teaching laboratory, a virtual cloud computing platform, a secure systems facility and an HPC cluster for research.

We are interested in outstanding candidates with a strong record of publications in top-tier cyber security venues and, in particular for the Senior Lecturer post, with an established network of international collaborators from academia and/or industry and experience in attracting sustainable research funding.

Closing date for applications:

Contact:
Head of Department: Dr Mark Manulis (m.manulis@surrey.ac.uk).
Director of SCCS: Prof Steve Schneider (s.schneider@surrey.ac.uk)

More information: https://jobs.surrey.ac.uk/vacancy.aspx?ref=027721

A few research scientist positions are available at the Institute for Infocomm Research (I2R), A*STAR, Singapore. We are looking for capable and responsible scientists to work on and contribute to collaborative/federated/split/multi-party learning (data valuation, privacy, black-box and white-box models, etc.), machine learning, etc. Candidates with experience in privacy-preserving technologies (homomorphic encryption, MPC, differential privacy, etc.) in machine learning, particularly on secure algorithm/protocol design, are preferred. Successful candidates will work with a team to conduct R&D on applications and domains using a secure collaboration learning framework and time-series data. They will also have opportunities to work with local and international collaborators in academia. To apply for the position, please click on the link https://careers.a-star.edu.sg/jobdetails.aspx?ID=4147

Closing date for applications:

Contact: Singee

More information: https://careers.a-star.edu.sg/jobdetails.aspx?ID=4147

Many new ciphers target a concise algebraic description for efficient evaluation in a proof system or a multi-party computation. This new target for optimization introduces algebraic vulnerabilities, particularly involving Gröbner basis analysis. Unfortunately, the literature on Gröbner bases tends to be either purely mathematical, or focused on small fields. In this paper, we survey the most important algorithms and present them in an intuitive way. The discussion of their complexities enables researchers to assess the security of concrete arithmetization-oriented ciphers. Aside from streamlining the security analysis, this paper helps newcomers enter the field.