International Association
for Cryptologic Research

We introduce a new signature scheme, SQISign, (for Short Quaternion and Isogeny Signature) from isogeny graphs of supersingular elliptic curves. The signature scheme is derived from a new one-round, high soundness, interactive identification protocol. Targeting the post-quantum NIST-1 level of security, our implementation results in signatures of $204$ bytes, secret keys of $16$ bytes and public keys of $64$ bytes. In particular, the signature and public key sizes combined are an order of magnitude smaller than all other post-quantum signature schemes. On a modern workstation, our implementation in C takes 0.6s for key generation, 2.5s for signing, and 50ms for verification.

While the soundness of the identification protocol follows from classical assumptions, the zero-knowledge property relies on the second main contribution of this paper. We introduce a new algorithm to find an isogeny path connecting two given supersingular elliptic curves of known endomorphism rings. A previous algorithm to solve this problem, due to Kohel, Lauter, Petit and Tignol, systematically reveals paths from the input curves to a `special' curve. This leakage would break the zero-knowledge property of the protocol. Our algorithm does not directly reveal such a path, and subject to a new computational assumption, we prove that the resulting identification protocol is zero-knowledge.

Authenticated dictionaries (ADs) are a key building block of many cryptographic systems, such as transparency logs, distributed file systems and cryptocurrencies. In this paper, we propose a new notion of cross-incremental proof (dis)aggregation for authenticated dictionaries, which enables aggregating multiple proofs with respect to different dictionaries into a single, succinct proof. Importantly, this aggregation can be done incrementally and can be later reversed via disaggregation. We give an efficient authenticated dictionary construction from hidden-order groups that achieves cross-incremental (dis)aggregation. Our construction also supports updating digests, updating (cross-)aggregated proofs and precomputing all proofs efficiently. This makes it ideal for stateless validation in cryptocurrencies with smart contracts. As an additional contribution, we give a second authenticated dictionary construction, which can be used in more malicious settings where dictionary digests are adversarially-generated, but features only “one-hop” proof aggregation (with respect to the same digest). We add support for append-only proofs to this construction, which gives us an append-only authenticated dictionary (AAD) that can be used for transparency logs and, unlike previous AAD constructions, supports updating and aggregating proofs.

The hardness of Entropic LWE has been studied in a number of works. However, there is not work study the hardness of algebraically structured LWE with entropic secrets. In this work, we conduct a comprehensive study on establishing hardness reductions for Entropic Module-LWE and Entropic Ring-LWE. We show an entropy bound that guarantees the security of arbitrary Entropic Module-LWE and Entropic Ring-LWE, these are the first results on the hardness of algebraically structured LWE with entropic secrets. One of our central techniques is a new generalized leftover hash lemma over ring and a new decomposition theorem for continuous Gaussian distribution on KR, which might be of independent interests.

We present the first rigorous dynamic analysis of BKZ, the most widely used lattice reduction algorithm besides LLL: previous analyses were either heuristic or only applied to variants of BKZ. Namely, we provide guarantees on the quality of the current lattice basis during execution. Our analysis extends to a generic BKZ algorithm where the SVP-oracle is replaced by an approximate oracle and/or the basis update is not necessarily performed by LLL. Interestingly, it also provides quantitative improvements, such as better and simpler bounds for both the output quality and the running time. As an application, we observe that in certain approximation regimes, it is more efficient to use BKZ with an approximate rather than exact SVP-oracle.

The round complexity of Byzantine Broadcast (BB) has been a central question in distributed systems and cryptography. In the honest majority setting, expected constant round protocols have been known for decades even in the presence of a strongly adaptive adversary. In the corrupt majority setting, however, no protocol with sublinear round complexity is known, even when the adversary is allowed to {\it strongly adaptively} corrupt only 51\% of the players, and even under reasonable setup or cryptographic assumptions. Recall that a strongly adaptive adversary can examine what original message an honest player would have wanted to send in some round, adaptively corrupt the player in the same round and make it send a completely different message instead.

In this paper, we are the first to construct a BB protocol with sublinear round complexity in the corrupt majority setting. Specifically, assuming the existence of time-lock puzzles with suitable hardness parameters and that the decisional linear assumption holds in suitable bilinear groups}, we show how to achieve BB in $(\frac{n}{n-f})^2 \cdot \poly\log \lambda$ rounds with $1-\negl(\lambda)$ probability, where $n$ denotes the total number of players, $f$ denotes the maximum number of corrupt players, and $\lambda$ is the security parameter. Our protocol completes in polylogarithmically many rounds even when 99\% of the players can be corrupt.

In this paper, we investigate the use of machine learning classiers to assess block cipher security from the perspective of differential cryptanalysis. The models are trained using the general block cipher features, making them generalizable to an entire class of ciphers. The features include the number of rounds, permutation pattern, and truncated differences whereas security labels are based on the number of differentially active substitution boxes. Prediction accuracy is further optimized by investigating the different ways of representing the cipher features in the dataset. Machine learning experiments involving six classifiers (linear and nonlinear) were performed on a simplied generalized Feistel cipher as a proof-of-concept, achieving a prediction accuracy of up to 95%. When predicting the security of unseen cipher variants, prediction accuracy of up to 77% was obtained. Our ndings show that nonlinear classiers outperform linear classiers for the prediction task due to the nonlinear nature of block ciphers. In addition, results also indicate the feasibility of using the proposed approach in assessing block cipher security or as machine learning distinguishers

In the random oracle model (ROM), it is provable from the DL assumption, whereas there is negative circumstantial evidence in the standard model. Fleischhacker, Jager, and Schr\"{o}der showed that the tight security of the Schnorr signature is unprovable from a strong cryptographic assumption, such as the One-More DL (OM-DL) assumption and the computational and decisional Diffie-Hellman assumption, in the ROM via a generic reduction as long as the underlying cryptographic assumption holds. However, it remains open whether or not the impossibility of the provable security of the Schnorr signature from a strong assumption via a non-tight and reasonable reduction. In this paper, we show that the security of the Schnorr signature is unprovable from the OM-DL assumption in the non-programmable ROM as long as the OM-DL assumption holds. Our impossibility result is proven via a non-tight Turing reduction.

A boardroom election is an election with a small number of voters carried out with public communications. We present BVOT, a self-tallying boardroom voting protocol with ballot secrecy, fairness (no tally information is available before the polls close), and dispute-freeness (voters can observe that all voters correctly followed the protocol).

BVOT works by using a multiparty threshold homomorphic encryption system in which each candidate is associated with a masked unique prime. Each voter engages in an oblivious transfer with an untrusted distributor: the voter selects the index of a prime associated with a candidate and receives the selected prime in masked form. The voter then casts their vote by encrypting their masked prime and broadcasting it to everyone. The distributor does not learn the voter's choice, and no one learns the mapping between primes and candidates until the audit phase. By hiding the mapping between primes and candidates, BVOT provides voters with insufficient information to carry out effective cheating. The threshold feature prevents anyone from computing any partial tally---until everyone has voted. Multiplying all votes, their decryption shares, and the unmasking factor yields a product of the primes each raised to the number of votes received.

In contrast to some existing boardroom voting protocols, BVOT does not rely on any zero-knowledge proof; instead, it uses oblivious transfer to assure ballot secrecy and correct vote casting. Also, BVOT can handle multiple candidates in one election. BVOT prevents cheating by hiding crucial information: an attempt to increase the tally of one candidate might increase the tally of another candidate. After all votes are cast, any party can tally the votes.

We study in this work a particular class of QC-MDPC codes for which the decoding failure rate is significantly larger than for typical QC-MDPC codes of same parameters. Our purpose is to figure out whether the existence of such weak codes impacts the security of cryptographic schemes using QC-MDPC codes as secret keys. A class of weak keys was exhibited in [DGK19]. We generalize it and show that, though their Decoding Failure Rate (DFR) is higher than normal, the set is not large enough to contribute significantly to the average DFR. It follows that with the proper semantically secure transform [HHK17], those weak keys do not affect the IND-CCA status of key encapsulation mechanisms, like BIKE, which are using QC-MDPC codes.

A deniable authenticated key exchange can establish a secure communication channel while leaving no cryptographic evidence of communication. Some well-designed protocol today, even in the case of betrayal by some participants and disclosure of long-term key materials, cannot leave any cryptographic evidence. However, this is no longer enough: If “Big data” technology is used to analyse data fetched from pivotal nodes, it’s not difficult to register your identity through your long-term public keys. (although it can’t be a solid evidence due to deniability) In this article, we have analysed the advantages and disadvantages of existing solutions which are claimed to be deniable to some degree, and proposed an authenticated key exchange protocol that is able to conceal the public keys from the outside of the secure channel, and deniable to some degree, and a reference implementation is provided.

Event date: to
Submission deadline: 30 December 2020

There is one Ph.D. position opening at Dr. Jiafeng Harvest Xie's research group at the Department of Electrical and Computer Engineering of Villanova University, Villanova, PA (west of Philadelphia). The research topics of this position primarily focused on side-channel attack related analysis related to the post-quantum cryptosystems.

Interested ones are warmly welcomed to send their resume/CV to Dr. Xie through email: jiafeng.xie@villanova.edu

Requirements: preferred to be at the majors of Computer Science or Computer Engineering. Familiar with FPGA board related side-channel attack and analysis will be desirable. Proficiency in programming languages such as C/C++ and HDLs. Good at English communication and writing. Great enthusiasm of doing research oriented tasks. Excellent team work member.

Degree: both B.S. and M.S. graduates or similar are warmly welcomed to apply.

Deadline: better to start at Spring 2021, though Fall 2021 is also ok. It is always better to apply as early as possible. Position is open until it is filled.

The 2021 U.S. News & World Report ranks Villanova as tied for the 53th best National University in the U.S.

Closing date for applications:

Contact: Jiafeng Harvest Xie (jiafeng.xie@villanova.edu)

More information: https://www1.villanova.edu/villanova/engineering/departments/ece/facultyStaff/biodetail.html?mail=jiafeng.xie@villanova.edu&xsl=bio_long

We are looking for a PhD student in the domain of Scalable Privacy-preserving Data Sharing. The PhD position is available in Charles Sturt University's Wagga Wagga campus, led by Prof. Zia. The potential candidate is expected to investigate and devise efficient functional encrytion that is compatible with privacy risk metrics according to different types of data. The research requires theoretical encryption scheme construction as well as experimental implementation with industry collaboration.

This PhD position will be supported by the CSCRC with excellent scholarship. The CSCRC aims to inspire the next generation of cyber security professionals through working with some of the best cyber security researchers in Australia, and engagement with the CSCRC Industry & Government Participants. Further details of the CSCRC Government and Industry Participants may be found at: https://www.cybersecuritycrc.org.au (Cyber Security Research Scholarships of up to AU$50,000 a year for outstanding PhD students; these scholarships are limited to Australian nationals or candidates from other 5-Eyes countries (US, UK, Canada, New Zealand); candidates from NATO countries will be considered on a case by case basis. Successful candidates must be eligible to obtain Australian Government Cyber Security Clearance (where appropriate).)

In order to be considered for the position, the candidate must:
• Hold a Master's degree in mathematics, computer science, cryptography or related fields with strong grades;
• Show strong background in mathematics, computer science and cryptography;
• Demonstrate experience in C/C++ or Java.
Having prior publications in security and privacy is highly desirable.

Please send (by e-mail) to below contact information:
• Transcripts,
• Curriculum vitae,
• Statement of Purpose, and
• Academic IELTS Test Report (or equivlent qualification).
In addition, three reference letters are required by e-mail from referees.

Closing date for applications:

Contact: Prof. Tanveer Zia (tzia@csu.edu.au)

Boneh et al proposed the cryptographic primitive public key encryption with keyword search (PEKS) to search on encrypted data without exposing the privacy of the keyword. Most standard PEKS schemes are vulnerable to inside keyword guessing attacks (KGA), i.e., a malicious server may generate a ciphertext by its own and then to guess the keyword of the trapdoor by testing. Huang et al. solved this problem by proposing the public-key authenticated encryption with keyword search (PAEKS) achieving single trapdoor privacy (TP). Qin et al. defined notion of multi-ciphertext indistinguishability (MCI) security and multi-trapdoor privacy (MTP) security, and proposed the first PAEKS scheme with MCI and TP.

Certificateless public-key authenticated encryption with keyword search (CLPAEKS) is first formally proposed by He et al. as combination of the PAEKS and the certificateless public key cryptography (CLPKC). Lin et al. revised He's work and re-formalize the security requirements for CLPAEKS in terms of trapdoor privacy and ciphertext indistinguishability. However, how to achieve both MCI and MTP security in a CLPAEKS scheme is still unknown.

In this paper, we initially propose a CLPAEKS scheme with both MCI security and MTP security simultaneously. We provide formal proof of our schemes in the random oracle model.

Custodian is a core financial service in which the custodian holds in safekeeping assets on behalf of the client. Although traditional custody service is typically endorsed by centralized authorities, decentralized custody scheme has become technically feasible since the emergence of digital assets, and furthermore it is badly needed by new applications such as blockchain and DeFi (Decentralized Finance). In this work, we propose a framework of decentralized asset custody scheme that is able to support a large number of custodians and safely hold customer assets of multiple times value of the total security deposit. The proposed custody scheme distributes custodians and assets into many custodian groups via combinatorial designs and random sampling, where each group fully controls the assigned assets. Since every custodian group is small, the overhead cost is significantly reduced. The liveness is also improved because even a single alive group would be able to process transactions. The security of this custody scheme is guaranteed in the game-theoretic sense, such that any adversary corrupting a bounded fraction of custodians cannot move assets more than his own security deposit. We further analyze the security and performance of our constructions, and give explicit examples with concrete numbers and figures for a better understanding of our results.

Body Biasing Injection (BBI) uses a voltage applied with a physical probe onto the backside of the integrated circuit die. Compared to other techniques such as electromagnetic fault injection (EMFI) or Laser Fault Injection (LFI), this technique appears less popular in academic literature based on published results. It is hypothesized being due to (1) moderate cost of equipment, and (2) effort required in device preperation.

This work demonstrates that BBI (and indeed many other backside attacks) can be trivially performed on Wafer-Level Chip-Scale Packaging (WLCSP), which inherently expose the die backside. A low-cost ($15) design for the BBI tool is introduced, and validated with faults introduced on a STM32F415OG against code flow, RSA, and some initial results on various hardware block attacks are discussed.

textsf{Tweakable TWINE} (\twine) is the first lightweight dedicated tweakable block cipher family built on Generalized Feistel Structure (GFS). \twine family is an extension of the conventional block cipher \textsf{TWINE} with minimal modification by adding a simple tweak based on the SKINNY's tweakey schedule. Similar to \textsf{TWINE}, \twine has two variants, namely \twine[80] and \twine[128]. The two variants have the same block size of 64 bits and a variable key length of 80 and 128 bits. In this paper, we study the implications for adding the tweak on the security of \twine against the integral cryptanalysis. In particular, we first utilize the bit-based division property to search for the longest integral distinguisher. As a result, we are able to perform a distinguishing attack against 19 rounds using $2^{6} \times 2^{63} = 2^{69}$ chosen tweak-plaintext combinations. We then convert this attack to key recovery attacks against 26 and 27 rounds (out of 36) of \twine[80] and \twine[128], respectively. By prepending one round before the distinguisher and using dynamically chosen plaintexts, we manage to extend the attack one more round without using the full codebook of the plaintext. Therefore, we are able to attack 27 and 28 rounds of \twine[80] and \twine[128], respectively.

This paper proposes a simple synchronous composable security framework as an instantiation of the Constructive Cryptography framework, aiming to capture minimally, without unnecessary artefacts, exactly what is needed to state synchronous security guarantees. The objects of study are specifications (i.e., sets) of systems, and traditional security properties like consistency and validity can naturally be understood as specifications, thus unifying composable and property-based definitions. The framework's simplicity is in contrast to current composable frameworks for synchronous computation which are built on top of an asynchronous framework (e.g. the UC framework), thus not only inheriting artefacts and complex features used to handle asynchronous communication, but adding additional overhead to capture synchronous communication.

As a second, independent contribution we demonstrate how secure (synchronous) multi-party computation protocols can be understood as constructing a computer that allows a set of parties to perform an arbitrary, on-going computation. An interesting aspect is that the instructions of the computation need not be fixed before the protocol starts but can also be determined during an on-going computation, possibly depending on previous outputs.

Secure Multi-party Computation (MPC) allows a set of mutually distrusting parties to jointly evaluate a function on their private inputs while maintaining input privacy. In this work, we improve semi-honest secure two-party computation (2PC) over rings, with a focus on the efficiency of the online phase.

We propose an efficient mixed-protocol framework, outperforming the state-of-the-art 2PC framework of ABY. Moreover, we extend our techniques to multi- input multiplication gates without inflating the online communication, i.e., it remains independent of the fan-in. Along the way, we construct efficient protocols for several primitives such as scalar product, matrix multiplication, comparison, maxpool, and equality testing. The online communication of our scalar product is two ring elements irrespective of the vector dimension, which is a feature achieved for the first time in the 2PC literature.

The practicality of our new set of protocols is showcased with four applications: i) AES S-box, ii) Circuit-based Private Set Intersection, iii) Biometric Matching, and iv) Privacy- preserving Machine Learning (PPML). Most notably, for PPML, we implement and benchmark training and inference of Logistic Regression and Neural Networks over LAN and WAN networks. For training, we improve online runtime (both for LAN and WAN) over SecureML (Mohassel et al., IEEE S&P’17) in the range 1.5x-6.1x, while for inference, the improvements are in the range of 2.5x-754.3x.

Functional Encryption (FE) allows users who hold a specific secret key (known as the functional key) to learn a specific function of encrypted data whilst learning nothing about the content of the underlying data. Considering this functionality and the fact that the field of FE is still in its infancy, we sought a route to apply this potent tool to design efficient applications. To this end, we first built a symmetric FE scheme for the $\ell_1$ norm of a vector space, which allows us to compute the sum of the components of an encrypted vector. Then, we utilized our construction, to design an Order-Revealing Encryption (ORE) scheme and a privately encrypted database. While there is room for improvement in our schemes, this work is among the first attempts that seek to utilize FE for the solution of practical problems that can have a tangible effect on people's daily lives.