ABSTRACT. As both notions employ the same key-evolution paradigm, Bellare et al.(CANS 2017) study combining forward security with leakage resilience. The idea is for forward security to serve as a hedge in case at some point the full key gets exposed from the leakage. In particular, Bellare et al. combine forward security with continual leakage resilience, dubbed FS+CL. Our first result improves on Bellare et al.’s FS+CL secure PKE scheme by building one from any continuous leakage-resilient binary-tree encryption (BTE) scheme; in contrast, Bellare et al. require extractable witness encryption. Our construction also preserves leakage rate of the underlying BTE scheme and hence, in combination with existing CL-secure BTE, yields the first FS+CL secure encryption scheme with optimal leakage rate from standard assumptions.

We next explore combining forward security with other notions of leakage resilience. Indeed, as argued by Dziembowski et al. (CRYPTO 2011), it is desirable to have a deterministic key-update procedure, which FS+CL does not allow for arguably pathological reasons. To address this, we combine forward security with entropy-bounded leakage (FS+EBL). We construct FS+EBL non-interactive key exchange (NIKE) with deterministic key update based on indistinguishability obfuscation (iO), and DDH or LWE. To make the public keys constant size, we rely on the Superfluous Padding Assumption (SuPA) of Brzuska and Mittelbach (ePrint 2015) without auxiliary information, making it more plausible. SuPA notwithstanding, the scheme is also the first FS-secure NIKE from iO rather than multilinear maps. We advocate a future research agenda that uses FS+EBL as a hedge for FS+CL, whereby a scheme achieves the latter if key-update randomness is good and the former if not.

ABSTRACT. We propose an anonymous broadcast authentication (ABA) scheme to simultaneously control massive numbers of devices within practical resources. As a theoretical foundation, we find a barrier to constructing an ABA working with a large number of devices: there is a trilemma between (i) security, (ii) ciphertext length, and (iii) freedom in the selection of target devices. For practical use, we propose ABAs with a ciphertext size of O(log N) where N is the number of target devices while we impose a certain restriction on (iii). We provide an ABA template and instantiate it into a specific scheme from the learning with errors (LWE) problem. Then, we give an estimation of the size and timing resources.

ABSTRACT. In PKC 2014, a policy-based signature (PBS) scheme was proposed by Bellare and Fuchsbauer in which a signer can only sign messages conforming to some policy specified by an issuing authority and the produced signatures are verified under the issuer’s public key. PBS construction supports the delegation of signing policy keys with possible restrictions to the original policy. Although the PBS scheme is meant to limit the signing privileges of the scheme’s users, singers could easily abuse their signing rights without being held accountable since PBS does not have a tracing capability, and a signing policy key defines a policy that should be satisfied by the message only. In this work, we build on PBS and propose a traceable policy-based signature scheme (TPBS) where we employ a rerandomizable signature scheme, a digital signature scheme, and a zero-knowledge proof system as its building blocks. TPBS introduces the notion of identity keys that are used with the policy keys for signing. Thus it achieves traceability without compromising the delegatability feature of the PBS scheme. Additionally, TPBS ensures non-frameability under the assumption of a corrupted tracing authority. We define and formally prove the security notions of the generic TPBS scheme. Finally, we propose an instantiation of TPBS utilizing the Pointcheval-Sanders rerandomizable signature scheme, Abe, et al.’s structure-preserving signature scheme, and Groth-Sahai NIZK system, and analyze its efficiency.

ABSTRACT. In the Learning with Errors (LWE) problem we are given a matrix A ∈ Z_q^{N×N} and a target vector t ∈ Z_q^N such that there exists small-norm s, e ∈ Z_q^N satisfying A · s = t + e mod q. Modern cryptosystems often sample s, e from narrow distributions that take integer values in a small range [−η, η]. KYBER and DILITHIUM both choose η = 2 and η = 3 using either a Centered Binomial distribution (KYBER), or a uniform distribution (DILITHIUM). In this work, we address the fundamental question how hard the enumeration of LWE secret keys for narrow distributions with η ≤ 3 is. At Crypto 21, May proposed a representation-based algorithm for enumerating ternary keys, i.e. the case η = 1, with a fixed number of ±1 entries. In this work, we extend May’s algorithm in several ways. First, we show how to deal with keys sampled from a probability distribution as in many modern systems like KYBER and DILITHIUM, rather than with keys having a fixed number of entries. Second, we generalize to larger values η = 2, 3, thereby achieving asymptotic key guess complexities that are not far off from lattice estimates. E.g. for KYBER’s Centered Binomial distribution we achieve heuristic time/memory complexities of O(2^{0.36N}) for η = 2, and O(2^{0.37N}) for η = 3. For DILITHIUM’s uniform distribution we achieve heuristic complexity O(2^{0.38N}) for η = 2. Let S be the Shannon entropy of KYBER/DILITHIUM keys. Then our algorithms runs in time about S^{1/6}, which greatly improves over the standard combinatorial Meet-in-the-Middle attack with complexity S^{1/2}. Our results also compare well to current lattice asymptotics of 2^{0.29β}, where the lattice parameter β is roughly of size 4/5N. Thus, our analysis supports that KYBER secret keys are indeed hard to enumerate. Yet, we find it remarkable that a purely combinatorial key search is almost competitive with highly evolved lattice sieving techniques.

ABSTRACT. Recent works have revisited blockcipher structures to achieve MPC- and ZKP-friendly designs. In particular, Albrecht et al. (EUROCRYPT 2015) first pioneered using a novel structure SP networks with partial non-linear layers (P-SPNs) and then (ESORICS 2019) repopularized using multi-line generalized Feistel networks (GFNs). In this paper, we persist in exploring symmetric cryptographic constructions that are conducive to the applications such as MPC. In order to study the minimization of non-linearity in Type-II Generalized Feistel Networks, we generalize the (extended) GFN by replacing the bit-wise shuffle in a GFN with the stronger linear layer in P-SPN and introducing the key in each round. We call this scheme Generalized Extended Generalized Feistel Network (GEGFN). When the block-functions (or S-boxes) are public random permutations or (domain-preserving) functions, we prove CCA security for the 5-round GEGFN. Our results also hold when the block-functions are over the prime fields F_p, yielding blockcipher constructions over (F_p)^*.

ABSTRACT. We show the approximate pairwise orthogonality of a class of functions formed by a single AES output bit under the assumption that all of its round keys except the initial one are independent. This result implies the hardness of learning AES encryption (and decryption) with gradient-based methods. The proof relies on the Boas-Bellman type of inequality in inner-product spaces.

ABSTRACT. The global lockdown imposed during the Covid-19 pandemic has resulted in significant social and economic challenges. In an effort to reopen economies and simultaneously control the spread of the disease, the implementation of contact tracing and digital vaccine passport technologies has been introduced. While contact tracing methods have been extensively studied and scrutinized for security concerns through numerous publications, vaccine passports have not received the same level of attention in terms of defining the problems they address, establishing security requirements, or developing efficient systems. Many of the existing methods employed currently suffer from privacy issues. This work introduces PPass, an advanced digital vaccine passport system that prioritizes user privacy. We begin by outlining the essential security requirements for an ideal vaccine passport system. To address these requirements, we present two efficient constructions that enable PPass to function effectively across various environments while upholding user privacy. By estimating its performance, we demonstrate the practical feasibility of PPass. Our findings suggest that PPass can efficiently verify a passenger’s vaccine passport in just 7 milliseconds, with a modest bandwidth requirement of 480KB

ABSTRACT. Android permission is a system of safeguards designed to restrict access to potentially sensitive data and privileged components. While third-party applications are restricted from accessing privileged resources without appropriate permissions, mobile browsers are treated by Android OS differently. Android mobile browsers are the privileged applications that have access to sensitive data based on the permissions implicitly granted to them. In this paper, we present a novel attack approach that allows a permission-less app to access sensitive data and privileged resources using mobile browsers as a proxy. We demonstrate the effectiveness of our proxy attack on 8 mobile browsers across 12 Android devices ranging from Android 8.1 to Android 13. Our findings show that all current versions of Android mobile browsers are susceptible to this attack. The findings of this study highlight the need for improved security measures in Android browsers to protect against privilege escalation and privacy leakage

ABSTRACT. The California Consumer Privacy Act (CCPA) secures the right to Opt-Out for consumers in California. However, websites may implement complex consent mechanisms that potentially do not capture the user’s true choices. We investigated the user choices in Cookie Consent Banner of US residents, the plurality of whom were from California, through an online experiment of 257 participants and compared the results with how they perceived to these Cookie Consent Banner. Our results show a contradiction between how often participants self-report their Opt-Out rates and their actual Opt-Out rate when interacting with a complex, CCPA-compliant website. This discrepancy expands the context with which modern websites may implement the CCPA without providing users sufficient information or instruction on how to successfully Opt-Out. We further elaborate on how US residents respond to and perceive the GDPR-like Opt-In model. Our results indicate that even though very few consumers actually exercised their right to Opt-Out, the majority of US consumers desire more transparent privacy policies that the current implementation of CCPA on websites lacks.

ABSTRACT. Card-based cryptography uses a physical deck of cards to achieve secure computations. To evaluate the performance of card-based protocols, the numbers of helping cards and shuffles required to execute are often used as evaluation metrics. In this paper, we focus on n-input AND protocols that use at most two helping cards, and investigate how many shuffles suffice to construct such a two-helping-card AND protocol. Since the Mizuki-Sone two-input AND protocol uses two helping cards and it can be repeatedly applied n-1 times to perform a secure n-input AND computation, an obvious upper bound on the number of required shuffles is n-1. In this paper, to obtain better bounds (than n-1), we consider making use of the “batching” technique, which was developed by Shinagawa and Nuida in 2020 to reduce the number of shuffles. Specifically, we first formulate the class of two-helping-card n-input AND protocols obtained by applying the batching technique to the Mizuki–Sone AND protocol, and then show n-input AND protocols requiring the minimum number of shuffles (among the class) for the case of 2≤n≤500.

ABSTRACT. This paper shows a free-XOR technique in card-based garbled circuits. Card-based cryptographic protocols were proposed as a secure multiparty computation using physical cards instead of computers. They can be used when users cannot trust software on computers. Shinagawa and Nuida proposed card-based garbled circuits that compute any Boolean functions using a single shuffle. Their protocol uses $24g+2n$ cards, where $g$ is the number of gates and $n$ is the number of inputs. Tozawa et al. reduced the number of cards to $8g+2n$. This paper introduces the free-XOR technique for standard garbled circuits to card-based garbled circuits. It is unnecessary to prepare a garbled table for XOR gates. The number of cards is reduced to $8g_1+2g_2+2n$, where $g_1$ is the number of gates other than XOR and $g_2$ is the number of XOR gates whose output is used as a final output. The card-based garbled circuits proposed by Shinagawa and Nuida have one restriction the final outputs cannot be used for inputs to the other gates. This paper eliminates the restriction with two different techniques.