Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
That’s AmorE: Amortized Efficiency for Pairing Delegation
No full textOver two decades since their introduction in 2005, all major verifiable pairing delegation protocols for public inputs have been designed to ensure unconditional security. However, we note that a delegation protocol involving only ephemeral secret keys in the public view can achieve everlasting security, provided the server is unable to produce a pairing forgery within the protocol\u27s execution time. Thus, computationally bounding the adversary\u27s capabilities during the protocol\u27s execution may be more reasonable when the goal is to achieve significant efficiency gains for the delegating party. This consideration is particularly relevant given the continuously evolving computational costs associated with pairing computations and their ancillary blocks, which creates an ever-changing landscape for what constitutes efficiency in pairing delegation protocols. With the goal of fulfilling both efficiency and everlasting security, we present AmorE, a protocol equipped with an adjustable security and efficiency parameter for sequential pairing delegation, which achieves state-of-the-art Amortized Efficiency in terms of the number of pairing computations. For example, delegating batches of 10 pairings on the BLS48-575 elliptic curve via our protocol costs to the client, on average, less than a single scalar multiplication in per delegated pairing, while still ensuring at least 40 bits of statistical security
VeriSSO: A Privacy-Preserving Legacy-Compatible Single Sign-On Protocol Using Verifiable Credentials
Get PDFSingle Sign-On (SSO) is a popular authentication mechanism enabling a user to access different online services (called Relying Parties, or RPs) with a single login credential obtained from the Identity Provider (IdP). Despite its convenience, SSO schemes represented by the OIDC standard faces significant privacy concerns---the IdP can track users across different RPs; colluding RPs may share data to find linkage of user access. Recent anonymous credential-based SSO solutions provide a promising direction to enhancing user privacy and mitigating IdP single-point failure; however, they fail to support RP authentication, an important security property of the incumbent SSO workflow, and require RPs to perform non-trivial cryptographic verification.
This paper introduces VeriSSO, a novel privacy-preserving SSO protocol based on verifiable credentials (VC) that supports RP authentication and is fully compatible with the incumbent SSO workflow. The key intuition is to employ a committee of independent authentication servers (i) to bind RP authentication to VC-based user verification and (ii) to issue identity tokens in a threshold manner, which crucially ensures RP authentication and user unlinkability without IdP involvement or reliance on a trusted central party. Our scheme allows RPs to continue using their existing signature-based identity token verification routine and supports lawful de-anonymization, providing user accountability for misbehavior. Our experiment shows the feasibility and efficiency and VeriSSO, with one SSO workflow completed within 30 milliseconds
On the Estonian Internet Voting System, IVXV, SoK and Suggestions
Get PDFThe Estonian i-voting experience is probably the richest to analyze; a country that is considered a pioneer in digitizing both the government and private sector since 2001 followed by online internet voting (i-voting) in 2005. However, there are still some complaints submitted, critics and remarks to consider about the IVXV system. In this paper, we introduce a Systemization of Knowledge of the Estonian IVXV i-voting system and propose some added security enhancements. The presented SoK discusses applications implemented by election observers in 2023 & 2024 elections, which, to our knowledge, have never been mentioned and/or analyzed in the academia before. We also point out to unnoticed automated formal verification analysis of IVXV; the researchers discovered a privacy attack that we show extendable to a possible large scale encrypted vote copying. In addition, we identify and analyze recent fixes and improvements in the June 2024 version used in the European Parliament elections connecting them to their academic sources. Finally, we discuss the current system status, propose our own suggestions to some remaining vulnerabilities, then raise the inevitable question of the approaching quantum threat
Blind Brother: Attribute-Based Selective Video Encryption
Get PDFThe emergence of video streams as a primary medium for communication and the demand for high-quality video sharing over the internet have given rise to several security and privacy issues, such as unauthorized access and data breaches. To address these limitations, various Selective Video Encryption (SVE) schemes have been proposed, which encrypt specific portions of a video while leaving others unencrypted. The SVE approach balances security and usability, granting unauthorized users access to certain parts while encrypting sensitive content. However, existing SVE schemes adopt an all-or-nothing coarse-grain encryption approach, where a user with a decryption key can access all the contents of a given video stream. This paper proposes and designs a fine-grained access control-based selective video encryption scheme, ABSVE, and a use-case protocol called \protocol. Our scheme encrypts different identified Regions of Interest (ROI) with a unique symmetric key and applies a Ciphertext Policy Attribute Based Encryption (CP-ABE) scheme to tie these keys to specific access policies. This method provides multiple access levels for a single encrypted video stream. Crucially, we provide a formal syntax and security definitions for ABSVE, allowing for rigorous security analysis of this and similar schemes -- which is absent in prior works. Finally, we provide an implementation and evaluation of our protocol in the Kvazaar HEVC encoder. Overall, our constructions enhance security and privacy while allowing controlled access to video content and achieve comparable efficiency to compression without encryption
Exploring General Cyclotomic Rings in Torus-Based Fully Homomorphic Encryption
Get PDFIn this article, we develop algebraic tools for fully homomorphic encryption over the torus in the setting of general composite cyclotomic indices. Working in cyclotomic rings and fields beyond the power-of-two case, we reframe and optimize key primitives—reduction modulo
, homomorphic evaluation of trace operators, blind extraction and the blind rotation used in bootstrapping—using systematic duality and trace techniques. Our approach yields a simpler, more modular description of bootstrapping, including a new systematic treatment
of so-called “nega-cyclicity” conditions and featuring an optimal reduction of the input noise, and provides sharp error bounds showing that bootstrap noise growth remains mild compared with the classical power-of-two instantiation. In addition, we introduce a new fast
packing strategy. These results broaden the algebraic toolkit for torus-based FHE and pave the way for new cryptographic constructions and applications
Practical Semi-Open Chat Groups for Secure Messaging Applications
Get PDFChat groups in secure messaging applications such as Signal, Telegram, and Whatsapp are nowadays used for rapid and widespread dissemination of information to large groups of people. This is common even in sensitive contexts, associated with the organisation of protests, activist groups, and internal company dialogues. Manual administration of who has access to such groups quickly becomes infeasible, in the presence of hundreds or thousands of members.
We construct a practical, privacy-preserving reputation system, that automates the approval of new group members based on their reputation amongst the existing membership. We demonstrate security against malicious adversaries in a single-server model, with no further trust assumptions required. Furthermore, our protocol supports arbitrary reputation calculations while almost all group members are offline (as is likely). In addition, we demonstrate the practicality of the approach via an open-source implementation. For groups of size 50 (resp. 200), an admission process on a user that received 40 (resp. 80) scores requires 1312.2 KiB (resp. 5239.4 KiB) of communication, and 3.3s (resp. 16.3s) of overall computation on a single core. While our protocol design matches existing secure messaging applications, we believe it can have value in distributed reputation computation beyond this problem setting
Practical Key Collision on AES and Kiasu-BC
Get PDFThe key collision attack was proposed as an open problem in key-committing security in Authenticated Encryption (AE) schemes like and . In ASIACRYPT 2024, Taiyama et al. introduce a novel type of key collision—target-plaintext key collision () for . Depending on whether the plaintext is fixed, can be divided into and , which can be directly converted into collision attacks and semi-free-start collision attacks on the Davies-Meyer () hashing mode.
In this paper, we propose a new rebound attack framework leveraging a time-memory tradeoff strategy, enabling practical key collision attacks with optimized complexity. We also present an improved automatic method for finding \textit{rebound-friendly} differential characteristics by controlling the probabilities in the inbound and outbound phases, allowing the identified characteristics to be directly used in key collision attacks. Through our analysis, we demonstrate that the 2-round attack proposed by Taiyama et al. is a attack in fact, while attacks are considerably more challenging than attacks. By integrating our improved automatic method with a new rebound attack framework, we successfully identify a new differential characteristic for the 2-round attack and develope the first practical attack against 2-round . Additionally, we present practical attacks against 5-round and 3-round , along with a practical attack against 6-round . Furthermore, we reduce time complexities for and attacks on other variants
Group Key Progression: Strong Security for Shared Persistent Data
Get PDFEnd-to-end encryption allows data to be outsourced and stored on an untrusted server, such as in the cloud, without compromising data privacy. In the setting when this data is shared between a group of users, members also all share access to the same static key material used for data encryption. When the group membership changes, access control is only enforced by the server: security breaches or compelled disclosure would allow even a removed member to decrypt the current shared data.
We propose to move away from static keys and instead use a group key progression (GKP) scheme, a novel primitive that enables a dynamic group of users to agree on a persistent sequence of keys while keeping a compact local state. GKP ensures that group members can only derive keys within a certain interval of the sequence, a notion that we call interval access control (IAC), and also provide post-compromise security. Our GKP construction, called Grappa, combines continuous group key agreement (CGKA, by Alwen et al., 2020) with a new abstraction called interval scheme. The latter is a symmetric-key primitive that can derive a sequence of keys from a compact state while preserving IAC. We explore different interval scheme constructions and simulate their storage and communication costs when used in group settings. The most efficient of them is a generalization of dual key regression (Shafagh et al., 2020), which we formalize and prove secure. Overall, our protocols offer a practical and robust solution to protect persistent data shared by a group
How to Make Any Computational Secret Sharing Scheme Adaptively Secure
Get PDFSecret sharing (SS) is a foundational cryptographic primitive with diverse applications, including secure multiparty computation and conditional disclosure of secrets. While traditional schemes have primarily emphasized information-theoretic security, recent advancements have increasingly leveraged computational assumptions to achieve more efficient constructions and support broader access policies. Despite these successes, most existing computational secret sharing (CSS) schemes are limited to a static security model, where adversaries must commit to their choice of corrupted participants at the outset. A critical challenge in CSS lies in achieving adaptive security, where adversaries can dynamically select participants to corrupt, better reflecting real-world threat models.
In this paper, we present a novel transformation that converts any statically secure CSS scheme into an adaptively secure one while preserving the original access policy and computational assumptions, providing a framework for bridging the gap between static and adaptive security. Our construction introduces a multiplicative share size overhead of where is the number of parties. Additionally, we explore trade-offs in efficiency and security, offering more efficient adaptive CSS constructions for specific, restricted policy classes. This work addresses key limitations in the current landscape of CSS and paves the way for broader adoption of adaptively secure secret sharing in cryptographic applications
NIZK Amplification via Leakage-Resilient Secure Computation
Get PDFSuppose that we are given a weak \emph{Non-Interactive Zero-Knowledge} (NIZK) proof system for NP with non-negligible soundness and zero-knowledge errors, denoted by and , respectively. Is it possible to to reduce these errors to a negligible level? This problem, known as NIZK amplification, was introduced by Goyal, Jain, and Sahai (Crypto\u2719) and was further studied by Bitansky and Geier (Crypto\u2724).
The latter work provides amplification theorems for proofs and arguments, assuming the existence of one-way functions and public-key encryption, respectively. Unfortunately, their results only apply when the security level, , is a constant bounded away from zero. Amplifying NIZK with an inverse polynomial security level remains an open problem and was stated as the main open question in both works.
In this work, we resolve the NIZK amplification problem and show how to amplify any non-trivial NIZK proof system that has a noticeable, inverse-polynomial level of security. As in previous works, we amplify proofs and arguments assuming the existence of one-way functions and public-key encryption, respectively. Furthermore, assuming the existence of collision-resistant hash functions, we preserve, for the first time, properties such as statistical zero-knowledge and proof succinctness.
Our main technical contribution is a new \emph{leakage-resilient secure multiparty} protocol that computes any public-output functionality with information-theoretic security against an adversary that corrupts an arbitrary subset of parties and obtains bounded leakage from each honest party. Our protocol operates in the pairwise correlated randomness model. Previous works relied on stronger setup assumptions in the form of -wise correlations and either supported a smaller corruption threshold or suffered from an exponential dependency on the number of parties. To transform our protocol into a NIZK amplifier, we introduce a new intermediate notion of \emph{leakage-resilient NP secret sharing}, that may be of independent interest