Publication

Undeniable Signatures Based on Characters: How to Sign with One Bit

Serge Vaudenay
2004
Conference Papers

Abstract

We present a new undeniable signature scheme which is based on the computation of characters. Our signature scheme offers the advantage of having an arbitrarily short signature. Its asymptotic complexity is attractive: the asymptotic complexity of all algorithms (even the key setup) are quadratic in the size of the modulus n in bits when the other parameters are fixed. The practical complexity can be quite low depending on parameter and variant choices. We present also a proof of security of our scheme containing the standard security requirements of an undeniable signature.

Official source

https://infoscience.epfl.ch/entities/publication/a8ef584a-9a7f-4b53-8c2a-e6c5cae2cd5e

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Serge Vaudenay
2004
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/a8ef584a-9a7f-4b53-8c2a-e6c5cae2cd5e

About this result

Related concepts (32)

Digital signature

A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature on a message gives a recipient confidence that the message came from a sender known to the recipient. Digital signatures are a standard element of most cryptographic protocol suites, and are commonly used for software distribution, financial transactions, contract management software, and in other cases where it is important to detect forgery or tampering.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used.

Related publications (3)

Undeniable Signatures Based on Characters: How to Sign with One Bit

Chat with Graph Search

Assessing wind dynamics and turbine power at Princess Elisabeth station, Antarctica, using Doppler wind LiDAR and vertical array anemometers

MATHICSE Technical Report : Fast simulations of patient-specific haemodynamics of coronary artery bypass grafts based on a Pod-Galerkin method and a vascular shape parametrization

Numerical modelling of potential and current distributions in a bipolar electrolytic cell