International Association
for Cryptologic Research

The introduction of the automatic search boosts the cryptanalysis of symmetric-key primitives to some degree. However, the performance of the automatic search is not always satisfactory for the search of long trails or ciphers with large state sizes. Compared with the extensive attention on the enhancement for the search with the mixed integer linear programming (MILP) method, few works care for the acceleration of the automatic search with the Boolean satisfiability problem (SAT) or satisfiability modulo theories (SMT) method. This paper intends to fill this vacancy. Firstly, with the additional encoding variables of the sequential counter circuit for the original objective function in the standard SAT method, we put forward a new encoding method to convert the Matsui's bounding conditions into Boolean formulas. This approach does not rely on new auxiliary variables and significantly reduces the consumption of clauses for integrating multiple bounding conditions into one SAT problem. Then, we evaluate the accelerating effect of the novel encoding method under different sets of bounding conditions. With the observations and experience in the tests, a strategy on how to create the sets of bounding conditions that probably achieve extraordinary advances is proposed. The new idea is applied to search for optimal differential and linear characteristics for multiple ciphers. For PRESENT, GIFT-64, RECTANGLE, LBlock, TWINE, and some versions in SIMON and SPECK families of block ciphers, we obtain the complete bounds (full rounds) on the number of active S-boxes, the differential probability, as well as the linear bias. The acceleration method is also employed to speed up the search of related-key differential trails for GIFT-64. Based on the newly identified 18-round distinguisher with probability $2^{-58}$, we launch a 26-round key-recovery attack with $2^{60.96}$ chosen plaintexts. To our knowledge, this is the longest attack on GIFT-64. Lastly, we note that the attack result is far from threatening the security of GIFT-64 since the designers recommended users to double the number of rounds under the related-key attack setting.

This paper presents three attack vectors of bit-wise cryptanalysis including rotational, bit-wise differential, and zero-sum distinguishing attacks on the AND-RX permutation Friet-PC, which is implemented in a lightweight authenticated encryption scheme Friet. First, we propose a generic procedure for a rotational attack on AND-RX cipher with round constants. By applying the proposed attack to Friet-PC, we can construct an 8-round rotational distinguisher with a time complexity of 2^{102}. Next, we explore single- and dual-bit differential biases, which are inspired by the existing study on Salsa and ChaCha, and observe the best bit-wise differential bias with 2^{−9.552}. This bias allows us to practically construct a 9-round bit-wise differential distinguisher with a time complexity of 2^{20.044}. Finally, we construct 13-, 15-, 17-, and 30-round zero-sum distinguishers with time complexities of 2^{31}, 2^{63}, 2^{127}, and 2^{383}, respectively. To summarize our study, we apply three attack vectors of bit-wise cryptanalysis to Friet-PC and show their superiority as effective attacks on AND-RX ciphers.

Sharding is an emerging technique to overcome scalability issues on blockchain based public ledgers. Without sharding, every node in the network has to listen to and process all ledger protocol messages. The basic idea of sharding is to parallelize the ledger protocol: the nodes are divided into smaller subsets that each take care of a fraction of the original load by executing lighter instances of the ledger protocol, also called shards. The smaller the shards, the higher the efficiency, as by increasing parallelism there is less overhead in the shard consensus.

In this vein, we propose a novel approach that leverages the sharding safety-liveness dichotomy. We separate the liveness and safety in shard consensus, allowing us to dynamically tune shard parameters to achieve essentially optimal efficiency for the current corruption ratio of the system. We start by sampling a relatively small shard (possibly with a small honesty ratio), and we carefully trade-off safety for liveness in the consensus mechanism to tolerate small honesty without losing safety. However, for a shard to be live, a higher honesty ratio is required in the worst case. To detect liveness failures, we use a so-called control chain that is always live and safe. Shards that are detected to be not live are resampled with increased shard size and liveness tolerance until they are live, ensuring that all shards are always safe and run with optimal efficiency. As a concrete example, considering a population of 10K parties, 30% corruption and 60-bit security, our design permits shards of size 200 parties in contrast to 6K parties in previous designs.

Moreover, in this highly concurrent execution setting, it is paramount to guarantee that both the sharded ledger protocol and its sub protocols (e.g., the shards) are secure under composition. To prove the security of our approach, we present ideal functionalities capturing a sharded ledger as well as ideal functionalities capturing the control chain and individual shard consensus, which needs adjustable liveness. We further formalize our protocols and prove that they securely realize the sharded ledger functionality in the UC framework.

The inherent difficulty of maintaining stateful environments over long periods of time gave rise to the paradigm of serverless computing, where mostly-stateless components are deployed on demand to handle computation tasks, and are teared down once their task is complete. Serverless architecture could offer the added benefit of improved resistance to targeted denial-of-service attacks, by hiding from the attacker the physical machines involved in the protocol until after they complete their work. Realizing such protection, however, requires that the protocol only uses stateless parties, where each party sends only one message and never needs to speaks again. Perhaps the most famous example of this style of protocols is the Nakamoto consensus protocol used in Bitcoin: A peer can win the right to produce the next block by running a local lottery (mining), all while staying covert. Once the right has been won, it is executed by sending a single message. After that, the physical entity never needs to send more messages.

We refer to this as the You-Only-Speak-Once (YOSO) property, and initiate the formal study of it within a new model that we call the YOSO model. Our model is centered around the notion of roles, which are stateless parties that can only send a single message. Crucially, our modelling separates the protocol design, that only uses roles, from the role-assignment mechanism, that assigns roles to actual physical entities. This separation enables studying these two aspects separately, and our YOSO model in this work only deals with the protocol-design aspect.

We describe several techniques for achieving YOSO MPC; both computational and information theoretic. Our protocols are synchronous and provide guaranteed output delivery (which is important for application domains such as blockchains), assuming honest majority of roles in every time step. We describe a practically efficient computationally-secure protocol, as well as a proof-of-concept information theoretically secure protocol.

Abstract

Modern cryptographic algorithms have an enormous key diversity, so if we want to test their strength for all the keys, it will take practically an infinite time. To avoid this, we use the sampling method, in which we examine a much smaller number of keys n and then we make estimation for the total key population N with a predetermined sampling error. For the generation of the n cipher outputs (samples) with the n corresponding keys, the critical questions are how many samples we will test and how large must be the size of each sample. The general rule is that, the sampling error is reduced as we increase the number of the samples. But since the tests must be executed in an acceptable time, we must compromise the above rule with some additional factors, such as the type of the cryptographic cipher, the kind and the size of the plain information and of course the available computer power. In this study we examine the interrelations of all the above factors, and we propose applicable solutions.

Keywords: Cryptography, Data encryption, Communication security, Computer security, Data security, Information security.

Event date: 21 August to 16 August 2021
Submission deadline: 25 April 2021

Event date: 19 July to 20 July 2021

Event date: 4 October to 6 October 2021
Submission deadline: 10 May 2021
Notification: 30 June 2021

The Naval Postgraduate School (NPS) is accepting applications for the position of Assistant or Associate Professor (tenure-track) in the Department of Computer Science. We encourage all qualified candidates to apply and are especially interested in candidates with a background in artificial intelligence, data science, distributed systems, machine learning, or security. We seek to fill the position by June 2021 and will consider applications beginning 30 March 2021. Additional position details can be found at: https://main.hercjobs.org/jobs/14480892

Closing date for applications:

Contact: Geoff Xie, Search Committee Chair

More information: https://main.hercjobs.org/jobs/14480892

Postdoc positions are available in the Cryptology and Data Security research group at the Institute of Computer Science, University of Bern, led by Christian Cachin.

Our research addresses all aspects of security in distributed systems, especially cryptographic protocols, consistency, consensus, and cloud-computing security. We are particularly interested in blockchains, distributed ledger technology, cryptocurrencies, and their security and economics.

Candidates should have a strong background in computer science. They should like conceptual, rigorous thinking for working theoretically, or be interested in building innovative systems for working practically. Demonstrated expertise in cryptography, distributed computing, or blockchain technology is a plus. Applicants should hold a Ph.D., with contributions in the relevant research topics.

Positions are available starting immediately and come with a competitive salary. The selection process runs until suitable candidates have been found. The University of Bern conducts excellent research and lives up its vision that “Knowledge generates value”. The city of Bern lies in the center of Switzerland and offers some of the highest quality of life worldwide.

If you are interested, please apply be sending email with one single PDF file and subject line set to Application for Postdoc addressed directly to Prof. Christian Cachin at crypto (at) inf.unibe.ch.

Closing date for applications:

Contact: For more information, please contact Christian Cachin (https://crypto.unibe.ch/cc/).

More information: https://crypto.unibe.ch/jobs/

The Cybersecurity - Identity Management group at the Hasso-Plattner-Institute (HPI), University of Potsdam is looking for a motivated PhD student or Postdoc in the area of cryptography and privacy.

Your future tasks

• Development and analysis of provably secure cryptographic protocols for real-world problems. Topics of interest include (but are not limited to):
  • Privacy-enhancing technologies
  • Password-based cryptography
  • Foundations and solutions for real-world cryptography
• Publish and present results at top-tier international conferences
• Participate in teaching activities

Your skills

• Master’s degree (or PhD for postdoctoral position) in Computer Science, Mathematics, or a related area by the time of appointment
• Profound knowledge in the areas of cryptography and IT security (for postdoctoral candidates proven in the form of publications in these areas)
• Excellent English language skills

We look forward to your application including a CV and motivation letter. Applications for the PhD position should also include a list of attended Master courses and grades, whereas applications for the Postdoc position should include contact information for two references. Please submit your application documents in a single PDF file via email.

Closing date for applications:

Contact: Anja Lehmann (anja.lehmann [at] hpi.de)

More information: https://hpi.de/lehmann/home.html

The APSIA group led by Peter Y.A. Ryan is offering a post-doc position in a research project on future-proofing privacy of secure electronic voting led by Johannes Müller. The position is fully funded for 2 years and may be extended up to 5 years.

Your Role

The candidate will shape research directions and produce results in one or more of the following topics:

• Protocol security
• Post-quantum cryptography
• Information-theoretic security
• Implementation of security protocols

Your Profile

• A PhD degree in Computer Science, Applied Mathematics or a related field
• Competitive research record in (applied) cryptography or protocol security
• Experience with secure e-voting or protocol security proofs is a plus
• Experience with post-quantum cryptography or information-theoretic security is a plus
• Experience with implementation of security protocols is a plus

Please apply online formally through the HR system (see link). Applications by email will not be considered.

Closing date for applications:

Contact: Johannes Müller

More information: https://recruitment.uni.lu/en/details.html?id=QMUFK026203F3VBQB7V7VV4S8&nPostingID=57676&nPostingTargetID=80219&mask=karriereseiten&lg=UK

We are looking for an assistant/associate professor to extend and complement the cryptology research and teaching of the Cyber Security Section at DTU Compute. The position is available from August 1 2021 or according to mutual agreement.

Closing date for applications:

Contact: Professor Lars Ramkilde Knudsen, lrkn@dtu.dk. Please use the above link when applying for the position. Applications sent by email will not be considered.

More information: https://www.dtu.dk/english/about/job-and-career/vacant-positions/job?id=fa3c2175-2322-42c9-b822-167147cf4e70

We introduce the first construction for secure two-party computation of Poisson regression, which enables two parties who hold shares of the input samples to learn only the resulting Poisson model while protecting the privacy of the inputs.

Our construction relies on new protocols for secure fixed-point exponentiation and correlated matrix multiplications. Our secure exponentiation construction avoids expensive bit decomposition and achieves orders of magnitude improvement in both online and offline costs over state of the art works. As a result, the dominant cost for our secure Poisson regression are matrix multiplications with one fixed matrix. We introduce a new technique, called correlated Beaver triples, which enables many such multiplications at the cost of roughly one matrix multiplication. This further brings down the cost of secure Poisson regression.

We implement our constructions and show their extreme efficiency. Our secure exponentiation for 20-bit fractional precision takes less than 0.07ms. One iteration of Poisson regression on a dataset with 10,000 samples with 1000 binary features, requires 16.47s offline time, 23.73s online computation and 7.279MB communication. For several real datasets this translates into training that takes seconds and only a couple of MB communication.

Iterative methods are a standard technique in many areas of scientific computing. The key idea is that a function is applied repeatedly until the resulting sequence converges to the correct answer. When applying such methods in a secure computation methodology (for example using MPC, FHE, or SGX) one either needs to perform enough steps to ensure convergence irrespective of the input data, or one needs to perform a convergence test within the algorithm, and this itself leads to a leakage of data. Using the Banach Fixed Point theorem, and its extensions, we show that this data-leakage can be quantified. We then apply this to a secure (via MPC) implementation of the PageRank methodology. For PageRank we show that allowing this small amount of data-leakage produces a much more efficient secure implementation, and that for many underlying graphs this `leakage' is already known to any attacker.

Bitcoin transfers value on a public ledger of transactions anyone can verify. Coin ownership is defined in terms of public keys. Despite potential use for private transfers, research has shown that users’ activity can often be traced in practice. Businesses have been built on dragnet surveillance of Bitcoin users because of this lack of strong privacy, which harms its fungibility, a basic property of functional money. Although the public nature of this design lacks strong guarantees for privacy, it does not rule it out. A number of methods have been proposed to strengthen privacy. Among these is CoinJoin, an approach based on multiparty transactions that can introduce ambiguity and break common assumptions that underlie heuristics used for deanonymization. Existing implementations of CoinJoin have several limitations which may partly explain the lack of their widespread adoption. This work introduces WabiSabi, a new protocol for centrally coordinated CoinJoin implementations utilizing keyed verification anonymous credentials and homomorphic value commitments. This improves earlier approaches which utilize blind signatures in both privacy and flexibility, enabling novel use cases and reduced overhead.

Threshold ECDSA signatures provide a higher level of security to a crypto wallet since it requires more than t parties out of n parties to sign a transaction. The state-of-the-art bandwidth efficient threshold ECDSA used the additive homomorphic Castagnos and Laguillaumie (CL) encryption based on an unknown order group G, together with a number of zero-knowledge proofs in G. In this paper, we propose compact zero-knowledge proofs for threshold ECDSA to lower the communication bandwidth, as well as the computation cost. The proposed zero-knowledge proofs include the discrete-logarithm relation in G and the well-formedness of a CL ciphertext.

When applied to two-party ECDSA, we can lower the bandwidth of the key generation algorithm by 47%, and the running time for the key generation and signing algorithms are boosted by about 35% and 104% respectively. When applied to threshold ECDSA, our first scheme is more optimized for the key generation algorithm (about 70% lower bandwidth and 70% faster computation in key generation, at a cost of 20% larger bandwidth in signing), while our second scheme has an all-rounded performance improvement (about 60% lower bandwidth, 27% faster computation in key generation without additional cost in signing).

The Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski/Fan-Vercauteren (BFV) schemes are the two main homomorphic encryption (HE) schemes to perform exact computations over finite fields and integers. Although the schemes work with the same plaintext space, there are significant differences in their noise management, algorithms for the core homomorphic multiplication operation, message encoding, and practical usability. The main goal of our work is to revisit both schemes, focusing on closing the gap between the schemes by improving their noise growth, computational complexity of the core algorithms, and usability. The other goal of our work is to provide both theoretical and experimental performance comparison of BGV and BFV.

More precisely, we propose an improved variant of BFV where the encryption operation is modified to significantly reduce the noise growth, which makes the BFV noise growth somewhat better than for BGV (in contrast to prior results showing that BGV has smaller noise growth for larger plaintext moduli). We also modify the homomorphic multiplication procedure, which is the main bottleneck in BFV, to reduce its algorithmic complexity. Our work introduces several other novel optimizations, including lazy scaling in BFV homomorphic multiplication and an improved BFV decryption procedure in the Residue Number System (RNS) representation. We also develop a usable variant of BGV as a more efficient alternative to BFV for common practical scenarios.

We implement our improved variants of BFV and BGV in PALISADE and evaluate their experimental performance for several benchmark computations. Our results suggest that BGV is faster for intermediate and large plaintext moduli, which are often used in practical scenarios with ciphertext packing, while BFV is faster for small plaintext moduli.

Anonymous tokens have recent applications in private Internet browsing and anonymous statistics collection. We develop new schemes in order to include public metadata such as expiration dates for tokens. This inclusion enables planned mass revocation of tokens without distributing new keys, which for natural instantiations can give 77 - 90 % amortized traffic savings compared to Privacy Pass (Davidson et al., 2018) and PrivateStats (Huang et al., 2021), respectively. By transforming the public key, we are able to append public metadata to several existing protocols without having to change the security proofs in any substantial way.

Additional contributions include expanded definitions and a description of how anonymous tokens can improve the privacy in dp3t-like digital contact tracing applications. We also show how to create efficient and conceptually simple tokens with public metadata and public verifiability from pairings.

We study when (dual) Vandermonde systems of the form ${V}_T^{{(\intercal)}} \cdot \vec{z} = s\cdot \vec{w}$ admit a solution $\vec{z}$ over a ring $\mathcal{R}$, where ${V}_T$ is the Vandermonde matrix defined by a set $T$ and where the "slack" $s$ is a measure of the quality of solutions. To this end, we propose the notion of $(s,t)$-subtractive sets over a ring $\mathcal{R}$, with the property that if $S$ is $(s,t)$-subtractive then the above (dual) Vandermonde systems defined by any $t$-subset $T \subseteq S$ are solvable over $\mathcal{R}$. The challenge is then to find large sets $S$ while minimising (the norm of) $s$ when given a ring $\mathcal{R}$.

By constructing families of $(s,t)$-subtractive sets $S$ of size $n = $ poly over cyclotomic rings $\mathcal{R} = \mathbb{Z}[\zeta_{p^\ell}]$ for prime $p$, we construct Schnorr-like lattice-based proofs of knowledge for the SIS relation ${A} \cdot \vec{x} = s \cdot \vec{y} \bmod q$ with $O(1/n)$ knowledge error, and $s = 1$ in case $p = $ poly. Our technique slots naturally into the lattice Bulletproof framework from Crypto'20, producing lattice-based succinct arguments for NP with better parameters.

We then give matching impossibility results constraining $n$ relative to $s$, which suggest that our Bulletproof-compatible protocols are optimal unless fundamentally new techniques are discovered. Noting that the knowledge error of lattice Bulletproofs is \(\Omega(\log k/n)\) for witnesses in \(\mathcal{R}^k\) and subtractive set size \(n\), our result represents a barrier to practically efficient lattice-based succinct arguments in the Bulletproof framework.

Beyond these main results, the concept of $(s,t)$-subtractive sets bridges group-based threshold cryptography to lattice settings, which we demonstrate by relating it to distributed pseudorandom functions.