Re: [CFRG] EdDSA and ECDLP
Natanael <natanael.l@gmail.com> Sun, 27 November 2022 13:58 UTC
Return-Path: <natanael.l@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 11029C14F743 for <cfrg@ietfa.amsl.com>; Sun, 27 Nov 2022 05:58:23 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.097
X-Spam-Level:
X-Spam-Status: No, score=-2.097 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([50.223.129.194]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 8v2_tOYIyz1U for <cfrg@ietfa.amsl.com>; Sun, 27 Nov 2022 05:58:22 -0800 (PST)
Received: from mail-ed1-x529.google.com (mail-ed1-x529.google.com [IPv6:2a00:1450:4864:20::529]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id AA531C14E514 for <cfrg@irtf.org>; Sun, 27 Nov 2022 05:58:22 -0800 (PST)
Received: by mail-ed1-x529.google.com with SMTP id z18so12184536edb.9 for <cfrg@irtf.org>; Sun, 27 Nov 2022 05:58:22 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=7jfFzZb0c/08DpYT9/23VA8g/yVYm8XOqGGbBYsQmtQ=; b=SuoI+5i18DcermtFBqjsV/eB4OgABmYUmdY81EGovpQnWUk8SdPS1IppJJj59CB++7 5jgE5FEOmw4b6YyC23NRQd5Ja//Wuc89jBG+A2jTkQ8LOue3lOjrrMF3jrJbJgG22tuh 0UIhtGZXBWJmAJkpek5s4yDyC8JSzXCKuL8QexR9P+q0mGM1hzY6Mf4ZBY3qWlR44X4E zjJt5XRjjse4v2nvKoDEHTZ0ntVJ1MSqXz1UdIwKe9StwYfUV4XkIhDoA+K7F00GBlWh UU9PUHgo1X3Wp6ggo0o0VxdZdI2r0iEl3o6bigPLkYS36sONEyGh+EIYliOCDBjfC6o1 uLuw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=7jfFzZb0c/08DpYT9/23VA8g/yVYm8XOqGGbBYsQmtQ=; b=qragGhoBTVfYOxcWxCBcGhw/f/kmDnFAwu5VpGKQdm+YiV7hyzH1TTP9wsN19u5Q6U 6hQN+U2yPUTmtl8mQfgcjy5h581y9lPPNNUpsoz0g3Mh+3V6gZhv/N4VCzN9TG62zP+e uRiUdu6mbPGmyko2wYn9Fliy2UJJ/BknVOiKHNGcikK8Vo6JD2rgtB1zpwQNXnREWLds P3Q30G/W8onAt+5tkylpb8CvW1KnOAb5UnaLnRdaPDm9yXaxEgD6yA6FNQYic2h7DwQ+ SrRNlbB6ADwrscSj3E8fzI79UOW/hvI+KF0BUg1lbIRQHj5Muutb2OUynol5mPqZyQHM XzOA==
X-Gm-Message-State: ANoB5plcFG1ZIFw+Ed44Hm5ybFKF1ZOCOKTkUK58apONmtLUfdkixrO+ 97/WRBTz8UhnxD7vCYB2/CigWaHQPZjg6k2X9eHKhDVO7Z8=
X-Google-Smtp-Source: AA0mqf6A55W65MEj9TmHBOArPwTKLz/EH+yGLtVTJzOmLPNLiwoQ5GfaDpfafVm9RYUT3Ge3N9jbn5P5/eACWtiNDUM=
X-Received: by 2002:aa7:c042:0:b0:462:2f5a:8618 with SMTP id k2-20020aa7c042000000b004622f5a8618mr43967387edo.42.1669557500396; Sun, 27 Nov 2022 05:58:20 -0800 (PST)
MIME-Version: 1.0
References: <000001d9024b$21574330$6405c990$@x500.eu>
In-Reply-To: <000001d9024b$21574330$6405c990$@x500.eu>
From: Natanael <natanael.l@gmail.com>
Date: Sun, 27 Nov 2022 14:58:03 +0100
Message-ID: <CAAt2M18bgy+JZL_HwN2fRVSJZDXBAuTTu+c-HVwo7MGYgTinzg@mail.gmail.com>
To: Erik Andersen <era@x500.eu>
Cc: Cfrg <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000be4aa505ee742543"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/JX5PaIQA-RJzwbmoBnAQX9y2hd4>
Subject: Re: [CFRG] EdDSA and ECDLP
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sun, 27 Nov 2022 13:58:23 -0000
Den sön 27 nov. 2022 kl 11:29 skrev Erik Andersen <era@x500.eu>: > I do not really understand how to break EdDSA by solving the ECDLP. > > > > Many sources I can find say that the public key is generated as it is done > for ECDSA, i.e., the public key Q = [k]G, but that that is not how I read > RFC 8032 and NIST FIPS 186-5. Here the private key is hashed with an > algorithm that that produces a digest having a size twice the size of the > private key. Only the first half of the digest is used to generate the > public key and by solving the ECDLP you can only get half of the digest. > However, to generate a false signature, you also need the other half of the > digest, so that does not really help you. So, I am still wandering how a > quantum computer can break EdDSA. > Only VRF schemes (Verifiable Random Functions) are guaranteed to have this kind of property where each input maps only to exactly one output, while EdDSA is only "normatively" deterministic but it's not enforced or verifiable by anybody but the signer.
- [CFRG] EdDSA and ECDLP Erik Andersen
- Re: [CFRG] EdDSA and ECDLP Ilari Liusvaara
- Re: [CFRG] EdDSA and ECDLP Bas Westerbaan
- Re: [CFRG] EdDSA and ECDLP Natanael