International Association
for Cryptologic Research

Key-Alternating Feistel (KAF) ciphers are a popular variant of Feistel ciphers whereby the round functions are defined as $x \mapsto F(k_i \oplus x)$, where k_i are the round keys and F is a public random function. Most Feistel ciphers, such as DES, indeed have such a structure. However, the security of this construction has only been studied in the classical CPA/CCA models. We provide the first security analysis of KAF ciphers in the key-dependent message (KDM) attack model, where plaintexts can be related to the private key. This model is motivated by cryptographic schemes used within application scenarios such as full-disk encryption or anonymous credential systems.

We show that the four-round KAF cipher, with a single function $F$ reused across the rounds, provides KDM security for a non-trivial set of KDM functions. To do so, we develop a generic proof methodology, based on the H-coefficient technique, that can ease the analysis of other block ciphers in such strong models of security.

Blockchain has been widely used in finance, logistics, copyright and other fields with its outstanding characteristics such as non-centralization, collective maintenance, openness, transparency and non-tamperability. However, as transactions are stored in plaintext in the blockchain for public verification, the anonymity and privacy of users can not be guaranteed and this hampers many financial applications. How to protect the privacy of transactions is worthy further research.

In this paper, we have proposed two regulatory and efficient confidential transaction schemes using homomorphic encrytion and zero-knowledge proof. The first one improves the efficiency of the existing ElGamal based scheme while preserves its privacy. The second one employs the Paillier encryption with homomorphic property and it empowers regulators with greater power to obtain transaction-related specific content. The core of ElGamal based scheme is the Modified ElGamal algorithm, which changes the form of the standard ElGamal algorithm and expands it into four ciphertexts such that $(m,r)$ in the transaction can be decrypted. The Paillier based scheme is mainly to combine Paillier encryption with ElGamal encryption. Contrast to other ElGamal based scheme, the combination makes any token amount can be directly decrypted without calculating a discrete logarithm problem. As any $(m,r)$ in transactions can be decrypted directly, game theory is applied to further reduce transaction size. In our construction, transactions are about 1.1KB.

The Department of Mathematics in the School of Sciences and Humanities at Nazarbayev University invites applications for several positions in applied mathematics at the rank of Instructor or Assistant Professor. The department currently has 23 members. Faculty specializations include statistics, numerical analysis, applied mathematics, analysis, and algebra/number theory, including cryptography. Appointments are for three years with the possibility of renewal.

Responsibilities of these positions:

• Teach undergraduate courses in mathematics;
• Advise students in academic matters;
• Administrative and service work at the departmental, school, and university level;
• Faculty appointed at the Assistant Professor level will also be expected to teach graduate courses in mathematics, supervise undergraduate and graduate student research and capstone projects, apply for grants, and develop new courses.

Applicants should submit a cover letter, a curriculum vitae, research and teaching statements, and contact information for at least three references, who will be asked to submit letters of recommendation. At least one of the letters of recommendation should address the candidate's teaching.

Closing date for applications:

Contact: Daniel Oliveira da Silva at daniel.dasilva@nu.edu.kz

More information: https://jobs.smartrecruiters.com/NazarbayevUniversity1/743999738292544-instructor-and-assistant-professor-position-department-of-mathematics-school-of-sciences-and-humanities

The Department of Computer Science at the University of Surrey, UK seeks to recruit Early Career Fellows (Lecturer A), on a full-time basis, for a period of up to five years. There are 3 positions with one being in cyber security, which includes cryptography. These positions are particularly well suited for recent PhD graduates or post-docs who want to develop their independent research agenda. The Department will seek to establish a long-term career planning for these post holders, with appropriate mentoring in place. Deadline for applications: 26th March 2021 Applicants will need to submit a research concept. Please follow the link for more information and application guidelines.

Closing date for applications:

Contact: Informal inquiries can be sent to Mark Manulis (m dot manulis at surrey dot uc dot uk)

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

Following the current direction in Deep Learning (DL), more recent papers have started to pay attention to the efficiency of DL in breaking cryptographic implementations. Several works focus on techniques to boost the efficiency of existing architectures by data augmentation, regularization, etc. In this work, we investigate using mixup data augmentation \cite{zhang2017mixup} in order to improve the efficiency of DL-based Side-Channel Attacks (SCAs). We validated the soundness of the mixup on real traces collected from the ChipWhisperer board \cite{cw} and from the ASCAD database \cite{benadjila2020deep}. The obtained results have proven that using mixup data augmentation decreases the number of measurements needed to reveal the secret key compared to the non-augmented case.

We propose Veksel, a simple generic paradigm for constructing efficient non-interactive coin mixes. The central component in our work is a concretely efficient proof $\pi_{one-many}$ that a homomorphic commitment $c^*$ is a rerandomization of a commitment $c \in \{c_1, \ldots, c_\ell \}$ without revealing $c$. We formalize anonymous account-based cryptocurrency as a universal composability functionality and show how to efficiently instantiate the functionality using $\pi_{one-many}$ in a straightforward way (Veksel). We instantiate and implement $\pi_{one-many}$ from Strong-RSA, DDH and random oracles targeting $\approx 112$ bits of security. The resulting NIZK has constant size ($|\pi_{one-many}| = 5.3 \text{KB}$) and constant proving/verification time ($\approx 90 \text{ms}$), on an already accumulated set. Compared to Zerocash---which offers comparable marginal verification cost and an anonymity set of every existing transaction---our transaction are larger ($6.2$ KB) and verification is slower. On the other hand, {\name} relies on more well-studied assumptions, does not require an expensive trusted setup for proofs and is arguably simpler (from an implementation standpoint). Additionally we think that $\pi_{one-many}$ might be interesting in other applications, e.g. proving possession of some credential posted on-chain.

The State-Separating Proofs (SSP) framework by Brzuska et al. (ASIACRYPT’18) proposes a novel way to perform modular, code-based game-playing proofs. In this work, we demonstrate the potential of SSP for guiding the development of formally verified security proofs of composed real-world protocols in the EasyCrypt proof assistant. In particular, we show how to extract an EasyCrypt formalization skeleton from an SSP formalization. As a concrete example, we study the Cryptobox protocol, a KEM-DEM construction that combines DH key agreement with authenticated encryption. We develop a Cryptobox formalization using SSP both on paper and in EasyCrypt, exploring the usefulness of the SSP method in conjunction with an automated proof construction and verification tool.

We present Spectrum, a high-bandwidth, metadata-private file broadcasting system with malicious security guarantees. In Spectrum, a small number of publishers broadcast to many subscribers via two or more non-colluding servers. Subscribers generate indistinguishable cover traffic, hiding which users are publishers, for full metadata privacy.

Spectrum builds on prior work that uses DC-nets for anonymous broadcast. Existing anonymous broadcast systems do not optimize for a setting where there are fewer publishers compared to subscribers -- a common situation in real-world broadcasts. To prevent disruption by malicious clients sending malformed requests, we develop a blind request authentication protocol that allows servers to reject malicious clients deviating from protocol. We also ensure security against malicious servers deviating from protocol and potentially colluding with clients. Our techniques for providing malicious security are applicable to other systems for anonymous broadcast and may be of independent interest.

We implement and evaluate Spectrum. Compared to the state-of-the-art in cryptographic anonymous communication systems, Spectrum is 3--140X faster (and commensurately cheaper). Deployed on two commodity servers, Spectrum allows publishers to share 500 MB in 1h 24m with an anonymity set of 10,000 (for a total cost of about $1.93). This corresponds to an anonymous upload of a full-length 720p documentary movie.

As the world adopts Artificial Intelligence (AI), the privacy risks are many. AI can improve our lives, but may leak or misuse our private data. Private AI is based on Homomorphic Encryption (HE), a new encryption paradigm which allows the cloud to operate on private data in encrypted form, without ever decrypting it, enabling private training and private prediction with AI algorithms. The 2016 ICML CryptoNets [26] paper demonstrated for the first time evaluation of neural net predictions on homomorphically encrypted data, and opened new research directions combining machine learning and cryptography. The security of Homomorphic Encryption is based on hard problems in mathematics involving lattices, a candidate for post-quantum cryptography. This paper gives an overview of my Invited Plenary Lecture at the International Congress of Industrial and Applied Mathematics (ICIAM), explaining Homomorphic Encryption, Private AI, and real-world applications.

What is the funniest number in cryptography? 0. The reason is that for all x, x*0 = 0, i.e., the equation is always satisfied no matter what x is. This article discusses crypto bugs in four BLS signatures’ libraries (ethereum/py ecc, supranational/blst, herumi/bls, sigp/milagro bls) that revolve around 0. Furthermore, we develop ”splitting zero” attacks to show a weakness in the proof-of-possession aggregate signature scheme standardized in BLS RFC draft v4. Eth2 bug bounties program generously awarded $35,000 in total for the reported bugs.

Succinct non-interactive arguments of knowledge (SNARKs) enable non-interactive efficient verification of NP computations and admit short proofs. However, all current SNARK constructions assume that the statements to be proven can be efficiently represented as either Boolean or arithmetic circuits over finite fields. For most constructions, the choice of the prime field $\mathbb{F}_{p}$ is limited by the existence of groups of matching order for which secure bilinear maps exist.

In this work, we overcome such restrictions and enable verifying computations over rings. We construct the first designated-verifier SNARK for statements which are represented as circuits over a broader kind of commutative rings, namely those containing big enough \emph{exceptional set}. Exceptional sets consist of elements such that their pairwise differences are invertible. Our contribution is threefold: We fist introduce Quadratic Ring Programs (QRPs) as a characterization of NP where the arithmetic is over a ring and we generalize pre-existent assumptions employed in field-restricted SNARKs to the ring context.

We construct ring SNARKs from framework based on encodings, inspired by the Pinocchio. Our scheme is modular, based on generic encodings over rings and allows for various instantiations in order to adapt to different settings. Finally, we propose two applications for our SNARKs. In the first one, we instantiate our construction for the Galois Rings $GR(2^k, d)$, i.e. the degree-$d$ Galois extension of $\mathbb{Z}_{2^k}$. This allows us to naturally prove statements about circuits over $\mathbb{Z}_{2^{64}}$, which closely matches real-life computer architectures such as standard CPUs. Our second application is verifiable computation over encrypted data, specifically for evaluations of Ring-LWE-based homomorphic encryption schemes.

The increasing deployment of end-to-end encrypted communications services has ignited a debate between technology firms and law enforcement agencies over the need for lawful access to encrypted communications. Unfortunately, existing solutions to this problem suffer from serious technical risks, such as the possibility of operator abuse and theft of escrow key material. In this work we investigate the problem of constructing law enforcement access systems that mitigate the possibility of unauthorized surveillance. We first define a set of desirable properties for an abuse-resistant law enforcement access system (ARLEAS), and motivate each of these properties. We then formalize these definitions in the Universal Composability framework, and present two main constructions that realize this definition. The first construction enables prospective access, allowing surveillance only if encryption occurs after a warrant has been issued and activated. The second, more powerful construction, allows retrospective access to communications that occurred prior to a warrant's issuance. To illustrate the technical challenge of constructing the latter type of protocol, we conclude by investigating the minimal assumptions required to realize these systems.

The KEM BIKE is a Round-3 alternative finalist in the NIST Post-Quantum Cryptography project. It uses the FO$^{\not \bot}$ transformation so that an instantiation with a decoder that has a DFR of $2^{-128}$ will make it IND-CCA secure. The current BIKE design does not bind the randomness of the ciphertexts (i.e., the error vectors) to a specific public key. We propose to change this design, although currently, there is no attack that leverages this property. This modification can be considered if BIKE is eventually standardized.

Tradeoff attacks on symmetric ciphers can be considered as the generalization of the exhaustive search. Their main objective is reducing the time complexity by exploiting the memory after preparing very large tables at a cost of exhaustively searching all the space during the precomputation phase. It is possible to utilize data (plaintext/ciphertext pairs) in some cases like the internal state recovery attacks for stream ciphers to speed up further both online and offline phases. However, how to take advantage of data in a tradeoff attack against block ciphers for single key recovery cases is still unknown. We briefly assess the state of art of tradeoff attacks on symmetric ciphers, introduce some open problems and discuss the security criterion on state sizes. We discuss the strict lower bound for the internal state size of keystream generators and propose more practical and fair bound along with our reasoning. The adoption of our new criterion can break a fresh ground in boosting the security analysis of small keystream generators and in designing ultra-lightweight stream ciphers with short internal states for their usage in specially low source devices such as IoT devices, wireless sensors or RFID tags.

In this paper, we describe Oblivious TLS: an MPC protocol that we prove UC secure against a majority of actively corrupted parties. The protocol securely implements TLS 1.3. Thus, any party P who runs TLS can communicate securely with a set of servers running Oblivious TLS; P does not need to modify anything, or even be aware that MPC is used. Applications of this include communication between servers who offer MPC services and clients, to allow the clients to easily and securely provide inputs or receive outputs. Also, an organization could use Oblivious TLS to improve in-house security while seamlessly connecting to external parties. Our protocol runs in the preprocessing model, and we did a preliminary non-optimized implementation of the on-line phase. In this version, the hand-shake completes in about 1 second. Performance of the record protocol depends, of course, on the encryption scheme used. We designed an MPC friendly scheme which achieved a throughput of about 300 KB/sec. Based on implementation results from other work, the standard AES-GCM can be expected to be as fast, although our implementation did not do as well.

Edge computing and caching have emerged as key technologies in the future communication network to enhance the user experience, reduce backhaul traffic, and enable various Internet of Things applications. Different from conventional resources like CPU and memory that can be utilized by only one party at a time, a cached data item, which can be considered as a public good, can serve multiple parties simultaneously. Therefore, instead of independent caching, it is beneficial for the parties (e.g., Telcos) to cooperate and proactively store their common items in a shared cache that can be accessed by all the parties at the same time.

In this work, we present MPCCache, a novel privacy-preserving Multi-party Cooperative Cache sharing framework, which allows multiple network operators to determine a set of common data items with the highest access frequencies to be stored in their capacity-limited shared cache while guaranteeing the privacy of their individual datasets. The technical core of our MPCCache is a new construction that allows multiple parties to compute a specific function on the intersection set of their datasets, without revealing the intersection itself to any party.

We evaluate our protocols to demonstrate their practicality and show that MPCCache scales well to large datasets and achieves a few hundred times faster compared to a baseline scheme that optimally combines existing MPC protocols.

We present a new construction of maliciously-secure, two-round multiparty computation (MPC) in the CRS model, where the first message is reusable an unbounded number of times. The security of the protocol relies on the Learning Parity with Noise (LPN) assumption with inverse polynomial noise rate 1/n^{1-epsilon} for small enough epsilon, where n is the LPN dimension. Prior works on reusable two-round MPC required assumptions such as DDH or LWE that imply some flavor of homomorphic computation. We obtain our result in two steps:

We obtain the first construction of this primitive from an assumption that is not known to support general homomorphic operations.

In the first step, we construct a two-round MPC protocol in the silent pre-processing model (Boyle et al., Crypto 2019). Specifically, the parties engage in a computationally inexpensive setup procedure that generates some correlated random strings. Then, the parties commit to their inputs. Finally, each party sends a message depending on the function to be computed, and these messages can be decoded to obtain the output. Crucially, the complexity of the pre-processing phase and the input commitment phase do not grow with the size of the circuit to be computed. We call this multiparty silent NISC, generalizing the notion of two-party silent NISC of Boyle et al. (CCS 2019). We provide a construction of multiparty silent NISC from LPN in the random oracle model.

In the second step, we give a transformation that removes the pre-processing phase and use of random oracle from the previous protocol. This transformation additionally adds (unbounded) reusability of the first round message, giving the first construction of reusable two-round MPC from the LPN assumption. This step makes novel use of randomized encoding of circuits (Applebaum et al., FOCS 2004) and a variant of the ``tree of MPC messages" technique of Ananth et al. and Bartusek et al. (TCC 2020).

Fully homomorphic encryption (FHE) allows to compute any function on encrypted values. However, in practice, there is no universal FHE scheme that is efficient in all possible use cases. In this work, we show that FHE schemes suitable for arithmetic circuits (e.g. BGV or BFV) have a similar performance as FHE schemes for non-arithmetic circuits (TFHE) in basic comparison tasks such as less-than, maximum and minimum operations. Our implementation of the less-than function in the HElib library is up to 3 times faster than the prior work based on BGV/BFV. It allows to compare a pair of 64-bit integers in 11 milliseconds, sort 64 32-bit integers in 19 seconds and find the minimum of 64 32-bit integers in 9.5 seconds on an average laptop without multi-threading.

All-or-nothing transforms have been defined as bijective mappings on all s-tuples over a specified finite alphabet. These mappings are required to satisfy certain "perfect security" conditions specified using entropies of the probability distribution defined on the input s-tuples. Alternatively, purely combinatorial definitions of AONTs have been given, which involve certain kinds of "unbiased arrays". However, the combinatorial definition makes no reference to probability definitions.

In this paper, we examine the security provided by AONTs that satisfy the combinatorial definition. The security of the AONT can depend on the underlying probability distribution of the s-tuples. We show that perfect security is obtained from an AONT if and only if the input s-tuples are equiprobable. However, in the case where the input s-tuples are not equiprobable, we still achieve a weaker security guarantee. We also consider the use of randomized AONTs to provide perfect security for a smaller number of inputs, even when those inputs are not equiprobable.

Efficient rank estimation algorithms are of prime interest in security evaluation against side-channel attacks (SCA) and recently also for password strength estimators. In a side channel setting it allows estimating the remaining security after an attack has been performed, quantified as the time complexity and the memory consumption required to brute force the key given the leakages as probability distributions over $d$ subkeys (usually key bytes). In password strength estimators the rank estimation allows estimating how many attempts a password cracker would need until it finds a given password. We propose ESrank, the first rank estimation algorithm with a bounded error ratio: its error ratio is bounded by $\gamma^{2d-2}$, for any probability distribution, where $d$ is the number of subkey dimensions and $\gamma>1$ can be chosen according to the desired accuracy. ESrank is also the first rank estimation algorithm that enjoys provable poly-logarithmic time- and space-complexity. Our main idea is to use exponential sampling to drastically reduce the algorithm's complexity.

We evaluated the performance of ESrank on real SCA and password strength corpora. We show ESrank gives excellent rank estimation with roughly a 1-bit margin between lower and upper bounds in less than 1 second on the SCA corpus and 4 seconds preprocessing time and 7$\mu$sec lookup time on the password strength corpus.