International Association
for Cryptologic Research

We apply Siegenthaler's construction, along with several techniques, to classify all $(n-4)$-resilient Boolean functions with $n$ variables, for all values of $n \geq 4$, up to extended variable-permutation equivalence. We show that, up to this equivalence, there are only 761 functions for any $n$ larger than or equal to 10, and for smaller values of $n$, i.e., for $n$ increasing from 4 to 9, there are 58, 256, 578, 720, 754, and 760 functions, respectively. Furthermore, we classify all 1-resilient 6-variable Boolean functions and show that there are 1035596784 such functions up to extended variable-permutation equivalence.

In this note, we identify a minor flaw in the design of the XOCB mode, presented at Eurocrypt '23. This vulnerability enables trivial tag forgeries and arises from the padding applied to messages. We examine the security proof and pinpoint the presence of the flaw within it. Furthermore, we propose a simple fix for this issue, drawing upon the features of OCB3, and discuss the implications of this modification on the proof of security.

Hash-based signatures are a type of Digital Signature Algorithms that are positioned as one of the most solid quantum-resistant constructions. As an example SPHINCS+, has been selected as a standard during the NIST Post-Quantum Cryptography competition. However, hash-based signatures suffer from two main drawbacks: signature size and slow signing process. In this work, we give a solution to the latter when it is used in a mobile device. We take advantage of the fact that hash-based signatures are highly parallelizable. More precisely, we provide an implementation of SPHINCS+ on the Snapdragon 865 Mobile Platform taking advantage of its eight CPUs and their vector extensions. Our implementation shows that it is possible to have a speed-up of 15 times when compared to a purely sequential and non-vectorized implementation. Furthermore, we evaluate the performance impact of side-channel protection using vector extensions in the SPHINCS+ version based on SHAKE.

Witness Encryption is a holy grail of cryptography that remains elusive. It asks that a secret is only revealed when a particular computational problem is solved. Modern smart contracts and blockchains make assumptions of “honest majority”, which allow for a social implementation of Witness Encryption. The core idea is to make use of a partially trusted committee to carry out the responsibilities mandated by these functionalities – such as keeping the secret private, and then releasing it publicly after a solution to the computational puzzle is presented. We implement Witness Encryption (with public witness security) in the form of an open source composable smart contract that can be utilized as an oracle by others within the broader DeFi ecosystem. We devise a cryptoeconomic scheme to incentivize honest participation, and analyze its security under the honest majority and rational majority settings. We conclude by measuring and optimizing gas costs and illustrating the practicality of our scheme.

This paper makes a comprehensive study of two important strategies for polynomial hashing over a prime order field $\mathbb{F}_p$, namely usual polynomial based hashing and hashing based on Bernstein-Rabin-Winograd (BRW) polynomials, and the various ways to combine them. Several hash functions are proposed and upper bounds on their differential probabilities are derived. Concrete instantiations are provided for the primes $p=2^{127}-1$ and $p=2^{130}-5$. A major contribution of the paper is an extensive 64-bit implementation of all the proposed hash functions in assembly targeted at modern Intel processors. The timing results suggest that using the prime $2^{127}-1$ is significantly faster than using the prime $2^{130}-5$. Further, a judicious mix of the usual polynomial based hashing and BRW-polynomial based hashing can provide a significantly faster alternative to only usual polynomial based hashing. In particular, the timing results of our implementations show that our final hash function proposal for the prime $2^{127}-1$ is much faster than the well known Poly1305 hash function defined over the prime $2^{130}-5$, achieving speed improvements of up to 40%.

The Cybersecurity Research Group is looking to expand. There is a job opportunity for a post-doctoral researcher who wishes to work in applied cryptography, including topics such as leakage resilience, secure implementations, side channels, or primitives for PETs, ZK, etc. The job includes a small teaching load (4hrs per week during term time), and it requires willingness to collaborate with members of the Digital Age Research Centre (across typical disciplinary boundaries). The starting salary is just over 60k (paid in 14 instalments), the starting date is negotiable (ideally no later than September 2023).

Closing date for applications:

Contact: Elisabeth.OswaldATaau.at

More information: https://jobs.aau.at/en/job/senior-scientist-all-genders-welcome-6/

Event date: 25 July to 29 July 2023
Submission deadline: 15 May 2023
Notification: 15 May 2023

Event date: 28 August to 30 August 2023
Submission deadline: 11 May 2023
Notification: 26 June 2023

Event date: 3 October to 6 October 2023
Submission deadline: 15 May 2023

Event date: 23 July to 25 July 2023
Submission deadline: 12 May 2023
Notification: 1 June 2023

Event date: 2 January to 7 January 2024
Submission deadline: 30 June 2023
Notification: 30 September 2023

With the escalating demand for lightweight ciphers as well as side channel protected implementation of those ciphers in recent times, this work focuses on two aspects. First, we present a tool for automating the task of finding a Threshold Implementation (TI) of a given Substitution Box (SBox). Our tool returns `with decomposition' and `without decomposition' based TI. The `with decomposition' based implementation returns a combinational SBox; whereas we get a sequential SBox from the `without decomposition' based implementation. Despite being high in demand, it appears that this kind of tool has been missing so far. Second, we show an algorithmic approach where a given cipher implementation can be tweaked (without altering the cipher specification) so that its TI cost can be significantly reduced. We take the PRESENT cipher as our case study (our methodology can be applied to other ciphers as well). Indeed, we show over 31 percent reduction in area and over 52 percent reduction in depth compared to the basic threshold implementation.

Secure Machine Learning as a Service is a viable solution where clients seek secure delegation of the ML computation while protecting their sensi- tive data. We propose an efficient method to se- curely evaluate deep standard convolutional neu- ral networks based on CKKS fully homomorphic encryption, in the manner of batch inference. In this paper, we introduce a packing method called Channel-by-Channel Packing that maximizes the slot compactness and single-instruction-multiple- data capabilities in ciphertexts. Along with fur- ther optimizations such as lazy rescaling, lazy Baby-Step Giant-Step, and ciphertext level man- agement, we could significantly reduce the com- putational cost of standard ResNet inference. Sim- ulation results show that our work has improve- ments in amortized time by 5.04× (from 79.46s to 15.76s) and 5.20×(from 455.56s to 87.60s) for ResNet-20 and ResNet-110, compared to the pre- vious best results, resp. We also got a dramatic reduction in memory usage for rotation keys from several hundred GBs to 6.91GB, which is about 38× smaller than the previous result.

Homomorphic encryption can perform calculations on encrypted data, which can protect the privacy of data during the usage of data. Functional Bootstraps algorithm proposed by I. Chillotti et al. can compute arbitrary functions represented as lookup table whilst bootstrapping, but the computational efficiency of F unctional Bootstraps with large lookup table or highly precise functions is not high enough. To tackle this issue, we propose a new Tree-BML algorithm. Our Tree-BML algorithm accelerates the computation of F unctional Bootstraps with large LUT by compressing more LWE ciphertexts to a TRLWE ciphertext and utilizing the PBSmanyLUT algorithm which was proposed by I. Chillotti et al. in 2021. The Tree-BML algorithm reduces the running time of LUT computation by 72.09% compared to Tree-based method(Antonio Guimarães et al., 2021). Additionally, we introduce a new TLWE-to-TRLWE Packing Key Switching algorithm which reduces the storage space required and communication overhead of homomorphic encryption algorithm by only generating one of those key-switching key ciphertexts of polynomials with the same non-zero coefficient values but only those values located in different slots. Our algorithm reduces the key-switching key size by 75% compared to Base-aware TLWE-to-TRLWE Key Switching algorithm. Finally, we obtained that our algorithms does not introduce new output error through theoretical and experiment result.

A fundamental result dating to Ligero (CCS '17) establishes that each fixed linear block code exhibits proximity gaps with respect to the collection of affine subspaces, in the sense that each given subspace either resides entirely close to the code, or else contains only a small portion which resides close to the code. In particular, any given subspace's failure to reside entirely close to the code is necessarily witnessed, with high probability, by a uniformly randomly sampled element of that subspace. We investigate a variant of this phenomenon in which the witness is not sampled uniformly from the subspace, but rather from a much smaller subset of it. We show that a logarithmic number of random field elements (in the dimension of the subspace) suffice to effect an analogous proximity test, with moreover only a logarithmic (multiplicative) loss in the possible prevalence of false witnesses. We discuss applications to recent noninteractive proofs based on linear codes, including Brakedown and Orion (CRYPTO '22).

We introduce the notion of publicly auditable functional encryption (PAFE). Compared to standard functional encryption, PAFE operates in an extended setting that includes an entity called auditor, besides key-generating authority, encryptor, and decryptor. The auditor requests function outputs from the decryptor and wishes to check their correctness with respect to the ciphertexts produced by the encryptor, without having access to the functional secret key that is used for decryption. This is in contrast with previous approaches for result verifiability and consistency in functional encryption that aim to ensure decryptors about the legitimacy of the results they decrypt. We propose four different flavors of public auditability with respect to different sets of adversarially controlled parties (only decryptor, encryptor-decryptor, authority-decryptor, and authority-encryptor-decryptor) and provide constructions for building corresponding secure PAFE schemes from standard functional encryption, commitment schemes, and non-interactive witness-indistinguishable proof systems. At the core of our constructions lies the notion of a functional public key, that works as the public analog of the functional secret key of functional encryption and is used for verification purposes by the auditor. Crucially, in order to ensure that these new keys cannot be used to infer additional information about plaintext values (besides the requested decryptions by the auditor), we propose a new indistinguishability-based security definition for PAFE to accommodate not only functional secret key queries (as in standard functional encryption) but also functional public key and decryption queries. Finally, we propose a publicly auditable multi-input functional encryption scheme (MIFE) that supports inner-product functionalities and is secure against adversarial decryptors. Instantiated with existing MIFE using ``El Gamal''-like ciphertexts and Σ-protocols, this gives a lightweight publicly auditable scheme.

Encrypted computation has over the past thirty years, turned into one of the holy grails of modern cryptography especially with the advent of cloud computing. Modern cryptographic techniques like Fully Homomorphic Encryption (FHE) allow arbitrary Boolean circuit evaluation with encrypted inputs. However, the prohibitively high computation and storage overhead coupled with high communication bandwidth of FHE severely limit its scalability in practical applications like real-time analytics or machine learning inference. In summary, the current cryptographic literature lacks robust and scalable methods for efficient encrypted computation in practical outsourced applications. In this work, we introduce a new approach for encrypted computation called SEC (Symmetric Encryption-based Computation) which offers fast Boolean circuit evaluation with optimal storage and communication overhead while scaling smoothly to real applications. SEC relies on an efficient Searchable Symmetric Encryption (SSE) construction to leverage the power of encrypted lookups in Boolean circuit evaluation. SEC is specifically suited for client-server systems, and the server, honest-but-curious receives the client’s encrypted inputs and outputs the encrypted evaluation result while leaking only benign information to the server. SEC essentially extends the capabilities of SSE schemes from searching over encrypted databases to arbitrary function evaluation over encrypted inputs. SEC supports Boolean function composition, allowing it to evaluate complex functions efficiently without blowing up storage overhead. SEC outperforms the state-of-the-art FHE, namely, Torus FHE (TFHE) scheme with an average 103× speed-up in basic Boolean gate evaluations. We present a prototype implementation of SEC and experimentally validate its practical efficiency. Our experiments show that SEC executes arbitrary depth Boolean circuit in a single round of communication between client and server with a significant improvement in performance than the fastest TFHE backends. We exemplify the applicability of our scheme by implementing one byte AES SBox using SEC and comparing the results with TFHE.

Let $C$ be an error-correcting code over a large alphabet $q$ of block length $n$, and assume that, a possibly corrupted, codeword $c$ is distributively stored among $n$ servers where the $i$th entry is being held by the $i$th server. Suppose that every pair of servers publicly announce whether the corresponding coordinates are ``consistent'' with some legal codeword or ``conflicted''. What type of information about $c$ can be inferred from this consistency graph? Can we check whether errors occurred and if so, can we find the error locations and effectively decode? We initiate the study of conflict-checkable and conflict-decodable codes and prove the following main results:

(1) (Almost-MDS conflict-checkable codes:) For every distance $d\leq n$, there exists a code that supports conflict-based error-detection whose dimension $k$ almost achieves the singleton bound, i.e., $k\geq n-d+0.99$. Interestingly, the code is non-linear, and we give some evidence that suggests that this is inherent. Combinatorially, this yields an $n$-partite graph over $[q]^n$ that contains $q^k$ cliques of size $n$ whose pair-wise intersection is at most $n-d\leq k-0.99$ vertices, generalizing a construction of Alon (Random Struct. Algorithms, '02) that achieves a similar result for the special case of triangles ($n=3$).

(2) (Conflict Decodable Codes below half-distance:) For every distance $d\leq n$ there exists a linear code that supports conflict-based error-decoding up to half of the distance. The code's dimension $k$ ``half-meets'' the singleton bound, i.e., $k=(n-d+2)/2$, and we prove that this bound is tight for a natural class of such codes. The construction is based on symmetric bivariate polynomials and is rooted in the literature on verifiable secret sharing (Ben-Or, Goldwasser and Wigderson, STOC '88; Cramer, Damgård, and Maurer, EUROCRYPT '00).

(3) (Robust Conflict Decodable Codes:) We show that the above construction also satisfies a non-trivial notion of robust decoding/detection even when the number of errors is unbounded and up to $d/2$ of the servers are Byzantine and may lie about their conflicts. The resulting conflict-decoder runs in exponential time in this case, and we present an alternative construction that achieves quasipolynomial complexity at the expense of degrading the dimension to $k=(n-d+3)/3$. Our construction is based on trilinear polynomials, and the algorithmic result follows by showing that the induced conflict graph is structured enough to allow efficient recovery of a maximal vertex cover.

As an application of the last result, we present the first polynomial-time statistical two-round Verifiable Secret Sharing (resp., three-round general MPC protocol) that remains secure in the presence of an active adversary that corrupts up to $t

Cryptocurrencies and decentralized platforms are rapidly gaining traction since Nakamoto's discovery of Bitcoin's blockchain protocol. These systems use Proof of Work (PoW) to achieve unprecedented security for digital assets. However, the significant power consumption and ecological impact of PoW are leading policymakers to consider stark measures against them and prominent systems to explore alternatives. But these alternatives imply stepping away from key security aspects of PoW.

We present Sprints, a blockchain protocol that achieves almost the same security guarantees as PoW blockchains, but with an order-of-magnitude lower ecological impact, taking into account both power and hardware. To achieve this, Sprints forces miners to mine intermittently. It interleaves Proof of Delay (PoD, e.g., using a Verifiable Delay Function) and PoW, where only the latter bares a significant resource expenditure. We prove that in Sprints the attacker's success probability is the same as that of legacy PoW. To evaluate practical performance, we analyze the effect of shortened PoW duration, showing a minor reduction in resilience (49% instead of 50%). We confirm the results with a full implementation using 100 patched Bitcoin clients in an emulated network.

An $n$-server information-theoretic \textit{Distributed Point Function} (DPF) allows a client to secret-share a point function $f_{\alpha,\beta}(x)$ with domain $[N]$ and output group $\mathbb{G}$ among $n$ servers such that each server learns no information about the function from its share (called a key) but can compute an additive share of $f_{\alpha,\beta}(x)$ for any $x$. DPFs with small key sizes and general output groups are preferred. In this paper, we propose a new transformation from share conversions to information-theoretic DPFs. By applying it to share conversions from Efremenko's PIR and Dvir-Gopi PIR, we obtain both an 8-server DPF with key size $O(2^{10\sqrt{\log N\log\log N}}+\log p)$ and output group $\mathbb{Z}_p$ and a 4-server DPF with key size $O(\tau \cdot 2^{6\sqrt{\log N\log\log N}})$ and output group $\mathbb{Z}_{2^\tau}$. The former allows us to partially answer an open question by Boyle, Gilboa, Ishai, and Kolobov (ITC 2022) and the latter allows us to build the first DPFs that may take any finite Abelian groups as output groups. We also discuss how to further reduce the key sizes by using different PIR, how to reduce the number of servers by resorting to statistical security or using nice integers, and how to obtain DPFs with $t$-security. We show the applications of the new DPFs by constructing new efficient PIR protocols with result verification.